Jak określić k przy użyciu K-means clustering?

Zasadniczo chcesz znaleźć równowagę między dwiema zmiennymi: liczbą klastrów (k) i średnią wariancją klastrów. Chcesz zminimalizować te pierwsze, jednocześnie minimalizując te drugie. Oczywiście, wraz ze wzrostem liczby klastrów, średnia wariancja maleje (do trywialnego przypadku k=N i wariancja=0).

Jak zawsze w analizie danych, nie ma jednego prawdziwego podejścia, które działa lepiej niż wszystkie inne we wszystkich przypadkach. W końcu masz aby użyć własnego najlepszego osądu. W tym celu pomaga wykreślić liczbę klastrów na podstawie średniej wariancji (co zakłada, że algorytm został już uruchomiony dla kilku wartości k ). Następnie możesz użyć liczby klastrów w kolanie krzywej.

Tak, najlepszą liczbę klastrów można znaleźć metodą Elbow, ale trudno mi było znaleźć wartość klastrów z wykresu elbow za pomocą skryptu. Możesz obserwować wykres łokcia i znaleźć punkt łokcia samodzielnie, ale znalezienie go ze skryptu było dużo pracy.

Więc inną opcją jest użyciemetody sylwetki , aby ją znaleźć. Wynik z sylwetki jest całkowicie zgodny z metodą wynik z łokcia w R.

#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")

Hope it pomaga!!

Spójrz na Ten artykuł, "Nauka k W K-oznacza" Greg Hamerly, Charles Elkan. Używa testu Gaussa do określenia odpowiedniej liczby klastrów. Ponadto autorzy twierdzą, że metoda ta jest lepsza niż BIC, o którym mowa w zaakceptowanej odpowiedzi.

Może być ktoś początkujący jak ja szukający przykładu kodu. informacje dla silhouette_score jest dostępny tutaj.

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)

Najpierw zbuduj minimum spanning tree swoich danych. Usunięcie najdroższych krawędzi K-1 dzieli drzewo na gromady K,
możesz więc zbudować MST raz, spójrz na odstępy klastra / metryki dla różnych K, i weź kolano krzywej.

To działa tylko dla Single-linkage_clustering , ale to jest szybkie i łatwe. Dodatkowo, MSTs robią dobre efekty wizualne.
Patrz na przykład wykres MST pod statystyki.oprogramowanie do wizualizacji stackexchange dla grupowanie .

Jest coś, co nazywa się regułą. Mówi, że liczbę klastrów można obliczyć przez K = (n/2)^0,5, gdzie n jest całkowitą liczbą pierwiastków z próbki. Możesz sprawdzić prawdziwość tych informacji na poniższym artykule:

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

Istnieje również inna metoda o nazwie G-oznacza, gdzie rozkład następuje po rozkładzie Gaussa lub rozkładzie normalnym. Polega na zwiększaniu k aż wszystkie grupy k podążają za rozkładem Gaussa. Wymaga to wielu statystyk, ale można to zrobić. Oto Źródło:

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

Mam nadzieję, że to pomoże!

Jeśli używasz MATLAB, dowolnej wersji od 2013b, czyli możesz użyć funkcji evalclusters, aby dowiedzieć się, jaka powinna być optymalna k dla danego zbioru danych.

Ta funkcja pozwala wybrać spośród 3 algorytmów klastrowania- kmeans, linkage i gmdistribution.

Pozwala również wybrać spośród 4 kryteriów oceny klastrów- CalinskiHarabasz, DaviesBouldin, gap i silhouette.

Dziwi mnie, że nikt nie wspomniał o tym wspaniałym artykule: http://www.ee.columbia.edu/~dpwe / papers/PhamDN05-kmeans.pdf

Po kilku innych sugestiach w końcu natknąłem się na ten artykuł podczas czytania tego bloga: https://datasciencelab.wordpress.com/2014/01/21/selection-of-k-in-k-means-clustering-reloaded/

Potem zaimplementowałem go w Scali, implementacji, która w moich przypadkach daje naprawdę dobre rezultaty. Oto kod:

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

Moim pomysłem jest użycie współczynnika sylwetki , aby znaleźć optymalną liczbę klastra(K). Wyjaśnienie szczegółów jest Tutaj .

Zakładając, że masz macierz danych o nazwie DATA, możesz wykonać podział wokół medoidów z estymacją liczby klastrów (poprzez analizę sylwetki) w następujący sposób:

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

Jedną z możliwych odpowiedzi jest użycie algorytmu Meta heurystycznego, takiego jak algorytm genetyczny, aby znaleźć K. To proste. możesz użyć losowego K (w pewnym zakresie) i ocenić funkcję dopasowania algorytmu genetycznego z pewnym pomiarem, takim jak sylwetka I znajdź najlepszą bazę K na funkcji dopasowania.

Https://en.wikipedia.org/wiki/Silhouette_

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

Innym podejściem jest użycie samoorganizujących się Map (SOP), aby znaleźć optymalną liczbę klastrów. Som (Samoorganizująca się mapa) jest nienadzorowanym neuronem metodologia sieci, która wymaga tylko wejścia jest wykorzystywana do grupowanie w celu rozwiązywania problemów. To podejście stosowane w artykule o segmentacji klientów.

Odniesienie do artykułu to

Abdellah Amine et al., Model segmentacji klientów w e-commerce z wykorzystaniem Techniki klastrowania i Model LRFM: sprawa Sklepów Internetowych w Maroko, World Academy of Science, Engineering and Technology International Journal of Computer and Information Engineering Vol: 9, No:8, 2015, 1999 - 2010

Użyłem rozwiązania, które znalazłem tutaj: http://efavdb.com/mean-shift / i bardzo dobrze mi to wyszło:

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