用人话讲明白聚类算法kmeans

目录

1.什么是聚类

2.K-Means步骤

3.K-Means的数学描述

4.初始中心点怎么确定

5.K值怎么确定

6.小结


1.什么是聚类

先来回顾一下开篇就讲到的机器学习的种类。

监督式学习:训练集有明确答案,监督学习就是寻找问题(又称输入、特征、自变量)与答案(又称输出、目标、因变量)之间关系的学习方式。监督学习模型有两类,分类和回归。

• 分类模型:目标变量是离散的分类型变量;
• 回归模型:目标变量是连续性数值型变量。

无监督学习:只有数据,无明确答案,即训练集没有标注目标变量。常见的无监督学习算法有聚类(clustering),由计算机自己找出规律,把有相似属性的样本放在一组,每个小组也称为簇(cluster)。

最早的聚类分析是在考古分类、昆虫分类研究中发展起来的,目的是找到隐藏于数据中客观存在的“自然小类”,“自然小类”具有类内结构相似、类间结构差异显著的特点,通过刻画“自然小类”可以发现数据中的规律、揭示数据的内在结构

之前一起学了回归算法中超级典型的线性回归,分类算法中非常难懂的SVM,这两都是有监督学习中的模型,那今天就来看看无监督学习中最最基础的聚类算法——K-Means Cluster吧。


2.K-Means步骤

K-Means聚类步骤是一个循环迭代的算法,非常简单易懂:

  1. 假定我们要对N个样本观测做聚类,要求聚为K类,首先选择K个点作为初始中心点
  2. 接下来,按照距离初始中心点最小的原则,把所有观测分到各中心点所在的类中;
  3. 每类中有若干个观测,计算K个类中所有样本点的均值,作为第二次迭代的K个中心点;
  4. 然后根据这个中心重复第2、3步,直到收敛(中心点不再改变或达到指定的迭代次数),聚类过程结束。


以二维平面中的点X_{i}=(x_{i1},x_{i2}),i=1,...,n为例,用图片展示K=2时的迭代过程:

  1. 现在我们要将(a)图中的n个绿色点聚为2类,先随机选择蓝叉和红叉分别作为初始中心点;
  2. 分别计算所有点到初始蓝叉和初始红叉的距离,X_{i}=(x_{i1},x_{i2})距离蓝叉更近就涂为蓝色,距离红叉更近就涂为红色,遍历所有点,直到全部都染色完成,如图(b);
  3. 现在我们不管初始蓝叉和初始红叉了,对于已染色的红色点计算其红色中心,蓝色点亦然,得到第二次迭代的中心,如图(c );
  4. 重复第2、3步,直到收敛,聚类过程结束。


怎么样,很简单吧?看完K-Means算法步骤的文字描述,我们可能会有以下疑问:

  1. 第一步中的初始中心点怎么确定?随便选吗?不同的初始点得到的最终聚类结果也不同吗?
  2. 第二步中点之间的距离用什么来定义?
  3. 第三步中的所有点的均值(新的中心点)怎么算?
  4. K怎么选择


3.K-Means的数学描述

我们先解答第2个和第3个问题,其他两个问题放到后面小节中再说。

聚类是把相似的物体聚在一起,这个相似度(或称距离)是用什么来度量的呢?这又得提到我们的老朋友——欧氏距离

给定两个样本X=(x_{1},x_{2},...,x_{n})Y=(y_{1},y_{2},...,y_{n}),其中n表示特征数 ,X和Y两个向量间的欧氏距离(Euclidean Distance)表示为:
dist_{ed}(X,Y)=||X-Y||_{2}=\sqrt[2]{(x_{1}-y_{1})^{2}+...+(x_{n}-y_{n})^{2}}


k-means算法是把数据给分成不同的簇,目标是同一个簇中的差异小,不同簇之间的差异大,这个目标怎么用数学语言描述呢?我们一般用误差平方和作为目标函数(想想线性回归中说过的残差平方和、损失函数,是不是很相似),公式如下:

SSE=\sum_{i=1}^{K} \sum_{x \in C_{i}}\left(C_{i}-x\right)^{2}

其中C表示聚类中心,如果x属于Ci这个簇,则计算两者的欧式距离,将所有样本点到其中心点距离算出来,并加总,就是k-means的目标函数。实现同一个簇中的样本差异小,就是最小化SSE。

我们知道,可以通过求导来求函数的极值,我们对SSE求偏导看看能得到什么结果:

