Regroupement/clustering

sous R

L'essentiel de cette page

Les regroupements sont des méthodes non supervisées qui permettent de définir des groupes ou classes. On distingue parmi ces mesures les méthodes suivantes :

Remarque importante : il ne faut pas confondre regroupement/clustering et classification/catégorisation.

Voir ma page pour faire cette distinction ! Regroupement/clustering et Classification/catégorisation avec R

0- Création d'un jeu de données simulées (exemple)

Il serait trop ambitieux de présenter ici un panel exhaustif des méthodes de regroupement de données (clustering).

Voici donc quelques méthodes et quelques liens externes pour aller plus loin.

Cette page est dédicacée à mon mentor initial, Denis Puthier, de l'université de Aix-Marseille, dont les exemples ci-dessous sont inspirés pour une part de ses enseignements à l'école d'ingénieur Polytech Marseille.

Clustering hiérarchique R project CRAN

Dans ce jeu de données simulées, 3 nuages semblent se distinguer. Comment les regrouper ?

# On simule 500 points de coordonnées x et y et on les affiche

x = runif(500) ; y = runif(500) ; plot(x, y)

#Fonction de définition d'un cercle

circu = function(xx, yy, r){ind = sqrt( (x-xx)^2 + (y-yy)^2 )<r ; return (ind)}

#De ces 500 points, on ne conserve que 3 nuages

GR =rep(NA, 500) ; ind = circu(.3,.3,.25) ;GR[ind] <- 1; ind = circu(.8,.4,.2) ; GR[ind] <- 2 ; ind = circu(.5,.6,.13) ; GR[ind] <- 3

# Les points retenus (catégories 1, 2 et 3 sont compilés dans un data.frame, les points non retenus (NA) sont éliminés

mymat = data.frame(x=x,y=y,catégories =GR) ; mymat = na.omit(mymat) ; head(mymat)


plot(mymat[,1],mymat[,2],pch=16,cex=1.2,main="Données brutes sans regroupement",xlab="x",ylab="y")

1- Regrouper les points en appliquant la méthode de clustering des k-means

La méthode des k-means permet de regrouper les points par itération en partant initialement de "centres de gravité" définis manuellement.

Regroupement par les k-means avec R project CRAN

Le regroupement par les k-means apporte une certaine objectivité mais le nuage vert semble déborder injustement sur le noir.

tableau <- data.frame(x=mymat[,1],y=mymat[,2]);plot(tableau)


# Regrouper les points autour de ces centres, recalculer de nouveaux centres : itérations

# 20 représente le nombre maximal d'iterations

# 5 le nombre de groupes souhaités


cluster_1 <- kmeans(tableau , centers = 5, iter.max = 20) 


summary(cluster_1) # pour obtenir une description de l'objet ainsi créé


# Afficher les résultats

plot(tableau, col = cluster_1$cluster,pch=16,cex=1.2,main="Regroupement par les k-means")

points(cluster_1$centers, col = 1:3, pch = 4,cex=2,lwd=3)

legend(x="topright", legend=unique(cluster_1$cluster), col=unique(cluster_1$cluster), pch=16)

On peut aussi fixer la position initiale des centres, ce qui va influencer le calcul

# Définir les centres de n nuages approximatifs, ici 3 - (optionnel)

centres_x = c(.3, .8 , .6);centres_y = c(.3, .4, .6);centers = data.frame(centres_x, centres_y)

# Regrouper les points autour de ces centres, recalculer de nouveaux centres : itérations

cluster_1 <- kmeans(tableau , centers, 5) # 5 représente le nombre maxima d'iterations

Faire des prédictions pour classifier de nouveaux points

predict(cluster_1,tableau) # faire des prédictions sur tableau

2- Clustering par segmentation hiérarchique ascendante (CAH)

3.1 - Calculer des distances avec la méthode dist()

Cette méthode est plus fine que les k-means car elle va regrouper sur le critère de la distance séparant chaque point.

Étape 1 - Calcul d'une matrice de distance 

mydi = dist(mymat[,-3]) # -3 pour éliminer la colonne des catégories dans cet exemple

# dist offre différents paramètres dont method qui permet de choisir la méthode de calcul : "euclidean", "maximum", "manhattan", "canberra", "binary" or "minkowski"

# Attention dist est disponible par défaut sous R (librairie stats) mais peut interférer avec factoextra qu'il faut alors détacher (detach("package:factoextra")

Étape 2 - Mise en place d'un cluster

myclust <- hclust(mydi, method="ward.D2")

# hclust offre différentes méthodes (paramètres method) de détermination du cluster :  "ward.D", "ward.D2", "single", "complete", "average", "mcquitty", "median" ou"centroid".

# ward.D2 donne de très bons résultats

