基于Hadoop的多核果蝇—Kmeans聚类算法

李小川 刘媛华

摘 要：针对Kmeans算法对海量数据聚类效率过低的不足，基于Hadoop的分布式架构思想，提出一种多核果蝇-Kmeans聚类算法（MKFOA-Kmeans）。以每次迭代后果蝇位置为聚类中心进行一次Kmeans聚类算法，综合了果蝇优化算法强全局搜索能力以及Kmeans算法强局部搜索能力的优点。MapReduce框架简化了算法执行过程，避免了由于存储空间不足而造成的算法失效。在由普通硬件搭建的Hadoop平台下进行仿真实验，表明MKFOA-Kmeans算法对大数据的聚类准确率高，并且随着数据量的增加，聚类效率优势也愈加明显。

关键词：大型数据聚类；Hadoop；果蝇算法；多核；Kmeans算法

DOI：10.11907/rjdk.172611

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）004-0051-03

Abstract：In order to overcome the disadvantage of low efficiency of massive data clustering of the Kmeans algorithm， a multi-kernel FOA-Kmeans clustering algorithm based on Hadoop is proposed. Using the positions of artificial flys as the clustering center， the new algorithm combines the strong global searching ability of the fly optimization algorithm and the strong local searching ability of the Kmeans algorithm. The MapReduce programming framework simplifies the execution of the algorithm and avoids the failure of the algorithm due to insufficient storage space of computer. Simulations on Hadoop platform constructed by common computers show that MKFOA-Kmeans algorithm has high accuracy for massive data clustering， and the clustering efficiency becomes more obvious with the increase of data.

Key Words：massive data clustering； Hadoop； fly optimization algorithm； multiple kernels； Kmeans Algorithm

0 引言

随着移动互联网等信息科技的快速发展，数据量级呈爆炸式增长，如何挖掘并利用有效数据成为各界关注的热点。聚类是数据挖掘中一个重要的方向，通过无监督学习确定合适的聚类中心，使其类内间距尽量小而类间间距尽量大。Kmeans算法因原理简单、局部搜索能力强等优点而成为经典的聚类算法，但其全局搜索能力较差，容易陷入局部最优值，尤其在对大型数据聚类时效率过低，算法滞慢劣势明显。很多学者对Kmeans算法进行了改进，文献[2]在粒子群算法中引入小概率变异事件，以有效克服Kmeans算法后期收敛速度慢的缺陷。文献[3]将蚁群算法的搜索方向性与Kmeans算法结合，成功应用在系统协同分类中，但搜索速度较慢。文献[4]提出一种基于人工蜂群的Kmeans算法，提高了全局搜索能力，但在处理大型数据时效率较低。近年来，针对海量数据的Kmeans算法改进研究越来越多，文献[5]提出了基于Hadoop平台的Canopy和Kmeans混合算法，在处理大型新闻数据时取得了较好的效果。文献[6]提出一种基于改进蜂群的Kmeans算法，在Hadoop平台下运行具有良好的可扩展性。

果蝇算法是一种基于生物学仿生的新型智能优化算法，具有参数少、收敛快、全局搜索能力强等优点，目前已经成功应用在函数优化、纺丝性能预测[7]、作业车间调度[8]、变压器故障诊断[9]等领域。本文采用自适应步长改进果蝇算法与Kmeans算法结合，根据MapReduce编程模型设计适合在Hadoop平台运行的算法流程，综合了果蝇算法的强全局搜索能力，Kmeans算法的强局部搜索能力以及Hadoop分布式框架的并行搜索效率，为海量数据的聚类方法提供了一种新思路。

1 相关方法

1.1 Kmeans聚类算法

1.2 果蝇优化算法

1.3 Hadoop平台

