4.2.1　K均值算法

K均值算法就是在没有任何监督信号的情况下将数据分为K份的一种方法。

1.算法步骤

K均值算法主要分为以下几个步骤：

1）为待聚类的点随机选择K个聚类中心；

2）计算每个点到聚类中心的距离，将每个点聚类到离该点最近的类中；

3）重新计算每个类中各自的聚类中心；

4）将每个点按照新的聚类中心重新聚类；

5）反复执行步骤3和步骤4，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止。具体原理在第13章中会详细阐述。

为了将点分到最近的类中，我们需要量化考虑数据的“邻近性度量”的概念。常见的数据量化距离公式如表4-1所示。

表4-1　K均值算法：常见的邻近度、中心点和目标函数组合

2.K均值算法中遇到的问题

（1）处理空类

如果所有的点在分类步骤都未分配到某个类，就会得到空的类。在这种情况下，需要通过某种方法来选择一个替补的聚类中心，否则平方误差会偏大。一种方法是选择一个距离当前任何聚类中心都最远的点，将其删除，即消除对总平方误差影响最大的点。另一种方法是从具有最大SSE（误差平方和，即计算每个数据点到最近聚类中心的欧氏距离，计算拟合数据和原始数据对应点的误差平方和）的类中选择一个候补聚类中心，这不仅分裂了类，而且降低了聚类的总SSE。若出现多个空的类，则重复该过程。

（2）离群点

使用SSE时，离群点可能会过度影响所发现的类。当存在离群点时，该聚类中心可能不如无离群点时那样有代表性，并且SSE也比较高。因此，提前发现离群点并删除它们是有用的。但是，并非每次都要删除离群点。当使用聚类分析方法来压缩数据时，必须对每个点聚类；但在财经类应用场景中，明显的离群点（有利可图的投资者）可能是令人感兴趣的点。

那我们如何识别离群点呢？可以通过记录每个点对SSE的影响，删除那些具有巨大影响的点。

（3）聚类中心的更新

在将点每次分到相应的类之后，增量地更新聚类中心，而不是在所有的点分到类中之后才更新聚类中心。

K均值算法的优点：

·原理易懂，实现容易；

·可解释性较强。

K均值算法的缺点：

·参数K的值较难确定；

·实验过程中会出现局部最优的现象；

·对于噪声点和异常点较为敏感；

·需要知道样本的均值（为了限定数据种类）；

·对于类别规模差异太大的数据，分类效果不太好。