聚类是数据分析的重要手段，将数据集分为若干类，使得簇内紧密且相似性大，簇与簇之间有明显区别，使得相似性最小，在数据挖掘、图像处理等领域被广泛应用^[1-4]。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 Mohammad Abualigah等^[11]将k-means算法采用和声搜索方法进行优化并应用于文本聚类中，提高了聚类精度；Li Yanyan等^[12]提出一种基于粒子群优化的k-means算法，并将其应用在岩体不连续数据分类中；Khanmohammadi等^[13]为克服对初始聚类中心的敏感问题，提出了一种混合k-谐波均值和重叠k均值算法的混合方法来克服缺点。以上改进算法都起到了较好的聚类效果，但在初始聚类中心选取问题上仍存在首个初始聚类中心点落于稀疏边界的缺陷。

基于此，本文提出一种基于可拓距的改进k-means聚类算法，将可拓学思想与k-means算法有效的结合，通过引入可拓侧距和缩放因子，对首个初始聚类中心点进行优化，选出一组最优初始聚类中心点，并通过仿真对比检验本文改进算法的可行性。通过实验验证，该方法具有更好的聚类效果。

1 基本知识 1.1 可拓距相关知识

可拓学是以蔡文教授为首的我国学者们创立的新学科，近年来，可拓学在计算机，人工智能、检测、控制等领域进行的应用取得了良好的成绩^[14]。其中，可拓距在实例检索领域应用较为广泛，通过可拓距构造关联函数，依据样本间关联度识别案例类别^[15-19]，显著提高了案例检索效率与正确率。

在经典数学中，当点在区间内时，默认点与区间的距离为零，即“类内即为同”，无法将事物内部的“质变”、“量变”表达出来。因此，为了描述类内事物(区间内的点)的区别，在可拓学中规定：实轴上任意一点x与区间X₀=<a, b>之距为^[14]

