Modèles à structure latente

TP1 Données, Kmeans, CHA

1 Données, ACP

Dans cette premiere partie nous travaillons sur les données crabs, afin d’illustrer le danger possible de l’utilisation de l’ACP.

1.1 Les données

Cet ensemble de données contient des mesures morphologiques sur les crabes Leptograpsus.
Il contient 200 observations et 8 variables.

Appercu du jeu de données Crabs

sp	sex	index	FL	RW	CL	CW	BD
B	M	1	8.1	6.7	16.1	19.0	7.0
B	M	2	8.8	7.7	18.1	20.8	7.4
B	M	3	9.2	7.8	19.0	22.4	7.7
B	M	4	9.6	7.9	20.1	23.1	8.2
B	M	5	9.8	8.0	20.3	23.0	8.2

Ce jeu comptabilise 5 mesures morphologiques sur 200 crabes, de deux couleurs et des deux sexes, de l’espèce Leptograpsus variegatus collectée à Fremantle en Australie occidentale.

Nous avons deux variables qualitatives :

• sp = L’espèce : B pour Bleu ou O pour Orange
• sex = Le sexe : M pour Male ou F pour Femelle

Et six variables quantitatives :

• index = Un indice allant jusq’à 50 dans chacun des quatre groupes
• FL = la taille du lobe frontal en mm
• RW = la largeur du dos en mm
• CL = la longueur de la carapace en mm
• CW = la largeur de la carapace en mm
• BD = la profondeur du corps en mm

Nous nous demandons quelles variables sont les plus importantes?
Comment réduire ce jeu de données afin de le représenter de manière simple sur 2 ou 3 axes par exemple?
Grace a l’Analyse en Composantes Principales nous allons pouvoir faire une réduction de dimension, et transformer les variables très corrélées en nouvelles variables décorrélées les unes des autres.
Évidemment, qui dit réduction de dimension dit perte d’informations.
C’est là tout l’enjeu : il faut pouvoir réduire la dimension de nos données tout en conservant un maximum d’informations.

Pour avoir une premiere idée sur ces données, on commence par tracer un histogramme:

En déplaçant le curseur sur le graphique nous pouvons voir facilement les valeurs de nos 5 variables d’interet.

Pour voir maintenant comment l’une de ces variable est affectée par une autre, nous réalisons un scatter plot:

De même, le curseur nous permet d’obtenir facilement chaque valeur.
Nous remarquons que les variables CL et CW s’alignent parfaitement sur une même droite, elles sont fortement liées, elles sont corrélées. Leur coeffcient de corrélation est proche de 1.
Les variables BD et RW sont les moins liées.
Les autres variables sont elles aussi correlées, mais un peu moins. Leurs coefficients de corrélation est proche de 0.8.
Quoi qu’il en soit, on voit une très forte corrélation générale entre les données. (dit “effet taille”)

1.2 Proportion de variance expliquée par les deux premières composantes principales

Sur le deuxieme graphique “PCA graph of variables” les variables corrélées positivement sont du même côté du graphique. Les variables corrélées négativement sont sur des côtés opposés du graphique.
Nous voyons que nous avons 95,78% de la variance expliquée par le premier axe principal, et seulement 3,03% par le deuxieme. Cela nous laisse penser que nous pouvons exprimer nos données avec uniquement la premiere composante principale.

1.3 Projection sur la première composante principale

La ligne en pointillé rouge nous indique la contribution moyenne attendue.
Si la contribution des variables était uniforme, la valeur attendue serait 1/length(variables) = 1/10 = 10%.
Pour une composante donnée, une variable avec une contribution supérieure à ce seuil pourrait être considérée comme importante pour contribuer à la composante.
Nous remarquons que les varibales CL,FL,BD,CW sont legerement importantes pour la contribution a cet axe, contrairement a la variable RW qui se trouve en dessous de ce seuil.

1.4 Projection sur la deuxième composante principale

Nous remarquons maintenant, a l’inverse, que la variable RW est celle qui contribue le plus pour le deuxieme axe. (et de loin)

1.5 Projection sur les deux premières composantes principales

Nous remarquons que les variables CW et CL sont les seules a contribuer désormais.

1.6 Conclusion

Nous décidons de projeter les données sur ses composantes principales, croisées entre elles. Tout d’abord, pour le sexe, nous obtenons :

Puis, pour le type d’espece nous obtenons:

Nous concluons finalement que l’ACP nous pousse a retenir qu’un seul axe principal, alors que dans les faits, toutes les variables contribuent uniformement sur les deux premiers axes, et qu’il faut garder les deux pour une meilleure interpetation!!

