Kmeans 算法 收敛不了 除了把两次的距离epsilon设置小一些 还有什么办法?


RT
另外这是因为数据分布不像是给定的K个cluster导致的么
已邀请:

SuiterChik - 烫烫烫烫烫烫烫烫烫烫烫烫烫

赞同来自: LostOsiris richardzrc July 画儿 Dream_whui joice_cd Seven Noodles dolphin_zs fanjiangke sumnous 品祎 fanksids VictorGun更多 »


=============================

又到了愉快的瞎扯时间:D

=============================

啊K-means聚类啊,首先我们需要知道K-means的工作原理,然后才能知道它的缺点
大家看下面这幅图,就是二维空间下2-means的流程,我们可以从这个缩影中看出k-means的一些特点
1.png


这个图应该不需要解释吧K-means的工作原理这么简单=。=

下面我们来聊一下K-means。
我们要知道,其实K-means是一种为了简化计算以及加快收敛速度的近似算法,为什么?你看算法在距离上的定义
$$D = ||x_k - \hat{\mu}_i||^2$$
是不是很熟悉呢,对的就是欧式距离
凭什么要用欧式距离?用别的距离不行?(K-means:我乐意,不服你来打我啊)

我们下面来聊一聊用别的距离会怎么样,为了方便起见,我们就用跟欧式距离很像的马氏距离好了
$$D = (x_k - \hat{\mu}_i)^T \hat{\Sigma}_i^{-1}(x_k - \hat{\mu}_i)$$

在此之前,我们要知道,聚类究竟是要做什么,聚类可以认为是这样的
1. 样本的类别c需要知道,比如你拿到一堆没有标签的数据,他们是手写字母,那么类别就应该是26(你要是跟我扯大写小写一共52个类别就是不客观,你就是来砸场的哼)。但是如果这些数据是类别不明确的,你根本就没办法知道有多少个类别,或者本来就没有类别的概念,那么这个c就取决你了,你可以凭直觉(只要你boss不踢你滚蛋),凭经验啥的来决定c取多少,但不管怎样,这个c是一定知道的。
2. 每个类别的先验概率P(w_i)也是知道的,这个如果你其他参数都定了,那么这个参数就能算出来。
3. 样本条件概率的数学形式是以知的,即
$$p(x|w_j, \theta_j), j=1, \cdots, c$$
是知道的,可能这个形式是你本来就知道这个模型是这样,或者你猜这个模型是这样(俗称:蒙的),不管怎样,我说你知道你就是知道别抵抗!
4.参数是未知的,即我们不知道以下参数
$$\theta_1, \theta_2, \cdots, \theta_c$$
的具体取值是什么,但是他们长什么样是知道的(因为模型是知道的)

所以聚类任务就可以看做是,我知道模型,知道类别,唯独不知道类别标签,所以有监督学习与无监督学习是很像的(其实这两个的界限本来就很模糊),如果你是学自动控制的,你会发现:这TM不就是系统辨识吗?!

好像扯远了,回到我们的k-means上来,k-means实际上是一种对数似然函数空间的随机梯度法,这个一会我们我们再回来聊,我们先来解决一个问题:我们刚还扯着聚类,怎么就突然扯到似然函数了???

根据我们之前关于聚类问题的定义,我们不难得出从一个混合密度中采样到一个样本的概率为
$$p(x|\theta) = \sum\limits_{j=1}^c p(x|w_j, \theta_j)P(w_j)$$
(友情提示:你可以认为上面的式子就是,对于某个样本x,他属于A类的概率,B类的概率.....所有类别的概率之和)
如果说这时候参数θ的数值知道了,那么整个问题就解决了,但是我们不知道,所以才会有后面的一大堆问题

