5.2 k-均值算法
5.2 k-均值算法
P2大家好，本次课我们学习k-均值算法，又称为k-means算法，最广为人知的用于聚类分析的方法，也是数据挖掘发展史上最成功的算法之一。以下是本次要学习的内容：k-means算法的思路、k-means算法的过程、k-means算法的实现。
P3 k-means算法的思路
k-均值算法，又称为k-means算法，是聚类分析中的重要算法，基本思路如下：
首先在 d 维实空间中随机选择 k 个点，作为 k 个簇的中心点（质心），然后反复执行下面的两个步骤。
步骤 1：为每个对象分配一个簇。将每个对象分配到距离它最近的那个中心点（质心）所代表的簇中
步骤 2：重新计算每个簇的代表点位置。根据步骤 1，每个簇的中心点（质心）的位置将更新为这个簇中所有对象的平均位置。也就是说，各簇的中心点的位置将得到更新。
k-均值算法反复执行步骤 1 和步骤 2，直到收敛。在执行步骤 1 的时候，如果每个对象所分配的新簇标号和原来的簇一样，那就收敛了。可以证明，k-均值算法一定会在有限步内收敛，并且一般而言，k-均值的收敛速度是很快的。
P4邮件类别划分的K-均值算法
这个例子中，数据集中有1000 封邮件，每封邮件被 d=57 个特征（维度）刻画，每个邮件属于三个给定类别中的一类。为了方便可视化显示，我们对数据进行降维操作，把原来的高维数据降到2维。降维后的数据分布情况如图所示，其中每个数据点代表二维特征平面上的一封邮件，不同颜色表示邮件的不同类别。图中黄色、黑色、红色点代表三类邮件，故K-均值算法中的K=3。
P5 如图所示，在开始的时候，每个数据点的类别都是未知的。 k-均值算法的第一步是初始化簇代表，我们从数据中随机选出 3 个点作为初始的簇代表点（后称簇中心）。在后续的图中，每个簇中心用红色点表示，每种颜色代表一个簇，所有被分配到该簇中的点都是用同一种颜色表示。在图中，由于所有数据点都还没有被分配簇中心标记，故所有数据暂时使用黑色表示。
P6接下来，将其他997个点与选中的三个中心点分别计算距离，从而每个数据点分配到距其最近的簇中心，并将在同一个簇的数据标记上相同的颜色，如图所示。然后，用当前所有被分配到该簇数据点的均值来作为新的簇中心，更新后簇中心的位置如图所示。红色圆圈中的红色点即为其最新的中心点位置，注意与上页最初的中心位置是不同的了。
P7第 1 次迭代后的结果, 注意每次迭代后，类别边界处的点的颜色是有变化的，重新计算后的中心点位置也是在变化的。由于随机初始化的簇中心往往具有较大的随机性，故在第一次迭代时，簇中心会出现较大幅度的移动。 为了强化表示，图中把移动的轨迹用红色的箭头标识。
P8下面是 k-均值算法的第二步。k-均值算法反复将每个数据点分配到离其最近的簇中心，同时根据每次的分配结果更新所有簇中心的位置。如图所示为第2次迭代、第11次迭代后的结果图。请大家比较两图的区别，重点在类别边界处的点的颜色是有变化的，重新计算后的中心点位置也是在变化的。如此反复，直至聚类结果不再变化，或者其变化量在可以容忍的范围内，则停止整个迭代过程。事实上，经过 11 次迭代，算法收敛，聚类结果不再变化。我们得到的最终聚类结果。
P9 k-均值算法的过程
k-均值算法的过程是这样的，
① 首先输入k的值，即希望将数据集D=经过聚类得到k个分类或分组。
② 从数据集D中随机选择k个数据点作为簇质心，每个簇质心代表一个簇。这样得到的簇质心集合。
③ 对D中每一个数据点，计算其与每个簇质心的距离，得到一组距离值，从中找出最小距离值对应的簇质心，则将数据点划分到此质心所在的簇中。
P10:
④ 根据每个簇所包含的对象集合，重新计算得到一个新的簇质心。
⑤ 如果这样划分后满足目标函数的要求，可以认为聚类已经达到期望的结果，算法终止。否则需要迭代③到⑤步骤。
P11下面给出K均值算法的过程示例。如图所示的K均值算法是如何实现的呢？
P12 如图所示给出的例子，是二维空间中的10个数据点（数据对象集），采用欧几里得距离，进行2-均值聚类。其过程如下：
P13 （1）k=2，随机选择两个点作为质心，假设选取的质心在图中用实心圆点表示。
（2）第一次迭代，将所有点按到质心的距离进行划分，其结果如图所示。
P14 （3）假设这样划分后不满足目标函数的要求，重新计算质心，如图所示，得到两个新的质心。
P15 （4）第2次迭代，其结果如图所示。
（5）假设这样划分后满足目标函数的要求，则算法结束，第2次划分的结果即为所求；否则还需要继续迭代。
P16 k-均值算法的实现
输入：数据对象集合D，簇数目k，阈值ε
输出：k个簇的集合
方法：其过程描述如图所示，注意算法中使用了一个while无限循环函数，中间使用了两个for循环，算法是使用了伪代码来实现的。
P17 k-均值算法的局限性
k-均值算法是一种既简单又好用的方法，原理简单，容易实现，可解释度较强，基本上可以拿来即用。k均值算法主要的缺陷有以下几种：
1. K值很难确定，需要预先给定，属于预先知识，很多情况下K值的估计是非常困难的，对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行。
2. K-Means算法对初始选取的聚类中心点是敏感的，不同的随机种子点得到的聚类结果完全不同
3. K均值算法并不适用所有的数据类型。它不能处理非球形簇、不同尺寸和不同密度的簇。
4. 对离群点的数据进行聚类时，K均值也有问题，这种情况下，离群点检测和删除有很大的帮助。
k-均值算法还存在一些其他问题。例如，k-均值算法对于噪音点特别是偏离很远的异常点非常敏感，这是因为它采用了距离的平方作为相似性的度量。要克服这个问题， 就需要采用不同的相似性定义， 如距离的绝对值， 但这时就不能用 k-均值的方法来做优化。另外，k-均值只擅长处理凸形的数据点分布，对于长相怪异的非凸数据分布常常无能为力，这时我们往往需要使用基于密度的方法。
P18二分k-均值算法
如图所示，二分k-均值算法是基本k-均值算法的直接扩充，它基于一种简单的想法：为了得到k个簇，将所有点的集合分为两个簇，从这些簇中选取一个继续分裂，如此下去，直到产生k个簇。
P19二分k-均值算法
二分k-均值算法的实现较容易理解，输入：数据对象集合D，簇数目k，二分次数b
输出：k个簇的集合，其过程描述如图所示，注意算法使用伪代码实现的。
P20总结
好了，到此本次课就要结束了，我们做一个简短的回顾。k-均值算法是一种简单的迭代型聚类算法，采用距离作为相似性指标，从而发现给定数据集中的K个类，且每个类的中心是根据类中所有值的均值得到，每个类用聚类中心来描述。对于给定的一个包含n个d维数据点的数据集X，以及要分得的类别K,选取欧式距离作为相似度指标，聚类目标是使得各类的聚类平方和最小，即最小化。结合最小二乘法和拉格朗日原理，聚类中心为对应类别中各数据点的平均值，同时为了使得算法收敛，在迭代过程中，应使最终的聚类中心尽可能的不变。好，这次课到此结束，谢谢！