对K-means聚类算法初始值的研究

蒋林岑 樊晓唯 刘向东

摘要：传统的K-means聚类算法属于典型的基于划分聚类算法，算法的实现过程简单易懂，聚类效果不错，因此被广泛使用。但是，因为传统K-means的初始值是随机选定的，使得聚类结果不稳定，受初始值影响较大。针对上述问题，该文对传统的K-means算法中随机选取初始值改进，对样本值增加进行预处理，首先对样本值多次取数，对采样数据集进行初次K-means运算后获得聚类结果，从聚类结果中取距离最大的[k]个聚类中心作为初始值。通过Iris数据集对改进算法进行验证，聚类效果有较好的提高。

关键词：聚类分析;K-means算法;初始值优化

中图分类号：TP391      文献标识码：A

文章编号：1009-3044（2022）11-0095-03

随着人工智能的发展，海量数据的涌现，如何从大量样本数据集中发现有效的信息，并利用这些信息成为人们研究的重点，数据挖掘为获取有效信息提供了方法和手段。

聚类分析对具有相似特征的一组对象进行分组，根据组中的数据特征自动分类[1]。在对数据进行分组前，不需要预先给出分类目标，根据对象之间的关联特征自动分组[2]。这样的分类结果，将具有相同特性的数据分为一组，不同分组之间的区别也显而易见，聚类分析是一种无监督学习的方法，不会给出学习目标[3]。组间的差别越大，聚类效果越好。聚类算法可以分为划分的、密度的、层次的聚类算法。K-means聚类算法，是一种基于划分的聚类算法，具有易懂、实现简单、收敛快速的优点[4]，在需要对对象进行快速分类时，常用到K-means聚类算法。为了证明改进算法的聚类效果，本文首先阐述K-means算法的基本思想和实现流程，接着详细描述根据传统K-means算法的局限性进行优化后的K-means算法，说明其思想和算法步骤。

1 K-means聚类算法

1.1 K-means聚类算法基本思想

传统的K-means算法是应用较早的聚类算法，它的核心是对需要聚类分析的数据集随机选出k个数据点作为初始值[5]，这些初始值作为分簇的中心点，其他样本对象根据离中心点的最近距离进行划分，和最近的中心点划分为一个簇即实现分组。设有数据集[X=xi|i=1，2…n，cjj=1，2…k]，k用来表示聚类的类别，聚类的初始中心值用[cjj=1，2，…k]来表示，任意对象之间的距离用欧式距离来表示，如下：

[dxi，xj=xi-xjTxi-xj]  （1）

聚类中心。

[cj=1njx∈Cjx]    （2）

K-means算法是当所有对象到相应初值中心值误差平方和最小时[6]，如公式（3） ，使得不同的迭代计算把具有不同特征的对象划分到不同的分组中，生成的簇尽可能地靠近收敛。

[E=i=1kj=1njd（xj，ci）] （3）

K-means算法的具体实现过程如下：

输入：数据集中包含n个对象和随机[k]个簇。

输出：迭代求得的[k]值和最终簇。

方法：

（1） 在包含n个对象的数据集中随机设置[k]个特征空间内的点为初始值，作为初始的聚类中心;

（2） 计算样本集中的其他对象到[k]个初始值之间的距离，选择最近的初始中心点所属类别，作为其他对象的类别标记;

（3） 将所有对象完成分类标记后，根据划分的分组对象，重新计算出每个分组新的初始值（中心点） ;

（4） 如果计算得出的新中心点与原中心点一样，那么计算结束，否则重新进行第二步过程。

1.2 K-means聚类算法分析

通过K-means聚类算法的实现过程可以发现：由于传统的K-means算法在选取初始值是随机选择的，每次得到的分类结果都不一样，每次对象分组的差异较大，由于算法要求终止在范围内的最佳状态，所以初始中心点对整个分组计算的过程有着重要影响，聚类的结果会随着初始值的不同而改变[7]。

K-means算法实例说明初始值对聚类结果的影响，由于每次随机选定的初始值不同，因此每次聚类的结果也会有差异。给定数据集：{随机生成1500个对象样本集合，初始默认[k]=3}，通过两次K-means算法计算结果可以观察发现：原始数据有4类数据分布如图1所示，通过K-means算法运行一次结果如图2，随机产生3个中心点并分组得到3个簇，第二次计算聚类如图3，结果也是3组簇，可以发现2次分类结果有部分差异。并且当数据集越大，遇到极端初始值时，需要运算的时间更长，聚类的结果反正难以收敛，因此无法得到聚类结果。

2 K-means改进算法

2.1 改进的K-means算法思想

算法思想：针对上述初始中心点随机的问题，本文提出在开始阶段对数据集进行预处理，找到最佳初始值，产生一个比较稳定的聚类结果，从而不依赖初始中心值。改进的K-means算法分为两步：（1） 预处理阶段：对样本数据集首先进行m次随机采样，对每次采样的数据随机取n（n³k） 个初始中心值进行K-means运算，每次得到n个簇中心的聚类结果，得到随机样本的m组数据，一共m´n个簇[8]。（2） 接着选取确定初始值：在第一步中获取到的m´n个簇中心，依次选择其中距离相差最大的点作为初始中心[9]。具体处理流程如图4所示。

2.2 改进K-means算法的实现流程

输入：待分类数据集D，[k]个聚类中心值。

輸出：满足目标函数值最小的[k]和簇。

