cluster-analysis - clustering - kmeans python 3

¿Cómo determino k cuando uso k-means clustering?

Question

He estado estudiando la agrupación en k-means , y una cosa que no está clara es cómo elegir el valor de k. ¿Es solo una cuestión de prueba y error, o hay más que eso?

Answer 1

Básicamente, desea encontrar un equilibrio entre dos variables: el número de clústeres ( k ) y la varianza promedio de los clusters. Desea minimizar lo primero mientras minimiza lo segundo. Por supuesto, a medida que aumenta el número de conglomerados, la varianza promedio disminuye (hasta el caso trivial de k = n y la varianza = 0).

Como siempre en el análisis de datos, no existe un enfoque verdadero que funcione mejor que todos los demás en todos los casos. Al final, debes usar tu propio juicio. Para eso, ayuda a trazar el número de clústeres contra la varianza promedio (que supone que ya ha ejecutado el algoritmo para varios valores de k ). Entonces puedes usar la cantidad de clústers en la rodilla de la curva.

Answer 2

Hay algo llamado Regla de oro. Dice que la cantidad de conglomerados se puede calcular por k = (n / 2) ^ 0,5, donde n es la cantidad total de elementos de tu muestra. Puede verificar la veracidad de esta información en el siguiente documento:

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

También hay otro método llamado G-means, donde su distribución sigue una Distribución Gaussiana, o Distribución Normal. Consiste en aumentar k hasta que todos tus k grupos sigan una distribución Gaussiana. Requiere muchas estadísticas, pero se puede hacer. Aquí está la fuente:

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

¡Espero que esto ayude!

Answer 3

Me sorprende que nadie haya mencionado este excelente artículo: http://www.ee.columbia.edu/~dpwe/papers/PhamDN05-kmeans.pdf

Después de seguir varias otras sugerencias, finalmente encontré este artículo mientras leía este blog: https://datasciencelab.wordpress.com/2014/01/21/selection-of-k-in-k-means-clustering-reloaded/

Después de eso lo implementé en Scala, una implementación que para mis casos de uso proporciona resultados realmente buenos. Aquí está el 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]]
}

Answer 4

Mi idea es usar Silhouette Coefficient para encontrar el número de clúster óptimo (K). La explicación de los detalles está here .

Answer 5

Mire este artículo, "Aprender k en k-means" por Greg Hamerly, Charles Elkan. Utiliza una prueba de Gauss para determinar la cantidad correcta de clústeres. Además, los autores afirman que este método es mejor que BIC, que se menciona en la respuesta aceptada.

Answer 6

Primero crea un árbol de expansión mínimo de tus datos. La eliminación de los bordes más costosos K-1 divide el árbol en K clusters,
para que pueda construir el MST una vez, mire los espaciamientos / métricas del grupo para varios K, y tome la rodilla de la curva.

Esto funciona solo para Single-linkage_clustering , pero para eso es rápido y fácil. Además, MSTs hacen buenos visuales.
Véase, por ejemplo, el gráfico MST en el software stats.stackexchange visualization para clustering .

Answer 7

Puede maximizar el Criterio de información bayesiano (BIC):

BIC(C | X) = L(X | C) - (p / 2) * log n

donde L(X | C) es la log-verosimilitud del conjunto de datos X según el modelo C , p es el número de parámetros en el modelo C , y n es el número de puntos en el conjunto de datos. Ver "X-means: extender K- medias con una estimación eficiente del número de clusters" por Dan Pelleg y Andrew Moore en ICML 2000.

Otro enfoque es comenzar con un valor grande para k y seguir eliminando centroides (reduciendo k) hasta que ya no reduzca la longitud de la descripción. Consulte "Principio de MDL para la cuantificación vectorial sólida" por Horst Bischof, Ales Leonardis y Alexander Selb en Pattern Analysis and Applications vol. 2, p. 59-72, 1999.

Finalmente, puede comenzar con un clúster y luego seguir dividiendo clústeres hasta que los puntos asignados a cada clúster tengan una distribución gaussiana. En "Aprendiendo k en k- medias" (NIPS 2003), Greg Hamerly y Charles Elkan muestran alguna evidencia de que esto funciona mejor que BIC, y que BIC no penaliza la complejidad del modelo con suficiente fuerza.

Answer 8

Puede ser alguien principiante como yo buscando un ejemplo de código. la información para silhouette_score está disponible here.

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)

Answer 9

Sí, puedes encontrar el mejor número de clusters usando el método de Elbow, pero me pareció problemático encontrar el valor de los clústers a partir del gráfico de codo usando el script. Puede observar el gráfico del codo y encontrar el punto del codo usted mismo, pero fue mucho trabajo encontrarlo desde el guión.

Entonces, otra opción es usar el en.wikipedia.org/wiki/… para encontrarlo. El resultado de Silhouette cumple completamente con el resultado del método del codo en R.

Aquí es lo que hice.

#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 eso ayude!!

Answer 10

Si utiliza MATLAB, cualquier versión desde 2013b, es decir, puede utilizar la función evalclusters para descubrir cuál debería ser la k óptima para un determinado conjunto de datos.

Esta función le permite elegir entre 3 algoritmos de clúster: kmeans , linkage y gmdistribution .

También le permite elegir entre 4 criterios de evaluación de agrupamiento: CalinskiHarabasz , DaviesBouldin , gap y silhouette .

Answer 11

Suponiendo que tiene una matriz de datos llamada DATA , puede realizar particiones alrededor de medoids con la estimación del número de clústeres (por análisis de silueta) como este:

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

Answer 12

Una respuesta posible es usar Algoritmo Meta Heurístico como Algoritmo Genético para encontrar k. Así de simple. puede usar K aleatorio (en algún rango) y evaluar la función de ajuste del Algoritmo Genético con alguna medida como Silueta y Encontrar la mejor base K en la función de ajuste.

https://en.wikipedia.org/wiki/Silhouette_(clustering)

Answer 13

Usé la solución que encontré aquí: http://efavdb.com/mean-shift/ y funcionó muy bien para mí:

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

Answer 14

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