Tsne python что это

Препарируем t-SNE

Работая над статьей «Глубокое обучение на R. », я несколько раз встречал упоминание t-SNE — загадочной техники нелинейного снижения размерности и визуализации многомерных переменных (например, здесь), был заинтригован и решил разобраться во всем в деталях. t-SNE это t-distributed stochastic neighbor embedding. Русский вариант с «внедрением соседей» в некоторой мере звучит нелепо, поэтому дальше буду использовать английский акроним.

Алгоритм t-SNE, который также относят к методам множественного обучения признаков, был опубликован в 2008 году (ссылка 1 в конце статьи) голландским исследователем Лоуренсом ван дер Маатеном (сейчас работает в Facebook AI Research) и чародеем нейронных сетей Джеффри Хинтоном. Классический SNE был предложен Хинтоном и Ровейсом в 2002 (ссылка 2). В статье 2008 года описывается несколько «трюков», которые позволили упростить процесс поиска глобальных минимумов, и повысить качество визуализации. Одним из них стала замена нормального распределения на распределение Стьюдента для данных низкой размерности. Кроме того, была сделана удачная реализация алгоритма (в статье есть ссылка на MatLab), которая потом портировалась в другие популярные среды.

Немного математики

Начнем с «классического» SNE и сформулируем задачу. У нас есть набор данных с точками, описываемыми многомерной переменной с размерностью пространства существенно больше трех. Необходимо получить новую переменную, существующую в двумерном или трехмерном пространстве, которая бы в максимальной степени сохраняла структуру и закономерности в исходных данных. SNE начинается с преобразования многомерной евклидовой дистанции между точками в условные вероятности, отражающие сходство точек. Математически это выглядит следующим образом (формула 1):

Эта формула показывает, насколько точка X_j близка к точке X_i при гауссовом распределении вокруг X_i с заданным отклонением σ. Сигма будет различной для каждой точки. Она выбирается так, чтобы точки в областях с большей плотностью имели меньшую дисперсию. Для этого используется оценка перплексии:

Где H(Pi) – энтропия Шеннона в битах (формула 2):

В данном случае перплексия может быть интерпретирована как сглаженная оценка эффективного количества «соседей» для точки X_i. Она задается в качестве параметра метода. Авторы рекомендуют использовать значение в интервале от 5 до 50. Сигма определяется для каждой пары X_i и X_j при помощи алгоритма бинарного поиска.

Для двумерных или трехмерных «коллег» пары X_i и X_j, назовем их для ясности Y_i и Y_j, не представляет труда оценить условную вероятность, используя ту же формулу 1. Стандартное отклонение предлагается установить в 1/√2:

Если точки отображения Y_i и Y_j корректно моделируют сходство между исходными точками высокой размерности X_i и X_j, то соответствующие условные вероятности p_j|i и q_j|i будут эквивалентны. В качестве очевидной оценки качества, с которым q_j|i отражает p_j|i, используется дивергенция или расстояние Кульбака-Лейблера. SNE минимизирует сумму таких расстояний для всех точек отображения при помощи градиентного спуска. Функция потерь для данного метода будет определяться формулой 3:

При этом градиент выглядит на удивление просто:

Авторы предлагают следующую физическую аналогию для процесса оптимизации: Все точки отображения соединены пружинами. Жесткость пружины, соединяющей точки i и j зависит от разности между сходством двух точек в многомерном пространстве и двух точек в пространстве отображения. В этой аналогии, градиент — это результирующая сила, действующая на точку в пространстве отображения. Если систему «отпустить», через какое-то время она придет в равновесие, это и будет искомое распределение. Алгоритмически, поиск равновесия предлагается делать с учетом моментов:

где η – параметр, определяющий скорость обучения (длину шага), а α – коэффициент инерции. Использование классического SNE позволяет получить неплохие результаты, но может быть связано с трудностями в оптимизации функции потерь и проблемой скученности (в оригинале – crowding problem). t-SNE если и не решает эти проблемы совсем, то существенно облегчает. Функция потерь t-SNE имеет два принципиальных отличая. Во-первых, у t-SNE симметричная форма сходства в многомерном пространстве и более простой вариант градиента. Во-вторых, вместо гауссова распределения для точек из пространства отображения используется t-распределение (Стьюдента), «тяжелые» хвосты которого облегчают оптимизацию и решают проблему скученности.

В качестве альтернативы минимизации суммы дивергенций Кульбака-Лейблера между условными вероятностями p_i|j и q_i|j предлагается минимизировать одиночную дивергенцию между совместной вероятностью P в многомерном пространстве и совместной вероятностью Q в пространстве отображения:

где p_ii и q_ii = 0, p_ij = p_ji, q_ij = q_ji для любых i и j, а p_ij определяется по формуле:

где n — количество точек в наборе данных. Градиент для симметричного SNE получается существенно проще, чем для классического:

Проблема скученности заключается в том, что расстояние между двумя точками в пространстве отображения, соответствующими двум среднеудаленным точкам в многомерном пространстве, должно быть существенно больше, нежели расстояние, которое позволяет получить гауссово распределение. Проблему решают хвосты Стьюдента. В t-SNE используется t-распределение с одной степенью свободы. Совместная вероятность для пространства отображения в этом случае будет определяться формулой 4:

А соответствующий градиент – выражением 5:

Возвращаясь к физической аналогии, результирующая сила, определяемая формулой 5, будет существенным образом стягивать точки пространства отображения для близлежащих точек многомерного пространства, и отталкивать — для удаленных.

Алгоритм

Алгоритм t-SNE в упрощенном виде можно представить следующим псевдокодом:

