2.2. Обучение многообразий

2.2.1. Введение

Визуализировать наборы данных высокой размерности может быть очень сложно. Данные в двух или трёх измерениях можно отобразить на графике, чтобы показать их внутреннюю структуру, однако эквивалентные графики в пространствах высокой размерности гораздо менее наглядны. Чтобы упростить визуализацию структуры набора данных, необходимо каким-либо образом уменьшить размерность.

Самый простой способ уменьшить размерность — выполнить случайную проекцию данных. Хотя это позволяет в некоторой степени визуализировать структуру данных, случайный выбор оставляет желать лучшего. При случайной проекции интересная структура данных, вероятно, будет утрачена.

Для решения этой проблемы разработан ряд методов линейного снижения размерности с учителем и без учителя, например анализ главных компонент (PCA), анализ независимых компонент, линейный дискриминантный анализ и другие. Эти алгоритмы определяют конкретные критерии выбора «интересной» линейной проекции данных. Такие методы могут быть эффективными, но часто не учитывают важную нелинейную структуру данных.

Обучение многообразий можно рассматривать как попытку обобщить линейные методы, такие как PCA, чтобы учитывать нелинейную структуру данных. Хотя существуют варианты с учителем, типичная задача обучения многообразий решается без учителя: алгоритм изучает структуру данных высокой размерности непосредственно по самим данным, не используя заранее заданные классификации.

Примеры

• См. Обучение многообразий на рукописных цифрах: локально-линейное вложение, Isomap… — пример снижения размерности данных с рукописными цифрами.
• См. Сравнение методов обучения многообразий — пример снижения размерности игрушечного набора данных «S-кривая».
• См. Визуализация структуры фондового рынка — пример применения обучения многообразий для отображения структуры фондового рынка на основе исторических цен акций.
• См. Методы обучения многообразий на разрезанной сфере — пример применения методов обучения многообразий к сферическому набору данных.
• См. Снижение размерности для «швейцарского рулета» и «швейцарской дыры» — пример применения методов обучения многообразий к набору данных «швейцарский рулет».

Реализации методов обучения многообразий, доступные в scikit-learn, кратко описаны ниже

2.2.2. Isomap

Один из первых подходов к обучению многообразий — алгоритм Isomap, сокращение от Isometric Mapping (изометрическое отображение). Isomap можно рассматривать как расширение многомерного шкалирования (MDS) или ядерного PCA. Isomap строит вложение в пространство меньшей размерности, сохраняющее геодезические расстояния между всеми точками. Isomap можно применить с помощью объекта Isomap.

Литература

• «Глобальная геометрическая основа нелинейного снижения размерности» Tenenbaum, J.B.; De Silva, V.; & Langford, J.C. Science 290 (5500)

2.2.3. Локально-линейное вложение

Локально-линейное вложение (LLE) строит проекцию данных в пространство меньшей размерности, сохраняющую расстояния внутри локальных окрестностей. Его можно представить как совокупность локальных анализов главных компонент, которые глобально сопоставляются для нахождения наилучшего нелинейного вложения.

Локально-линейное вложение можно выполнить с помощью функции locally_linear_embedding или её объектно-ориентированного аналога LocallyLinearEmbedding.

Литература

• «Нелинейное снижение размерности с помощью локально-линейного вложения» Roweis, S. & Saul, L. Science 290:2323 (2000)

2.2.4. Модифицированное локально-линейное вложение

Одна из известных проблем LLE — проблема регуляризации. Если число соседей превышает размерность входных данных, матрица, определяющая каждую локальную окрестность, оказывается вырожденной. Для решения этой проблемы в стандартном LLE используется произвольный параметр регуляризации \(r\), выбираемый относительно следа локальной матрицы весов. Хотя формально можно показать, что при \(r \to 0\) решение сходится к требуемому вложению, нет гарантии, что при \(r > 0\) будет найдено оптимальное решение. Эта проблема проявляется в искажении исходной геометрии многообразия во вложении.

