Agrupación en la salida de t-SNE

78

Tengo una aplicación en la que sería útil agrupar un conjunto de datos ruidoso antes de buscar efectos de subgrupo dentro de los grupos. Primero examiné PCA, pero se necesitan ~ 30 componentes para llegar al 90% de la variabilidad, por lo que agrupar en solo un par de PC arrojará mucha información.

Luego probé t-SNE (por primera vez), lo que me da una forma extraña en dos dimensiones que es muy susceptible de agruparse a través de k-means. Además, ejecutar un bosque aleatorio en los datos con la asignación de clúster ya que el resultado muestra que los clústeres tienen una interpretación bastante sensata dado el contexto del problema, en términos de las variables que componen los datos sin procesar.

Pero si voy a informar sobre estos grupos, ¿cómo los describo? Los grupos de K-medias en componentes principales revelan individuos que están cerca uno del otro en términos de las variables derivadas que comprenden el X% de la varianza en el conjunto de datos. ¿Qué afirmación equivalente se puede hacer sobre los clústeres t-SNE?

Quizás algo en el sentido de:

t-SNE revela contigüidad aproximada en una variedad subyacente de alta dimensión, por lo que los grupos en la representación de baja dimensión del espacio de alta dimensión maximizan la "probabilidad" de que los individuos contiguos no estén en el mismo grupo

¿Alguien puede proponer una mejor propaganda que esa?

genérico_usuario
fuente
1
Pensé que el truco es describir los grupos basados ​​en las variables originales, en lugar de las variables en el espacio reducido.
Tim
1
Correcto, pero a falta de una descripción concisa e intuitiva de qué objetivo minimiza el algoritmo de asignación de clúster, puedo estar abierto a los cargos de elegir un algoritmo de agrupamiento que facilite obtener los resultados que quiero.
generic_user
1
Para algunas advertencias y visuales agradables en t-SNE también eche un vistazo a distill.pub/2016/misread-tsne
Tom Wenseleers

Respuestas:

96

El problema con t-SNE es que no conserva distancias ni densidad. Solo hasta cierto punto conserva a los vecinos más cercanos. La diferencia es sutil, pero afecta a cualquier algoritmo basado en la densidad o la distancia.

Para ver este efecto, simplemente genere una distribución gaussiana multivariada. Si visualiza esto, tendrá una pelota que es densa y se vuelve mucho menos densa hacia afuera, con algunos valores atípicos que pueden estar muy lejos.

Ahora ejecute t-SNE en estos datos. Por lo general, obtendrá un círculo de densidad bastante uniforme. Si usa una baja perplejidad, incluso puede tener algunos patrones extraños allí. Pero ya no puedes distinguir los valores atípicos.

Ahora hagamos las cosas más complicadas. Usemos 250 puntos en una distribución normal en (-2,0) y 750 puntos en una distribución normal en (+2,0).

Datos de entrada

Se supone que este es un conjunto de datos fácil, por ejemplo con EM:

Agrupamiento EM

Si ejecutamos t-SNE con una perplejidad predeterminada de 40, obtenemos un patrón de forma extraña:

t-SNE p = 40

No está mal, pero tampoco es tan fácil de agrupar, ¿verdad? Te resultará difícil encontrar un algoritmo de agrupación que funcione aquí exactamente como lo desees. E incluso si le pidiera a los humanos que agrupen estos datos, lo más probable es que encuentren mucho más de 2 grupos aquí.

Si ejecutamos t-SNE con una perplejidad demasiado pequeña como 20, obtenemos más de estos patrones que no existen:

t-SNE p = 20

Esto se agrupará, por ejemplo, con DBSCAN, pero generará cuatro grupos. ¡Así que cuidado, t-SNE puede producir patrones "falsos"!

La perplejidad óptima parece estar en algún lugar alrededor de 80 para este conjunto de datos; pero no creo que este parámetro deba funcionar para cualquier otro conjunto de datos.

t-SNE p = 80

Ahora esto es visualmente agradable, pero no mejor para el análisis . Un anotador humano probablemente podría seleccionar un corte y obtener un resultado decente; ¡k-means sin embargo fallará incluso en este escenario muy fácil ! Ya puede ver que la información de densidad se pierde , todos los datos parecen vivir en un área de casi la misma densidad. Si, en cambio, aumentasemos aún más la perplejidad, la uniformidad aumentaría y la separación se reduciría nuevamente.

