Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

t-SNE

¿Qué es t-SNE?

t-SNE () es un algoritmo para la reducción de la dimensionalidad que se adapta bien a la visualización de datos de alta dimensión.tsne El nombre significa-distribuido estocástico vecino incrustación.t La idea es incrustar puntos de alta cota en dimensiones bajas de una manera que respete las similitudes entre los puntos. Los puntos cercanos en el espacio de alta dimensionalidad corresponden a los puntos bajos-dimensionales incrustados cercanos, y los puntos distantes en el espacio de alta dimensionalidad corresponden a puntos de baja cota incrustados distantes. (Generalmente, es imposible igualar distancias exactamente entre espacios de alta dimensión y baja dimensión.)

La función crea un conjunto de puntos de baja cota a partir de datos de alta dimensionalidad.tsne Normalmente, se visualizan los puntos de cota baja para ver los clústeres naturales en los datos de alta cota originales.

El algoritmo toma los siguientes pasos generales para incrustar los datos en dimensiones reducidas.

  1. Calcule las distancias en pares entre los puntos de alta cota.

  2. Cree una desviación estándar Σi para cada punto de alta cota de modo que el de cada punto se encuentra en un nivel predeterminado.iPerplejidad Para la definición de perplejidad, ver.Distancias de cómputo, varianzas Gaussianas y similitudes

  3. Calcule el.matriz de similitud Esta es la distribución de probabilidad conjunta de X, definida por.Ecuación 1

  4. Cree un conjunto inicial de puntos de baja cota.

  5. Actualice de forma iterativa los puntos de cota baja para minimizar la divergencia Kullback-Leibler entre una distribución gaussiana en el espacio de alta dimensión y una distribución en el espacio de dimensiones reducidas.t Este procedimiento de optimización es la parte que consume más tiempo del algoritmo.

Véase van der Maaten y Hinton.[1]

Algoritmo t-SNE

El algoritmo básico de t-SNE realiza los siguientes pasos.

Preparar datos

primero quita cada fila de los datos de entrada X que contiene los valores.tsneNaN A continuación, si el par nombre-valor es, centros X restando la media de cada columna y escalas X dividiendo sus columnas por sus desviaciones estándar.Standardizetruetsne

Los autores originales van der Maaten y Hinton recomiendan la reducción de los datos originales X a una versión de menor dimensión utilizando.[1]Análisis de componentes principales (PCA) Puede establecer el par nombre-valor en el número de dimensiones que le guste, quizás 50.tsneNumPCAComponents Para ejercer un mayor control sobre este paso, preprocese los datos mediante la función.pca

Distancias de cómputo, varianzas Gaussianas y similitudes

Después del preprocesamiento, calcula la distanciatsne d(xi,xj) entre cada par de puntos Xi Y Xj en X. Puede elegir varias métricas de distancia mediante el par nombre-valor.Distance De forma predeterminada, utiliza la métrica euclidiana estándar. utiliza el cuadrado de la métrica de distancia en sus cálculos subsiguientes.tsnetsne

A continuación, para cada fila de X, calcula una desviación estándaritsne Σi para que el de la fila sea igual al par nombre-valor.PerplejidadiPerplexity La perplejidad se define en términos de una distribución gaussiana modelo de la siguiente manera. Como van der Maaten y Hinton describen, "la similitud de Datapoint[1] Xj a Datapoint Xi es la probabilidad condicional, pj|iese Xi elegiría Xj como su vecino si los vecinos fueron recogidos en proporción a su densidad de probabilidad bajo un gaussiano centrado en Xi. Para los puntos de datos cercanos, pj|i es relativamente alta, mientras que para los puntos de datos ampliamente separados, pj|i será casi infinitesimal (para valores razonables de la varianza de la gaussiana, Σi)."

Defina la probabilidad condicional de dado comoji

pj|i=exp(d(xi,xj)2/(2σi2))kiexp(d(xi,xk)2/(2σi2))pi|i=0.

A continuación, defina la probabilidad articular Pij simetrizando las probabilidades condicionales:

pij=pj|i+pi|j2N,(1)

donde está el número de filas de X.N

