【人工智能基础】基于可拓距的改进k-means聚类算法

第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 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 聚类是数据分析的重要手段，将数据集分为 若干类，使得簇内紧密且相似性大，簇与簇之间 有明显区别，使得相似性最小，在数据挖掘、图像 处理等领域被广泛应用[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=之距为 可确定聚类算法，通过网格对象的密度值进行划 分以完成聚类；李亚等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 的分布式改进 k￾means 算法，通过引入 Canopy 算法初始化 k-means 算法的聚类中心；Tzortzis G 等 [10] 提出了 MinMax k-means 算法，在初始化不好的情况下通过赋予方 差权重以优化目标提高聚类效果；Laith Moham￾mad Abualigah 等 [11] 将 k-means 算法采用和声搜索 方法进行优化并应用于文本聚类中，提高了聚类 精度；Li Yanyan 等 [12] 提出一种基于粒子群优化 的 k-means 算法，并将其应用在岩体不连续数据 分类中；Khanmohammadi 等 [13] 为克服对初始聚类 中心的敏感问题，提出了一种混合 k-谐波均值和 重叠 k 均值算法的混合方法来克服缺点。以上改 进算法都起到了较好的聚类效果，但在初始聚类 中心选取问题上仍存在首个初始聚类中心点落于 稀疏边界的缺陷。 基于此，本文提出一种基于可拓距的改进 k￾means 聚类算法，将可拓学思想与 k-means 算法有 效的结合，通过引入可拓侧距和缩放因子，对首 个初始聚类中心点进行优化，选出一组最优初始 聚类中心点，并通过仿真对比检验本文改进算法 的可行性。通过实验验证，该方法具有更好的聚 类效果。 1 基本知识 1.1 可拓距相关知识 可拓学是以蔡文教授为首的我国学者们创立 的新学科，近年来，可拓学在计算机，人工智能、 检测、控制等领域进行的应用取得了良好的成 绩 [14]。其中，可拓距在实例检索领域应用较为广 泛，通过可拓距构造关联函数，依据样本间关联 度识别案例类别[15-19] ，显著提高了案例检索效率 与正确率。 在经典数学中，当点在区间内时，默认点与区 间的距离为零，即“类内即为同”，无法将事物内 部的“质变”、“量变”表达出来。因此，为了描述 类内事物 (区间内的点) 的区别，在可拓学中规 定：实轴上任意一点 x 与区间 X0=之距为[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,dA 0, A生Z 其中：A,=p(A,A,Z)= A-B, A∈Z 0⑧(A-B),A使Z且A∈Z. (5) A-d,dB. 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 其中 : Az=ρl(A,A,Z)=    0, A− B, 0⊗(A− B), A 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 卷

第2期 赵燕伟，等：基于可拓距的改进k-means聚类算法 ·349· 行衡量。 算法在聚类的均衡性上差异较小，但当维数增高 对初始聚类中心点聚类后分类正确率统计如 时，现有改进算法聚类均衡性和分类准确性会降 表2所示。对初始聚类中心点聚类后各簇类样本 低，导致个别类中样本较多，相反也会出现有些 的个数统计如表3所示。由表3得出改进前后算 类中样本过少的情况，使得之后聚类中心点更新 法的均衡性指标如表4所示。从表2与表4中可 时，较少样本数据的中心点在迭代更新时坐标变 看出当数据集样本维数不高时，本文算法与改进 化不明显，从而导致最终聚类效果差。 表2改进前后算法聚类正确率指标 Table 2 Accuracy of clustering algorithm before and after % 数据集 文献[17改进算法 文献[18]改进算法 传统k-means?算法 本文提出算法 Iris 87.36 85.24 82.37 86.79 Wine 61.05 63.07 60.12 65.28 表3改进前后算法聚类后各簇类样本个数 Table 3 The number of samples in each cluster 数据 实际各簇数 本文提出算法各簇数 文献[1刀改进算法各簇数 文献[18]改进算法各簇数 Iris [50,50,50] [40,29,81] [53,84,13] [61,39,50] Wine [59,71,48] [27,78,73] [118,53,7刀 [116,4,58] 表4改进前后算法聚类均衡性指标 Table 4 Balance of clustering algorithm before and after 均衡性指标 实际聚类 本文提出算法聚类 文献[17刀改进算法聚类 文献[18]改进算法聚类 Iris 0 22.4 29.1 8.98 Wine 0 23.8 42.77 51.11 4结束语 参考文献： 本文提出一种基于可拓距的改进k-means聚 [1]于佐军，秦欢.基于改进蜂群算法的k-means算法).控 类算法，将样本间平均距离映射为可拓距上对应 制与决策，2018,33(1)181-185. 两个平均侧距，作为初始聚类中心选取的约束范 YU Zuojun,QIN Huan.k-means algorithm based on im- 围，克服了首个选取的初始中心点可能位于较疏 proved artificial bee colony algorithm[J].Control and de- cision,2018,33(1):181-185 散边界的缺陷。实验表明在高维数据集的情况 [2]HE Hong,TAN Yonghong.Automatic pattern recognition 下，基于可拓距的改进k-means算法选取的初始 of ECG signals using entropy-based adaptive dimensional- 聚类中心点聚类具有较高的正确率和均衡率，表 ity reduction and clustering[J].Applied soft computing, 明选取的初始聚类中心点较优，更适合大数据背 2017,55:238-252 景下的海量、高维数据聚类。 [3]PENG Chong,KANG Zhao,XU Fei,et al.Image projec- 本文对k-means聚类算法初始聚类中心的选 tion ridge regression for subspace clustering[J].IEEE sig- 取展开了研究，由于时间和个人能力有限，还存 nal processing letters,2017,24(7):991-995. 在不足之处有待后续研究中深化、提高：1)本文 [4]ROTHLISBERGER V,ZISCHG A P,KEILER M,et al. 算法对非数值型的数据集样本如何衡量相似度， Identifying spatial clusters of flood exposure to support de- cision making in risk management[J].Science of the total 并没有给出解决方法。2)文中提到的缩放因子并 environment,2017,598:593-603 不能自适应的变化，对算法的性能有所影响。 [5]何熊熊，管俊轶，叶宣佐，等.一种基于密度和网格的簇 3)如何引人关联函数代替距离计算相似度，是值 心可确定聚类算法[J].控制与决策，2017,32(5)： 得深人研究的问题。4)在理论上和实用上的意义 913-919. 及价值。5)进一步深入研究本课题的建议。 HE Xiongxiong,GUAN Junyi,YE Xuanzuo,et al.A dens-