2 Kmeans et clustering hiérarchique ascendant

2.1 Les données

Comme proposé, nous allons travailler sur les données Seeds.
Cet ensemble de données contient des mesures, correspondantes aux propriétés géométriques de grains de blé.
Il contient 210 observations et 8 variables.

Appercu du jeu de données Seeds

Variétés	Surface	Périmètre	Compacité	Longueur	Largeur	CoefAsym	Rainure
Kama	15.26	14.84	0.8710	5.763	3.312	2.221	5.220
Kama	14.88	14.57	0.8811	5.554	3.333	1.018	4.956
Kama	14.29	14.09	0.9050	5.291	3.337	2.699	4.825
Kama	13.84	13.94	0.8955	5.324	3.379	2.259	4.805
Kama	16.14	14.99	0.9034	5.658	3.562	1.355	5.175

Nous avons trois variétés de grains de blé différentes, de 70 éléments chacun, choisis au hasard :

• Variétés = Kama, Rosa et Canadian

Et sept paramètres géométriques (continus à valeur réelle) mesurés :

• Surface = la surface A
• Périmètre = le périmètre P
• Compacité = la compacité \(C = \frac{4\pi A}{P^2}\)
• Longueur = la longueur du noyau
• Largeur = la largeur du noyau
• CoefAsym = le coefficient d’asymétrie
• Rainure = la longueur de la rainure du noyau

A partir de ces sept parametres, notre objectif de clustering sera donc de regrouper les 210 grains en K classes,
les plus concentrées et disctinctes possibles.
Nous allons donc faire comme si nous ne savions pas a quelle variété chaque grain appartenait, et essayer de retomber sur nos 3 clusters :
Kama - Rosa - Canadian, tous distincts, de taille 70.

Pour avoir une premiere idée des données, réalisons quelques graphiques.
On commence par tracer un histogramme de nos 7 paramètres normalisés:

Ces histogrammes representent la fréquence en fonction des valeurs de nos variables.
Nous voyons bien la symétrie, dû a la mise a l’echelle, mais c’est tout…il nous est difficile de savoir combien de composantes nous seront nécessaires pour décrire les données.

Nous décidons donc de faire une ACP sur nos 7 variables quantitatives continues, afin de réduire la dimension de nos données tout en gardant un maximum de l’information.

En jetant un coup d’oeil sur la variance cumulée, nous voyons qu’il faudrait 5 composantes pour décrire la variance a 100%.

Nous réalisons tout d’abord un graphique en 3D des données projetées sur les trois composantes principales :

A nouveau ici le curseur nous permet d’avoir directement les valeurs de nos données. De plus l’aspect 3D nous permet de mieux visualiser leur rapartition dans l’espace. Les trois premières composantes contiennent 99,48% de la variance, donc presque 100%!

Cependant, comme les deux premières composantes contiennent environ 90% de la variance, nous estimons qu’il nous est suffisant de se limiter a celles-ci pour exprimer nos données.

Voici donc nos données projetées sur ces deux premieres composantes principales:

Visuellement nous voyons bien nos 3 groupes, cependant certains points se mélangent a d’autre variété, donc nous nous attendons a ne pas obtenir une classification “parfaite” par la suite.

On trace en complément un biplot :

Une flèche est associée à chacun des 7 paramètres, elle pointe dans la direction des valeurs croissantes du paramètre quelle represente.
La première composante principale permet de bien séparer les variétés Rosa et Canadian.
La variété Rosa sera le plus grand type de grain, la variété Canadian sera le plus petit, et la variété Kama sera entre les deux.
La variété Kama a des valeurs d’ACP plus faibles que les deux autres variétés, ce qui signifie qu’elle sera plus ronde.

De plus nous pouvons dire que les cinq paramètres Largeur, Longueur, Périmètre, Rainure et Surface sont les contributions les plus importantes pour la premiere composante principale. (ce sont les cinq flèche qui pointent sur la gauche). Elles sont bien corréléées entre elles.
Le paramètre CoefAsym est le plus important pour la deuxieme composante principale. Il est moins corrélé avec les cinqs autres paramètre Largeur, Longueur, Périmètre, Rainure et Surface.

2.2 Kmeans