Étape 3 - Affichage du dendrogramme correspondant


# Afficher le dendrogramme en indiquant comme étiquette les résultats du k-means (cluster_l$cluster

plot(myclust,labels=cluster_1$cluster) # labels est optionnel


rect.hclust(myclust,3) #encadre les groupes déduit de la segmentation

rect.hclust(myclust,5,border="blue") # en cinq catégories, encadrés bleux

Clustering hiérarchique par segmentation ascendante R project CRAN

Cette méthode va permettre ainsi de retrouver 3 nouveaux groupes à partir de données présentées ici sous forme de dendrogramme.

D'autres methodes de calcul de la distance peuvent être utilisées dans la commande dist() telles :

Étape 4 - Détermination le nombre le plus logique de catégories en calculant l'inertie de l'arbre de clusterisation.

Chaque pas important correspond à une rupture qui indique un nombre vraisemblable de catégories.

inertie <- sort(myclust$height, decreasing = TRUE)

plot(inertie[1:20], type = "s", xlab = "Nombre de classes", ylab = "Inertie",lwd=2);grid()

k <- 3 # Nombre de catégorie souhaité (à paramétrer)

abline(v=k,col="red",lty=3)

points(k,inertie[k],pch=16,cex=2,col="red")

On voit ici qu'une découpe en 3 catégories est pertienent (saut à 3 catégories) : en rouge.

On aurait pu aussi ne conserver que 2 catégories.

Étape 5 - Découper en choisissant le nombre de groupes de son choix

# source : http://www.grappa.univ-lille3.fr/~gilleron/tdhclustenR.html

mytree = cutree(myclust, k=3) # 3 catégories

mytree

# Colorer le graphique selon les groupes identifiés

plot(mymat[,-3], col = mytree,pch=16,cex=1.2,main="Regroupement par segmentation hiérarchique ascendante")

legend(x="topright", legend=unique(mytree), col=unique(mytree), pch=16,bg="white")

Regroupement par segmentation hiérarchique ascendante (R project CRAN)

Le regroupement par segmentation hiérarchique ascendante semble donner des résultats plus précis que les k-means.

Remarque, on peut ainsi très facilement regrouper selon le nombre de catégories désirées. (Par exemple 5 catégories, k=5)


Regroupement par segmentation hiérarchique ascendante (5 catégories)

Si k = 5

On peut aussi afficher les dendrogrammes de chaque catégorie :

plot(hclust(dist(mymat[cutree(myclust,k=3)==1,-3]),method="ward.D2"))

plot(hclust(dist(mymat[cutree(myclust,k=3)==2,-3]),method="ward.D2"))

plot(hclust(dist(mymat[cutree(myclust,k=3)==3,-3]),method="ward.D2"))

3.2 - Mettre en forme les dendrogrammes

On peut mettre les dendrogrammes en forme de façon subtile avec la librairie dendextend.

# Compiler le dendrogramme

hc <- hclust(mydi, "ave") # méthode : average 

dend <- as.dendrogram(hc)

# Installer et exécuter le package dendextend pour mettre en forme les dendrogrammes

install.packages("dendextend");library(dendextend)

# Mise en forme : on attribue 3 catégories, une épaisseur de trait pour ces catégories et un type de traits

dend <- dend %>%

          color_branches(k = 3) %>%

          set("branches_lwd", c(0.5,1,1.1)) %>%

          set("branches_lty", c(1,2,1))

 

plot(dend)

# Aller plus loin --> Source : https://cran.r-project.org/web/packages/dendextend/vignettes/FAQ.html

dend <- color_labels(dend, k = 3)

 # The same as:

 # labels_colors(dend)  <- get_leaves_branches_col(dend)

# Changer la taille de police des labels

dend <- set(dend, "labels_cex", 0.5)

# Changer le nom de labels (ici on reprend les catégories de k-means)

labels(dend) <- cluster_1$cluster

plot(dend,horiz=T) # Pour avoir un dendrogramme horizontal

Clustering hiérarchique ascendant avec changement de couleurs des branches

Mise en forme horizontale du dendrogramme avec colorations des branches correspondant à différentes catégories;

3.3 - Réaliser un cluster en heatmap (avec dendrogrammes) pour visualiser l'ensemble des résultats, les catégories mais aussi le poids de chaque paramètre et leur lien

Aller sur cette page pour voir commencent réaliser ce type de figures et en extraire les résultats.


C'est aussi l'occasion de voir le poids de chaque paramètre sur la clusterisation.

Cette représentation est aussi une introduction à la clusterisation de variables.

3.4 - Un autre exemple : on peut aussi regrouper les individus avec la Théorie des graphs (igraph)

3- Mélange de gaussiennes