行衡量。 对初始聚类中心点聚类后分类正确率统计如 表 2 所示。对初始聚类中心点聚类后各簇类样本 的个数统计如表 3 所示。由表 3 得出改进前后算 法的均衡性指标如表 4 所示。从表 2 与表 4 中可 看出当数据集样本维数不高时，本文算法与改进 算法在聚类的均衡性上差异较小，但当维数增高 时，现有改进算法聚类均衡性和分类准确性会降 低，导致个别类中样本较多，相反也会出现有些 类中样本过少的情况，使得之后聚类中心点更新 时，较少样本数据的中心点在迭代更新时坐标变 化不明显，从而导致最终聚类效果差。 表 2 改进前后算法聚类正确率指标 Table 2 Accuracy of clustering algorithm before and after % 数据集 文献[17]改进算法 文献[18]改进算法 传统k-means算法 本文提出算法 Iris 87.36 85.24 82.37 86.79 Wine 61.05 63.07 60.12 65.28 表 3 改进前后算法聚类后各簇类样本个数 Table 3 The number of samples in each cluster 数据 实际各簇数 本文提出算法各簇数 文献[17]改进算法各簇数 文献[18]改进算法各簇数 Iris [50, 50, 50] [40, 29, 81] [53, 84, 13] [61, 39, 50] Wine [59, 71, 48] [27, 78, 73] [118, 53, 7] [116, 4, 58] 表 4 改进前后算法聚类均衡性指标 Table 4 Balance of clustering algorithm before and after 均衡性指标 实际聚类 本文提出算法聚类 文献[17]改进算法聚类 文献[18]改进算法聚类 Iris 0 22.4 29.1 8.98 Wine 0 23.8 42.77 51.11 4 结束语 本文提出一种基于可拓距的改进 k-means 聚 类算法，将样本间平均距离映射为可拓距上对应 两个平均侧距，作为初始聚类中心选取的约束范 围，克服了首个选取的初始中心点可能位于较疏 散边界的缺陷。实验表明在高维数据集的情况 下，基于可拓距的改进 k-means 算法选取的初始 聚类中心点聚类具有较高的正确率和均衡率，表 明选取的初始聚类中心点较优，更适合大数据背 景下的海量、高维数据聚类。 本文对 k-means 聚类算法初始聚类中心的选 取展开了研究，由于时间和个人能力有限，还存 在不足之处有待后续研究中深化、提高：1) 本文 算法对非数值型的数据集样本如何衡量相似度， 并没有给出解决方法。2) 文中提到的缩放因子并 不能自适应的变化，对算法的性能有所影响。 3) 如何引入关联函数代替距离计算相似度，是值 得深入研究的问题。4) 在理论上和实用上的意义 及价值。5) 进一步深入研究本课题的建议。 参考文献： 于佐军, 秦欢. 基于改进蜂群算法的 k-means 算法 [J]. 控 制与决策, 2018, 33(1): 181–185. YU Zuojun, QIN Huan. k-means algorithm based on im￾proved artificial bee colony algorithm[J]. Control and de￾cision, 2018, 33(1): 181–185. [1] HE Hong, TAN Yonghong. Automatic pattern recognition of ECG signals using entropy-based adaptive dimensional￾ity reduction and clustering[J]. Applied soft computing, 2017, 55: 238–252. [2] PENG Chong, KANG Zhao, XU Fei, et al. Image projec￾tion ridge regression for subspace clustering[J]. IEEE sig￾nal processing letters, 2017, 24(7): 991–995. [3] RÖTHLISBERGER V, ZISCHG A P, KEILER M, et al. Identifying spatial clusters of flood exposure to support de￾cision making in risk management[J]. Science of the total environment, 2017, 598: 593–603. [4] 何熊熊, 管俊轶, 叶宣佐, 等. 一种基于密度和网格的簇 心可确定聚类算法 [J]. 控制与决策, 2017, 32(5): 913–919. HE Xiongxiong, GUAN Junyi, YE Xuanzuo, et al. A dens- [5] 第 2 期 赵燕伟，等：基于可拓距的改进 k-means 聚类算法 ·349·