Data: набор данных X = , параметр функции потерь: перплексия Perp, Параметры оптимизации: количество итераций T, скорость обучения η, момент α(t). Result: представление данных Y(T) = (в 2D или 3D). begin вычислить попарное сходство pj|i c перплексией Perp (используя формулу 1) установить pij = (pj|i + pi|j)/2n инициализировать Y(0) = точками нормального распределения (mean=0, sd=1e-4) for t = 1 to T do вычислить сходство точек в пространстве отображения qij (по формуле 4) вычислить градиент δCost/δy (по формуле 5) установить Y(t) = Y(t-1) + ηδCost/δy + α(t)(Y(t-1) - Y(t-2)) end end

Чтобы улучшить результат предлагается использовать два трюка. Первый авторы назвали «ранней компрессией». Его задача – заставить точки в пространстве отображения в начале оптимизации быть как можно ближе друг к другу. Когда дистанция между точками отображения невелика, перемещать один кластер через другой существенно легче. Так гораздо проще исследовать пространство оптимизации и «нацелиться» на глобальные минимумы. Ранняя компрессия создается за счет добавочного L2-штрафа в функции потерь, который пропорционален сумме квадратов дистанций точек отображения от начала координат (в исходном коде этого не нашел).

Второй трюк менее очевидный — «раннее гиперусиление» (в оригинале – «early exaggeration»). Заключается он в умножении в начале оптимизации всех p_ij на некоторое целое число, например на 4. Смысл в том, чтобы для больших p_ij получить бόльшие q_ij. Это позволит для кластеров в исходных данных получить плотные и широко разнесенные кластеры в пространстве отображения.

Реализация на R

В качестве исходного кода я взял оригинальную MatLab реализацию ван дер Маатена. Однако академическая лицензия на MatLab у меня давно закончилась, поэтому весь код я портировал на R. Код доступен в репозитарии. Также в моем распоряжении был код из архива R-пакета tsne, взял оттуда пару идей.

Для экспериментов предлагается использовать следующие параметры:
Количество итераций: 1000;
Перплексия: 40;
Раннее гиперусиление: х4 для первых 50 итераций;
Момент α: 0.5 для первых 250 итераций, 0.8 для оставшихся 750;
Скорость обучения η: первоначально 100 (в оригинальном коде — 500) и изменяется после каждой итерации в соответствие со схемой, описанной Робертом Джекобсом в 1988 (ссылка 3).

1. Вычисление перплексии и гауссового ядра для вектора текущих значений сигма (вернее gamma, я использовал переменную, обратную квадрату сигма)
2. Вычисление попарного сходства p_ij в многомерном пространстве при помощи бинарного поиска для заданной перплексии
3. Вычисление попарного сходства для пространства отображения, функции потерь и градиента

Проиллюстрирую только самые важные конструкции. Прежде всего, необходимо рассчитать матрицу квадратов евклидовой дистанции для исходного набора данных. Для этого лучше использовать функцию rdist() из пакета fields. Она работает в разы быстрее, чем популярная dist() из базового пакета stats. Возможно, это по тому, что она оптимизирована именно для евклидовой дистанции. Далее нужно инициализировать пространство отображения. Это можно сделать при помощи rnorm() с нулевым мат. ожиданием и стандартным отклонением 1е-4.

Расчет логарифма перплексии и гауссового ядра выглядит следующим образом:

Для поиска gamma существуют следующие ограничения – количество попыток (делений) — не более 50, порог разницы между логарифмами заданной и вычисленной перплексии 1e-5. Одна итерация бинарного поиска выглядит следующим образом:

 if (perpDiff > 0) < gammamin = gamma[i] if (is.infinite(gammamax)) gamma[i] = gamma[i] * 2 else gamma[i] = (gamma[i] + gammamax)/2 >else < gammamax = gamma[i] if (is.infinite(gammamin)) gamma[i] = gamma[i]/ 2 else gamma[i] = ( gamma[i] + gammamin) / 2 >

gammamin и gammamax изначально устанавливаются в – и + Inf.

Функция потерь считается как сумма по строкам поэлементного произведения двух матриц n x n:

cost = sum(apply(P * log(P/Q),1,sum)) 

P – симметричная версия совместной вероятности для многомерного пространства, рассчитывается как P = .5 * (P + t(P)) из условной попарной вероятности, t – оператор транспонирования матриц. Q – совместная вероятность для пространства отображения:

 num = 1/(1 + (rdist(Y))^2) diag(num)=0 # Set diagonal to zero Q = num / sum(num) # Normalize to get probabilities 

Y – инициализированная матрица точек n x 2 для двумерного пространства отображения. Q получается матрицей n x n за счет использования rdist().

Градиент рассчитывается в векторизованной форме сразу для всех Yi:

L = (P - Q) * num; grads = 4 * (diag(apply(L, 1, sum)) - L) %*% Y 

Здесь grads это матрица, размером n x 2, которая образуется за счет матричного произведения. Конструкция в круглых скобках — матрица размера n x n, на главной диагонали которой построчные суммы матрицы L, а все остальные элементы взяты со знаком минус. Матричное произведение позволяет умножить на разность Y_i и Y_j и сразу посчитать суммы по j (формула 4). Правда градиент получается обратного знака.

Для поиска оптимальных значений Y используется что-то похожее на эвристику Роберта Джекобса «дельта-бар-дельта». Смысл её в том чтобы адаптивно изменять шаг обучения. Если градиент не меняет свой знак на очередной итерации, шаг увеличивается линейно (к коэффициенту усиления добавляется 0.2), если знак меняется — то уменьшается экспоненциально (коэффициент умножается на 0.8). С учетом того, что градиент у нас обратного знака:

