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

Ищите самое необходимое
Самые простые предметы первой необходимости
Забудь о своих заботах и ​​ссорах
Я имею в виду самое необходимое
Рецепты древней матери-природы
Это приносит самое необходимое для жизни

— Песня Балу [Книга джунглей]

2.2.1. Введение

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

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

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

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

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

2.2.2. Isomap

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

2.2.2.1. Сложность

Алгоритм Isomap состоит из трех этапов:

1. Поиск ближайшего соседа. Isomap использует BallTree для эффективного поиска соседей. Стоимость ориентировочно $O[D \log(k) N \log(N)]$, для $k$ ближайшие соседи $N$ указывает в $D$ Габаритные размеры.
2. Поиск по графу кратчайшего пути. Наиболее эффективными известными алгоритмами для этого являются алгоритм Дейкстры , который приблизительно равен $O[N^2(k + \log(N))]$, или алгоритм Флойда-Уоршалла , который $O[N^3]$. Алгоритм может быть выбран пользователем с path_method ключевым словом Isomap. Если не указано иное, код пытается выбрать лучший алгоритм для входных данных.
3. Частичное разложение на собственные значения. Вложение кодируется в собственных векторах, соответствующихd наибольшие собственные значения $N \times N$ ядро isomap. Стоимость плотного решателя составляет примерно $O[d N^2]$. Эту стоимость часто можно уменьшить с помощью ARPACK решателя. Собственный преобразователь может быть указан пользователем с eigen_solver ключевым словом Isomap. Если не указано иное, код пытается выбрать лучший алгоритм для входных данных.

Общая сложность Isomap составляет $O[D \log(k) N \log(N)] + O[N^2(k + \log(N))] + O[d N^2]$.

• $N$ : количество точек данных обучения
• $D$ : входной размер
• $k$ : количество ближайших соседей
• $d$ : выходной размер

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

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

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

2.2.3.1. Сложность

Стандартный алгоритм LLE состоит из трех этапов:

1. Поиск ближайших соседей . См. Обсуждение под Isomap выше.
2. Построение весовой матрицы .$O[D N k^3]$. Построение весовой матрицы LLE включает решение $k \times k$ линейное уравнение для каждого из $N$ местные районы
3. Частичное разложение на собственные значения . См. Обсуждение под Isomap выше.

Общая сложность стандартного LLE составляет $O[D \log(k) N \log(N)] + O[D N k^3] + O[d N^2]$.

• $N$ : количество точек данных обучения
• $D$ : входной размер
• $k$ : количество ближайших соседей
• $d$ : выходной размер

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

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

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

2.2.4.1. Сложность

Алгоритм MLLE состоит из трех этапов:

1. Поиск ближайших соседей . То же, что и стандартный LLE
2. Построение весовой матрицы . Примерно $O[D N k^3] + O[N (k-D) k^2]$. Первый член в точности эквивалентен стандартному LLE. Второй член связан с построением весовой матрицы из нескольких весов. На практике дополнительные затраты на построение весовой матрицы MLLE относительно невелики по сравнению со стоимостью этапов 1 и 3.
3. Частичное разложение на собственные значения . То же, что и стандартный LLE

Общая сложность MLLE составляет $O[D \log(k) N \log(N)] + O[D N k^3] + O[N (k-D) k^2] + O[d N^2]$.

• $N$ : количество точек данных обучения
• $D$ : входной размер
• $k$ : количество ближайших соседей
• $d$ : выходной размер

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

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

2.2.5.1. Сложность

Алгоритм HLLE состоит из трех этапов:

1. Поиск ближайших соседей . То же, что и стандартный LLE
2. Построение весовой матрицы . Примерно $O[D N k^3] + O[N d^6]$. Первый член отражает стоимость, аналогичную стоимости стандартного LLE. Второй член получается из QR-разложения локальной оценки гессиана.
3. Частичное разложение на собственные значения . То же, что и стандартный LLE

Общая сложность стандартного HLLE составляет $O[D \log(k) N \log(N)] + O[D N k^3] + O[N d^6] + O[d N^2]$.

• $N$ : количество точек данных обучения
• $D$ : входной размер
• $k$ : количество ближайших соседей
• $d$ : выходной размер

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

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

2.2.6.1. Сложность