·350· 智能系统学报 第15卷 ity-based and grid-based cluster centers determination clus- 研究D].哈尔滨：哈尔滨工程大学，2010. tering algorithm[J].Control and decision,2017,32(5): GUAN Fengxu.Research on finger vein recognition 913-919 based on manifold learning and extension classifier[D]. [6]李亚，刘丽平，李柏青，等.基于改进K-Means聚类和 Harbin:Harbin Engineering University,2010. BP神经网络的台区线损率计算方法).中国电机工程 [16]赵燕伟，苏楠，张峰，等.基于可拓实例推理的产品族配 学报，2016,36(17)：4543-4551. 置设计方法[U.机械工程学报，2010,46(15)：146-154. LI Ya,LIU Liping,LI Baiqing,et al.Calculation of line ZHAO Yanwei,SU Nan,ZHANG Feng,et al.Configura- loss rate in transformer district based on improved K- tion design method for product family based on extension Means clustering algorithm and BP neural network[J].Pro- case reasoning[J].Journal of mechanical engineering, ceedings of the CSEE,2016,36(17):4543-4551. 2010,46(15):146-154. [7]邢长征，谷浩.基于平均密度优化初始聚类中心的k- [17刀叶永伟，张帆，王运.基于可拓距的起重机产品配置方 means算法[.计算机工程与应用，2014,50(20)： 法设计.中国制造业信息化，2012,41(23)：24-27. 135-138 YE Yongwei,ZHANG Fan,WANG Yun.The crane XING Changzheng,GU Hao.K-means algorithm based on products configuration design based on extension dis- average density optimizing initial cluster centre[J].Com- tance[J].Manufacturing information engineering of puter engineering and applications,2014,50(20):135-138. China.2012,41(23):2427. [8]张天骐，杨强，宋玉龙，等.一种K-means改进算法的软 [18]NOUAOURIA N.BOUKADOUM M.Case retrieval with 扩频信号伪码序列盲估计).电子与信息学报，2018， combined adaptability and similarity criteria:application 40(1):226-234 to case retrieval nets[C]//Proceedings of the 18th Interna- ZHANG Tianqi,YANG Qiang,SONG Yulong,et al.Blind tional Conference on Case-Based Reasoning.Research estimation PN sequence in soft spread spectrum signal of and Development.Alessandria,Italy,2010:242-256. improved K-means algorithm[J].Journal of electronics [19]赵燕伟，任设东，陈尉刚，等.基于改进BP神经网络的 information technology,2018,40(1):226-234. 可拓分类器构建[J.计算机集成制造系统，2015 [9]李晓瑜，俞丽颖，雷航，等.一种K-means改进算法的并 21(10):2807-2815 行化实现与应用).电子科技大学学报，2017,46(1) ZHAO Yanwei,REN Shedong,CHEN Weigang,et al. 61-68. Extension classifier construction based on improved BP LI Xiaoyu,YU Liying,LEI Hang,et al.The parallel imple- neural network[J].Computer integrated manufacturing mentation and application of an improved K-means al- systems,.2015,21(10y:2807-2815. gorithm[J].Journal of University of Electronic Science and [20]李敏.K-means算法的改进及其在文本聚类中的应用研 Technology of China,2017,46(1):61-68. 究D].无锡：江南大学，2018 [10]TZORTZIS G,LIKAS A.The MinMax k-means cluster- LI Min.The research and application of text clustering ing algorithm[J].Pattern recognition,2014,47(7): based on improved K-means algorithm[D].Wuxi:Jiang- 2505-2516. nan University,2018. [11]ABUALIGAH L M,KHADER A T,AI-BETAR M A. [21]杨明极，马池，王娅，等.一种改进K-means聚类的 Unsupervised feature selection technique based on har- FCMM算法[J].计算机应用研究，2019,36(7)： mony search algorithm for improving the text 2007-2010. clustering[C]//Proceedings of the 7th International Con- YANG Mingji,MA Chi,WANG Ya,et al.Algorithm ference on Computer Science and Information Techno- named FCMM to improve K-means clustering logy.Amman,Jordan,2016:1-6. algorithm [J].Application research of computers,2019, [12]LI Yanyan,WANG Qing,CHEN Jianping,et al.K-means 36(7):2007-2010. algorithm based on particle swarm optimization for the [22]韩俊，谈健，黄河，等.基于改进K-means聚类算法的供 identification of rock discontinuity sets[J.Rock mechan- 电块划分方法[J].电力自动化设备，2015,35(6)： ics and rock engineering,2015,48(1):375-385. 123-129. [13]KHANMOHAMMADI S,ADIBEIG N,SHANE- HAN Jun,TAN Jian,HUANG He,et al.Power-supply- HBANDY S.An improved overlapping k-means cluster- ing block partition based on improved K-means cluster- ing method for medical applications[J].Expert systems ing algorithm[J].Electric power automation equipment, with applications,2017,67:12-18. 2015,35(6):123-129. [14]杨春燕，蔡文.可拓学M.北京：科学出版社，2014. [23]李武，赵娇燕，严太山.基于平均差异度优选初始聚类 [15]管凤旭.基于流形学习及可拓分类器的手指静脉识别 中心的改进K-均值聚类算法.控制与决策，2017

ity-based and grid-based cluster centers determination clus￾tering algorithm[J]. Control and decision, 2017, 32(5): 913–919. 李亚, 刘丽平, 李柏青, 等. 基于改进 K-Means 聚类和 BP 神经网络的台区线损率计算方法 [J]. 中国电机工程 学报, 2016, 36(17): 4543–4551. LI Ya, LIU Liping, LI Baiqing, et al. Calculation of line loss rate in transformer district based on improved K￾Means clustering algorithm and BP neural network[J]. Pro￾ceedings of the CSEE, 2016, 36(17): 4543–4551. [6] 邢长征, 谷浩. 基于平均密度优化初始聚类中心的 k￾means 算法 [J]. 计算机工程与应用, 2014, 50(20): 135–138. XING Changzheng, GU Hao. K-means algorithm based on average density optimizing initial cluster centre[J]. Com￾puter engineering and applications, 2014, 50(20): 135–138. [7] 张天骐, 杨强, 宋玉龙, 等. 一种 K-means 改进算法的软 扩频信号伪码序列盲估计 [J]. 电子与信息学报, 2018, 40(1): 226–234. ZHANG Tianqi, YANG Qiang, SONG Yulong, et al. Blind estimation PN sequence in soft spread spectrum signal of improved K-means algorithm[J]. Journal of electronics & information technology, 2018, 40(1): 226–234. [8] 李晓瑜, 俞丽颖, 雷航, 等. 一种 K-means 改进算法的并 行化实现与应用 [J]. 电子科技大学学报, 2017, 46(1): 61–68. LI Xiaoyu, YU Liying, LEI Hang, et al. The parallel imple￾mentation and application of an improved K-means al￾gorithm[J]. Journal of University of Electronic Science and Technology of China, 2017, 46(1): 61–68. [9] TZORTZIS G, LIKAS A. The MinMax k-means cluster￾ing algorithm[J]. Pattern recognition, 2014, 47(7): 2505–2516. [10] ABUALIGAH L M, KHADER A T, AI-BETAR M A. Unsupervised feature selection technique based on har￾mony search algorithm for improving the text clustering[C]//Proceedings of the 7th International Con￾ference on Computer Science and Information Techno￾logy. Amman, Jordan, 2016: 1–6. [11] LI Yanyan, WANG Qing, CHEN Jianping, et al. K-means algorithm based on particle swarm optimization for the identification of rock discontinuity sets[J]. Rock mechan￾ics and rock engineering, 2015, 48(1): 375–385. [12] KHANMOHAMMADI S, ADIBEIG N, SHANE￾HBANDY S. An improved overlapping k-means cluster￾ing method for medical applications[J]. Expert systems with applications, 2017, 67: 12–18. [13] [14] 杨春燕, 蔡文. 可拓学 [M]. 北京: 科学出版社, 2014. [15] 管凤旭. 基于流形学习及可拓分类器的手指静脉识别 研究 [D]. 哈尔滨: 哈尔滨工程大学, 2010. GUAN Fengxu. Research on finger vein recognition based on manifold learning and extension classifier[D]. Harbin: Harbin Engineering University, 2010. 赵燕伟, 苏楠, 张峰, 等. 基于可拓实例推理的产品族配 置设计方法 [J]. 机械工程学报, 2010, 46(15): 146–154. ZHAO Yanwei, SU Nan, ZHANG Feng, et al. Configura￾tion design method for product family based on extension case reasoning[J]. Journal of mechanical engineering, 2010, 46(15): 146–154. [16] 叶永伟, 张帆, 王运. 基于可拓距的起重机产品配置方 法设计 [J]. 中国制造业信息化, 2012, 41(23): 24–27. YE Yongwei, ZHANG Fan, WANG Yun. The crane products configuration design based on extension dis￾tance[J]. Manufacturing information engineering of China, 2012, 41(23): 24–27. [17] NOUAOURIA N, BOUKADOUM M. Case retrieval with combined adaptability and similarity criteria: application to case retrieval nets[C]//Proceedings of the 18th Interna￾tional Conference on Case-Based Reasoning. Research and Development. Alessandria, Italy, 2010: 242–256. [18] 赵燕伟, 任设东, 陈尉刚, 等. 基于改进 BP 神经网络的 可拓分类器构建 [J]. 计算机集成制造系统, 2015, 21(10): 2807–2815. ZHAO Yanwei, REN Shedong, CHEN Weigang, et al. Extension classifier construction based on improved BP neural network[J]. Computer integrated manufacturing systems, 2015, 21(10): 2807–2815. [19] 李敏. K-means 算法的改进及其在文本聚类中的应用研 究 [D]. 无锡: 江南大学, 2018. LI Min. The research and application of text clustering based on improved K-means algorithm[D]. Wuxi: Jiang￾nan University, 2018. [20] 杨明极, 马池, 王娅, 等. 一种改进 K-means 聚类的 FCMM 算法 [J]. 计算机应用研究, 2019, 36(7): 2007–2010. YANG Mingji, MA Chi, WANG Ya, et al. Algorithm named FCMM to improve K-means clustering algorithm[J]. Application research of computers, 2019, 36(7): 2007–2010. [21] 韩俊, 谈健, 黄河, 等. 基于改进 K-means 聚类算法的供 电块划分方法 [J]. 电力自动化设备, 2015, 35(6): 123–129. HAN Jun, TAN Jian, HUANG He, et al. Power-supply￾ing block partition based on improved K-means cluster￾ing algorithm[J]. Electric power automation equipment, 2015, 35(6): 123–129. [22] 李武, 赵娇燕, 严太山. 基于平均差异度优选初始聚类 中心的改进 K-均值聚类算法 [J]. 控制与决策, 2017, [23] ·350· 智 能 系 统 学 报 第 15 卷

第2期 赵燕伟，等：基于可拓距的改进k-means聚类算法 ·351· 32(4):759-762 朱芬，硕士研究生，主要研究方向 LI Wu,ZHAO Jiaoyan,YAN Taishan.Improved K- 为可拓设计。 means clustering algorithm optimizing initial clustering centers based on average difference degree[J].Control and decision,2017,32(4):759-762 作者简介： 赵燕伟，教授，博土生导师，博土， 桂方志，博士研究生，主要研究方 主要研究方向为可拓设计理论与方 向为可拓设计。 法、物流系统智能配送与优化调度、数 字化产品现代设计。出版教材4部， 多次获得国家自然基金项目资助等。 发表学术论文100余篇。 全国第17届可拓学年会 “全国第17届可拓学年会”将于2020年8月14一16日在江苏南京召开。会议由中国人工智能学会主 办，由中国人工智能学会可拓学专业委员会、南京审计大学、《智能系统学报》编辑部、广东工业大学可拓 学与创新方法研究所等单位联合承办。会议将交流近年来可拓学的理论和应用研究成果，讨论可拓学发展 方向、学科建设和人才培养等问题。为此诚邀国内外相关领域的专家学者、管理人员和工程技术人员参加会议。 本次会议征文范围为可拓学理论、方法与应用方面的最新研究成果，包括但不限于： 1)可拓论：基元理论、可拓集、可拓逻辑。 2)可拓创新方法：可拓模型建立方法，拓展分析方法，可拓变换方法，优度评价方法，矛盾问题求解方法等。 3)可拓工程：可拓智能、可拓设计、可拓控制、可拓检测、可拓决策、可拓管理，以及可拓学与其他学科 (如计算机、数学、自动化、审计、经济、教育、教学等)的交叉研究成果。 征文要求： 1)文笔精练、资料可靠，字数不超过7000字，并附中英文摘要和关键词。 2)论文应是新的研究成果，严格按照科技论文规范撰写，且未在学术会议或刊物上发表。 会议征文中被大会录用的论文，需要作者参加会议交流，再由可拓学学术委员会评审出优秀论文，推荐 到《智能系统学报》、《数学的实践与认识》等核心期刊和《广东工业大学学报》（中国科技核心期刊） “可拓论坛”正式发表。 欢迎相关领域的研究人员、高校师生、企业家、工程技术人员、以及一切爱好和有志于可拓学研究的朋 友踊跃投稿。 本届大会的征文采用E-mail投稿的方式，投稿邮箱：extenics@vip.163.com 重要日期： 征文截止日期：2020年5月30日 录用通知日期：2020年6月30日 会议时间：2020年8月14一16日 联系方式： 联系地址：广东工业大学可拓学与创新方法研究所 联系人：李剑明汤龙 E-mail:extenics@vip.163.com 联系电话：020-39322973，传真：020-39322019 会议网址：htp://extenics.gdut.edu.cn/