gains = (gains + .2) * abs(sign(grads) != sign(incs)) + gains * .8 * abs(sign(grads) == sign(incs)) gains[gains < min_gain] = min_gain incs = momentum * incs - gains * epsilon * grads Y = Y + incs 

Эксперименты

Я не мог не попробовать повторить эксперимент, описанный в статье (ссылка 1). Идея этого эксперимента – в визуализации структуры кластеров для набора изображений MNIST. Одна из частей этого набора содержит 60000 изображений рукописных цифр от 0 до 9, 28х28 пикселей. Набор данных можно загрузить с сайта гуру нейронных сетей, Яна Лекуна.

С загрузкой в R придется повозиться, но помогает функция readBin(), которая позволяет читать (и записывать) бинарные данные. 20 случайных цифр:

Как и в оригинальном эксперименте я использовал не весь набор, а только 6000 изображений, выбранных случайным образом при помощи функции sample(). 1000 итераций заняла чуть менее полутора часов на x64 c Intel Core i7 2.4 GHz. Результат на картинке:

Цвета задаются при помощи меток, MNIST – это размеченный набор данных. Результат можно существенно улучшить. Как советуют авторы, для исходного набора точек следует сделать анализ главных компонент (PCA) и выбрать первые 30:

Существует несколько реализаций PCA для R. Простейший вариант в две строки:

Скорость алгоритма пропорциональна квадрату количества точек. Если это количество уменьшить, результат будет не таким наглядным, но вполне приемлемым. Скажем, 2000 точек обрабатываются всего за 9 минут.

Техника t-SNE не была бы, наверное, так популярна, если бы не возможность визуализации распределенного представления слов. В этом эксперименте я использовал сравнительно небольшую модель (около 900 слов и 300-мерное пространство признаков), обученную при помощи word2vec.

Здесь размер побольше. Используется трехмерное пространство отображения, третье измерение представлено цветом. Слова можно считать близкими, если они расположены рядом и имеют один и тот же оттенок.

Оказывается, с распределенным представлением слов, подготовленным на реальных данных, не всё так просто. Проблем две: как правило, очень большое количество кластеров и существенные различия по их размеру. Для визуализации можно сделать случайную выборку, однако результат будет, скорее всего, не репрезентативным. Авторы объясняют это на следующем примере: Если A, B и С — равноудаленные точки в многомерном пространстве, но между A и B есть еще точки, а между B и C нет, то алгоритм с большей вероятностью объединит A и B в один кластер нежели B и C.

Но бывает так, что важна именно наглядность, а не полнота картины. Тогда вместо случайной выборки точек можно попробовать отобрать интересные кластеры. Кластеризация встроена в оригинальный word2vec, кроме того можно использовать k-means. Возможно, этот вариант покажется не совсем «честным», но, на мой взгляд, имеет право на существование. Выборка данных для распределенного представления слов из пятнадцати кластеров выглядит уже не такой запутанной:

Для больших наборов данных есть специальная реализация t-SNE, в которой для вычисления сходства в многомерном пространстве используются деревья ближайших соседей и метод случайного блуждания (описана в статье 1). На практике можно использовать пакет Rtsne, обертку для C++ реализации Barnes-Hut-SNE. Rtsne позволяет обработать все 60000 изображений MNIST менее чем за час. Подробности можно посмотреть в публикации 6.

С Rtsne я еще не экспериментировал, а вот tsne (порт MatLab-овского кода для R) испытал. Визуализация получается гораздо хуже, чем мой вариант. Заглянув в архив пакета я обнаружил две вещи: Во-первых, при расчете гауссового ядра дистанция используется без квадарата, во-вторых, в выражении для перплексии стоит матричное произведение. В моей версии и в коде для MatLab оно поэлементное. Странно, что вообще получились видимые кластеры. Объясняю это «живучестью» алгоритма, но допускаю, что в чем-то я не до конца разобрался. Буду рад замечаниям и желаю всем впечатляющих многомерных визуализаций.

Формулы для этой статьи подготовлены при помощи онлайн редактора формул LATEX.

Ссылки:

1. L.J.P. van der Maaten and G.E. Hinton. Visualizing High-Dimensional Data Using t-SNE. Journal of Machine Learning Research 9(Nov):2579-2605, 2008. PDF
2. G.E. Hinton and S.T. Roweis. Stochastic Neighbor Embedding. In Advances in Neural Information. Processing Systems, volume 15, pages 833–840, Cambridge, MA, USA, 2002. The MIT Press. PDF
3. R.A. Jacobs. Increased rates of convergence through learning rate adaptation. Neural Networks, 1: 295–307, 1988. PDF
4. Эксперименты с t-SNE на Python: Алгоритм t-SNE. Иллюстрированный вводный курс (перевод оригинальной статьи на O’Reilly). datareview.info/article/algoritm-t-sne-illyustrirovannyiy-vvodnyiy-kurs
5. Rtsne против tsne: www.codeproject.com/Tips/788739/Visualization-of-High-Dimensional-Data-using-t-SNE Здесь же доступен набор данных для экспериментов с распределенным представлением слов.
6. L.J.P. van der Maaten. Accelerating t-SNE using Tree-Based Algorithms. Journal of Machine Learning Research 15(Oct):3221-3245, 2014. PDF

• R
• t-SNE
• снижение размерности
• визуализация данных
• deep learning

Алгоритм машинного обучения t-SNE — отличный инструмент для снижения размерности в Python

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

В этой статье вы познакомитесь с одним из таких методов. Он называется t-SNE, что расшифровывается как t-distributed stochastic neighbor embedding (стохастическое вложение соседей с t-распределением).

Стохастическое вложение соседей с t-распределением (t-SNE) в мире алгоритмов машинного обучения

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

