基于探索向量的Ball K-Means聚类算法

钟世立 华帅 陈彩凤 王陈陈

(东莞理工学院 计算机科学与技术学院，广东东莞 523808)

数据聚类是数据挖掘中的一个重要任务，其目的是根据数据对象之间的相似性确定一组有限的类别来描述数据集。目前，聚类已被广泛应用于客户细分、动态趋势检测、生物数据分析和社会网络分析等领域[1]。对于各种数据处理任务，有许多聚类方法,其中K-Means是最经典的方法之一。在早期的研究中，经典K-Means算法是人们关注的焦点，主要原因是该算法的数学思想简单、扩展性强，并且它对于问题的任何变量都具有线性渐近执行时间。然而，K-Means聚类算法也存在以下缺陷：1)要求预先指定数据集簇数K；2)对初始质心的选择敏感和缺乏全局搜索能力，大概率导致算法收敛到局部最优解；3)随着样本维度和样本数量增加导致计算成本剧增。针以上问题，许多改进算法被提出[2-3,7-13]。

为了克服K-Means算法对初始质心过于敏感的缺点，许多有效的算法被提出[2-3]。Arthur等[2]通过用一种简单的随机播种技术对K-Means进行了增广，降低了K-Means在初始种子选择中的随机性。Lasheng等[3]提出了基于最大最小准则和FLANN的初始聚类中心选择算法，提高了算法的稳定性和准确性。上述的算法克服了K-Means聚类对初始质心敏感的缺陷，但是迭代过程仍采用K-Means聚类的框架，缺乏全局搜索能力。受遗传算法和粒子群优化算法等启发式算法[4-6]全局搜索能力的影响，许多研究学者结合启发式算法对K-Means算法进行了改进。Ahmadyfard等[7]结合粒子群优化算法(PSO)和K-Means，提出了一种全局搜索能力更强的混合算法，称为“PSO-KM”。Du等[8]为了进一步降低陷入局部最优解的可能性，提出了一种改进的粒子对优化算法(PPO)，并将其与K-Means相结合，称为“PK-Means”。早期基于遗传机制的聚类算法要么使用昂贵的交叉算子，要么使用昂贵的适应度函数，或两者兼而有之。为了避免这些昂贵的操作，Krishna等[9]将遗传算法与聚类使用的经典梯度下降算法K-Means进行杂交。上述改进算法在一定程度上降低了聚类的总体误差和计算成本。尽管这些方法是可行的，但是由于使用群体的思想，计算成本明显高于K-Means。因此，Lam等[10]将简单的探索向量与K-Means相结合，提出了一种称为“XK-Means”的聚类算法，该方法从速度、误差、稳定性及复杂度等方面都优于现有的基于进化和群体智能的聚类方法。近期，针对K-Means面对高维度和大样本数据时计算成本剧增的问题，Xia等[13]提出了一种新颖的加速精确K-Means聚类算法，称为“Ball K-Means”。尽管它可以降低K-Means的计算成本，但它和K-Means都存在对初始质心敏感和缺乏全局搜索能力的缺点。

因此考虑算法的全局搜索能力和计算成本两个因素，本文结合探索向量和Ball K-Means技术提出一种新的聚类方法，称为“基于探索向量的Ball K-Means聚类算法”，亦称为“Ball XK-Means”。Ball XK-Means的目的是提高算法的搜索能力，同时使算法的计算成本尽可能低，其原理是基于这样一个事实：虽然Ball K-Means可以有效地降低计算成本，但是在探索全局最优的途径上通常是无效的。因此，将一种防止聚类过程过早收敛的探索向量引入到Ball K-Means中，提出了一种更稳定、更准确和更高效地针对高维度和大样本数据的聚类算法。

1 相关工作

本节首先介绍与本文相关的聚类评价准则，然后介绍K-Means[14]和Ball K-Means[13]聚类技术。

1.1 评价准则

聚类的目标是将数据集分成若干簇，使得簇内的样本相似度尽可能大，而簇间的样本相似度尽可能小[15]。该理念有多种实现方式，每种方式对应一种评价指标，可用于检验算法的有效性。在本文中，采用如下评价指标对聚类算法进行评估：均方误差(MSE)[16]。它的定义如下：

(1)

