基于空间分布优选初始聚类中心的改进K-均值聚类算法

宋仁旺，苏小杰，石 慧

(太原科技大学电子信息工程学院，太原 030024)

随着信息行业的爆炸式发展，数据已成为行各业重要的生产因素，同时也对海量数据的挖掘提出新的挑战。信息爆炸产生的海量数据对从大量数据中挖掘有用信息提出挑战[1-4]。数据的聚类是数据挖掘实施过程中的核心技术[5-6]。MacQueen[7]为解决数据挖掘问题提出了一个局部搜索的算法——K-means聚类算法。该算法原理简单、运算高效、时间和空间复杂度较低，至今依然是工业和社会科学中最流行的算法[8]。但该K-means聚类效果对最初K个初始中心点的选取和离群值都非常敏感，当用于海量数据聚类时，由于其迭代次数过多且迭代过程涉及多次文件系统的读写操作非常费时[9-11]，所以有必要对K-means聚类算法初始聚类中心点的选取进行改进以减少聚类过程中的迭代次数，从而降低聚类所需的时间并提高聚类效果。

针对上述问题，学者从不同角度对K-means算法进行了改进。Arthur等[12]在K-means算法的基础上对中心点的选择进行改进，即基于每个数据点到已有中心点的距离采用线性概率选出下一个聚类中心点，简单地说就是数据点离现有的中心点距离越远就越有可能被选为类簇中心点，该方法能有效解决初始聚类中心点敏感的问题，但是由于类簇中心点的选择具有有序性，这使得算法无法并行扩展，极大地限制了算法在大规模数据集上的应用。K-medoids算法是在K-means聚类方法基础演变而来，该算法的特点是选取的每个中心点都是样本点，因此该方法能够解决K-means算法对噪声和离群值敏感问题，但是该算法时间复杂度高，不适合应用于大批量数据集[13]。Goode[14]为了减少聚类的迭代过程提出了X-means算法，该算法利用K-means迭代和基于BIC(Bayesian information criterion)的停止规则确定聚类的最优数目，但是该算法过程复杂，增加了算法复杂度，效果并不理想。

通过以上分析，可以发现现存对K-means算法改进的文献所提出的算法都是具有代价的。现拟在分析K-means聚类算法的基础上不降低K-means算法的准确性、高鲁棒性等性能情况下，提高聚类算法的算法效率和高稳定性。为此提出了一种针对海量数据集初始聚类中心点选择的聚类算法。在该算法中，为了消除数据集中孤立的噪声点对聚类效果的影响，采用冒泡排序法对数据集进行排序，获取数据集的各维中心值组成第一个初始聚类中心点，为保证所有的聚类中心点均匀地分布在数据集密度较大的空间上，余下候选初始聚类中心点的优化选择依据其与第一个初始聚类中心点的欧式距离，并且所有聚类中心点两两之间设置一定的距离间隔，以此减少聚类过程中的迭代次数和提高聚类算法效率。改进后的K-means聚类算法能显著减少聚类的迭代次数，降低噪声对聚类效果的影响，提高算法效率。最后选取UCI(University of California, Irvine)中多个针对聚类算法的数据集进行实验验证，对比K-means、K-means++聚类算法验证本文算法的高效性和准确性。

1 K-均值聚类算法理论

聚类通常又被称为无监督学习，属于一种动态算法。数据的聚类就是按照某个特定标准(如距离、密度)把一个集合分为互不相交的类簇，使得同一个类簇内的对象的相似性尽可能大，同时不在同一个类簇中的对象的相似性尽可能地小[15-18]。根据分类对象和分析计算方法不同，聚类算法分为小数据聚类和大数据聚类两种类型，其中小数据聚类包含传统聚类和智能聚类算法，大数据聚类包含的算法分为并行聚类、分布式聚类和高维聚类[19]。

假设数据集X包含n个d维属性的数据点，即X={x1,x2,…,xn},其中xi∈Rd。K-means聚类的目标是将n个样本点按照数据集间样本的相似性划分到指定的K个类簇中，每个样本只属于到其中一个中心点距离最小的类簇中。首先K-means聚类算法是随机产生K个聚类中心点{c1,c2,…,cn}，然后计算每一个数据点到所有聚类中心的欧式距离，根据就近原则，把其余的数据点分配给距离最小的类簇中心点，最后通过计算每个数据点与其类簇中心点距离差的平方和来评价聚类的效果。

2 改进的K-means聚类算法

K-means聚类算法初始聚类中心点是随机选取的，极有可能存在选取的初始聚类中心点是数据集边缘的噪声点或孤立点，或者选取的聚类中心点两两之间的空间距离十分接近,这可能增加聚类过程的迭代次数，影响聚类效果。鉴于此，现提出一种改进的K-means聚类算法，该算法的核心思想是初始聚类中心点尽可能均匀分布在数据集密度较大的一定范围内且各个中心点的距离足够大，同时应避免一些极端距离的点被选为中心点，具体步骤如下。

Step1设置K值，令M=K，扫描数据集，采用冒泡排序法把数据集各维从小到大进行排序，排序后的数据集为X1。