Все же иногда полезно привнести некую структурированность в огромный мир МО. Приведенный ниже интерактивный граф является моей попыткой сделать именно это.

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

Хотя это не проиллюстрировано на приведенном графике, стоит знать, что методы уменьшения размерности можно дополнительно разделить на два типа:

• Параметрический — создающий явную функцию отображения, которую можно использовать для тестовых данных, т.е. для определения местоположения новых точек во вложении с более низкой размерностью (например, PCA);
• Непараметрический — не создающий явной функции отображения, т.е. не способный точно отобразить новые точки во вложении с более низкой размерностью. Тем не менее,на практике можно создать обходные пути для обеспечения такого отображения новых точек.

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

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

Анализ названия метода t-SNE

Чтобы составить общее представление о работе алгоритма, начнем с анализа названия t-SNE.

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

• вложение — многомерные данные, представленные в пространстве меньшей размерности;
• сосед — точка данных, расположенная близко к интересующей нас точке данных;
• стохастический — случайно используемый в итерационном процессе при поиске репрезентативного вложения;
• t-распределение — распределение вероятности, используемое алгоритмом для вычисления оценок сходства в низкоразмерном вложении.

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

Обратите внимание, что для общего понимания этого алгоритма не стоит уделять много внимания элементу вероятностного распределения. t-распределение, используемое на 2-м и 3-м этапе, отличается “более плоской” формой с “более высокими” “хвостами”. Такая форма позволяет распределить точки в пространстве с более низкой размерностью. В противном случае вы можете получить кучу точек, нагроможденных друг на друга.

Этапы работы алгоритма t-SNE

Этап 1

t-SNE начинается с определения сходства точек на основе расстояний между ними. Близлежащие точки считаются похожими, в то время как удаленные считаются непохожими.

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

Например, на приведенной ниже иллюстрации мы наблюдаем более высокую плотность в секции, занятой синими точками, и более низкую плотность в секции, занятой желтыми точками.

Результатом этих вычислений является матрица, содержащая оценки сходства между каждой парой точек из исходного многомерного пространства.

Этап 2

Далее переходим к t-SNE, который рандомно отображает все точки в более низкоразмерном пространстве и вычисляет сходство между ними, как описано выше. Правда, с одним отличием: на этот раз алгоритм использует t-распределение вместо нормального распределения.

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

Этап 3

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

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

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

Перплексия

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

Параметр перплексии играет важнейшую роль в определении конечного результата вложения. Как правило, можно выбрать значение перплексии где-то между 5 и 50, но при этом обязательно следует поэкспериментировать с другими значениями.

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

Как использовать t-SNE в Python?

Теперь, когда вы поняли механизм работы алгоритма, самое время поговорить об использовании его в Python.

Применим t-SNE к набору данных MNIST (набору рукописных цифр), чтобы увидеть, насколько успешно визуализируются данные высокой размерности.

Настройка

Будем использовать следующие данные и библиотеки:

• Scikit-learn библиотека для:
  1) данных образцов цифр MNIST из набора данных sklearn (load_digits);
  2) выполнения уменьшения размерности (t-SNE);
• Plotly и Matplotlib для визуализации данных;
• Pandas для манипулирования данными.

Первым шагом является импорт библиотек, которые мы перечислили выше:

# Манипулирование данными
import pandas as pd # для манипулирования данными

# Визуализация
import plotly.express as px # для визуализации данных
import matplotlib.pyplot as plt # для отображения рукописных цифр

# Sklearn
from sklearn.datasets import load_digits # для данных MNIST
from sklearn.manifold import TSNE # для снижения размерности с помощью t-SNE

Затем загружаем данные MNIST:

# Загрузка данных образцов цифр
digits = load_digits()

# Загрузка массивов, содержащих данные образцов цифр (64 пикселя на изображение) и их истинных меток
X, y = load_digits(return_X_y=True)

# Статистические данные
print('Shape of digit images: ', digits.images.shape)
print('Shape of X (training data): ', X.shape)
print('Shape of y (true labels): ', y.shape)

Теперь выведем первые десять написанных от руки цифр, чтобы лучше понимать, с чем мы работаем.

# Отображение изображений первых 10 цифр
fig, axs = plt.subplots(2, 5, sharey=False, tight_layout=True, figsize=(12,6), facecolor='white')
n=0
plt.gray() 
for i in range(0,2): 
for j in range(0,5): 
axs[i,j].matshow(digits.images[n]) 
axs[i,j].set(title=y[n]) 
n=n+1
plt.show()

Применение t-SNE к выбранным данным

На предыдущем шаге мы загрузили данные в массив X формы (1797,64), что означает, что у нас 1797 цифр, каждая из которых является 64-мерной.

Теперь будем использовать t-SNE, чтобы уменьшить размерность с 64 до 2. Обратите внимание, что я использую значения по умолчанию для большинства гиперпараметров. Я также включил краткие пояснения к каждому параметру, чтобы вы могли поэкспериментировать, опробовав различные настройки.

