使用K均值聚类算法时，是否可能会有一组数据导致无限循环？

Question

此问题是理论上的问题，不是专门解决问题的方法。

我最近被介绍给K-Means聚类算法和无监督的机器学习算法，尽管有些数据集即使是完全随机的，但绘制的平均质心在每次迭代中仍会不断变化，这让我很感兴趣。

示例：

我想在这里显示的是，假设程序是否在第6次迭代到第9次迭代之间切换，并且一直保持下去。

我在使用K-Means之前已经使我的代码随机挂起，所以我不认为这是不可能的，但是请告诉我这是否是已知事件，或者由于算法的性质而不可能。

如果您需要更多信息，请在评论中问我。使用Python 3.7]

Answer 1

tl; dr，如果算法编码正确，则K-means算法始终具有终点。

说明：

考虑此问题的理想方法不是从数据点会导致问题的角度出发，而是从更广泛的意义上来说，kmeans是如何工作的。 k-means算法始终在有限空间中工作。对于N个数据点，数据点只有N ^ k个不同的布置。 （这个数字可能很大，但仍然是有限的）

第二，k-均值算法始终在优化损失函数，基于每个数据点与其分配的聚类中心之间距离的平方和。这意味着两个非常重要的事情：每个N ^ k不同的布置都可以按照最小损失到最大损失的升序/降序排列。同样，K-means算法将永远不会从净损失较低的状态变为净损失较高的状态。

这两个条件保证了算法将始终趋向于在有限空间中进行最小损失的安排，从而确保了它的结局。

最后一种情况：如果一个以上的最小状态具有相等的损失怎么办？这是极不可能的情况，但可能会导致问题仅当且仅当该算法对于平局决胜者编码不正确。本质上，这可能导致周期的唯一方法是，如果一个数据点对于两个群集具有相等的距离，并且即使在相等的距离上，也允许将群集更改为远离其当前群集。可以说，通常对算法进行编码，以便数据点永远不会在平局上或以其他确定性方式交换，从而完全避免了这种情况。