一种基于MapReduce的改进人工蜂群算法

王凯杰

摘 要：针对现有序列聚类算法在对大规模数据进行聚类时，内存空间和计算时间开销较大的问题，提出了基于MapReduce的人工蜂群聚类算法。该算法通过引入MapReduce并行编程范式，快速计算聚类中心适应度，可实现对大规模数据的高效聚类。基于仿真数据对算法的聚类效果和聚类效率进行了验证。实验结果表明，与现有PK-Means算法和并行K-PSO算法相比，该算法具有更好的聚类效果和更高的聚类效率。

关键词：大数据；人工蜂群；聚类；并行编程范式

DOIDOI：10.11907/rjdk.171911

中图分类号：TP312

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

0 引言

数据挖掘技术常被用于发现数据中潜在的某种模式，从而为最优决策提供依据[1]。

聚类是重要的数据挖掘技术，主要用于将某个集合中的项分配到目标类别或簇。近年来，仿生算法如遗传算法（GA）、差分进化（DE）、蚁群优化（ACO）、微粒群优化（PSO）等被用于解决聚类问题。Maulik等[2]提出了被称为“GA-聚类”的基于遗传算法的聚类方法，该方法从特征空间搜索到适当的簇中心，优化利用相似性度量得到的簇。王勇臻等[3]针对K-means算法依赖于初始聚类中心和易陷入局部最优解的缺陷，提出一种改进的求解聚类问题的差分进化算法。姜参等[4]对蚁群聚类算法的收敛速度和易陷入局部最优问题进行了改进，提高了聚类速度和效果。Cura等[5]利用微粒群优化方法，通过模拟鸟类结队和鱼的群居行为特征解决聚类问题。然而，大规模数据集通常包含大量文件，应用上述序列聚类算法对大规模数据进行聚类时，往往在内存空间和计算时间等方面开销较大[6]。目前，MapReduce编程范式已成为一个数据并行编程模型，可将计算任务自动并行处理，具有较好的容错和负载均衡能力，受到众多研究者青睐。

针对大规模数据聚类问题，本文提出了基于MapReduce的人工蜂群聚类算法，能对大规模数据进行高效聚类。

1 人工蜂群聚类算法改进

1.1 传统的人工蜂群算法

人工蜂群算法是一种元启发式算法，涉及到的概念包括：①食物源：表示优化问题的一种可能方案；②适应度：适应度的值表示食物源的质量；③蜜蜂种类：雇佣蜂、观察蜂和侦察蜂。

人工蜂群算法步骤：①随机分布式初始化食物源位置；②所有雇佣蜂选择一个候选食物源位置，基于之前已选择食物源位置的临近位置，选择新的食物源。若新的候选食物源位置适应度更高，则更新雇佣蜂记忆中原有的食物源位置并返回蜂巢，与观察蜂共享新的食物源位置的适应度；③每个观察蜂根据从雇佣蜂得到的适应度值以一定概率选择新的食物源位置；④观察蜂前往被选择食物源位置，并根据所选食物源，选择其临近的新的食物源位置；⑤丢弃所有适应度未增加的食物源位置，并由侦察蜂随机确定新的位置。

上述过程重复执行，直到迭代次数达到最大循环次数。其中，步骤①、②和③在重复过程中，于步骤⑤之前循环执行。

1.2 改进算法流程

基于MapReduce的人工蜂群算法流程如图1所示。

主要步骤如下：

（1）随机分布式初始化食物源位置，将其作为雇佣蜂的初始位置。初始位置如式（1）所示：

其中，xi为以D维向量表示的食物源位置，为目标函数，决定着当前位置的优劣，表示食物源数量。

（2）更新雇佣蜂新的中心值。将初始位置作为雇佣蜂的当前位置，并基于当前位置对邻域进行搜索。在搜索过程中选择新的位置，通过式（2）计算得到：

（3）基于MapReduce计算适应度。基于MapReduce计算雇佣蜂从邻域搜索到的新的食物源適应度，如果该适应度高于原位置适应度，则用该位置更新原有位置。

（4）从雇佣蜂选择中心值并更新。雇佣蜂返回蜂巢，将新的食物源位置共享给观察蜂，观察蜂根据共享信息利用式（3）选择食物源位置：

式（3）中，fiti表示食物源的适应度，与食物源i的目标函数值有关。选择好食物源位置后，观察蜂前往该位置，利用公式（2）选择其邻域中心的食物源位置。

（5）基于MapReduce计算新位置的适应度，并根据适应度的大小决定是否更新当前位置。

