t-SNE с нуля (ft. NumPy)
Эта статья предназначена для читателей, которые заинтересованы в понимании t-SNE посредством перевода математики из оригинальной статьи — Лоренса ван дер Маатена и Джеффри Хинтона — в реализацию кода на python.[1] Я нахожу, что такого рода упражнения достаточно проливают свет на внутреннюю работу статистических алгоритмов / моделей и действительно проверяют ваше базовое понимание относительно этих алгоритмов / моделей. Как минимум, успешная реализация всегда приносит большое удовлетворение!
Эта статья будет доступна лицам с любым уровнем взаимодействия с t-SNE. Однако, стоить заметить, что эта статья не будет каким-либо полноценным руководством:
- Строго концептуальное введение и исследование t-SNE, поскольку существует множество других замечательных ресурсов, которые делают это; тем не менее, я сделаю всё возможное, чтобы связать математические уравнения с их интуитивными / концептуальными аналогами на каждом этапе реализации.
- Всестороннее обсуждение применений и плюсов /минусов t-SNE, а также прямые сравнения t-SNE с другими методами уменьшения размерности. Я, однако, кратко коснусь этих тем на протяжении всей этой статьи, но ни в коем случае не буду подробно их освещать.
Без лишних слов давайте начнём с краткого введения в t-SNE.
Краткое введение в t-SNE
Стохастическое вложение соседей с t-распределением (t-SNE) — это инструмент уменьшения размерности, который в основном используется в наборах данных с пространством пространственных объектов большой размерности и позволяет визуализировать данные или спроецировать их в пространство меньшей размерности (обычно 2-D). Это особенно полезно для визуализации нелинейно разделяемых данных, в которых линейные методы, такие как анализ главных компонент (PCA), потерпели бы неудачу. Обобщение линейных структур уменьшения размерности (таких как PCA) на нелинейные подходы (такие как t-SNE) также известно как многообразное обучение. Эти методы могут быть чрезвычайно полезны для визуализации и понимания базовой структуры многомерного нелинейного набора данных, а также могут быть полезны для распутывания и группировки воедино наблюдений, которые похожи в многомерном пространстве. Для получения дополнительной информации о t-SNE и других разнообразных методах обучения документация scikit-learn является отличным ресурсом. Кроме того, чтобы прочитать о некоторых интересных областях применения t-SNE, на странице Википедии освещаются некоторые из этих областей со ссылками на работу.
Давайте начнём с разбиения названия стохастического вложение соседей с t-распределением на его компоненты. t-SNE — это расширение стохастического вложения соседей (SNE), представленное 6 годами ранее в этой статье Джеффри Хинтоном и Сэмом Роуэйсом. Итак, давайте начнём с этого. Стохастическая часть названия происходит от того факта, что целевая функция не является выпуклой и, следовательно, при разных инициализациях могут получаться разные результаты. Вложение соседей подчёркивает природу алгоритма — оптимальное отображение точек в исходном многомерном пространстве в соответствующее низкоразмерное пространство при наилучшем сохранении структуры точек ”окрестности». SNE состоит из следующих (упрощённых) шагов:
- Получение матрицы подобия между точками в исходном пространстве: Вычислите условные вероятности для каждой точки данных j относительно каждой точки данных i. Эти условные вероятности вычисляются в исходном многомерном пространстве с использованием гауссова уравнения с центром в точке i и принимают следующую интерпретацию: вероятность того, что i выберет j в качестве своего соседа в исходном пространстве. Это создаёт матрицу, которая представляет сходства между точками.
- Инициализация: Выберите случайные начальные точки в пространстве нижнего измерения (скажем, 2-D) для каждой точки данных в исходном пространстве и вычислите новые условные вероятности аналогично описанным выше в этом новом пространстве.
- Отображение: Итеративно улучшайте точки в пространстве меньшей размерности до тех пор, пока расхождения Кульбака-Лейблера между всеми условными вероятностями не будут сведены к минимуму. По сути, мы сводим к минимуму различия в вероятностях между матрицами подобия двух пространств, чтобы обеспечить наилучшее сохранение сходства при отображении исходного набора данных в низкоразмерный датасетах.
t-SNE улучшает SNE двумя основными способами:
- Это сводит к минимуму расхождения Кульбака-Лейблера между совместными вероятностями, а не условными. Авторы называют это “симметричным SNE”, поскольку их подход гарантирует, что совместные вероятности p_ij = p_ji. Это приводит к гораздо лучшему функционированию функции затрат, которую легче оптимизировать.
- Он вычисляет сходства между точками, используя распределение Стьюдента-t с одной степенью свободы (также распределение Коши), а не гауссово в низкоразмерном пространстве (шаг 2 выше). Здесь мы можем видеть, откуда берётся буква “t” в t-SNE. Это улучшение помогает устранить “проблему скученности”, выделенную авторами, и ещё больше улучшить задачу оптимизации. Эту “проблему скученности” можно представить следующим образом: представьте, что у нас есть 10-мерное пространство, объема пространства, доступного в 2-мерном пространстве, будет недостаточно для точного захвата этих умеренно непохожих точек по сравнению с объемом пространства для соседних точек относительно объема пространства, доступного в 10-мерном пространстве. Проще говоря, просто представьте, что вы берёте трёхмерное пространство и проецируете его в 2-D. В трёхмерном пространстве будет гораздо больше общего пространства для моделирования сходств относительно 2-D проекции. Распределение Стьюдента-t помогает облегчить эту проблему, поскольку имеет более тяжелые хвосты, чем нормальное распределение.
Я надеюсь, что когда мы реализуем это в коде, все части встанут на свои места. Основной вывод таков: t-SNE моделирует сходства между точками данных в многомерном пространстве, используя совместные вероятности точек данных, выбирающих других в качестве своих соседей, а затем пытается найти наилучшее отображение этих точек вниз в низкоразмерное пространство, наилучшим образом сохраняя исходные многомерные сходства.
Внедрение с Scratch
Давайте теперь перейдем к пониманию t-SNE посредством реализации оригинальной версии алгоритма, представленной в статье Лоуренса ван дер Маатена и Джеффри Хинтона. Сначала мы начнём с пошаговой реализации приведённого ниже алгоритма, который будет охватывать 95% основного алгоритма. Авторы отмечают два дополнительных улучшения: 1) Раннее преувеличение и 2) Адаптивная скорость обучения. Мы обсудим только добавление ранних преувеличений, поскольку это наиболее способствует интерпретации внутренней работы реальных алгоритмов, поскольку адаптивная скорость обучения направлена на повышение скорости сходимости.
Алгоритм 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 — отличный инструмент для снижения размерности в 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 имеет определенные ограничения, которые необходимо учитывать при его использовании:
- t-SNE предполагает непараметрический подход к уменьшению размерности, то есть алгоритм не создает явной функции отображения для использования относительно новых точек данных.
- Возможно, вам придется поэкспериментировать с различными значениями перплексии, чтобы найти то, которое лучше всего подходит для ваших данных.
- Вы можете получать разные результаты после каждого запуска из-за случайной инициализации и стохастического характера. Если вам нужны воспроизводимые результаты, обязательно укажите начальное значение (random_state).
- Объяснение понятий вероятности: оценка максимального правдоподобия
- Обработка естественного языка для анализа отзывов онлайн-покупателей
- Моделирование логистического роста
Tsne python что это
Шаг 96.
Введение в машинное обучение с использованием Python. Методы машинного обучения без учителя . . Множественное обучение с помошью алгоритма t-SNE
На этом шаге мы рассмотрим назначение и использование этого алгоритма .
Хотя PCA часто выступает в качестве приоритетного метода, преобразующего данные таким образом, что можно визуализировать их с помощью диаграммы рассеяния, сам характер метода (вращение данных, а затем удаление направлений, объясняющих незначительную дисперсию данных) ограничивает его полезность, как мы уже убедились на примере диаграммы рассеяния для набора данных Labeled Faces in the Wild . Существует класс алгоритмов визуализации, называемых алгоритмами множественного обучения (manifold learning algorithms) , которые используют гораздо более сложные графические представления данных и позволяют получить визуализации лучшего качества. Особенно полезным является алгоритм t-SNE .
Алгоритмы множественного обучения в основном направлены на визуализацию и поэтому редко используются для получения более двух новых характеристик. Некоторые из них, в том числе t-SNE , создают новое представление обучающих данных, но при этом не осуществляют преобразования новых данных. Это означает, что данные алгоритмы нельзя применить к тестовому набору, они могут преобразовать лишь те данные, на которых они были обучены. Множественное обучение может использоваться для разведочного анализа данных, но редко используется в тех случаях, когда конечной целью является применение модели машинного обучения с учителем. Идея, лежащая в основе алгоритма t-SNE , заключается в том, чтобы найти двумерное представление данных, сохраняющее расстояния между точками наилучшим образом. t-SNE начинает свою работу со случайного двумерного представления каждой точки данных, а затем пытается сблизить точки, которые в пространстве исходных признаков находятся близко друг к другу, и отдаляет друг от друга точки, которые находятся далеко друг от друга. При этом t-SNE уделяет большее внимание сохранению расстояний между точками, близко расположенными друг к другу. Иными словами, он пытается сохранить информацию, указывающую на то, какие точки являются соседями друг другу.
Мы применим алгоритм множественного обучения t-SNE к набору данных рукописных цифр, который включен в scikit-learn .
Не следует путать с гораздо большим набором данных MNIST .
Каждая точка данных в этом наборе является изображением цифры в градациях серого. Рисунок 1 показывает примеры изображений для каждого класса:
[In 42]: from sklearn.datasets import load_digits digits = load_digits() fig, axes = plt.subplots(2, 5, figsize=(10, 5), subplot_kw='xticks':(), 'yticks': ()>) for ax, img in zip(axes.ravel(), digits.images): ax.imshow(img)
Рис.1. Примеры изображений из набора данных digits
Давайте используем PCA для визуализации данных, сведя их к двум измерениям. Мы построим график первых двух главных компонент и отметим цветом класс каждой точки (рисунок 2):
[In 43]: # строим модель PCA pca = PCA(n_components=2) pca.fit(digits.data) # преобразуем данные рукописных цифр к первым двум компонентам digits_pca = pca.transform(digits.data) colors = ["#476A2A", "#7851B8", "#BD3430", "#4A2D4E", "#875525", "#A83683", "#4E655E", "#853541", "#3A3120", "#535D8E"] plt.figure(figsize=(10, 10)) plt.xlim(digits_pca[:, 0].min(), digits_pca[:, 0].max()) plt.ylim(digits_pca[:, 1].min(), digits_pca[:, 1].max()) for i in range(len(digits.data)): # строим график, где цифры представлены символами вместо точек plt.text(digits_pca[i, 0], digits_pca[i, 1], str(digits.target[i]), color = colors[digits.target[i]], fontdict='weight': 'bold', 'size': 9>) plt.xlabel("Первая главная компонента") plt.ylabel("Вторая главная компонента")
Рис.2. Диаграмма рассеяния для набора данных digits , использующая первые две главные компоненты
Здесь мы вывели фактические классы цифр в виде символов, чтобы визуально показать расположение каждого класса. Цифры 0, 6 и 4 относительно хорошо разделены с помощью первых двух главных компонент, хотя по-прежнему перекрывают друг друга. Большинство остальных цифр значительно перекрывают друг друга.
Давайте применим t-SNE к этому же набору данных и сравним результаты. Поскольку t-SNE не поддерживает преобразование новых данных, в классе TSNE нет метода transform() . Вместо этого мы можем вызвать метод fit_transform() , который построит модель и немедленно вернет преобразованные данные (см. рисунок 3):
[In 44]: from sklearn.manifold import TSNE tsne = TSNE(random_state=42) # используем метод fit_transform вместо fit, т.к. класс TSNE не использует метод transform digits_tsne = tsne.fit_transform(digits.data)
[In 45]: plt.figure(figsize=(10, 10)) plt.xlim(digits_tsne[:, 0].min(), digits_tsne[:, 0].max() + 1) plt.ylim(digits_tsne[:, 1].min(), digits_tsne[:, 1].max() + 1) for i in range(len(digits.data)): # строим график, где цифры представлены символами вместо точек plt.text(digits_tsne[i, 0], digits_tsne[i, 1], str(digits.target[i]), color = colors[digits.target[i]], fontdict='weight': 'bold', 'size': 9>) plt.xlabel("t-SNE признак 0") plt.xlabel("t-SNE признак 1")
Рис.3. Диаграмма рассеяния для набора данных digits , которая использует первые две главные компоненты, найденные с помощью t-SNE
Результат, полученный с помощью t-SNE , весьма примечателен. Все классы довольно четко разделены. Единицы и девятки в некоторой степени распались, однако большинство классов образуют отдельные сплоченные группы. Имейте в виду, что этот метод не использует информацию о метках классов: он является полностью неконтролируемым. Тем не менее он может наити двумерное представление данных, которое четко разграничивает классы, используя лишь информацию о расстояниях между точками данных в исходном пространстве.
Алгоритм t-SNE имеет некоторые настраиваемые параметры, хотя, как правило, дает хорошее качество, когда используются настроики по умолчанию. Вы можете поэкспериментировать с параметрами perplexity и early_exaggeration , но эффекты от их применения обычно незначительны.
Архив блокнота со всеми вычислениями, выполненными на 82-96 шагах, можно взять здесь.
Со следующего шага мы начнем рассматривать кластеризацию .