K-Means聚类算法_kmeans聚类算法

什么是聚类分析

聚类分析是数据挖掘中一个重要概念，其核心是寻找数据对象中隐藏的有价值的信息，根据相似性原则，把具有较高相似度的数据对象划分到同一类簇，把具有较高相异度的数据对象划分到不同类簇，从而使相同组中的数据点之间比其他组中的数据点更具有相似性。

聚类算法

典型的聚类算法分为三个阶段，主要包括

• 特征选择和特征提取
• 数据对象间相似度计算
• 根据相似度将数据对象分组

聚类算法可以分为两大类：

• 层次聚类算法
• 划分聚类算法。

层次聚类算法通过不同类别间的数据对象的相似度试图构建一个高层次的嵌套聚类树结构，聚类树的构建有两种类型凝聚型层次聚类（自底向上的方式构建树结构）和分裂型层次聚类（自顶向下的方式构建树结构）。

划分聚类算法需要预先指定聚类数目和聚类中心，通过优化一些损失函数，将数据集分成若干互不相交的簇。

K-Means聚类算法

01 K-Means聚类算法原理

K-Means算法是一种典型的基于划分的聚类算法，也是一种无监督学习算法。K-Means算法的思想很简单，对给定的样本集，用欧氏距离作为衡量数据对象间相似度的指标，相似度与数据对象间的距离成反比，相似度越大，距离越小。

预先指定初始聚类数以及个初始聚类中心，按照样本之间的距离大小，把样本集划分为个簇根据数据对象与聚类中心之间的相似度，不断更新聚类中心的位置，不断降低类簇的误差平方和（Sum of Squared Error，SSE），当SSE不再变化或目标函数收敛时，聚类结束，得到最终结果。

K-Means算法的核心思想：首先从数据集中随机选取k个初始聚类中心Ci（i≤1≤k），计算其余数据对象与与聚类中心Ci的欧氏距离，找出离目标数据对象最近的聚类中心Ci，并将数据对象分配到聚类中心Ci所对应的簇中。然后计算每个簇中数据对象的平均值作为新的聚类中心，进行下一次迭代，直到聚类中心不再变化或达到最大的迭代次数时停止。

空间中数据对象与聚类中心间的欧氏距离计算公式为：

其中，X为数据对象；Ci为第i个聚类中心；m为数据对象的维度；Xj，Cij为X和Ci的第j个属性值。

整个数据集的误差平方和SSE计算公式为：

其中，SSE的大小表示聚类结果的好坏；k为簇的个数。

02 K-Means聚类算法步骤

K-Means聚类算法步骤实质是EM算法（最大期望算法（Expectation-Maximization algorithm, EM）)的模型优化过程，具体步骤如下：

（1）随机选择k个样本作为初始簇类的均值向量；

（2）将每个样本数据集划分离它距离最近的簇；

（3）根据每个样本所属的簇，更新簇类的均值向量；

（4）重复（2）（3）步，当达到设置的迭代次数或簇类的均值向量不再改变时，模型构建完成，输出聚类算法结果。

03 K-Means算法迭代过程

K-Means聚类算法是一个不断迭代的过程，如图所示，原始数据集有4个簇，图中和分别代表数据点的横纵坐标值，使用K-Means算法对数据集进行聚类，在对数据集经过两次迭代后得到最终的聚类结果，迭代过程如下图所示。

（a）原始数据

（b）随机选择初始中心

（c）第一次迭代

（d）第二次迭代

（e）最终结果

K-Means聚类算法的缺陷

该算法非常简单且使用广泛，但是主要存在以下四个缺陷：

• 1.K值需要预先给定，属于预先知识，很多情况下K值的估计是非常困难的，对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行。对于可以确定K值不会太大但不明确精确的K值的场景，可以进行迭代运算，然后找出对应的K值，这个值往往能较好地描述有多少个簇类；
• 2.K-Means算法对初始选取的聚类中心点是敏感的，不同的随机种子点得到的聚类结果完全不同；
• 3.该算法并不适合所有的数据类型。它不能处理非球形簇、不同尺寸和不同密度的簇；
• 4.易陷入局部最优解。

K-Means 聚类算法的改进

基于萤火虫优化的加权K-Means算法，利用萤火虫优化算法的全局搜索能力强，易收敛的特点选取K-Means算法的初始聚类中心。

由于数据属性对聚类结果的影响程度不同，在传统欧式距离的基础上引入权重值，加大了数据的不同属性间的区分程度，消除了数据集中噪声点的影响。该算法很好地克服了传统K-Means算法中初始聚类中心难选取和噪声点对聚类结果的影响，提升了聚类的性能。

还有基于改进森林优化算法的K-Means算法，引入衰减因子作为自适应步长加快算法聚类速度，结合算术交叉操作，改进传统森林优化算法易陷入局部最优解、收敛慢的缺点，提高聚类精度和聚类准确率。

将遗传算法与K-Means算法相结合，提高K-Means算法的聚类效率与精确度。该算法首先使用近邻排序算法对原始数据集中的重复数据进行清理，将去重后的数据进行归一化，计算数据集中各个数据对象之间的欧氏距离，然后使用公式

求数据集的平均欧氏距离，其中，Dis(Si,Sj)为数据对象Si和Sj之间的欧氏距离，An为数据对象的数量。数据集中的每个数据对象如果与目标点的距离在AvgDis之内，那么认为该数据对象为目标点的邻近点，并统计其邻近点的数量。将数据集中各个数据对象的邻近点的数量按降序排列，取其前k个数据对象作为初始聚类中心进行K-Means聚类。然后利用遗传算法对K-Means聚类后的结果进行清理，初始种群是由50个01字符生成的基因序列，选择每个基因对应的特征作为K-Means 聚类算法的结果。适应度函数公式为

其中，fi为基因i的适应度，N为数据集中数据对象的数目，aik为基因i在聚类结果被分错的数目,l为种群中个体的数目，k为簇的数目。为了计算更加简便，需要将适应度进行归一化：

其中，fmax和fmin分别代表了种群中适应度的最大值与最小值。根据个体的适应度的大小选择轮盘对赌区域进行交叉操作和突变操作，消除数据集中无用的属性特征，如果达到最大迭代次数则输出新种群和最优结果，否则利用遗传算法继续进行迭代。

总结

（1）提升K-Means算法处理海量或多维数据集的能力。随着大数据时代的到来，我们所能获取的信息量呈指数式爆炸，如何将K-Means更好地用于处理指数级数据的聚类，也是我们需要研究的方向。

（2）降低K-Means算法的时间复杂度。改进的K-Means聚类算法有着良好的聚类效果，但这是在牺牲了时间的前提下换来的，如何能更好更快地提升聚类能力，需要我们做更进一步优化。