使用K-均值聚类时如何确定K？

StackOverflow https://stackoverflow.com/questions/1793532

  •  22-09-2019
  •  | 
  •  

题

我一直在研究 K-均值聚类, ，一件事不清楚的是您如何选择k的值。这只是一个反复试验的问题，还是还有更多的问题？

有帮助吗？

解决方案

您可以最大化贝叶斯信息标准（BIC）：

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

在哪里 L(X | C) 是数据集的日志样本 X 根据模型 C, p 是模型中的参数数 C, ， 和 n 是数据集中的点数。看 “ X均值：扩展 k- 有效估计簇数的含量” 丹·佩莱格（Dan Pelleg）和安德鲁·摩尔（Andrew Moore）在ICML 2000中。

另一种方法是从巨大的价值开始 k 并继续删除质心（减少K），直到它不再减少描述长度为止。看 “稳健矢量定量的MDL原理” 霍斯特·比索夫（Horst Bischof），艾尔斯·伦纳迪斯（Ales Leonardis）和亚历山大·塞尔布（Alexander Selb） 模式分析和应用 卷。 2，第2页。 59-72，1999。

最后，您可以从一个群集开始，然后继续分裂簇，直到分配给每个群集的点具有高斯分布。在 “学习 k 在 k-方法” （NIPS 2003），格雷格·哈默利（Greg Hamerly）和查尔斯·埃尔坎（Charles Elkan）表明，这比BIC更好，并且BIC并未对模型的复杂性进行严厉的惩罚。

其他提示

基本上，您想在两个变量之间找到平衡：集群数（k）和集群的平均方差。您想最大程度地减少前者，同时也最大程度地减少了后者。当然，随着聚类数量的增加，平均差异会减少（直至 k=n 和方差= 0）。

与往常一样，在数据分析中，没有一种真正的方法在所有情况下都比所有其他方法都更好。最后，您必须使用自己的最佳判断。为此，它有助于绘制簇数与平均方差的数量（假设您已经运行了几个值的算法 k）。然后，您可以使用曲线膝盖处的簇数。

是的，您可以使用肘方法找到最佳数量的簇数，但是我发现使用脚本从肘图中找到簇的值很麻烦。您可以观察肘部图并自己找到肘部点，但是从脚本中找到它是很多工作。

所以另一个选择是使用 轮廓方法 找到它。轮廓的结果完全符合R中的肘法结果。

这就是我所做的。

#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")

希望能帮助到你！！

可能是像我这样的初学者寻找代码示例。信息 silhouette_score可用 这里。

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)

看着 这个 论文，“学习K-均值的K”，由Charles Elkan的Greg Hamerly撰写。它使用高斯测试来确定正确数量的簇。同样，作者声称，这种方法比接受答案中提到的BIC更好。

有一种叫做经验法则。它说簇数可以通过k =（n/2）^0,5计算，其中n是样品中元素的总数。您可以在以下论文中检查此信息的真实性：

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

还有另一种称为g均值的方法，您的分布遵循高斯分布或正态分布。它包括增加K，直到您所有的K组都遵循高斯分布。它需要很多统计数据，但可以完成。这是来源：

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

我希望这有帮助！

首先构建一个 最小跨越树 您的数据。卸下K-1最昂贵的边缘将树拆分为K簇，
因此，您可以构建一次MST，查看各种K的群集间距 /指标，然后弯曲曲线。

这仅适用于 单链接_Clustering，但为此快速而容易。另外，MSTS可以很好地视觉效果。
例如，请参见下面的MST图Stats.Stackexchange可视化软件用于群集.

如果使用MATLAB，则自2013b以来的任何版本都可以使用该功能 evalclusters 找出最佳 k 用于给定的数据集。

此功能使您可以从3种聚类算法中进行选择 - kmeans, linkage 和 gmdistribution.

它还使您可以从4个聚类评估标准中进行选择 - CalinskiHarabasz, DaviesBouldin, gap 和 silhouette.

