t-SNE (tsne
) алгоритм для сокращения размерности, которое является подходящим к визуализации высоко-размерных данных. Имя обозначает t - распределил Стохастическое Соседнее Встраивание. Идея состоит в том, чтобы встроить высоко-размерные точки в низкие размерности способом, который уважает общие черты между точками. Соседние точки в высоком мерном пространстве соответствуют поблизости встроенным низко-размерным точкам, и удаленные точки в высоком мерном пространстве соответствуют удаленным встроенным низко-размерным точкам. (Обычно невозможно совпадать с расстояниями точно между высоко-размерными и низкими мерными пространствами.)
tsne
функция создает набор низко-размерных точек из высоко-размерных данных. Как правило, вы визуализируете низко-размерные точки, чтобы видеть естественные кластеры в исходных высоко-размерных данных.
Алгоритм делает следующие общие шаги, чтобы встроить данные в низкие размерности.
Вычислите попарные расстояния между высоко-размерными точками.
Создайте стандартное отклонение σi для каждой высоко-размерной точки i так, чтобы perplexity каждой точки был на предопределенном уровне. Для определения недоумения смотрите, Вычисляют Расстояния, Гауссовы Отклонения и Общие черты.
Вычислите similarity matrix. Это - объединенное вероятностное распределение X, заданный уравнением 1.
Создайте начальный набор низко-размерных точек.
Итеративно обновите низко-размерные точки, чтобы минимизировать расхождение Kullback-Leibler между Распределением Гаусса в высоком мерном пространстве и распределением 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 строки i был равен Perplexity
пара "имя-значение". Недоумение задано в терминах Распределения Гаусса модели можно следующим образом. Как ван дер Маатен и Хинтон [1] описывают, “Подобие точки данных xj к точке данных xi является условной вероятностью, , тот xi выбрал бы xj как своего соседа, если бы соседи были выбраны пропорционально их плотности вероятности под Гауссовым, сосредоточенным в xi. Для соседних точек данных, относительно высоко, тогда как для широко разделенных точек данных, будет почти бесконечно малая величина (для рыночной стоимости отклонения Гауссова, σi)”.
Задайте условную вероятность j, данного i как
Затем задайте объединенную вероятность pij путем симметрирования условных вероятностей:
(1) |
где N является количеством строк X.
Распределениям все еще не задали их стандартные отклонения σi в терминах Perplexity
пара "имя-значение". Позволенный Pi представляет распределение условной вероятности по всей другой точке определенных данных точек данных xi. Недоумение распределения
где H (Pi) является шенноновской энтропией Pi:
Недоумение измеряет эффективное количество соседей точки i. tsne
выполняет двоичный поиск по σi, чтобы достигнуть фиксированного недоумения для каждой точки i.
Встроить точки в X в низкое мерное пространство, tsne
выполняет оптимизацию. tsne
попытки минимизировать расхождение Kullback-Leibler между Распределением Гаусса модели точек в X и Студентом распределение t точек Y в низком мерном пространстве.
Процедура минимизации начинается с начального набора точек Y. tsne
создайте точки по умолчанию как случайные Распределенные гауссовым образом точки. Можно также создать эти точки сами и включать их в 'InitialY'
пара "имя-значение" для tsne
. tsne
затем вычисляет общие черты между каждой парой точек в Y.
Вероятностная модель qij распределения расстояний между точками yi и yj
Используя это определение и модель расстояний в X данный уравнением 1, расхождением Kullback-Leibler между совместным распределением P и Q
Для последствий этого определения смотрите Полезное Нелинейное Искажение.
Минимизировать расхождение Kullback-Leibler, 'exact'
алгоритм использует модифицированную процедуру градиентного спуска. Градиент относительно точек в Y расхождения
где термин нормализации
Модифицированный алгоритм градиентного спуска использует несколько настраивающихся параметров, чтобы попытаться достигнуть хорошего локального минимума.
'Exaggeration'
— Во время первых 99 шагов градиентного спуска, tsne
умножает вероятности pij от уравнения 1 значением преувеличения. Этот шаг имеет тенденцию создавать больше пространства между кластерами в выходе Y.
'LearnRate'
— tsne
использует адаптивное обучение улучшить сходимость итераций градиентного спуска. Алгоритм спуска имеет итеративные шаги, которые являются линейной комбинацией предыдущего шага в спуске и текущем градиенте. 'LearnRate'
множитель текущего градиента для линейной комбинации. Для получения дополнительной информации смотрите Джейкобса [3].
Ускорить t-SNE алгоритм и сократить его использование памяти, tsne
предлагает аппроксимированную схему оптимизации. Алгоритм Barnes-хижины собирает в группу соседние точки, чтобы понизить сложность и использование памяти t-SNE шага оптимизации. Алгоритм Barnes-хижины является аппроксимированным оптимизатором, не точным оптимизатором. Существует неотрицательный настраивающий параметр Theta
это производит компромисс между скоростью и точностью. Большие значения 'Theta'
дайте более быстрые но менее точные результаты оптимизации. Алгоритм относительно нечувствителен к 'Theta'
значения в области значений (0.2 0.8).
Группы алгоритма Barnes-хижины поблизости указывают в низком мерном пространстве и выполняют аппроксимированный градиентный спуск на основе этих групп. Идея, первоначально используемая в астрофизике, состоит в том, что градиент подобен для соседних точек, таким образом, расчеты могут быть упрощены.
Смотрите ван дер Маатена [2].
Поскольку t-SNE часто разделяет кластеры данных хорошо, может казаться, что t-SNE может классифицировать новые точки данных. Однако t-SNE не может классифицировать новые точки. Встраивание t-SNE является нелинейной картой, которая информационно-зависима. Чтобы встроить новую точку в низкое мерное пространство, вы не можете использовать предыдущее встраивание в качестве карты. Вместо этого запустите целый алгоритм снова.
t-SNE может занять много времени, чтобы обработать данные. Если у вас есть точки данных N в размерностях D, которые вы хотите сопоставить с размерностями Y, то
Точные t-SNE взятия операций D *N2 порядка.
Barnes-хижина t-SNE взятия порядка D *Nlog (N) *exp (размерность (Y)) операции.
Таким образом для больших наборов данных, где N больше приблизительно 1000, и где размерность встраивания Y равняется 2 или 3, алгоритм Barnes-хижины может быть быстрее, чем точный алгоритм.
T-SNE сопоставляет высоко-размерные расстояния до искаженных низко-размерных аналогов. Из-за более толстого хвоста Студенческого t распределения в низком мерном пространстве, tsne
часто двигает близкие точки поближе вместе и перемещает далекие точки дальше независимо, чем в высоком мерном пространстве, как проиллюстрировано в следующем рисунке. Рисунок показывает и Гауссовы и Студенческие t распределения в точках, где плотность в 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
, смотрите Wattenberg, Виегаса и Джонсона [4].
[1] ван дер Маатен, Лоренс и Джеффри Хинтон. "Визуализируя Данные с помощью t-SNE". J. Исследование Машинного обучения 9, 2008, стр 2579–2605.
[2] ван дер Маатен, Laurens. Барнс-Хут-СН. arXiv:1301.3342 [cs.LG], 2013.
[3] Джейкобс, Роберт А. "Увеличил уровни сходимости посредством адаптации скорости обучения". Нейронные сети 1.4, 1988, стр 295–307.
[4] Wattenberg, Мартин, Фернанда Виегас и Иэн Джонсон. "Как Использовать t-SNE Эффективно". Дистиллируйте, 2016. Доступный в How to Use t-SNE Effectively
.