# Настройка функции t-SNE.
embed = TSNE( 
n_components=2, # значение по умолчанию=2. Размерность вложенного пространства. 
perplexity=10, # значение по умолчанию=30.0. Перплексия связана с количеством ближайших соседей, которое используется в других алгоритмах обучения на множествах. 
early_exaggeration=12, # значение по умолчанию=12.0. Определяет, насколько плотными будут естественные кластеры исходного пространстве во вложенном пространстве и сколько места будет между ними. 
learning_rate=200, # значение по умолчанию=200.0. Скорость обучения для t-SNE обычно находится в диапазоне [10.0, 1000.0]. Если скорость обучения слишком высока, данные могут выглядеть как "шар", в котором любая точка приблизительно равноудалена от ближайших соседей. Если скорость обучения слишком низкая, большинство точек могут быть похожими на сжатое плотное облако с незначительным количеством разбросов. 
n_iter=5000, # значение по умолчанию=1000. Максимальное количество итераций для оптимизации. Должно быть не менее 250. 
n_iter_without_progress=300, # значение по умолчанию=300. Максимальное количество итераций без прогресса перед прекращением оптимизации, используется после 250 начальных итераций с ранним преувеличением. 
min_grad_norm=0.0000001, # значение по умолчанию=1e-7. Если норма градиента ниже этого порога, оптимизация будет остановлена. 
metric='euclidean', # значение по умолчанию='euclidean', Метрика, используемая при расчете расстояния между экземплярами в массиве признаков. 
init='random', или ndarray формы (n_samples, n_components), значение по умолчанию='random'. Инициализация вложения. 
verbose=0, # значение по умолчанию=0. Уровень детализации. 
random_state=42, # экземпляр RandomState или None, по умолчанию=None. Определяет генератор случайных чисел. Передача int для воспроизводимых результатов при многократном вызове функции. 
method='barnes_hut', # значение по умолчанию='barnes_hut'. По умолчанию алгоритм вычисления градиента использует аппроксимацию Барнса-Хата, работающую в течение времени O(NlogN). метод='exact' будет работать по более медленному, но точному алгоритму за время O(N^2). Следует использовать точный алгоритм, когда количество ошибок ближайших соседей должно быть ниже 3%. 
angle=0.5, # значение по умолчанию=0.5. Используется только если метод='barnes_hut' Это компромисс между скоростью и точностью в случае T-SNE с применением алгоритма Барнса-Хата. 
n_jobs=-1, # значение по умолчанию=None. Количество параллельных заданий для поиска соседей. -1 означает использование всех процессоров.
)

# Преобразование X
X_embedded = embed.fit_transform(X)

# Вывод результатов
print('New Shape of X: ', X_embedded.shape)
print('Kullback-Leibler divergence after optimization: ', embed.kl_divergence_)
print('No. of iterations: ', embed.n_iter_)
#вывод('Embedding vectors: ', embed.embedding_)

Приведенный выше код выводит основные статистические данные:

Наконец, давайте построим новый массив X в виде 2-мерной диаграммы разброса. Обратите внимание, что при ее создании использованы различные цвета для представления фактических меток цифр. Это помогает увидеть, как сходные цифры группируются вместе.

# Создание диаграммы разброса
fig = px.scatter(None, x=X_embedded[:,0], y=X_embedded[:,1], 
labels= "x": "Dimension 1", 
"y": "Dimension 2", 
>, 
opacity=1, color=y.astype(str))

# Изменение цвета фона графика
fig.update_layout(dict(plot_bgcolor = 'white'))

# Обновление линий осей
fig.update_xaxes(showgrid=True, gridwidth=1, gridcolor='lightgrey', 
zeroline=True, zerolinewidth=1, zerolinecolor='lightgrey', 
showline=True, linewidth=1, linecolor='black')

fig.update_yaxes(showgrid=True, gridwidth=1, gridcolor='lightgrey', 
zeroline=True, zerolinewidth=1, zerolinecolor='lightgrey', 
showline=True, linewidth=1, linecolor='black')

# Установка названия рисунка
fig.update_layout(title_text="t-SNE")

# Обновление размера маркера
fig.update_traces(marker=dict(size=3))

fig.show()

Мы видим, что алгоритм t-SNE проделал довольно хорошую работу по выявлению схожих цифр, причем большинство из них образовали плотные группы. Однако есть несколько небольших кластеров, а именно 1 (красный), 3 (фиолетовый) и 9 (желтый), которые, по-видимому, довольно далеки от своих основных групп. Такие результаты могут указывать на существование различных способов написания одной и той же цифры.

Заключение

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

Например, он поможет определить различные варианты написания одной и той же цифры или найти синонимы слов / фразы со схожим значением при выполнении анализа НЛП. Вы также можете использовать его в качестве наглядного пособия при объяснении выполненного анализа заинтересованным сторонам.

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

1. t-SNE предполагает непараметрический подход к уменьшению размерности, то есть алгоритм не создает явной функции отображения для использования относительно новых точек данных.
2. Возможно, вам придется поэкспериментировать с различными значениями перплексии, чтобы найти то, которое лучше всего подходит для ваших данных.
3. Вы можете получать разные результаты после каждого запуска из-за случайной инициализации и стохастического характера. Если вам нужны воспроизводимые результаты, обязательно укажите начальное значение (random_state).

• Объяснение понятий вероятности: оценка максимального правдоподобия
• Обработка естественного языка для анализа отзывов онлайн-покупателей
• Моделирование логистического роста

Алгоритм t-SNE. Иллюстрированный вводный курс

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

Многие реальные наборы данных имеют малую внутреннюю размерность, даже если они вложены в пространство большой размерности.

Представьте, что вы фотографируете панорамный пейзаж, поворачиваясь вокруг своей оси. Мы можем рассматривать каждую фотографию, как точку в 16 000 000-мерном пространстве (при использовании камеры с разрешением 16 мегапикселей). При этом набор фотографий лежит в трехмерном пространстве (рыскание, тангаж, крен). То есть пространство малой размерности вложено в пространство большой размерности сложным нелинейным образом. Эта структура, скрытая в данных, может быть восстановлена только с помощью специальных математических методов.

К ним относится подраздел машинного обучения без учителя под названием множественное обучение (manifold learning) или нелинейное уменьшение размерности (nonlinear dimensionality reduction).