我很惊讶没有人提到过这篇出色的文章：http://www.ee.columbia.edu/~dpwe/papers/phamdn05-kmeans.pdf

在遵循了其他几个建议之后，我终于在阅读此博客时遇到了这篇文章：https://datasciencelab.wordpress.com/2014/01/21/selection-of-kin-k-means-clustering-reloaded/

之后，我在Scala中实施了它，对于我的用例，它提供了非常好的结果。这是代码：

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

我的想法是使用 轮廓系数 找到最佳群集编号（k）。细节说明是 这里.

假设您有一个数据矩阵 DATA, ，您可以在类似的簇数（通过轮廓分析）估计群集数量的情况下进行分区：

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

一个可能的答案是使用元启发式算法（例如遗传算法）找到k。这很简单。您可以使用随机K（在某些范围内），并通过某些测量值等测量来评估遗传算法的拟合功能，并找到最佳的K基础拟合功能。

https://en.wikipedia.org/wiki/silhouette_(Clustering）

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

另一种方法是使用自组织地图（SOP）查找最佳数量簇数。 SOM（自组织地图）是一种无监督的神经网络方法，仅需要输入来聚类解决问题。该方法在有关客户细分的论文中使用。

本文的参考是

Abdellah Amine等人，使用聚类技术和LRFM模型的电子商务客户细分模型：摩洛哥在线商店的案例，世界科学，工程和技术学院国际计算机与信息工程杂志杂志：9，否：8：8 ，2015，1999-2010

如果您不知道群集k的数量以作为k均值的参数提供，则有四种方法可以自动发现它：

  • G-Means算法：它发现使用统计测试自动发现簇数，以决定是否将K均值中心拆分为两个。该算法采用层次方法来检测群集数量，基于统计检验，该测试是对数据子集遵循高斯分布（连续函数，近似于事件的确切二项式分布）的假设，如果没有，则分配了群集。 。它从少数中心开始，例如一个群集（k = 1），然后该算法将其分成两个中心（k = 2），然后再次分裂这两个中心（k = 4），在四个中心中有四个中心全部的。如果G-Means不接受这四个中心，则答案是上一步：在这种情况下，两个中心（k = 2）。这是您的数据集将分为的群集数。当您没有对实例分组后会得到的群集数量的估计，G-Means非常有用。请注意，“ K”参数的不便选择可能会给您错误的结果。 g均值的并行版本称为 p均值. 。 G-Means资料来源：来源1 来源2 来源3

  • X均值: ：一种有效的新算法，搜索群集位置的空间和簇数，以优化贝叶斯信息准则（BIC）或AKAIKE信息标准（AIC）度量。此版本的k均值找到了数字k，还加速了k均值。

  • 在线K-均值或流k-均值：它允许通过扫描整个数据来执行K-均值，并发现自动k的最佳数量k的最佳数量。火花实现它。

  • 刻痕算法: ：这是一种非参数聚类技术，不需要事先了解簇数的数量，也不需要限制簇的形状。平均移位聚类旨在发现样品平滑密度中的“斑点”。它是一种基于质心的算法，它是通过更新候选者为质心作为给定区域内点的平均值而起作用的。然后，将这些候选物在后处理阶段过滤，以消除近乎解纤维，以形成最终的质心组。资料来源： Source1, Source2, Source3

我使用了我在这里找到的解决方案： http://efavdb.com/mean-shift/ 而且对我来说很好： 

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

enter image description here

嗨，我会简单而直接解释，我喜欢使用“ nbclust”库来确定簇。

现在，如何使用“ nbclust”函数来确定簇数的数量：您可以使用实际数据和簇检查GitHub中的实际项目 - 扩展到此“ Kmeans”算法也使用正确的“中心”进行了执行。

GitHub项目链接： https://github.com/rutvijbhutaiya/thailand-customer-engagement-facebook

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top