Hadoop平台是由多个普通硬件构成的分布式运行环境，其目标是建立一个并行处理大數据的可扩展软件框架[13]，运行环境主要包括HDFS和MapReduce组件。HDFS是Google分布式文件系统，具有低成本、高容量、高稳定性等特点；MapReduce是一个编程模型，以计算机集群为平台，编写处理大数据的并行化程序。Map Reduce执行过程分为Map和Reduce两个阶段，Map对输入的键值对（key-value）进行分割并处理后输出结果，Reduce以Map的输出作为输入进行程序处理后输出最终结果，MapReduce的执行模型如图1所示：

2 基于Hadoop的MKFOA-Kmeans算法

2.1 MKFOA-Kmeans算法与算法编码

果蝇优化算法中，当果蝇群体完成靠嗅觉觅食的阶段后，所有果蝇飞向味道浓度最大的果蝇，将味道浓度最大的果蝇抽象为一个中心点，则该过程可以理解为果蝇群体向中心聚集。

根据上述观点，对果蝇算法进行改进，选取味道浓度总和最大的k只果蝇作为聚类中心，其它果蝇以距离判定准则划分到相应的类中，提出基于多核果蝇-Kmeans算法。设样本数据为S={sDi|i=1，2，…n}，从中随机选取k个数据作为初始果蝇种群，编码方式如下：

2.2 适应度函数

采用Kmeans算法聚类时，类内数据个数多且类内间距小的聚类结果较优，由此构造如下适应度函数：

式（8）～（9）中，CNi为第i个类内的数据个数，CDi为第i个类内数据与聚类中心之间的距离和，V为聚类结果评价量。

2.3 基于Hadoop的MKFOA-Kmeans算法步骤

果蝇-Kmeans算法在对大型数据进行聚类时仍存在计算内存不足、收敛速度慢等问题，为解决以上问题，根据MapReduce编程模型对算法进行并行化处理，计算步骤如下：

Step1初始化各参数，输入待聚类数据样本，设置聚类数k，最大迭代次数G，果蝇基本步长ld，当前迭代t=1。

Step2 随机选择样本中的k个数据作为初始果蝇群体。

Step3 启动MapTask1，以样本数据索引号以及聚类中心（果蝇群体坐标）索引号作为key输入，样本数据距各聚类中心距离作为value输出；启动ReduceTask1，以MapTask1的输出作为输入，根据距离判断原则进行聚类，输出聚类结果。

Step4 启动MapTask2，以聚类中心索引号作为key输入，根据公式（8）计算每个类的适应值作为value输出；ReduceTask2以MapTask2的输出作为输入，输出最佳果蝇个体，记录最佳果蝇个体和聚类结果评价量V。

Step5 对除最佳果蝇个体外的其它果蝇进行迭代寻优，启动MapTask3，以聚类中心索引号作为key输入，由公式（2）计算移动步长L并作为value输出；启动ReduceTask3，以MapTask3的输出作为输入，由公式（2）更新果蝇的位置。

Step6 令t=t+1，转Step3，若V（t）>V（t-1），则执行Step5，否则果蝇群体回滚到t-1代的果蝇群体后执行Step5。

Step7 若t>G，则算法结束，输出聚类结果，否则转Step3继续迭代。

3 仿真实验结果及分析

3.1 仿真实验环境

本文算法运行环境为四台单核处理器，4GB内存，300GB硬盘，CentOS7.0操作系统的PC机搭建的Hadoop计算机集群，Hadoop版本为2.6.0，JDK版本为1.7.0。其中一台作为NameNode，另外3台作为DataNode。

3.2 仿真实验1

为验证本文所提MKFOA-Kmeans算法及其在Hadoop平台上进行聚类的可行性和准确性，首先选取5个不同大小和维数的UCI标准数据集（如表1所示）进行实验，每种算法独立运行20次。

由表2可见，在对4个不同的数据集进行聚类时，MKFOA-Kmeans和基于Hadoop平台的MKFOA-Kmeans的聚类准确性差别不大，但均明显高于Kmeans算法的聚类准确性，说明本文改进的Kmeans算法在数据聚类方面具有较好的可行性。

3.3 仿真实验2