式(1)中，N表示数据集样本总数，K表示数据集簇数，集合Ci表示第i个簇,|Ci|表示第i个簇的样本数量，ci为簇Ci的质心。

1.2 K-Means聚类

K-Means是最经典的聚类算法之一，由于其简单的数学思想、易扩展性和快速收敛性等优点，已被广泛用于解决聚类问题。但是，K-Means也存在缺陷，例如需自定义簇数K、对初始质心的敏感性、缺乏全局搜索能力和面对高维度据、大样本数据时算法的计算成本高等[15]。本质上，K-Means聚类是在D维欧几里得空间RD中将给定的个数据对象划分为K个簇的方法，使簇内样本尽可能相似，簇间样本尽可能不相似。K-Means代码如算法1。

算法 1:K-Means聚类

输入：数据集X=x1,…,xn⊂Rd,簇数K；

输出：簇质心C=c1,…,cK；

1. 随机选择K个样本作为初始质心C=c1,c2,…,cK；

2. 将每一个样本x依据最近距离分配给最近的簇Ci中，i∈1,…,K；

4. 重复步骤2、3直到C不再改变；

1.3 Ball K-Means聚类

考虑到K-Means算法在高维度和大样本数据下计算成本高的问题，Xia等[13]提出了一种新颖的K-Means聚类算法，称为“Ball K-Means”。该算法使用“球”的思想来描述每个簇，以减少样本点和簇质心间的计算次数。Ball K-Means聚类算法代码如算法2，该算法减少计算次数的核心思路有以下三点。

算法 2:Ball K-Means聚类

输入：数据集X=1,…,xn⊂RD,K表示簇的数量，初始簇质心C=c1,…,ck；

输出：簇质心C=c1,…,ck；

1. 初始化迭次数t=1，进行一步标准的K-Means迭代；

2. flagi=FLASE(i=1,…,K)；//决定簇质心和半径是否需要被更新；

3. while簇质心发生改变 do

4. fori=1,…,Kdo

5. if flagi=FALSE then

//其中δ(cit)表示为第i个簇质心第t-1代和第t代的差值，为了找出下一代的邻居关系；

6. 更新簇质心cit=mean(x|x∈Ci)，记录δ(cit)=cit-ci(t-1)；

7. 根据式(2)更新当前簇半径rit；//rit表示第i个簇第t代的半径；

8. end if

9. end for

10. ift=1 then

11. 计算任意两个质心的距离dist(cit,cjt)(i,j=1,…,K)；//初始化质心距离矩阵；

12. else

13. 若满足式(4)，则dist(cit,cjt)=dist(ci(t-1),cj(t-1))-δ(ci(t))-δ(cj(t))；

14. end if

15. fori=1，…，Kdo

16. 设置当前代簇Ci的邻居质心集合NCi(t)=φ，根据式(3)计算簇的邻居簇；

17. 根据稳定域、活动域和环域的关系，重新分配样本点进入簇Ci中；

18. end for

19. fori=1，…，Kdo

20. ifCi稳定then

21. flagi=TRUE；

22. else

23. flagi=FALSE；

24. end if

25. end for

26.t=t+1；

27. end while

1)精确地找到每一个簇的邻居簇，使得样本点和簇质心间的计算限制在样本点和它的邻居簇中而不是所有的簇。Ball K-Means中的簇质心和簇半径定义如下：

(2)

式(2)中，集合Ci表示为第i个簇，|Ci|表示第i个簇的样本数量，ci表示为第i个簇Ci的质心，x是属于簇Ci中的样本点，ri表示为第i个簇Ci的半径。其邻居簇关系定义如下：

(3)

式(3)中，ci和cj分别表示第i和j个簇的质心，此式表明簇Cj是簇Ci的邻居簇(邻居簇为非对称关系)。簇和邻居簇的关系如图1。

图1 簇C1的邻居簇关系 虚线表示连接两个簇质心的线段的平分线，菱形和实线分别代表簇质心和簇半径。根据邻居的定义可知，簇C1的邻居簇有：C2和C3。

2)将每一个簇划分为稳定域和活动域，且进一步将活动域切分为多个环域。经数学上的证明，处于稳定域中的样本点将不再改变，而处于活动域中的样本将依据距离最近原则重新分配进入某个邻居簇或原簇，达到减少计算成本的目的。具体关系如图2。