不知道怎么办呢?回想我们的概率论,参数不知道,那就拿极大似然去撸他咯
友情提示:如果你忘了极大似然的含义,那么你可以理解为极大似然就是,我观察到这个现象,那么我就要让参数使得我观察到这个现象出现的概率最大。
举个栗子,现在有两个人,某位低调的网红小王,以及我。还有一个参数---某位地产大亨健林先生,健林先生这个参数只能取两个值:小王的父亲、或是我的父亲,但是这个取值我们不知道。好了背景介绍完毕,现在发生了一件事,我和小王同时追一名女生,结果女生对我说“你是个好人”。那么问题来了,参数取值为什么?当然是“小王的父亲”啊,为什么?因为这个取值使得我被发好人卡的概率最大。这就是极大似然的中心思想。

好了,回到原来问题上的讨论,对于训练集合D,我们有
$$p(\mathcal{D}|\theta) = \prod\limits_{k=1}^n p(x_k|\theta)$$

当然了,我们往往都是撸对数似然的,因为连加要比连乘容易处理,所以我们有
$$l = \sum\limits_{k=1}^{n}p(x_k|\theta)$$

代入混合概率密度并求导,得到
$$\nabla_{\theta_i}l = \sum\limits_{k=1}^n \frac{1}{p(x_k|\theta)} \nabla_{\theta_i} \bigg[\sum\limits_{j=1}^c p(x|w_j, \theta_j)P(w_j)\bigg] $$
假设我们的参数θ1, θ2....是独立的,那么引入后验概率
$$p(w_i|x_k, \theta) = \frac{p(x|w_j, \theta_j)P(w_j)}{p(x_k|\theta)}$$

于是我们可以将似然函数的梯度改写成:
$$\nabla_{\theta_i}l = \sum\limits_{k=1}^{n}P(w_i|x_k, \theta)\nabla_{\theta_i}\ln p(x_k|w_i, \theta_i)$$
友情提示:这个可以反推回去的,自己试着推一下吧:D

在数学推导上,接下来就是令梯度为0,然后求解参数blahblah

================================================
上面扯了很多看似没有关联的东西,因为我们还没进入到聚类的领域上来,大家估计也看烦了
这时候你可以去刷下微博刷下朋友圈拉黑代购狗啥的,过一会儿再回来看
中场休息五分钟

e37b5cf4jw1eiizvfeafij20c81dxwi2.jpg

好了,回到我们之前的话题,我们之前讲到似然函数,大家有没有发现,上面的推导跟有监督学习的推导是一模一样的!!!!!
是的,上面的就是有监督学习的推导=。=

诶诶诶??同学!别打脸,我明天还要出门见人的

为什么说上面的是有监督的推导?因为在这里我们假定我们是知道先验概率P(w_i)的,也就是说,我们知道各个类别的出现概率的,问题就出现了,我们现在是无监督的啊,一开始就没给标签你你哪来的先验概率?

接下来我们就将上面的东西推广到P(w_i)也未知的情况,下面问题就变成了要求一组参数θ以及一组P(w)使得似然最大,且这组P(w)还要满足概率三大公理的前两条:
$$P(w_i) \geq 0, i = 1, \cdots, c, ~~~~~~~~~~~\sum\limits_{i=1}^cP(w_i) = 1$$
如果我们分别定义P(w_i)和θ的最大似然估计为:
$$\hat{P}(w_i), ~~~\hat{\theta}_i$$
那么我们有
$$\hat{P}(w_i) = \frac{1}{n} \sum\limits_{k=1}^n \hat{P}(w_i | x_k, \hat{\theta}) $$
以及
$$ \sum\limits_{k=1}^n \hat{P}(w_i | x_k, \hat{\theta}) \nabla_{\theta_i} \ln p(x_k|w_i, \hat{\theta}_i) = 0$$
其中
$$\hat{P}(w_i | x_k, \hat{\theta}) = \frac{p(x_k|w_i, \hat{\theta}_i) \hat{P}(w_i)}{\sum_{j=1}^c p(x_k|w_j, \hat{\theta}_j)\hat{P}(w_j)}$$

解释一下上面两个个式子
第一个式子:类别概率的最大似然估计是每个样本估计之和然后求平均,体现贝叶斯的思想
第二个式子:这是最大似然估计(令导数为0),体现最大似然思想

