我在 MATLAB 中编写了一个k-Means 聚类算法，我想我会针对内置的 MATLAB 进行尝试kmeans(X,k)。
然而，对于非常简单的四集群设置（见图），MATLAB kMeans并不总是收敛到最优解（左），而是收敛到（右）。
我写的也不总是那样做，但是内置函数不应该能够解决这样一个简单的问题，总是找到最佳解决方案吗？
问问题
7754 次
5 回答
11
正如@Alexandre C.解释的那样，K-means 算法取决于初始集群质心位置，并且不能保证它会收敛到最优解。
你能做的最好的事情就是用随机的起点重复实验几次。
MATLAB 的实现提供了这样一个选项：replicates它重复聚类 N 次，并选择具有最低的总聚类内点到质心距离的聚类。您还可以使用该选项控制如何选择初始质心start。
此外，MATLAB 提供了多种距离度量（欧几里得、曼哈顿、余弦等）的选择。一个简洁的选项emptyaction允许您控制当集群在迭代期间失去所有分配的成员时会发生什么。
但真正的优势在于它采用了两阶段算法：通常的分配-重新计算迭代，然后是在线更新阶段。请务必阅读文档页面的算法部分以获取更多信息。
于 2010-09-07T21:42:30.000 回答
4
k-means 算法对聚类中心的初始猜测非常敏感。您是否尝试了具有相同初始质心的两种代码？
该算法很简单，我怀疑您的实现与 Matlab 之间存在很大差异。
于 2010-09-07T11:25:49.107 回答
3
我不会认为这是一个简单的问题。:) 事实上，关于“k-means clustering”的 Wikipedia 文章对计算复杂性给出了一幅相当悲观的图景。
如果你想摆脱随机重启（依赖于初始猜测），折衷方案是“全局 k-means”算法；论文和 matlab 代码可以在这里找到：http: //lear.inrialpes.fr/~verbeek/software.php
于 2011-01-12T17:01:42.820 回答
2
虽然K-Means++不会在一次运行中解决问题，但它在运行 N 次时往往会给出更好的结果（与运行原始 K-Means 算法 N 次相比）。
于 2010-10-03T08:29:09.557 回答
2
您可能经常会对“k-means 算法”（即 Lloyd 算法）的任何特定运行所提出的解决方案感到失望。那是因为劳埃德的算法经常陷入糟糕的局部最小值。
幸运的是，Lloyd's 只是解决 k-means 的一种方法。还有一种方法几乎总能找到更好的局部最小值。
诀窍是一次更新一个数据点的集群分配。n您可以通过计算分配给每个平均值的点数来有效地做到这一点。这样您就可以m在删除点后重新计算聚类均值x，如下所示：
m_new = (n * m - x) / (n - 1)
并添加x到集群意味着m使用：
m_new = (n * m + x) / (n + 1)
当然因为不能向量化，所以在 MATLAB 中运行有点痛苦，但在其他语言中也不算太糟糕。
如果您真的热衷于获得尽可能好的局部最小值，并且您不介意使用基于示例的聚类，那么您应该查看相似性传播。Frey 实验室亲和力传播页面上提供了 MATLAB 实现。
于 2010-09-15T02:27:53.620 回答