Clustering sur la sortie de t-SNE

78

J'ai une application où il serait pratique de regrouper un ensemble de données bruyant avant de rechercher des effets de sous-groupe dans les clusters. J'ai d'abord examiné PCA, mais il faut environ 30 composants pour obtenir 90% de la variabilité. Par conséquent, le regroupement sur seulement quelques PC va jeter beaucoup d'informations.

J'ai ensuite essayé t-SNE (pour la première fois), ce qui me donne une forme étrange en deux dimensions qui se prête très bien à la mise en cluster via k-means. De plus, l'exécution d'une forêt aléatoire sur les données avec l'affectation de grappe en tant que résultat montre que les grappes ont une interprétation assez judicieuse compte tenu du contexte du problème, en termes de variables qui constituent les données brutes.

Mais si je vais faire un rapport sur ces groupes, comment puis-je les décrire? Les grappes de K-moyennes sur les composantes principales révèlent des individus proches les uns des autres en termes de variables dérivées constituant X% de la variance dans l'ensemble de données. Quelle déclaration équivalente peut-on faire au sujet des grappes t-SNE?

Peut-être quelque chose à l'effet de:

Le t-SNE révèle une contiguïté approximative dans une variété sous-dimensionnelle sous-jacente, de sorte que les grappes sur la représentation en basse dimension de l'espace en haute dimension maximisent la "probabilité" que des individus contigus ne soient pas dans le même groupe

Quelqu'un peut-il proposer un meilleur texte de présentation?

utilisateur_générique
la source
1
J'aurais pensé que l'astuce consiste à décrire les grappes en fonction des variables d'origine plutôt que des variables de l'espace réduit.
Tim
1
Bien, mais sans une description concise et intuitive de l’objectif que l’algorithme d’affectation de grappes minimise, je suis peut-être ouvert aux accusations de choisir un algorithme de classification qui facilite l’obtention des résultats souhaités.
generic_user
2
Pour des mises en garde et de jolis graphismes sur t-SNE, consultez également distill.pub/2016/misread-tsne
Tom Wenseleers

Réponses:

97

Le problème avec le t-SNE est qu’il ne conserve ni les distances ni la densité. Il ne conserve que dans une certaine mesure les voisins les plus proches. La différence est subtile, mais affecte tout algorithme basé sur la densité ou la distance.

Pour voir cet effet, générez simplement une distribution gaussienne multivariée. Si vous visualisez cela, vous obtiendrez une balle dense et beaucoup moins dense vers l'extérieur, avec des valeurs aberrantes pouvant être très éloignées.

Maintenant, lancez t-SNE sur ces données. Vous obtiendrez généralement un cercle de densité plutôt uniforme. Si vous utilisez une perplexité faible, il peut même y avoir quelques motifs étranges. Mais vous ne pouvez plus vraiment distinguer les autres.

Maintenant rendons les choses plus compliquées. Utilisons 250 points dans une distribution normale à (-2,0) et 750 points dans une distribution normale à (+2,0).

Des données d'entrée

Ceci est supposé être un ensemble de données facile, par exemple avec EM:

Clustering EM

Si nous utilisons t-SNE avec une perplexité par défaut de 40, nous obtenons un motif de forme étrange:

t-SNE p = 40

Pas mal, mais pas aussi facile à regrouper, n'est-ce pas? Vous aurez du mal à trouver un algorithme de clustering qui fonctionne ici exactement comme vous le souhaitez. Et même si vous demandiez aux humains de regrouper ces données, ils trouveraient très probablement plus de 2 groupes ici.

Si nous exécutons t-SNE avec une perplexité trop petite telle que 20, nous aurons plus de modèles qui n'existent pas:

t-SNE p = 20

Cela regroupera par exemple avec DBSCAN, mais cela produira quatre grappes. Alors, méfiez-vous, t-SNE peut produire de "faux" modèles!

La perplexité optimale semble se situer autour de 80 pour cet ensemble de données; mais je ne pense pas que ce paramètre devrait fonctionner pour tous les autres ensembles de données.

t-SNE p = 80

Ceci est visuellement agréable, mais pas meilleur pour l'analyse . Un annotateur humain pourrait probablement sélectionner une coupe et obtenir un résultat décent; k-means cependant échouera même dans ce scénario très très facile ! Vous pouvez déjà voir que les informations de densité sont perdues , toutes les données semblent vivre dans une zone de densité presque identique. Si au contraire nous augmentions davantage la perplexité, l'uniformité augmenterait et la séparation diminuerait à nouveau.