终于进入到聚类的领域了,上面这两个式子,第一个,你可以理解为k-means的第一阶段;第二个,你可以理解为k-means的第二阶段。事实上,k-means和EM算法是很像的,非常非常像,不信你仔细想想EM是不是也在做同样的事情?只不过表达换了一下而已。

好了,回到我之前说的那句话“k-means实际上是一种对数似然函数空间的随机梯度法”,现在大家应该已经知道为什么会出现似然空间这个说法了,下面我们依然不打算直接讲k-means,我们先来看下面这个图
2.png

上面三条曲线,其中实线是真实的概率密度,而两条虚线是分别是两种估计,事实上我们也不难看出,A那条曲线要比B的更准确,但是就能说A更好吗?如果我们开了上帝视角当然能这么说,但实际中我们不知道真实的密度是怎么样的,所以A和B两条曲线差不多,没有那个更好。此外,如果我们一开始类别设置错了,我们设置成了3个类别,那么得到的曲线又不一样了,所以,我们对于类别的设置也对算法起到很重要的作用。

但事实上,哪怕类别C设定准确了,也不一定能收敛到全局最优点,为什么?看下面这张马鞍面
3.png

图中的红线是迭代过程中最大似然的轨迹,如果我们初始化的位置比较好,那么可以上升到最顶点,如果不好呢?那就有可能收敛到鞍点,所以我们的观点是:多在几个不同的初始点试几次,选最好的来用。

好了回到k-means上来。在上面那个模型中,我们知道他是高斯模型,所以我们就使用马氏距离,所以对于概率
$$\hat{P}(w_i | x_k, \hat{\theta}) = \frac{p(x_k|w_i, \hat{\theta}_i) \hat{P}(w_i)}{\sum_{j=1}^c p(x_k|w_j, \hat{\theta}_j)\hat{P}(w_j)}$$
我们经过推导是可以证明它随着
$$(x_k - \hat{\mu}_i)^T \hat{\Sigma}_i^{-1}(x_k - \hat{\mu}_i)$$
的减小而增大,关于这个证明,我实在是不想敲公式了。。。原谅我。。。。。。

但如果我们换成欧式距离呢?也就是
$$ ||x_k - \hat{\mu}_i||^2$$
然后通过欧氏距离找到中心,并对概率进行简化
$$\hat{P}(w_i | x_k, \hat{\theta}) \approx 1, \text{若}i=m$$
$$\hat{P}(w_i | x_k, \hat{\theta}) \approx 0, \text{否则}$$

然后我们就得到了K-means,所以“k-means实际上是一种对数似然函数空间的随机梯度法”这种说法明白了吗?

依然是上面的曲面,我们看下它的等高线图,在k-means中,他的上升轨迹如下:
4.png

从不同的起始点,我们可以看到k-means将收敛到不同的点,大部分情况下是到全局最后点,但也有收敛到鞍点的情况。

聚类,其实是比较主观的事,比如下面这个图,我既可以说它可以分为两类,也可以说它可以分为3类,所以这种事,你开心就好
5.png


此外,聚类得到的结果也不一定是正确的,比如下面这张图,上面部分是聚类的结果,下面部分才是其真实情况
6.png


K-means简单粗暴有成效,是个挺有效果的算法,但不意味着它总能奏效,比如下面这种情况:
7.png

如果我们继续使用k-means聚类:
8.png

很显然这时候k-means就不在奏效了,对此我们有谱聚类这种算法,那个太跑题了,而且我也不太懂那块,比如下面是对上图谱聚类的结果
9.png

这其实不能说K-means就一无是处,事实上,在机器学习里,每个算法都是有用处的,只有适不适合,没有谁比谁本质上更好,比如用logistic regression就能工作得很好的工作你就没必要搬卷积神经网络这种大炮出来,而且这座大炮还不一定工作得比LR好

楼主对不起=。=
我扯了半天也没回答你的问题
对于你的问题,我觉得,可以多换几个初始值试试,关于收敛则准则有两种,一种是判断中心移动(如果你的中心已经不怎么变化了说明收敛了阿,你可以将误差记录下来看看误差下降情况),另外一种是根据迭代次数,k-means我印象中是收敛的吧=。=

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~