Comment puis-je déterminer k lors de l'utilisation k-means?
https://stackoverflow.com/questions/1793532
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'étudie à propos de k-means , et une chose qui est pas clair comment vous choisissez la valeur de k. Est-ce juste une question d'essais et d'erreurs, ou est-il de plus?
La solution
Vous pouvez maximiser le critère d'information bayésien (BIC):
BIC(C | X) = L(X | C) - (p / 2) * log n
où L(X | C) est la log-vraisemblance de l'ensemble de données selon le modèle X C, p est le nombre de paramètres dans le modèle C et n est le nombre de points dans l'ensemble de données.
Voir "X-moyens: l'extension K -un moyen avec une estimation efficace du nombre de clusters " par Dan Pelleg et Andrew Moore dans ICML 2000.
Une autre approche est de commencer par une grande valeur pour k et maintenir la suppression centroïdes (réduction k) jusqu'à ce qu'il ne réduit plus la longueur de la description. Voir "principe de MDL pour le vecteur robuste quantisation" par Horst Bischof, Ales Leonardis, et Alexander Selb Analyse et applications Motif vol. 2, p. 59-72, 1999.
Enfin, vous pouvez commencer par un cluster, puis garder les clusters de fractionnement jusqu'à ce que les points attribués à chaque groupe ont une distribution gaussienne. "Apprendre k k -un moyen " (NIPS 2003), Greg Hamerly et Charles Elkan montrent des preuves que cela fonctionne mieux que BIC, et que BIC ne pénalise pas la complexité du modèle assez fort.
Autres conseils
En gros, vous voulez trouver un équilibre entre deux variables: le nombre de grappes ( k ) et la variance moyenne des grappes. Vous voulez minimiser l'ancien tout en minimisant celle-ci. Bien entendu, comme le nombre de groupes augmente, la variance moyenne diminue (jusqu'à le cas trivial de k = n et la variance = 0).
Comme toujours dans l'analyse des données, il n'y a pas une véritable approche qui fonctionne mieux que tous 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 contre 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 niveau du genou de la courbe.
Oui, vous pouvez trouver le meilleur nombre de grappes en utilisant la méthode du coude, mais je l'ai trouvé gênant pour trouver la valeur des grappes de graphique du coude en utilisant un script. Vous pouvez observer le graphique du coude et trouver le coude-vous pointer, mais il a été beaucoup de travail le trouver à partir du script.
Une autre option consiste à utiliser méthode Silhouette pour le trouver. Le résultat de Silhouette se conformer complètement avec le résultat de la méthode du coude dans l'affaire R.
Here`s ce que je faisais.
#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")
it helps !!
Peut-être quelqu'un débutant comme moi par exemple à la recherche de code. informations 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)
Regardez ce document , « Apprendre k en k- signifie » par Greg Hamerly, Charles Elkan. Il utilise un test gaussienne pour déterminer le nombre exact de groupes. En outre, les auteurs affirment que cette méthode est meilleure que BIC qui est mentionné dans la réponse acceptée.
Il y a quelque chose appelé la règle du pouce. Il 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 ces informations sur le document suivant:
http://www.ijarcsms.com/docs/ papier / volume1 / question6 / V1I6-0015.pdf
Il y a aussi une autre méthode appelée G-means, où votre distribution suit une distribution gaussienne ou distribution normale. Il consiste à augmenter k jusqu'à ce que tous les groupes k suivent une distribution gaussienne. Il exige beaucoup de statistiques, mais peut être fait. Voici la source:
http: //papers.nips. cc / papier / 2526-learning-the-k en k-means.pdf
J'espère que cela aide!
Tout d'abord construire un Spanning Tree de vos données.
Retrait des K-1 arêtes les plus chers scinde l'arbre en grappes K,
de sorte que vous pouvez construire le MST une fois, regardez espacements / paramètres différents clusters pour K,
et prendre le genou de la courbe.
Cela ne fonctionne que pour unique linkage_clustering,
mais pour cela il est rapide et facile. De plus, font de bons visuels MST.
Voir par exemple la parcelle MST sous
logiciel de visualisation stats.stackexchange pour le clustering .
Si vous utilisez Matlab, une version depuis 2013b qui est, vous pouvez utiliser la fonction evalclusters pour savoir ce que l'k optimale devrait être un ensemble de données.
Cette fonction vous permet de choisir parmi trois algorithmes de regroupement -. kmeans, linkage et gmdistribution
Il vous permet également de choisir parmi les critères d'évaluation 4 de clustering -. CalinskiHarabasz, DaviesBouldin, gap et silhouette
Je suis surpris que personne n'a mentionné cet excellent article: http://www.ee.columbia.edu/~dpwe/papers /PhamDN05-kmeans.pdf
Après avoir suivi plusieurs autres suggestions que je tombe 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 mis en œuvre dans Scala, une mise en œuvre qui, pour mon cas, l'utilisation fournissent 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]]
}
Mon idée est d'utiliser Silhouette Coefficient pour trouver le numéro de cluster optimal ( K). explication Détails est .
En supposant que vous avez une matrice de données appelées DATA, vous pouvez effectuer le partitionnement autour medoids 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 Meta Heuristique algorithme génétique comme algorithme pour trouver k. C'est simple. vous pouvez utiliser K aléatoire (dans une plage) et d'évaluer la fonction d'ajustement de l'algorithme génétique avec une measurment comme Silhouette Et Trouver la meilleure base de K sur la fonction en forme.
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 à l'aide Self Organizing Maps (SOP) pour trouver le nombre optimal de clusters. Le SOM (Self-Organizing Map) est une neurale sans supervision méthodologie du réseau, qui a besoin que l'entrée est utilisée pour le regroupement pour la résolution de problèmes. Cette approche utilisée dans un document sur la segmentation de la clientèle.
La référence du papier est
Amine Abdellah et al., Segmentation client Modèle dans le commerce électronique utilisant Techniques de clustering et LRFM Modèle: le cas de magasins en ligne au Maroc, Académie mondiale des sciences, de l'ingénierie et de la technologie Journal international de l'informatique et de génie de l'information Vol: 9, No: 8, 2015, 1999-2010
Si vous ne connaissez pas les numéros des groupes k pour fournir en tant que paramètre à k-means donc il y a quatre façons de le trouver automaticaly:
-
G moyens algortithm: il découvre le nombre de grappes automatiquement à l'aide d'un test statistique pour décider de diviser un centre k-means en deux. Cet algorithme utilise une approche hiérarchique pour détecter le nombre de grappes, sur la base d'un test statistique pour l'hypothèse selon laquelle 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, par exemple un cluster uniquement (k = 1), alors l'algorithme il se divise en deux centres (k = 2) et se divise chacun de ces deux centres à nouveau (k = 4), ayant quatre centres 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). Ceci est le nombre de grappes de votre ensemble de données sera divisé en. G-means est très utile lorsque vous ne disposez pas d'une estimation du nombre de grappes que vous obtiendrez après regroupement vos instances. Notez qu'un choix pratique pour le paramètre « k » peut vous donner des résultats erronés. La version parallèle de g-moyen est appelé p-moyens . G-sources signifie: source 1 Source 2 source 3
-
X moyens : un nouvel algorithme qui efficace, recherche dans l'espace des emplacements de cluster et le nombre de grappes pour optimiser l'Bayesian information Criterion (BIC) ou la mesure d'information Akaike (AIC). Cette version de k-means trouve le nombre k et accélère également k-means.
-
En ligne k-means ou en streaming k-means: elle permet d'exécuter k-means par balayage une fois l'ensemble des données et trouve automatiquement le nombre optimal de k. Spark implémente.
-
algorithme écart des moyennes: il est une technique de classification non paramétrique qui ne exigent une connaissance préalable du nombre de grappes, et ne limite pas la forme des grappes. le regroupement de changement moyen vise à découvrir « blobs » dans une densité lisse d'échantillons. Il est un algorithme basé barycentre, qui travaille en mettant à jour les candidats pour centroïdes d'être la moyenne des points dans une région donnée. Ces candidats sont ensuite filtrés dans une phase de post-traitement pour éliminer les doublons quasi-pour former l'ensemble final de centroïdes. Sources: source1 , source2 , source3
J'ai utilisé la solution que je trouve ici: http://efavdb.com/mean-shift/ il a travaillé très bien 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()
Salut, je vais le faire pour expliquer simple, et j'aime déterminer les clusters en utilisant la bibliothèque « NbClust ».
Maintenant, comment utiliser la fonction « NbClust » pour déterminer le nombre exact de groupes: Vous pouvez vérifier le projet réel dans Github avec des données réelles et des clusters - Extention à cet algorithme « kmeans » également réalisée en utilisant le bon nombre de ' centres.
Github Projet Lien: https://github.com/RutvijBhutaiya/Thailand-Customer -Engagement-Facebook