En conclusión, use t-SNE para la visualización (¡y pruebe diferentes parámetros para obtener algo visualmente agradable!), Pero no ejecute la agrupación después , en particular no use algoritmos basados ​​en la distancia o la densidad, ya que esta información fue intencionalmente (!) perdido. Los enfoques basados ​​en gráficos de vecindad pueden estar bien, pero no es necesario que primero ejecute t-SNE de antemano, solo use los vecinos de inmediato (porque t-SNE intenta mantener este nn-gráfico en gran parte intacto).

Más ejemplos

Estos ejemplos se prepararon para la presentación del documento (pero aún no se pueden encontrar en el documento, ya que hice este experimento más adelante)

Erich Schubert y Michael Gertz.
Incrustación intrínseca de vecino t-estocástico para visualización y detección de valores atípicos: ¿un remedio contra la maldición de la dimensionalidad?
En: Actas de la 10ª Conferencia Internacional sobre Búsqueda de Similitudes y Aplicaciones (SISAP), Munich, Alemania. 2017

Primero, tenemos estos datos de entrada:

Pescado

Como puede suponer, esto se deriva de una imagen de "colorearme" para niños.

Si ejecutamos esto a través de SNE ( NO t-SNE , sino el predecesor):

Pescado SNE

¡Guau, nuestro pez se ha convertido en un monstruo marino! Debido a que el tamaño del núcleo se elige localmente, perdemos gran parte de la información de densidad.

Pero te sorprenderá mucho la salida de t-SNE:

pez t-SNE

De hecho, he intentado dos implementaciones (las implementaciones ELKI y sklearn), y ambas produjeron ese resultado. Algunos fragmentos desconectados, pero que cada uno parece algo consistente con los datos originales.

Dos puntos importantes para explicar esto:

  1. SGD se basa en un procedimiento de refinamiento iterativo y puede atascarse en los óptimos locales. En particular, esto dificulta que el algoritmo "voltee" una parte de los datos que ha reflejado, ya que esto requeriría mover puntos a través de otros que se supone que están separados. Por lo tanto, si algunas partes del pez se reflejan y otras no, es posible que no pueda solucionarlo.

  2. t-SNE usa la distribución t en el espacio proyectado. A diferencia de la distribución gaussiana utilizada por el SNE regular, esto significa que la mayoría de los puntos se repelerán entre sí , ya que tienen 0 afinidad en el dominio de entrada (Gaussian obtiene cero rápidamente), pero> 0 afinidad en el dominio de salida. A veces (como en MNIST) esto hace una visualización más agradable. En particular, puede ayudar a "dividir" un conjunto de datos un poco más que en el dominio de entrada. Esta repulsión adicional también a menudo hace que los puntos usen el área de manera más uniforme, lo que también puede ser deseable. Pero aquí, en este ejemplo, los efectos repelentes en realidad hacen que se separen los fragmentos de los peces.

Podemos ayudar (en este conjunto de datos de juguetes ) el primer problema usando las coordenadas originales como ubicación inicial, en lugar de coordenadas aleatorias (como se usa generalmente con t-SNE). Esta vez, la imagen es sklearn en lugar de ELKI, porque la versión sklearn ya tenía un parámetro para pasar las coordenadas iniciales:

Pez, t-SNE, con coordenadas originales como inicialización

Como puede ver, incluso con una colocación inicial "perfecta", t-SNE "romperá" el pez en varios lugares que originalmente estaban conectados porque la repulsión de Student-t en el dominio de salida es más fuerte que la afinidad gaussiana en la entrada espacio.

Como puede ver, t-SNE (¡y SNE también!) Son técnicas de visualización interesantes , pero deben manejarse con cuidado. ¡Prefiero no aplicar k-means en el resultado! porque el resultado estará muy distorsionado, y ni las distancias ni la densidad se conservan bien. En cambio, más bien utilícelo para la visualización.