Las distribuciones todavía no tienen sus desviaciones estándar Σi define en términos del par nombre-valor.Perplexity Dejar Pi representa la distribución de probabilidad condicional sobre todos los demás puntos de datos dados Datapoint Xi. La perplejidad de la distribución es

perplexity(Pi)=2H(Pi),

dondeHPi) es la entropía de Shannon de Pi:

H(Pi)=jpj|ilog2(pj|i).

La perplejidad mide el número efectivo de vecinos de punto. realiza una búsqueda binaria sobre elitsne Σi para lograr una perplejidad fija para cada punto.i

Inicializar la incrustación y divergencia

Para incrustar los puntos en X en un espacio de dimensiones reducidas, realiza una optimización. intenta minimizar la divergencia Kullback-Leibler entre la distribución gaussiana del modelo de los puntos en X y una distribución Student de los puntos Y en el espacio de dimensiones reducidas.tsnetsnet

El procedimiento de minimización comienza con un conjunto inicial de puntos Y. crear los puntos de forma predeterminada como puntos aleatorios de Gauss distribuidos.tsne También puede crear estos puntos usted mismo e incluirlos en el par nombre-valor para. a continuación, calcula las similitudes entre cada par de puntos en Y.'InitialY'tsnetsne

El modelo de probabilidad Qij de la distribución de las distancias entre los puntos yi Y yj Es

qij=(1+yiyj2)1klk(1+ykyl2)1qii=0.

Utilizando esta definición y el modelo de distancias en X dada por, la divergencia Kullback-Liebler entre la distribución articular y esEcuación 1PQ

KL(P||Q)=jijpijlogpijqij.

Para las consecuencias de esta definición, véase.Útil distorsión no lineal

Descenso degradado de la divergencia Kullback-Leibler

Para minimizar la divergencia Kullback-Leibler, el algoritmo utiliza un procedimiento de descenso de gradiente modificado.'exact' El gradiente con respecto a los puntos en Y de la divergencia es

KL(P||Q)yi=4jiZ(pijqij)qij(yiyj),

donde el término de normalización

Z=klk(1+ykyl2)1.

El algoritmo de descenso de degradado modificado utiliza algunos parámetros de ajuste para intentar alcanzar un buen mínimo local.

  • — Durante los primeros 99 pasos de descenso de gradiente, multiplica las probabilidades'Exaggeration'tsne Pij por el valor de exageración.Ecuación 1 Este paso tiende a crear más espacio entre los clústeres de la salida Y.

  • : utiliza el aprendizaje adaptativo para mejorar la convergencia de las iteraciones de descenso de degradado.'LearnRate'tsne El algoritmo de descenso tiene pasos iterativos que son una combinación lineal del paso anterior en el descenso y el degradado actual. es un multiplicador del degradado actual para la combinación lineal.'LearnRate' Para obtener más información, consulte Jacobs.[3]

La variante Barnes-Hut de t-SNE

Para acelerar el algoritmo t-SNE y reducir su uso de memoria, ofrece un esquema de optimización aproximado.tsne El algoritmo de Barnes-Hut agrupa los puntos cercanos para reducir la complejidad y el uso de memoria del paso de optimización de t-SNE. El algoritmo de Barnes-Hut es un optimizador aproximado, no un optimizador exacto. Hay un parámetro de ajuste no negativo que produce un equilibrio entre la velocidad y la precisión.Theta Los valores más grandes de dar resultados de optimización más rápidos pero menos precisos.'Theta' El algoritmo es relativamente insensible a los valores del rango (0.2, 0.8).'Theta'

El algoritmo Barnes-Hut agrupa los puntos cercanos en el espacio de dimensiones reducidas y realiza un descenso de gradiente aproximado basado en estos grupos. La idea, utilizada originalmente en Astrofísica, es que el gradiente es similar para los puntos cercanos, por lo que los cálculos se pueden simplificar.

Véase van der Maaten.[2]

Características de t-SNE

No se puede usar incrustar para clasificar nuevos datos