Алгоритм Spectral Embedding (Laplacian Eigenmaps) состоит из трех этапов:

1. Построение взвешенного графа . Преобразуйте необработанные входные данные в графическое представление, используя матричное представление сходства (смежности).
2. Построение графа Лапласа . ненормализованный граф Лапласиан строится как $L=D−A$ для и нормализованный как $L = D^{-\frac{1}{2}} (D — A) D^{-\frac{1}{2}}$.
3. Частичное разложение на собственные значения . Разложение по собственным значениям выполняется на лапласиане графа

Общая сложность спектрального вложения составляет $O[D \log(k) N \log(N)] + O[D N k^3] + O[d N^2]$.

• $N$ : количество точек данных обучения
• $D$ : входной размер
• $k$ : количество ближайших соседей
• $d$ : выходной размер

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

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

2.2.7.1. Сложност

Алгоритм LTSA состоит из трех этапов:

1. Поиск ближайших соседей . То же, что и стандартный LLE
2. Построение весовой матрицы . Примерно $O[D N k^3] + O[k^2 d]$. Первый член отражает стоимость, аналогичную стоимости стандартного LLE.
3. Частичное разложение на собственные значения . То же, что и стандартный LLE

Общая сложность стандартного LTSA составляет $O[D \log(k) N \log(N)] + O[D N k^3] + O[k^2 d] + O[d N^2]$.

• $N$ : количество точек данных обучения
• $D$ : входной размер
• $k$ : количество ближайших соседей
• $d$ : выходной размер

2.2.8. Многомерное масштабирование (MDS)

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

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

Существует два типа алгоритма MDS: метрический и неметрический. В scikit-learn класс MDS реализует оба. В Metric MDS входная матрица подобия возникает из метрики (и, таким образом, соблюдается треугольное неравенство), расстояния между двумя выходными точками затем устанавливаются как можно ближе к данным подобия или несходства. В неметрической версии алгоритмы будут пытаться сохранить порядок расстояний и, следовательно, искать монотонную связь между расстояниями во вложенном пространстве и сходствами / различиями.

Позволять $S$ — матрица подобия, а $X$ координаты nточки ввода. Несоответствия $\hat{d}_{ij}$ являются преобразованием подобранных оптимальным образом подобранных способов. Тогда цель, называемая напряжением, определяется следующим образом:
$\sum_{i < j} d_{ij}(X) — \hat{d}_{ij}(X)$

2.2.8.1. Метрические MDS

Простейшая метрическая MDS модель, называемая абсолютным MDS , различия определяются следующим образом : $\hat{d}{ij} = S{ij}$. При абсолютном MDS значение $S_{ij}$ тогда должно точно соответствовать расстоянию между точками $i$ а также $j$ в точке вложения.

Чаще всего устанавливается неравенство $\hat{d}{ij} = b S{ij}$.

2.2.8.2. Неметрические МДС

Неметрическая система MDS ориентирована на упорядочение данных. Если $S_{ij} < S_{jk}$, то вложение должно обеспечивать $d_{ij} <d_{jk}$. Простой алгоритм для обеспечения этого заключается в использовании монотонной регрессии $d_{ij}$ на $S_{ij}$, приводя к диспропорциям $\hat{d}_{ij}$ в том же порядке, что и $S_{ij}$.

Тривиальное решение этой проблемы — установить все точки в начале координат. Чтобы этого избежать, неравенство $\hat{d}_{ij}$ нормализованы.

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 Барнса-Хата ограничен двумерным или трехмерным вложением.
• Алгоритм является стохастическим, и несколько перезапусков с разными начальными числами могут дать разные вложения. Однако вполне законно выбрать встраивание с наименьшей ошибкой.
• Глобальная структура явно не сохраняется. Эта проблема смягчается за счет инициализации точек с помощью PCA (с использованием init='pca').

2.2.9.1. Оптимизация t-SNE

Основная цель t-SNE — визуализация данных большой размерности. Следовательно, лучше всего работает, когда данные будут встраиваться в двух или трех измерениях.

Оптимизация расхождения KL иногда может быть немного сложной. Есть пять параметров, которые контролируют оптимизацию t-SNE и, следовательно, возможно качество результирующего встраивания:

