K Means为什么不能收敛到全局最优点？

Kmeans不是Convex optimization。参考这里

$\min J=\min\sum_{i=1}^{N}\min_{k=1}^{K}||x_i-\mu_k||_2^2$

这里$\mu_k$是第$k$均值。

Kmeans分为两步交替进行：

1.确定每个点属于哪个cluster，$\min_{k=1}^{K}||x_i-\mu_k||_2^2$

2.更新均值$\mu_k=mean_{i\in c_k}(x_i)$

注意第一步里的优化问题，如果一个函数求两个convex函数的最小值，那么它不是convex函数。举个例子，$\mu_1=[1,1],\mu_2=[-1,-1]$，

$$z=\min_{k=1}^{2}||x_i-\mu_k||_2^2$$

$z$的等高线是

这明显有两个全局最低点，不是convex/concave。

Kmeans对初始均值$\mu_k$的选择非常敏感，所以会尝试选择多个初始值，并选一个结果最好的。

有一些研究是对$\mu_k$加一些限制，把整个问题变成宽松的convex。