Debido a que t-SNE a menudo separa bien los clústeres de datos, puede parecer que t-SNE puede clasificar nuevos puntos de datos. Sin embargo, t-SNE no puede clasificar nuevos puntos. La incrustación de t-SNE es un mapa no lineal dependiente de los datos. Para incrustar un nuevo punto en el espacio de dimensiones reducidas, no puede utilizar la incrustación anterior como un mapa. En su lugar, vuelva a ejecutar el algoritmo completo.

Rendimiento depende de los tamaños de datos y el algoritmo

t-SNE puede tomar una buena cantidad de tiempo para procesar los datos. Si tiene puntos de datos en dimensiones que desea asignar a cotas,NDY

  • Exact t-SNE toma de orden D*N2 Operaciones.

  • Barnes-Hut t-SNE toma de orden D*Nlog(N)*exp(dimension(Y)) Operaciones.

Por lo tanto, para conjuntos de datos grandes, donde es mayor que 1000 o así, y donde la dimensión de incrustación es 2 o 3, el algoritmo de Barnes-Hut puede ser más rápido que el algoritmo exacto.NY

Útil distorsión no lineal

T-SNE mapea distancias elevadas a análogos distorsionados de baja dimensión. Debido a la cola más gorda de la distribución de Student en el espacio de baja dimensión, a menudo mueve los puntos cercanos más cerca, y mueve los puntos lejanos más lejos que en el espacio de alta dimensión, como se ilustra en la siguiente figura.ttsne La figura muestra las distribuciones gaussiana y Student en los puntos donde las densidades están en 0,25 y 0,025.t La densidad gaussiana se relaciona con distancias elevadas, y la densidad se relaciona con distancias de dimensiones bajas.t La densidad corresponde a los puntos de cierre que están más cerca, y los puntos lejanos están más lejos, en comparación con la densidad Gaussiana.t

t = linspace(0,5); y1 = normpdf(t,0,1); y2 = tpdf(t,1); plot(t,y1,'k',t,y2,'r') hold on x1 = fzero(@(x)normpdf(x,0,1)-0.25,[0,2]); x2 = fzero(@(x)tpdf(x,1)-0.25,[0,2]); z1 = fzero(@(x)normpdf(x,0,1)-0.025,[0,5]); z2 = fzero(@(x)tpdf(x,1)-0.025,[0,5]); plot([0,x1],[0.25,0.25],'k-.') plot([0,z2],[0.025,0.025],'k-.') plot([x1,x1],[0,0.25],'g-',[x2,x2],[0,0.25],'g-') plot([z1,z1],[0,0.025],'g-',[z2,z2],[0,0.025],'g-') text(1.1,.25,'Close points are closer in low-D') text(2.4,.05,'Far points are farther in low-D') legend('Gaussian(0,1)','Student t (df = 1)') xlabel('x') ylabel('Density') title('Density of Gaussian(0,1) and Student t (df = 1)') hold off

Esta distorsión es útil cuando se aplica. No se aplica en casos como cuando la varianza gaussiana es alta, lo que disminuye el pico gaussiano y apura la distribución. En tal caso, puede mover los puntos de cierre más alejados que en el espacio original.tsne Para lograr una distorsión útil,

  • Establezca el par nombre-valor en.'Verbose'2

  • Ajuste el par nombre-valor para que el rango de desviaciones notificado no esté demasiado lejos y la varianza media esté cerca.'Perplexity'11

Si usted puede alcanzar este rango de varianzas, después el diagrama se aplica, y la distorsión es útil.tsne

Para conocer las formas efectivas de sintonizar, véase Wattenberg, Viégas y Johnson.tsne[4]

Referencias

[1] van der Maaten, Laurens, and Geoffrey Hinton. Visualizing Data using t-SNE. J. Machine Learning Research 9, 2008, pp. 2579–2605.

[2] van der Maaten, Laurens. Barnes-Hut-SNE. arXiv:1301.3342 [cs.LG], 2013.

[3] Jacobs, Robert A. Increased rates of convergence through learning rate adaptation. Neural Networks 1.4, 1988, pp. 295–307.

[4] Wattenberg, Martin, Fernanda Viégas, and Ian Johnson. How to Use t-SNE Effectively. Distill, 2016. Available at How to Use t-SNE Effectively.

Ejemplos relacionados

Más acerca de