Эта статья — введение в популярный алгоритм уменьшения размерности под названием t-SNE (t-distributed stochastic neighbor embedding, стохастическое вложение соседей с распределением Стьюдента). Разработанный Лоренсом ван дер Маатеном и Джеффри Хинтоном, он был успешно применен ко многим реальным наборам данных.

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

Визуализация рукописных цифр

Для начала импортируем библиотеки.

# That's an impressive list of imports. import numpy as np from numpy import linalg from numpy.linalg import norm from scipy.spatial.distance import squareform, pdist # We import sklearn. import sklearn from sklearn.manifold import TSNE from sklearn.datasets import load_digits from sklearn.preprocessing import scale # We'll hack a bit with the t-SNE code in sklearn 0.15.2. from sklearn.metrics.pairwise import pairwise_distances from sklearn.manifold.t_sne import (_joint_probabilities, _kl_divergence) from sklearn.utils.extmath import _ravel # Random state. RS = 20150101 # We'll use matplotlib for graphics. import matplotlib.pyplot as plt import matplotlib.patheffects as PathEffects import matplotlib %matplotlib inline # We import seaborn to make nice plots. import seaborn as sns sns.set_style('darkgrid') sns.set_palette('muted') sns.set_context("notebook", font_scale=1.5, rc=) # We'll generate an animation with matplotlib and moviepy. from moviepy.video.io.bindings import mplfig_to_npimage import moviepy.editor as mpy

Теперь загрузим классический набор данных, содержащий рукописные цифры . Он состоит из 1797 изображений с разрешением 8 * 8 = 64 пикселя каждое.

digits = load_digits() digits.data.shape

print(digits['DESCR'])

Ниже представлены изображения цифр:

nrows, ncols = 2, 5 plt.figure(figsize=(6,3)) plt.gray() for i in range(ncols * nrows): ax = plt.subplot(nrows, ncols, i + 1) ax.matshow(digits.images[i. ]) plt.xticks([]); plt.yticks([]) plt.title(digits.target[i]) plt.savefig('images/digits-generated.png', dpi=150)

Применим к набору данных алгоритм t-SNE. Благодаря scikit-learn, для этого требуется всего одна строка кода.

# We first reorder the data points according to the handwritten numbers. X = np.vstack([digits.data[digits.target==i] for i in range(10)]) y = np.hstack([digits.target[digits.target==i] for i in range(10)])

digits_proj = TSNE(random_state=RS).fit_transform(X)

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

def scatter(x, colors): # We choose a color palette with seaborn. palette = np.array(sns.color_palette("hls", 10)) # We create a scatter plot. f = plt.figure(figsize=(8, 8)) ax = plt.subplot(aspect='equal') sc = ax.scatter(x[:,0], x[:,1], lw=0, s=40, c=palette[colors.astype(np.int)]) plt.xlim(-25, 25) plt.ylim(-25, 25) ax.axis('off') ax.axis('tight') # We add the labels for each digit. txts = [] for i in range(10): # Position of each label. xtext, ytext = np.median(x[colors == i, :], axis=0) txt = ax.text(xtext, ytext, str(i), fontsize=24) txt.set_path_effects([ PathEffects.Stroke(linewidth=5, foreground="w"), PathEffects.Normal()]) txts.append(txt) return f, ax, sc, txts

Получим следующий результат.

scatter(digits_proj, y) plt.savefig('images/digits_tsne-generated.png', dpi=120)

Мы видим, что изображения, соответствующие различным цифрам, четко разделены на группы.

Математическая база

Давайте разберемся, как работает алгоритм. Сначала дадим несколько определений.

Точка данных (data point) – это точка x _i в исходном пространстве данных R D (data space), где D = 64 – размерность (dimensionality) пространства данных. Каждая точка данных – это изображение рукописной цифры. Всего N = 1797 точек данных.

Точка отображения (map point) – это точка y _i в пространстве отображения R 2 (map space). Это пространство будет содержать целевое представление набора данных. Между точками данных и точками отображения имеет место биекция (bijection): каждая точка отображения представляет одно исходное изображение.

Как нам выбрать расположение точек отображения? Мы хотим сохранить структуру данных. Более конкретно, если две точки данных расположены близко друг к другу, мы хотим, чтобы две соответствующие точки отображения также располагались близко друг к другу. Пусть | x _i — x _j | – евклидово расстояние между двумя точками данных, а | y _i — y _j | – расстояние между точками отображения. Сначала определим условное сходство (conditional similarity) для двух точек данных:

Это выражение показывает, насколько точка x _j близка к x _i , при гауссовом распределении вокруг x _i с заданной дисперсией σ _i 2 . Дисперсия различна для каждой точки. Она выбирается таким образом, чтобы точки, расположенные в областях с большой плотностью, имели меньшую дисперсию, чем точки, расположенные в областях с малой плотностью. В публикации детально описано, как вычисляется данная дисперсия.

Теперь определим сходство, как симметричный вариант условного сходства:

Получаем матрицу сходства (similarity matrix) для исходного набора данных. Как же выглядит эта матрица?

Матрица сходства

Следующая функция вычисляет сходство с постоянной σ .

def _joint_probabilities_constant_sigma(D, sigma): P = np.exp(-D**2/2 * sigma**2) P /= np.sum(P, axis=1) return P

Затем вычислим сходство при σ _i , зависящей от точки данных (находится с помощью двоичного поиска (binary search) согласно публикации). Этот алгоритм реализован в функции _joint_probabilities библиотеки scikit-learn.

# Pairwise distances between all data points. D = pairwise_distances(X, squared=True) # Similarity with constant sigma. P_constant = _joint_probabilities_constant_sigma(D, .002) # Similarity with variable sigma. P_binary = _joint_probabilities(D, 30., False) # The output of this function needs to be reshaped to a square matrix. P_binary_s = squareform(P_binary)

