问为什么k-means不给出全局最小值呢？

EN

不要把问题和算法混在一起。

k-means问题是寻找质心的最小二乘分配。

有多种算法可以找到解决方案。

有一种显而易见的方法可以找到全局最优值:枚举k^n possible assignments -这将产生全局最小值，但在指数运行时。

人们更多地关注于在更快的时间内找到近似解。

Lloyd/Forgy算法是一种EM式的迭代模型改进方法，由于存在有限数量的状态，因此保证收敛到局部最小值，并且目标函数必须在每一步中减小。此算法在i << n通常所在的O(n*k*i)中运行，但它可能只找到局部最小值。

从技术上讲，MacQueens方法不是迭代的。这是一种单次通过，一次一个元素的算法，甚至不会找到劳埃德意义上的局部最小值。(但是，您可以在数据集上多次运行它，直到收敛，以获得局部最小值！)如果你做一个单过程，它在O(n*k)中，对于多个过程添加i。它可能会也可能不会比劳埃德需要更多的传球。

然后是哈蒂根和王。我不记得细节了，IIRC它是Lloyd/Forgy的一个聪明的，更懒惰的变体，所以可能在O(n*k*i)中也是如此(尽管可能不会在以后的迭代中重新计算所有的n*k距离？)

你也可以做一个只测试l随机赋值的随机算法。它可能根本找不到最小值，但在“线性”时间O(n*l)中运行。

哦，你可以尝试不同的随机初始化，以提高你找到全局最小值的机会。添加一个因子t来表示试验次数...

考虑一下：

.   c   .

.   c   .

其中c是集群质心。算法将停止，但更好的解决方案是：

.       .
c       c
.       .

关于证明-你不需要数学证明来证明某些东西并不总是正确的，你只需要一个反例，如上所述。您可能会将上述内容转换为数学证明，但这是不必要的，而且通常需要大量的工作；即使在学术界，也可以仅举一个反例来反驳某些东西。

根据定义，k-means算法是一个迭代过程，它的工作方式很简单。The problem of clustering is NP-hard，因此使用精确的算法来计算质心将花费非常长的时间。