通过实验1已经验证了MKFOA-Kmeans和Hadoop-MKFOA-Kmeans的聚类可行性与准确性，但是测试集数据量均相对较小，为了更好地验证Hadoop-MKFOA-Kmeans在对海量数据进行聚类的优势，本文随机生成6个类数和维数相同但数据量不同的数据集（如表3所示）进行实验，并与文献[6]所提的ACO-Kmeans算法聚类结果进行对比，每种算法独立运行20次。

由表4可知，对于DataBase1与DataBase2而言，基于Hadoop平台的并行算法运行时间要大于Kmeans和MCFOA-Kmeans，这是因为对于较小数据集的聚类，Hadoop分布式计算机集群不断读写花费的时间要大于算法实际运行时间。随着数据量的不断增大，基于Hadoop平台并行计算的效率优势也愈发明显。对于DataBase5与DataBase6，由于计算机内存溢出导致Kmeans和MCFOA-Kmeans算法失效，基于Hadoop平台的两种算法均可执行聚类过程，但本文提到的基于Hadoop的MCFOA-Kmeans算法平均运行时间要略少于文献[6]所提到的算法。总体而言，本文所提的基于Hadoop的MCFOA-Kmeans算法在对海量数据进行聚类时表现出了较优的性能。

4 结语

本文首次将果蝇算法应用在数据聚类领域，重新设计了拥有多个互相独立的最优果蝇多核果蝇优化算法，并将其与Kmeans算法结合，提出了基于Hadoop平台的多核果蝇-Kmeans算法，解决了Kmeans算法对海量数据聚类效率低甚至失效的不足。在Hadoop搭建的计算机集群上对UCI库中的数据集和随机生成的不同规模数据集进行仿真实验，表明本文所提算法在处理海量数据时具有较高的效率与准确性，为海量数据有效聚类提供了一种思路。

参考文献：

[1] 周丽娟，王慧，王文伯，等.面向海量数据的并行KMeans算法[J].华中科技大学学报：自然科学版，2012，40（S1）：150-152.

[2] 陶新民，徐晶，杨立标，等.一种改进的粒子群和K均值混合聚类算法[J].电子与信息学报，2010，32（1）：92-97.

[3] 莫赞，罗世雄，杨清平，等.基于K-means算法的改进蚁群聚类算法及其应用[J].系统科学学报，2012，20（3）：91-95.

[4] 喻金平，郑杰，梅宏标.基于改进人工蜂群算法的K均值聚类算法[J].计算机应用，2014，34（4）：1065-1069+1088.

[5] 赵庆.基于Hadoop平台下的Canopy-Kmeans高效算法[J].电子科技，2014，27（2）：29-31.

[6] 虞倩倩，戴月明，李晶晶.基于MapReduce的ACO-Kmeans并行聚类算法[J].计算机工程与应用，2013，49（16）：117-120+136.

[7] 郭凡，丁永生，郝矿荣，等.基于果蝇算法优化支持向量回归机的纺丝性能预测[J].系统仿真学报，2014，26（10）：2360-2364.

[8] 潘玉霞，谢光，桑红燕，等.双目标流水线调度的动态双子群离散果蝇算法[J].计算机工程与应用，2017，53（12）：140-146.

[9] 李宗岳，陈志军，李名远.基于改进FOA-LSSVM的变压器故障诊断[J].水电能源科学，2016，34（4）：194-197.

[10] 沈泓，刘顺.基于K-means聚类算法的数据分析模型应用研究[J].软件导刊，2017，16（3）：103-107.

[11] PAN W T.Using modified fruit fly optimisation algo-rithm to perform the function test and case studies[J].Connection Science，2013，25（2/3）：151-160.

[12] YUAN X F，DAI X，ZHAO J Y，et al.On a novel multi-swarm fruit fly optimization algorithm and its application[J].Applied Mathematics and Computation，2014，233（5）：260-271.

[13] 王彥明，奉国和，薛云.近年来Hadoop国外研究综述[J].计算机系统应用，2013，22（6）：1-5+28.

（责任编辑：刘亭亭）