（6）考察一段时间内的中心值适应度是否增加，如适应度未增加，则丢弃当前中心值，侦察蜂重新产生新的中心值，否则，执行步骤（7）。

（7）考察中心值是否满足条件，如满足则执行步骤（8），否则执行步骤（2）。

（8）利用最优中心值对数据进行聚类。

在上述步骤中，大规模数据的适应度计算会耗费大量时间。因此，本文采用MapReduce计算适应度值。

1.3 基于MapReduce的适应度计算

具体步骤如下：①映射函数从簇的中心开始，将数据记录到Hadoop分布式文件系统中；②映射函数从每个蜜蜂提取中心值，计算数据记录与中心值之间的距离，并返回最小距离及中心的编号。映射函数使用蜜蜂的ID和中心的ID建立一个新的合成键，并根据最小距离计算新的值；③映射函数将新的键和值调用给规约函数，规约函数利用同一个键的多个值计算得到平均距离；④规约函数调用键和平均距离，计算得到每个蜜蜂的适应度值。

2 实验

对改进算法的聚类效果和聚类效率进行实验，对算法性能进行评估和验证。

2.1 实验设置

本文算法和对比算法均以Perl语言实现，并在包含10个节点的Hadoop集群中运行，每个节点的配置为：1核2.26GHz CPU，2G内存，120G硬盘空间，Ubuntu 14.04操作系统，Apache Hadoop 2.6.2。endprint

算法使用的数据集为仿真数据，该数据为UCI机器学习数据集中的4个基准数据集，如表1所示。为了获得大规模的仿真数据，本文通过多次复制，将每个基准数据集扩充到约1 000万条记录。

2.2 实验结果

2.2.1 聚类效果测试

在衡量聚类效果时，本文采用F值度量（F-Measure）方法来评估聚类的准确度。F值度量（F-Measure）方法将每个簇作为一个查询，将每个类别作为查询的预期结果。算法得到的簇和已标记的基准数据类别之间的F度量值可用式（4）计算得到：

基于仿真数据，本文实现了基于MapReduce的人工蜂群聚类算法，与现有的PK-Means算法[7]和并行K-PSO算法[8]的聚类效果比较结果见表2。其中，初始簇中心是通过计算随机抽取0.1%的数据记录平均值得到的。

从表2可以看出，本文算法的F度量值明显高于PK-Means算法和并行K-PSO算法的F度量值，即本文算法的聚类效果更优。

2.2.2 聚类效率测试

本文除对算法的聚类效果进行测试外，还测试了大规模数据的聚类效率。在10个节点上对不同大小的数据集进行聚类，数据集的大小从2GB～10GB不等，测试结果如表3～表6所示。聚类效率通过式（6）计算得到。

从表3～表6可以看出，随着数据集的增大，本文算法的性能逐步提高，效率达到90%以上。实验结果表明，对大规模数据进行聚类时，本文算法可节省大量时间，显著降低成本，在合理的时间内处理大规模数据且处理结果较优。

3 结语

本文针对大规模数据聚类问题，提出了基于MapReduce的人工蜂群聚类算法，并利用仿真数据对算法的聚类效果和效率进行了验证。实验结果表明，与PK-Means算法和并行K-PSO算法相比，本文算法具有更好的分类性能。今后的进一步研究可在更大规模的数据集上开展实验。

参考文献：

[1] 穆肇南，张健.数据挖掘技术在经济预测中的应用[J].计算机仿真，2012，29（6）：347-350.

[2] WU X， ZHU X， WU G Q， et al. Data mining with big data[J]. IEEE transactions on knowledge and data engineering，2014，26（1）：97-107.

[3] 王勇臻，陈燕，张金松，等.一种改进的求解聚类问题的差分进化算法[J].计算机应用研究，2016，33（9）：2630-2633.

[4] 姜參，王大伟.一种改进蚁群聚类的入侵检测方法[J].计算机技术与发展，2013，23（12）：139-142.

[5] CURA T. A particle swarm optimization approach to clustering[J]. Expert Systems with Applications，2012，39（1）：1582-1588.

[6] 李晓峰.云平台中大数据并行聚类方法优化研究仿真[J].计算机仿真，2016，33（7）：327-330.

[7] ZHAO W， MA H， HE Q. Parallel K-means clustering based on MapReduce[C]. Proceedings of the IEEE International Conference on Cloud Computing，2009：674-679.

[8] WANG J， YUAN D， JIANG M. Parallel K-PSO based on MapReduce[C]. Proceedings of the 14th IEEE International Conference on Communication Technology，2012：1203-1208.endprint