【学习】K-means聚类算法

背景

K-means也是聚类算法中最简单的一种了,但是里面包含的思想却是不一般。最早我使用并实现这个算法是在学习韩爷爷那本数据挖掘的书中,那本书比较注重应用。看了Andrew Ng的这个讲义后才有些明白K-means后面包含的EM思想。

聚类属于无监督学习,以往的回归、朴素贝叶斯、SVM等都是有类别标签y的,也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y,只有特征x,比如假设宇宙中的星星可以表示成三维空间中的点集。聚类的目的是找到每个样本x潜在的类别y,并将同类别y的样本x放在一起。比如上面的星星,聚类后结果是一个个星团,星团里面的点相互距离比较近,星团间的星星距离就比较远了。

在聚类问题中,给我们的训练样本是,每个,没有了y。

算法

K-means算法是将样本聚类成k个簇(cluster),具体算法描述如下:

1、 随机选取k个聚类质心点(cluster centroids)为。2、 重复下面过程直到收敛 {对于每一个样例i,计算其应该属于的类对于每一个类j,重新计算该类的质心

K是我们事先给定的聚类数,代表样例i与k个类中距离最近的那个类,的值是1到k中的一个。质心代表我们对属于同一个类的样本中心点的猜测,拿星团模型来解释就是要将所有的星星聚成k个星团,首先随机选取k个宇宙中的点(或者k个星星)作为k个星团的质心,然后第一步对于每一个星星计算其到k个质心中每一个的距离,然后选取距离最近的那个星团作为,这样经过第一步每一个星星都有了所属的星团;第二步对于每一个星团,重新计算它的质心(对里面所有的星星坐标求平均)。重复迭代第一步和第二步直到质心不变或者变化很小。

下图展示了对n个样本点进行K-means聚类的效果,这里k取2。

K-means面对的第一个问题是如何保证收敛,前面的算法中强调结束条件就是收敛,可以证明的是K-means完全可以保证收敛性。下面我们定性的描述一下收敛性,我们定义畸变函数(distortion function)如下:

J函数表示每个样本点到其质心的距离平方和。K-means是要将J调整到最小。假设当前J没有达到最小值,那么首先可以固定每个类的质心,调整每个样例的所属的类别来让J函数减少,同样,固定,调整每个类的质心也可以使J减小。这两个过程就是内循环中使J单调递减的过程。当J递减到最小时,和c也同时收敛。(在理论上,可以有多组不同的和c值能够使得J取得最小值,但这种现象实际上很少见)。

由于畸变函数J是非凸函数,意味着我们不能保证取得的最小值是全局最小值,也就是说k-means对质心初始位置的选取比较感冒,但一般情况下k-means达到的局部最优已经满足需求。但如果你怕陷入局部最优,那么可以选取不同的初始值跑多遍k-means,然后取其中最小的J对应的和c输出。

K-means与EM

下面累述一下K-means与EM的关系,首先回到初始问题,我们目的是将样本分成k个类,其实说白了就是求每个样例x的隐含类别y,然后利用隐含类别将x归类。由于我们事先不知道类别y,那么我们首先可以对每个样例假定一个y吧,但是怎么知道假定的对不对呢?怎么评价假定的好不好呢?我们使用样本的极大似然估计来度量,这里是就是x和y的联合分布P(x,y)了。如果找到的y能够使P(x,y)最大,那么我们找到的y就是样例x的最佳类别了,x顺手就聚类了。但是我们第一次指定的y不一定会让P(x,y)最大,而且P(x,y)还依赖于其他未知参数,当然在给定y的情况下,我们可以调整其他参数让P(x,y)最大。但是调整完参数后,我们发现有更好的y可以指定,那么我们重新指定y,然后再计算P(x,y)最大时的参数,反复迭代直至没有更好的y可以指定。

这个过程有几个难点,第一怎么假定y?是每个样例硬指派一个y还是不同的y有不同的概率,概率如何度量。第二如何估计P(x,y),P(x,y)还可能依赖很多其他参数,如何调整里面的参数让P(x,y)最大。这些问题在以后的篇章里回答。

这里只是指出EM的思想,E步就是估计隐含类别y的期望值,M步调整其他参数使得在给定类别y的情况下,极大似然估计P(x,y)能够达到极大值。然后在其他参数确定的情况下,重新估计y,周而复始,直至收敛。

上面的阐述有点费解,对应于K-means来说就是我们一开始不知道每个样例对应隐含变量也就是最佳类别。最开始可以随便指定一个给它,然后为了让P(x,y)最大(这里是要让J最小),我们求出在给定c情况下,J最小时的(前面提到的其他未知参数),然而此时发现,可以有更好的(质心与样例距离最小的类别)指定给样例,那么得到重新调整,上述过程就开始重复了,直到没有更好的指定。这样从K-means里我们可以看出它其实就是EM的体现,E步是确定隐含类别变量,M步更新其他参数来使J最小化。这里的隐含类别变量指定方法比较特殊,属于硬指定,从k个类别中硬选出一个给样例,而不是对每个类别赋予不同的概率。总体思想还是一个迭代优化过程,有目标函数,也有参数变量,只是多了个隐含变量,确定其他参数估计隐含变量,再确定隐含变量估计其他参数,直至目标函数最优。

PPV课其他精彩文章:


1、回复“干货”查看干货 数据分析师完整知识结构

2、回复“答案”查看大数据Hadoop面试笔试题及答案

3、回复“设计”查看这是我见过最逆天的设计,令人惊叹叫绝

4、回复“可视化”查看数据可视化专题-数据可视化案例与工具

5、回复“禅师”查看当禅师遇到一位理科生,后来禅师疯了!!知识无极限

6、回复“啤酒”查看数据挖掘关联注明案例-啤酒喝尿布

7、回复“栋察”查看大数据栋察——大数据时代的历史机遇连载

8、回复“数据咖”查看数据咖——PPV课数据爱好者俱乐部省分会会长招募

9、回复“每日一课”查看【每日一课】手机在线视频集锦

PPV课大数据ID: ppvke123 (长按可复制)

大数据人才的摇篮!专注大数据行业人才的培养。每日一课,大数据(EXCEL、SAS、SPSS、Hadoop、CDA)视频课程。大数据资讯,每日分享!数据咖—PPV课数据爱好者俱乐部!

原文发布于微信公众号 - PPV课数据科学社区(ppvke123)

原文发表时间:2015-07-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

斯坦福完全可解释深度神经网络:你需要用决策树搞点事

54560
来自专栏CVer

[计算机视觉论文速递] 2018-03-09

通知:这篇推文有19篇论文速递信息,涉及图像分类、目标检测、目标分割、超分辨率SR、姿态估计、行人重识别Re-ID等方向 [1]《A Deep Learning...

382100
来自专栏专知

【BicycleGAN】NIPS 2017论文图像转换多样化,大幅提升pix2pix生成图像效果

【导读】你一定记得非常热门的加州大学伯克利分校在CVPR2017上提出的图片翻译 pix2pix,它使用GAN方法可以将白马“转化”为斑马,可以把积木“转化”为...

2.8K60
来自专栏Coding迪斯尼

深度学习:透过神经网络的内在灵活与柏拉图的哲学理念

15730
来自专栏人工智能

深度学习如何在医学影像分割上大显神通?——分割网络的三个改进思路

一、医学影像分割有助于临床工作 图像分割在影像学诊断中大有用处。自动分割能帮助医生确认病变肿瘤的大小,定量评价治疗前后的效果。除此之外,脏器和病灶的识别和甄别也...

3.7K120
来自专栏AI科技大本营的专栏

干货 | 目标检测入门,看这篇就够了(下)

? 作者 | 李家丞( 同济大学数学系本科在读,现格灵深瞳算法部实习生) 近年来,深度学习模型逐渐取代传统机器视觉方法而成为目标检测领域的主流算法,本系列文...

71480
来自专栏机器学习AI算法工程

通俗的将Xgboost的原理讲明白

初看Xgboost,翻了多篇博客发现关于xgboost原理的描述实在难以忍受,缺乏逻辑性,写一篇供讨论。 观其大略,而后深入细节,一开始扎进公式反正我是觉得效...

1.4K60
来自专栏AI研习社

详解基于朴素贝叶斯的情感分析及Python实现

相对于「 基于词典的分析 」,「 基于机器学习 」的就不需要大量标注的词典,但是需要大量标记的数据,比如: 还是下面这句话,如果它的标签是: 服务质量 - 中 ...

45780
来自专栏SIGAI学习与实践平台

OCR技术简介

光学字符识别(Optical Character Recognition, OCR)是指对文本资料的图像文件进行分析识别处理,获取文字及版面信息的过程。亦即将图...

4.1K10
来自专栏人工智能头条

卷积神经网络模型如何辨识裸体图片

26850

扫码关注云+社区

领取腾讯云代金券