图2 簇C1的分区 虚线表示连接两个簇质心的线段的平分线。根据定义可知，第1个环域的样本点将重新划分进入簇C1和簇C3, 并且第2环域中的样本点将重新划分进入C1、C2和C3，而处于稳定域的样本将不会被重新划分。

3) 同时，由于当簇数很大时,寻找每个簇的邻居簇需要很高的计算成本。因此Ball K-Means通过记录下任意两个簇质心的距离，提前找到下一代簇间的关系从而达到减少计算成本的目的。设置Ci和Cj表示第i和j个簇，如果满足式(4)，意味着在当前迭代中不能是的邻居簇，因此可以忽略这两个簇质心间的距离计算。

dist(ci(t-1),cj(t-1))≥2ri(t)+δ(ci(t))+δ(cj(t))，

(4)

式(4)中，ci(t-1)表示第j个簇在第t-1代的质心，dist(ci(t-1),cj(t-1))表示为第i和j个簇在第t-1代的簇质心距离，δ(cit)表示为第i个簇质心第t-1代和第t代的差值。目的是为了找出不可能的邻居关系。

2 基于探索向量的Ball K-Means聚类算法

本节首先介绍探索向量在K-Means算法中的作用以及它相关参数，然后提出改进的聚类算法。

2.1 探索向量

受启发式算法的影响，Lam等[10]提出了一种称为“XK-Means”聚类算法，其基本思路是：保留K-Means聚类算法的框架，在算法分配样本前将探索向量作用到簇质心上，提升算法的全局搜索能力。为了更好地理解探索向量的作用，做了更直观的描述(如图3),其数学定义如下：

图3 探索向量(三角形为簇质心，其他同形状的样本表示同簇数据) (a)图是实验中由K-Means聚类产生的局部最优解，即算法此时已达到终止条件; (b)是在左图的基础上加上探索向量后的第一划分，由于探索向量打破了局部最优状态，此时算法继续迭代，最终收敛到更准确聚类结果。

(5)

vij=rand(aj,bj)*randSign(j),j=1,2,…,D,

(6)

式(6)中，vij表示第i个探索向量第j维的值，aj和bj非0且为正，被称为是第j维的上下惯性权重。rand(aj,bj)和randSign(j)的功能分别是在aj和bj和之间分配一个随机值和分配一个随机负号或正号，这两个随机因素是控制算法搜索行为的关键随机因素。其中aj被定义为与bj成比例，如下：

aj=βbj，

(7)

式 (7)中，β∈[0, 1) 为给定的因子。此处为了达到更好的效果，选取的参数值是β=0.5。同时，为了使得探索能够从更大范围的开始，并逐步转向越来越多有效的开发。因此，随着迭代的进行将bj定义如下:

(8)

2.2 基于探索向量的Ball K-Means聚类

在高维度和大样本数据的条件下，尽管Ball K-Means聚类算法提高了K-Means聚类计算效率，但是该算法缺乏全局搜索能力。因此，从全局搜索能力和计算成本两个因素考虑，结合探索向量和Ball K-Means聚类提出了一种改进的算法，称为基于探索向量的Ball K-Means聚类算法，亦称“Ball XK-Means”。

Ball XK-Means聚类算法是基于事实：在整个聚类过程中，将探索向量引入到Ball K-Means聚类算法中，从而提高算法的搜索能力。首先，算法早期，Ball XK-Means聚类算法不会由于随机的初始质心差而收敛到局部最优，而是使算法在更大的解空间内探索更多的潜在解。其次，随着算法的迭代，不会因为算法框架本身缺乏全局搜索能力而迅速陷入局部最优解，而是使Ball XK-Means聚类算法去探索当前解附近更好的解，从而达到增强算法搜索能力的目的。正是因为本算法引入了探索向量，因此与Ball K-Means聚类和K-Means聚类算法相比，它具有更强的搜索能力。同时又因为本算法使用“球”的思想改进了算法，减小了样本点与质心的计算，在一定程度上克服了K- Means和XK-Means 聚类算在簇数多、数据维度高和数据量大的情况下，计算成本急剧上升的缺点。

