优化K(理想的簇数)使用PyCluster

Question

我正在使用PyCluster的kMeans来聚集一些数据 - 主要是因为SciPy的kMeans2()产生了一个不可克服的错误. 这里提到.无论如何,PyCluster kMeans运行良好,我现在正在尝试优化kMeans集群的数量.PyCluster的附带文献表明我可以通过实现EM算法来优化其kMeans - 这里是第13页的底部 - 但我找不到一个例子.

有人可以指点一下PyCluster k-means优化问题吗？在此先感谢您的帮助.

Answer 1

PyCluster的手册指的是与您询问的问题不同的优化问题.当您询问如何确定最佳群集数时,本手册将介绍如何在给定群集总数的情况下找到最佳群集.要理解的概念是k-means,它是一种EM(期望最大化问题)算法,不能保证最优的聚类解决方案(其中最优聚类解决方案可以定义为最小化总和的聚类的分配).每个数据点与其簇的平均值之间的距离的平方).k-means的工作方式是这样的:

set cluster means to equal k randomly generated points
while not converged:
     # expectation step:
     for each point:
          assign it to its expected cluster (cluster whose mean it is closest to)
     # maximization step:
     for each cluster:
          # maximizes likelihood for cluster mean
          set cluster mean to be the average of all points assigned to it

给定初始化时,k-means算法将输出最佳解决方案,但不一定能在全局范围内找到最佳的聚类解决方案.这是本手册在第13页底部引用的内容.手册说kcluster例程将多次执行EM(这正是k-means算法)并选择最佳聚类.它从未提到找到最佳簇数的问题.

也就是说,您可以使用一些启发式方法来确定最佳簇数(例如,请参阅维基百科):

1. 也许最简单的只是设置k = sqrt(n/2),这经常被认为是最优的.
2. 另一种方法是将数据分为两部分:训练集(可能是前90%的数据)和测试集(可能是最后10%的数据).两个集都应该代表整个数据集,因此您可能需要事先使用random.shuffle或random.sample.仅使用训练集,您可以应用k均值聚类来查找聚类分配,从中可以推导出每个聚类的均值.然后,使用测试数据集,计算每个数据点之间的距离的平方和与其指定的簇的平均值之和.最后,如果您绘制簇的数量与测试错误的关系,您(可能)会发现在k的某个值之后,错误将开始增加,或者至少会停止减少.然后,您可以选择发生这种情况的k.使用测试数据集将有助于保证培训产生的聚类代表实际数据集,而不是您抽样的特定培训集.如果您有n个训练数据点和n个聚类,您当然可以在训练集上获得完美的聚类,但测试集的错误可能仍然很大.
3. 或许您可以尝试更高级的高斯模型混合物.在高斯模型的混合中,存在k个高斯分布,N_1,...,N_k,出现权重c_1,...,c_k,其中c_1 + ... + c_k = 1.从高斯N_i以概率c_i绘制数据点.k均值是一种特殊类型的高斯模型的混合,其中每个高斯假设是具有相等协方差的球面,并且所有权重相等.这个模型的一个优点是,如果你看到一些c_i真的很小,那么高斯驼峰可能不是一个真正的集群.为了降低复杂度(以及过度拟合的风险),您可以将高斯约束为球形或具有相等的协方差,这为您提供了一种几乎像k均值一样的聚类机制,除了它显示了每个聚类的重要性.