刘荣凯 孙忠林

摘要：Kmeans算法在聚类过程中随机选取k个初始聚类中心，容易造成聚类结果不稳定。针对该问题，提出PCATDKM算法：使用主成分分析法对数据对象集合的属性进行降维，提取出主属性，去掉无关属性，从而加速聚类过程;基于最小生成树算法及树的剪枝方法将数据对象划分为k个初始聚类簇，然后进行剪枝生成k棵子树，计算每棵子树中所有数据对象的均值，作为初始聚类中心;利用基于密度与最大最小距离的算法思想进行聚类。将PCATDKM算法与Kmeans、KNEKM、QMCKM、CFSFDPKM在UCI数据集上进行聚类比较，结果表明该算法聚类结果稳定、聚类准确率高。

关键词：

Kmeans算法;主成分分析法;聚类;聚类准确率

DOIDOI：10.11907/rjdk.182064

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）009008503

英文标题PCATDKM Algorithm for Kmeans Initial Clustering Center Optimization

——副标题

英文作者LIU Rongkai， SUN Zhonglin

英文作者单位（College of Computer Science and Engineering， Shandong University of Science and Technology， Qingdao 266590， China）

英文摘要Abstract：The Kmeans algorithm selects cluster centers randomly， which is likely to cause unstable clustering results.To solve this problem， this paper proposes the PCATDKM algorithm.Which uses principal component analysis to reduce the dimension of the data set and extract the main attribute. The data object is divided into k initial clusters based on the minimum spanning tree algorithm and the tree pruning method， and then pruning is performed to generate k subtrees and the average value of each subtree is calculated as the initial clustering center; the PCATDKM algorithm uses clustering algorithms based on density and maximum and minimum distances for clustering. The algorithm is clustered with Kmeans， KNEKM， QMCKM and CFSFDPKM on the UCI dataset. The results show that the clustering results are stable and the clustering accuracy is high.

英文關键词Key Words：Kmeans algorithm; principal component analysis; clustering; accuracy of clustering

0引言

许多学者从算法初始k个聚类中心选择、数据对象相似度计算、聚类质量评价函数三方面对算法进行改进，使算法聚类效果得到了一定改善。冯波等[1]利用对象的距离矩阵生成最小生成树，将k个树分支中所包含点的均值作为初始聚类中心进行聚类;郑丹等[2]基于密度选取各主要密度水平曲线上的第一个点作为k个初始聚类中心;石文峰等[3]提出一种用个体轮廓系数作为聚类有效性评估参数的改进算法;周炜奔等[4]提出利用均衡函数自动生成最优簇数k值的算法;王宏杰等[5]结合初始中心优化和特征加权改进Kmeans聚类算法;陈小雪等[6]提出一种基于萤火虫优化的加权Kmeans算法;王赛芳等[7]提出基于点密度的初始聚类中心选择方法;李海洋等[8]提出一种改进人工蜂群和K均值聚类的图像分割算法IABCK;朱晓峰等[9]提出一种基于文本平均相似度的Kmeans算法;李敏等[10]提出密度峰值优化初始中心的Kmeans算法;庄瑞格等[11]提出基于拟蒙特卡洛的Kmeans聚类算法;熊开玲等[12]提出基于核密度估计的Kmeans聚类优化算法;张雪凤等[13]通过调整Kmeans算法运行中数据对象被重新分配时的策略以提高数据对象集合的聚类质量;翟东海等[14]提出用最大距离法选取初始簇中心的kmeans文本聚类算法;赵将等[15]提出一种推荐算法IKC（Improved Kmeans Clustering Recommendation Method）用来改进Kmeans聚类。

以上算法分别针对聚类中心以及聚类质量评价函数进行优化，在一定程度上提高了聚类准确率，但是仍然存在聚类中心不稳定、聚类效果不佳等缺点。因此，本文提出一种基于传统Kmeans算法改进的PCATDKM（Principal Component AnalysisTree Distribution KMeans）算法。实验证明：PCATDKM算法在UCI数据集上得到的聚类结果比Kmeans算法准确度高，聚类结果更稳定。

1主成分分析算法

主成分分析算法[16]的思想是：对各维数据进行分析，提取并合成数据对象中无相关性的主要属性，用主要属性代表数据对象集中的原有属性。使用主成分分析法能够有效降低数据对象集合中的无关属性，大幅提高聚类运算效率及聚类准确率。

标准化变换公式：

zij=xij-xjsji=1，2…p;j=1，2…m（1）

其中，xj=∑pi=1xijp，sj=∑pi=1（xij-xj）p-1。xij表示矩阵中每个样本值，zij表示标准化矩阵，xj表示列均值，sj表示列标准差。

R=[rij]mxm=zTzp-1（2）

其中，rij=∑zkj.zkjp-1，i，j=1，2…m;R为相关系数矩阵;x为随机向量;m为维数;zT表示标准化矩阵z的转置。

2PCATDKM算法