Ball XK-Means聚类算法的基本思路如下：1)首先初始化簇数和惯性权重等参数，并且进行一次K-Means聚类算法迭代；2)更新质心并记录簇的半径；3)在更新后的质心上增加探索向量，并根据(7)、式(8)更新权重参数，评价MSE值；4)计算两个簇质心间的距离和计算每个簇的邻居簇，并依据稳定域、活动域和环域的关系重新分配样本。依次重复上述2)、3)、4)三个步骤，直到算法达到终止条件。该算法流程如图4。

图4 基于探索向量的Ball K-Means聚类算法的流程图

3 数值实验与结果讨论

本节首先介绍实验采用的数据集以及相关的参数设置，然后从算法的精确度和稳定性、计算成本和收敛速度四个方面对实验结果进行分析与讨论。

3.1 数据集和参数设置

如表1所示，第5、6个数据集Sporulation、Yeast Cell Cycle是基因表达数据集[17]，另外6个来自于UCI数据集。由于Yeast Cell Cycle数据集的部分样本存在缺失分量，为了纠正这些缺失数据，采用了文献[8]中的策略：首先，删除数据集中缺失分量超过的样本。然后，采用k=15的KNN算法[18]估计其他缺失的分量值，其中k是相邻样本的个数。特别指出，这里的k值和本文提到的簇数K不是同一个。

表1 数据集信息

要达到数值实验条件统一的原则。首先，由于Ball XK-Means聚类算法和XK-Means聚类算法都引入了探索向量，因此统一设置给定因子α=0.95,β=0.5。其次，将实验所有聚类算法的停止准则替换为式(8)[10]，且因为每次迭代都使用探索向量来探索质心，所以在一次迭代之后评价结果可能有时不会提升。为确保算法有效性，让该停止准则连续满足10次即为终止条件。其中式(8)停止准则被定义如下：

(8)

其中，MSEt和MSEt-1分别代表当前代和上一代的MSE值。

在实验中，在具有4核心Intel Core i7与16 GB 1600 MHz DDR3的笔记本电脑上，采用C++编程语言实现了K-Means、XK-Means、Ball K-Means及Ball XK-Means聚类算法。

3.2 实验结果分析和讨论

实验中，8个数据集的簇数K设置如表1，且4种算法都采用随机初始化质心的方式。记录下评估这4种算法在8个真实数据集上运行20次的实验指标数值，分别是：1)MSE平均值(值越小聚类效果越好)；2)MSE值的标准差(值越小算法越稳定)；3)平均迭代次数(取整后)和平均每代的计算次数(样本点和质心间的计算次数)；4)CPU平均执行时间。以上列举的实验指标分别反映了算法的精确度、稳定性、计算成本以及收敛速度。实验数值列在表2中，并绘制4个算法在8个数据集上运行20次的MSE、平均每代的计算次数以及随CPU执行时间收敛结果(随机选取20次中的1次)的图像，分别为图5和图6、图7、以及图8和图9。为了更好地体现本算法在高维度和大样本数据下的有效性，将图5和图8绘制为低维度或小样本数据集的实验结果，将图6和图9绘制为高维度或大样本数据集的实验结果。

图7 4种算法在8个数据集上平均每代的计算次数

比较表2中MSE平均值，Ball XK-Means和XK-Means获得的MSE平均值均小于K-Means和Ball K-Means。从图5、图6可以更直观地看出在20次的运行中Ball XK-Means和XK-Means多次优于K-Means和Ball K-Means的MSE值，尤其随着样本维度和数量增加，这种差距更加明显。尽管与XK-Means相比，Ball XK-Means并不总是能够获得最小的MSE值，但Ball XK-Means始终可以收敛到与XK-Means具有近似相同的聚类结果。因此，以上分析结果意味着提出的Ball XK-Means算法比K-Means和Ball K-Means算法具有更强的搜索能力，能收敛到更精确的解。主要原因是将探索向量引入到Ball K-Means聚类算法中，克服了它容易陷入局部最优的缺点，进而提高了算法的搜索能力。

表2 MSE平均值和MSE标准差

图5 4种算法分别在前4个数据集(低维度或小样本)上运行20次的MSE值

图6 4种算法分别在后4种数据集(高维度或大样本)上运行20次的MSE值