Dans les conclusions, utilisez t-SNE pour la visualisation (et essayez différents paramètres pour obtenir quelque chose de visuellement agréable!), Mais évitez plutôt de faire du clustering après coup , en particulier n'utilisez pas d'algorithmes basés sur la distance ou la densité, car ces informations étaient intentionnellement (!) perdu. Les approches basées sur les graphes de voisinage peuvent convenir, mais dans ce cas, vous n'avez pas besoin de lancer d'abord t-SNE, vous devez simplement utiliser les voisins immédiatement (car t-SNE essaie de garder ce nn-graph en grande partie intact).

Plus d'exemples

Ces exemples ont été préparés pour la présentation du papier (mais ne peuvent pas être trouvés dans le papier pour le moment, comme j'ai fait cette expérience plus tard)

Erich Schubert et Michael Gertz.
Inclusion intrinsèque de voisins t-stochastiques pour la visualisation et la détection de valeurs aberrantes: un remède contre la malédiction de la dimensionnalité?
In: Actes de la 10e Conférence internationale sur la recherche de similarité et les applications (SISAP), Munich, Allemagne. 2017

Premièrement, nous avons ces données d'entrée:

Poisson

Comme vous pouvez le deviner, ceci est dérivé d'une image "colore-moi" pour les enfants.

Si nous passons cela par SNE ( PAS t-SNE , mais le prédécesseur):

Poisson SNE

Wow, notre poisson est devenu tout à fait un monstre marin! Comme la taille du noyau est choisie localement, nous perdons une grande partie des informations de densité.

Mais vous serez vraiment surpris par la sortie de t-SNE:

poisson t-SNE

En fait, j'ai essayé deux implémentations (ELKI et implémentations Sklearn) et les deux ont produit un tel résultat. Certains fragments déconnectés, mais qui ont chacun une apparence quelque peu cohérente avec les données d'origine.

Deux points importants pour expliquer cela:

  1. SGD s'appuie sur une procédure de raffinement itérative et risque de rester bloqué dans les optima locaux. En particulier, il est difficile pour l’algorithme de "retourner" une partie des données qu’il a reflétée, car cela nécessiterait de déplacer des points à travers d’autres qui sont supposés être séparés. Donc, si certaines parties du poisson sont reflétées et que d'autres ne le sont pas, il sera peut-être impossible de résoudre ce problème.

  2. t-SNE utilise la distribution t dans l'espace projeté. Contrairement à la distribution gaussienne utilisée par le SNE classique, cela signifie que la plupart des points se repousseront , car ils ont une affinité 0 dans le domaine en entrée (le gaussien obtient rapidement zéro), mais une affinité> 0 dans le domaine en sortie. Parfois (comme dans MNIST), cela rend la visualisation plus agréable. En particulier, cela peut aider à "séparer" un ensemble de données un peu plus que dans le domaine d'entrée. Cette répulsion supplémentaire amène souvent les points à utiliser la zone plus uniformément, ce qui peut également être souhaitable. Mais ici, dans cet exemple, les effets répulsifs provoquent la séparation de fragments de poisson.

Nous pouvons aider (sur cet ensemble de données de jouets ) le premier numéro en utilisant les coordonnées d'origine comme placement initial, plutôt que des coordonnées aléatoires (comme utilisé habituellement avec t-SNE). Cette fois, l'image est sklearn au lieu de ELKI, car la version de sklearn avait déjà un paramètre pour transmettre les coordonnées initiales:

Poisson, t-SNE, avec les coordonnées d'origine comme initialisation

Comme vous pouvez le constater, même avec un placement initial "parfait", le t-SNE "casse" le poisson dans un certain nombre de lieux initialement connectés, car la répulsion de Student-t dans le domaine de sortie est supérieure à l'affinité gaussienne de l'entrée. espace.

Comme vous pouvez le constater, le t-SNE (et le SNE aussi!) Est une technique de visualisation intéressante , mais elle doit être manipulée avec précaution. Je préférerais ne pas appliquer k-means sur le résultat! parce que le résultat sera fortement déformé et que ni les distances ni la densité ne sont bien préservées. Au lieu de cela, utilisez-le plutôt pour la visualisation.

Erich Schubert
la source
1
Merci d'avoir répondu. Je peux imaginer des méthodes de classification adaptative basées sur le voisinage, mais existe-t-il des méthodes spécifiques bien développées que vous pourriez recommander?
generic_user
1
CHAMAELEON est probablement le plus cité, mais il semble qu’il n’ya qu’un fichier binaire disponible pour l’étape principale. L'idée semble bonne, mais vous allez rapidement expérimenter les mêmes effets que ceux que t-SNE rend visibles. Tels que la tendance à "se rassembler" comme on le voit avec p = 20, des problèmes de hubs et d'anti-hubs, etc.
Erich Schubert
2
@AlexR: Perplexité est utilisé pour calculer les similitudes dans l'espace de haute dimension que t-sne tente ensuite de faire correspondre en 2D. Changer la perplexité signifie changer les similitudes, donc je ne vois pas en quoi comparer les divergences de KL résultantes peut être significatif.
amibe dit de réintégrer Monica
1
@AlexR. "Seule la probabilité conditionnelle de l'espace de dimension inférieure dépend de la perplexité" - cette affirmation est fausse. La perplexité est utilisée pour choisir les sigmas nécessaires pour eq (1), elle influence donc les cond. probs. dans le plein espace.
Amibe dit: Réintégrer Monica
1
Pour des mises en garde et de jolis graphismes sur t-SNE, consultez également distill.pub/2016/misread-tsne
Tom Wenseleers
34

J'aimerais apporter une opinion quelque peu dissidente à la réponse bien argumentée (+1) et hautement votée de @ErichSchubert. Erich ne recommande pas le regroupement sur la sortie du t-SNE et présente quelques exemples de jouets pouvant induire en erreur. Sa suggestion est d'appliquer la classification aux données d'origine à la place.

utilisez t-SNE pour la visualisation (et essayez différents paramètres pour obtenir quelque chose de visuellement agréable!), mais ne lancez pas de clustering par la suite, en particulier n'utilisez pas d'algorithmes basés sur la distance ou la densité, car ces informations ont été intentionnellement (!) perdues.

Je suis bien conscient de la façon dont la sortie t-SNE peut être trompeuse (voir https://distill.pub/2016/misread-tsne/ ) et je conviens qu'elle peut produire des résultats étranges dans certaines situations.

Mais considérons quelques données réelles de grande dimension.

Prendre des données MNIST : 70000 images à un chiffre. Nous savons qu'il y a 10 classes dans les données. Ces classes semblent bien séparées pour un observateur humain. Cependant, le regroupement des données MNIST en 10 groupes est un problème très difficile. Je ne suis au courant d' aucun algorithme de mise en grappes qui classerait correctement les données en 10 grappes; plus important encore, je ne suis au courant d'aucune heuristique de regroupement qui indiquerait qu'il existe 10 (pas plus et pas moins) de grappes dans les données. Je suis certain que les approches les plus courantes ne pourraient pas l'indiquer.

Mais faisons t-SNE à la place. (On peut trouver de nombreuses figures de t-SNE appliquées au MNIST en ligne, mais elles sont souvent sous-optimales. D'après mon expérience, il est nécessaire d'exagérer tôt pendant un certain temps pour obtenir de bons résultats. Ci-dessous, je l'utilise perplexity=50, max_iter=2000, early_exag_coeff=12, stop_lying_iter=1000). Voici ce que j'obtiens, à gauche, sans étiquette, et à droite, coloré selon la vérité sur le terrain:

MNIST t-SNE

Je dirais que la représentation t-SNE non marquée suggère 10 groupes. L'application d'un algorithme de regroupement basé sur la densité, tel que HDBSCAN, avec des paramètres soigneusement sélectionnés, permettra de regrouper ces données 2D en 10 groupes.

Au cas où quelqu'un douterait que l'intrigue de gauche ci-dessus suggère effectivement 10 grappes, voici ce que je tire de l'astuce "exagération tardive" qui consiste à effectuer des max_iter=200itérations supplémentaires exaggeration=4(cette astuce est suggérée dans cet excellent article: https://arxiv.org /abs/1712.09005 ):

MNIST t-SNE avec exagération tardive

Maintenant, il devrait être très évident qu’il existe 10 grappes.

J'encourage tous ceux qui pensent que le regroupement après t-SNE est une mauvaise idée de montrer un algorithme de regroupement qui permettrait d'obtenir un résultat aussi satisfaisant.

Et maintenant, encore plus de données réelles.

Dans le cas du MNIST, nous connaissons la vérité sur le terrain. Considérons maintenant des données avec une vérité de terrain inconnue. Le clustering et le t-SNE sont couramment utilisés pour décrire la variabilité cellulaire dans les données de cellules uniques ARN-seq. Par exemple , Shekhar et al. 2016 a essayé d'identifier des grappes parmi 27 000 cellules rétiniennes (le génome de la souris contient environ 20 000 gènes, la dimensionnalité des données est donc en principe d'environ 20 000; Ils font t-SNE et ils font séparément la mise en cluster (un pipeline de mise en cluster compliqué suivi de certaines fusions de cluster, etc.). Le résultat final a l'air plaisant:

entrez la description de l'image ici

La raison pour laquelle cela semble si agréable est que t-SNE produit des grappes clairement distinctes et que son algorithme de grappage produit exactement les mêmes grappes. Agréable.

Cependant, si vous regardez dans les questions complémentaires, vous verrez que les auteurs ont essayé différentes approches de regroupement. Beaucoup d'entre eux ont l'air horribles sur l'intrigue t-SNE parce que, par exemple, le grand groupe central est divisé en plusieurs sous-groupes:

entrez la description de l'image ici

Alors, que croyez-vous: la sortie de votre algorithme de classification préféré avec votre heuristique préférée pour identifier le nombre de classes, ou ce que vous voyez sur le graphe t-SNE? Pour être honnête, malgré toutes les faiblesses du t-SNE, j'ai tendance à le croire davantage. Ou en tout cas, je ne vois pas pourquoi je devrais le croire moins .

l'amibe dit de réintégrer Monica
la source
2
Et pour le dernier exemple, n’est-ce pas essentiellement ce que @ErichSchubert a observé ci-dessus: vous pouvez obtenir des résultats "agréables" sur le plan visuel, ce qui est évidemment faux? Comme avec la perplexité 20? Ce tSNE aime séparer les pièces (comme dans le poisson) qui n'ont pas été séparées? Alors savez-vous que les grappes que vous voyez sont bien des grappes séparées? Je n'aime pas cette "boîte noire" là-bas. Oui, nous avons tendance à croire davantage ces complots, mais que se passe-t-il s'ils se trompent?
Anony-Mousse
1
Eh bien, tSNE est basé sur NN. Un accord avec cela est à prévoir. tSNE est un bon choix pour visualiser NN. Cela ne préserve pas très bien les similitudes, alors il faut interpréter cela avec prudence, si je comprends bien. Une lacune dans la TNEE n'implique pas une grande distance.
Anony-Mousse
1
+1 Curieux de savoir comment UMAP fonctionne par rapport à t-SNE.
Paul
1
@Paul: l'auteur revendique la supériorité d'UMAP, en termes de temps de calcul, il l'est. Sur le jeu de données MNIST, je trouve que UMAP génère une meilleure incorporation que t-SNE, mais pas sur d'autres jeux de données. Autant que je sache, il existe récemment une version CUDA de t-SNE, qui est beaucoup plus rapide que l'ancien t-SNE le plus rapide, mais je n'ai pas pu installer et tester.
SiXUlm
1
@SiXUlm github.com/KlugerLab/FIt-SNE fonctionne beaucoup plus vite que Barnes-Hut t-SNE et est souvent plus rapide que UMAP. De plus, dans de nombreux cas, on peut obtenir une intégration très similaire avec t-SNE en utilisant quelques ajustements supplémentaires, par exemple, sur MNIST, la t-SNE avec une légère exagération donne presque la même chose qu’UMAP, voir l’exemple de cahier Python dans le référentiel FIt-SNE.
amibe dit de réintégrer Monica le
6

Je pense qu'avec une grande perplexité, t-SNE peut reconstruire la topologie globale, comme indiqué dans https://distill.pub/2016/misread-tsne/ .

À partir de l'image du poisson, j'ai échantillonné 4000 points pour le t-SNE. Avec une grande perplexité (2000), l'image du poisson a été pratiquement reconstruite.

Voici l'image originale. Image originale

Voici l'image reconstruite par t-SNE avec perplexité = 2000. Image reconstruite en t-SNE (perplexité = 2000)

en sens inverse
la source
8
Si vous choisissez de telles perplexités, ce n’est plus vraiment la tNE. Chaque point est approximativement voisin tous les jours. Ce n'est plus local. Oui, une image 2D peut ensuite être approximativement reconstruite, car elle est 2D. Mais ne pas faire la chose entière est plus facile.
Anony-Mousse
1
Mon opinion est que la TNE avec une grande perplexité puisse reconstruire la topologie globale. L'image en 2D est un exemple car sa dimensionnalité intrinsèque est 2. L'application réelle du tSNE doit sélectionner la perplexité appropriée en fonction du but recherché pour capturer les caractéristiques locales ou globales.
Renxwise
1
Des perplexités aussi élevées signifient que vous utilisez un "noyau" trop volumineux et que vous utilisez simplement les distances. Il dégénère alors probablement en un SDM approximatif et très coûteux. Utilisez simplement MDS alors. SNE / tSNE devrait vraiment être utilisé avec de petites perplexités et des quartiers locaux.
Erich Schubert
3
Exactement. Lorsque la perplexité est suffisamment grande, tSNE est en effet proche de MDS, ce qui montre que le tSNE peut également capturer la structure globale. Ainsi, les affirmations selon lesquelles tSNE ne peut capturer que les structures locales ne sont pas correctes. Différent de MDS, tSNE peut équilibrer les structures locales et globales via la sélection de la perplexité. De toute évidence, la sélection de la perplexité dépend de l'ensemble de données.
Renxwise
Existe-t-il une règle de base pour choisir une perplexité plausible?
Catbuilts
5

Sur la base des preuves mathématiques dont nous disposons, cette méthode pourrait techniquement préserver les distances! pourquoi ignorez-vous tous cette fonctionnalité! Le t -SNE convertit les distances euclidiennes de haute dimension entre échantillons en probabilités conditionnelles représentant des similitudes. J'ai essayé le t -SNE avec plus de 11 000 échantillons (dans le contexte de la génomique) en parallèle avec différents algorithmes de clustering consensuels, notamment le clustering spectral, Affinity et, surtout, le clustering GMM (un algorithme de clustering basé sur la densité!). En conséquence, j’ai trouvé un très bon résultat concordant entre deux approches ( t-SNE vs algorithmes de clustering de consensus). Je pense que l'intégration de t-SNE avec des algorithmes de clustering consensuels pourrait fournir la meilleure preuve des structures de données locales et globales existantes.

Reza Rafiee
la source
Existe-t-il des paramètres qui influenceront la probabilité que les T-SNE préservent les distances?
Keith Hughitt le
Ce ne sont pas des algorithmes de clustering de consensus. La classification par consensus est un type d'apprentissage de l'ensemble qui regroupe les résultats de la répétition de l'algorithme de classification avec une certaine variation des paramètres ou des données d'entrée pour obtenir un résultat de classification final. Vous pouvez utiliser des approches de clustering de consensus avec clustering spectral ou GMM ou bien n’importe quel algorithme de clustering, mais mon point dans votre terminologie est un peu décalé, c’est tout :)
Christopher John
1

Vous pouvez essayer l'algorithme de clustering DBSCAN. En outre, la complexité de tsne devrait être à peu près de la même taille que le plus petit cluster attendu.

James LI
la source
0

Personnellement, je l’ai expérimenté une fois, mais pas avec le t-SNE ou le PCA. Mes données d'origine sont dans un espace à 15 dimensions. En utilisant UMAP pour le réduire aux intégrations 2D et 3D, j'ai obtenu 2 clusters parfaitement et visuellement séparables sur les tracés 2D et 3D. Trop beau pour être vrai. Mais quand j'ai "examiné" les données originales du diagramme de persistance, j'ai réalisé qu'il y avait beaucoup plus de clusters "significatifs", pas seulement 2.

Le regroupement des résultats de la technique de réduction de dimension doit être fait avec beaucoup de prudence, sinon toute interprétation peut être très trompeuse ou erronée car la réduction de la dimension entraînera sûrement une perte de fonctionnalités (peut-être des fonctionnalités bruyantes ou vraies, mais à priori, nous ne le ferons pas. t savoir lequel). À mon avis, vous pouvez faire confiance / interpréter les clusters, si:

  • Les grappes dans les données projetées correspondent / confirment à une classification définie a priori (pensez au jeu de données MNIST, où les grappes de données projetées correspondent très bien à la classification des chiffres), et / ou,

  • Vous pouvez confirmer la présence de ces clusters dans les données d'origine à l'aide d'autres méthodes, telles que les diagrammes de persistance. Compter uniquement le nombre de composants connectés peut être effectué dans un délai raisonnable.

SiXUlm
la source
Pourquoi avez-vous fait confiance au "diagramme de persistance" plus qu’à UMAP? Je ne pense pas que regarder le diagramme de persistance puisse être décrit comme "regarder les données originales" ...
amibe dit Réintégrer Monica
Vous avez raison. Le diagramme de persistance ne montre que certaines caractéristiques des données d'origine, le plus souvent des composants connectés, des trous unidimensionnels et des trous beaucoup plus rares, bidimensionnels ou plus en raison d'un calcul coûteux. J'aurais donc dû dire que je ne peux que "regarder" partiellement les données d'origine en consultant le diagramme de persistance correspondant. Mais je peux faire confiance à ce que j'observe à partir de ce diagramme de persistance, car il est directement construit à partir des données d'origine.
SiXUlm le
En revanche, en utilisant UMAP ou toute autre technique de réduction de dimension, nous travaillons uniquement avec une version projetée / modifiée des données d'origine. Comme l'a souligné la réponse la plus votée, la classification peut être différente pour les différents choix de paramètres.
SiXUlm le