Wie bestimme ich K, wenn ich k-Means-Clustering verwende?
https://stackoverflow.com/questions/1793532
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe darüber studiert K-Means Clustering, und eine Sache, die nicht klar ist, ist, wie Sie den Wert von k wählen. Ist es nur eine Frage von Versuch und Irrtum oder gibt es mehr?
Lösung
Sie können das Bayes'sche Informationskriterium (BIC) maximieren:
BIC(C | X) = L(X | C) - (p / 2) * log n
wo L(X | C) ist die Protokoll-Likelihood des Datensatzes X nach Modell C, p ist die Anzahl der Parameter im Modell C, und n ist die Anzahl der Punkte im Datensatz. Sehen "X-Means: Ausdehnung K-Means mit effizienter Schätzung der Anzahl der Cluster " von Dan Pelleg und Andrew Moore in ICML 2000.
Ein anderer Ansatz ist es, mit einem großen Wert für zu beginnen k und entfernen Sie weiterhin Schwerpunkte (reduzieren k), bis die Beschreibungslänge nicht mehr reduziert wird. Sehen "MDL -Prinzip für eine robuste Quantisierung der Vektor" von Horst Bischof, Ales Leonardis und Alexander Selb in Musteranalyse und Anwendungen vol. 2, p. 59-72, 1999.
Schließlich können Sie mit einem Cluster beginnen und dann Cluster weiter aufspalten, bis die zugewiesenen Punkte jedem Cluster eine Gaußsche Verteilung haben. Im "Lernen das k in k-meint" (NIPS 2003), Greg Hamerly und Charles Elkan zeigen einige Beweise dafür, dass dies besser funktioniert als BIC und BIC bestraft nicht die Komplexität des Modells stark genug.
Andere Tipps
Grundsätzlich möchten Sie ein Gleichgewicht zwischen zwei Variablen finden: die Anzahl der Cluster (k) und die durchschnittliche Varianz der Cluster. Sie möchten das erstere minimieren und gleichzeitig das letztere minimieren. Natürlich nimmt die durchschnittliche Varianz mit zunehmender Anzahl von Clustern ab (bis zum trivialen Fall von k=n und Varianz = 0).
Wie immer in der Datenanalyse gibt es keinen echten Ansatz, der in allen Fällen besser funktioniert als alle anderen. Am Ende müssen Sie Ihr bestes Urteil verwenden. Dafür hilft es, die Anzahl der Cluster gegen die durchschnittliche Varianz zu zeichnen (die davon ausgeht, dass Sie den Algorithmus bereits für mehrere Werte von ausgeführt haben k). Dann können Sie die Anzahl der Cluster am Knie der Kurve verwenden.
Ja, Sie können die beste Anzahl von Clustern mit der Ellbogenmethode finden, aber ich fand es problematisch, den Wert von Clustern aus dem Ellbogendiagramm mit Skript zu finden. Sie können das Ellbogendiagramm beobachten und den Ellbogenpunkt selbst finden, aber es war viel Arbeit, es aus dem Skript zu finden.
Eine andere Option ist also zu verwenden Silhouette -Methode es zu finden. Das Ergebnis aus der Silhouette entspricht dem Ergebnis aus der Ellbogenmethode in R.
Hier ist was ich getan habe.
#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")
Ich hoffe es hilft!!
Möglicherweise ist jemand Anfänger wie ich nach Code -Beispiel. Information für silhouette_scoreist verfügbar hier.
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)
Ansehen Dies Papier, "Lernen des k in k-means" von Greg Hamerly, Charles Elkan. Es verwendet einen Gaußschen Test, um die richtige Anzahl von Clustern zu bestimmen. Außerdem behaupten die Autoren, dass diese Methode besser ist als BIC, was in der akzeptierten Antwort erwähnt wird.
Es gibt eine sogenannte Faustregel. Es heißt, dass die Anzahl der Cluster durch k = (n/2)^0,5 berechnet werden kann, wobei n die Gesamtzahl der Elemente aus Ihrer Stichprobe ist. Sie können die Richtigkeit dieser Informationen auf dem folgenden Papier überprüfen:
http://www.ijarcsms.com/docs/paper/volume1/issue6/v1i6-0015.pdf
Es gibt auch eine andere Methode namens G-Means, bei der Ihre Verteilung einer Gaußschen Verteilung oder einer Normalverteilung folgt. Es besteht darin, K zu erhöhen, bis alle Ihre K -Gruppen einer Gaußschen Verteilung folgen. Es erfordert viele Statistiken, kann aber erledigt werden. Hier ist die Quelle:
http://papers.nips.cc/paper/2526-learning-the-k-in-k-means.pdf
Ich hoffe das hilft!
Zuerst bauen a Minimum Spanning Tree Ihrer Daten. Das Entfernen der k-1-teuersten Kanten spaltet den Baum in K-Cluster.
So können Sie den MST einmal bauen, Clusterabstand / Metriken für verschiedene K ansehen und das Knie der Kurve nehmen.
Dies funktioniert nur für Single-Linkage_ClusteringAber dafür ist es schnell und einfach. Außerdem machen MSTs gute Grafik.
Siehe zum Beispiel das MST -Diagramm unterSTATS.Stackexchange Visualisierungssoftware zum Clustering.
Wenn Sie Matlab verwenden, können Sie die Funktion verwenden evalclusters Um herauszufinden, was das Optimal ist k für einen bestimmten Datensatz sein.
Mit dieser Funktion können Sie zwischen 3 Clustering -Algorithmen auswählen - kmeans, linkage und gmdistribution.
Außerdem können Sie aus 4 Clustering -Bewertungskriterien auswählen - CalinskiHarabasz, DaviesBouldin, gap und silhouette.
Ich bin überrascht, dass niemand diesen hervorragenden Artikel erwähnt hat:http://www.ee.columbia.edu/~dpwe/papers/phamdn05-kmeans.pdf
Nachdem ich einige andere Vorschläge befolgt hatte, stieß ich beim Lesen dieses Blogs endlich auf diesen Artikel:https://datasciencelab.wordpress.com/2014/01/21/Selection-of-k-in-k-means-clustering-reloaded/
Danach habe ich es in Scala implementiert, eine Implementierung, die für meine Anwendungsfälle wirklich gute Ergebnisse liefert. Hier ist 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]]
}
Meine Idee ist zu verwenden Silhouette -Koeffizient um die optimale Clusternummer (k) zu finden. Details Erläuterung ist hier.
Angenommen, Sie haben eine Matrix von Daten, die aufgerufen werden DATA, Sie können eine Partitionierung von Medoiden mit Schätzung der Anzahl der Cluster (durch Silhouette -Analyse) wie folgt durchführen:
library(fpc)
maxk <- 20 # arbitrary here, you can set this to whatever you like
estimatedK <- pamk(dist(DATA), krange=1:maxk)$nc
Eine mögliche Antwort besteht darin, den meta -heuristischen Algorithmus wie genetischer Algorithmus zu verwenden, um k zu finden. Das ist einfach. Sie können Random K (in einem bestimmten Bereich) verwenden und die Anpassungsfunktion des genetischen Algorithmus mit einer gewissen Messung wie Silhouette bewerten und die beste K -Basis für die Passform finden.
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})
Ein anderer Ansatz ist die Verwendung von Self Organizing Maps (SOP), um eine optimale Anzahl von Clustern zu finden. Die SOM (selbstorganisierende Karte) ist eine unbeaufsichtigte Methodik für neuronale Netzwerke, die nur die Eingabe benötigt, um die Problemlösung zu gruppieren. Dieser Ansatz wird in einem Papier zur Kundensegmentierung verwendet.
Die Referenz des Papiers ist
Abdellah Amine et al., Kundensegmentierungsmodell im E-Commerce unter Verwendung von Clustering-Techniken und LRFM-Modell: Der Fall von Online-Stores in Marokko, World Academy of Science, Engineering und Technology International Journal of Computer and Information Engineering Vol: 9, Nr.: 8 , 2015, 1999 - 2010
Wenn Sie die Anzahl der Cluster K nicht kennen, um K-Means als Parameter zu liefern, gibt es vier Möglichkeiten, es automatisch zu finden:
G-Means-Algortithmus: Es entdeckt die Anzahl der Cluster automatisch einen statistischen Test, um zu entscheiden, ob ein K-Means-Zentrum in zwei Teile teilnehmen soll. Dieser Algorithmus verfolgt einen hierarchischen Ansatz, um die Anzahl der Cluster zu erkennen, basierend auf einem statistischen Test für die Hypothese, dass eine Untergruppe von Daten einer Gaußschen Verteilung folgt (kontinuierliche Funktion, die sich der genauen Binomialverteilung der Ereignisse annähert), und wenn nicht, spaltet er den Cluster auf . Es beginnt mit einer kleinen Anzahl von Zentren, beispielsweise nur ein Cluster (k = 1), dann teilt der Algorithmus ihn in zwei Zentren (k = 2) und teilt jede dieser beiden Zentren erneut (k = 4) mit vier Zentren in gesamt. Wenn G-Means diese vier Zentren nicht akzeptiert, ist die Antwort der vorherige Schritt: zwei Zentren in diesem Fall (k = 2). Dies ist die Anzahl der Cluster, in die Ihr Datensatz unterteilt wird. G-Means ist sehr nützlich, wenn Sie keine Schätzung der Anzahl der Cluster haben, die Sie nach der Gruppierung Ihrer Instanzen erhalten. Beachten Sie, dass eine unbequeme Wahl für den Parameter "K" Ihnen falsche Ergebnisse liefert. Die parallele Version von G-Means heißt P-Means. G-Means Quellen:Quelle 1 Quelle 2 Quelle 3
X-Means: Ein neuer Algorithmus, der effizient den Raum der Cluster -Standorte und der Anzahl der Cluster sucht, um das Bayes'sche Informationskriterium (BIC) oder das Akaike -Informationskriterium (AIC) zu optimieren. Diese Version von K-Means findet die Nummer k und beschleunigt auch K-Means.
Online-K-Mittel- oder Streaming-K-Mittel: Es ermöglicht es, K-Means auszuführen, indem die gesamten Daten einmal gescannt werden und die optimale Anzahl von k automatisch findet. Spark implementiert es.
Meanshift -Algorithmus: Es handelt sich um eine nichtparametrische Clustering -Technik, die keine Vorkenntnisse über die Anzahl der Cluster erfordert und die Form der Cluster nicht beschränkt. Das mittlere Verschiebungsclustering zielt darauf ab, „Blobs“ in einer glatten Probendichte zu entdecken. Es handelt sich um einen zentroidbasierten Algorithmus, der die Kandidaten für Zentroids als Mittelwert der Punkte innerhalb einer bestimmten Region aktualisiert. Diese Kandidaten werden dann in einer Nachbearbeitungsstufe filtriert, um nahezu Duplikate zu eliminieren, um den endgültigen Satz von Zentroiden zu bilden. Quellen: Quelle1, Quelle2, Quelle3
Ich habe die Lösung verwendet, die ich hier gefunden habe: http://efavdb.com/mean-shift/ Und es hat sehr gut für mich funktioniert:
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()
Hallo, ich werde es einfach und direkt machen, um zu erklären. Ich möchte Cluster mithilfe der NBCLUST -Bibliothek bestimmen.
So verwenden Sie nun die Funktion "NBCLUST", um die richtige Anzahl von Clustern zu bestimmen: Sie können das tatsächliche Projekt in GitHub mit tatsächlichen Daten und Clustern überprüfen - Erweiterung auf diesen "Kmeans" -Algorithmus, der auch mit der richtigen Anzahl von "Zentren" durchgeführt wird.
Github -Projektlink: https://github.com/rutvijbhutaiya/thailand-customer-engagement-facebebook
