对于一个作业，我被要求提供一个证明，证明 k-means 在有限的步骤中收敛。
这是我写的：
下面，是所有聚类中心的集合。定义一个“能量”函数 能量函数是非负的。我们看到算法的步骤（2）和（3）都减少了能量。由于能量是从下方限制并不断减少的，因此它必须收敛到局部最小值。当E(C) 以低于某个阈值的速率变化时，可以停止迭代。
步骤 2 是指通过其最近的聚类中心标记每个数据点的步骤，步骤 3 是通过取均值更新中心的步骤。
这不足以证明在有限数量的步骤中收敛。能量可以不断变小，但不排除中心点可以跳跃而不改变能量的可能性。换句话说，可能存在多个能量最小值，算法可以在它们之间跳跃，不是吗？
首先，最多有种方式将个数据点划分为个簇；每个这样的分区都可以称为“集群”。这是一个很大但有限的数字。对于算法的每次迭代，我们仅基于旧聚类生成新聚类。请注意
由于该算法迭代一个定义域为有限集的函数，所以迭代最终必须进入一个循环。循环的长度不能大于，因为否则通过 (2)，您将拥有一些成本低于自身的集群，这是不可能的。因此，循环的长度必须恰好为。因此，k-means 在有限次数的迭代中收敛。
补充一点：算法是否收敛也取决于你的停止标准。如果一旦集群分配不再改变就停止算法，那么您实际上可以证明算法不一定收敛（假设集群分配在多个质心具有相同距离的情况下没有确定性的决胜局）。
这里有 8 个数据点（点）和两个质心（红十字）。现在绿色数据点与左右质心的距离相同。蓝色数据点也是如此。让我们假设在这种情况下分配函数不是确定性的。此外，我们假设在第 1 次迭代中，绿点被分配到左侧集群，蓝点被分配到右侧集群。然后我们更新质心。事实证明，他们实际上停留在同一个地方。（这是一个简单的计算。对于左质心，您平均两个左黑点和两个绿点的坐标 -> (0, 0.5)。右质心相同）。
然后在第 2 次迭代中，情况再次看起来相同，但现在我们假设（在平局的情况下）非确定性分配函数将绿点分配给右侧集群，将蓝点分配给左侧集群。同样，质心不会改变。
迭代 3 再次与迭代 1 相同。因此，我们遇到了集群分配不断变化并且算法（使用此停止标准）不收敛的情况。
本质上，我们只能保证 k-means 中的每一步都会降低成本或保持成本不变（即而不是）。这使我能够构建一个成本通过迭代保持不变的案例，即使分配仍然发生变化。