（南京师范大学电气与自动化工程学院 江苏南京 210023）
摘要：聚类作为典型的数据分析方法，尤其是对大规模数据进行聚类分析成为近年来的研究热点。针对现有序列聚类算法在大数据计算时存在开销大的问题，提出了基于MapReduce的人工蜂群聚类算法。通过引入MapReduce并行编程范式，快速计算聚类中心适应度，基于仿真和真实的磁盘驱动器制造两类数据，对算法的聚类效果进行了验证。实验结果表明，本文算法具有更好的聚类效果。
关键词：MapReduce；人工蜂群；聚类
1概述
当前，可采集数据规模不断增大，在短时间内已很难通过人工分析的方式从中得到有价值信息。数据挖掘技术作为目前十分流行的数据分析技术，常被用于发现数据中潜在的某种模式，从而为作出最优的决策提供依据[1，2]。
聚类作为重要的数据挖掘技术，主要用于将某个集合中的项分配到目标类别或簇，使得同一簇中成员的相似性最高。近年来，仿生算法如遗传算法（GA）、微粒群优化（PSO）等被用于解决聚类问题。Maulik[2]等人提出了被称为“GA-聚类”的基于遗传算法的聚类方法，该方法优化利用相似性度量得到的簇。王勇臻等针对K-means算法依赖于初始聚类中心和易陷入局部最优解的缺陷，提出改进的求解聚类问题的差分进化算法[3]。单冬红等对收敛速度方面和易陷入局部最优问题进行了改进[4]。Cura等利用微粒群优化方法，通过模拟鸟类结队和鱼的群居行为特征来解决聚类问题[5]。然而，大规模数据集通常包含相当多信息量的大量文件，上述序列聚类算法在对大规模数据进行聚类时，往往在内存空间和计算时间等方面具有较大开销。目前，MapReduce编程范式已经成为另一个数据并行编程模型，具有较好的容错和负载均衡能力。王焱将K⁃means和蝙蝠算法结合应用在云计算虚拟机智能调度上，降低了物理节点数量和提高资源利用率[6]。
针对大规模数据聚类问题，本文提出了基于MapReduce的人工蜂群聚类算法，能够对大规模数据进行高效聚类。
2聚类和人工蜂群算法基本原理
2.1聚类
2.2人工蜂群算法
人工蜂群算法是一种元启发式算法，步骤如下：
1）随机分布式初始化食物源的位置；2）所有雇佣蜂选择一个候选食物源位置，基于之前已选择食物源位置的临近位置，选择新食物源位置；3）每个观察蜂根据从雇佣蜂得到的适应度值以一定概率选择新的食物源位置；4）观察蜂前往被选择食物源的位置，并根据所选食物源，选择其临近的新的食物源位置；5）丢弃所有适应度未增加的食物源位置，并由侦察蜂随机确定新的位置。
上述过程重复执行，直到迭代次数达到最大循环次数。
3基于MapReduce的人工蜂群聚类算法
基于MapReduce的人工蜂群算法的步骤如下：
1）随机分布式初始化食物源位置，并将其作为雇佣蜂的初始位置。初始位置用如下公式（3）表示：
（3）
5）基于MapReduce计算新位置的适应度，并根据适应度的大小决定是否更新当前位置。
6）考察一段时间内中心值适应度是否增加，如适应度未增加，则丢弃当前中心值，产生新的中心值，否则，执行步骤7）。
7）考察中心值是否满足条件，如是，则执行步骤8），如否，则执行步骤2）。
8）利用最优中心值对数据进行聚类。
4实验
4.1实验设置
本文算法和对比算法均以Perl语言实现，并在包含10个节点的Hadoop集群中运行，每个节点的配置为：1核2.26GHzCPU，2G内存，120G硬盘空间，Ubuntu14.04操作系统，ApacheHadoop2.6.2。算法使用的仿真数据是磁盘驱动器产生的，数据为UCI机器学习数据集中的4个基准数据集，如表1所示。
表1 4个测试数据集
4.2实验结果
在衡量聚类效果时，本文采用F值度量方法来评估聚类的准确度。F值度量方法将每个簇作为一个查询，将每个类别作为查询的预期结果。算法得到的簇 和已标记的基准数据中类别 之间的F度量值可
利用公式（6）计算得到：
其中，F值的上限为1，当且仅当类别 中的全部实例被分到簇 时。F越大，表示聚类的效果越好。
基于仿真数据，与现有PK-Means算法和并行K-PSO算法的聚类效果比较如表2所示。
表2 不同数据集的F度量值计算结果
从表2可以看出，本文算法的F度量值明显高于PK-Means算法和并行K-PSO算法的F度量值，即本文算法的聚类效果更优。
5结束语
针对大数据聚类问题，提出了基于MapReduce的人工蜂群聚类算法，并利用仿真数据和磁盘驱动器制造真实数据两类数据对算法的聚类效果，实验结果表明，与PK-Means算法和并行K-PSO算法相比，本文算法具有更好的分类性能。
参考文献
[1]任凯，邓武，俞琰.基于大数据技术的网络日志分析系统研究[J].现代电子技术，2016，39(2):39-42.
[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]单冬红，郭静博，赵伟艇.Hadoop集群作业调度算法优化技术研究[J]，现代电子技术，2016，39(6):25-30.
[5]Cura T. A particle swarm optimization approach to clustering [J]， Expert Systems with Applications， 2012， 39(1): 1582-1588.
[6]王焱.基于K-means和蝙蝠算法的云计算虚拟机智能调度[J]，现代电子技术，2016，39(21)，21-24.
论文作者:沈舒雨
论文发表刊物:《电力设备》2018年第23期
论文发表时间:2019/1/2
标签：算法论文; 数据论文; 位置论文; 的人论文; 工蜂论文; 蜂群论文; 食物论文; 《电力设备》2018年第23期论文;