Erich Schubert
fuente
1
Gracias por la respuesta. Puedo imaginar métodos de agrupamiento adaptativo basados ​​en el vecindario, pero ¿hay alguno específico bien desarrollado que pueda recomendar?
generic_user
1
CHAMAELEON es probablemente el más citado, pero parece que solo hay un binario disponible para el paso central. La idea suena bien, pero rápidamente experimentará los mismos efectos que t-SNE hace visibles. Tal como la tendencia a "agruparse" como se ve con p = 20, problemas con los centros y los anti-centros, etc.
Erich Schubert
2
@AlexR: La perplejidad se usa para calcular las similitudes en el espacio de alta dimensión que t-sne intenta hacer coincidir en 2D. Cambiar la perplejidad significa cambiar las similitudes, por lo que no veo cómo la comparación de las divergencias KL resultantes puede ser significativa.
ameba dice Reinstate Monica
1
@AlexR. "Solo la probabilidad condicional del espacio dimensional inferior depende de la perplejidad": esta afirmación es incorrecta. La perplejidad se usa para elegir las sigmas necesarias para la ecuación (1), por lo que influye en cond. problemas en todo el espacio
ameba dice Reinstate Monica
1
Para algunas advertencias y visuales agradables en t-SNE también eche un vistazo a distill.pub/2016/misread-tsne
Tom Wenseleers
34

Me gustaría proporcionar una opinión algo disidente a la respuesta bien argumentada (+1) y altamente votada por @ErichSchubert. Erich no recomienda el agrupamiento en la salida t-SNE, y muestra algunos ejemplos de juguetes en los que puede ser engañoso. Su sugerencia es aplicar la agrupación a los datos originales en su lugar.

use t-SNE para la visualización (¡y pruebe diferentes parámetros para obtener algo visualmente agradable!), pero no ejecute la agrupación después, en particular no use algoritmos basados ​​en distancia o densidad, ya que esta información se perdió intencionalmente (!).