Теперь мы можем вывести матрицу расстояний (distance matrix) для точек данных и матрицу сходства при постоянной и переменной дисперсии.

plt.figure(figsize=(12, 4)) pal = sns.light_palette("blue", as_cmap=True) plt.subplot(131) plt.imshow(D[::10, ::10], interpolation='none', cmap=pal) plt.axis('off') plt.title("Distance matrix", fontdict=) plt.subplot(132) plt.imshow(P_constant[::10, ::10], interpolation='none', cmap=pal) plt.axis('off') plt.title("$p_$ (constant $\sigma$)", fontdict=) plt.subplot(133) plt.imshow(P_binary_s[::10, ::10], interpolation='none', cmap=pal) plt.axis('off') plt.title("$p_$ (variable $\sigma$)", fontdict=) plt.savefig('images/similarity-generated.png', dpi=120)

Мы уже видим 10 групп данных, соответствующих 10 цифрам.

Давайте также определим матрицу сходства для точек отображения.

Здесь применяется такой же подход, как и для точек данных, но используется другое распределение ( распределение Стьюдента с одной степенью свободы (t-Student with one degree of freedom) или распределение Коши (Cauchy distribution) вместо гауссового распределения). Мы подробно обсудим этот выбор ниже.

В то время как матрица сходства для данных ( p _ij ) является постоянной, матрица сходства для отображения ( q _ij ) зависит от точек отображения. Мы стремимся к тому, чтобы две эти матрицы были максимально близкими. Это будет означать, что сходные точки данных дают сходные точки отображения.

Физическая аналогия

Представим, что все точки отображения соединены пружинами. Жесткость пружины, соединяющей точки i и j , зависит от разности между сходством двух точек данных и сходством двух точек отображения, т.е. p _ij — q _ij . Теперь мы позволим системе изменяться согласно законам физики. Если расстояние между двумя точками отображения большое, а между точками данных малое, – точки отображения притягиваются. Если наоборот – точки отображения отталкиваются.

Целевое отображение будет получено при достижении равновесия.

