图解K-Means算法
本文中介绍的是一种常见的无监督学习算法,名字叫做K均值算法:K-Means算法
。
K-Means
算法在无监督学习,尤其是聚类算法中是最为基础和重要的一个算法。它实现起来非常简单。聚类效果也很不错的,因此应用非常广泛。
本文将会从以下8
个方面进行详细的讲解:
算法思想
无监督学习
在正式介绍K-Means
算法之前,我们先解释一下无监督学习。用一句很通俗的话来解释:
是否有监督(supervised),我们只需要看输入的数据是否有标签
输入的数据如果带有标签,则是有监督学习,比如KNN算法(K近邻)就是监督学习的典型算法;如果没有标签,则认为是无监督学习,比如本文中即将介绍的K-Means算法
我们看看无监督学习聚类算法的应用:
- 市场分割
- 社交网络分析
- 组织计算机集群
- 星系的形成
算法思想
K-Means
聚类算法是一种迭代求解的聚类分析算法。算法思想是:我们需要随机选择K个对象作为初始的聚类中心,然后计算每个对象和各个聚类中心之间的距离,然后将每个对象分配给距离它最近的聚类中心。
聚类中心及分配给它们的对象就代表着一个聚类。每分配一个样本,聚类的中心会根据聚类中现有的对象被重新计算。此过程将不断重复,直至满足设置的终止条件。
算法步骤
K-Means
算法的具体步骤如下:
- 首先我们需要确定一个k值(随机),即我们希望数据经过聚类得到k个不同的集合
- 从给定的数据集中随机选择K个数据点作为质心
- 对数据集中的每个点计算其与每一个质心的距离(比如欧式距离);数据点离哪个质心近,就划分到那个质心所属的集合
- 第一轮将所有的数据归号集合后,一共有K个集合,然后重新计算每个集合的质心
- 如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值,则表示重新计算的质心的位置变化不大,数据整体趋于稳定,或者说数据已经收敛。在这样的情况下,我们认为聚类效果已经达到了期望的结果,算法可终止。
- 反之,如果新质心和原来质心的距离变化很大,需要重复迭代3-5步骤,直至位置变化不大,达到收敛状态。
图解K-Means
具体步骤
1、给定需要进行聚类划分的数据集
2、随机选择2个聚类中心(K=2)
3、计算每个数据点到质心的距离,并将数据点划分到离它最近的质心的类中
4、计算2个数据集的各自的质心(红点、蓝点的均值),将聚类中心移动到均值处,变成新的聚类中心
5、找到新的聚类中心。如果
完整过程
- 在上面的过程中我们假设k=2。在图b中我们随机选择了两个类所对应的质心,也就是图中蓝色和红色质心
- 分别求出样本中每个点到这两个质心的距离,并且将每个样本所属的类别归到和该样本距离最小的质心的类别,得到图c,也就是第一轮迭代后的结果
- 我们对c图中的当前标记为红色和蓝色的点分别求出其新的质心,得到了图d,此时质心的位置发生了改变
- 图e和图f重复了图c和图d的过程,即将所有点的类别标记为距离最近的质心的类别并求新的质心。
- 一般的,
K-Means
算法需要运行多次才能达到图f的效果。
注:以上图形来自吴恩达老师在机器学习视频的讲解截图
k值选择
k值决定了我们将数据划分成多少个簇类。k个初始化的质心的位置选择对最后的聚类结果和整个大代码的运行时间都有非常大的影响。因此需要选择合适的k个质心
一般k值是通过先验知识来选取的。如果没有什么先验知识,我们可以通过交叉验证的方式来选择一个合适的k值。
距离问题
在机器学习中,我们常用的距离有以下几种:
1、两个集合之间的$x_i,x_j$的$L_p$距离定义为:
2、当p=1则表示为曼哈顿距离:
3、当p=2则表示为我们常用的欧式距离:
4、当p趋于无穷时,表示为切比雪夫距离,它是各个坐标距离的最大值:
在K-Means
算法中一般采用的是欧式距离
算法优缺点
优点
- 原理很简单,实现起来也是非常容易,算法收敛速度也很快
- 聚类效果优,可解释性强。当数据最终收敛之后,我们最终能够很清晰的看到聚类的效果
- 约束条件少。算法中需要控制的参数只有簇数k。通过对k的不断调节才能得到最好的聚类效果
缺点
- k值的选取不好把握,很多情况下K值的估计是非常困难的,有时候通过交叉验证来获取。
- 迭代的方法得到的结果只能是局部最优解,而不能得到全局最优解。
- 对噪音和异常点很敏感。异常点对质心的确定影响很大的。可以用来检测异常值。
Python实现K-Means
下面讲解一种利用Python实现k-means算法的代码:
1 | import numpy as np |
延伸学习
传统的K-Means
算法存在一些缺陷,比如K
值的选取不是很好把握、对异常数据敏感等,于是提出了很多在其基础上改进的聚类算法:
1、K-Means++(初始化优化)
针对K-Means算法中随机初始化质心的方法进行了优化
2、elkan K-Means(距离优化)
在传统的K-Means
算法中,在每轮迭代中我们都需要计算所有的样本点到质心的距离,这样是非常耗时的。
elkan K-Means
算法利用:两边之和大于等于第三边,以及两边之差小于第三边的三角形性质,来减少距离的计算。
3、Mini Batch K-Means算法(大样本优化)
在传统的K-Means
算法中,要计算所有的样本点到所有的质心的距离。现在大数据时代,如果样本量非常大,传统的算法将会非常耗时。
Mini Batch K-Means
就是从原始的样本集中随机选择一部分样本做传统的K-Means
。这样可以避免样本量太大的计算难题,同时也加速算法的收敛。当然,此时的代价就是我们最终聚类的精度会降低一些。
为了增加算法的准确性,我们一般会多跑几次Mini Batch K-Means
算法,用得到不同的随机样本集来得到聚类簇,选择其中最优的聚类簇。
参考资料
1、李航老师—《统计学习方法》一书
2、吴恩达老师—《机器学习》视频
3、刘建平老师—博客:https://www.cnblogs.com/pinard/