第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 的分布式改进 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=<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·