以下哪个不是迭代算法的缺点_算法笔记|一文读懂Kmeans聚类算法

1、引言

什么是聚类&＃xff1f;我们通常说&＃xff0c;机器学习任务可以分为两类&＃xff0c;一类是监督学习&＃xff0c;一类是无监督学习。监督学习&＃xff1a;训练集有明确标签&＃xff0c;监督学习就是寻找问题(又称输入、特征、自变量)与标签(又称输出、目标、因变量)之间关系的学习方式。监督学习模型又可以分为两类&＃xff0c;分类和回归。分类模型&＃xff1a;目标变量是离散的分类型变量&＃xff1b;回归模型&＃xff1a;目标变量是连续性数值型变量。无监督学习&＃xff1a;只有数据&＃xff0c;无标签&＃xff0c;即训练集没有标注目标变量。常见的无监督学习算法有聚类&＃xff0c;由计算机自己找出规律&＃xff0c;把有相似属性的样本放在一组&＃xff0c;每个小组也称为簇。简单来说&＃xff0c;聚类是指根据相似数据点的属性或特征将它们分组在一起。例如&＃xff0c;如果我们有一组人的收入和支出&＃xff0c;我们可以将他们分为以下几类&＃xff1a;

• 高收入&＃xff0c;高消费

• 高收入&＃xff0c;低消费

• 低收入&＃xff0c;低消费

• 低收入&＃xff0c;高消费

2、K-means聚类

聚类算法有很多&＃xff0c;最流行的聚类算法之一是 k-means。让我们了解 k-means 算法是如何工作的&＃xff0c;以及该算法可能达不到预期的情况。K-means有一个很著名很清晰的解析&＃xff0c;就是牧师-村民模型。有四个牧师去郊区布道&＃xff0c;一开始牧师们随意选了几个布道点&＃xff0c;并且把这几个布道点的情况公告给了郊区所有的居民&＃xff0c;于是每个居民到离自己家最近的布道点去听课。听课之后&＃xff0c;大家觉得距离太远了&＃xff0c;于是每个牧师统计了一下自己的课上所有的居民的地址&＃xff0c;搬到了所有地址的中心地带&＃xff0c;并且在海报上更新了自己的布道点的位置。牧师每一次移动不可能离所有人都更近&＃xff0c;有的人发现A牧师移动以后自己还不如去B牧师处听课更近&＃xff0c;于是每个居民又去了离自己最近的布道点……就这样&＃xff0c;牧师每个礼拜更新自己的位置&＃xff0c;居民根据自己的情况选择布道点&＃xff0c;最终稳定了下来。根据上面这个故事&＃xff0c;我们可以简单来概括一下K-means算法的一般步骤&＃xff0c;K-Means聚类步骤是一个循环迭代的算法&＃xff0c;非常简单易懂&＃xff1a;Step1&＃xff1a;确定类别数量K&＃xff0c;K值人为设定&＃xff0c;在训练数据分布范围内&＃xff0c;随机选择K个点作为初始中心点&＃xff1b;Step2&＃xff1a;按照距离最小原则&＃xff0c;把所有数据点分到距离最近的中心点所在的类中&＃xff1b;step3&＃xff1a;每类中有若干个观数据点&＃xff0c;计算K个类中所有数据点的均值&＃xff0c;作为下一次迭代的中心点&＃xff1b;Step4&＃xff1a;重复step2、step3步&＃xff0c;直到收敛(每个数据点所属类别或中心点不再改变)&＃xff0c;聚类过程结束。下面我们通过一组图来直观了解一下K-means算法迭代过程&＃xff1a;初始状态随机生成了3个聚类中心点&＃xff0c;然后分别计算每一个数据点对这些中心的距离&＃xff0c;把距离最短的那个当成自己的类别。这样每个点都会对应一个中心点&＃xff0c;可以看到聚类的并不准确&＃xff0c;红色聚类中心太偏&＃xff0c;没有数据点属于该类&＃xff0c;在代码中&＃xff0c;我们会再次随机更新这个聚类中心。第一次迭代经过一次迭代之后&＃xff0c;聚类中心向该类别的数据点的中心移动。收敛状态收敛状态&＃xff0c;聚类中心移动到每个类别数据点中心&＃xff0c;继续迭代中心点位置也不在变化。

3、思考