PCATDKM算法的思想是：用主成分分析法提取集合中主要属性进行降维，去除无关属性，从而提高运算效率、加速聚类。利用数据对象集合的距离矩阵构造出一棵最小生成树[17]。对构造出的最小生成树进行剪枝，将其划分为k棵子树，每棵子树中所包含的数据对象代表一個类别（共k个类别），计算每棵子树中所包含数据对象的算术均值作为初始聚类中心，然后选取其中一个算术均值作为第一个聚类中心，利用最大最小距离算法选取剩下的k-1个初始聚类中心。进行k次操作，选取使误差平方和函数值最小的一组作为最终聚类结果[18]。

2.1PCATDKM算法相关定义

假设数据对象集合U含有N个样本数据，样本数据有m个属性——m维，则数据对象x可以表示为：x=（x1，x2…xm）。

定义1两个m维数据对象x、y的欧式距离公式为：

d[x，y]=（x1-y1）2+…+（xm-ym）2（3）

其中：x1，x2…xm和y1，y2…ym分别表示数据对象x、y的各维数据;d（x，y）表示数据对象x和y的距离。

定义2数据xi与其它每一个数据点的距离和定义为sum[xi][19]：

sum[xi]=∑Nj=1dist[xi，xj]（4）

定义3集合U中的距离和均值定义为avg[U]：

avg[U]=∑Ni=1sum[xi]/N（5）

定义4误差平方和函数：

E=∑ki=1∑x=ci|x-mi|2（6）

其中，E是样本空间所有对象的平方误差之和，x是数据库中属于类ci的数据样本，mi是类ci中所有样本的平均值。

2.2PCATDKM算法步骤

输入：包含N个对象的数据对象集合UP×m、聚类个数k。

输出：根据数据对象特征分成的k个类别。

算法步骤：

（1）UP×m按式（1）、式（2）计算相关系数矩阵R。

（2）根据|R-λIm|=0计算m个特征值λi。

（3）由贡献率λi∑mi=1λi确定n个主成分，得到Dp×n。

（4）利用式（3）计算两数据点的距离d[x，y]，生成数据集合的距离矩阵B;然后利用式（4）计算出每个数据对象之间的距离和，用式（5）计算样本之间距离和的均值。

（5）从Dp×n中删除样本间距离之和大于其均值的噪声点（孤立点），从而得到新的样本集合。

（6）更新Dp×n和新生成样本集合中样本的距离矩阵B，得到最终的样本集U1与样本之间距离的矩阵B1。

（7）调用genMST（U1，B1），构造最小生成树T。

（8）根据权值降序的方法对构造出的最小生成树T进行剪枝，剪枝出k-1个树分支，得到k棵子树。

（9）计算所构造最小生成树T剪枝的k-1棵子树中每棵子树的算术均值，记作数据中心C[i]，完成初始聚类中心k个数据中心的选取。

（10）选取C[1]加入初始聚类中心集合M中，作为第一个初始聚类中心k1，计算数据对象集合U1中所有对象与k1的距离d。从对象集合U1中，找出距离初始聚类中心集合M中所有数据对象最远的数据对象k2，将k2从集合U1中删除，并将k2加入到集合M中。

（10）从U1中找出距离初始聚类中心集合M中所有数据对象距离最远的数据对象k3，从集合U1中删除k3，将k3加入到集合M中。

（11）从集合U1中找距离集合M距离最远的对象，直到找到k个初始中心为止。

（12）从集合M中的k个中心出发，将其它对象分到距离最近的簇，用Kmeans算法进行聚类，计算误差平方和函数值E。

（13）从数据中心C中选取第二个均值C[2]作为第一个聚类中心k1，重复步骤（6）-步骤（12），直到选取C[k]为第一个初始聚类中心结束。

（14）算法结束。比较每次的误差平方和函数值E，从中选取最小的一组作为结果。

2.3最小生成树算法步骤

本文提出的算法基于最小生成树以及树的剪枝方法将数据对象划分为k个类别，其中最小生成树算法步骤如下：

Procedure genMST（U，B）

（1）T=NULL;n是U中对象数据个数。

（2）Flag[]数组表示n个对象点的访问状态，置为false，Flag[0]=true。

（3）repeat。

（4）搜索所有已访问节点，找出与各个节点链接的各个权值中最小的一条边dist[i，j]。

（5）将dist[i，j]加入树中。

（6）将找出的新节点访问状态标记为true。

（7）until搜索出n-1条边。

（8）return T。

3实验及结果分析

3.1PCATDKM算法与各改进Kmeans算法对比

实验描述：采用专为机器学习和数据挖掘算法设计的公共数据库UCI数据库进行实验[20]。在UCI数据集中选取4个数据集：yeast、abalone、magic和skin。将PCATDKM算法分别与CFSFDPKM算法、QMCKM聚类算法、KNEKM聚类优化算法进行聚类准确率及聚类误差平方和比较。通过实验得到聚类精度、误差平方和的比较结果（见表1、表2）。其中HIG表示最高聚类准确率，LOW表示最低聚类准确率，AVG表示平均聚类准确率。