Step2筛选数据的各维中心值作为第一个聚类中心点c1，保证第一个聚类中心点位于数据集空间的中心，即

c1=X1,p,p=[n/2]

(1)

式(1)中：[]表示取整运算；X1,p表示排序后数据集的第p个样本。

Step3对数据集中的每个点xi，通过式(2)计算每一个数据点到已有聚类中心的欧式距离，即

(2)

式(2)中:xi表示第i个样本；cj表示第j个类簇中心点;xit表示第i个样本的第t维属性;cjt表示第j个聚类中心点的第t维属性。通过式(2)计算任意点xi到已有聚类中心点的距离，即

D(xi)=[d(xi,c1),d(xi,c2),…,d(xi,cj)]

(3)

其余k-1个聚类中心点要满足以下两点：

(1)候选的聚类中心点应排除在距离指定中心点0.8d之外和0.2d之内的空间上(d代表所有数据点距第一个初始聚类中心点的最远欧式距离)，即剩下k-1个聚类中心点分布在数据集数据密度较大的空间中。

(2)两两中心点之间设置一定的间隔，本文选取间隔为3d/M。

Step5重复Step 3、Step 4，直到其余k-1个聚类中心点全选择出来。

Step6通过式(4)分别计算数据集中的所有数据点到K个类簇中心点的欧氏距离，并依据式(4)将所有数据点分别分配到距离中心点最近的类簇中；如果

(4)

则x∈ci，从而得到k个类簇{S1,S2,…,Sk}。

Step7在Step 6的基础上，通过式(5)重新计算K个类簇各自的中心点，计算方法是取类簇中所有元素各自维度的算术平均值，即

(5)

式(5)中：ni表示类簇Si中数据点的个数，且xj∈Si。Step8将K个类簇新的中心点与原有中心点进行比较，相邻最小化平方误差和不再变化或迭代次数达到设定的最大值，则输出聚类结果。假设数据集划分为{S1,S2,…,Sk}，最终的最佳聚类目标是最小化误差平方和(sum of the squared errors，SSE)，即

(6)

总误差平方和越小，聚类效果越好。

本文聚类算法流程如图1所示。

图1 本文聚类算法流程图

3 实验验证

为了说明本文改进的算法在减少迭代次数的同时不降低聚类的效果，算法高效。本文数据样本包含两部分：一部分是UCI中针对验证聚类算法的Iris、Wilt、Avila、letter-recognition、Activity-recognition数据集作为实验数据集，另一部分数据集是由MATLAB中标准正态分布函数产生的矩阵，并选取了K-means、K-means++聚类算法与本文提出的算法进行了对比实验，检验算法效果。

实验环境:LenovoG40-80笔记本、Windows10专业版、系统类型为64位操作系统、基于X64的处理器、Intel(R)Core(TM)i5-5200U CPU @ 2.20 GHz、4 G RAM、MATLABR2018a 集成开发环境。

为了能直观地显示本文算法的聚类效果，首先在由MATLAB中标准正态分布函数产生的数据集上进行实验，实验分别在K-means、K-means++和本文提出的聚类算法上进行。该二维数据集分为5个类簇，共400个数据点。聚类结果如图2～图5所示。

图2 K-means算法聚类效果

图2中五个黑色标记是K-means算法聚类的最终类簇中心点，坐标分别是(0.618,-1.749)(-0.388,-0.101)(-1.617,-1.288)(1.722,-0.075)(0.794,1.654)。

图3中五个黑色标记是K-means++算法聚类的最终类簇中心点，坐标分别为(0.597,-1.718)(-0.677,-0.260)(-1.769,-1.518)(1.569,-0.088)(0.780,1.618)。

图3 K-means++算法聚类效果图

图4中红色的标记点是本文算法通过采用冒泡排序法自动选取数据集的各维中心点作为第一个初始聚类中心点，其余四个黑色的标记点是另外四个初始聚类中心点，坐标分别为(0.141,-0.453)(1.382,1.879)(2.081,-0.774)(-1.743,-0.294)(0.255,-2.326)，每个蓝色圆圈表示一个数据点，可以直观看出本文算法选取的五个初始的聚类中心点可以离散均匀分布在数据集中数据点密度相对大的空间上。

图4 本文算法产生的初始簇心

在图5中五个黑色标记是本文算法聚类的最终类簇中心点，坐标分别为(-0.294,-0.046)(0.991,1.591)(-1.722,-1.047)(1.629,-0.478)(0.132,-1.909)，相同颜色的点属于同一类簇。

图5 本文算法产生的聚类效果图

通过对比图2～图5的类簇中心点坐标可以得出，三个聚类算法的最终类簇中心点的坐标的比较接近，而本文聚类算法自动选择的5个初始聚类中心点的坐标与最终形成的类簇中心点坐标的位置十分接近，由此可以直观地看出本文算法可以达到减少聚类过程中的迭代次数，提高聚类算法效率预期效果。