Cette méthode consiste à regrouper des données dans des classes, les plus homogènes possibles.
Pour ce faire, un nombre arbitraire de classes doit etre (bien) choisi.
Ensuite, l’algorithme prend k points aléatoires (les centres) dans le nuage de point des données,
et chaque donnée est affectée au centre le plus proche.
Puis le barycentre des points de chaque classe consitutée est calculé. (donc les centres bougent)
Et une ré-affectation des individus au nouveau centre le plus proche a lieu.
Ces deux dernieres étapes sont répètées jusqu’à ce que les barycentres ne “bougent plus”. (convergence)

Il faut donc faire attention a la fois au nombre de cluster, et a la fois au nombre de points initiaux.

Tout d’abord, pour déterminer le nombre optimal de clusters, nous allons utiliser les trois méthodes suivantes:

Clustering k = 1,2,..., K.max (= 12): .. done
Bootstrapping, b = 1,2,..., B (= 100)  [one "." per sample]:
.................................................. 50 
.................................................. 100 

• La méthode Elbow permet de comparer le nombre total de WSS pour chaque valeur de k.
  Plus la valeur de k augmente, plus le WSS devrait être petit. Nous voulons donc trouver le point sur le graphique où la courbe semble se plier (indiquant une petite diminution du WSS par rapport aux valeurs précédentes de k)
  On remarque une plus forte diminution de k=1 a k=2, et de k=2 a k=3.
  Donc k=2 ou k=3 seraient de bons candidats à essayer.

• La méthode Silhouette mesure la façon dont chaque point de données s’intègre dans son cluster.
  Une valeur de silhouette élevée, indique un bon clustering.
  Cette méthode nous suggére donc de prendre k=2 comme nombre optimal de clusters.

• La statistique de GAP permet de comparer la variation intra-clusters totale pour différentes valeurs de k, aux valeurs attendues.
  La valeur k=3 semble etre le bon chiffre!

Nous allons donc utiliser 3 clusters pour répartir nos données.

Pour comprendre maintenant comment l’algorithme des Kmeans fonctionne, nous représentons graphiquement l’évolution des affectations des classes et des centres de celles-ci, au cours des trois premieres itérations, avec la même initialisation à chaque fois:

Nous indiquons les points qui changent d’appartenance à un groupe en les colorant.
Malheureusement (ou heureusement) comme l’algorithme converge très vite, cela s’arrete dès la deuxieme itération…

Maintenant, nous réalisons la méthode Kmeans afin d’obtenir 3 clusters:

L’agorithme des Kmeans affecte : 71 Kama - 67 Rosa - 72 Canadian

Nous avons représenté sur un même graphique :
Les résultats de la classification Kmeans : 1 - 2 - 3
superposés aux étiquettes réelles : Kama - Rosa - Canadian

Cette classfication n’est pas parfaite, mais relativement correcte.

2.3 Clustering Hiérarchique Ascendant

Nous gardons le même objectif de classification, mais nous appliquons maintenant la méthode du clustering hiérarchique ascendant, avec differentes fonctions de linkage.

• Methode 1: la fonction de linkage de Ward
  Elle consiste a minimiser la variance totale au sein du cluster. (clusters compacts)
  À chaque étape, la paire de clusters ayant la plus petite distance inter-clusters est fusionnée.

Regardons inertie et dendogramme:

Pour bien voir la classification faite , nous avons représenté les sauts d’inertie en gardant que les 20 premieres valeurs du dendrogramme, selon le nombre de classes retenues. Nous pouvons remarquer deux sauts signifivatif en 2 et en 3 classes. nous les avons entouré ensuite en bleu et rouge sur le dendrogramme. La meilleure classification avec la méthode Ward est avec 3 classes.

Finalement, la classification ascendante hiérarchique avec la methode Ward affecte :
61 Kama - 86 Rosa - 63 Canadian

• Methode 2: single linkage (min)
  Elle consiste a calculer toutes les dissimilarités par paire entre les éléments de deux clusters, et considère la plus petite de ces dissimilarités comme un critère de liaison. (clusters longs) Nous allons refaire exactement la meme analyse.

Regardons inertie et dendogramme:

On observe que le single linkage tend à créer des dendogrammes avec de très fines parties/clusters.
Agissant comme un nearest neighbor, cette classification hierachique assure une petite distance entre deux points voisins, mais des points de parts et d’autres du cluster peuvent être éloignés.

Regardons les pertes relatives d’inertie:

[1] 4

La meilleure partition selon ce critère est représentée par un point noir, et la seconde par un point gris. Cela nous indique de prendre 4 clusters…

• Methode 3: complete linkage (max)
  Elle consiste a calculer toutes les dissimilarités par paire entre les éléments de deux clusters, et considère la plus grande valeur de ces dissimilarités comme la distance entre les deux clusters. (clusters compacts)

