K-means 中的总距离总和必须始终递减吗？

Question

我正在使用 Java 进行 k 均值聚类。我的代码中没有发现问题，而且看起来不错。但是，我不明白一些事情。

步骤1：选择N个中心。（假设有N个簇）

步骤2：使用欧氏距离将每个向量放入距离最近的中心的簇中。(||v1 - v2||)

步骤 3：找到每个簇的新均值（=中心）

步骤 4：如果中心发生显着移动，则转至步骤 2

然而，当我在每次迭代后绘制点到各自中心距离的总和时，我可以看到总距离一直在减少（尽管它总体上在减少并且收敛得很好）。

第二次迭代的总距离总是比第一次迭代的总距离短，并且是最短的。总距离在第 3 次迭代时略有增加，并在第 4 次或第 5 次迭代时收敛。

我相信有人告诉我它应该总是减少。怎么了？我的算法（实现）或我对总距离的假设？

Answer 1

对于同一个种子，它必须始终减少。

也许您的错误是您使用了欧几里德距离。

K-means 不会最小化欧几里德距离。

这是一个常见的误解，甚至有一半的教授都错了。K 均值最小化平方和，即欧几里得距离平方和。不，这不具有最小欧几里德距离的解决方案。

因此，请确保您在各处都绘制了 SSQ。从代码中删除所有平方根。它们不属于 k-means。