由表1可得，基于PCA的PCATDKM算法聚类效果稳定;对于yeast、abalone、skin数据集，PCATDKM算法的聚类准确率都达到了85.35%以上，高于其它3种算法;在magic数据集上，PCATDKM算法聚类准确率也达到了80.63%，优于其它3种算法。

由表2可得，在4个数据集上，PCATDKM算法的误差平方和小于其它3种算法，说明PCATDKM算法的聚类效果比其它3种算法好。

综上所述，PCATDKM算法在传统的Kmeans算法中增加了PCA、TD與最大最小距离算法。PCA算法能够对数据对象集合进行降维，加速聚类过程。TD算法能够在选择初始聚类中心时根据数据对象的实际分布情况进行动态选择，使得通过聚类算法得到的初始k个聚类中心与实际聚类相对应。利用最大最小距离算法在聚类过程中选取聚类中心使得聚类中心选择稳定，提高了聚类准确率。PCATDKM算法在数据对象集合聚类过程中，加速聚类过程的同时减少了聚类中的迭代次数，使得聚类中心更加稳定，提高了聚类准确率和聚类效率，增强了算法的稳定性。

4结语

针对Kmeans算法在初始k个聚类中心选取时采用随机选取方法具有聚类结果不稳定的缺陷，本文提出了改进PCATDKM算法。改进算法利用PCA算法对数据对象集合进行降维，加速聚类过程。然后利用最小生成树算法，在聚类过程中根据数据对象的实际分布情况动态选取k个初始聚类中心，找出数据对象中分布比较密集的区域，使得采用本文算法得到的初始聚类中心更具有代表性。利用最大最小距离算法进行k次实验，选取最优解，进一步提高了聚类准确率。PCATDKM算法克服了孤立数据和噪音数据点带来的聚类结果不稳定影响。实验结果证实，PCATDKM算法能够得到较高且稳定的准确率，更适用于对实际数据的聚类。

参考文献参考文献：

[1]冯波，郝文宁，陈刚，等.Kmeans算法初始聚类中心选择的优化[J].计算机工程与应用，2013，49（14）：182185+192.

[2]郑丹，王潜平.Kmeans初始聚类中心的选择算法[J].计算机应用，2012，32（8）：21862188+2192.

[3]石文峰，商琳.一种基于决策粗糙集的模糊C均值聚类数的确定方法[J].计算机科学，2017，44（9）：4548+66.

[4]周炜奔，石跃祥.基于密度的Kmeans聚类中心选取的优化算法[J].计算机应用研究，2012，29（5）：17261728.

[5]王宏杰，师彦文.结合初始中心优化和特征加权的Kmeans聚类算法[J].计算机科学，2017，44（S2）：457459+502.

[6]陈小雪，尉永清，任敏，等.基于萤火虫优化的加权Kmeans算法[J].计算机应用研究，2018，35（2）：466470.

[7]王赛芳，戴芳，王万斌，等.基于初始聚类中心优化的K均值算法[J].计算机工程与科学，2010，32（10）：105107+116.

[8]李海洋，何红洲.改进人工蜂群优化的K均值图像分割算法[J].智能计算机与应用，2018，8（3）：4549.

[9]朱晓峰，陈楚楚，尹婵娟.基于微博舆情监测的Kmeans算法改进研究[J].情报理论与实践，2014，37（1）：136140.

[10]李敏，张桂珠.密度峰值优化初始中心的Kmeans算法[J].计算机应用与软件，2017，34（3）：212217.

[11]庄瑞格，倪泽邦，刘学艺.基于拟蒙特卡洛的K均值聚类中心初始化方法[J].济南大学学报：自然科学版，2017，31（1）：3541.

[12]熊开玲，彭俊杰，杨晓飞，等.基于核密度估计的Kmeans聚类优化[J].计算机技术与发展，2017，27（2）：15.

[13]张雪凤，张桂珍，刘鹏.基于聚类准则函数的改进Kmeans算法[J].计算机工程与应用，2011，47（11）：123127.

[14]翟东海，鱼江，高飞，等.最大距离法选取初始簇中心的Kmeans文本聚类算法的研究[J].计算机应用研究，2014，31（3）：713715+719.

[15]赵将.基于改进Kmeans聚类的推荐方法研究[D].武汉：华中科技大学，2016.

[16]林海明，杜子芳.主成分分析综合评价应该注意的问题[J].统计研究，2013，30（8）：2531.

[17]欧阳浩，陈波，黄镇谨，等.基于Kmeans的最小生成树聚类算法[J].组合机床与自动化加工技术，2014（4）：4144+52.

[18]周海洋，余剑，张卫涛.基于最小误差平方和的无线传感器网络多边定位算法[J].传感器与微系统，2014，33（7）：126128+132.

[19]张靖， 段富.优化初始聚类中心的改进kmeans算法[J].计算机工程与设计， 2013， 34（5）：16911694.

[20]傅德胜，周辰.基于密度的改进K均值算法及实现[J].计算机应用，2011，31（2）：432434.

责任编辑（责任编辑：何丽）