Один из способов решения проблемы регуляризации — использовать несколько векторов весов в каждой окрестности. В этом заключается суть модифицированного локально-линейного вложения (MLLE). MLLE можно выполнить с помощью функции locally_linear_embedding или её объектно-ориентированного аналога LocallyLinearEmbedding, указав ключевое слово method = 'modified'. Для этого требуется n_neighbors > n_components.

Литература

• «MLLE: модифицированное локально-линейное вложение с использованием нескольких весов» Zhang, Z. & Wang, J.

2.2.5. Гессианное отображение по собственным векторам

Гессианное отображение по собственным векторам (также известное как LLE на основе матрицы Гессе: HLLE) — ещё один метод решения проблемы регуляризации LLE. В его основе лежит квадратичная форма на основе матрицы Гессе для каждой окрестности, которая используется для восстановления локально-линейной структуры. Хотя в других реализациях отмечается плохая масштабируемость алгоритма с ростом размера данных, sklearn реализует некоторые алгоритмические улучшения, благодаря которым при малой размерности выходных данных его вычислительная сложность сопоставима со сложностью других вариантов LLE. HLLE можно выполнить с помощью функции locally_linear_embedding или её объектно-ориентированного аналога LocallyLinearEmbedding, указав ключевое слово method = 'hessian'. Для этого требуется n_neighbors > n_components * (n_components + 3) / 2.

Литература

• «Гессианные отображения по собственным векторам: методы локально-линейного вложения для данных высокой размерности» Donoho, D. & Grimes, C. Proc Natl Acad Sci USA. 100:5591 (2003)

2.2.6. Спектральное вложение

Спектральное вложение — это подход к вычислению нелинейного вложения. В scikit-learn реализованы лапласиановы собственные отображения, которые находят низкоразмерное представление данных с помощью спектрального разложения лапласиана графа. Построенный граф можно рассматривать как дискретное приближение низкоразмерного многообразия в пространстве высокой размерности. Минимизация целевой функции на основе графа обеспечивает близкое отображение точек, близких друг к другу на многообразии, в низкоразмерном пространстве, сохраняя локальные расстояния. Спектральное вложение можно выполнить с помощью функции spectral_embedding или её объектно-ориентированного аналога SpectralEmbedding.

Литература

• «Лапласиановы собственные отображения для снижения размерности и представления данных» M. Belkin, P. Niyogi, Neural Computation, June 2003; 15 (6):1373-1396.

2.2.7. Выравнивание локальных касательных пространств

Хотя выравнивание локальных касательных пространств (LTSA) формально не является вариантом LLE, алгоритмически оно достаточно близко к LLE, чтобы относить его к этой категории. В отличие от LLE, ориентированного на сохранение расстояний между соседями, LTSA характеризует локальную геометрию каждой окрестности с помощью её касательного пространства и выполняет глобальную оптимизацию, выравнивая эти локальные касательные пространства для построения вложения. LTSA можно выполнить с помощью функции locally_linear_embedding или её объектно-ориентированного аналога LocallyLinearEmbedding, указав ключевое слово method = 'ltsa'.

Литература

• «Главные многообразия и нелинейное снижение размерности посредством выравнивания касательных пространств» Zhang, Z. & Zha, H. Journal of Shanghai Univ. 8:406 (2004)

2.2.8. Многомерное шкалирование (MDS)

Многомерное шкалирование (MDS и ClassicalMDS) ищет низкоразмерное представление данных, в котором расстояния приближены к расстояниям в исходном высокоразмерном пространстве.

В целом MDS — это метод анализа данных о несходстве. Он пытается моделировать несходства как расстояния в евклидовом пространстве. Данные могут представлять собой оценки несходства между объектами, частоты взаимодействия молекул или торговые индексы между странами.

Существует три типа алгоритмов MDS: метрический, неметрический и классический. В scikit-learn класс MDS реализует метрический и неметрический MDS, а ClassicalMDS реализует классический MDS. При метрическом MDS расстояния во вложенном пространстве устанавливаются максимально близкими к данным о несходстве. В неметрическом варианте алгоритм пытается сохранить порядок расстояний и, следовательно, найти монотонную зависимость между расстояниями во вложенном пространстве и входными значениями несходства. Наконец, классический MDS близок к PCA и вместо аппроксимации расстояний аппроксимирует попарные скалярные произведения. Это более простая задача оптимизации с аналитическим решением на основе спектрального разложения.

