Matlab：Kmeans每次都会给出不同的结果

Question

我在Matlab上对一个400x1000的矩阵运行kmeans算法，但每次运行时结果都不同。以下是代码示例：

[idx, ~, ~, ~] = kmeans(factor_matrix, 10, 'dist','sqeuclidean','replicates',20);

每次运行这段代码，为什么会得到不同的结果？有什么想法吗？

我正在使用它来识别多重共线性问题。

感谢您的帮助！

- user1129988

Answer 1

MATLAB中的k-means实现具有随机性：选择初始中心点。这会导致不同的结果。然而，在实际应用中，MATLAB会运行多次k-means，并返回失真度最低的聚类结果。如果每次看到的聚类结果差别很大，这可能意味着您的数据不适合k-means寻找的那种（球形）聚类，这提示您尝试其他聚类算法（例如，谱聚类算法）。

通过将初始中心点作为函数参数之一传递给它，您可以获得确定性行为（start 参数）。这将使您每次得到相同的聚类输出。有几种启发式方法可以选择初始中心点（例如 K-means++ 方法）。

- Ansari

---

有没有简单而有效的确定性方法来初始化K-Means？ - Royi

最简单但天真的解决方案是自己选择一些聚类中心。如果您应用某些启发式方法来找到“好”的初始聚类中心，则会得到确定性的K均值算法。您可能需要阅读这篇论文，该论文使用“最近邻搜索”构建确定性K均值算法：http://research.ijcaonline.org/volume63/number15/pxc3885541.pdf - Hans-Helge

但是质心应该总是收敛到相同的星座。在理论上，K-Means会导致相同的一组质心。那么在实践中，是什么使最终结果变得随机呢？ - Leevo

Answer 2

正如您可以在维基上阅读的那样，k-means算法通常是启发式的和部分概率的，Matlab中的算法也不例外。

这意味着算法中有一定的随机性（在Matlab的情况下，重复使用随机起始点来找到全局解）。这使得kmeans输出的聚类平均质量很好。但是：由于算法的伪随机性质，每次都会得到略微不同的聚类结果--这是正常行为。

- Rody Oldenhuis

---

挑剔一点：请注意，通常来说，“启发式”和“随机”的算法属性是两个不同的概念。启发式算法使用近似（但通常是确定性的）评分来做决策，而随机算法则使用（伪）随机数来做决策。当然，这两种属性也可以组合使用。 - Florian Brucker

@FlorianBrucker 确实如此。在我看来，这并不是吹毛求疵 :) - Rody Oldenhuis

质心不应该总是收敛到相同的星座吗？从理论上讲，K-Means会导致相同的质心集合。在实践中，是什么造成了最终结果的随机性呢？ - Leevo

Answer 3

这被称为初始化问题，因为kmeans从随机的初始点开始对数据进行聚类。Matlab选择k个随机点，并计算数据中各个点到这些位置的距离，然后找到新的质心以进一步最小化距离。因此，你可能会得到不同的质心位置结果，但答案是相似的。

- user14372