第15卷第2期 智能系统学报 Vol.15 No.2 2020年3月 CAAI Transactions on Intelligent Systems Mar.2020 D0:10.11992/tis.201811020 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190829.1004.004html 基于可拓距的改进k-means聚类算法 赵燕伟，朱芬，桂方志，任设东2，谢智伟，徐晨 (1.浙江工业大学特种装备制造与先进加工技术教育部/汾江省重点实验室，浙江杭州310014,2.浙江业大学 计算机科学与技术学院，浙江杭州310014) 摘要：针对现有聚类算法在初始聚类中心优化过程中存在首个初始聚类中心点落于边界非密集区域的不足， 导致出现算法聚类效果不均衡问题，提出一种基于可拓距优选初始聚类中心的改进k-meas算法。将样本经典 距离向可拓区间映射，并通过可拓侧距计算方法得到可拓左侧距及可拓右侧距：引入平均可拓侧距概念，将平 均可拓左侧距和平均可拓右侧距分别作为样本密集度和聚类中心疏远度的量化指标：在此基础上，给出初始聚 类中心选取准则。通过与传统k-means聚类算法进行对比，结果表明改进后的k-means聚类算法选取的初始聚 类中心分布更加均匀，聚类效果更好，尤其在对高维数据聚类时具有更高的聚类准确率和更好的均衡性。 关键词：可拓距；k-means聚类算法；缩放因子；初始聚类中心；密集度；疏远度 中图分类号：TP181文献标志码：A 文章编号：1673-4785(2020)02-0344-08 中文引用格式：赵燕伟，朱芬，桂方志，等.基于可拓距的改进k-means聚类算法.智能系统学报，2020,15(2)：344-351. 英文引用格式：ZHAO Yanwei,,ZHU Fen,GUI Fangzhi,,etal.Improved k-means algorithm based on extension distance.CAAl transactions on intelligent systems,2020,15(2):344-351. Improved k-means algorithm based on extension distance ZHAO Yanwei',ZHU Fen',GUI Fangzhi',REN Shedong',XIE Zhiwei',XU Chen' (1.Key Lab of Special Purpose Equipment and Advanced Manufacturing Technology,Ministry of Education Zhejiang Province, Zhejiang University of Technology,Hangzhou 310014,China;2.College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310014,China) Abstract:An improved k-means algorithm optimizing the initial cluster centers based on extension distance was pro- posed to solve several problems that lead to clustering imbalance of the algorithm,such as the poor quality of initial cluster center selection or the first initial cluster center easily falling into the non-dense area of the data boundary.First, the classical distance of the sample was mapped onto the extension interval,and the extension left-side and right-side distances were obtained using the extension distance calculation method.Then,the average extension side distance was determined,and the extension left-side and right-side distances were taken as the quantitative indicators of sample dens- ity and cluster center distance,respectively.Subsequently,the selection criteria of the initial cluster center were given. Finally,compared with the traditional k-means algorithm,the improved k-means algorithm obtained higher clustering accuracy and better balance,particularly in high-dimensional data clustering. Keywords:extension distance;k-means clustering algorithm;scaling factor;initial cluster center;intensity;alienation 聚类是数据分析的重要手段，将数据集分为有明显区别，使得相似性最小，在数据挖掘、图像 若干类，使得簇内紧密且相似性大，簇与簇之间 处理等领域被广泛应用。k-means聚类算法是 收稿日期：2018-11-26.网络出版日期：2019-08-29 一种常用的动态聚类算法，具有聚类速度快，操 基金项目：国家自然科学基金项目(51875524)：浙江省公益技 做简单，效率高等特点，但其同时存在对初始聚 术应用研究计划项目(2017C31072). 通信作者：赵燕伟(1959-，.E-mail:ywz@zjut.edu.cn. 类中心点较敏感、全局搜索能力弱的缺点，使得
DOI: 10.11992/tis.201811020 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190829.1004.004.html 基于可拓距的改进 k-means 聚类算法 赵燕伟1 ，朱芬1 ，桂方志1 ，任设东2 ，谢智伟1 ，徐晨1 （1. 浙江工业大学 特种装备制造与先进加工技术教育部/浙江省重点实验室，浙江 杭州 310014; 2. 浙江业大学 计算机科学与技术学院，浙江 杭州 310014） 摘 要：针对现有聚类算法在初始聚类中心优化过程中存在首个初始聚类中心点落于边界非密集区域的不足， 导致出现算法聚类效果不均衡问题，提出一种基于可拓距优选初始聚类中心的改进 k-means 算法。将样本经典 距离向可拓区间映射，并通过可拓侧距计算方法得到可拓左侧距及可拓右侧距；引入平均可拓侧距概念，将平 均可拓左侧距和平均可拓右侧距分别作为样本密集度和聚类中心疏远度的量化指标；在此基础上，给出初始聚 类中心选取准则。通过与传统 k-means 聚类算法进行对比，结果表明改进后的 k-means 聚类算法选取的初始聚 类中心分布更加均匀，聚类效果更好，尤其在对高维数据聚类时具有更高的聚类准确率和更好的均衡性。 关键词：可拓距；k-means 聚类算法；缩放因子；初始聚类中心；密集度；疏远度 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2020)02−0344−08 中文引用格式：赵燕伟, 朱芬, 桂方志, 等. 基于可拓距的改进 k-means 聚类算法 [J]. 智能系统学报, 2020, 15(2): 344–351. 英文引用格式：ZHAO Yanwei, ZHU Fen, GUI Fangzhi, et al. Improved k-means algorithm based on extension distance[J]. CAAI transactions on intelligent systems, 2020, 15(2): 344–351. Improved k-means algorithm based on extension distance ZHAO Yanwei1 ，ZHU Fen1 ，GUI Fangzhi1 ，REN Shedong2 ，XIE Zhiwei1 ，XU Chen1 (1. Key Lab of Special Purpose Equipment and Advanced Manufacturing Technology, Ministry of Education & Zhejiang Province, Zhejiang University of Technology, Hangzhou 310014, China; 2. College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310014, China) Abstract: An improved k -means algorithm optimizing the initial cluster centers based on extension distance was proposed to solve several problems that lead to clustering imbalance of the algorithm, such as the poor quality of initial cluster center selection or the first initial cluster center easily falling into the non-dense area of the data boundary. First, the classical distance of the sample was mapped onto the extension interval, and the extension left-side and right-side distances were obtained using the extension distance calculation method. Then, the average extension side distance was determined, and the extension left-side and right-side distances were taken as the quantitative indicators of sample density and cluster center distance, respectively. Subsequently, the selection criteria of the initial cluster center were given. Finally, compared with the traditional k-means algorithm, the improved k-means algorithm obtained higher clustering accuracy and better balance, particularly in high-dimensional data clustering. Keywords: extension distance; k-means clustering algorithm; scaling factor; initial cluster center; intensity; alienation 聚类是数据分析的重要手段，将数据集分为 若干类，使得簇内紧密且相似性大，簇与簇之间 有明显区别，使得相似性最小，在数据挖掘、图像 处理等领域被广泛应用[1-4]。k-means 聚类算法是 一种常用的动态聚类算法，具有聚类速度快，操 做简单，效率高等特点，但其同时存在对初始聚 类中心点较敏感、全局搜索能力弱的缺点，使得 收稿日期：2018−11−26. 网络出版日期：2019−08−29. 基金项目：国家自然科学基金项目 (51875524)；浙江省公益技 术应用研究计划项目 (2017C31072). 通信作者：赵燕伟 (1959-). E-mail：ywz@zjut.edu.cn. 第 15 卷第 2 期 智 能 系 统 学 报 Vol.15 No.2 2020 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2020
第2期 赵燕伟，等：基于可拓距的改进k-means聚类算法 ·345· 聚类效率低，准确性差。因此，很多学者为得到 间的距离为零，即“类内即为同”，无法将事物内 稳定、高效的聚类效果，对k-means聚类算法的局 部的“质变”、“量变”表达出来。因此，为了描述 限性进行了改进与研究。 类内事物（区间内的点）的区别，在可拓学中规 何熊熊等提出一种基于密度和网格的簇心 定：实轴上任意一点x与区间X=<a,b>之距为 可确定聚类算法，通过网格对象的密度值进行划 分以完成聚类；李亚等6引入轮廓系数作为聚类 P(x.Xo)=k-atb_b-a a-x,xsatb 2 2 效果评价指标，并将改进的算法应用到台折损率 r-bx≥ab (1) 2 的计算中：邢长征等针对聚类结果对孤立点敏 当实例点在区间中点时，该实例最符合要求； 感的问题，提出了一种基于平均密度优化初始聚 (a,b)可以是开区间、闭区间、半开区间。 类中心的k-means算法；张天骐等1提出一种基 但在实际工作中，却不全如此，例如，误差要 于k-means聚类改进的软扩频信号伪码序列盲估 求越小越好；成本要求越低越好；性价比越高越 计算法，利用相似度从分段数据中寻找初始聚类 好；洗衣机的洗净率越大越好等，一般而言，实例 中心，并通过平均轮廓系数估计规模数：李晓瑜 点并不是越在区间中点越好，因此在可拓距的基 等9提出了一种基于Hadoop的分布式改进k- 础上，引入可拓侧距的概念： means算法，通过引入Canopy算法初始化k-means a+b 给定区间X=a,b),∈(a,2称 算法的聚类中心；Tzortzis G等io提出了MinMax a-x, k-means算法，在初始化不好的情况下通过赋予方 b-xo x≤a ix,xo.Xo) (x-a), x∈(a,xo) (2) 差权重以优化目标提高聚类效果；Laith Moham- a-Xo x-b. x≥X0 mad Abualigah等u将k-means算法采用和声搜索 为x与区间X关于x的左侧距。 方法进行优化并应用于文本聚类中，提高了聚类 精度；Li Yanyan等)提出一种基于粒子群优化 给定区间X=a,b),<a 2,,称 的k-means算法，并将其应用在岩体不连续数据 a-xx≤0 分类中；Khanmohammadi等i)为克服对初始聚类 Pr(x,xo,Xo) a-xo(b-x). x∈(xo,b) (3) b-0 中心的敏感问题，提出了一种混合k-谐波均值和 x-b. x≥b 重叠k均值算法的混合方法来克服缺点。以上改 为x与区间X关于x的右侧距。 进算法都起到了较好的聚类效果，但在初始聚类 1.2k-means聚类算法基本原理 中心选取问题上仍存在首个初始聚类中心点落于 k-means聚类算法基本思想是将样本划分成 稀疏边界的缺陷。 多个类，使得各簇内对象具有尽可能大的相似 基于此，本文提出一种基于可拓距的改进k- 度，同时使簇间的相似度尽可能的小2o。k-means means聚类算法，将可拓学思想与k-means算法有 聚类算法的处理过程如下： 效的结合，通过引入可拓侧距和缩放因子，对首 1)从数据集X中随机选择k个对象，分别作 个初始聚类中心点进行优化，选出一组最优初始 为k个类别的初始聚类中心： 聚类中心点，并通过仿真对比检验本文改进算法 2)计算剩余每个对象与各个聚类中心的距 的可行性。通过实验验证，该方法具有更好的聚 离，并将其划分到距离最近的子类中： 类效果。 3)重新计算每个子类中所有对象的平均值， 将其作为新的聚类中心。 1基本知识 重复上述过程，直到聚类中心不再改变四。 1.1可拓距相关知识 l.3k-means聚类算法的不足分析 可拓学是以蔡文教授为首的我国学者们创立 k-means算法中，对于k个初始中心点的选取 的新学科，近年来，可拓学在计算机，人工智能、 是随机完成的，而初始中心点选取的不同会导致 检测、控制等领域进行的应用取得了良好的成 不同的聚类效果，从而引起聚类结果的不稳定 绩。其中，可拓距在实例检索领域应用较为广 性。针对该不足，一些学者提出用密集度、差异 泛，通过可拓距构造关联函数，依据样本间关联 度等22]概念对初始聚类中心进行优化，都无法 度识别案例类别s1,显著提高了案例检索效率 避免初始聚类中心点落在边界非密集区域，因此 与正确率。 本文将从初始中心点选取方面对k-means算法提 在经典数学中，当点在区间内时，默认点与区 出相应的改进措施
聚类效率低，准确性差。因此，很多学者为得到 稳定、高效的聚类效果，对 k-means 聚类算法的局 限性进行了改进与研究。 何熊熊等[5] 提出一种基于密度和网格的簇心 可确定聚类算法，通过网格对象的密度值进行划 分以完成聚类；李亚等[6] 引入轮廓系数作为聚类 效果评价指标，并将改进的算法应用到台折损率 的计算中；邢长征等[7] 针对聚类结果对孤立点敏 感的问题，提出了一种基于平均密度优化初始聚 类中心的 k-means 算法；张天骐等[8] 提出一种基 于 k-means 聚类改进的软扩频信号伪码序列盲估 计算法，利用相似度从分段数据中寻找初始聚类 中心，并通过平均轮廓系数估计规模数；李晓瑜 等 [ 9 ] 提出了一种基于 Hadoop 的分布式改进 kmeans 算法，通过引入 Canopy 算法初始化 k-means 算法的聚类中心；Tzortzis G 等 [10] 提出了 MinMax k-means 算法，在初始化不好的情况下通过赋予方 差权重以优化目标提高聚类效果；Laith Mohammad Abualigah 等 [11] 将 k-means 算法采用和声搜索 方法进行优化并应用于文本聚类中，提高了聚类 精度；Li Yanyan 等 [12] 提出一种基于粒子群优化 的 k-means 算法，并将其应用在岩体不连续数据 分类中；Khanmohammadi 等 [13] 为克服对初始聚类 中心的敏感问题，提出了一种混合 k-谐波均值和 重叠 k 均值算法的混合方法来克服缺点。以上改 进算法都起到了较好的聚类效果，但在初始聚类 中心选取问题上仍存在首个初始聚类中心点落于 稀疏边界的缺陷。 基于此，本文提出一种基于可拓距的改进 kmeans 聚类算法，将可拓学思想与 k-means 算法有 效的结合，通过引入可拓侧距和缩放因子，对首 个初始聚类中心点进行优化，选出一组最优初始 聚类中心点，并通过仿真对比检验本文改进算法 的可行性。通过实验验证，该方法具有更好的聚 类效果。 1 基本知识 1.1 可拓距相关知识 可拓学是以蔡文教授为首的我国学者们创立 的新学科，近年来，可拓学在计算机，人工智能、 检测、控制等领域进行的应用取得了良好的成 绩 [14]。其中，可拓距在实例检索领域应用较为广 泛，通过可拓距构造关联函数，依据样本间关联 度识别案例类别[15-19] ，显著提高了案例检索效率 与正确率。 在经典数学中，当点在区间内时，默认点与区 间的距离为零，即“类内即为同”，无法将事物内 部的“质变”、“量变”表达出来。因此，为了描述 类内事物 (区间内的点) 的区别，在可拓学中规 定：实轴上任意一点 x 与区间 X0=<a, b>之距为[14] ρ(x,X0) = |x− a+b 2 | − b−a 2 = a− x, x ⩽ a+b 2 x−b, x ⩾ a+b 2 (1) ⟨a,b⟩ 当实例点在区间中点时，该实例最符合要求； 可以是开区间、闭区间、半开区间。 但在实际工作中，却不全如此，例如，误差要 求越小越好；成本要求越低越好；性价比越高越 好；洗衣机的洗净率越大越好等，一般而言，实例 点并不是越在区间中点越好，因此在可拓距的基 础上，引入可拓侧距的概念[14] ： ⟨a,b⟩ x0 ∈ (a, a+b 2 给定区间 X ⟩ 0= ， ，称 ρl(x, x0 ,X0) = a− x, b− x0 a− x0 (x−a), x−b, x ⩽ a x ∈ ⟨a, x0⟩ x ⩾ x0 (2) 为 x 与区间 X0 关于 x0 的左侧距。 ⟨a, b⟩ x0 ∈< a+b 2 给定区间 X ,b) 0= ， ，称 ρr(x, x0 ,X0) = a− x, a− x0 b− x0 (b− x), x−b, x ⩽ x0 x ∈ ⟨x0,b⟩ x ⩾ b (3) 为 x 与区间 X0 关于 x0 的右侧距。 1.2 k-means 聚类算法基本原理 k-means 聚类算法基本思想是将样本划分成 多个类，使得各簇内对象具有尽可能大的相似 度，同时使簇间的相似度尽可能的小[20]。k-means 聚类算法的处理过程如下： 1) 从数据集 X 中随机选择 k 个对象，分别作 为 k 个类别的初始聚类中心； 2) 计算剩余每个对象与各个聚类中心的距 离，并将其划分到距离最近的子类中； 3) 重新计算每个子类中所有对象的平均值， 将其作为新的聚类中心。 重复上述过程，直到聚类中心不再改变[21]。 1.3 k-means 聚类算法的不足分析 k-means 算法中，对于 k 个初始中心点的选取 是随机完成的，而初始中心点选取的不同会导致 不同的聚类效果，从而引起聚类结果的不稳定 性。针对该不足，一些学者提出用密集度、差异 度等[22-23] 概念对初始聚类中心进行优化，都无法 避免初始聚类中心点落在边界非密集区域，因此 本文将从初始中心点选取方面对 k-means 算法提 出相应的改进措施。 第 2 期 赵燕伟，等：基于可拓距的改进 k-means 聚类算法 ·345·
·346· 智能系统学报 第15卷 2可拓距改进的k-means聚类算法 况对左右侧距平均值的影响，将经典平均距离映 射为两个平均侧距值，如图2所示，其中平均左侧 2.1基本思想 距值相对中心点靠左分布，平均右侧距值相对中 为便于表述，首先定义距离区间、距离可拓 心点靠右分布。特别指出，当数据在区间对称分 侧距、距离平均可拓侧距3个概念。对于n个样 布时，左右平均可拓侧距值重合于一点。将可拓 本的集合X={,2,…,x山，其中x为m维向量(i= 平均左侧距可作为衡量密集度指标，可拓平均右 1,2,…,),有如下定义： 侧距可，作为衡量疏远度指标，首个大于可拓平均 定义1样本集合X的距离区间Z为 左侧距可所对应中心坐标作为第一个聚类中心， Z=[A,B][min(D),max(D)] (4) 下一待选取初始聚类中心点需满足与各已确定初 始聚类中心点间可拓距均大于可拓右侧平均距 其中， 两两样本间距 可，方可作为聚类中心点。 离集合。 初始中心点 定义2根据式(2)和式(3)定义两样本x,和 x(切的距离d对区间Z的左、右侧距分别为 A-d,d<A 左侧距：p=p(d,A,Z)= A: d=A d-B.d>A 0, A生Z 其中：A,=p(A,A,Z)= A-B, A∈Z 0⑧(A-B),A使Z且A∈Z. (5) A-d,d<B 右侧距：p,=p,(d,B,Z= B., d=B d-B.d>B. 0 B使Z 其中：B=P,(B,B,Z= A-B B∈Z 图1初始中心点展示图 0⑧(A-B),B使Z且B∈Z. Fig.1 The display map of first initial center point (6) 定义3 根据定义2可计算所有两两样本的 avg X1 经典距 可拓侧距，则平均左、右侧距为 p= 户i+1e1 (7) C2 其中，C?表示从n个样本中任意取2个样本的组 p 合数。 可拓距 针对传统k-means算法初始中心点随机选取 图2经典距向可拓距映射 Fig.2 Mapping of classical distances to extension distances 所引起聚类算法稳定性差问题，现有的改进算法 虽取得了一定的效果，但仍无法避免初始聚类中 当选出初始聚类中心点数未达到所要求个数 心点落在边界非密集区域如图1所示，取样本间 时，引入缩放因子？如式（⑦）所示，对可拓平均右 距离最小值所对应中心坐标作为首个初始聚类 侧距进行缩放，选出满足个数的初始聚类中心点。 点，因下一初始聚类中心点的选取决定于首个初 1+ Cr-k' K≠K 1= (8) 始中心的位置，当该点位于边界非密集区域，既 1,K=K 降低了剩余初始聚类中心点质量，又会出现最终 其中，K为每次遍历后，所获得的初始聚类中心个 聚类集合中样本数为0或1的情况，使得聚类效 数；K为指定聚类中心数。 果不均衡。 最后按传统聚类算法进行聚类。选取的一组 初始聚类中心的选取，不仅要求分布在较密 最优初始聚类中心点克服了中心点出现于边界非 集的范围内，还需要保证各初始聚类中心尽可能 密集区域缺陷，最大限度分布在密集区且各聚类 分散。针对上述问题，利用可拓距中数据分布情 中心点均匀分布
2 可拓距改进的 k-means 聚类算法 2.1 基本思想 X = {x1, x2,··· , xn} 1,2,··· ,n) 为便于表述，首先定义距离区间、距离可拓 侧距、距离平均可拓侧距 3 个概念。对于 n 个样 本的集合 ，其中 xi 为 m 维向量 (i = ，有如下定义： 定义 1 样本集合 X 的距离区间 Z 为 Z = [A,B] = [min(D),max(D)] (4) D = d d = vt∑m p=1 ( x p i − x p j )2 其中， 为两两样本间距 离集合。 , 定义 2 根据式 (2) 和式 (3) 定义两样本 xi 和 xj (i j) 的距离 d 对区间 Z 的左、右侧距分别为 左侧距 : ρ (i, j) l = ρl(d,A,Z) = A−d, Az , d − B, d < A d = A d > A 其中 : Az=ρl(A,A,Z)= 0, A− B, 0⊗(A− B), A < Z A ∈ Z A < Z且A ∈ Z. (5) 右侧距 : ρ (i, j) r = ρr(d,B,Z) = A−d, Bz , d − B, d < B d = B d > B. 其中 : Bz=ρr(B,B,Z)= 0, A− B, 0⊗(A− B), B < Z B ∈ Z B < Z且B ∈ Z. (6) 定义 3 根据定义 2 可计算所有两两样本的 可拓侧距，则平均左、右侧距为 ρ = ∑n j=i+1 ∑n−1 i=1 ρ (i, j) C2 n (7) C 2 其中， n 表示从 n 个样本中任意取 2 个样本的组 合数。 针对传统 k-means 算法初始中心点随机选取 所引起聚类算法稳定性差问题，现有的改进算法 虽取得了一定的效果，但仍无法避免初始聚类中 心点落在边界非密集区域如图 1 所示，取样本间 距离最小值所对应中心坐标作为首个初始聚类 点，因下一初始聚类中心点的选取决定于首个初 始中心的位置，当该点位于边界非密集区域，既 降低了剩余初始聚类中心点质量，又会出现最终 聚类集合中样本数为 0 或 1 的情况，使得聚类效 果不均衡。 初始聚类中心的选取，不仅要求分布在较密 集的范围内，还需要保证各初始聚类中心尽可能 分散。针对上述问题，利用可拓距中数据分布情 ρl ρr ρl ρr 况对左右侧距平均值的影响，将经典平均距离映 射为两个平均侧距值，如图 2 所示，其中平均左侧 距值相对中心点靠左分布，平均右侧距值相对中 心点靠右分布。特别指出，当数据在区间对称分 布时，左右平均可拓侧距值重合于一点。将可拓 平均左侧距 作为衡量密集度指标，可拓平均右 侧距 作为衡量疏远度指标，首个大于可拓平均 左侧距 所对应中心坐标作为第一个聚类中心， 下一待选取初始聚类中心点需满足与各已确定初 始聚类中心点间可拓距均大于可拓右侧平均距 ，方可作为聚类中心点。 初始中心点 图 1 初始中心点展示图 Fig. 1 The display map of first initial center point x0 avg o x1 ρ0 o ρ1 经典距 可拓距 ρl ρr 图 2 经典距向可拓距映射 Fig. 2 Mapping of classical distances to extension distances η 当选出初始聚类中心点数未达到所要求个数 时，引入缩放因子 如式 (7) 所示，对可拓平均右 侧距进行缩放，选出满足个数的初始聚类中心点。 η = 1+ C 2 n −k ′ C2 n k ′ , K 1 , k ′ = K (8) k 其中， ′ 为每次遍历后，所获得的初始聚类中心个 数；K 为指定聚类中心数。 最后按传统聚类算法进行聚类。选取的一组 最优初始聚类中心点克服了中心点出现于边界非 密集区域缺陷，最大限度分布在密集区且各聚类 中心点均匀分布。 ·346· 智 能 系 统 学 报 第 15 卷
第2期 赵燕伟，等：基于可拓距的改进k-means聚类算法 ·347· 2.2改进k-means算法初始聚类中心选取流程 3实验与分析 根据上述思想，得到改进k-means算法初始 聚类中心选取的具体实施步骤如下： 为了验证本文所提出算法的有效性，将本文 1)按式(4)计算出两两样本间距离及等效密 算法与传统k-means算法及文献[22-23]所提出的 集距离区间[A,B]: 改进聚类算法进行对比分析。 2)按式(5)和式(6)将距离映射为可拓左侧距 实验所用的测试数据集为UCI数据库中用于 pD及可拓右侧距P,D,将p按从小到大顺序 测试聚类的Iris数据集和Wine数据集，各数据的 依次排序，同时按式(7)计算样本间可拓平均左 特征如表1所示。 侧距可及可拓平均右侧距p; 表1 各数据集的基本特征 Table 1 Characteristics of datasets 3)遍历排序好的可拓距，将其中首个大于样 数据集 样本维数 本间可拓平均左侧距可的可拓距对应中心点坐 样本个数 分类数 标作为第一个初始聚类中心。 Iris 150 4)计算排好序可拓距中下一个值对应中心点 Wine 179 3 坐标并依次计算出其与已确定的初始聚类中心的 基于本文提出算法对Iris、Wine数据进行初 可拓距，将其与样本平均可拓右侧距F进行比 始中心点选取，特别指出，为了观察初始聚类中 较，若其均大于可，则该中心点坐标作为下一个 心点选取位置的大体远近及分散程度，本文为节 初始聚类中心；否则重新执行步骤4)。 省篇幅，只展示数据集两属性的二维图3和图4。 5)如果遍历一次后，初始聚类中心未达到K, 从图3和图4中可看出本文提出改进算法选取的 则按式(8)计算出缩小因子，动态缩小样本平均 初始聚类中心点，对低维与高维数据选取的初始 可拓右侧距可，重新回到步骤3)。 聚类中心点，相较于其他改进算法分布更均匀， 6)若聚类中心数达到K时，则完成初始聚类 位于边界区域初始聚类中心点，其周围数据点也 中心的选取。 相对密集。 4.5r 4.5 4.5 840 号4.0 84.0 35 35 35 3.0 3.0 3.0 25 2.5 2.0 2.0上 2.0 4.55.05.56.06.57.07.58.0 4.55.05.56.06.57.07.58.0 4.55.05.56.06.57.07.58.0 花萼长度/cm 花萼长度/cm 花萼长度/cm (a)基于可拓距方法 (b)基于密集度方法 (c)基于平均差异度方法 图3基于Iis数据的初始聚类中心点分布对比 Fig.3 Comparison of distribution of initial cluster centers based on Iris dataset 6 6 6 5 5 5 …… 34 2 2 3 1 11.0 12.013.014.0 15.0 11.012.013.0 14.015.0 11.0 12.013.014.015.0 乙醇 乙醇 乙醇 (a)基于可拓距方法 (b)基于密集度方法 (c)基于平均差异度方法 图4基于Wine数据的初始聚类中心点分布对比 Fig.4 Comparison of distribution of initial cluster centers based on Wine dataset 为了定量描述初始聚类中心点选取的质量， 情况和现有改进算法聚类情况进行对比，其聚类 本文先将所选中心点聚类，将其与样本实际聚类 效果图5和图6
2.2 改进 k-means 算法初始聚类中心选取流程 根据上述思想，得到改进 k-means 算法初始 聚类中心选取的具体实施步骤如下： 1）按式 (4) 计算出两两样本间距离及等效密 集距离区间 [A,B]； ρl (i, j) ρr (i, j) ρl (i, j) ρl ρr 2）按式 (5) 和式 (6) 将距离映射为可拓左侧距 及可拓右侧距 ，将 按从小到大顺序 依次排序，同时按式 (7) 计算样本间可拓平均左 侧距 及可拓平均右侧距 ； ρl 3）遍历排序好的可拓距，将其中首个大于样 本间可拓平均左侧距 的可拓距对应中心点坐 标作为第一个初始聚类中心。 ρr ρr 4）计算排好序可拓距中下一个值对应中心点 坐标并依次计算出其与已确定的初始聚类中心的 可拓距，将其与样本平均可拓右侧距 进行比 较，若其均大于 ，则该中心点坐标作为下一个 初始聚类中心；否则重新执行步骤 4）。 η ρr 5）如果遍历一次后，初始聚类中心未达到 K， 则按式 (8) 计算出缩小因子 ，动态缩小样本平均 可拓右侧距 ，重新回到步骤 3）。 6）若聚类中心数达到 K 时，则完成初始聚类 中心的选取。 3 实验与分析 为了验证本文所提出算法的有效性，将本文 算法与传统 k-means 算法及文献 [22-23] 所提出的 改进聚类算法进行对比分析。 实验所用的测试数据集为 UCI 数据库中用于 测试聚类的 Iris 数据集和 Wine 数据集，各数据的 特征如表 1 所示。 表 1 各数据集的基本特征 Table 1 Characteristics of datasets 数据集 样本个数 样本维数 分类数 Iris 150 4 3 Wine 179 13 3 基于本文提出算法对 Iris、Wine 数据进行初 始中心点选取，特别指出，为了观察初始聚类中 心点选取位置的大体远近及分散程度，本文为节 省篇幅，只展示数据集两属性的二维图 3 和图 4。 从图 3 和图 4 中可看出本文提出改进算法选取的 初始聚类中心点，对低维与高维数据选取的初始 聚类中心点，相较于其他改进算法分布更均匀， 位于边界区域初始聚类中心点，其周围数据点也 相对密集。 (a) 基于可拓距方法 4.5 4.5 5.0 5.5 6.0 6.5 7.0 7.5 8.0 4.0 3.5 3.0 花萼宽度/cm 花萼长度/cm 2.5 2.0 (c) 基于平均差异度方法 4.5 4.5 5.0 5.5 6.0 6.5 7.0 7.5 8.0 4.0 3.5 3.0 花萼宽度/cm 花萼长度/cm 2.5 2.0 (b) 基于密集度方法 4.5 4.5 5.0 5.5 6.0 6.5 7.0 7.5 8.0 4.0 3.5 3.0 花萼宽度/cm 花萼长度/cm 2.5 2.0 图 3 基于 Iris 数据的初始聚类中心点分布对比 Fig. 3 Comparison of distribution of initial cluster centers based on Iris dataset (a) 基于可拓距方法 6 11.0 12.0 13.0 14.0 15.0 5 4 3 苹果酸 乙醇 2 1 (b) 基于密集度方法 6 11.0 12.0 13.0 14.0 15.0 5 4 3 苹果酸 乙醇 2 1 (c) 基于平均差异度方法 6 11.0 12.0 13.0 14.0 15.0 5 4 3 苹果酸 乙醇 2 1 图 4 基于 Wine 数据的初始聚类中心点分布对比 Fig. 4 Comparison of distribution of initial cluster centers based on Wine dataset 为了定量描述初始聚类中心点选取的质量， 本文先将所选中心点聚类，将其与样本实际聚类 情况和现有改进算法聚类情况进行对比，其聚类 效果图 5 和图 6。 第 2 期 赵燕伟，等：基于可拓距的改进 k-means 聚类算法 ·347·
·348· 智能系统学报 第15卷 其中，图5与图6中3种颜色代表3个聚类簇，可 的改进算法，虽然仍存在误差，但误差的大小有 看出其他两种改进算法，由于初始中心点分布不 所缩小，尤其在对更高维的Wine数据集聚类时， 均匀且有位于稀疏边界的中心点，从而导致对两 优势更明显。 组样本集聚类的结果存在一定误差，但本文提出 654321 654 321 4.0 4.0 5.0 6.0 花萼宽度cm 3.0 5.0 花萼长度/c 7.08.02. 6.0 3.0 花萼长度cm 7.0 020花普0暖@ (a)实际聚类 (b)基于可拓距方法聚类 6543 765 43 2 21 4.0 4.0 5.0 3.0 6.0 花萼宽度cm 5.0 3.0 花萼长度cm 7.0 6.0 8.02. 花萼长度em 7.0 8.02. 花萼宽度/cm (c)基于密集度方法聚 (d基于平均差异度方法聚类 图5基于Iris数据聚类对比图 Fig.5 Comparison of clustering based on Iris dataset 13.25 00 222, 11.012.0 3￥6 13.0 11.012.0 13.0 乙醇 1401502线梁 (a)实际聚类 (b)基于可拓距方法聚类 1 50 11.0 12.0 11.0 12.0 13.0 13.0 乙醇 1050了20 乙醇 14.015.0 (c)基于密集度方法聚类 (d)基于平均差异度方法聚类 图6基于Wine数据聚类对比 Fig.6 Comparison of clustering based on Wine dataset 为了定量衡量算法的有效性，本文采用分类 与总样本个数比值以及聚类均衡性指标，即各类 正确率指标，即被正确分到对应类别的样本个数 中样本个数与实际相应类中样本个数的方差，进
其中，图 5 与图 6 中 3 种颜色代表 3 个聚类簇，可 看出其他两种改进算法，由于初始中心点分布不 均匀且有位于稀疏边界的中心点，从而导致对两 组样本集聚类的结果存在一定误差，但本文提出 的改进算法，虽然仍存在误差，但误差的大小有 所缩小，尤其在对更高维的 Wine 数据集聚类时， 优势更明显。 (a) 实际聚类 7 6 5 4 3 2 1 花瓣长度/cm 花萼长度/cm 8.0 2.0 7.0 6.0 5.0 3.0 花萼宽度/cm 4.0 (b) 基于可拓距方法聚类 7 6 5 4 3 2 1 花瓣长度/cm 花萼长度/cm 8.0 2.0 7.0 6.0 5.0 3.0 花萼宽度/cm 4.0 (c) 基于密集度方法聚类 7 6 5 4 3 2 1 花瓣长度/cm 花萼长度/cm 8.0 2.0 7.0 6.0 5.0 3.0 花萼宽度/cm 4.0 (d) 基于平均差异度方法聚类 7 6 5 4 3 2 1 花瓣长度/cm 花萼长度/cm 8.0 2.0 7.0 6.0 5.0 3.0 花萼宽度/cm 4.0 图 5 基于 Iris 数据聚类对比图 Fig. 5 Comparison of clustering based on Iris dataset (a) 实际聚类 3.25 3.00 2.75 2.50 2.25 2.00 1.75 1.50 烬 乙醇 15.0 1 14.0 13.0 12.0 11.0 3 2 苹果酸 6 5 4 (b) 基于可拓距方法聚类 3.25 3.00 2.75 2.50 2.25 2.00 1.75 1.50 烬 乙醇 15.0 1 14.0 13.0 12.0 11.0 3 2 苹果酸 6 5 4 (c) 基于密集度方法聚类 3.25 3.00 2.75 2.50 2.25 2.00 1.75 1.50 烬 乙醇 15.0 1 14.0 13.0 12.0 11.0 3 2 苹果酸 6 5 4 (d) 基于平均差异度方法聚类 3.25 3.00 2.75 2.50 2.25 2.00 1.75 1.50 烬 乙醇 15.0 1 14.0 13.0 12.0 11.0 3 2 苹果酸 6 5 4 图 6 基于 Wine 数据聚类对比 Fig. 6 Comparison of clustering based on Wine dataset 为了定量衡量算法的有效性，本文采用分类 正确率指标，即被正确分到对应类别的样本个数 与总样本个数比值以及聚类均衡性指标，即各类 中样本个数与实际相应类中样本个数的方差，进 ·348· 智 能 系 统 学 报 第 15 卷