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

  统计/机器学习 最优化 无监督学习    浏览次数: 199
1

做K Means的时候,我们需要多次随机选取初始点,进行迭代,从而得到一个最佳的聚类。这么做是为了防止K Means陷入局部最小值。

我的问题是K Means为什么不能收敛到全局最优点?它的目标函数不是凸的吗?

 

dsjobhunter   2018-09-03 12:57



   1个回答 
6

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。


Zealing   2018-09-11 01:01

感谢!链接也很有帮助! - dsjobhunter   2018-09-13 03:04


  相关主题

K-MEANS初始点选择的问题   2回答

K Means初始点必须是样本中的点吗   2回答

通俗地解释c-means以及fuzzy c-means是什么意思   1回答

如何用K Means做异常点检测?   1回答

k-medoids和k-means区别   3回答

关于小批量K均值(mini-batch K Means)的问题   2回答

Jenks和K Means在一维数据时,是不是等价的?   2回答

K-means怎么选K?   6回答

二分法K Means的算法是什么?和普通的K Means有什么区别?   2回答

进行K-Means聚类前,需要对数据做怎样的预处理?   1回答

sklearn.cluster.KMeans可以用其他距离吗?   2回答

sklearn kmeans里的n_init是什么意思   2回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!