Пусть \(\delta_{ij}\) — матрица несходства между \(n\) входными точками (возможно, полученная из попарных расстояний \(d_{ij}(X)\) между координатами \(X\) входных точек). Несоответствия \(\hat{d}_{ij} = f(\delta_{ij})\) представляют собой некоторое преобразование значений несходства. Целевая функция MDS, называемая сырым стрессом, определяется как \(\sum_{i < j} (\hat{d}_{ij} - d_{ij}(Z))^2\), где \(d_{ij}(Z)\) — попарные расстояния между координатами \(Z\) вложенных точек.

Неметрический MDS

Неметрический MDS ориентирован на упорядочение данных. Если \(\delta_{ij} > \delta_{kl}\), то вложение стремится обеспечить \(d_{ij}(Z) > d_{kl}(Z)\). Простой алгоритм обеспечения правильного упорядочения — использовать изотоническую регрессию \(d_{ij}(Z)\) по \(\delta_{ij}\), получая несоответствия \(\hat{d}_{ij}\), которые являются монотонным преобразованием значений несходства \(\delta_{ij}\) и, следовательно, имеют тот же порядок. Это выполняется после каждого шага алгоритма оптимизации. Чтобы избежать тривиального решения, при котором все точки вложения совпадают, несоответствия \(\hat{d}_{ij}\) нормализуются.

Обратите внимание: поскольку нас интересует только относительный порядок, наша целевая функция должна быть инвариантна к простому переносу и масштабированию, однако стресс, используемый в метрическом MDS, чувствителен к масштабированию. Для решения этой проблемы неметрический MDS возвращает нормализованный стресс, также известный как Stress-1, который определяется следующим образом:

\[\sqrt{\frac{\sum_{i < j} (\hat{d}_{ij} - d_{ij}(Z))^2}{\sum_{i < j} d_{ij}(Z)^2}}.\]

Нормализованный Stress-1 возвращается, если normalized_stress=True.

Классический MDS, также известный как анализ главных координат (PCoA) или шкалирование Торгерсона, реализован в отдельном классе ClassicalMDS. В классическом MDS функция потерь на основе стресса заменяется другой функцией потерь, называемой деформацией, для которой существует точное решение на основе спектрального разложения. Если матрица несходства состоит из попарных евклидовых расстояний между некоторыми векторами, то классический MDS эквивалентен PCA, применённому к этому набору векторов.

Формально функция потерь классического MDS (деформация) задаётся следующим образом:

где \(Z\) — матрица вложения размера \(n \times d\), строки которой равны \(z_i^T\), \(\|\cdot\|_F\) обозначает норму Фробениуса, а \(B\) — матрица Грама с элементами \(b_{ij}\), задаваемая как \(B = -\frac{1}{2}C\Delta C\). Здесь \(C\Delta C\) — матрица квадратов значений несходства с двойным центрированием, где \(\Delta\) — матрица квадратов входных значений несходства \(\delta^2_{ij}\), а \(C=I-J/n\) — матрица центрирования (единичная матрица минус матрица, состоящая из единиц и делённая на \(n\)). Эту функцию можно точно минимизировать с помощью спектрального разложения \(B\).

Литература

• «Ещё о многомерном шкалировании и развёртывании в R: smacof, версия 2» Mair P, Groenen P., de Leeuw J. Journal of Statistical Software (2022)
• «Современное многомерное шкалирование: теория и приложения» Borg, I.; Groenen P. Springer Series in Statistics (1997)
• «Неметрическое многомерное шкалирование: численный метод» Kruskal, J. Psychometrika, 29 (1964)
• «Многомерное шкалирование путём оптимизации качества соответствия неметрической гипотезе» Kruskal, J. Psychometrika, 29, (1964)

2.2.9. Стохастическое вложение соседей с t-распределением (t-SNE)

