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

142

J'ai étudié le clustering k-means , et une chose qui n'est pas claire est la façon dont vous choisissez la valeur de k. Est-ce juste une question d'essais et d'erreurs, ou y a-t-il autre chose?

Jason Baker
la source
34
Ah ah ... C'est vraiment la question (à propos de k-mean).
mjv
pouvez-vous partager le code de la fonction L (log de vraisemblance)? Étant donné un centre en X, Y et des points en (x (i = 1,2,3,4, ..., n), y (i = 1,2,3,4, .., n)), comment est-ce que j'obtiens L?
7
un lien vers l'article Wikipedia sur le sujet: en.wikipedia.org/wiki/…
Amro
11
J'ai répondu à une question similaire avec une demi-douzaine de méthodes (en utilisant R) ici: stackoverflow.com/a/15376462/1036500
Ben

Réponses:

142

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

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

L(X | C)est le log-vraisemblance de l'ensemble de données Xselon le modèle C, pest le nombre de paramètres dans le modèle Cet nest le nombre de points dans l'ensemble de données. Voir "X-means: étendre K -means avec une estimation efficace du nombre de clusters" par Dan Pelleg et Andrew Moore dans ICML 2000.

Une autre approche consiste à commencer par une valeur élevée pour ket à continuer à supprimer les centres de gravité (réduction de k) jusqu'à ce que la longueur de la description ne soit plus réduite. Voir «Principe MDL pour la quantification vectorielle robuste» par Horst Bischof, Ales Leonardis et Alexander Selb dans Pattern Analysis and Applications vol. 2, p. 59-72, 1999.

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

Vebjorn Ljosa
la source
Très bonne réponse! Pour X-Means, savez-vous si le score BIC global n: = k * 2 (k clusters, chaque cluster modélisé par Gaussian avec des paramètres de moyenne / variance). De plus, si vous déterminez le BIC "parent"> "2 enfants", feriez-vous de nouveau fractionner ce cluster lors de la prochaine itération?
Budric
2
@Budric, ces questions devraient probablement être séparées, et peut-être sur stats.stackexchange.com.
Vebjorn Ljosa
37