\begin{aligned} \frac{\partial}{\partial C_{k}} S S E &=\frac{\partial}{\partial C_{k}} \sum_{i=1}^{K} \sum_{x \in C_{i}}\left(C_{i}-x\right)^{2} \\ &=\sum_{i=1}^{K} \sum_{x \in C_{i}} \frac{\partial}{\partial C_{k}}\left(C_{i}-x\right)^{2} \\ &=\sum_{x \in C_{i}} 2\left(C_{i}-x\right)=0 \end{aligned}

\sum_{x \in C_{i}} 2\left(C_{i}-x\right)=0 \Rightarrow m_{i} C_{i}=\sum_{x \in C_{i}} x \Rightarrow C_{i}=\frac{1}{m_{i}} \sum_{x \in C_{i}} x
式中m是簇中点的数量,发现了没有,这个C的解,就是X的均值点。多点的均值点应该很好理解吧,给定一组点X_{1},...,X_{m},其中X_{i}=(x_{i1},x_{i2},...,x_{in}),这组点的均值向量表示为:
C=(\frac{x_{11}+...+x_{1n}}{m},...,\frac{x_{m1}+...+x_{mn}}{m})


4.初始中心点怎么确定

在k-means算法步骤中,有两个地方降低了SSE:

  1. 把样本点分到最近邻的簇中,这样会降低SSE的值;
  2. 重新优化聚类中心点,进一步的减小了SSE。

这样的重复迭代、不断优化,会找到局部最优解(局部最小的SSE),如果想要找到全局最优解需要找到合理的初始聚类中心。

那合理的初始中心怎么选?

方法有很多,譬如先随便选个点作为第1个初始中心C1,接下来计算所有样本点与C1的距离,距离最大的被选为下一个中心C2,直到选完K个中心。这个算法叫做K-Means++,可以理解为 K-Means的改进版,它可以能有效地解决初始中心的选取问题,但无法解决离群点问题

我自己也想了一个方法,先找所有样本点的均值点,计算每个点与均值点的距离,选取最远的K个点作为K个初始中心。当然,如果样本中有离群点,这个方法也不佳。

总的来说,最好解决办法还是多尝试几次,即多设置几个不同的初始点,从中选最优,也就是具有最小SSE值的那组作为最终聚类。


5.K值怎么确定

要知道,K设置得越大,样本划分得就越细,每个簇的聚合程度就越高,误差平方和SSE自然就越小。所以不能单纯像选择初始点那样,用不同的K来做尝试,选择SSE最小的聚类结果对应的K值,因为这样选出来的肯定是你尝试的那些K值中最大的那个。

确定K值的一个主流方法叫“手肘法”。

如果我们拿到的样本,客观存在J个“自然小类”,这些真实存在的小类是隐藏于数据中的。三维以下的数据我们还能画图肉眼分辨一下J的大概数目,更高维的就不能直观地看到了,我们只能从一个比较小的K,譬如K=2开始尝试,去逼近这个真实值J。

  • 当K小于样本真实簇数J时,K每增大一个单位,就会大幅增加每个簇的聚合程度,这时SSE的下降幅度会很大;
  • 当K接近J时,再增加K所得到的聚合程度回报会迅速变小,SSE的下降幅度也会减小;
  • 随着K的继续增大,SSE的变化会趋于平缓。

例如下图,真实的J我们事先不知道,那么从K=2开始尝试,发现K=3时,SSE大幅下降,K=4时,SSE下降幅度稍微小了点,K=5时,下降幅度急速缩水,再后面就越来越平缓。所以我们认为J应该为4,因此可以将K设定为4。


叫“手肘法”可以说很形象了,因为SSE和K的关系图就像是手肘的形状,而肘部对应的K值就被认为是数据的真实聚类数

当然还有其他设定K值的方法,这里不赘述,总的来说还是要结合自身经验多做尝试,要知道没有一个方法是完美的。

而且,聚类有时是比较主观的事,比如下面这组点,真实簇数J是几呢?我们既可以说J=3,也可以就把它分成2个簇。


6.小结

K-Means优点在于原理简单,容易实现,聚类效果好。

当然,也有一些缺点:

  1. K值、初始点的选取不好确定;
  2. 得到的结果只是局部最优;
  3. 受离群值影响大

每个算法都有自己的特点,所以要多学习,掌握不同算法的逻辑、作用、应用场景和优缺点。这样的话,在需要解决实际问题时,就容易结合自身经验,选出最合适的算法模型来达到自己的目标。


参考链接

k-means算法原理以及数学知识
K-means聚类最优k值的选取


本文首发于知乎:机器学习笔记04-KMeans

文中图片的水印网址为本人CSDN博客地址:BeSimple

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,126评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,254评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,445评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,185评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,178评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,970评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,276评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,927评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,400评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,883评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,997评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,646评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,213评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,204评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,423评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,423评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,722评论 2 345

推荐阅读更多精彩内容