Regardons inertie et dendogramme:

La methode Complete nous donne un partitionnement de 3 classes, mais pas du tout equilibré, du coup la classification n’est pas bonne:

• Méthode 4: group average
  Elle consiste a calculer toutes les dissimilarités par paire entre les éléments de deux clusters, et considère la moyenne de ces dissimilarités comme la distance entre les deux clusters.

[1] 3

Cela nous indique 3 clusters.
Finalement, la classification ascendante hiérarchique avec la methode Average affecte :
81 Kama - 64 Rosa - 65 Canadian

C’est une classfication moins bonne que celle avec la methode Ward mais elle reste correcte.

Nous en concluons que la méthode Ward est la meilleure!!

2.4 Caractérisation des classifications obtenues

Les différences entre les deux methodes de classiffication sont:

• La distance utilisée: Le clustering hiérarchique peut gérer n’importe quelle mesure de distance, tandis que les Kmeans reposent sur les distances euclidiennes.

• La stabilité des résultats: La méthode Kmeans nécessite une étape aléatoire lors de son initialisation qui peut donner des résultats différents si le processus est réexécuté, ce qui n’est pas le cas dans le clustering hiérarchique.

• Le nombre de cluster: Même si on peut utiliser des tracés de silhouette, ou d’autre moyens pour trouver le bon nombre avant d’appliquer la méthode des Kmeans, Le clustering hiérarchique peut en plus s’appuyer sur un dendrogramme.

• Complexité de calcul: La méthode des Kmeans est moins coûteuse en calcul que celle du clustering hiérarchique, et elle peut être exécuté sur de grands ensembles de données assez rapidement, ce pourquoi on la prèfere!

• Categorie: Le Kmeans est de base centroide, alors que la CHA est hiérarchical.

• Methodes pour trouver différents clusters: Pour le Kmeans nous avons Elbow, Silhouette, et Gap. Tandis que pour la CHA nous avons en plus Dendrogramme et inertie.

• Conclusion: Le Kmeans est fortement impacté par les centroides initiaux, ce qui peut produire des resultats sous optimaux. Mais il a l’avantage d’avoir une convergence garantie, spécifiquement pour les clusters de differentes tailles et formes.
  La CHA est plus flexible, plus facile en traitement de toute forme de similarité et de distance. Elle est plus facile pour determiner le nombre de clusters.
  Par rapport a notre étude, nous en concluons qu’il y a bien une différence spécifique de clusters dans les données (nous avons bien 3 variétés). Il est mieux pour nous de choisir la méthode des kmeans dans l’ensemble. Mais particulierement, le nombre de clusters se fait mieux avec la CHA, et le clustering avec les K-means.

2.5 Pour aller plus loin

Nous pourrons comparer nos resultas avec plusieurs autres methodes de clustering, il existe une large varieté d’algorithme de classification non supervisé. Comme par exemple la methode MNIVAR (variance minimizing hierarchical clustering) mais malheureusement n’avons trouvé que des articles payants a ce sujet…

Nous avons alors decidé de tester d’autre methode, tel que l’alghortime de CLARA. Au lieu de trouver des médoïdes pour l’ensemble de données, CLARA considère un petit échantillon de données avec une taille fixe (sampsize) et applique l’algorithme PAM pour générer un ensemble optimal de médoïdes pour l’échantillon. La qualité des médoïdes résultants est mesurée par la dissemblance moyenne entre chaque objet de l’ensemble de données et le médoïde de son cluster, défini comme la fonction de coût.
CLARA répète les processus d’échantillonnage et de regroupement un nombre de fois prédéfini afin de minimiser le biais d’échantillonnage. Les résultats de regroupement finaux correspondent à l’ensemble des médoïdes avec le coût minimal.

     size max_diss  av_diss isolation
[1,]   74 2.953138 1.432597 1.4337330
[2,]   64 2.599767 1.355004 0.7086906
[3,]   72 2.809322 1.353406 1.3639109

Nous remarquons que l’alghorithme a classé : 74 kama, 64 Rosa et 72 Canadian…ce qui n’est toujours pas parfait…

     size max_diss  av_diss diameter separation
[1,]   77 2.769122 1.400510 4.601093  0.5747312
[2,]   62 2.334422 1.322603 3.954075  0.5747312
[3,]   71 3.168492 1.331149 5.155598  0.6125787

Nous remarquons que l’alghorithme a classé : 77 kama, 62 Rosa et 71 Canadian…ce qui n’est toujours pas parfait…