Fondamentalement, vous souhaitez trouver un équilibre entre deux variables: le nombre de clusters ( k ) et la variance moyenne des clusters. Vous voulez minimiser le premier tout en minimisant le second. Bien sûr, à mesure que le nombre de grappes augmente, la variance moyenne diminue (jusqu'au cas trivial de k = n et de variance = 0).

Comme toujours dans l'analyse des données, il n'y a pas une seule vraie approche 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 par rapport à 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.

Jan Krüger
la source
24

Oui, vous pouvez trouver le meilleur nombre de clusters à l'aide de la méthode Elbow, mais j'ai trouvé difficile de trouver la valeur des clusters à partir d'un graphique de coude à l'aide d'un script. Vous pouvez observer le graphique du coude et trouver le point du coude vous-même, mais il a fallu beaucoup de travail pour le trouver à partir du script.

Une autre option consiste donc à utiliser la méthode Silhouette pour le trouver. Le résultat de Silhouette est entièrement 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 aide!!

Udeep Shakya
la source
2
Il suffit d'ajouter un lien vers le didacticiel d'analyse de silhouette pour les utilisateurs de python scikit-learn.org/stable/auto_examples/cluster
Chaitanya Shivade
10

Peut-être quelqu'un de débutant comme moi à la recherche d'un exemple de code. des informations pour silhouette_score sont disponibles ici.

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score

range_n_clusters = [2, 3, 4]            # clusters range you want to select
dataToFit = [[12,23],[112,46],[45,23]]  # sample data
best_clusters = 0                       # best cluster number which you will get
previous_silh_avg = 0.0

for n_clusters in range_n_clusters:
    clusterer = KMeans(n_clusters=n_clusters)
    cluster_labels = clusterer.fit_predict(dataToFit)
    silhouette_avg = silhouette_score(dataToFit, cluster_labels)
    if silhouette_avg > previous_silh_avg:
        previous_silh_avg = silhouette_avg
        best_clusters = n_clusters

# Final Kmeans for best_clusters
kmeans = KMeans(n_clusters=best_clusters, random_state=0).fit(dataToFit)
bhargav patel
la source
9

Regardez cet article, "Apprendre le k en k-signifie" par Greg Hamerly, Charles Elkan. Il utilise un test gaussien pour déterminer le bon nombre de clusters. En outre, les auteurs affirment que cette méthode est meilleure que le BIC qui est mentionné dans la réponse acceptée.

Autonome
la source
7

Il y a quelque chose qui s'appelle Rule of Thumb. Il dit que le nombre de clusters peut être calculé par

k = (n/2)^0.5

où n est le nombre total d'éléments de votre échantillon. Vous pouvez vérifier la véracité de ces informations sur le papier suivant:

http://www.ijarcsms.com/docs/paper/volume1/issue6/V1I6-0015.pdf

Il existe également une autre méthode appelée G-means, où votre distribution suit une distribution gaussienne ou une distribution normale. Il consiste à augmenter k jusqu'à ce que tous vos k groupes suivent une distribution gaussienne. Cela nécessite beaucoup de statistiques mais peut être fait. Voici la source:

http://papers.nips.cc/paper/2526-learning-the-k-in-k-means.pdf

J'espère que ça aide!

Arthur Busqueiro
la source
3

Créez d'abord un arbre couvrant minimum de vos données. La suppression des arêtes les plus chères de K-1 divise l'arbre en K clusters,
vous pouvez donc construire le MST une fois, regarder les espacements / métriques des cluster pour divers K et prendre le genou de la courbe.

Cela ne fonctionne que pour Single-linkage_clustering , mais pour cela, c'est rapide et facile. De plus, les MST font de bons visuels.
Voir par exemple le tracé MST sous le logiciel de visualisation stats.stackexchange pour le clustering .

denis
la source
3

Je suis surpris que personne n'ait mentionné cet excellent article: http://www.ee.columbia.edu/~dpwe/papers/PhamDN05-kmeans.pdf

Après avoir suivi plusieurs autres suggestions, je suis finalement tombé sur cet article en lisant ce blog: https://datasciencelab.wordpress.com/2014/01/21/selection-of-k-in-k-means-clustering-reloaded/

Après cela, je l'ai implémenté dans Scala, une implémentation qui, pour mes cas d'utilisation, donne de très bons résultats. Voici le code:

import breeze.linalg.DenseVector
import Kmeans.{Features, _}
import nak.cluster.{Kmeans => NakKmeans}

import scala.collection.immutable.IndexedSeq
import scala.collection.mutable.ListBuffer

/*
https://datasciencelab.wordpress.com/2014/01/21/selection-of-k-in-k-means-clustering-reloaded/
 */
class Kmeans(features: Features) {
  def fkAlphaDispersionCentroids(k: Int, dispersionOfKMinus1: Double = 0d, alphaOfKMinus1: Double = 1d): (Double, Double, Double, Features) = {
    if (1 == k || 0d == dispersionOfKMinus1) (1d, 1d, 1d, Vector.empty)
    else {
      val featureDimensions = features.headOption.map(_.size).getOrElse(1)
      val (dispersion, centroids: Features) = new NakKmeans[DenseVector[Double]](features).run(k)
      val alpha =
        if (2 == k) 1d - 3d / (4d * featureDimensions)
        else alphaOfKMinus1 + (1d - alphaOfKMinus1) / 6d
      val fk = dispersion / (alpha * dispersionOfKMinus1)
      (fk, alpha, dispersion, centroids)
    }
  }

  def fks(maxK: Int = maxK): List[(Double, Double, Double, Features)] = {
    val fadcs = ListBuffer[(Double, Double, Double, Features)](fkAlphaDispersionCentroids(1))
    var k = 2
    while (k <= maxK) {
      val (fk, alpha, dispersion, features) = fadcs(k - 2)
      fadcs += fkAlphaDispersionCentroids(k, dispersion, alpha)
      k += 1
    }
    fadcs.toList
  }

  def detK: (Double, Features) = {
    val vals = fks().minBy(_._1)
    (vals._3, vals._4)
  }
}

object Kmeans {
  val maxK = 10
  type Features = IndexedSeq[DenseVector[Double]]
}
eirirlar
la source
Implémenté dans scala 2.11.7 avec brise 0.12 et nak 1.3
eirirlar
Salut @eirirlar J'essaie d'implémenter le même code avec Python - mais je n'ai pas pu suivre le code du site Web. Voir mon message: stackoverflow.com/questions/36729826/python-k-means-clustering
piccolo
@ImranRashid Désolé, je n'ai testé qu'avec 2 dimensions, et je ne suis pas un expert Python.
eirirlar
3

Si vous utilisez MATLAB, n'importe quelle version depuis 2013b c'est-à-dire, vous pouvez utiliser la fonction evalclusterspour savoir ce que devrait être l'optimum kpour un ensemble de données donné.

Cette fonction vous permet de choisir parmi 3 algorithmes de clustering - kmeans, linkageetgmdistribution .

Il vous permet également de choisir parmi 4 critères d'évaluation de regroupement - CalinskiHarabasz, DaviesBouldin, gapet silhouette.

Kristada673
la source
3

Si vous ne connaissez pas les nombres de clusters k à fournir comme paramètre à k-means, il y a donc quatre façons de le trouver automatiquement:

  • Algortithme G-means: il découvre automatiquement le nombre de clusters à l'aide d'un test statistique pour décider s'il faut diviser un centre k-means en deux. Cet algorithme adopte une approche hiérarchique pour détecter le nombre de clusters, basé sur un test statistique pour l'hypothèse qu'un sous-ensemble de données suit une distribution gaussienne (fonction continue qui se rapproche de la distribution binomiale exacte des événements), et sinon il divise le cluster . Il commence par un petit nombre de centres, disons un seul cluster (k = 1), puis l'algorithme le divise en deux centres (k = 2) et divise à nouveau chacun de ces deux centres (k = 4), ayant quatre centres en total. Si G-means n'accepte pas ces quatre centres, alors la réponse est l'étape précédente: deux centres dans ce cas (k = 2). Il s'agit du nombre de clusters dans lesquels votre ensemble de données sera divisé. G-means est très utile lorsque vous ne disposez pas d'une estimation du nombre de clusters que vous obtiendrez après le regroupement de vos instances. Notez qu'un choix peu pratique pour le paramètre "k" peut vous donner des résultats erronés. La version parallèle de g-means est appeléep-signifie . G-means sources: source 1 source 2 source 3

  • x-means : un nouvel algorithme qui recherche efficacement l'espace des emplacements de cluster et le nombre de clusters pour optimiser le critère d'information bayésien (BIC) ou la mesure Akaike Information Criterion (AIC). Cette version de k-means trouve le nombre k et accélère également les k-means.

  • K-means ou Streaming k-means: il permet d'exécuter k-means en scannant une fois l'ensemble des données et il trouve automatiquement le nombre optimal de k. Spark l'implémente.

  • Algorithme MeanShift : c'est une technique de clustering non paramétrique qui ne nécessite pas de connaissance préalable du nombre de clusters, et ne contraint pas la forme des clusters. Le clustering par décalage moyen vise à découvrir des «taches» dans une densité lisse d'échantillons. Il s'agit d'un algorithme basé sur les centroïdes, qui fonctionne en mettant à jour les candidats pour que les centroïdes soient la moyenne des points dans une région donnée. Ces candidats sont ensuite filtrés dans une étape de post-traitement pour éliminer les quasi-doublons pour former l'ensemble final de centres de gravité. Sources: source1 , source2 , source3

curiosus
la source
2

J'ai utilisé la solution que j'ai trouvée ici: http://efavdb.com/mean-shift/ et cela a très bien fonctionné pour moi:

import numpy as np
from sklearn.cluster import MeanShift, estimate_bandwidth
from sklearn.datasets.samples_generator import make_blobs
import matplotlib.pyplot as plt
from itertools import cycle
from PIL import Image

#%% Generate sample data
centers = [[1, 1], [-.75, -1], [1, -1], [-3, 2]]
X, _ = make_blobs(n_samples=10000, centers=centers, cluster_std=0.6)

#%% Compute clustering with MeanShift

# The bandwidth can be automatically estimated
bandwidth = estimate_bandwidth(X, quantile=.1,
                               n_samples=500)
ms = MeanShift(bandwidth=bandwidth, bin_seeding=True)
ms.fit(X)
labels = ms.labels_
cluster_centers = ms.cluster_centers_

n_clusters_ = labels.max()+1

#%% Plot result
plt.figure(1)
plt.clf()

colors = cycle('bgrcmykbgrcmykbgrcmykbgrcmyk')
for k, col in zip(range(n_clusters_), colors):
    my_members = labels == k
    cluster_center = cluster_centers[k]
    plt.plot(X[my_members, 0], X[my_members, 1], col + '.')
    plt.plot(cluster_center[0], cluster_center[1],
             'o', markerfacecolor=col,
             markeredgecolor='k', markersize=14)
plt.title('Estimated number of clusters: %d' % n_clusters_)
plt.show()

entrez la description de l'image ici

snoob dogg
la source
1

Mon idée est d'utiliser le coefficient Silhouette pour trouver le numéro de cluster optimal (K). L'explication des détails est ici .

qmaruf
la source
1

En supposant que vous ayez une matrice de données appelée DATA, vous pouvez effectuer un partitionnement autour des médoïdes avec une estimation du nombre de clusters (par analyse de silhouette) comme ceci:

library(fpc)
maxk <- 20  # arbitrary here, you can set this to whatever you like
estimatedK <- pamk(dist(DATA), krange=1:maxk)$nc
Megatron
la source
1

Une réponse possible est d'utiliser un algorithme méta heuristique comme l'algorithme génétique pour trouver k. C'est simple. vous pouvez utiliser K aléatoire (dans une certaine plage) et évaluer la fonction d'ajustement de l'algorithme génétique avec des mesures comme Silhouette et trouver la meilleure base K sur la fonction d'ajustement.

https://en.wikipedia.org/wiki/Silhouette_(clustering)

Masoud
la source
1
km=[]
for i in range(num_data.shape[1]):
    kmeans = KMeans(n_clusters=ncluster[i])#we take number of cluster bandwidth theory
    ndata=num_data[[i]].dropna()
    ndata['labels']=kmeans.fit_predict(ndata.values)
    cluster=ndata
    co=cluster.groupby(['labels'])[cluster.columns[0]].count()#count for frequency
    me=cluster.groupby(['labels'])[cluster.columns[0]].median()#median
    ma=cluster.groupby(['labels'])[cluster.columns[0]].max()#Maximum
    mi=cluster.groupby(['labels'])[cluster.columns[0]].min()#Minimum
    stat=pd.concat([mi,ma,me,co],axis=1)#Add all column
    stat['variable']=stat.columns[1]#Column name change
    stat.columns=['Minimum','Maximum','Median','count','variable']
    l=[]
    for j in range(ncluster[i]):
        n=[mi.loc[j],ma.loc[j]] 
        l.append(n)

    stat['Class']=l
    stat=stat.sort(['Minimum'])
    stat=stat[['variable','Class','Minimum','Maximum','Median','count']]
    if missing_num.iloc[i]>0:
        stat.loc[ncluster[i]]=0
        if stat.iloc[ncluster[i],5]==0:
            stat.iloc[ncluster[i],5]=missing_num.iloc[i]
            stat.iloc[ncluster[i],0]=stat.iloc[0,0]
    stat['Percentage']=(stat[[5]])*100/count_row#Freq PERCENTAGE
    stat['Cumulative Percentage']=stat['Percentage'].cumsum()
    km.append(stat)
cluster=pd.concat(km,axis=0)## see documentation for more info
cluster=cluster.round({'Minimum': 2, 'Maximum': 2,'Median':2,'Percentage':2,'Cumulative Percentage':2})
sumit
la source
vous sélectionnez les données et la bibliothèque ajouter et vous copiez km = [] dans le pourcentage ': 2}) en dernier et exécutez votre python et voyez
sumit
Bienvenue dans Stack Overflow! Bien que ce code puisse aider à résoudre le problème, il n'explique pas pourquoi et / ou comment il répond à la question. Fournir ce contexte supplémentaire améliorerait considérablement sa valeur éducative à long terme. Veuillez modifier votre réponse pour ajouter une explication, y compris les limites et les hypothèses applicables.
Toby Speight
1

Une autre approche consiste à utiliser des cartes auto-organisées (SOP) pour trouver le nombre optimal de clusters. Le SOM (Self-Organizing Map) est une méthodologie de réseau neuronal non supervisé, qui n'a besoin que de l'entrée est utilisée pour le clustering pour la résolution de problèmes. Cette approche est utilisée dans un article sur la segmentation des clients.

La référence de l'article est

Abdellah Amine et al., Customer Segmentation Model in E-commerce Using Clustering Techniques and LRFM Model: The Case of Online Stores in Morocco, World Academy of Science, Engineering and Technology International Journal of Computer and Information Engineering Vol: 9, No: 8 , 2015, 1999 - 2010

boyaronur
la source
0

Salut, je vais le rendre simple et direct à expliquer, j'aime déterminer les clusters en utilisant la bibliothèque 'NbClust'.

Maintenant, comment utiliser la fonction 'NbClust' pour déterminer le bon nombre de clusters: Vous pouvez vérifier le projet réel dans Github avec des données et des clusters réels - Extension de cet algorithme 'kmeans' également effectuée en utilisant le bon nombre de 'centres'.

Lien du projet Github: https://github.com/RutvijBhutaiya/Thailand-Customer-Engagement-Facebook

Rutvij
la source
Au lieu d'ajouter le lien github, pouvez-vous ajouter quelques lignes de code clés qui peuvent aider les autres même si votre code n'est pas accessible?
Giulio Caccin
0

Vous pouvez choisir le nombre de clusters en inspectant visuellement vos points de données, mais vous vous rendrez vite compte qu'il y a beaucoup d'ambiguïté dans ce processus pour tous sauf les ensembles de données les plus simples. Ce n'est pas toujours mauvais, car vous faites un apprentissage non supervisé et il y a une certaine subjectivité inhérente au processus d'étiquetage. Ici, avoir une expérience antérieure avec ce problème particulier ou quelque chose de similaire vous aidera à choisir la bonne valeur.

Si vous voulez des conseils sur le nombre de clusters à utiliser, vous pouvez appliquer la méthode Elbow:

Tout d'abord, calculez la somme de l'erreur quadratique (SSE) pour certaines valeurs de k (par exemple 2, 4, 6, 8, etc.). Le SSE est défini comme la somme de la distance au carré entre chaque membre du cluster et son centre de gravité. Mathématiquement:

SSE = ∑Ki = 1∑x∈cidiste (x, ci) 2

Si vous tracez k par rapport au SSE, vous verrez que l'erreur diminue à mesure que k devient plus grand; en effet, lorsque le nombre de clusters augmente, ils doivent être plus petits, de sorte que la distorsion est également plus faible. L'idée de la méthode du coude est de choisir le k auquel l'ESS diminue brusquement. Cela produit un "effet de coude" dans le graphique, comme vous pouvez le voir dans l'image suivante:

entrez la description de l'image ici

Dans ce cas, k = 6 est la valeur que la méthode Elbow a sélectionnée. Tenez compte du fait que la méthode Elbow est une heuristique et qu'en tant que telle, elle peut ou non fonctionner correctement dans votre cas particulier. Parfois, il y a plus d'un coude ou pas de coude du tout. Dans ces situations, vous finissez généralement par calculer le meilleur k en évaluant les performances de k-means dans le contexte du problème de clustering particulier que vous essayez de résoudre.

Faisal Shahbaz
la source
0

J'ai travaillé sur un package Python à genoux (algorithme Kneedle). Il trouve le numéro de cluster dynamiquement comme le point où la courbe commence à s'aplatir. Étant donné un ensemble de valeurs x et y, genou retournera le point de coude de la fonction. Le point de coude est le point de courbure maximale. Voici l'exemple de code.

y = [7342.1301373073857, 6881.7109460930769, 6531.1657905495022,
6356,2255554679778, 6209,8382535595829, 6094,9052166741121, 5980,0191582610196, 5880,1869867848218, 5779,8957906367368, 5691,1879324562778, 5617,5153566271356, 5532,2613232619951, 5467,352265375117, 5395,4493783888756, 5345,3459908298091, 5290,6769823693812, 5243,5271656371888, 5207,2501206569532, 5164,9617535255456]

x = intervalle (1, len (y) +1)

depuis l'importation à genoux KneeLocator kn = KneeLocator (x, y, courbe = 'convexe', direction = 'décroissante')

imprimer (kn.knee)

madhuri M
la source
Veuillez ajouter une explication à votre réponse afin que d'autres puissent en tirer des leçons
Nico Haase