Soy muy consciente de las formas en que la salida de t-SNE puede ser engañosa (consulte https://distill.pub/2016/misread-tsne/ ) y estoy de acuerdo en que puede producir resultados extraños en algunas situaciones.

Pero consideremos algunos datos reales de alta dimensión.

Tome datos MNIST : 70000 imágenes de un solo dígito. Sabemos que hay 10 clases en los datos. Estas clases parecen estar bien separadas para un observador humano. Sin embargo, agrupar datos MNIST en 10 grupos es un problema muy difícil. No conozco ningún algoritmo de agrupación que agrupe correctamente los datos en 10 agrupaciones; Más importante aún, no conozco ninguna heurística de agrupación que indique que hay 10 (ni más ni menos) agrupaciones en los datos. Estoy seguro de que los enfoques más comunes no podrían indicar eso.

Pero hagamos t-SNE en su lugar. (Se pueden encontrar muchas cifras de t-SNE aplicadas a MNIST en línea, pero a menudo son subóptimas. En mi experiencia, es necesario realizar una exageración temprana durante bastante tiempo para obtener buenos resultados. A continuación, estoy usando perplexity=50, max_iter=2000, early_exag_coeff=12, stop_lying_iter=1000). Esto es lo que obtengo, a la izquierda sin etiquetar, y a la derecha coloreado según la verdad básica:

MNIST t-SNE

Yo diría que la representación sin etiquetar de t-SNE sugiere 10 grupos. La aplicación de un buen algoritmo de agrupación basado en la densidad, como HDBSCAN con parámetros cuidadosamente seleccionados, permitirá agrupar estos datos 2D en 10 agrupaciones.

En caso de que alguien dude de que el diagrama de la izquierda de arriba sugiere 10 grupos, esto es lo que obtengo con el truco de "exageración tardía" en el que adicionalmente ejecuto max_iter=200iteraciones exaggeration=4(este truco se sugiere en este gran artículo: https://arxiv.org /abs/1712.09005 ):

MNIST t-SNE con exageración tardía

Ahora debería ser muy obvio que hay 10 grupos.

Animo a todos los que piensan que la agrupación en clúster después de t-SNE sea una mala idea para mostrar un algoritmo de agrupación que logre un resultado comparablemente bueno.

Y ahora aún más datos reales.

En el caso de MNIST, conocemos la verdad fundamental. Considere ahora algunos datos con verdad desconocida. La agrupación y el t-SNE se usan de manera rutinaria para describir la variabilidad celular en los datos de secuencia de ARN de una sola célula. Por ejemplo, Shekhar et al. 2016 trató de identificar grupos entre 27000 células de la retina (hay alrededor de 20k genes en el genoma del ratón, por lo que la dimensionalidad de los datos es, en principio, de aproximadamente 20k; sin embargo, uno generalmente comienza con la reducción de la dimensionalidad con PCA hasta 50 o menos). Realizan t-SNE y agrupan por separado (una tubería de agrupación complicada seguida de algunas fusiones de agrupación, etc.). El resultado final parece agradable:

ingrese la descripción de la imagen aquí

La razón por la que parece tan agradable es que t-SNE produce grupos claramente diferenciados y el algoritmo de agrupamiento produce exactamente los mismos grupos. Agradable.

Sin embargo, si observa los suplementos, verá que los autores probaron muchos enfoques de agrupación diferentes. Muchos de ellos se ven horribles en el diagrama t-SNE porque, por ejemplo, el gran grupo central se divide en muchos subgrupos:

ingrese la descripción de la imagen aquí

Entonces, ¿qué crees: la salida de tu algoritmo de agrupamiento favorito junto con tu heurística favorita para identificar el número de grupos, o lo que ves en el diagrama t-SNE? Para ser sincero, a pesar de todas las deficiencias de t-SNE, tiendo a creer más en t-SNE. O, en cualquier caso, no veo por qué debería creerlo menos .

ameba dice Reinstate Monica
fuente
2
Y para el último ejemplo, ¿no es eso esencialmente lo que @ErichSchubert observó anteriormente: puede obtener resultados visualmente "agradables", que obviamente son incorrectos? Como con perplejidad 20? ¿A tSNE le gusta separar las partes (como en el pescado) que no estaban separadas? Entonces, ¿sabes que los grupos que ves son grupos separados? No me gusta esta "caja negra" allí. Sí, tendemos a creer más en tales complots, pero ¿y si están equivocados?
Anony-Mousse
1
Bueno, tSNE está basado en NN. Se espera un acuerdo con esto. tSNE es una buena opción para visualizar NN. Sin embargo, no conserva bien las similitudes, por lo que debo interpretarlo con cuidado, según tengo entendido. Una brecha en tSNE no implica una gran distancia.
Anony-Mousse
1
+1 Curioso cómo funciona UMAP en comparación con t-SNE.
Paul
1
@Paul: el autor afirma la superioridad de UMAP, en términos de tiempo de cálculo, lo es. En el conjunto de datos MNIST, encuentro que UMAP genera una mejor integración que t-SNE, pero no estoy seguro en otros conjuntos de datos. Hasta donde sé, recientemente hay una versión CUDA de t-SNE, que es mucho más rápido que el t-SNE más rápido anterior, pero no pude instalarlo y probarlo.
SiXUlm
1
@SiXUlm github.com/KlugerLab/FIt-SNE funciona mucho más rápido que Barnes-Hut t-SNE y a menudo es más rápido que UMAP. Además, en muchos casos, se puede lograr una integración muy similar con t-SNE utilizando algunos ajustes adicionales, por ejemplo, en MNIST, el t-SNE con una exageración pequeña produce casi lo mismo que UMAP, vea el cuaderno de Python en el repositorio FIt-SNE.
ameba dice Reinstate Monica el
6

Creo que con gran perplejidad, t-SNE puede reconstruir la topología global, como se indica en https://distill.pub/2016/misread-tsne/ .

De la imagen del pez, tomé muestras de 4000 puntos para t-SNE. Con una gran perplejidad (2000), la imagen del pez fue virtualmente reconstruida.

Aquí está la imagen original. Imagen original

Aquí está la imagen reconstruida por t-SNE con perplejidad = 2000. Imagen reconstruida de t-SNE (perplejidad = 2000)

renxwise
fuente
8
Si elige perplejidades tan altas, ya no es realmente tSNE. Cada punto es aproximadamente vecino todos los días. Ya no es local. Sí, una imagen 2d puede ser reconstruida aproximadamente, porque es 2d. Pero no hacer todo en absoluto es más fácil.
Anony-Mousse
1
Mi opinión es que tSNE con gran perplejidad puede reconstruir la topología global. La imagen 2D es un ejemplo porque su dimensionalidad intrínseca es 2. La aplicación real de tSNE debería seleccionar la perplejidad adecuada de acuerdo con el propósito de capturar las características locales o globales.
renxwise
1
Perplejidades tan altas significan que usa un "núcleo" demasiado grande, y efectivamente solo usa distancias. Luego, probablemente degenera en un MDS aproximado y muy costoso. Solo usa MDS entonces. SNE / tSNE realmente debería usarse con pequeñas perplejidades y vecindarios locales.
Erich Schubert
3
Exactamente. Cuando la perplejidad es lo suficientemente grande, tSNE es, de hecho, aproximado a MDS, lo que ilustra que tSNE también puede capturar la estructura global. Por lo tanto, las afirmaciones de que tSNE solo puede capturar estructuras locales no son correctas. A diferencia de MDS, tSNE puede equilibrar entre estructuras locales y globales mediante la selección de perplejidad. Obviamente, la selección de perplejidad depende del conjunto de datos.
renxwise
¿Hay alguna regla general para elegir la perplejidad plausible?
Catbuilts
5

¡Basado en la evidencia matemática que tenemos, este método técnicamente podría preservar distancias! ¿Por qué ignoran esta característica? t- SNE está convirtiendo las distancias euclidianas de alta dimensión entre muestras en probabilidades condicionales que representan similitudes. He intentado t -SNE con más de 11,000 muestras (en contexto genómico) en paralelo con diferentes algoritmos de agrupación por consenso, incluyendo agrupación espectral, afinidad y, lo que es más importante, con agrupación GMM (que es un algoritmo de agrupación basado en densidad). Como resultado, encontré un muy buen resultado concordante entre dos enfoques ( t-SNE vs. algoritmos de agrupación de consenso). Creo que la integración de t-SNE con algoritmos de agrupación por consenso podría proporcionar la mejor evidencia de las estructuras de datos locales y globales existentes.

Reza Rafiee
fuente
¿Hay parámetros que influirán en la probabilidad de t-SNE de preservar distancias?
Keith Hughitt
Esos no son algoritmos de agrupamiento por consenso. El agrupamiento consensuado es un tipo de aprendizaje conjunto que agrega los resultados de repetir el algoritmo de agrupamiento con alguna variación en los parámetros o datos de entrada, para obtener un resultado de agrupamiento final. Puede usar enfoques de agrupación por consenso con agrupación espectral o GMM o, de hecho, cualquier algoritmo de agrupación, pero mi punto en su terminología está un poco apagado, eso es todo :)
Christopher John
1

Puede probar el algoritmo de agrupación DBSCAN. Además, la perplejidad del tsne debería ser aproximadamente del mismo tamaño que el grupo más pequeño esperado.

James LI
fuente
0

Personalmente, he experimentado esto una vez, pero no con t-SNE o PCA. Mis datos originales están en un espacio de 15 dimensiones. Usando UMAP para reducirlo a incrustaciones 2D y 3D, obtuve 2 clústeres perfectamente y visualmente separables en trazados 2D y 3D. Demasiado bueno para ser verdad. Pero cuando "miré" los datos originales del diagrama de persistencia, me di cuenta de que hay grupos mucho más "significativos", no solo 2.

La agrupación en el resultado de la técnica de reducción de dimensiones debe hacerse con mucha precaución, de lo contrario, cualquier interpretación puede ser muy engañosa o incorrecta porque la reducción de la dimensión seguramente dará como resultado la pérdida de características (quizás características ruidosas o verdaderas, pero a priori, no lo hacemos ' No sé cuál). En mi opinión, puede confiar / interpretar los grupos, si:

  • Los grupos en los datos proyectados corresponden / confirman a alguna clasificación definida a priori (piense en el conjunto de datos MNIST, donde los grupos de datos proyectados coinciden muy bien con la clasificación de dígitos), y / o,

  • Puede confirmar la presencia de estos clústeres en los datos originales utilizando otros métodos, como los diagramas de persistencia. Solo se puede contar el número de componentes conectados en un período de tiempo bastante razonable.

SiXUlm
fuente
¿Por qué (confiaste) en "el diagrama de persistencia" más que en UMAP? No creo que mirar el diagrama de persistencia pueda describirse como "mirar los datos originales" ...
ameba dice Reinstate Monica el
Estás en lo correcto. El diagrama de persistencia solo muestra algunas características de los datos originales, con mayor frecuencia, componentes conectados, agujeros unidimensionales y agujeros mucho más raros, de 2 o más dimensiones debido a la costosa computación. Entonces debería haber dicho que solo puedo "mirar" parcialmente los datos originales mirando el diagrama de persistencia correspondiente. Pero puedo confiar en lo que observo en este diagrama de persistencia porque está construido directamente a partir de los datos originales.
SiXUlm
Por el contrario, al usar UMAP o cualquier otra técnica de reducción de dimensiones, solo trabajamos con una versión proyectada / modificada de los datos originales. Como señaló la respuesta más votada, la agrupación puede ser diferente para las diferentes opciones de parámetros.
SiXUlm