k-means会陷入无限循环吗？

Question

我研究过 k 均值算法并且知道它是如何工作的。

只是好奇，是否有任何情况该算法会进入无限循环，比如说我们对初始质心点有一些特别糟糕的选择？我只能想象 k 均值会在初始选择错误的情况下达到局部最小值的情况。

Answer 1

否。k 均值在 d 维空间中的上限为 O(n^kd)。

Answer 2

另请考虑同一问题的这个答案。
https://stackoverflow.com/a/60312554/15467861

最后一种边缘情况：如果多个最小状态具有相同的损失怎么办？这是一种极不可能发生的情况，但当且仅当算法对于平局断路器的编码很差时才可能导致问题。本质上，这可能导致循环的唯一方法是，数据点对于两个簇的距离相等，并且即使距离相等，也允许将簇更改为远离当前的簇。可以说，算法通常经过编码，以便数据点永远不会在平局上或以其他确定性方式交换，从而完全避免这种情况。