32(4): 759–762. LI Wu, ZHAO Jiaoyan, YAN Taishan. Improved K￾means clustering algorithm optimizing initial clustering centers based on average difference degree[J]. Control and decision, 2017, 32(4): 759–762. 作者简介： 赵燕伟，教授，博士生导师，博士， 主要研究方向为可拓设计理论与方 法、物流系统智能配送与优化调度、数 字化产品现代设计。出版教材 4 部， 多次获得国家自然基金项目资助等。 发表学术论文 100 余篇。 朱芬，硕士研究生，主要研究方向 为可拓设计。 桂方志，博士研究生，主要研究方 向为可拓设计。 全国第 17 届可拓学年会 “全国第 17 届可拓学年会”将于 2020 年 8 月 14—16 日在江苏南京召开。会议由中国人工智能学会主 办，由中国人工智能学会可拓学专业委员会、南京审计大学、《智能系统学报》编辑部、广东工业大学可拓 学与创新方法研究所等单位联合承办。会议将交流近年来可拓学的理论和应用研究成果，讨论可拓学发展 方向、学科建设和人才培养等问题。为此诚邀国内外相关领域的专家学者、管理人员和工程技术人员参加会议。 本次会议征文范围为可拓学理论、方法与应用方面的最新研究成果，包括但不限于： 1）可拓论：基元理论、可拓集、可拓逻辑。 2）可拓创新方法:可拓模型建立方法，拓展分析方法，可拓变换方法，优度评价方法，矛盾问题求解方法等。 3）可拓工程：可拓智能、可拓设计、可拓控制、可拓检测、可拓决策、可拓管理，以及可拓学与其他学科 （如计算机、数学、自动化、审计、经济、教育、教学等）的交叉研究成果。 征文要求： 1）文笔精练、资料可靠，字数不超过 7000 字，并附中英文摘要和关键词。 2）论文应是新的研究成果，严格按照科技论文规范撰写，且未在学术会议或刊物上发表。 会议征文中被大会录用的论文，需要作者参加会议交流，再由可拓学学术委员会评审出优秀论文，推荐 到《智能系统学报》、《数学的实践与认识》等核心期刊和《广东工业大学学报》（中国科技核心期刊） “可拓论坛”正式发表。 欢迎相关领域的研究人员、高校师生、企业家、工程技术人员、以及一切爱好和有志于可拓学研究的朋 友踊跃投稿。 本届大会的征文采用 E-mail 投稿的方式，投稿邮箱：extenics@vip.163.com 重要日期： 征文截止日期：2020 年 5 月 30 日 录用通知日期：2020 年 6 月 30 日 会议时间：2020 年 8 月 14—16 日 联系方式： 联系地址：广东工业大学可拓学与创新方法研究所 联系人：李剑明 汤龙 E-mail：extenics@vip.163.com 联系电话：020-39322973，传真：020-39322019 会议网址：http://extenics.gdut.edu.cn/ 第 2 期 赵燕伟，等：基于可拓距的改进 k-means 聚类算法 ·351·