• недоумение
• фактор раннего преувеличения
• скорость обучения
• максимальное количество итераций
• угол (не используется в точном методе)

Недоумение определяется как $k=2^{(S)}$ где $S$ — энтропия Шеннона условного распределения вероятностей. Недоумение $k$-сторонний штамп $k$, чтобы $k$ фактически является числом ближайших соседей, которое t-SNE учитывает при генерации условных вероятностей. Большие сложности приводят к большему количеству ближайших соседей и менее чувствительны к мелким строениям. И наоборот, при меньшем недоумении учитывается меньшее количество соседей и, таким образом, игнорируется более глобальная информация в пользу местного соседства. По мере увеличения размеров набора данных потребуется больше точек, чтобы получить разумную выборку местного соседства, и, следовательно, могут потребоваться большие затруднения. Точно так же более зашумленные наборы данных потребуют больших значений недоумения, чтобы охватить достаточно локальных соседей, чтобы видеть за пределами фонового шума.

Максимальное количество итераций обычно достаточно велико и не требует настройки. Оптимизация состоит из двух этапов: этапа раннего преувеличения и заключительной оптимизации. Во время раннего преувеличения совместные вероятности в исходном пространстве будут искусственно увеличены путем умножения на заданный коэффициент. Более высокие факторы приводят к большим разрывам между естественными кластерами в данных. Если коэффициент слишком высок, расхождение KL может увеличиться на этом этапе. Обычно его не нужно настраивать. Критическим параметром является скорость обучения. Если он слишком низкий, градиентный спуск застрянет в плохом локальном минимуме. Если оно слишком велико, дивергенция KL увеличится во время оптимизации. Дополнительные советы можно найти в FAQ Лоренса ван дер Маатена (см. Ссылки). Последний параметр, угол, представляет собой компромисс между производительностью и точностью.Большие углы означают, что мы можем аппроксимировать большие области одной точкой, что приводит к более высокой скорости, но менее точным результатам.

«Как использовать t-SNE эффективно» дает хорошее обсуждение эффектов различных параметров, а также интерактивные графики для изучения эффектов различных параметров.

2.2.9.2. Barnes-Hut t-SNE

Реализованный здесь t-SNE Barnes-Hut обычно намного медленнее, чем другие алгоритмы обучения многообразию. Оптимизация довольно сложна, и вычисление градиента требует $O[d N log(N)]$, где $d$ количество выходных размеров и $N$ количество образцов. Метод Барнса-Хата улучшает точный метод, в котором сложность t-SNE равна $O[d N^2]$, но имеет несколько других заметных отличий:

• Реализация Barnes-Hut работает только тогда, когда целевая размерность равна 3 или меньше. 2D-случай типичен при построении визуализаций.
• Barnes-Hut работает только с плотными входными данными. Матрицы разреженных данных могут быть встроены только с помощью точного метода или могут быть аппроксимированы плотной проекцией низкого ранга, например, с использованием TruncatedSVD
• Barnes-Hut является приближением точного метода. Приближение параметризуется с помощью параметра угла, поэтому параметр угла не используется, если метод = «точный».
• Barnes-Hut значительно более масштабируемый. Barnes-Hut может использоваться для встраивания сотен тысяч точек данных, в то время как точный метод может обрабатывать тысячи образцов, прежде чем станет трудноразрешимым в вычислительном отношении.

Для целей визуализации (что является основным вариантом использования t-SNE) настоятельно рекомендуется использовать метод Barnes-Hut. Точный метод t-SNE полезен для проверки теоретических свойств вложения, возможно, в пространство более высокой размерности, но ограничивается небольшими наборами данных из-за вычислительных ограничений.

Также обратите внимание, что метки цифр примерно соответствуют естественной группировке, обнаруженной t-SNE, в то время как линейная 2D-проекция модели PCA дает представление, в котором области меток в значительной степени перекрываются. Это явный признак того, что эти данные могут быть хорошо разделены нелинейными методами, ориентированными на локальную структуру (например, SVM с гауссовым ядром RBF). Однако невозможность визуализировать хорошо разделенные однородно помеченные группы с t-SNE в 2D не обязательно означает, что данные не могут быть правильно классифицированы с помощью контролируемой модели. Возможно, двух измерений недостаточно для точного представления внутренней структуры данных.

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

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