方法：

（1）  对数据集[D]进行[ⅈ=1]次的采样，得到采样数据集[D']。

（2）  在数据集[D']中随机获取n个初始簇中心[c1，c2，…cn]。

（3）  通过公式1计算数[D']中其余需要分类的对象[p]到n个初始中心距离[dp，ci]。

（4）  计算对象[p]和簇中心的距离，若距离最小则将对象和[ci]分类到同一组，成为同一个簇。

（5）  遍历完所有对象后，利用公式2重新计算[ci]的值，得到n个新的簇中心。

（6）  重复采样次数当[i≪m]，获取[m×n]个簇中心，记作[sm×n=x1，x2，..xm×n，]，选取距离最大的两点[p，q]，满足[dp，q=maxdij，i，j∈1，2，…n]，[xp，xq]作为初始的兩个聚类中心。

（7）  将剩余的[m×n-2]个样本按就近距离划分到[p，q]的簇中。

（8）  对[p]簇[q]簇中的对象进行距离计算，将距离最大的对象定为新的第三个聚类中心。

（9）  依次类推，输出满足均方误差函数值最小的[k]个簇和[k]个初始值。

3 实验结果与分析

通过实验对改进算法进行聚类效果分析，Iris鸢尾花数据集是UCI数据集的一部分，这个数据集经常被用作机器学习的分类场景[10]。Iris鸢尾花数据集被分为Iris-setosa、Iris-versicolor、Iris-virginica三类，数据集共包括150个样本[11]。为了分析聚类效果，分别使用传统K-means算法和改进的K-means算法，前者是随机取值作为初始值，后者是首先确定初始值和k簇值，再进行计算。实验中，通过多次选取初始值取平均数从而均衡分类准确率结果。用传统算法和改进后算法分别对Iris数据集各自进行5次计算，传统K-means算法随机聚类中心位置分别是（45，78，101） ，（10，45，77） ，（45，66，89） ，（23，67，89） ，（34，56，121） ，该进算法的初始化中心（35，56，111） ，（23，67，131） ，（9，35，103） ，（24，56，89） ，（45，67，129） ，实验结果如表1。

通过表1可以看出，用传统K-means算法随机选取的中心值，给定聚类数k=3，通过5次随机取数产生的初始值都不相同，计算得出准确率不同的花分类，由5次计算的准确率结果也发现，传统方法中选取初始中心值得到聚类准确率也不稳定，平均准确率较低[9]。当数据集数量较大时，由初始值产生的对聚类结果的影响会越来越大。而对初始值进行改进后的算法每次的分类准确率有所提升，并且计算结果相对稳定，准确率有了明显提升。

4 结束语

本文通过对K-means算法中随机获取的初始值的局限性进行改进，提出了一种优化初始值的K-means算法。改进的K-means从研究探索如何能获取稳定的初始值为目标，增加对数据集多次采样后的聚类中心点预处理，经过多次迭代获取的中心点中选取距离最大的点作为确定初始值。改进后的算法虽然提升了准确率，由于在选定初始值时进行了预处理，因此增加了时间复杂度，下一步将对减少时间复杂度和提升聚类效果做进一步研究。

参考文献：

[1] Harmer P K，Williams P D，Gunsch G H，etal.Anartificial immune system architecture for computer security applications[J].IEEE Transactions on Evolutionary Computation，2002，6（3）：252-280.

[2] Hand D J，VinciottiV.Choosing k for two-class nearest neighbour classifiers with unbalanced classes[J].Pattern RecognitionLetters，2003，24（9/10）：1555-1562.

[3] Yang M S，Hu Y J，Lin K C R，etal.Segmentationtechniques for tissue differentiation in MRI of Ophthalmology using fuzzyclustering algorithms[J].Magnetic Resonance Imaging，2002，20（2）：173-179.

[4] 刘文佳，张骏.一种改进的K-Means聚类算法[J].现代商贸工业，2018，30（19）：196-198.

[5] 初广辉，王晓利.一种改进的基于差分隐私的k-m eans聚类算法[J].软件导刊，2019，18（8）：71-74.

[6] 齐晓娜，王佳，徐东升，等.基于改进的k-means差分隐私保护方法在位置隐私保护中的应用[J].河北大学学报（自然科学版），2018，38（3）：315-320.

[7] 常彤.K-means算法及其改进研究现状[J].通讯世界，2017（19）：289-290.

[8] 于梦馨，刘波，汤恩生.改进粒子群算法优化SVM参数的遥感图像分类[J].航天返回与遥感，2018，39（2）：133-140.

[9] 周涛.具有自适应参数的粗糙k-means聚类算法[J].计算机工程与应用，2010，46（26）：7-10.

[10] 任恒妮.大数据K-means聚类算法的研究与应用[J].信息技术，2019，43（11）：20-23.

[11] 安计勇，闫子骥，翟靖轩.基于距离阈值及样本加权的K-means聚类算法[J].微电子学与计算机，2015，32（8）：135-138.

收稿日期：2021-12-20

基金项目：2020 年度江苏省工业软件工程技术研究开发中心开放基金项目（ZK20-04-02）

作者简介：蒋林岑，女，工程师，硕士，研究方向为人工智能、机器学习;樊晓唯，女，工程师，硕士，研究方向为人工智能、计算机视觉;刘向东，男，副教授，博士，研究方向为人工智能、知识图谱。