使用PyClus优化K（理想集群）

Question

我使用PyCluster的kMeans来集群一些数据——主要是因为SciPy的kMeans2（）产生了一个无法克服的错误。Mentioned here。总之，pyclusterkmeans运行得很好，我现在正试图优化kMeans集群的数量。PyCluster附带的文献表明，我可以通过实现EM算法bottom of page 13 here来优化其kMeans，但我找不到一个例子。在

有人能告诉我一个PyCluster k-means优化问题吗？提前谢谢你的帮助。在

Answer 1

PyCluster的手册提到了一个不同于您所询问的优化问题。当您询问如何确定最佳集群数量时，本手册讨论如何在给定集群总数的情况下找到最佳集群。要理解的概念是k-均值，这是一种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算法）多次并选择最佳的聚类。它从未涉及到寻找最佳簇数的问题。在

也就是说，您可以使用一些启发式方法来确定最佳集群数量（请参见示例Wikipedia）：

1. 也许最简单的方法就是设置k=sqrt（n/2），这通常被认为是最优的。在
2. 另一种方法是将数据分成两部分，一个是训练集（可能是前90%的数据），另一个是测试集（可能是最后10%的数据）。这两个集合都应该代表整个数据集，因此您可能希望使用随机洗牌或者随机抽样事先。只需使用训练集，就可以应用k-均值聚类来寻找聚类分配，从中可以推断出每个聚类的平均值。然后，使用测试数据集，计算每个数据点之间距离的平方和及其指定簇的平均值。最后，如果您绘制集群数量与测试错误的关系图，您将（也许）发现在k的某个值之后，错误将开始增加，或者至少停止减少。然后你可以选择发生这种情况的k。测试数据集的使用将有助于保证由训练产生的聚类代表实际的数据集，而不是您偶然采样的特定训练集。如果有n个训练数据点和n个簇，当然可以在训练集中获得一个完美的聚类，但是测试集的误差可能仍然很大。在
3. 或者你可以试试更一般的高斯混合模型。在混合高斯模型中，有k个高斯分布，Nˉ1，…，Nаk，以权重c_c1，…，cаk出现，其中c_1+…+c_k=1。用概率c峎i从高斯N峎i中提取一个数据点，k均值是高斯混合模型的一种特殊类型，其中假设每个高斯函数都是协方差相等且所有权重相等的球形。这个模型的一个优点是，如果你看到一些c_i真的很小，那么高斯峰可能不是真正的簇。为了减少复杂性（以及过度拟合的风险），可以将高斯函数约束为球形或具有相等的协方差，这将为您提供一个行为几乎类似于k-均值的聚类机制，只是它显示了每个簇的重要性。在