使用 K平均算法时如何确定 k?

我一直在研究 K平均算法,有一件事不清楚,那就是如何选择 k 的值。这只是一个反复试验的问题,还是有更多的原因?

122300 次浏览

基本上,您希望找到两个变量之间的平衡: 集群的数量(K)和集群的平均方差。您希望将前者最小化,同时也将后者最小化。当然,随着集群数量的增加,平均方差减小(直到 K = N和方差 = 0的平凡情况)。

在数据分析中,没有一种真正的方法在所有情况下都比其他方法更有效。最后,你必须用你自己最好的判断力。为此,它有助于根据平均方差绘制集群的数量(假设您已经为 K的几个值运行了算法)。然后可以使用曲线拐角处的集群数。

你可以最大化贝斯信息量准则:

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

其中 L(X | C)是根据模型 C的数据集 X的对数似然性,p是模型 C中的参数数目,n是数据集中的点数。 参见丹 · 佩莱格和安德鲁 · 摩尔在 ICML 2000中提出的 X- 均值: 扩展 < i > K -均值有效地估计簇的数目

另一种方法是从一个较大的 k值开始,并不断去除质心(减少 k) ,直到它不再减少描述长度。参见《 模式分析与应用》第2卷,第59-72页,1999年霍斯特 · 比肖夫、阿莱斯 · 莱昂纳迪斯和亚历山大 · 塞尔布的《 “稳健矢量量化的 MDL 原理”》。

最后,您可以从一个集群开始,然后继续拆分集群,直到分配给每个集群的点有一个正态分布。在 学习 < em > k 中的 < em > k -手段(NIPS 2003)中,Greg Hamery 和 Charles Elkan 展示了一些证据,证明这比 BIC 工作得更好,而且 BIC 没有足够强烈地惩罚模型的复杂性。

首先构建数据的 最小生成树。 删除 K-1最昂贵的边将树分割成 K 簇,
这样您就可以构建一次 MST,查看不同 K 的集群间距/指标, 然后走弯路。

这只适用于 单链接群集, 但是它的快速和容易。此外,MST 作出良好的视觉效果。
例如,请参见下面的 MST 图 用于聚类的 stackexchange 可视化软件

看看 这个的论文,格雷格 · 哈默里和查尔斯 · 埃尔坎的《学习 k 的 k 意思》。它使用高斯检验来确定正确的簇数。同时,作者认为这种方法优于公认答案中提到的 BIC。

是的,您可以使用 Elbow 方法找到最佳的集群数量,但是我发现使用脚本从肘形图中找到集群的值很麻烦。您可以观察肘关节图并自己找到肘关节点,但是从脚本中找到它需要很多工作。

因此,另一种选择是使用 剪影法来查找它。剪影法的计算结果完全符合弯管法的计算结果。

我是这么做的。

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

希望能有帮助!

我的想法是使用 剪影系数来找到最佳的集群数(K)。详细说明是 给你

有一个叫经验法则的东西,它说集群的数量可以通过

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-k-in-k-means.pdf

希望这个能帮上忙!

假设你有一个称为 DATA的数据矩阵,你可以通过估计聚类的数量(通过轮廓分析)来对媒体进行划分,如下所示:

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

我很惊讶竟然没有人提到这篇优秀的文章: Http://www.ee.columbia.edu/~dpwe/papers/phamdn05-kmeans.pdf

在接受了其他一些建议之后,我最终在阅读这篇博客时读到了这篇文章: Https://datasciencelab.wordpress.com/2014/01/21/selection-of-k-in-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]]
}

如果使用 MATLAB,也就是2013b 以来的任何版本,都可以使用函数 evalclusters来找出给定数据集的最佳 k应该是什么。

这个函数允许您从3种集群算法中进行选择-kmeanslinkagegmdistribution

它还允许您从4个集群评估标准中进行选择—— CalinskiHarabaszDaviesBouldingapsilhouette

一个可能的解决方案是使用元启发式算法,如遗传算法找到 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})

可能是像我这样的初学者在寻找代码示例 在这里可以获得。

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)

我使用了我在这里找到的解决方案: 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

另一种方法是使用自组织映射(SOP)来寻找最佳的集群数量。SOM (自组织映射)是一种无监督的神经 网络方法,这只需要输入被用来 聚类用于问题解决。这种方法在一篇关于客户细分的文章中使用。

本文的参考文献是

Abdellah Amine 等,电子商务应用中的客户细分模型 聚类技术与 LRFM 模型: 实例 世界科学、工程和技术研究院在摩洛哥的网上商店 国际计算机与信息工程杂志 卷: 9,号: 8,2015,1999-2010

如果你不知道作为参数的集群 k 的数目,那么有四种方法可以自动找到它:

嗨,我将简单直接地解释一下,我喜欢使用‘ NbClust’库来确定集群。

现在,如何使用“ NbClust”函数来确定正确的集群数量: 你可以使用实际的数据和集群检查 Github 中的实际项目——扩展到这个“ kmeans”算法也使用正确的“中心”数量来执行。

Github 项目链接: https://github.com/RutvijBhutaiya/Thailand-Customer-Engagement-Facebook

您可以通过可视化地检查数据点来选择集群的数量,但是您很快就会意识到,除了最简单的数据集之外,在这个过程中存在很多不确定性。这并不总是坏事,因为你在做非监督式学习,而且在贴标签的过程中有一些固有的主观性。在这里,以前的经验与特定的问题或类似的东西将帮助您选择正确的价值。

如果你想知道应该使用的集群数量,你可以使用 Elbow 方法:

首先,计算某些 k 值的平方误差和(SSE)(例如2,4,6,8等)。SSE 定义为集群中每个成员与其形心之间的平方距离之和。数学上来说:

SSE = ∑ Ki = 1∑ x ∈ cidist (x,ci)2

如果将 k 与 SSE 对比,就会看到误差随着 k 的增大而减小; 这是因为当集群数量增加时,它们应该更小,所以失真也更小。肘形法的思想是选择 SSE 突然降低的 k。这在图中产生了“肘效应”,如下图所示:

enter image description here

在这种情况下,k = 6是 Elbow 方法选择的值。考虑到肘方法是一个启发式的,因此,它可能会或可能不会在你的特殊情况下很好地工作。有时候,有不止一个肘关节,或者根本没有肘关节。在这些情况下,您通常通过评估 k-means 在您试图解决的特定集群问题上下文中的表现来计算最佳 k。

我做了一个 Python 包膝盖(膝盖算法)。它动态地找到作为曲线开始变平的点的集群数字。给定一组 x 和 y 值,kneed 将返回函数的膝点。膝关节是最大弯曲点。下面是示例代码。

y = [7342.1301373073857, 6881.7109460930769, 6531.1657905495022,
6356.2255554679778, 6209.8382535595829, 6094.9052166741121,
5980.0191582610196, 5880.1869867848218, 5779.8957906367368,
5691.1879324562778, 5617.5153566271356, 5532.2613232619951,
5467.352265375117, 5395.4493783888756, 5345.3459908298091,
5290.6769823693812, 5243.5271656371888, 5207.2501206569532,
5164.9617535255456]


x = range(1, len(y)+1)


from kneed import KneeLocator
kn = KneeLocator(x, y, curve='convex', direction='decreasing')


print(kn.knee)

在这里留下一个很酷的 Codecademy 课程的动图: enter image description here

K- 均值算法:

  1. 为初始集群放置 k 个随机质心。
  2. 将数据样本分配到最近的质心。
  3. 根据上述分配的数据样本更新质心。

顺便说一句,这不是一个完整的算法的解释,它只是有益的可视化