Представленная ниже иллюстрация демонстрирует процесс динамического формирования структуры графа, основанный на аналогичном подходе. Узлы соединены пружинами, и система изменяется согласно законам физики (автор примера – Майк Босток (Mike Bostock).

Алгоритм

Примечательно то, что эта физическая аналогия естественным образом вытекает из математического алгоритма. Она соответствует минимизации расстояния Кульбака-Лейблера (Kullback-Leibler divergence) между двумя распределениями ( p _ij ) и ( q _ij ):

Данная формула выражает расстояние между двумя матрицами сходства.

Чтобы минимизировать эту величину, применим градиентный спуск (gradient descent). Градиент может быть вычислен аналитически:

Здесь u _ij – единичный вектор, идущий от y _j к y _i . Этот градиент выражает сумму всех сил, приложенных к точке отображения i .

Проиллюстрируем этот процесс с помощью анимации. Необходимо реализовать «обезьяний патч» ( monkey patch) для внутренней функции _gradient_descent(), которая присутствует в реализации t-SNE в библиотеке scikit-learn, чтобы иметь возможность регистрировать положение точек отображения на каждой итерации.

# This list will contain the positions of the map points at every iteration. positions = [] def _gradient_descent(objective, p0, it, n_iter, n_iter_without_progress=30, momentum=0.5, learning_rate=1000.0, min_gain=0.01, min_grad_norm=1e-7, min_error_diff=1e-7, verbose=0, args=[]): # The documentation of this function can be found in scikit-learn's code. p = p0.copy().ravel() update = np.zeros_like(p) gains = np.ones_like(p) error = np.finfo(np.float).max best_error = np.finfo(np.float).max best_iter = 0 for i in range(it, n_iter): # We save the current position. positions.append(p.copy()) new_error, grad = objective(p, *args) error_diff = np.abs(new_error - error) error = new_error grad_norm = linalg.norm(grad) if error n_iter_without_progress: break if min_grad_norm >= grad_norm: break if min_error_diff >= error_diff: break inc = update * grad >= 0.0 dec = np.invert(inc) gains[inc] += 0.05 gains[dec] *= 0.95 np.clip(gains, min_gain, np.inf) grad *= gains update = momentum * update - learning_rate * grad p += update return p, error, i sklearn.manifold.t_sne._gradient_descent = _gradient_descent

Выполним алгоритм еще раз, но теперь сохраним все промежуточные положения.

X_proj = TSNE(random_state=RS).fit_transform(X)

X_iter = np.dstack(position.reshape(-1, 2) for position in positions)

Создадим анимацию с помощью библиотеки MoviePy.

f, ax, sc, txts = scatter(X_iter[. -1], y) def make_frame_mpl(t): i = int(t*40) x = X_iter[. i] sc.set_offsets(x) for j, txt in zip(range(10), txts): xtext, ytext = np.median(x[y == j, :], axis=0) txt.set_x(xtext) txt.set_y(ytext) return mplfig_to_npimage(f) animation = mpy.VideoClip(make_frame_mpl, duration=X_iter.shape[2]/40.) animation.write_gif("https://d3ansictanv2wj.cloudfront.net/images/animation-94a2c1ff.gif", fps=20)

Здесь четко видны различные фазы оптимизации, как и описано в публикации.

Давайте также создадим анимацию для матрицы сходства точек отображения. Мы увидим, что она все больше и больше приближается к матрице сходства точек данных.

n = 1. / (pdist(X_iter[. -1], "sqeuclidean") + 1) Q = n / (2.0 * np.sum(n)) Q = squareform(Q) f = plt.figure(figsize=(6, 6)) ax = plt.subplot(aspect='equal') im = ax.imshow(Q, interpolation='none', cmap=pal) plt.axis('tight') plt.axis('off') def make_frame_mpl(t): i = int(t*40) n = 1. / (pdist(X_iter[. i], "sqeuclidean") + 1) Q = n / (2.0 * np.sum(n)) Q = squareform(Q) im.set_data(Q) return mplfig_to_npimage(f) animation = mpy.VideoClip(make_frame_mpl, duration=X_iter.shape[2]/40.) animation.write_gif("https://d3ansictanv2wj.cloudfront.net/images/animation_matrix-da2d5f1b.gif", fps=20)

Распределение Стьюдента

Теперь объясним, почему для точек отображения было выбрано распределение Стьюдента, в то время как для точек данных применяется нормальное распределение. Известно, что объем N -мерного шара радиуса r пропорционален r N . При больших N , если выбирать случайные точки в шаре, большинство точек будет располагаться около поверхности, и очень небольшое количество – около центра.

Моделирование, реализованное ниже, демонстрирует распределение расстояний для этих точек при различном количестве измерений.

npoints = 1000 plt.figure(figsize=(15, 4)) for i, D in enumerate((2, 5, 10)): # Normally distributed points. u = np.random.randn(npoints, D) # Now on the sphere. u /= norm(u, axis=1)[:, None] # Uniform radius. r = np.random.rand(npoints, 1) # Uniformly within the ball. points = u * r**(1./D) # Plot. ax = plt.subplot(1, 3, i+1) ax.set_xlabel('Ball radius') if i == 0: ax.set_ylabel('Distance from origin') ax.hist(norm(points, axis=1), bins=np.linspace(0., 1., 50)) ax.set_title('D=%d' % D, loc='left') plt.savefig('images/spheres-generated.png', dpi=100, bbox_inches='tight')

При уменьшении размерности набора данных, если использовать гауссово распределение для точек данных и точек отображения, мы получим дисбаланс в распределении расстояний для соседей точек. Это объясняется тем, что распределение расстояний существенно отличается для пространства большой размерности и для пространства малой размерности. Тем не менее, алгоритм пытается воспроизвести одинаковые расстояния в обоих пространствах. Этот дисбаланс создает избыток сил притяжения, что иногда приводит к неудачному отображению. Данный недостаток действительно присутствовал в первоначальном алгоритме SNE, разработанном Хинтоном и Ровейсом (Roweis) и опубликованном в 2002 году.

Алгоритм t-SNE решает эту проблему, используя распределение Стьюдента с одной степенью свободы (или распределение Коши) для точек отображения. В отличие от гауссова распределения, это распределение имеет значительно более «тяжелый» хвост, что позволяет компенсировать дисбаланс. Для данного сходства между двумя точками данных, две соответствующие точки отображения должны находиться намного дальше друг от друга, чтобы их сходство соответствовало сходству точек данных. Это можно увидеть на следующем графике.

z = np.linspace(0., 5., 1000) gauss = np.exp(-z**2) cauchy = 1/(1+z**2) plt.plot(z, gauss, label='Gaussian distribution') plt.plot(z, cauchy, label='Cauchy distribution') plt.legend() plt.savefig('images/distributions-generated.png', dpi=100)

Использование этого распределения обеспечивает более эффективную визуализацию данных, при которой группы точек более отчетливо отделены друг от друга.

Заключение

Алгоритм t-SNE обеспечивает эффективный метод визуализации сложных наборов данных. Он успешно обнаруживает скрытые структуры в данных, демонстрирует группы и компенсирует нелинейные отклонения по измерениям. Данный алгоритм реализован на многих языках программирования, в том числе на Python, и может быть легко применен благодаря библиотеке scikit-learn.

t-SNE в машинном обучении

t-SNE – это очень мощный алгоритм машинного обучения, который можно использовать для визуализации многомерного набора данных также в двумерных фигурах. Аббревиатура означает t-распределенное стохастическое соседнее вложение. Если вы хотите узнать больше о t-SNE и о том, как визуализировать многомерный набор данных с помощью t-SNE, эта статья для вас. В этой статье я познакомлю вас с t-SNE в машинном обучении и его реализацией с использованием Python.

Что такое t-SNE?

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

Существует множество инструментов и библиотек визуализации, которые можно использовать для реализации t-SNE с использованием Python. В следующем разделе я расскажу вам о реализации t-SNE с использованием Python для визуализации многомерного набора данных на двухмерной фигуре с помощью plotly.

t-SNE с использованием Python

Теперь давайте посмотрим, как реализовать алгоритм t-распределенного стохастического соседнего вложения в машинном обучении с использованием языка программирования Python. Здесь я буду использовать классический набор данных радужной оболочки для этой задачи. Итак, вот как вы можете легко реализовать алгоритм t-SNE в машинном обучении с помощью Python:

from sklearn.manifold import TSNE import plotly.express as px df = px.data.iris() features = df.loc[:, :'petal_width'] tsne = TSNE(n_components=2, perplexity=20, random_state=1000) projections = tsne.fit_transform(features) fig = px.scatter( projections, x=0, y=1, color=df.species, labels= ) fig.show()

Реализация t-распределенного стохастического соседнего вложения в наборе данных Iris

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

Резюме

Вот как можно реализовать алгоритм t-SNE в машинном обучении с помощью языка программирования Python. Это расшифровывается как t-Distributed Stochastic Neighbor Embedding (t-распределенное стохастическое соседнее встраивание) и используется для визуализации многомерного набора данных в двухмерной фигуре за очень короткий промежуток времени. Надеюсь, вам понравилась эта статья о t-SNE в машинном обучении и его реализации с использованием Python.