(1)初始中心点怎么确定&＃xff1f;如果我们用欧式距离评估数据点与聚类中心的距离&＃xff0c;那么在k-means算法步骤中&＃xff0c;相当于我们一直在寻求一种最优的分割方式&＃xff0c;使得总平方误差(SSE)最小&＃xff0c;即数据点与其聚类中心的欧式距离最小。在迭代过程中&＃xff0c;从两个方面来降低SSE&＃xff1a;第一&＃xff0c;把样本点分到最近邻的簇中&＃xff0c;这样会降低SSE的值&＃xff1b;第二&＃xff0c;用均值更新聚类中心&＃xff0c;进一步的减小了SSE(以MSE为目标函数&＃xff0c;求导可知最优解即为平均数&＃xff0c;以MAE为目标函数&＃xff0c;求导可知最优解为中位数&＃xff0c;因此如果采用曼哈顿距离进行聚类&＃xff0c;更新聚类中心时&＃xff0c;我们就需要采用中位数而不是平均数更新)。这样的重复迭代、不断优化&＃xff0c;会找到局部最优解(局部最小的SSE)&＃xff0c;如果想要找到全局最优解需要找到合理的初始聚类中心。那合理的初始中心怎么选&＃xff1f;方法有很多&＃xff0c;譬如先随便选个点作为第1个初始中心C1&＃xff0c;接下来计算所有样本点与C1的距离&＃xff0c;距离最大的被选为下一个中心C2&＃xff0c;直到选完K个中心。这个算法叫做K-Means&＃43;&＃43;&＃xff0c;可以理解为 K-Means的改进版&＃xff0c;它可以能有效地解决初始中心的选取问题&＃xff0c;但无法解决离群点问题。总的来说&＃xff0c;最好解决办法还是多尝试几次&＃xff0c;即多设置几个不同的初始点&＃xff0c;从中选最优&＃xff0c;也就是具有最小SSE值的那组作为最终聚类。(2)K值怎么确定&＃xff1f;如果K过大&＃xff0c;样本划分就越细&＃xff0c;每个簇的聚合程度就越高&＃xff0c;误差平方和SSE自然就越小。所以不能单纯像选择初始点那样&＃xff0c;用不同的K来做尝试&＃xff0c;选择SSE最小的聚类结果对应的K值&＃xff0c;毫无疑问&＃xff0c;SSE最小时必然对应K的最大值。假设在我们的原始数据中&＃xff0c;其客观存在的类别数量为M&＃xff0c;当K值小于M时&＃xff0c;随着K值的增大&＃xff0c;SSE会快速下降&＃xff0c;而当K值大于M时&＃xff0c;随着K值增大&＃xff0c;SSE下降幅度会减小。如下图所示&＃xff0c;M取值事先未知&＃xff0c;K&＃61;2开始尝试&＃xff0c;发现K&＃61;3时&＃xff0c;SSE大幅下降&＃xff0c;K&＃61;4时&＃xff0c;SSE下降幅度稍微小了点&＃xff0c;K&＃61;5时&＃xff0c;下降幅度迅速降低&＃xff0c;再后面就越来越平缓。所以我们认为M取值应该为4&＃xff0c;因此可以将K设定为4。这种方法叫做“手肘法”&＃xff0c;因为SSE和K的关系图就像是手肘的形状&＃xff0c;而肘部对应的K值就被认为是数据的真实聚类数。

4、总结

k-means 聚类概念听起来不错&＃xff0c;它易于理解&＃xff0c;相对容易实现&＃xff0c;并且可以应用于很多用例中。最重要的一点是&＃xff0c;算法复杂度不高&＃xff0c;仅仅为O(s*n)&＃xff0c;s为迭代次数&＃xff0c;而一般情况下&＃xff0c;k-means算法收敛速度很快&＃xff0c;迭代次数不超过10次&＃xff0c;因此在数据集较大时&＃xff0c;k-means应用起来非常方便。但也有一些缺点和局限性需要我们注意。从上文的算例来看&＃xff0c;k-means 算法似乎运行得很好&＃xff0c;但是&＃xff0c;如果你仔细观察&＃xff0c;你会发现所有创建的簇都是圆形的。这是因为聚类中心是使用平均值迭代更新的。现在&＃xff0c;考虑下面的例子&＃xff0c;其中点的分布不是圆形的。如果我们对这些数据使用 k-means 聚类&＃xff0c;你认为会发生什么&＃xff1f;它仍然试图以循环方式对数据点进行分组。那不太好&＃xff01;k-means 无法识别正确的分类&＃xff1a;因此&＃xff0c;我们需要一种不同的方法来将数据点分配给聚类中心。因此&＃xff0c;我们不应该再使用基于距离的模型&＃xff0c;而是应该使用基于分布的模型。下一篇文章&＃xff0c;我们再来看&＃xff0c;高斯混合模型(GMM)是如何来克服K-means算法的缺点。