Kmeans聚类算法局限性与策略研究

陈文静

【摘要】由于Kmeans聚类算法具有简单且聚类速度较快的特点因而在很多场景中被使用。本文从Kmeans聚类算法出发，首先对该算法的算法步骤进行简要描述;然后对该算法存在的局限性进行全面分析;最后针对相应的局限性提出对应的解决策略。

【关键词】Kmeans算法  局限性  解决策略

传统聚类算法中由于Kmeans聚类算法具有出色的速度和良好的可扩展性，从而使其成为应用最广泛的聚类算法之一。

一、Kmeans聚类算法简介

Kmeans聚类算法是一个重复移动类中心点的过程，把类的中心点，也称重心（centroids），移动到其包含成员的平均位置，然后重新划分其内部成员。Kmeans算法步骤如下：

输入：样本集为D={x1，x2，…，xn}，聚类个数k;

输出：满足条件的k个聚类。

（1）从n个数据对象中随机选取k个对象作为初始的聚类中心;

（2）根据聚类均值（中心对象），计算每个对象与这些聚类中心的距离，并根据最小距离对相应的数据对象重新划分聚类;

（3）更新聚类的均值（中心对象）;

（4）计算适应度函数，并验证函数是否收敛或者算法是否终止，如果函数未收敛或者算法未达到终止次数，则返回到步骤（2）。

二、Kmeans聚类算法局限性

聚类算法由于算法简洁易懂，理论可靠、可以处理不同类型的数据集等特点使其在人工智能、模式识别、图像处理、深度学习、医疗、生物工程以及政府等领域被广泛应用。目前聚类算法的分类方式可以采用层次法、划分法、密度法等进行。然而Kmeans聚类算法仍然存在一定的局限性。分别如下：

（一）k值的依赖性

一般Kmeans算法中k值的选取由用户自己选定，不同的k值决定了不同的聚类效果。因此，如何选择合适的k值成为聚类算法准确性的一个因素。如果数据集有一定的规律这对于k值的选取也较为容易。但是如果数据集较大且数据之间没有规律可循则对于k值的选取也就无法准确判断。研究学者针对k值的不确定性选取提出了多种改进方法，这为Kmeans算法的深入研究提供了基础。

（二）初始点的依赖性

Kmeans算法不仅对k值的选取有局限性，同时对聚类算法的初始聚类中心的选取也具有敏感性。如果初始聚类中心选择不恰当，则会使得算法陷入局部最优解亦或是算法的适应度函数达不到收敛条件，则会导致算法的迭代次数增加从而降低了算法的执行效率。因此，如何选择算法的初始聚类中心成为了科研专家的又一研究问题，本文正是基于此问题对Kmeans算法进行改进和优化。

（三）对离群点具有敏感性

这里我們将数据集中的某条数据到数据集中的其他数据的距离相对较远的数据点称为离群点。当运用离群点计算更新聚类中心时，由于离群点距离聚类中心点的距离较远，会导致聚类中心更新次数增加。同时，影响最终聚类结果的准确性。如果我们选择将离群点作为Kmeans算法的初始聚类中心则会使算法陷入局部最优，而达不到全局最优的结果。

（四）可扩展性

随着数据集不断增大，Kmeans算法需要更多的迭代次数以及更多的时间去计算数据之间的相似度，这种时间复杂度以线性方式增长的趋势对如何处理大规模的数据集提出了挑战。

三、Kmeans聚类算法解决策略

由于Kmeans聚类算法存在一定的局限性，因此针对Kmeans聚类算法初始聚类中心敏感性问题，研究人员提出了许多改进初始聚类中心的算法。针对Kmeans聚类算法中的聚类K值及初始聚类中心点的敏感性问题，胡威通过研究Kmeans聚类算法的优缺点，提出了一种优化Kmeans初始聚类中心的方法，并将此方法应用于网络入侵检测，实验证明该检测结果相对于传统的Kmeans聚类算法具有更好的入侵检测结果。针对离群点敏感性问题，唐东凯等人使用基于密度的离群点的检测算法对数据的离群点进行筛除，并将最大最小距离算法进行结合进而在筛选后的样本选取初始中心。针对算法的可扩展性，魏杰通过借鉴Kmeans聚类算法的思想，为了让Kmeans算法有更好的扩展性，提出了NCA聚类算法，从而使得该算法可以脱离Kmeans独立运行。

四、总结

在众多聚类算法中，Kmeans聚算法由于其聚类简单且速度快的优势在许多场景中被使用。本文对Kmeans聚类算法进行了详细描述，并就算法的局限性及对应的解决策略给出了阐述。通过文章的叙述使我们对Kmeans聚类算法有了更详细的认识并对改进策略有了更多的了解。

参考文献：

[1]彭长生.基于Fisher判别的分布式K-Means聚类算法[J].江苏大学学报（自然科学版），2014，（04）.

[2]谢秀华，李陶深.一种基于改进PSO的K-means优化聚类算法[J].计算机技术与发展，2014，（02）.

[3]刘兴亮.基于Hadoop的海量图书流通数据的kmeans分析[D].东华理工大学， 2015.

[4]胡威.一种改进的K-means算法在网络入侵检测中的应用研究[D].合肥工业大学，2017.

[5]唐东凯，王红梅，胡明，刘钢.优化初始聚类中心的改进K-means算法[J].小型微型计算机系统，2018.

[6]魏杰.基于K-means聚类算法改进算法的研究[J].信息通信，2018，（05）.