Agrupación en la salida de t-SNE

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?

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).

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

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

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:

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.

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:

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):

¡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:

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:

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.

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:

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 ):

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:

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:

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 .

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.

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

¡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.

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.

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.