通过分析表1可以发现：和经典的聚类算法相比较，本文提出的改进的聚类算法的迭代次数为10次，而K-means、K-means++的迭代次数分别为19和17次，可以看出本文算法在聚类过程中的迭代次数显著的减少，这由于本文算法选择的初始类簇中心点能够离散均匀地分布在数据集中数据点相对集中的地方，即提高了算法的运行效率；通过对比三个聚类算法的运行时间，可以看出K-means++算法的聚类时间较大，而K-means算法和本文算法的时间相差不大，主要时由于K-means++算法选择K个初始聚类中心点时同时采用串行的方式比较消耗时间；通过对比三个算法的误差平方和可以发现，本文算法的类簇内的误差平方和相比于其他算法也有所下降，即本文算法的聚类效果优于K-means、K-means++聚类算法。主要原因是，传统的聚类算法的中心点是在全数据集上随机选取的，那么选取的中心点可能处于极端的孤立点或两两中心点之间间隔过大或过小，而本文提出的改进聚类算法所选择的初始中心点是均匀地分布在数据点密度较大的空间中，这些初始中心点能非常好地贴近最终的聚类中心点。

表1 针对人造二维数据集各算法的聚类性能结果

为了进一步检验本文算法在多维数据集上的聚类效果，验证算法在聚类过程中减少迭代次数和提高聚类算法效率，现选取UCI中多个针对聚类算法的数据集进行聚类对比实验。

数据预处理:由于UCI中的数据集中有一些原始数据中带有数据的类别标识字母或数字，而我们进行实验时是不需要将类别标识放入算法中，所以在进行实验之前需要对数据集进行预处理，去掉数据集的标识部分。其中Activity-recognition数据集的采集包含房间1和房间2两个数据集，本文选取的房间1采集的数据集。实验数据集性质如表2所示。

表2 UCI中针对聚类数据集的性质

为了使本文选择的数据集具有多样性、代表性、说服力。本文选择的数据集维数最低的是4维，最高的是16维，样本数最少的是150个，最大的54 568，数据集的分类数也各不等，总的数据点最高的数据集Activity-recognition达436 544个，Iris数据集的最少数据点也达到600个。

通过对表3的分析可得：针对Iris、Wilt、Avila、letter-recognition、Activity-recognition多个不同的多维数据集的聚类，本文提出的聚类算法的迭代次数均小于K-means、K-means++聚类算法，特别是针对Iris、Activity-recognition数据集的迭代次数，K-means、K-means++算法的迭代次数均2倍于本文算法的迭代次数，针对letter-recognition,Avila数据集的迭代次数，K-means算法的迭代次数也接近与本文算法迭代次数的2倍。由上可以看出本文的算法在迭代次数方面的性能较优于K-means、K-means++聚类算法，特别是相对于K-means算法，本文算法更胜一筹。

表3 各算法迭代次数

在误差平方和方面，通过对表4的分析可得：三个聚类算法针对Iris、Wilt、Activity-recognition数据集的误差平方和十分接近，聚类的效果相差不大，本文算法针对letter-recognition数据集的聚类效果略优于K-means、K-means++算法，而K-means算法针对 Avila数据集的误差平方和却远远高于K-means++和本文算法，主要原因是K-means算法选取了数据集边缘的噪声点为类簇中心，使算法陷入局部最优的状态，影响了聚类效果。

表4 各算法的误差平方和

通过表5对比三个聚类算法针对相同数据集所需的时间，可以发现，K-means算法的时间略低于K-means++算法，主要是由于K-means算法选取K个聚类中心点采用并行算法，而K-means++选用效率较低的串行算法，本文算法所用的时间最短，主要是本文算法的迭代次数显著低于K-means、K-means++算法，从而缩短程序运行的时间，进而证明本文算法达到了减少聚类过程中的迭代次数和提高聚类算法效率的预期效果。

表5 各个算法的时间

针对验证本文算法在实际实验中的应用，本文又选取了西安交通大学XJTU-SY滚动轴承加速寿命试验数据中工况为1的第五个轴承的数据进行聚类，该数据集包含垂直和水平振动信号，共有1 638 400个数据点，失效位置分为内圈和外圈两类[20]。该数据集的具体聚类效果如表6所示。

通过对表6的分析可以看出，本文算法对滚动轴承加速寿命试验数据实际的应用效果中，迭代次数，算法运行的时间均小于K-means、K-means++算法，即本文算法整体实验效果优于K-means，K-means++算法。

表6 针对XJTU-SY滚动轴承加速寿命试验数据集各算法的聚类性能结果

4 结论

K-means算法是一种原理十分简单和应用十分广泛的聚类算法，但是它存在着初始中心点不稳定的问题。本文在分析了经典的K-means聚类算法的基础上，对传统的聚类算法进行了改进，本文算法基于人工数据集和UCI数据集的实验结果与经典的聚类算法结果相比较表明，本文算法的迭代次数可以降低50%，甚至更高，所需的时间也显著降低了10%，不仅解决初始中心点不稳定对聚类效果带来的影响，还改善了聚类效率，效果十分显著。在下一步的工作中，针对一些数据波动范围较大的数据集，考虑在本文的算法中加入数据的预处理，如归一化的处理等，此外对初始聚类中心点的限制空间可以进一步进行优化。