Como faço para determinar K ao usar o agrupamento de K-Means?
https://stackoverflow.com/questions/1793532
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho estudado sobre cluster de k-means, e uma coisa que não está clara é como você escolhe o valor de k. É apenas uma questão de tentativa e erro, ou há mais?
Solução
Você pode maximizar o critério de informação bayesiano (BIC):
BIC(C | X) = L(X | C) - (p / 2) * log n
Onde L(X | C) é a probabilidade de log do conjunto de dados X De acordo com o modelo C, p é o número de parâmetros no modelo C, e n é o número de pontos no conjunto de dados. Ver "X-Means: estendendo K-Means com estimativa eficiente do número de grupos " Por Dan Pelleg e Andrew Moore em ICML 2000.
Outra abordagem é começar com um grande valor para k e continue removendo os centróides (reduzindo K) até que não reduz mais o comprimento da descrição. Ver "Princípio da MDL para quantização robusta do vetor" Por Horst Bischof, Ales Leonardis e Alexander Selb em Análise de padrões e aplicações vol. 2, p. 59-72, 1999.
Por fim, você pode começar com um cluster e continuar dividindo os clusters até que os pontos atribuídos a cada cluster tenham uma distribuição gaussiana. Dentro "Aprendendo o k dentro k-significa" (NIPS 2003), Greg Hamerly e Charles Elkan mostram algumas evidências de que isso funciona melhor que o BIC, e que o BIC não penaliza a complexidade do modelo com força suficiente.
Outras dicas
Basicamente, você deseja encontrar um equilíbrio entre duas variáveis: o número de clusters (k) e a variação média dos clusters. Você deseja minimizar o primeiro, além de minimizar o último. Obviamente, à medida que o número de clusters aumenta, a variação média diminui (até o caso trivial de k=n e variação = 0).
Como sempre na análise de dados, não existe uma abordagem verdadeira que funcione melhor do que todos os outros em todos os casos. No final, você deve usar seu melhor julgamento. Para isso, ajuda a plotar o número de clusters contra a variação média (que assume que você já executou o algoritmo para vários valores de k). Em seguida, você pode usar o número de clusters no joelho da curva.
Sim, você pode encontrar o melhor número de clusters usando o método do cotovelo, mas achei problemático encontrar o valor dos clusters do gráfico do cotovelo usando o script. Você pode observar o gráfico do cotovelo e encontrar o cotovelo, mas foi muito trabalho encontrá -lo do script.
Então, outra opção é usar Método da silhueta Para encontrar isso. O resultado da silhueta atende completamente ao resultado do método do cotovelo em R.
Aqui está o que eu fiz.
#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")
Espero que ajude!!
Pode ser alguém iniciante como eu procurando por exemplo de código. informação para SHOUETTE_SCOREestá disponível aqui.
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)
Olhe para isto Artigo, "Aprendendo o K em K-Means", de Greg Hamerly, Charles Elkan. Ele usa um teste gaussiano para determinar o número certo de clusters. Além disso, os autores afirmam que esse método é melhor que o BIC mencionado na resposta aceita.
Há algo chamado regra geral. Diz que o número de clusters pode ser calculado por k = (n/2)^0,5, onde n é o número total de elementos da sua amostra. Você pode verificar a veracidade dessas informações sobre o seguinte artigo:
http://www.ijarcsms.com/docs/paper/volume1/issue6/v1i6-0015.pdf
Há também outro método chamado G-means, onde sua distribuição segue uma distribuição gaussiana ou distribuição normal. Consiste em aumentar K até que todos os seus K grupos sigam uma distribuição gaussiana. Requer muitas estatísticas, mas pode ser feito. Aqui está a fonte:
http://papers.nips.cc/paper/2526-learning-the-k-in-k-means.pdf
Eu espero que isso ajude!
Primeiro construa um Árvore de abrangência mínima de seus dados. Remover as bordas mais caras do K-1 divide a árvore em aglomerados K,
Assim, você pode construir o MST uma vez, observar espaçamentos / métricas de cluster para vários K e tomar o joelho da curva.
Isso funciona apenas para Single-linkage_clustering, mas para isso é rápido e fácil. Além disso, os MSTs fazem bons visuais.
Veja, por exemplo, o enredo MST emSTATS.STACKEXCHANGE Software de visualização para clustering.
Se você usa o MATLAB, qualquer versão desde 2013b, ou seja, você pode usar a função evalclusters Para descobrir o que deve ser o ideal k Seja para um determinado conjunto de dados.
Esta função permite escolher entre 3 algoritmos de agrupamento - kmeans, linkage e gmdistribution.
Ele também permite escolher entre 4 critérios de avaliação de agrupamento - CalinskiHarabasz, DaviesBouldin, gap e silhouette.
Estou surpreso que ninguém tenha mencionado este excelente artigo:http://www.ee.columbia.edu/~dpwe/papers/phamdn05-kmeans.pdf
Depois de seguir várias outras sugestões, finalmente me deparei com este artigo ao ler este blog:https://datasciencelab.wordpress.com/2014/01/21/selection-of-k-in-k-keans-clustering-reloaded/
Depois disso, implementei -o em Scala, uma implementação que, para meus casos de uso, fornece resultados realmente bons. Aqui está o código:
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]]
}
Minha ideia é usar Coeficiente de silhueta Para encontrar o número ideal de cluster (K). Detalhes a explicação é aqui.
Supondo que você tenha uma matriz de dados chamada DATA, você pode executar a partição em torno dos medóides com a estimativa de número de clusters (por análise de silhueta) como este:
library(fpc)
maxk <- 20 # arbitrary here, you can set this to whatever you like
estimatedK <- pamk(dist(DATA), krange=1:maxk)$nc
Uma resposta possível é usar o algoritmo meta -heurístico como o algoritmo genético para encontrar k. Isso é simples. Você pode usar K aleatório (em algum intervalo) e avaliar a função de ajuste do algoritmo genético com alguma medição como a silhueta e encontrar a melhor base de K base na função de ajuste.
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})
Outra abordagem é usar mapas auto -organizadores (SOP) para encontrar o número ideal de clusters. O SOM (mapa auto-organizado) é uma metodologia de rede neural não supervisionada, que precisa de apenas a entrada é usada para agrupar-se para a solução de problemas. Essa abordagem usada em um artigo sobre segmentação de clientes.
A referência do artigo é
Abdellah Amine et al., Modelo de segmentação de clientes no comércio eletrônico usando técnicas de agrupamento e modelo LRFM: o caso de lojas on-line no Marrocos, Academia Mundial de Ciência, Engenharia e Tecnologia Jornal Internacional de Computador e Engenharia de Informações Vol: 9, não: 8 , 2015, 1999 - 2010
Se você não conhece o número de clusters k para fornecer como parâmetro para K-means, então há quatro maneiras de encontrar automaticamente:
Algortitmo G-Means: descobre que o número de clusters automaticamente usando um teste estatístico para decidir se dividia um centro K em dois. Esse algoritmo adota uma abordagem hierárquica para detectar o número de clusters, com base em um teste estatístico para a hipótese de que um subconjunto de dados segue uma distribuição gaussiana (função contínua que se aproxima da distribuição binomial exata dos eventos) e, se não, divide o cluster . Começa com um pequeno número de centros, digamos apenas um cluster (k = 1), então o algoritmo o divide em dois centros (k = 2) e divide cada um desses dois centros novamente (k = 4), tendo quatro centros em centros em total. Se o G-means não aceitar esses quatro centros, a resposta será a etapa anterior: dois centros neste caso (k = 2). Este é o número de clusters em que seu conjunto de dados será dividido. O G-Means é muito útil quando você não tem uma estimativa do número de clusters que receberá depois de agrupar suas instâncias. Observe que uma opção inconveniente para o parâmetro "K" pode fornecer resultados errados. A versão paralela do g-means é chamada P-means. Fontes g-means:Fonte 1 Fonte 2 Fonte 3
X-means: Um novo algoritmo que eficientemente pesquisa no espaço de locais de cluster e número de clusters para otimizar o critério de informação bayesiano (BIC) ou a medida do critério de informação Akaike (AIC). Esta versão do K-Means encontra o número K e também acelera o K-Means.
K-means on-line ou streaming k-means: permite executar o K-Means, digitalizando todos os dados uma vez e considera automaticamente o número ideal de k. Spark implementa.
Algoritmo MeanShift: É uma técnica de cluster não paramétrica que não requer conhecimento prévio do número de clusters e não restringe a forma dos clusters. O agrupamento médio de mudança tem como objetivo descobrir “bolhas” em uma densidade suave de amostras. É um algoritmo baseado em centróide, que funciona atualizando os candidatos a centróides para ser a média dos pontos em uma determinada região. Esses candidatos são então filtrados em um estágio de pós-processamento para eliminar quase duplicatos para formar o conjunto final de centróides. Fontes: fonte1, fonte2, fonte3
Eu usei a solução que encontrei aqui: http://efavdb.com/mean-shift/ E funcionou muito bem para mim:
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()
Olá, vou simplificar e direto para explicar, gosto de determinar os clusters usando a biblioteca 'NBClust'.
Agora, como usar a função 'nbclust' para determinar o número certo de clusters: você pode verificar o projeto real no github com dados e clusters reais - a extensão desse algoritmo 'kmeans' também foi executado usando o número certo de 'centros'.
Link do projeto do Github: https://github.com/rutvijbhutaiya/thailand-customer-engagement-facebook