$\rho \left( {x,{X_0}} \right) = |x - \dfrac{{a + b}}{2}| - \dfrac{{b - a}}{2} = \left\{ \begin{array}{l} a - x,\;\;\;\;x \leqslant \dfrac{{a + b}}{2}\\ x - b,\;\;\;\;x \geqslant \dfrac{{a + b}}{2} \end{array} \right.$

(1)

当实例点在区间中点时，该实例最符合要求； $\left\langle a,b \right\rangle$ 可以是开区间、闭区间、半开区间。

但在实际工作中，却不全如此，例如，误差要求越小越好；成本要求越低越好；性价比越高越好；洗衣机的洗净率越大越好等，一般而言，实例点并不是越在区间中点越好，因此在可拓距的基础上，引入可拓侧距的概念^[14]：

给定区间X₀= $\left\langle a,b \right\rangle $ ， ${x_0} \in (a,\dfrac{{a + b}}{2} \left. \right\rangle$ ，称

$\rho {_l}(x,{x_0},{X_0}) = \left\{ {\begin{array}{*{20}{l}} {a - x,}\\ {\dfrac{{b - {x_0}}}{{a - {x_0}}}(x - a),}\\ {x - b,} \end{array}\begin{array}{*{20}{c}} \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{x \leqslant a}\\ {x \in \left\langle a,{x_0} \right\rangle }\\ \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{x \geqslant {x_0}} \end{array}} \right.$

(2)

为x与区间X₀关于x₀的左侧距。

给定区间X₀= $ \left\langle a ,\; b\right\rangle$ ， ${x_0} \in < \dfrac{{a + b}}{2},b)$ ，称

${\rho _r}(x,{x_0},{X_0}) = \left\{ {\begin{array}{*{20}{l}} {a - x,}\\ {\dfrac{{a - {x_0}}}{{b - {x_0}}}(b - x),}\\ {x - b,} \end{array}\begin{array}{*{20}{c}} \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{x \leqslant {x_0}}\\ {x \in \left\langle {x_0},b \right\rangle }\\ \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{x \geqslant b} \end{array}} \right.$

(3)

为x与区间X₀关于x₀的右侧距。

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聚类算法 2.1 基本思想

为便于表述，首先定义距离区间、距离可拓侧距、距离平均可拓侧距3个概念。对于n个样本的集合 $X = \{ {x_1},{x_2}, \cdots ,{x_n}\} $ ，其中x_i为m维向量(i = $ 1,2, \cdots ,n)$ ，有如下定义：

定义1　样本集合X的距离区间Z为

$Z = \left[ {A,B} \right] = \left[ {\min (D),\max (D)} \right]$

(4)

其中， $D = \left\{ {d\left| {d = \sqrt {\displaystyle\sum\limits_{p = 1}^m {{{\left( {x_i^p - x_j^p} \right)}^2}} } } \right.} \right\}$ 为两两样本间距离集合。

定义2　根据式(2)和式(3)定义两样本x_i和x_j (i $ \ne $ j)的距离d对区间Z的左、右侧距分别为

$ \begin{array}{l} {\text{左侧距}}:\rho _l^{(i,j)} = {\rho _l}(d,A,Z) = \left\{ {\begin{array}{*{20}{l}} {A - d{\rm{,}}}\\ {{A_z}{\rm{,}}}\\ {d - B,} \end{array}\begin{array}{*{20}{c}} {d < A}\\ {d = A}\\ {d > A} \end{array}} \right.\\ {\text{其中}}:{A_z}{\rm{ = }}{\rho _l}(A,A,Z){\rm{ = }}\left\{ {\begin{array}{*{20}{l}} {0,}\\ {A - B,}\\ {0 \otimes \left( {A - B} \right),} \end{array}\begin{array}{*{20}{c}} {A \notin Z}\\ {A \in Z}\\ {A \notin Z{\text{且}}A \in Z.} \end{array}} \right. \end{array} $

(5)

$ \begin{array}{l} {\text{右侧距}}:\rho _r^{(i,j)} = {\rho _r}(d,B,Z) = \left\{ {\begin{array}{*{20}{l}} {A - d{\rm{,}}}\\ {{B_z}{\rm{,}}}\\ {d - B,} \end{array}\begin{array}{*{20}{c}} {d < B}\\ {d = B}\\ {d > B.} \end{array}} \right.\\ {\text{其中}}:{B_z}{\rm{ = }}{\rho _r}(B,B,Z){\rm{ = }}\left\{ {\begin{array}{*{20}{l}} {0,}\\ {A - B,}\\ {0 \otimes \left( {A - B} \right),} \end{array}\begin{array}{*{20}{c}} {B \notin Z}\\ {B \in Z}\\ {B \notin Z{\text{且}}B \in Z.} \end{array}} \right. \end{array} $

(6)

定义3　根据定义2可计算所有两两样本的可拓侧距，则平均左、右侧距为

$\overline \rho = \dfrac{{\displaystyle\sum\limits_{j = i + 1}^n {\displaystyle\sum\limits_{i = 1}^{n - 1} {{\rho ^{(i,j)}}} } }}{{C_n^2}}$

(7)

其中， $C_n^2$ 表示从n个样本中任意取2个样本的组合数。

针对传统k-means算法初始中心点随机选取所引起聚类算法稳定性差问题，现有的改进算法虽取得了一定的效果，但仍无法避免初始聚类中心点落在边界非密集区域如图1所示，取样本间距离最小值所对应中心坐标作为首个初始聚类点，因下一初始聚类中心点的选取决定于首个初始中心的位置，当该点位于边界非密集区域，既降低了剩余初始聚类中心点质量，又会出现最终聚类集合中样本数为0或1的情况，使得聚类效果不均衡。

初始聚类中心的选取，不仅要求分布在较密集的范围内，还需要保证各初始聚类中心尽可能分散。针对上述问题，利用可拓距中数据分布情况对左右侧距平均值的影响，将经典平均距离映射为两个平均侧距值，如图2所示，其中平均左侧距值相对中心点靠左分布，平均右侧距值相对中心点靠右分布。特别指出，当数据在区间对称分布时，左右平均可拓侧距值重合于一点。将可拓平均左侧距 $\overline {{\rho _l}} $ 作为衡量密集度指标，可拓平均右侧距 $\overline {{\rho _r}} $ 作为衡量疏远度指标，首个大于可拓平均左侧距 $\overline {{\rho _l}} $ 所对应中心坐标作为第一个聚类中心，下一待选取初始聚类中心点需满足与各已确定初始聚类中心点间可拓距均大于可拓右侧平均距 $\overline {{\rho _r}} $ ，方可作为聚类中心点。

当选出初始聚类中心点数未达到所要求个数时，引入缩放因子 $\eta $ 如式(7)所示，对可拓平均右侧距进行缩放，选出满足个数的初始聚类中心点。

$ \eta = \left\{ {\begin{array}{*{20}{l}} {1 + \dfrac{{C_n^2 - k'}}{{C_n^2}}}&{k' \ne K}\\ 1\;,\;{k' = K} \end{array}} \right.$

(8)

其中， $k'$ 为每次遍历后，所获得的初始聚类中心个数；K为指定聚类中心数。

最后按传统聚类算法进行聚类。选取的一组最优初始聚类中心点克服了中心点出现于边界非密集区域缺陷，最大限度分布在密集区且各聚类中心点均匀分布。

2.2 改进k-means算法初始聚类中心选取流程

根据上述思想，得到改进k-means算法初始聚类中心选取的具体实施步骤如下：

1）按式(4)计算出两两样本间距离及等效密集距离区间[A,B]；

2）按式(5)和式(6)将距离映射为可拓左侧距 $\;{\rho _l}^{(i,j)}$ 及可拓右侧距 ${\rho _r}^{(i,j)}$ ，将 ${\rho _l}^{(i,j)}$ 按从小到大顺序依次排序，同时按式(7)计算样本间可拓平均左侧距 $\overline {{\rho _l}} $ 及可拓平均右侧距 $\overline {{\rho _r}} $ ；

3）遍历排序好的可拓距，将其中首个大于样本间可拓平均左侧距 $\overline {{\rho _l}} $ 的可拓距对应中心点坐标作为第一个初始聚类中心。

4）计算排好序可拓距中下一个值对应中心点坐标并依次计算出其与已确定的初始聚类中心的可拓距，将其与样本平均可拓右侧距 $\overline {{\rho _r}} $ 进行比较，若其均大于 $\overline {{\rho _r}} $ ，则该中心点坐标作为下一个初始聚类中心；否则重新执行步骤4）。

5）如果遍历一次后，初始聚类中心未达到K，则按式(8)计算出缩小因子 $\eta $ ，动态缩小样本平均可拓右侧距 $\overline {{\rho _r}} $ ，重新回到步骤3）。

6）若聚类中心数达到K时，则完成初始聚类中心的选取。

3 实验与分析

为了验证本文所提出算法的有效性，将本文算法与传统k-means算法及文献[22-23]所提出的改进聚类算法进行对比分析。

实验所用的测试数据集为UCI数据库中用于测试聚类的Iris数据集和Wine数据集，各数据的特征如表1所示。

基于本文提出算法对Iris、Wine数据进行初始中心点选取，特别指出，为了观察初始聚类中心点选取位置的大体远近及分散程度，本文为节省篇幅，只展示数据集两属性的二维图3和图4。

从图3和图4中可看出本文提出改进算法选取的初始聚类中心点，对低维与高维数据选取的初始聚类中心点，相较于其他改进算法分布更均匀，位于边界区域初始聚类中心点，其周围数据点也相对密集。

为了定量描述初始聚类中心点选取的质量，本文先将所选中心点聚类，将其与样本实际聚类情况和现有改进算法聚类情况进行对比，其聚类效果图5和图6。

其中，图5与图6中3种颜色代表3个聚类簇，可看出其他两种改进算法，由于初始中心点分布不均匀且有位于稀疏边界的中心点，从而导致对两组样本集聚类的结果存在一定误差，但本文提出的改进算法，虽然仍存在误差，但误差的大小有所缩小，尤其在对更高维的Wine数据集聚类时，优势更明显。

为了定量衡量算法的有效性，本文采用分类正确率指标，即被正确分到对应类别的样本个数与总样本个数比值以及聚类均衡性指标，即各类中样本个数与实际相应类中样本个数的方差，进行衡量。

对初始聚类中心点聚类后分类正确率统计如表2所示。对初始聚类中心点聚类后各簇类样本的个数统计如表3所示。由表3得出改进前后算法的均衡性指标如表4所示。从表2与表4中可看出当数据集样本维数不高时，本文算法与改进算法在聚类的均衡性上差异较小，但当维数增高时，现有改进算法聚类均衡性和分类准确性会降低，导致个别类中样本较多，相反也会出现有些类中样本过少的情况，使得之后聚类中心点更新时，较少样本数据的中心点在迭代更新时坐标变化不明显，从而导致最终聚类效果差。

4 结束语

本文提出一种基于可拓距的改进k-means聚类算法，将样本间平均距离映射为可拓距上对应两个平均侧距，作为初始聚类中心选取的约束范围，克服了首个选取的初始中心点可能位于较疏散边界的缺陷。实验表明在高维数据集的情况下，基于可拓距的改进k-means算法选取的初始聚类中心点聚类具有较高的正确率和均衡率，表明选取的初始聚类中心点较优，更适合大数据背景下的海量、高维数据聚类。

本文对k-means聚类算法初始聚类中心的选取展开了研究，由于时间和个人能力有限，还存在不足之处有待后续研究中深化、提高：1)本文算法对非数值型的数据集样本如何衡量相似度，并没有给出解决方法。2)文中提到的缩放因子并不能自适应的变化，对算法的性能有所影响。3)如何引入关联函数代替距离计算相似度，是值得深入研究的问题。4)在理论上和实用上的意义及价值。5)进一步深入研究本课题的建议。