t-SNE (TSNE) преобразует аффинности точек данных в вероятности. Аффинности в исходном пространстве представлены совместными вероятностями с распределением Гаусса, а аффинности во вложенном пространстве — t-распределениями Стьюдента. Благодаря этому t-SNE особенно чувствителен к локальной структуре и обладает рядом других преимуществ по сравнению с существующими методами:

• Выявление структуры на многих масштабах на одной карте
• Выявление данных, принадлежащих нескольким различным многообразиям или кластерам
• Уменьшение склонности точек скучиваться в центре

В то время как Isomap, LLE и их варианты лучше всего подходят для распрямления одного непрерывного низкоразмерного многообразия, t-SNE фокусируется на локальной структуре данных и стремится выделить локальные группы образцов в виде кластеров, как показано на примере S-образной кривой. Эта способность группировать образцы на основе локальной структуры может быть полезна для визуального разделения набора данных, одновременно содержащего несколько многообразий, как в случае набора данных с цифрами.

Минимизация дивергенции Кульбака — Лейблера (KL) совместных вероятностей в исходном и вложенном пространствах выполняется методом градиентного спуска. Обратите внимание, что дивергенция KL не является выпуклой, то есть при нескольких запусках с разными начальными значениями алгоритм будет попадать в локальные минимумы дивергенции KL. Поэтому иногда полезно попробовать разные начальные значения и выбрать вложение с наименьшей дивергенцией KL.

К недостаткам использования t-SNE относятся:

• t-SNE требует больших вычислительных затрат и может выполняться несколько часов на наборах данных с миллионом образцов, тогда как PCA завершит работу за секунды или минуты
• Метод t-SNE Barnes-Hut ограничен вложениями в два или три измерения.
• Алгоритм является стохастическим, и несколько запусков с разными начальными значениями могут давать разные вложения. Тем не менее вполне допустимо выбрать вложение с наименьшей ошибкой.
• Глобальная структура явно не сохраняется. Эту проблему можно смягчить, задав начальное расположение точек с помощью PCA (используя init='pca').

Литература

• «Визуализация высокоразмерных данных с помощью t-SNE» van der Maaten, L.J.P.; Hinton, G. Journal of Machine Learning Research (2008)
• «Стохастическое вложение соседей с t-распределением» van der Maaten, L.J.P.
• «Ускорение t-SNE с помощью алгоритмов на основе деревьев» van der Maaten, L.J.P.; Journal of Machine Learning Research 15(Oct):3221-3245, 2014.
• «Автоматически оптимизированные параметры стохастического вложения соседей с t-распределением улучшают визуализацию и анализ больших наборов данных» Belkina, A.C., Ciccolella, C.O., Anno, R., Halpert, R., Spidlen, J., Snyder-Cappione, J.E., Nature Communications 10, 5415 (2019).

2.2.10. Советы по практическому использованию

• Убедитесь, что для всех признаков используется одинаковый масштаб. Поскольку методы обучения многообразий основаны на поиске ближайших соседей, в противном случае алгоритм может работать плохо. О способах масштабирования разнородных данных см. StandardScaler.
• Ошибку восстановления, вычисляемую каждой процедурой, можно использовать для выбора оптимальной выходной размерности. Для \(d\)-мерного многообразия, вложенного в пространство параметров размерности \(D\), ошибка восстановления будет уменьшаться с увеличением n_components до тех пор, пока n_components == d.
• Обратите внимание, что зашумлённые данные могут «закорачивать» многообразие, фактически создавая мост между его частями, которые иначе были бы хорошо разделены. Обучение многообразий на зашумлённых и/или неполных данных — активно развивающаяся область исследований.
• Некоторые конфигурации входных данных могут приводить к вырожденным матрицам весов, например, если в наборе данных совпадают более двух точек или если данные разделены на несвязанные группы. В этом случае solver='arpack' не сможет найти нулевое пространство. Проще всего решить эту проблему с помощью solver='dense', который работает с вырожденной матрицей, хотя может быть очень медленным в зависимости от числа входных точек. Другой вариант — попытаться определить причину вырождения: если дело в несвязанных множествах, может помочь увеличение n_neighbors. Если причина в совпадающих точках в наборе данных, может помочь удаление этих точек.