Come faccio a determinare k quando si utilizza il clustering k-means?
https://stackoverflow.com/questions/1793532
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho studiato su k-means , e una cosa che non è chiaro è come si sceglie il valore di k. È solo una questione di tentativi ed errori, o c'è di più ad esso?
Soluzione
È possibile massimizzare il criterio di informazione bayesiana (BIC):
BIC(C | X) = L(X | C) - (p / 2) * log n
dove L(X | C) è la probabilità logaritmica del X set di dati secondo il modello C, p è il numero di parametri del modello C, e n è il numero di punti nell'insieme di dati.
Vedere "X-means: l'estensione K -Mezzi con efficiente stima del numero di cluster " di Dan Pelleg e Andrew Moore nel ICML 2000.
Un altro approccio è quello di iniziare con un valore elevato per k e mantenere rimozione centroidi (riducendo k) fino a che non riduce la lunghezza descrizione. Vedere "principio di MDL per robusta quantizzazione vettoriale" da Horst Bischof, Ales Leonardis, e Alexander Selb in pattern Analysis and Applications vol. 2, p. 59-72, 1999.
Infine, si può iniziare con un cluster, quindi continuare a grappoli splitting fino a quando i punti assegnati a ciascun gruppo hanno una distribuzione gaussiana. In "Imparare il k k -Mezzi " (PIN 2003), Greg Hamerly e Charles Elkan mostrano una certa evidenza che questo funziona meglio di BIC, e che BIC non penalizza la complessità del modello abbastanza forte.
Altri suggerimenti
In sostanza, si vuole trovare un equilibrio tra due variabili: il numero di cluster ( k ) e la varianza media dei cluster. Si vuole ridurre al minimo l'ex riducendo al minimo la seconda. Naturalmente, il numero di cluster aumenta, la varianza media diminuisce (fino al caso banale di k = n e varianza = 0).
Come sempre in analisi dei dati, non c'è nessuno approccio vero che funziona meglio di tutti gli altri in tutti i casi. Alla fine, è necessario utilizzare il proprio giudizio migliore. Per questo, aiuta a tracciare il numero di cluster contro la varianza media (che presuppone che sia già stato eseguito l'algoritmo per diversi valori di k ). Quindi è possibile utilizzare il numero di cluster al ginocchio della curva.
Sì, è possibile trovare il miglior numero di cluster utilizzando il metodo del gomito, ma ho trovato fastidioso per trovare il valore di cluster dal grafico gomito utilizzando script. È possibile osservare il grafico gomito e trovare il gomito punto da soli, ma è stato molto lavoro trovandolo dallo script.
Quindi, un'altra opzione è quella di utilizzare Metodo Silhouette per trovarlo. Il risultato da Silhouette completamente conformi risultato dal metodo di gomito in R.
Qui `s quello che ho fatto.
#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")
Speranza che aiuta !!
Può essere qualcuno principiante come me cerca di esempio di codice. informazioni per silhouette_score è disponibile qui.
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)
questo documento , "Imparare il k in K- significa" da Greg Hamerly, Charles Elkan. Esso utilizza un test gaussiana per determinare il giusto numero di cluster. Inoltre, gli autori sostengono che questo metodo è migliore di BIC che è menzionato nella risposta accettata.
C'è una cosa chiamata Regola generale. Si dice che il numero di cluster può essere calcolato k = (n / 2) ^ 0,5, dove n è il numero totale di elementi dal vostro campione. È possibile verificare la veridicità di queste informazioni sul seguente documento:
http://www.ijarcsms.com/docs/ carta / Volume1 / issue6 / V1I6-0015.pdf
C'è anche un altro metodo chiamato G-mezzo, dove la vostra distribuzione segue una distribuzione gaussiana, o distribuzione normale. Consiste sull'aumento k fino a quando tutti i gruppi k seguono una distribuzione gaussiana. Essa richiede un sacco di statistiche, ma può essere fatto. Qui è la fonte:
http: //papers.nips. cc / carta / 2526-apprendimento-il-k-in-k-means.pdf
Spero che questo aiuta!
In primo luogo costruire una spanning tree dei tuoi dati.
Rimozione dei K-1 spigoli più costosi divide l'albero in cluster K,
modo da poter costruire la MST una volta, guarda distanze cluster / metriche per vari K,
e prendere il ginocchio della curva.
Questo funziona solo per Single-linkage_clustering ,
ma per questo è facile e veloce. Inoltre, MST fanno buone visuali.
Si veda ad esempio la trama MST sotto
stats.stackexchange software di visualizzazione per il clustering .
Se si utilizza MATLAB, dal momento che qualsiasi versione 2013b che è, si può fare uso della funzione evalclusters per scoprire che cosa dovrebbe la k ottimale sia per un dato insieme di dati.
Questa funzione consente di scegliere tra gli algoritmi di clustering 3 -. kmeans, linkage e gmdistribution
Inoltre, consente di scegliere tra i criteri di valutazione 4 di clustering -. CalinskiHarabasz, DaviesBouldin, gap e silhouette
Sono sorpreso che nessuno ha parlato di questo eccellente articolo: http://www.ee.columbia.edu/~dpwe/papers /PhamDN05-kmeans.pdf
Dopo aver seguito diversi altri suggerimenti che ho finalmente sono imbattuto in questo articolo durante la lettura di questo blog: https: // datasciencelab. wordpress.com/2014/01/21/selection-of-k-in-k-means-clustering-reloaded/
Dopo che ho implementato in Scala, un'implementazione che per il mio uso casi forniscono risultati davvero buoni. Ecco il codice:
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]]
}
La mia idea è quella di utilizzare Silhouette Coefficiente per trovare il numero di cluster ottimale ( K). Dettagli spiegazione è qui .
Supponendo di avere una matrice di dati chiamati DATA, è possibile eseguire il partizionamento intorno medoids con stima del numero di cluster (mediante analisi silhouette) in questo modo:
library(fpc)
maxk <- 20 # arbitrary here, you can set this to whatever you like
estimatedK <- pamk(dist(DATA), krange=1:maxk)$nc
Una risposta possibile è quella di utilizzare Meta euristico Algorithm come algoritmo genetico per trovare k. E 'semplice. è possibile utilizzare K casuale (in un certo range) e valutare la funzione in forma di algoritmo genetico con alcuni measurment come Sagoma E Trovare migliore base di K sulla funzione in forma.
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})
Un altro approccio è utilizzare Self Organizing Maps (SOP) per trovare il numero ottimale di cluster. La SOM (Self-Organizing Map) è un neurale non supervisionato metodologia rete, che ha bisogno soltanto l'ingresso è utilizzato per il clustering per la soluzione dei problemi. Questo approccio utilizzato in un documento sulla segmentazione della clientela.
Il riferimento della carta è
Abdellah Amine et al., Clienti Segmentazione Modello in E-commerce Utilizzando Tecniche di clustering e LRFM Modello: il caso di negozi online in Marocco, Accademia World of Science, Engineering and Technology International Journal di Informatica e Ingegneria Vol: 9, No: 8, 2015, 1999-2010
Se non si conoscono i numeri dei cluster k per fornire come parametro K-Means così ci sono quattro modi per trovare esso automaticamente:
-
G-means algortithm: scopre il numero di cluster automaticamente utilizzando un test statistico per decidere se suddividere un centro k-means in due. Questo algoritmo richiede un approccio gerarchico per rilevare il numero di cluster, sulla base di un test statistico per l'ipotesi che un sottoinsieme di dati segue una distribuzione gaussiana (funzione continua che approssima la distribuzione binomiale esatta degli eventi), e se non si divide il cluster . Si inizia con un piccolo numero di centri, dire solo cluster (k = 1), allora l'algoritmo divide in due centri (k = 2) e divide ciascuno di questi due centri nuovamente (k = 4), aventi quattro centri totale. Se G-means non accetta questi quattro centri allora la risposta è il passo precedente: due centri in questo caso (k = 2). Questo è il numero di cluster set di dati sarà divisa in. G-means è molto utile quando non si dispone di una stima del numero di cluster si ottengono dopo il raggruppamento le istanze. Si noti che una scelta scomoda per il parametro "k" potrebbe dare risultati errati. La versione parallela g-means è chiamato p-significa . G-: fonti: sorgente 1 fonte 2 fonte 3
-
x-means : un nuovo algoritmo che in modo efficiente, cerca lo spazio delle posizioni cluster e numero di cluster per ottimizzare il criterio di informazione bayesiana (BIC) o la misura Akaike Information Criterion (AIC). Questa versione di k-means trova il numero k e accelera anche k-means.
-
k-means online o streaming k-means: permette di eseguire k-means dalla scansione dell'intero dati una volta e trova automaticamente il numero ottimale di k. Spark implementa.
-
MeanShift algoritmo : si tratta di una tecnica di clustering non parametrico che non lo fa richiedono la preventiva conoscenza del numero di cluster, e non vincolare la forma dei cluster. Significare spostamento cluster scopo di scoprire “macchie” in un liscio densità di campioni. Si tratta di un algoritmo centroide-based, che funziona aggiornando i candidati per centroidi ad essere la media dei punti all'interno di una determinata regione. Questi candidati vengono filtrati in una fase di post-elaborazione per eliminare quasi-duplicati per formare il set finale di centroidi. Fonti: source1 , sorgente2 , Sorgente Primaria3
Ho usato la soluzione che ho trovato qui: http://efavdb.com/mean-shift/ ha funzionato molto bene per me:
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()
Ciao ce la farò semplice e diretto per spiegare, mi piace per determinare i cluster che utilizzano libreria 'NbClust'.
Ora, come utilizzare la funzione 'NbClust' per determinare il giusto numero di cluster: È possibile controllare il progetto vero e proprio in Github con dati reali e cluster - Estensione a questo algoritmo 'Kmeans' anche eseguita utilizzando il giusto numero di ' centri.
Github Progetto Link: https://github.com/RutvijBhutaiya/Thailand-Customer -Engagement-Facebook
