基于布谷鸟算法的K-medoids聚类挖掘与并行优化

谭成兵，刘 源，徐 健，3

（1.亳州职业技术学院 智能工程系，安徽 亳州 236813；2.桂林医学院 信息中心，广西 桂林 541001；3.桂林电子科技大学 机电工程学院，广西 桂林 541004）

0 引言

聚类作为数据分析的常用方法，在多个行业得到了深度应用，特别是基于大数据分析时，通过对大规模数据的聚类，可以完成多种看似无关联的数据的归类，从而降低了大规模数据管理和分析的难度。基于聚类分析的应用场景非常多，在电商领域，可根据用户消费数据进行分类来制定合适的营销方案[1]；在线服务行业中，可以根据用户使用习惯实现用户聚类[2]，为不同类别用户推荐合适服务等。在基于互联网的数据分析平台中，随处可见聚类技术的影子。

当前，关于聚类挖掘的研究成果较多，主要集中在聚类算法的研究方面。余胜辉和李玲娟采用层次聚类算法来实现聚类[3]，为了提高大规模数据的聚类性能，他们应用spark平台完成并行聚类研究，节省了聚类时间；陶莹等采用K均值聚类算法实现大规模样本数据聚类[4]，并研究了不同K值情况下的聚类性能；雷涛等采用模糊聚类算法应用于图像类样本的聚类[5]，实现了从文本到图像聚类的转变，开拓了聚类算法的新应用对象。这些算法实现了不同规模和类型的数据聚类，取得了较好的聚类准确率，本文采用K-medoids聚类，通过布谷鸟算法来进行优化，提高聚类准确率；在聚类时间方面采用了多节点的并行聚类方法，提高聚类效率[6]。

1 布谷鸟算法

设鸟群共有N只布谷鸟，鸟巢被宿主发现概率为Pa，鸟群的初始位置分布为X0，计算初始适应度，选择较好的鸟巢和对应最优解集合分别为。

设布谷鸟移动的方式为[7]：

其中，α为移动步，Levy(λ)服从莱维分布，具体表达式为[8]：

其中，u和v均表示分布参数，λ=1.5，

其中，Γ为Gamma函数。通过式（1）位置更新，然后计算适应度，第t次得到的适应度最优解集合为，其中，1＜t≤T。

设r∈[0 ,1 ]对比r与Pa，若r＞Pa，则继续进行位置更新，鸟巢位置更新方式为[9]：

继续迭代直到达到最大迭代次数或者适应度满足阈值时[10]，输出Xbest和fbest。一般情况下取Pa=0.25，α=1。

2 布谷鸟优化的K-medoids聚类

2.1 K-medoids聚类

2.2 布谷鸟优化的K-mediods聚类流程

根据聚类簇构建布谷鸟算法模型，采用K-mediods的适应度函数获得最优鸟巢位置，通过莱维分布更新方法，获取最优位置及最优适应度值，其主要流程如图1所示。分布式环境下聚类算法的Reduce具体实现步骤如表1所示。

图1 布谷鸟优化的K-mediods聚类流程图

表1 Reduce具体实现步骤

3 实例仿真

为了验证布谷鸟算法在K-mediods的聚类性能，对其进行实例仿真。聚类对象分别选择了自有数据集和公开UCI的5种类别数据集，UCI数据集参数如表2所示。仿真主要测试布谷鸟算法对K-mediods聚类的性能影响，以及多个运算节点同时参与聚类的并行优化性能。

表2 UCI数据集参数

3.1 聚类性能仿真

3.1.1 聚类可视化

选择某电商公司的2000个客户，根据其消费习惯对2000个客户从3个维度进行分类，类别K=5，分别将客户数据属性进行数字化和归一化。

布谷鸟优化的K-mediods聚类将2000用户分成了5个类别，通过matlab仿真输出结果，其对5个类别分类的准确率及标准差如表3所示。

表3 用户聚类准确率

从表3可得，2000个分属于5个类别的用户的聚类准确率均达到92%以上，其中A和E等级的聚类准确率最高，可能是样本属性值差距大，较易分类，而C类别聚类准确率略低，这可能是由于其用户属性和B、D类别较近，不容易分类造成的。在标准差方面，不同类别的聚类性能差异较小。

3.1.2 UCI数据集聚类准确率

为了进一步验证布谷鸟算法在K-mediods的聚类效果，对常用UCI数据集进行布谷鸟算法的K-mediods聚类，K=9，结果如表4所示。

表4 布谷鸟算法的聚类优化性能对比

通过对比发现，经过布谷鸟算法优化后的K-mediods聚类对5种UCI数据集的聚类准确率均有所提升，其中glass数据集提升最明显，提升了3.565%，seeds数据集优化性能不显著。在标准差方面，经过布谷鸟优化后的性能均有不同程度的提升。

3.2 并行优化性能

在并行优化聚类时，共构建了基于10个运算节点的分布式聚类节点，可以灵活选择多个节点进行表1中数据集的聚类，初始化随机设置K-mediods的聚类中心数目，分别对单机K-mediods、多节点K-mediods和布谷鸟优化K-mediods进行性能仿真。

设定3种算法的聚类停止条件为聚类准确率不低于75%，聚类节点数为10，其运算时间如图2所示。

图2 聚类时间（样本容量=32.64GB）

从图2中可以看出，3种算法的聚类时间随着聚类中心数的增加而增长，但通过对比发现，单机K-mediods算法聚类时间增长较快，多节点聚类时间增长较缓，而且单机运行时间相比多节点超出很多，证明并行优化在聚类时间方面性能提升显著。从图2中也可得出，采用布谷鸟算法优化后，节省了K-mediods算法对UCI数据集的聚类时间。

3.3 不同算法的聚类准确率对比

最后对常用聚类算法进行聚类性能比较，分别采用均值聚类算法、层次聚类算法、布谷鸟 K-means算法[14-15]和布谷鸟 K-mediods算法方法对表1中的glass样本进行仿真。参数Pa=0.25，α=1，聚类准确率阈值0.75，并行计算节点数10，仿真结果如图3所示。

图3 不同算法聚类准确率

从图3中可以看出，对于glass数据集，布谷鸟K-mediods聚类算法的准确率最高，布谷鸟K-means聚类算法次之，其他两种算法聚类准确率差别较小。从聚类时间来看，本文中的算法有绝对优势，聚类时间小于100 s，其他聚类时间均在120 s以上，这是因为采用了并行多节点参与聚类，所以节省了聚类时间。

4 结语

采用布谷鸟优化的K-mediods聚类，选择合适布谷鸟算法的宿主发现概率及适应度函数，分别对自有数据集和UCI公开数据集进行仿真，均获得了较好的聚类效果。采用多节点参与聚类的并行优化方法，能够快速提高大规模样本的聚类效率。