t-SNE (tsne) - это алгоритм уменьшения размерности, который хорошо подходит для визуализации высокоразмерных данных. Название означает t-distributed Stochastic Neighbor Embedding. Идея состоит в том, чтобы встроить высокомерные точки в низкие размеры таким образом, чтобы уважать сходство между точками. Близлежащие точки в многомерном пространстве соответствуют близлежащим встроенным низкоразмерным точкам, а отдаленные точки в многомерном пространстве соответствуют удаленным встроенным низкомерным точкам. (Как правило, невозможно точно сопоставить расстояния между многомерными и низкоразмерными пространствами.)
tsne создает набор низкоразмерных точек из высокомерных данных. Обычно визуализируются низкоразмерные точки, чтобы увидеть естественные кластеры в исходных высокомерных данных.
Алгоритм выполняет следующие общие шаги для встраивания данных в малые измерения.
Вычислите попарные расстояния между высокомерными точками.
Создайте среднеквадратичное отклонение для каждой высокомерной точки i так, чтобы недоумение каждой точки было на заданном уровне. Определение недоумений см. в разделах Вычислительные расстояния, Гауссовы отклонения и Сходства.
Вычислите матрицу подобия. Это совместное распределение вероятности X, определенное уравнением 1.
Создайте начальный набор низкоразмерных точек.
Итеративно обновить низкоразмерные точки, чтобы минимизировать дивергенцию Куллбэка-Лейблера между гауссовым распределением в высокомерном пространстве и t распределением в низкомерном пространстве. Эта процедура оптимизации является наиболее трудоемкой частью алгоритма.
См. Ван дер Маатен и Хинтон [1].
Базовый алгоритм t-SNE выполняет следующие шаги.
tsne сначала удаляет каждую строку входных данных X, которая содержит любые NaN значения. Затем, если Standardize пара имя-значение true, tsne центров X путем вычитания среднего значения каждого столбца, и шкал X путем деления его столбцов на их стандартные отклонения.
Оригинальные авторы ван дер Маатен и Хинтон [1] рекомендуют сократить исходные данные X до более узкой версии с помощью анализа основных компонентов (PCA). Можно установить tsne
NumPCAComponents пара «имя-значение» к количеству размеров, которые вам нравятся, возможно, 50. Для усиления контроля над этим шагом выполните предварительную обработку данных с помощью pca функция.
После предварительной обработки tsne вычисляет расстояние d (xi, xj) между каждой парой точек xi и xj в X. Вы можете выбрать различные метрики расстояния, используя Distance пара имя-значение. По умолчанию tsne использует стандартную евклидову метрику. tsne использует квадрат метрики расстояния в последующих расчетах.
Затем для каждой строки i из X, tsne вычисляет среднеквадратичное отклонение, так что недоумение строки i равно Perplexity пара имя-значение. Недоумение определяется в терминах модели гауссова распределения следующим образом. Как описывают ван дер Маатен и Хинтон [1], "сходство точки данных xj с точкой данных xi является условной вероятностью, , что си выберет xj в качестве своего соседа, если соседи будут выбраны пропорционально их плотности вероятности под гауссовым центром в xi. для близлежащих точек данных, является относительно высоким, тогда как для широко разделенных точек данных будет почти бесконечно малым (для разумных значений дисперсии гауссова, starti) ".
Определите условную вероятность j, указанную i как
( 2starti2)) pi' i = 0.
Затем определяют вероятность соединения pij путем симметрии условных вероятностей:
| pi' j2N, | (1) |
где N - число строк X.
В распределениях по-прежнему нет их стандартных отклонений Perplexity пара имя-значение. Пусть Pi представляет условное распределение вероятности по всем другим точкам данных, заданным точкой данных xi. недоумение распределения
Pi),
где H (Pi) - энтропия Шеннона Pi:
pj 'i).
Недоумение измеряет эффективное число соседей точки i. tsne выполняет бинарный поиск по starti для достижения фиксированного недоумения для каждой точки i.
Чтобы вставить точки в X в низкомерное пространство, tsne выполняет оптимизацию. tsne попытки минимизировать расхождение Куллбэка-Лейблера между модельным гауссовым распределением точек в X и студенческим t распределением точек Y в низкомерном пространстве.
Процедура минимизации начинается с начального набора точек Y. tsne создать точки по умолчанию как случайные точки, распределенные по Гауссу. Вы также можете создать эти точки самостоятельно и включить их в 'InitialY' пара имя-значение для tsne. tsne затем вычисляет сходство между каждой парой точек в Y.
Вероятностная модель qij распределения расстояний между точками yi и yj равна
1qii = 0.
Используя это определение и модель расстояний в X, заданную уравнением 1, дивергенция Куллбэка-Лейблера между совместным распределением P и Q равна
=∑j∑i≠jpijlogpijqij.
Последствия этого определения см. в разделе Полезные нелинейные искажения.
Чтобы минимизировать расхождение Kullback-Leibler, 'exact' алгоритм использует модифицированную процедуру градиентного спуска. Градиент относительно точек Y расхождения равен
qij (yi − yj),
где термин нормализации
1.
Модифицированный алгоритм градиентного спуска использует несколько параметров настройки, чтобы попытаться достичь хорошего локального минимума.
'Exaggeration' - во время первых 99 шагов градиентного спуска, tsne умножает вероятности pij из уравнения 1 на значение преувеличения. Этот шаг имеет тенденцию создавать больше пространства между кластерами на выходе Y.
'LearnRate' — tsne использует адаптивное обучение для улучшения сходимости итераций градиентного спуска. Алгоритм спуска имеет итеративные шаги, являющиеся линейной комбинацией предыдущего шага в спуске и текущего градиента. 'LearnRate' - множитель текущего градиента для линейной комбинации. Для получения более подробной информации см. Jacobs [3].
Для ускорения алгоритма t-SNE и сокращения его использования в памяти, tsne предлагает примерную схему оптимизации. Расположенные рядом группы алгоритмов Барнса-Хата указывают друг на друга для снижения сложности и использования памяти на этапе оптимизации t-SNE. Алгоритм Барнса-Хата является приблизительным оптимизатором, а не точным оптимизатором. Существует неотрицательный параметр настройки Theta это влияет на компромисс между скоростью и точностью. Большие значения 'Theta' дают более быстрые, но менее точные результаты оптимизации. Алгоритм относительно нечувствителен к 'Theta' значения в диапазоне (0,2,0,8).
Алгоритм Барнса-Хута группирует близлежащие точки в низкомерном пространстве и выполняет приближенный градиентный спуск на основе этих групп. Идея, первоначально использовавшаяся в астрофизике, заключается в том, что градиент аналогичен для близлежащих точек, поэтому вычисления можно упростить.
См. Ван дер Маатен [2].
Поскольку t-SNE часто хорошо разделяет кластеры данных, может показаться, что t-SNE может классифицировать новые точки данных. Однако t-SNE не может классифицировать новые точки. Встраивание t-SNE является нелинейной картой, зависящей от данных. Для встраивания новой точки в низкоразмерное пространство нельзя использовать предыдущее встраивание в качестве карты. Вместо этого снова запустите весь алгоритм.
t-SNE может занять много времени для обработки данных. Если в измерениях D имеется N точек данных, которые необходимо сопоставить с измерениями Y, то
Точное количество операций t-SNE порядка D * N2.
Barnes-Hut t-SNE принимает порядок операций D * Nlog (N) * exp (размерность (Y)).
Так для больших наборов данных, где N больше 1000 или около того, и где размерность встраивания Y равна 2 или 3, алгоритм Барнса-Хута может быть быстрее точного алгоритма.
T-SNE отображает высокоразмерные расстояния на искаженные низкоразмерные аналоги. Из-за более толстого хвоста распределения Стьюдента в низкомерном пространстве, tsne часто перемещают близкие точки ближе друг к другу и перемещают дальние точки дальше друг от друга, чем в многомерном пространстве, как показано на следующем рисунке. На рисунке показано распределение по Гауссу и по Стьюденту в точках, где плотности составляют 0,25 и 0,025. Гауссова плотность относится к высокоразмерным расстояниям, а t плотность относится к низкоразмерным расстояниям. Плотность t соответствует близким точкам и дальним точкам, находящимся дальше, по сравнению с плотностью Гаусса.
t = linspace(0,5); y1 = normpdf(t,0,1); y2 = tpdf(t,1); plot(t,y1,'k',t,y2,'r') hold on x1 = fzero(@(x)normpdf(x,0,1)-0.25,[0,2]); x2 = fzero(@(x)tpdf(x,1)-0.25,[0,2]); z1 = fzero(@(x)normpdf(x,0,1)-0.025,[0,5]); z2 = fzero(@(x)tpdf(x,1)-0.025,[0,5]); plot([0,x1],[0.25,0.25],'k-.') plot([0,z2],[0.025,0.025],'k-.') plot([x1,x1],[0,0.25],'g-',[x2,x2],[0,0.25],'g-') plot([z1,z1],[0,0.025],'g-',[z2,z2],[0,0.025],'g-') text(1.1,.25,'Close points are closer in low-D') text(2.4,.05,'Far points are farther in low-D') legend('Gaussian(0,1)','Student t (df = 1)') xlabel('x') ylabel('Density') title('Density of Gaussian(0,1) and Student t (df = 1)') hold off
Это искажение полезно, когда оно применимо. Он не применяется в таких случаях, как когда гауссова дисперсия высока, что снижает гауссов пик и сглаживает распределение. В таком случае, tsne может перемещать близкие точки дальше, чем в исходном пространстве. Чтобы добиться полезного искажения,
Установите 'Verbose' пара имя-значение к 2.
Отрегулируйте 'Perplexity' пара «имя-значение», чтобы сообщаемый диапазон отклонений не был слишком далек от 1, и средняя дисперсия близка 1.
Если можно достичь этого диапазона отклонений, то применяется диаграмма, и tsne искажение полезно.
Для эффективных способов настройки tsne, см. Ваттенберг, Вьегас и Джонсон [4].
[1] ван дер Маатен, Лоренс и Джеффри Хинтон. «Визуализация данных с помощью t-SNE». J. Machine Learning Research 9, 2008, стр. 2579-2605.
[2] ван дер Маатен, Лоренс. Барнс-Хат-СНЕ. arXiv:1301.3342 [cs.LG], 2013.
[3] Джейкобс, Роберт А. «Увеличение скорости конвергенции за счет адаптации скорости обучения». Нейронные сети 1.4, 1988, стр. 295-307.
[4] Ваттенберг, Мартин, Фернанда Вьегас и Ян Джонсон. «Эффективное использование t-SNE». Дистилл, 2016. Доступно по адресу How to Use t-SNE Effectively.