K-means 中的总距离总和是否必须始终递减？
Does the total distance sum in K-means have to be always decreasing?
我正在使用 Java 进行 k 均值聚类。我在我的代码中没有看到问题，它看起来很好。但是，我有点不明白。
第一步：
选择 N 个中心。 (假设有N个簇)
第 2 步：
使用欧氏距离将每个向量放入最近中心的簇中。 (||v1 - v2||)
第 3 步：
为每个集群找到新的平均值（=中心）
第 4 步：
如果中心有明显移动，转到步骤 2
但是，当我在每次迭代后绘制点到相应中心距离的总和时，我可以看到总和一直在减少（尽管它总体上在减少并且收敛得很好）。
第二次迭代的总距离总是比第一次短，而且是最短的。并且总距离在第 3 次迭代时略有增加，并在第 4 或第 5 次迭代时收敛。
我相信有人告诉我它应该一直在减少。怎么了？我的算法（实现）或我对总距离的假设？
对于同一个种子，它必须总是递减的。
也许你的错误是你使用了欧氏距离。
K-means 不会最小化欧氏距离。
这是一个普遍的误解，甚至一半的教授都错了。 K-means 最小化平方和，即 squared 欧氏距离之和。不，这没有找到具有最小欧氏距离的解。
因此请确保您在所有地方都策划了 SSQ。从代码中删除所有平方根。它们不属于 k-means。
补充评论：
- 不要最小化方差（或等效的标准差），因为它可能很诱人：
最小化距离平方和并不等同于最小化方差，但这并没有阻止人们建议将其作为 k-means 的正确 objective。
很容易想象为什么这可能是个坏主意：
假设一个点几乎位于两个簇质心之间的中点（欧几里得），在包含新点之前两者具有相同的方差。现在想象其中一个集群的点成员比另一个集群大得多。假设新点稍微靠近成员数大得多的点。将新点添加到较大的集群虽然是正确的，因为它更接近该质心，但不会像将新点添加到成员资格小得多的另一个集群那样减少其方差。
- 如果您正在最小化正确的 objective 函数，但它仍然没有单调递减，请检查您是否没有量化质心意味着：
例如，如果您使用 [0, 255] 范围内的整数值而不是 [0, 1] 范围内的浮点值执行图像分割，并且您强制质心均值为 uint8，就会发生这种情况数据类型。
只要找到质心均值，就应该按原样在 objective 函数中使用它们。如果您的算法正在为质心均值（浮点数）找到一个值，但随后将 objective 与其他值（字节整数）最小化，这可能会导致与假设的单调递减 objective 不可接受的变化。
我正在使用 Java 进行 k 均值聚类。我在我的代码中没有看到问题，它看起来很好。但是，我有点不明白。
第一步： 选择 N 个中心。 (假设有N个簇)
第 2 步： 使用欧氏距离将每个向量放入最近中心的簇中。 (||v1 - v2||)
第 3 步： 为每个集群找到新的平均值（=中心）
第 4 步： 如果中心有明显移动，转到步骤 2
但是，当我在每次迭代后绘制点到相应中心距离的总和时，我可以看到总和一直在减少（尽管它总体上在减少并且收敛得很好）。
第二次迭代的总距离总是比第一次短，而且是最短的。并且总距离在第 3 次迭代时略有增加，并在第 4 或第 5 次迭代时收敛。
我相信有人告诉我它应该一直在减少。怎么了？我的算法（实现）或我对总距离的假设？
对于同一个种子，它必须总是递减的。
也许你的错误是你使用了欧氏距离。
K-means 不会最小化欧氏距离。
这是一个普遍的误解，甚至一半的教授都错了。 K-means 最小化平方和，即 squared 欧氏距离之和。不，这没有找到具有最小欧氏距离的解。
因此请确保您在所有地方都策划了 SSQ。从代码中删除所有平方根。它们不属于 k-means。
补充评论：
- 不要最小化方差（或等效的标准差），因为它可能很诱人：
最小化距离平方和并不等同于最小化方差，但这并没有阻止人们建议将其作为 k-means 的正确 objective。
很容易想象为什么这可能是个坏主意：
假设一个点几乎位于两个簇质心之间的中点（欧几里得），在包含新点之前两者具有相同的方差。现在想象其中一个集群的点成员比另一个集群大得多。假设新点稍微靠近成员数大得多的点。将新点添加到较大的集群虽然是正确的，因为它更接近该质心，但不会像将新点添加到成员资格小得多的另一个集群那样减少其方差。
- 如果您正在最小化正确的 objective 函数，但它仍然没有单调递减，请检查您是否没有量化质心意味着：
例如，如果您使用 [0, 255] 范围内的整数值而不是 [0, 1] 范围内的浮点值执行图像分割，并且您强制质心均值为 uint8，就会发生这种情况数据类型。
只要找到质心均值，就应该按原样在 objective 函数中使用它们。如果您的算法正在为质心均值（浮点数）找到一个值，但随后将 objective 与其他值（字节整数）最小化，这可能会导致与假设的单调递减 objective 不可接受的变化。