¿Cómo determino k cuando se utiliza la agrupación de k-medias?
https://stackoverflow.com/questions/1793532
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
He estado estudiando sobre k-means clustering , y una cosa que no es claro es cómo elegir el valor de k. ¿Es sólo una cuestión de prueba y error, o hay más?
Solución
Puede maximizar el Criterio de Información Bayesiano (BIC):
BIC(C | X) = L(X | C) - (p / 2) * log n
donde L(X | C) es el logaritmo de la verosimilitud de la X conjunto de datos de acuerdo con C modelo, 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-medios: extiende K -means con la estimación eficiente del número de grupos " de Dan Pelleg y Andrew Moore en ICML 2000.
Otro enfoque consiste en comenzar con un valor grande para k y mantener la eliminación de los centroides (k reductor) hasta que ya no se reduce la longitud de la descripción. Ver "principio MDL para la cuantificación vectorial robusta" de Horst Bischof, Ales Leonardis, y Alexander Selb en Modelo de Análisis y Aplicaciones vol. 2, p. 59-72, 1999.
Por último, se puede empezar con un racimo, a continuación, mantener las agrupaciones de división hasta que los puntos asignados a cada grupo tienen una distribución de Gauss. En "El aprendizaje de la k en k means " (PIN 2003), Greg Hamerly y Charles Elkan muestran alguna evidencia de que esto funciona mejor que el BIC y que los BIC no penaliza la complejidad del modelo con suficiente fuerza.
Otros consejos
Básicamente, usted quiere encontrar un equilibrio entre dos variables: el número de grupos ( k ) y la varianza media de los racimos. Desea reducir al mínimo la antigua a la vez que se minimiza el último. Por supuesto, como el número de grupos aumenta, la varianza media disminuye (hasta el caso trivial de k = n y varianza = 0).
Como siempre en el análisis de datos, no hay un enfoque cierto que funciona mejor que todas las demás en todos los casos. Al final, usted tiene que utilizar su mejor juicio. Por eso, ayuda a trazar el número de grupos en contra de la varianza media (que asume que ya ha ejecutado el algoritmo para varios valores de k ). A continuación, puede utilizar el número de grupos en el codo de la curva.
Sí, usted puede encontrar el mejor número de conglomerados utilizando el método del codo, pero me pareció molesto para encontrar el valor de las agrupaciones de gráfico codo utilizando script. Se puede observar el gráfico de codo y encontrar el punto de codo a sí mismo, pero era mucho trabajo encontrarlo desde el guión.
Así que otra opción es utilizar para encontrarlo. El resultado de la silueta cumple completamente con todos resultado del método del codo en R.
Aquí `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")
Esperamos que ayude !!
Puede ser alguien principiante como yo en busca de código de ejemplo. información para silhouette_score está disponible aquí.
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)
este documento , "El aprendizaje de la k en el k- significa" de Greg Hamerly, Charles Elkan. Se utiliza una prueba de Gauss para determinar el número correcto de las agrupaciones. Además, los autores afirman que este método es mejor que el BIC que se menciona en la respuesta aceptada.
Hay algo que se llama Regla de oro. Se dice que el número de grupos se puede calcular k = (n / 2) ^ 0,5, donde N es el número total de elementos de la muestra. Puede comprobar la veracidad de esta información en el siguiente documento:
http://www.ijarcsms.com/docs/ papel / volume1 / número6 / V1I6-0015.pdf
También hay otro método llamado G-medio, donde su distribución sigue una distribución gaussiana o distribución normal. Consiste en el aumento de k hasta que todos los k grupos siguen una distribución de Gauss. Se requiere una gran cantidad de estadísticas, pero se puede hacer. Aquí está la fuente:
http: //papers.nips. cc / papel / 2526-aprendizaje-la-k-en-k-means.pdf
Espero que esto ayude!
En primer lugar construir un expansión mínima árbol de sus datos.
La eliminación de los K-1 aristas más caras divide el árbol en grupos K,
para que pueda construir el MST vez, mirada en racimo separaciones / métricas para diferentes K,
y tomar el codo de la curva.
Esto funciona sólo para solo linkage_clustering ,
pero para que sea rápido y fácil. Además, MSTs hacen buenas imágenes.
Véase, por ejemplo, bajo la trama MST
stats.stackexchange software de visualización para la agrupación de .
Si utiliza MATLAB, desde cualquier versión 2013b, es decir, se puede hacer uso de la función de evalclusters para averiguar cuál debería ser la k óptima para un determinado conjunto de datos.
Esta función le permite elegir de entre los algoritmos de agrupamiento 3 -. kmeans, linkage y gmdistribution
También le permite elegir de entre los criterios de evaluación de agrupamiento 4 -. CalinskiHarabasz, DaviesBouldin, gap y silhouette
Me sorprende que nadie ha mencionado este excelente artículo: http://www.ee.columbia.edu/~dpwe/papers /PhamDN05-kmeans.pdf
Después de seguir varias otras sugerencias que finalmente se encontró con este artículo al leer este blog: https: // datasciencelab. wordpress.com/2014/01/21/selection-of-k-in-k-means-clustering-reloaded/
Después de que he implementado en Scala, una aplicación que por mis casos de uso proporciona muy buenos resultados. Aquí de 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]]
}
Mi idea es utilizar Silueta Coeficiente para encontrar el número de clúster óptimo ( K). Detalles explicación es aquí .
Asumiendo que tiene una matriz de datos de llamadas DATA, puede realizar la partición de alrededor medoids con la estimación del número de grupos (por análisis de la 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
Una respuesta posible es utilizar Meta heurístico como Algoritmo Algoritmo Genético para encontrar k. Así de simple. puede utilizar K aleatorio (en algún rango) y evaluar la función de ajuste del algoritmo genético con un poco de Measurment como la silueta Encuentra y mejor base K en función 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})
Otro enfoque está utilizando Self Organizing Maps (SOP) para encontrar el número óptimo de las agrupaciones. El SOM (Self-Organizing Map) es un neuronal no supervisada metodología de red, que necesita sólo la entrada se utiliza para clustering para la resolución de problemas. Este enfoque se utiliza en un artículo sobre la segmentación de clientes.
La referencia del documento es
Abdellah Amina et al., Segmentación de clientes de modelo en el comercio electrónico Utilizando La agrupación de Técnicas y LRFM Modelo: el caso de tiendas en línea en Marruecos, Academia Mundial de Ciencias, Ingeniería y Tecnología Revista Internacional de Informática e Ingeniería de la Información Vol: 9, nº 8, 2015, 1999-2010
Si no conoce los números de los grupos k para proporcionar como parámetro de k-medias por lo que hay cuatro maneras de encontrar que de forma automática:
-
G-medios algortithm: descubre el número de grupos automáticamente utilizando una prueba estadística para decidir si se divide un centro de k-medias en dos. Este algoritmo toma un enfoque jerárquico para detectar el número de grupos, sobre la base de una prueba estadística para la hipótesis de que un subconjunto de datos sigue una distribución gaussiana (función continua que se aproxima a la distribución exacta binomial de eventos), y si no se divide el clúster . Se inicia con un pequeño número de centros, por ejemplo uno de clúster sólo (k = 1), entonces el algoritmo de la divide en dos centros (k = 2) y se divide cada uno de estos dos centros de nuevo (k = 4), que tiene cuatro centros en total. Si G-medios no acepta estos cuatro centros entonces la respuesta es el paso anterior: dos centros en este caso (k = 2). Este es el número de grupos el conjunto de datos se divide en. G-means es muy útil cuando usted no tiene una estimación del número de grupos que obtendrá después de agrupar las instancias. Tenga en cuenta que una opción inconveniente para el parámetro "k" que podría dar resultados erróneos. La versión paralela de g-medio se llama p-medios . G-significa fuentes: fuente 1 fuente de 2 fuente 3
-
x-medios : un nuevo algoritmo que de manera eficiente, las búsquedas del espacio de los lugares de racimo y número de grupos para optimizar la medida del criterio de información de Akaike (AIC) Criterio de Información Bayesiano (BIC) o. Esta versión de k-medias encuentra el número k, y también acelera k-medias.
-
k-medias en línea o en tiempo real de k-medias: permite ejecutar k-medias mediante el escaneo de todos los datos de una vez y se encuentra de forma automática el número óptimo de k. Spark implementa.
-
MeanShift algoritmo : es una técnica de agrupación no paramétrico que no hace requiere un conocimiento previo del número de grupos, y no limita la forma de los racimos. objetivos de cambio de agrupamiento medias para descubrir “manchas” en una densidad uniforme de las muestras. Se trata de un algoritmo basado en el centroide, que funciona mediante la actualización de los candidatos a centroides como la media de los puntos dentro de una región dada. Estos candidatos se filtran entonces en una etapa de post-procesamiento para eliminar cerca-duplicados para formar el conjunto final de centroides. Fuentes: Source1 , source2 , source3
He utilizado la solución que encontré aquí: http://efavdb.com/mean-shift/ 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()
Hola voy a hacer que sea sencillo y directo para explicar, me gusta para determinar los grupos que utilizan la biblioteca 'NbClust'.
Ahora, cómo usar la función 'NbClust' para determinar el número correcto de las agrupaciones: Puede comprobar el actual proyecto en Github con los datos y las agrupaciones reales - Extensión a este algoritmo 'kmeans' también se realizó utilizando el número correcto de ' centros.
Github Proyecto Enlace: https://github.com/RutvijBhutaiya/Thailand-Customer -Engagement-Facebook
