cluster-analysis - 为什么 k-means 不给出全局最小值？

Question

我读到 k-means 算法只收敛到局部最小值而不是全局最小值。为什么是这样？我可以从逻辑上想到初始化如何影响最终的聚类，并且存在次优聚类的可能性，但我没有找到任何可以在数学上证明这一点的东西。

另外，为什么 k-means 是一个迭代过程？
我们不能只是部分地区分目标函数 w.r.t.到质心，将其等于零以找到最小化此函数的质心？为什么一定要使用梯度下降一步步达到最小值？

Answer 1

考虑:

.   c   .

.   c   .

其中 c 是聚类质心。算法会停止，但更好的解决方案是:

.       .
c       c
.       .

关于证明 - 您不需要数学证明来证明某些事情并不总是正确的，您只需要一个反例，如上所述。你大概可以把上面的转换成数学证明，但这是不必要的，通常需要大量的工作；即使在学术界，仅仅举一个反例来反驳某事也是被接受的。

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