Comment déterminer k lors de l'utilisation du clustering k-means ?

Question

J'ai étudié clustering k-means Le choix de la valeur de k n'est pas clair. S'agit-il simplement d'une question d'essais et d'erreurs, ou y a-t-il autre chose à faire ?

Answer 1

Vous pouvez maximiser le critère d'information bayésien (BIC) :

BIC(C | X) = L(X | C) - (p / 2) * log n

donde L(X | C) est la log-vraisemblance de l'ensemble de données X selon le modèle C , p est le nombre de paramètres du modèle C y n est le nombre de points dans l'ensemble de données. Voir "X-means : extension K -moyens avec estimation efficace du nombre de clusters". par Dan Pelleg et Andrew Moore à l'ICML 2000.

Une autre approche consiste à commencer avec une grande valeur pour k et continuez à supprimer des centroïdes (en réduisant k) jusqu'à ce que cela ne réduise plus la longueur de la description. Voir "Principe MDL pour une quantification robuste des vecteurs". par Horst Bischof, Ales Leonardis, et Alexander Selb en Analyse de motifs et applications vol. 2, p. 59-72, 1999.

Enfin, vous pouvez commencer avec un seul cluster, puis continuer à diviser les clusters jusqu'à ce que les points attribués à chaque cluster aient une distribution gaussienne. Dans "Apprendre le k sur k -moyens" (NIPS 2003), Greg Hamerly et Charles Elkan montrent que cela fonctionne mieux que le BIC, et que le BIC ne pénalise pas assez fortement la complexité du modèle.

Answer 2

Fondamentalement, vous voulez trouver un équilibre entre deux variables : le nombre de clusters ( k ) et la variance moyenne des clusters. Vous voulez minimiser la première tout en minimisant également la seconde. Bien sûr, lorsque le nombre de clusters augmente, la variance moyenne diminue (jusqu'au cas trivial de k \= n et variance=0).

Comme toujours en matière d'analyse de données, il n'existe pas d'approche unique qui fonctionne mieux que toutes les autres dans tous les cas. En fin de compte, vous devez utiliser votre propre jugement. Pour cela, il est utile de tracer le nombre de clusters en fonction de la variance moyenne (ce qui suppose que vous avez déjà exécuté l'algorithme pour plusieurs valeurs de k ). Ensuite, vous pouvez utiliser le nombre de clusters au genou de la courbe.

Answer 3

Oui, vous pouvez trouver le meilleur nombre de clusters en utilisant la méthode Elbow, mais j'ai trouvé difficile de trouver la valeur des clusters à partir du graphique elbow en utilisant script. Vous pouvez observer le graphique du coude et trouver le point du coude vous-même, mais c'était beaucoup de travail de le trouver à partir de script.

Une autre option consiste donc à utiliser Méthode de la silhouette pour le trouver. Le résultat de Silhouette est tout à fait conforme au résultat de la méthode Elbow dans R.

Voici ce que j'ai fait.

#Dataset for Clustering
n = 150
g = 6 
set.seed(g)
d <- data.frame(x = unlist(lapply(1:g, function(i) rnorm(n/g, runif(1)*i^2))), 
                y = unlist(lapply(1:g, function(i) rnorm(n/g, runif(1)*i^2))))
mydata<-d
#Plot 3X2 plots
attach(mtcars)
par(mfrow=c(3,2))

#Plot the original dataset
plot(mydata$x,mydata$y,main="Original Dataset")

#Scree plot to deterine the number of clusters
wss <- (nrow(mydata)-1)*sum(apply(mydata,2,var))
  for (i in 2:15) {
    wss[i] <- sum(kmeans(mydata,centers=i)$withinss)
}   
plot(1:15, wss, type="b", xlab="Number of Clusters",ylab="Within groups sum of squares")

# Ward Hierarchical Clustering
d <- dist(mydata, method = "euclidean") # distance matrix
fit <- hclust(d, method="ward") 
plot(fit) # display dendogram
groups <- cutree(fit, k=5) # cut tree into 5 clusters
# draw dendogram with red borders around the 5 clusters 
rect.hclust(fit, k=5, border="red")

#Silhouette analysis for determining the number of clusters
library(fpc)
asw <- numeric(20)
for (k in 2:20)
  asw[[k]] <- pam(mydata, k) $ silinfo $ avg.width
k.best <- which.max(asw)

cat("silhouette-optimal number of clusters:", k.best, "\n")
plot(pam(d, k.best))

# K-Means Cluster Analysis
fit <- kmeans(mydata,k.best)
mydata 
# get cluster means 
aggregate(mydata,by=list(fit$cluster),FUN=mean)
# append cluster assignment
mydata <- data.frame(mydata, clusterid=fit$cluster)
plot(mydata$x,mydata$y, col = fit$cluster, main="K-means Clustering results")

J'espère que ça aidera !

Answer 4

Pour le k-mean, vous pouvez regarder la statistique de l'écart.

http://blog.echen.me/2011/03/19/counting-clusters/

Answer 5

Construisez d'abord un arbre à portée minimale de vos données. En retirant les K-1 arêtes les plus coûteuses, on divise l'arbre en K clusters,
ainsi vous pouvez construire la MST une fois, regarder les espacements / métriques des clusters pour différents K, et prendre le genou de la courbe.

Cela ne fonctionne que pour Regroupement à lien unique , mais pour cela, c'est rapide et facile. De plus, les MST font de bons visuels.
Voir par exemple le graphique MST sous stats.stackexchange logiciel de visualisation pour le clustering .