On peut toujours trouver légitime de partager en paquets un ensemble de points même régulièrement répartis dans l’espace. Le problème est de ne pas faire d’erreurs grossières, lesquelles se voient bien en dimension 2, mais se cachent sans peine en dimension quelconque
On rappelle que la méthode des K-means consiste à faire évoluer la constitution des K groupes d’une partition des individus en les associant au centre de groupe le plus proche et en mettant à jour ces centres de classes en fonction des nouveaux groupes constitués.
La fonction kmeans est une routine permettant d’aborder un autre type de problème de clustering : le nombre de classes à former étant fixé à K, on cherche à créer K groupes d’individus aussi homogènes que possible. Etant donné une partition de départ en K groupes, on détermine pour chaque groupe son centre de gravité puis on reforme les groupes en associant ensemble les points qui sont les plus proches d’un centre de gravité. La procédure est itérée jusqu’à satisfaction d’un critère d’arrêt (généralement la stabilisation des groupes). Il faut bien comprendre qu’à l’issue des itérations, on espère avoir une partition de bonne qualité, mais il n’y a aucune garantie d’optimalité globale (par rapport à l’inertie intraclasse)
La fonction kmeans implémente le schéma des méthodes des centres mobiles et en propose plusieurs déclinaisons :
K-means clustering with 3 clusters of sizes 3, 3, 3
Cluster means:
[,1] [,2]
1 0.000000 4.333333
2 2.666667 1.333333
3 0.000000 1.000000
Clustering vector:
[1] 3 3 3 2 2 2 1 1 1
Within cluster sum of squares by cluster:
[1] 2.666667 1.333333 2.000000
(between_SS / total_SS = 85.2 %)
Available components:
[1] "cluster" "centers" "totss" "withinss" "tot.withinss"
[6] "betweenss" "size" "iter" "ifault"
il est aisé d’observer les classes formées en jouant sur les couleurs des points :
Code
KM <-kmeans(D,C)couleur <-c("blue", "red", "orange2")plot(D, asp =1, pch =19, col = couleur[KM$cluster])points(KM$centers, pch =8, col = couleur, cex =2)
l’object cluster contient l’affectation des points aux classes et
l’objet centers fournit les coordonnées des centres de classes.
Elle prend en entrée les points et le nombre de classes
L’argument des centres de classes initiaux peut être remplacé par un simple entier, le nombre de classes à former. Dans ce cas, les centres de classes initiaux sont choisis aléatoirement.
le résultat est fortement lié aux points initiaux. Afin d’observer cela, reprenez les données utilisées en 2.3 et faites plusieurs essais pour observer les variations du R2
Code
a<-kmeans(D,3)a$betweenss/a$totss # la valeur du R2
[1] 0.8516484
La fonction kmeans(x, centers, iter.max = 10, nstart = 1, algorithm = c("Hartigan-Wong", "Lloyd", "Forgy","MacQueen"), trace=FALSE) propose 4 versions classiques de la méthode des K-means : la version de Lloyd puis celle de Forgy qui diffèrent sur le choix des centres initiaux, puis les versions de Mac Queen et de Hartigan & Wong qui permettent de garantir la production de K classes
Observons dans l’objet centers le nombre de centres pour lesquels aucune coordonnée n’a pu être calculée
Code
res4$centers
[,1] [,2]
1 -4.02910907 2.96498129
2 0.09842884 0.01031509
3 3.99568399 -0.08277690
4 NaN NaN
Testons la nullité de la taille des clusters
Code
res4$size
[1] 40 120 80 0
Transformons notre commande afin d’obtenir les groupes formés au bout d’une seule itération et représentons-les en associant à chaque groupe une couleur distincte.
Code
CK <- res4$centers[-4,]a <-kmeans(P, CK, algorithm ="Lloyd")a
représentez-les en associant à chaque groupe une couleur distincte.
Code
couleur <-c("blue", "red", "orange2")plot(P, asp =1, pch =19, col = couleur[a$cluster])points(a$centers, pch =8, col = couleur, cex =2)
graphiquement on remarque que 3 classes n’est pas le nombre de classe idéale pour notre base de donnée. La raison de la dimunition du nombre de classe était que : nos centres initiaux étaient mal choisis
La version de Forgy propose une amélioration en choisissant les centres de classes aléatoirement parmi les individus. Ceci limite le risque de vidage de classes. La meilleure garantie reste implémentée dans les variantes de Mac Queen et de Hartigan-Wong qui mettent à jour les centres de classes dès qu’un point change de groupe.
on reprent donc avec vieux père Forgy en choisissant 4 points aléatoirement parmi les individus
Code
b <-kmeans(P, 4, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green")plot(P, asp =1, pch =19, col = couleur[b$cluster])points(b$centers, pch =8, col = couleur, cex =2)
Stabilité des classes construites
Il est assez facile d’observer une certaine diversité comme illustré sur la figure ci-dessous (variante de Forgy)
Code
par(mfrow =c(1,3))b <-kmeans(P, 5, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green", "yellow")plot(P, asp =1, pch =19, col = couleur[b$cluster])points(b$centers, pch =8, col = couleur, cex =2)b <-kmeans(P, 5, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green","yellow")plot(P, asp =1, pch =19, col = couleur[b$cluster])points(b$centers, pch =8, col = couleur, cex =2)b <-kmeans(P, 5, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green", "yellow")plot(P, asp =1, pch =19, col = couleur[b$cluster])points(b$centers, pch =8, col = couleur, cex =2)
Afin de maximiser les chances d’identifier un partitionnement présentant la variance intragroupe la plus faible, il est possible de réaliser un grand nombre d’essais et de conserver la partition d’inertie intraclasse minimale. C’est l’objet de l’argument nstart de la fonction kmeans.
maintenant étudions la variabilité en utilisant l’argument nstart avec une grande valeur (e.g. 100 ou 1000)
Code
par(mfrow =c(1,3))b <-kmeans(P, 5, nstart =1000, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green", "yellow")plot(P, asp =1, pch =19, col = couleur[b$cluster])points(b$centers, pch =8, col = couleur, cex =2)c <-kmeans(P, 5, nstart =1000, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green","yellow")plot(P, asp =1, pch =19, col = couleur[c$cluster])points(c$centers, pch =8, col = couleur, cex =2)d <-kmeans(P, 5, nstart =1000, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green", "yellow")plot(P, asp =1, pch =19, col = couleur[d$cluster])points(d$centers, pch =8, col = couleur, cex =2)
on observe qu’il y a pratiquement pas de variabilité dans les sorties produites ?
donc nos sortie sont stable car toutes les kmeans ont les mêmes centroïdes
Performances des variantes des kmeans
La méthode de Lloyd présente le risque de construire des classes vides. De ce point de vue, celle de Forgy, Mac Queen et Hartigan & Wong sont meilleures. Ces deux dernières présentent la particularité de recalculer le centre de classes dès qu’une classe est modifiée. Quid de leurs performances ? La méthode de Hartigan & Wong est réputée être la meilleure.
L’hypothèse d’une complexité linéaire semble-t-elle vraisemblable ?
je sais pas (vous même voyez)
Parallélisation du code
R permet de tirer profit des machines dotées d’une architecture multicœurs. Le fait de trouver un intérêt à la multiplication des essais avec la fonction kmeans nous fournit un terrain d’expérimentation des bienfaits de la parallélisation de code dans le cadre relativement simple d’une machine multicœurs.
Code
library(parallel)detectCores()X<-big[1:150,-5]T2 <-system.time( KM <-kmeans(X,50,iter.max=300,nstart=128))system.time(mclapply(rep(128/detectCores(), detectCores()), function(ess)kmeans(X, 50, iter.max =300, nstart = ess), mc.cores =detectCores())) -> T3
Source Code
---title: " K-Means Clustering"author: "TRA BI"format: html: # page-layout: custom number-sections: false toc: true toc-depth: 3 smooth-scroll: true toc-location: right code-fold: show code-tools: true highlight-style: githubtheme: dark: darkly light: flatlyexecute: debug: true warning: falsecss: style.csseditor: visualecho: true---```{r}#| echo: falselibrary(ade4)library(DT)library(ggplot2)library(plotly)library(MASS)```## Introduction à la fonction kmeansOn peut toujours trouver légitime de partager en paquets un ensemble de points même régulièrement répartis dans l'espace. Le problème est de ne pas faire d'erreurs grossières, lesquelles se voient bien en dimension 2, mais se cachent sans peine en dimension quelconqueOn rappelle que la méthode des K-means consiste à faire évoluer la constitution des K groupes d’une partition des individus en les associant au centre degroupe le plus proche et en mettant à jour ces centres de classes en fonction desnouveaux groupes constitués.La fonction `kmeans` est une routine permettant d’aborder un autre type de problème de clustering : le **nombre de classes** à former étant fixé à **K**, on cherche àcréer **K** groupes d’individus aussi **homogènes** que possible.Etant donné une partition de départ en K groupes, on détermine pour chaque groupe son centre de gravité puis on reforme les groupes en associant ensemble les points qui sont les plus proches d’un centre de gravité. La procédure estitérée jusqu’à satisfaction d’un **critère d’arrêt** (généralement la stabilisation desgroupes). Il faut bien comprendre qu’à l’issue des itérations, on espère avoir unepartition de bonne qualité, mais il n’y a aucune garantie d’optimalité globale(par rapport à l’inertie intraclasse)La fonction `kmeans` implémente le schéma des méthodes des centres mobiles et en propose plusieurs déclinaisons :##### Elle prend en entrée les points et les centresde classes initiaux```{r}D <-matrix(c(0,0,0,1,0,2,2,1,3,1,3,2,0,5,1,4,-1,4), ncol =2, byrow =TRUE)C <-matrix(c(0,4,3/2,2.4,1,4/5), ncol =2, byrow =TRUE)kmeans(D,C)```il est aisé d’observer les classes formées en jouant sur les couleursdes points :```{r}KM <-kmeans(D,C)couleur <-c("blue", "red", "orange2")plot(D, asp =1, pch =19, col = couleur[KM$cluster])points(KM$centers, pch =8, col = couleur, cex =2)```- l’object `cluster` contient l’affectationdes points aux classes et - l’objet `centers` fournit les coordonnées des centres declasses.#### Elle prend en entrée les points et le nombre de classesL’argument des centres de classes initiaux peut être remplacé par un simpleentier, le nombre de classes à former. Dans ce cas, les centres de classes initiaux sont choisis aléatoirement.le résultat est fortement liéaux points initiaux. Afin d’observer cela, reprenez les données utilisées en 2.3 etfaites plusieurs essais pour observer les variations du R2```{r} a<-kmeans(D,3)a$betweenss/a$totss # la valeur du R2```La fonction ```kmeans(x, centers, iter.max = 10, nstart = 1, algorithm = c("Hartigan-Wong", "Lloyd", "Forgy","MacQueen"), trace=FALSE)``` propose 4 versions classiques de la méthode des K-means :la version de **Lloyd** puis celle de **Forgy** qui diffèrent sur le choix des centres initiaux, puis les versions de **Mac Queen** et de **Hartigan & Wong** qui permettent de garantir la production de K classes## Le risque des centres initiaux mal choisis```{r}set.seed(11103)C1 <-mvrnorm(120, c(0,0), matrix(c(0.5,0,0,0.5),2,2))C2 <-mvrnorm(40, c(4,2), matrix(c(0.15,0,0,0.15),2,2))C3 <-mvrnorm(40, c(4,-2), matrix(c(0.15,0,0,0.15),2,2))C4 <-mvrnorm(40, c(-4,3), matrix(c(0.15,0,0,0.15),2,2))P <-rbind(C1, C2, C3, C4)CK <-matrix(c(-6,0,2,0,4,4,10,-1), ncol =2, byrow =TRUE)``````{r}#| eval: falsekmeans(P, CK)```ce jeu de centre ne nous permet pas d'avoir 4 classes```{r}res4 <-kmeans(P, CK, algorithm ="Lloyd")res4```On obtient 3 classes en sortieObservons dans l’objet `centers` le nombre de centres pour lesquels aucune coordonnée n’a pu être calculée ```{r}res4$centers```Testons la nullité de la taille des clusters```{r}res4$size```Transformons notre commande afin d’obtenir les groupes formés au bout d’uneseule itération et représentons-les en associant à chaque groupe une couleur distincte.```{r}CK <- res4$centers[-4,]a <-kmeans(P, CK, algorithm ="Lloyd")a``````{r}a$centers == CK```nous avons concervé nos centres---représentez-les en associant à chaque groupe une couleur distincte.```{r}couleur <-c("blue", "red", "orange2")plot(P, asp =1, pch =19, col = couleur[a$cluster])points(a$centers, pch =8, col = couleur, cex =2)```graphiquement on remarque que 3 classes n'est pas le nombre de classe idéale pour notre base de donnée. La raison de la dimunition du nombre de classe était que : noscentres initiaux étaient mal choisis>La version de **Forgy** propose une amélioration en choisissant les centres de classes**aléatoirement** parmi les **individus**. Ceci limite le risque de vidage de classes. La**meilleure garantie** reste implémentée dans les variantes de **Mac Queen** et de**Hartigan-Wong** qui **mettent à jour les centres de classes** dès qu’un **point change de groupe**.on reprent donc avec vieux père **Forgy** en choisissant 4 points **aléatoirement** parmi les **individus**```{r}b <-kmeans(P, 4, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green")plot(P, asp =1, pch =19, col = couleur[b$cluster])points(b$centers, pch =8, col = couleur, cex =2)```## Stabilité des classes construitesIl est assez facile d’observer une certaine diversité comme illustré surla figure ci-dessous (variante de Forgy)```{r}par(mfrow =c(1,3))b <-kmeans(P, 5, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green", "yellow")plot(P, asp =1, pch =19, col = couleur[b$cluster])points(b$centers, pch =8, col = couleur, cex =2)b <-kmeans(P, 5, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green","yellow")plot(P, asp =1, pch =19, col = couleur[b$cluster])points(b$centers, pch =8, col = couleur, cex =2)b <-kmeans(P, 5, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green", "yellow")plot(P, asp =1, pch =19, col = couleur[b$cluster])points(b$centers, pch =8, col = couleur, cex =2)```>Afin de maximiser les chances d’identifier un partitionnement présentant la variance intragroupe la plus faible, il est possible de réaliser un grand nombred’essais et de conserver la partition d’inertie intraclasse minimale. C’est l’objetde l’argument `nstart` de la fonction `kmeans.`maintenant étudions la variabilité en utilisant l’argument `nstart` avec une grandevaleur (e.g. 100 ou 1000)```{r}par(mfrow =c(1,3))b <-kmeans(P, 5, nstart =1000, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green", "yellow")plot(P, asp =1, pch =19, col = couleur[b$cluster])points(b$centers, pch =8, col = couleur, cex =2)c <-kmeans(P, 5, nstart =1000, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green","yellow")plot(P, asp =1, pch =19, col = couleur[c$cluster])points(c$centers, pch =8, col = couleur, cex =2)d <-kmeans(P, 5, nstart =1000, algorithm ="Forgy")couleur <-c("blue", "red", "orange2", "green", "yellow")plot(P, asp =1, pch =19, col = couleur[d$cluster])points(d$centers, pch =8, col = couleur, cex =2)```on observe qu'il y a pratiquement pas de variabilité dans les sorties produites ?on vérifie vite fait pour voir```{r}all((sort(b$centers)==sort(c$centers))&(sort(c$centers)==sort(d$centers)))```donc nos sortie sont stable car toutes les kmeans ont les mêmes centroïdes## Performances des variantes des kmeans>La méthode de Lloyd présente le risque de construire des classes vides. De cepoint de vue, celle de Forgy, Mac Queen et Hartigan & Wong sont meilleures.Ces deux dernières présentent la particularité de recalculer le centre de classesdès qu’une classe est modifiée. Quid de leurs performances ? La méthode deHartigan & Wong est réputée être la meilleure.```{r}big <-rbind(iris, iris, iris, iris, iris, iris, iris, iris)T <-sapply(seq(from=100,to=1000,by=100),function(n) {system.time(kmeans(big[sort(sample(1:nrow(big),n)),-5], 4, nstart =100, algorithm ="MacQueen"))})y <- T[3,]plot(seq(from=100,to=1000,by=100),y)lines(seq(from=100,to=1000,by=100),y)```L’hypothèse d’une complexité linéaire semble-t-elle vraisemblable ?je sais pas (vous même voyez)## Parallélisation du code>R permet de tirer profit des machines dotées d’une architecture multicœurs. Lefait de trouver un intérêt à la multiplication des essais avec la fonction kmeansnous fournit un terrain d’expérimentation des bienfaits de la parallélisation decode dans le cadre relativement simple d’une machine multicœurs.```{r}#| eval: falselibrary(parallel)detectCores()X<-big[1:150,-5]T2 <-system.time( KM <-kmeans(X,50,iter.max=300,nstart=128))system.time(mclapply(rep(128/detectCores(), detectCores()), function(ess)kmeans(X, 50, iter.max =300, nstart = ess), mc.cores =detectCores())) -> T3```