Les mélanges de gaussiennes sont performantes, plus que le k-means et certainement plus que le CAH (en tous cas, moins lourd à mettre en oeuvre sur un grand jeu de données).

Toutefois, le nombre de catégories fixé "G" doit être fixé manuellement. Un CAH peut donc s'avérer utile comme outil d'aide à la décision du nombre de catégories à choisir.

library(mclust)

data(iris)

iris_mclust <- Mclust(iris[, 1:4], G = 3)

names(iris_mclust)

plot(iris[,1:2],col=iris_mclust$classification,pch=16)

Faire une prédiction lorsqu'on souhaite classer de nouveaux points :

# Prédiction

pred <- predict(iris_mclust, iris[, 1:4])

table(iris$Species,pred$classification)

4- Autres méthodes de clustering...

Il existe beaucoup d'autres méthodes de clustering.

Exemple ici : le Polar swarm.

Ou encore le DBSCAN quand les groupes ont des formes étranges et imbriquées.


Si vous avez besoin d'aide, n'hésitez pas à nous contacter pour organiser une formation (en Aquitaine, FRANCE)  !

Regroupement de plusieurs théorie pour modéliser la distance entre les points sur un nombre réduit de composantes. (Réseaux de neurones)

Voir la page d'aide.

5- Faire du clustering à partir de données issues d'une ACM, d'une ACP ou d'une projection de Fisher

1) Voici des catégories "réelles" issues de données simulées. Voyons quelle méthode permettra de retrouver au mieux ces catégories.

2) Un clustering classique donne des résultats parfois limités qui ne correspondent pas à la réalité

3) Un même clustering basé sur des résultats d'ACP ou d'ACM semble déjà mieux se rapprocher de la réalité

4) FactoMineR semble donné des résultats très proches de la classification réelle par sa méthode HCPC.

Remarque : les données traitées dans cet exemple peuvent être rapidement simulées dans R en allant les copier dans la rubrique disponible à ce lien : compilation d'analyses sanguines.

Graphique 1 - Catégories par défaut

color <- categories;color[color=="A"] <- "black";color[color=="B"] <- "red";color[color=="C"] <- "green"

plot(compilation[3:4], col = color,pch=16,cex=1.2,main="Catégories par défaut")

legend(x="topright", legend=unique(categories), col=unique(color), pch=16,bg="white")

grid()

Graphique 2 - Catégorisation classique par segmentation hiérarchique ascendante (clustering)

mydi = dist(compilation[-1],method="minkowski")

mytree = cutree((hclust(mydi)), k=3) # 3 catégories

mytree

plot(compilation[3:4], col = mytree,pch=16,cex=1.2,main="Regroupement par \nsegmentation hiérarchique ascendante")

legend(x="topright", legend=unique(mytree), col=unique(mytree), pch=16,bg="white");grid()

Graphique 3 - Catégorisation par clustering à partir des composantes issues d'ACP

acp <- dudi.pca(compilation[-1],scannf= F,scale=T,center=T,nf=5)

distances <- dist.dudi(acp)

mytree <- hclust(distances, method = "ward.D2") # d'autres méthodes de clustering existent.

mytree = cutree(mytree, k=3) # 3 catégories

plot(compilation[3:4], col = mytree,pch=16,cex=1.2,main="Regroupement par \nsegmentation hiérarchique ascendante\nsur ACP")

legend(x="topright", legend=unique(mytree), col=unique(mytree), pch=16,bg="white");grid()

Graphique 4 - Catégorisation par clustering par la méthode HCPC du package FactoMineR

library(FactoMineR)

res.pca = PCA(compilation[-1], scale.unit=TRUE, ncp=5, graph=F)

cah <- HCPC(res.pca, nb.clust = -1, graph = FALSE) # -1 : l'algo choisi le nobre de groupes

#cah <- HCPC(res.pca, nb.clust = 3, graph = F,method="single") 

#cah <- HCPC(res.pca, nb.clust = 3, graph = F,method="average") 

color <- cah$call$X$clust

plot(compilation[3:4], col = color,pch=16,cex=1.2,main="Regroupement par HCPC FactomineR")

legend(x="topright", legend=unique(mytree), col=unique(mytree), pch=16,bg="white");grid()

Avec FactoMineR, il est possible de faire différents affichages dont un cluster 3D :

plot(cah, choice = "3D.map")

Dendrogramme 3D obtenu après clustering HCPC de FactomineR

6- Visualiser les classes, les coloriser et visualiser la diversité des paramètres de chaque classe ainsi que leur relation

Aller sur cette page pour voir des méthodes automatiques pour afficher des catégories et visualiser leurs caractéristiques associées.

Coloration automatique de catégories de points sous R (CRAN)