Comment déterminer k lorsqu'on utilise K-signifie regroupement?

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

comme toujours dans l'analyse des données, il n'y a pas de vrai 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 aide à tracer le nombre de grappes 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 grappes au genou de la courbe.

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

donc une autre option est d'utiliser méthode de la Silhouette pour le trouver. Le résultat de la Silhouette entièrement conforme avec le résultat de la méthode du coude dans R.

voilà 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")

Espère que cela aide!!

Regardez ce papier", l'Apprentissage de la k dans k-means" par Greg Hamerly, Charles Elkan. Il utilise un test gaussien pour déterminer le bon nombre de grappes. En outre, les auteurs font valoir que cette méthode est meilleure que le BIC, qui est mentionné dans la réponse acceptée.

peut être quelqu'un de débutant comme moi qui cherche un exemple de code. information pour silhouette_score est disponible 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)

premier build a minimum spanning tree de vos données. Enlever les bords les plus chers de K-1 divise l'arbre en grappes de K,

ainsi, vous pouvez construire le MST une fois, regardez les espacements / mesures de cluster pour divers K, et prendre le genou de la courbe.

cela ne fonctionne que pour Single-linkage_clustering , mais pour cela, il est facile et rapide. En plus, les MST font de bons visuels.

Pour voir exemple la parcelle MST sous stats.stackexchange logiciel de visualisation pour le clustering .

il y a quelque chose qui s'appelle la Règle du pouce. Il est dit que le nombre de grappes 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 cette information sur le papier suivant:

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

il y a aussi une autre méthode appelée g-means, où votre distribution suit une gaussienne Distribution, ou Distribution normale. Il consiste à augmenter k jusqu'à ce que tous vos groupes K suivent une Distribution gaussienne. Il exige 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 cela aide!

si vous utilisez MATLAB, n'importe quelle version depuis 2013b c'est-à-dire, vous pouvez utiliser la fonction evalclusters pour savoir ce que devrait être l'optimal k pour un ensemble de données donné.

cette fonction vous permet de choisir parmi 3 algorithmes de regroupement - kmeans , linkage et gmdistribution .

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

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 que je l'ai mis en œuvre dans Scala, une mise en œuvre qui pour mon usage cas fournissent vraiment de 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]]
}

mon idée est d'utiliser Coefficient de Silhouette pour trouver le nombre d'amas optimal(K). Détails explication est ici .

en supposant que vous avez une matrice de données appelée DATA , vous pouvez effectuer le partitionnement autour des médoïdes avec l'estimation du nombre de grappes (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

une réponse possible est d'utiliser un algorithme heuristique méta comme un algorithme génétique pour trouver K. C'est simple. vous pouvez utiliser random K (dans une certaine gamme) et évaluer la fonction d'ajustement de L'algorithme génétique avec un certain mesure comme Silhouette Et trouver le meilleur K base sur la fonction fit.

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

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})

une autre approche consiste à utiliser des cartes Auto-Organisantes (POS) pour trouver le nombre optimal de grappes. La carte SOM (Self-Organizing Map) est une carte neuronale non supervisée. réseau de la méthodologie, qui a besoin que l'entrée est utilisée pour le clustering pour la résolution de problème. Cette approche a été utilisée dans un article sur la segmentation de la clientèle.

la référence du papier est

Abdellah Amine et al., Modèle de Segmentation de la clientèle dans le commerce électronique en utilisant Clustering Les Techniques et le modèle LRFM: le cas des boutiques en ligne au Maroc, Académie mondiale des sciences, de L'ingénierie et de la technologie Revue internationale de l'Informatique et de l'Ingénierie de l'Information Vol: 9, No:8, 2015, 1999 - 2010

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()