Chapitre 9 : t-Sne ou la réinvention de MDS

24873243915_dd5220e41c_k
Classement de 1728 images d’animaux et de plantes avec t-Sne – Gene Kogan

1 Un peu de théorie

la méthode t-Sne peut être présentée comme une méthode d’analyse des proximités s’inscrivant dans une vieille tradition des modèles de Multi Dimensional Scaling qui ont eu leur heure de gloire en marketing, dès les années 1970 pour réaliser des cartes de positionnement perceptuel). Ce sont des méthodes qui vise à mettre à plat des données multidimensionnelles, qui déplie leur relation.

Dans cette bonne tradition, l’objectif est de représenter dans un espace de faible dimension (1,2 ou 3 rarement 4), les positions relatives d’objets dont on connait le degré de similarité. Il s’agit donc de minimiser l’écart entre la somme des distances dans l’espace réduit et celle de la matrice de similarité qui en est l’input. Dans les méthodes classiques quand le nombre d’objet est grand, que les similarités ne sont pas des distances ( par exemple ne respecte pas certains critères ex: …) on obtient généralement des solutions dites dégénérées. Tous les points sont sur un cercle, ou une sphère, qui les rend tous plus ou moins équidistants. Aucune information n’est obtenue.

La singularité et la force de t-Sne est de pouvoir fonctionner sur de grands ensembles de points, des centaines des milliers, voie des dizaines de milliers. Une de ses réalisations remarquable est le artexperiment with Google. Des milliers d’oeuvres, dont les ressemblances deux à deux ont été sans doute calculée en comparant les couleurs et tonalités de chaque pixels, donc sur 1 million de variables ( là il commence à s’agir de big data), sont positionnées dans un espace plan plus ou moins vallonnés qui dessine un véritable jardin des arts.

Celle-ci provient d’une particularité de t-Sne est de s’appuyer sur une distance particulière qui permet de déformer le plan de projection et ainsi de modifier la distance localement en la contractant ou la dilatant selon la densité d’objets. Autrement dit quand de nombreux points sont dans la même zone de l’espace, l’algorithme tendra à les éloigner les uns des zones, en revanche, entre deux zones éloignée, et peu dense, l’algorithme rapprochera les groupes de points.

La perplexité est le paramètre principal du modèle et dans la pratique il est nécessaire d’explorer des valeurs de 10 à 100.

Le site de l’auteur, Laurent Van Der Maaten, est précieux.

Le package Rtsne est la solution que nous allons employer. C’est essentiellement une passerelle vers le code C originel.

2. mise en oeuvre de rtsne

Elle est simplissime. Les premières lignes du code vise fixer le tableau de données que l’on va traiter tous les lemmes qui apparaissent au moins deux fois dans le corpus.

L’analyse proprement dite est réalisée avec la fonction Rtsne. On indique le fichier le donnée, le nombre de dimension initiale qui est en fait une ACP, la valeur de la perplexité qui est le paramètre de commande principal. Du thêta qui pilote la vitesse d’ajustement, du nombre maximum d’itérations.

tbl_stem_tsne<-select(tbl_stem,year,doc,word)%>%
  ungroup()%>%
  group_by(doc)%>%
  count(word)%>%
  filter(n>1)%>%
  ungroup()

library(tsne)
tsne_out_2 <- Rtsne(tbl_stem_tsne, dims=2, initial_dims = 102, check_duplicates = FALSE, verbose=TRUE, perplexity = 2, theta=0.8,  max_iter = 500)

L’output montre qu’à partir de l’epoch 300 l’erreur est fortement réduite et
devient stationnaire. Le modèle converge. Le calcul prend près de 13 » sur un processeur cadencée à 4ghhtz et 32Go de mémoire vive.

## Read the 3514 x 102 data matrix successfully!
## Using no_dims = 2, perplexity = 2.000000, and theta = 0.800000
## Computing input similarities...
## Normalizing input...
## Building tree...
## - point 0 of 3514
## Done in 0.69 seconds (sparsity = 0.002586)!
## Learning embedding...
## Iteration 50: error is 110.170334 (50 iterations in 1.28 seconds)
## Iteration 100: error is 89.631841 (50 iterations in 1.06 seconds)
## Iteration 150: error is 83.163893 (50 iterations in 1.25 seconds)
## Iteration 200: error is 79.446961 (50 iterations in 1.26 seconds)
## Iteration 250: error is 76.811074 (50 iterations in 1.31 seconds)
## Iteration 300: error is 3.070142 (50 iterations in 1.25 seconds)
##
Iteration 350: error is 2.520174 (50 iterations in 1.36 seconds)
## Iteration 400: error is 2.225130 (50 iterations in 1.37 seconds)
##
Iteration 450: error is 2.049118 (50 iterations in 1.43 seconds)
## Iteration 500: error is 1.907466 (50 iterations in 1.41 seconds)
## Fitting performed in 12.98 seconds

On répète l’opération pour différente valeur de perplexité et on obtient les représentations suivantes qui traduise certainement des échelles thématiques différentes. Quand la perplexité est grande, les lemmes se regroupent en apparemment 6 catégories, quand la perplexité est minimal des groupements plus dispersés occupent l’ensemble de l’espace.

Puisque désormais chaque lemme est identifié par ses coordonnées, pour y voir plus clair, des méthodes de clustering ( en français on préfère typologie, et en informatique celui d’apprentissage non supervisé) peuvent être utiles. (On les examine dans le chapitre 4).

Voici les résultats de deux approches, l’une par une méthode non hiérarchique ultra classique : k-means et l’autre par une méthode standard hiérarchique.

## keeping original data
d_tsne_original=d_tsne_30

## Creating k-means clustering model, and assigning the result to the data used to create the tsne
fit_cluster_kmeans=kmeans(scale(d_tsne_30), 6)  
d_tsne_original$cl_kmeans = factor(fit_cluster_kmeans$cluster)

## Creating hierarchical cluster model, and assigning the result to the data used to create the tsne
fit_cluster_hierarchical=hclust(dist(scale(d_tsne_30)))

## setting 6 clusters as output
d_tsne_original$cl_hierarchical = factor(cutree(fit_cluster_hierarchical, k=6))  
plot_k=plot_cluster(d_tsne_original, "cl_kmeans", "Accent")  
plot_h=plot_cluster(d_tsne_original, "cl_hierarchical", "Set1")
## and finally: putting the plots side by side with gridExtra lib...
grid.arrange(plot_k, plot_h,  ncol=2) 

 

Maintenant il reste à analyser les contenus! Ils reste à faire la liste des mots les plus fréquents par groupes pour deviner les thèmes du discours. Le reste du travail est graphique, les artistes de ggplot en feront apparaître les éléments saillants par des filtres astucieux.

Et d’ailleurs, une idée. Plutôt que de projeter bêtement les scores des objets d’une AFCM dans un espace bêtement euclidien, autant prendre les scores factoriels jusqu’à des dizaines de dimensions et les injecter dans le calcul de distances. Je suis prêt à papier que les modalités rare qui déforme le nuages seront rapprochées des autres et laisseront apparaître des motifs plus fins.

t-Sne est un outil de visualisation, un coup de génie qui permet de faire le pont entre des dimensions si nombreuses qu’elles défient notre capacité de représentation, et le travail graphique et esthétique qui permet à l’esprit de prendre une décision.

 

 

 

Publicités