我正在使用PyCluster的kMeans对一些数据进行聚类——主要是因为SciPy的kMeans2()产生了一个无法克服的错误。在这里提到。无论如何，PyCluster的kMeans运行得很好，现在我正在尝试优化kMeans聚类的数量。PyCluster的相关文献建议我可以通过实现EM算法来优化其kMeans——在第13页底部这里——但我找不到一个例子。

请问有人能指导我到一个PyCluster的k-means优化问题吗？提前感谢任何帮助。

回答：

PyCluster的手册提到的优化问题与您询问的不同。您询问如何确定最佳聚类数量，而手册处理的是在已知总聚类数量的情况下如何找到最佳聚类。需要理解的概念是，k-means是一种EM（期望最大化问题）算法类型，它并不能保证找到最优的聚类解决方案（最优的聚类解决方案可以定义为将每个数据点与其聚类均值之间的距离平方和最小化的聚类分配）。k-means的工作方式如下：

set cluster means to equal k randomly generated pointswhile 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-means聚类来找到聚类分配，从而推导出每个聚类的均值。然后，使用测试数据集，计算每个数据点与其分配的聚类均值之间的距离平方和。最后，如果您绘制聚类数量与测试误差的关系图，您可能会发现，在某个k值之后，误差开始增加，或者至少不再减少。然后您可以选择发生这种情况的k。使用测试数据集将有助于保证训练产生的聚类能代表实际数据集，而不仅仅是您碰巧抽样的特定训练集。如果您有n个训练数据点和n个聚类，当然可以在训练集上获得完美的聚类，但测试集的误差可能仍然很大。
3. 或者您可以尝试更一般的Gaussian混合模型。在Gaussian混合模型中，有k个Gaussian分布，N_1, …, N_k，以权重c_1, …, c_k出现，其中c_1+…+c_k=1。一个数据点以概率c_i从Gaussian N_i中抽取。k-means是Gaussian混合模型的一种特殊类型，其中每个Gaussian被假定为球形且具有相等的协方差，并且所有权重相等。这种模型的一个优点是，如果您看到某些c_i非常小，那么那个Gaussian隆起可能不是一个真正的聚类。为了减少复杂性（和过拟合的风险），您可以约束Gaussian为球形或具有相等的协方差，这为您提供了一种几乎像k-means一样的聚类机制，但它显示了每个聚类的重要性。