同时，由于实验中的4种聚类算法都具有随机性，尤其是基于探索向量的聚类算法，因此稳定性也是影响算法质量的一个相对重要的因素。比较表2中的MSE标准差，Ball XK-Means在Svmguide1、Codrna、Yeast Cell Cycle、Epileptic数据集上获得了最小的值，在其它的数据集中也总是能够获得与其他算法相差不大的MSE标准差。从图5和图6也可以看出，与K-Means和Ball K-Means相比，Ball XK-Means和XK-Means在20次的MSE上多次获得最小的MSE值和具有更小的波动，并且随着样本维度和数量增加，Ball XK-Means算法的优势更加明显。因此，综合表2、图5及图6中的实验结果可以得出，Ball XK-Means相比于K-Means和Ball K-Means具有更好的稳定性。

计算成本一直是影响算法效率的重要因素，比较表2中平均每代计算次数可以看出，Ball XK-Means和Ball K-Means比K-Means和XK-Means的平均每代计算次数少。从图7也可以直观的看出，与K-Means和XK-Means相比，在计算成本上，Ball XK-Means和Ball K-Means取得了更好的结果。更重要的是，Ball XK-Means和Ball K-Means与K-Means和XK-Means相比，在平均每代计算次数上的差距，将会随着样本维度和数量的增加而增加。这反映了面对高维度和大样本数据时Ball XK-Means和Ball K-Means的有效性,主要是因为在算法引入了“球”的思想，有效地减少样本点与簇质心间的计算次数。但是，由于Ball XK-Means在Ball K-Means的基础上增加了防止算法过早收敛的探索向量，从而在平均意义上增加了算法的计算成本。因此，Ball XK-Means的计算成本将高于Ball K-Means。

同时，从表2中的CPU平均执行时间参数可以得出，Ball XK-Means和Ball K-Means比K-Means和XK-Means具有更少的CPU执行时间。从图8和图9中也可以直观地看出，Ball XK-Means和Ball K-Means在CPU执行时间(即收敛速度)上要优于K-Means和XK-Means。尤其是随着样本维度或样本数的增加，与K-Means和XK-Means相比，Ball XK-Means和Ball K-Means在CPU执行时间上有更明显的提升，充分体现了Ball XK-Means和Ball K-Means面对高维和大样本数据时的高效性，主要是因为Ball XK-Means和Ball K-Means算法引入了“球”的思想，减少了计算量，提升了CPU执行速度。同理，也是因为引入了探索向量来增强全局搜索能力，使得在Ball XK-Means的基础上增加了计算成本，因此就CPU执行速度而言，Ball XK-Means不如Ball K-Means聚类算法。

图8 4种算法在前4个数据集(低维度或小样本)上随时间的收敛效果

图9 4种算法在后4个数据集(高维度或大样本)上随时间的收敛效果

4 结语

笔者主要关注K-Means和Ball K-Means聚类算法存在的问题，K-Means和Ball K-Means在划分数据集时具有很好的收敛速度，但是它们往往只收敛到局部最优解。虽然XK-Means算法增强了K-Means算法的搜索能力，获得了更精确的聚类结果，但是随着样本维度和样本数量的增加，XK-Means的计算成本也会急剧增加。因此，综合考虑算法搜索能力和计算成本这两个因素，结合探索向量和“球”的思想，针对高维度、大样本数据提出了一种更稳定、更精确及更高效的基于探索向量的Ball K-Means聚类算法，称为“Ball XK-Means”。对K-Means、Ball K-Means、XK-Means和Ball XK-Means算法进行了数值实验。主要从四个方面评价算法的性能：1)均方误差(MSE)越小表明算法越精确(搜索能力越强)；2)MSE标准差越小表明算法越算法越稳定；3)平均每代的计算次数越小表明算法的计算成本越低；4)CPU执行时间越小表明算法收敛速度越快。

实验结果表明：首先，与Ball K-Means和K-Means相比，Ball XK-Means能够获得更稳定、更精确的聚类结果，说明引入探索向量的有效性。其次，与K-Means和XK-Means相比，Ball XK-Means在平均每代计算次数和CPU执行时间有更小的值，表明了算法的高效性，这说明了引入“球”思想的有效性。更重要的是，随着样本维度和样本数量的增加，笔者提出的Ball XK-Means在聚类的稳定性、精确性和执行效率上有更明显的优势。