6.2 基于K-Means聚类算法

K平均算法是一种无监督的机器学校算法。K-平均聚类与K-邻近之间没有任何关系。K-Means的核心思想是人以类聚；而KNN的核心思想是少数服从多数。

6.2.1 应用实例：新闻聚类

对新闻聚类，目的是尽可能使相同类别的新闻聚合在一个聚类中，一边网民浏览。

6.2.2 逻辑流程

K-Means是一种基于自下而上的聚类分析方法，基本概念就是空间中有N个点，初始选择K个点作为中心聚类点，将N个点分别与K个点计算距离，选择自己最近的点作为自己的中心点，不断地更新中心聚集点。

K-Means找到的中心一定是自然聚簇的中，这点与EM算法有雷同，其具体算法流程如下：

1、从数据点集合中，随机选择K个点作为初始的聚集中心。每个中心点，代表着每个聚集中心的平均值。

2、对其余的数据点，依次判断它与K个中心点的距离，距离最近的表明它属于这项聚类。

3、重新计算新的聚簇集合的平均值即中心点。整个过程不断迭代计算，直到达到预先设定的迭代次数或中心点不再频繁波动。

6.2.3 K-Means聚类分析的优缺点

优：非常简单快速地完成聚类工作，K-Means聚类后的聚类簇相对密集，且类别与类别之间的区别相对明显，效果较好。

缺：

1、对异常值、摇摆值比较敏感，导致收敛变慢。

2、非常不适合分布均匀、数据界限不明晰的聚类，这样的聚类效果比较差。

3、初始中心点的选择对迭代次数影响较大，如果是随机选择的初始中心点，很容易计算周期过长，如随机选取的初始中心点均同一个聚类簇时，则计算量相对较大。

4、需要提前确定聚类簇的K值，优时不知道数据可能存在的聚类个数，对于经验比较丰富的算法工程师而言，过程常常时以经验确定的值，而经验来自于对数据分布的感觉，但经验不一定代表着准确，仍然需要时间去调整K值。

6.2.4 K-Means++

K-Means++算法的工作流程基本上同K-Means类似，不同点在于选择初始中心点的方式。

K-Means初始中心是随机的方式选择产生的。

K-Means++算法是在选择初始中心之前，对所有数据进行了一次计算，使得选择的初始聚类中心之间的距离尽可能的远。这样的目的在于减少计算的过程量（初始中心点距离较大，属于同一个聚簇的可能小，能很好地分开，计算量也会相应减少）。

6.2.5 K-中心点聚类算法

K-Medoids算法的基本思想和K-Means相同，也是通过不断迭代得到数据的聚类结果，采用点到中心聚类的绝对差之和来度量聚类效果的好坏，实现步骤如下：

1、确定聚类的个数K。

2、在所有数据集合中选择K个点作为各个聚簇的中心点。

3、计算其余所有点到K个中心点的距离，并把每个点到K个中心点最短的聚簇作为自己所属的聚簇。

4、在每个聚簇中按照顺序依次选取点，计算该点到当前聚簇中所有点距离之和，最终距离之后最小的点，则视为新的中心点。

5、重复2、3步骤，直到各个聚簇的中心点不再改变。

第4步是对K-Means算法中中心点选择的改进，K-Means算法选择中心点时是通过计算某点到其他所有点的平均距离最短的点，而K-Medoids算法计算的是某点到其他所有点的距离之和最小的点。好处：通过距离之和最短的计算方式可以减少某些孤立数据对聚类过程的影响，从而使得最终效果接近真实划分（减少异常数据对结果的影响）。缺点：计算量会相对大于K-Means，大约增加O(n)的计算量，因此一般情况下K-Medoids算法根据适合小规模数据运算。

6.2.6 ISODATA聚类算法

ISODATA聚类算法（迭代式自组织数据分析算法）和K-Means算法是相似的算法，都是属于无监督的聚类分析方法。ISODATA算法有效地解决了K值需要预先设定的问题。为此，ISODATA算法在中间过程中增加了对聚类结果的“合并”和“分裂”两个操作，简单地说即是，当两个聚簇中心的距离小于某个阈值时，将两个聚簇合并为一个类别；当某个聚簇内的标准差小于一定阈值时或者聚簇内样本数量超过一定阈值时，则将该聚簇分裂为两个聚簇，甚至在当某个聚簇中的样本数量小于一定阈值时，取消该聚簇。通过“合并”和“分裂”使得达到较好的聚类效果。

ISODATA算法通过试探性的方式有效地处理聚类时K值得问题，利用聚簇中心之间的距离、聚簇内的样本数量及样本标准标准差参与样本聚类分析。