Снижение размерности
Снижение размерности в задачах статистики, машинного обучения и теории информации — набор техник преобразования данных, направленных на уменьшение числа переменных путём выявления главных переменных[1]; в общем случае может быть разделено на отбор признаков и выделение признаков[2]. Снижение размерности наборов данных позволяет снизить требуемое время и требуемую память для обработки набора, улучшить скорость моделей машинного обучения за счёт удаления мультиколлинеарности, проще представить данные визуально (в двумерных и трёхмерных графиках).
Для наборов данных высокой размерности (на практике высоким считается число размерностей больше 10) снижение размерности обычно осуществляется перед применением метода ближайших соседей (англ. k-nearest neighbors algorithm, k-NN) с целью избежать эффект проклятия размерности[3]. Выделение признаков и снижение размерности может быть скомбинировано в один шаг с помощью метода главных компонент, линейного дискриминантного анализа, канонического корреляционного анализа или неотрицательного разложения матрицы как предварительный шаг с последующей группировкой с помощью K-NN на векторе признаков в пространстве редуцированной размерности. В машинном обучении этот процесс называется также малоразмерным вложением[4].
Для любых наборов данных высокой размерности (например, когда осуществляется поиск подобия в видеопотоке, ДНК данных или временном ряде высокой размерности) использование быстрого приближённого K-NN поиска с помощью методов «locality sensitive hashing», случайной проекции[англ.][5], «выжимок (sketches)»[6] (например, тензорный скетч) или других высокоразмерных техник поиска похожести из арсенала сверхбольших баз данных[уточнить] может оказаться единственно возможным вариантом.
Техника снижения размерности, которая иногда используется в нейронауках, — это максимальные информативные размерности[англ.], позволяет находить представления низкой размерности набора данных, сохраняющие как можно больше информации об исходных данных.
Отбор признаков
[править | править код]Метод отбора признаков пытается найти подмножество исходных переменных (которые называются признаками или атрибутами). Есть три стратегии — стратегия фильтра (например, накопление признаков[англ.]), стратегия обёртывания (например, поиск согласно точности) и стратегия вложения (выбираются признаки для добавления или удаления по мере построения модели, основанной на ошибках прогнозирования). См. также задачи комбинаторной оптимизации.
В некоторых случаях анализ данных, такой как регрессия или классификация, может быть осуществлён в редуцированном пространстве более точно, чем в исходном пространстве[7].
Проекция признаков
[править | править код]Проекция признаков преобразует данные из пространства высокой размерности к пространству малой размерности. Преобразование данных может быть линейным, как в методе главных компонент (МГК), но существует большое число техник нелинейного понижения размерности[англ.][8][9]. Для многомерных данных может быть использовано тензорное представление для снижения размерности через полилинейное обучение подпространств[англ.][10].
Метод главных компонент
[править | править код]Основная линейная техника для снижения размерности, метод главных компонент, осуществляет линейное отображение данных в пространство меньшей размерности таким образом, что дисперсия данных в малоразмерном представлении максимизируется. На практике строится матрица ковариации (а иногда корреляции) данных и вычисляются собственные вектора этой матрицы. Собственные вектора, соответствующие наибольшим собственным значениям (главные компоненты) теперь можно использовать для восстановления большей части дисперсии исходных данных. Более того, первые несколько собственных векторов часто можно интерпретировать в терминах крупномасштабного физического поведения системы. Исходное пространство (с размерностью, равной числу точек) редуцируется (с потерей данных, но с надеждой, что остаётся наиболее важная дисперсия) до пространства, натянутого на несколько собственных векторов.
Неотрицательное матричное разложение
[править | править код]Неотрицательное матричное разложение раскладывает неотрицательную матрицу на произведение двух неотрицательных матриц, которые имеют многообещающие средства в областях, где существуют только неотрицательные сигналы[11][12], таких как астрономия[13][14]. Неотрицательное матричное разложение хорошо известно ввиду правила мультипликативных корректировок (англ. multiplicative update rule) Ли и Сына[11], которое непрерывно разрабатывалось: включение неопределённости (англ. the inclusion of uncertainties)[13], учёт отсутствующих данных (англ. the consideration of missing data) и параллельные вычисления[15], последовательное построение (англ. sequential construction)[15], которое ведёт к стабильности и линейности НМР[14], а также другие корректировки.
Со стабильным компонентным базисом во время построения и линейным процессом моделирования последовательное неотрицательное матричное разложение (англ. sequential NMF)[15] способно сохранить поток околозвёздных структур прямого наблюдения (то есть наблюдаемых непосредственно, а не по косвенным признакам) в астрономии[14], как один из методов обнаружения экзопланет, особенно для околозвёздных дисков прямого наблюдения. По сравнению с МГК неотрицательное матричное разложение не удаляет среднее матриц, удаление которых приводит к нефизическим неотрицательным потокам, потому НМР способно сохранить больше информации, чем метод главных компонент, что продемонстрировал Рен с соавторами[14].
Ядерный метод главных компонент
[править | править код]Метод главных компонент может применяться другим способом при использовании ядерного трюка. Получающаяся техника способна построить нелинейные отображения, которые максимизируют дисперсию данных. Эта техника называется ядерным методом главных компонент[англ.].
Основанный на графах ядерный МГК
[править | править код]Другие многообещающие нелинейные техники — это техники обучения на базе многообразий[англ.], такие как Isomap[англ.], локально-линейное вложение[англ.] (ЛЛВ), локально-линейное вложение с использованием гессиана (англ. Hessian LLE), метод карт собственных значений лапласиана (англ. Laplacian Eigenmaps) и метод выравнивания локальных касательных пространств[англ.] (англ. local tangent space alignment, LTSA). Эти техники строят низкоразмерное представление данных, используя функцию цены, которая сохраняет локальные свойства данных и которую можно рассматривать как определение основанного на графах ядра для ядерного МГК.
Недавно были предложены техники, которые вместо определения фиксированного ядра пытаются изучить ядро с помощью полуопределённого программирования. Наиболее значительным примером такой техники является развертка по максимуму невязки (РМН). Центральная идея РМН состоит в точности в сохранении всех попарных расстояний между ближайшими соседями (в пространстве со скалярным произведением), максимизируя при этом расстояния между точками, не являющимися ближайшими соседями.
Альтернативный подход к сохранению соседства заключается в минимизации функции цены, которая измеряет расстояния во входном и выходном пространствах. Важные примеры таких техник: классическое многомерное шкалирование, которое идентично МГК; Isomap[англ.], которая использует геодезические расстояния в пространстве данных; метод диффузионных карт[англ.], который использует диффузионные расстояния в пространстве данных; стохастическое вложение соседей с t-распределением (англ. t-distributed stochastic neighbor embedding, t-SNE), который минимизирует разницу между парами точек, UMAP (Uniform Approximation and Projection), который минимизирует дивергенцию Кульбака-Лейблера между множествами в высоко- и низкоразмерном пространствах[16], и нелинейный анализ компонент (англ. Curvilinear Component Analysis, CCA).
Другой подход к нелинейному снижению размерности — через использование автокодировщиков, специального вида нейронных сетей прямого распространения (англ. feed-forward networks) с бутылочным (в виде бутылочного горлышка) скрытым слоем[17]. Обучение глубоких кодировщиков обычно осуществляется с использованием жадного послойного предобучения (например, используя каскад ограниченных машин Больцмана), за которым следует этап тонкой настройки, основанный на методе обратного распространения ошибки.
Линейный дискриминантный анализ
[править | править код]Линейный дискриминантный анализ является обобщением линейного дискриминанта Фишера, метода, применяемого в статистике, распознавании образов и машинном обучении для поиска линейной комбинации признаков, которые описывают или разделяют два и более класса объектов или событий.
Обобщённый дискриминантный анализ
[править | править код]Обобщённый дискриминантный анализ имеет дело с нелинейным дискриминантным анализом с помощью оператора ядра функции (англ. kernel function operator). Лежащая в основе теория близка к методу опорных векторов, поскольку обобщённый дискриминантный анализ даёт отображение входных векторов в пространство признаков высокой размерности [18][19]. Аналогично линейному, целью обобщённого дискриминантного анализа является поиск проекции признаков в пространство меньшей размерности с максимизацией отношения межклассовой инвариантности (англ. between-class scatter) к внутриклассовой инвариантности (англ. within-class scatter).
Автокодировщик
[править | править код]Автокодировщик может быть использован для изучения функций нелинейного снижения размерности и кодирования вместе с обратной функцией из кодированного к исходному представлению.
См. также
[править | править код]- Задача поиска ближайшего соседа
- MinHash[англ.]
- Накопление информации в дереве решений[англ.]
- Полуопределённое вложение[англ.]
- Снижение размерности многофакторного пространства[англ.]
- Полилинейное обучение подпространств[англ.]
- Полилинейный метод главных компонент[англ.]
- Случайная проекция[англ.]
- Сингулярное разложение
- Латентно-семантический анализ
- Семантическое отображение[англ.]
- Топологический анализ данных
- Locality sensitive hashing
- Достаточное снижение размерности[англ.]
- Преобразование данных
- Анализ взвешенной сети корреляций
- Оптимизация гиперпараметров
- CUR аппроксимации матрицы[англ.]
- Модель конверта
- Нелинейное снижение размерности[англ.]
- Отображение Саммона[англ.]
- Лемма Джонсона — Линденштрауса
Примечания
[править | править код]- ↑ Roweis, Saul, 2000.
- ↑ Pudil, Novovičová, 1998, с. 101.
- ↑ Beyer, Goldstein, Ramakrishnan, Shaft, 1999, с. 217–235.
- ↑ Shaw, Jebara, 2009, с. 1.
- ↑ Bingham, Mannila, 2001, с. 245.
- ↑ Shasha, 2004.
- ↑ Rico-Sulayes, 2017, с. 26—35.
- ↑ Samet, 2006.
- ↑ Ding, He, Zha, Simon, 2002.
- ↑ Lu, Plataniotis, Venetsanopoulos, 2011, с. 1540–1551.
- ↑ 1 2 Lee, Seung, 1999, с. 788—791.
- ↑ Lee, Seung, 2001, с. 556—562.
- ↑ 1 2 Blanton, Roweis, 2007, с. 134.
- ↑ 1 2 3 4 Ren, Pueyo, Zhu, Duchêne, 2018, с. 104.
- ↑ 1 2 3 Zhu, Guangtun B. (2016-12-19). "Nonnegative Matrix Factorization (NMF) with Heteroscedastic Uncertainties and Missing data". arXiv:1612.06037 [astro-ph.IM].
- ↑ UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction (англ.) (7 декабря 2018). Дата обращения: 26 августа 2019. Архивировано 3 ноября 2019 года.
- ↑ Hu, Zahorian, 2010.
- ↑ Baudat, Anouar, 2000, с. 2385–2404.
- ↑ Haghighat, Zonouz, Abdel-Mottaleb, 2015, с. 7905–7916.
Литература
[править | править код]- Baudat G., Anouar F. Generalized discriminant analysis using a kernel approach // Neural computation. — 2000. — Т. 12, вып. 10.
- Haghighat M., Zonouz S., Abdel-Mottaleb M. CloudID: Trustworthy Cloud-based and Cross-Enterprise Biometric Identification // Expert Systems with Applications. — 2015. — Т. 42, вып. 21.
- Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft. When is “nearest neighbor” meaningful? // Proceedings of the 7th International Conference on Database Theory (ICDT). — Jerusalem, Israel,, 1999.
- Hongbing Hu, Stephen A. Zahorian. Dimensionality Reduction Methods for HMM Phonetic Recognition // ICASSP 2010. — Dallas, TX, 2010.
- Bingham E., Mannila H. Random projection in dimensionality reduction // Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining – KDD '01. — 2001. — ISBN 158113391X. — doi:10.1145/502512.502546.
- D High Shasha. Performance Discovery in Time Series. — Berlin: Springer, 2004. — ISBN 0-387-00857-8.
- Shaw B., Jebara T. Structure preserving embedding // Proceedings of the 26th Annual International Conference on Machine Learning – ICML '09. — 2009. — С. 1. — ISBN 9781605585161. — doi:10.1145/1553374.1553494.
- Roweis S. T., Saul L. K. Nonlinear Dimensionality Reduction by Locally Linear Embedding // Science. — 2000. — Т. 290, вып. 5500. — С. 2323–2326. — doi:10.1126/science.290.5500.2323. — . — PMID 11125150.
- Pudil P., Novovičová J. Novel Methods for Feature Subset Selection with Respect to Problem Knowledge // Feature Extraction, Construction and Selection / Huan Liu, Hiroshi Motoda. — 1998. — ISBN 978-1-4613-7622-4. — doi:10.1007/978-1-4615-5725-8_7.
- Antonio Rico-Sulayes. Reducing Vector Space Dimensionality in Automatic Classification for Authorship Attribution // Revista Ingeniería Electrónica, Automática y Comunicaciones. — 2017. — Т. 38, № 3.
- Samet H. Foundations of Multidimensional and Metric Data Structures. — Morgan Kaufmann, 2006. — ISBN 0-12-369446-9.
- Ding C., He X., Zha H., Simon H.D. Adaptive Dimension Reduction for Clustering High Dimensional Data // Proceedings of International Conference on Data Mining. — 2002.
- Haiping Lu, K.N. Plataniotis, A.N. Venetsanopoulos. A Survey of Multilinear Subspace Learning for Tensor Data // Pattern Recognition. — 2011. — Т. 44, № 7. — С. 1540–1551. — doi:10.1016/j.patcog.2011.01.004.
- Daniel D. Lee, H. Sebastian Seung. Learning the parts of objects by non-negative matrix factorization // Nature. — 1999. — Т. 401, вып. 6755. — С. 788–791. — doi:10.1038/44565. — . — PMID 10548103.
- Daniel D. Lee, H. Sebastian Seung. Algorithms for Non-negative Matrix Factorization // Advances in Neural Information Processing Systems 13: Proceedings of the 2000 Conference. — MIT Press, 2001. — С. 556–562.
- Michael R. Blanton, Sam Roweis. K-corrections and filter transformations in the ultraviolet, optical, and near infrared // The Astronomical Journal. — 2007. — Т. 133. — doi:10.1086/510127. — . — arXiv:astro-ph/0606170.
- Bin Ren, Laurent Pueyo, Guangtun B. Zhu, Gaspard Duchêne. Non-negative Matrix Factorization: Robust Extraction of Extended Structures // The Astrophysical Journal. — 2018. — Т. 852. — doi:10.3847/1538-4357/aaa1f2. — . — arXiv:1712.10317.
- Fodor I. A survey of dimension reduction techniques. National Technical Report UCRL-ID-148494. — Lawrence Livermore: Center for Applied Scientific Computing,, 2002.
- Cunningham P. Dimension Reduction. Technical Report UCD-CSI-2007-7. — University College Dublin, 2007.
- Stephen A. Zahorian, Hongbing Hu. Nonlinear Dimensionality Reduction Methods for Use with Automatic Speech Recognition // Speech Technologies. — 2011. — ISBN 978-953-307-996-7. — doi:10.5772/16863.
- Dhyaram Lakshmi Padmaja, B Vishnuvardhan. Comparative Study of Feature Subset Selection Methods for Dimensionality Reduction on Scientific Data. — 2016. — Август. — С. 31–34. — doi:10.1109/IACC.2016.16.
Ссылки
[править | править код]- JMLR Special Issue on Variable and Feature Selection
- ELastic MAPs
- Locally Linear Embedding
- A Global Geometric Framework for Nonlinear Dimensionality Reduction
Для улучшения этой статьи желательно:
|