基于Hadoop MapReduce和粗粒度并行遗传算法的大数据聚类方法改进

郭晨晨，朱红康

(山西师范大学 数学与计算机科学学院，山西 临汾 041000)



基于Hadoop MapReduce和粗粒度并行遗传算法的大数据聚类方法改进

郭晨晨，朱红康*

(山西师范大学 数学与计算机科学学院，山西 临汾 041000)

为了提高并行遗传算法在大数据聚类问题中的时间效率，通过利用粗粒度遗传算法的并行化思想，提出了Hadoop平台上基于MapReduce计算框架的粗粒度遗传算法的并行化设计。该思想主要来源于大数据体量庞大的特点，聚类算法时间消耗巨大。并行是解决算力不足的一个较为有效的方法，实验结果表明，并行化的遗传算法在处理大数据聚类时相比传统的串行化处理在时间消耗方面有明显的降低。

大数据;聚类;MapReduce;数据挖掘;并行;粗粒度遗传算法

聚类[1]作为数据挖掘领域的一种重要的方法和手段已在各领域广泛应用。但大数据时代的到来给许多原有技术在实现层面上带来了很多新的挑战。为应对这些挑战，出现了很多关于大数据聚类方面的研究。文献[2]将遗传算法引入到聚类算法中使得聚类效果明显优于K-means算法；文献[3]是传统的遗传算法与“爬山法”相结合形成一种混合型聚类算法，以此提高寻优速率；文献[4]将聚类融合引入到遗传算法的交叉算子中，有效地缩小了算法的探索空间，加快了算法的收敛速度；文献[5]使用最大属性值范围划分法克服聚类算法对初始值的敏感性,并运用两阶段的动态选择和变异策略，先进行不同聚类数目的并行搜索,再获取最优的聚类中心。由此可见，将遗传算法加入到聚类算法中可明显提高其聚类性能。但串行的算法会造成大量的时间消耗，在实际的应用过程中产生诸多不利的影响。由此，产生传统的并行化技术。基于MPI的并行化设计[6]使得计算节点间的通信需要较多的时间来完成。基于这样的缺点，使用MapReduce[7]并行化计算框架在处理大数据聚类问题时，节点间的通信时长会降低。文献[8-9]是最近通过MapReduce并行处理一些经典聚类算法的研究。本文将大数据聚类过程分为两个阶段，分别对应MapReduce计算框架的Map阶段和Reduce阶段，牺牲少量聚类正确率换取大量算力的提升。

1　传统遗传算法和并行遗传算法

图1　遗传算法基本流程Fig.1　Basic process of genetic algorithm

遗传算法的灵感来源于大自然的客观规律。通过模拟生物进化机制中染色体的交叉、变异、选择和继承达到个体的不断优化，这种启发式的算法用于解决基于搜索和优化的问题。遗传算法在其整个运行过程中的遗传操作具有随机性，但并不代表遗传算法是完全随机搜索的。因为该算法能利用过去有效的信息来预测进化形成的下一代期望性能有所提升的寻优点集。重复这样的迭代过程，一代一代的进化，最后收敛于所期望出现的最适应环境的个体上，进而寻找到最优解。遗传算法的基本流程见图1。

并行遗传算法是在传统的遗传算法中加入并行化的设计，该技术的实现主要基于以下几个方面工作取得的成就[10-12]：①主从式并行遗传算法；②细粒度并行遗传算法；③粗粒度并行遗传算法。

主从并行遗传算法在主处理器执行选择、交叉、变异等操作，操作对象是全部个体。每个个体的适应值计算则分配给从处理器并行处理。细粒度并行遗传算法整体结构框架与大规模并行计算机体系结构相适应，操作对象针对于符合特定空间结构模式的单一个体而非全部个体，具有保持种群多样性、避免早熟等特点。粗粒度并行遗传算法结构相比于前两个较为复杂，一般包含有多个种群，子群通过某种方式交换个体，从而达到每个子种群中的最优化组合。该算法具有较好的全局搜索能力和局部的快速搜索能力，在过去的研究中常常使用单台计算机串行地实现该算法，而本文则使用多台计算机并行执行，进一步提高运算速度。

2　MapReduce

MapReduce是一种编程模型，也是一种计算框架，用于大规模数据集的并行运算。它是建立在大规模数据的分布式集群之上。每次输入数据是分布式文件系统中(Distributed File System)的一个或多个文件块，这是由于Hadoop将数据给到Map进行处理之前会使用InputFormat对数据进行两方面的预处理：①对输入数据进行切分，生成一组Split，一个Split会分发给一个Mapper进行处理;②针对每个Split，调用RecordReader读取Split内的数据，并按照的形式组织成一条Record传给Map函数进行处理。

对于生成的键-值对，需要经过两个阶段的处理，这两个阶段包括Map阶段和Reduce阶段。

Map阶段：Mapper接收通过RecordReader得到的键-值对，Mapper运用分布式算法处理键-值对并且为每一个Reduce任务建立一个中间文件。

Reduce阶段：Reduce函数的输入参数是键及其关联值表组成的对，将Reduce函数应用到单键称为一个Reducer,对Map阶段传来每一个中间文件进行并行处理，合并产生最终输出数据。

MapReduce计算框架见图2。

图2　MapReduce计算框架Fig.2　Calculation model of MapReduce

2.1基于MapRuduce的并行遗传聚类算法的实现

该方法是根据粗粒度并行遗传算法的基础上进行的改进，该方法成功的关键在于Map和Ruduce两个阶段的聚类。开始，系统调用Input Format类将输入数据集分成一定大小的文件块(split)，每一个Split被一个Mapper处理并完成第一阶段的聚类。将第一阶段产生的数据均交给单个Reducer进行处理并完成第二阶段的聚类。用若干Mapper和单个Reducer可执行该算法，具体模型见图3。

图3　MapReduce改进计算模型Fig.3　Improved computational model of MapReduce

2.2第一聚类阶段

1)种群初始化 ：每个Mapper通过接收Split形成种群的初始化个体。每个个体是大小为N的染色体，每一个染色体中包含一个质心，质心是从接收的Split数据点中随机选择的。对每个染色体中的数据点进行聚类，将数据点分配给拥有最近质心的簇。

2)适应值评估。

3)通过Davies-bouldin指标[12]对每个个体的适应值进行计算。

Davies-bouldin是用于衡量聚类效果的一种方法，该方法定义一个离散度参数Si，表示第i个类中数据点的离散程度。定义如下：

(1)

式中Ti为第i类中数据点的个数；Xi为第i类中第j个数据点；Ai为第i类的质心(聚类中心)，当q=2时，可利用公式求欧式距离。

两个聚类质心间的距离用Mij表示，公式如下：

(2)

式中ai,j为第i类质心的第j个属性。

DBI还定义了一个相似度参数Ri,j，用来评估第i类与第j类的相似度，公式如下：

(3)

最后得到DBI指数：

(4)

4)采用交叉和变异技术对染色体进行处理，需要注意的是后代的质心是父母相应质心的算术平均值。

5)对于染色体的选择，采用联赛选择算法[14]对进化的下一代进行选择，通过联赛选择算法，N个体竞争产生下一代，根据优胜劣汰原则，随机挑选N个竞争者，在交配池中竞争每一位基因遗传，适应性最好的将获得该基因的遗传权。

6)第一阶段的结束阶段：旧种群被新种群取代，而新种群被更新的种群取代，取代过程伴随着交叉、变异、选择等过程。这样一代一代的更替，直到达到终止条件结束。迭代完成得到的“最适应种群”交由Reducer处理，从而进入第二聚类阶段。

2.3第二聚类阶段

1)Reducer接收来自所有Mapper的染色体并组合成一条新的染色体。

2)新梁色体中的多个类的那些质心间距小于指定阈值的聚类要合并为一个类。合并产生的新的质心为原来质心的算术平均值。阈值的计算公式如下：

式中T为阈值；Mi,j为聚类i和聚类j之间的距离；Di和Dj分别为i类和j类中距离各自质心距离最远点；0.2距离比例系数由反复试验得到。

3)重复上述过程，直至染色体中所有聚类的质心间距有一个大于指定阈值，迭代结束。

4)最后染色体获得最佳聚类中心的位置。

3　性能评估

用本文所提方法与传统串行遗传算法进行比较。采用5台普通的计算机搭建Hadoop集群系统来评估本文方法的性能，具体配置见表1。运行迭代算法的单节点处理器配置见表2。

必要的参数设定如下: 交叉概率pc=6%； 变异概率pm=0.25%； 迭代运算次数500次； 为每个聚类分配5个Node。

软件环境如下： 软件平台：Hadoop-1.2.1。 硬件平台：VMware Workstation虚拟机上运行的Ubuntu16.04系统，分配运行内存2 G、硬盘200 G。

为了客观地评价本方法的性能，将聚类正确率的高低和消耗时间的多少作为评判标准，使用系统时钟测量执行时间。测试数据集选用Europe map坐标数据集，该数据集包含169 308个实例。

将传统串行方法设定为100%，实验可见，聚类算法的运算速度提高了80%，聚类正确率仅下降8%。

表1　实验硬件配置

表2　单节点处理器硬件配置

4　结　论

将MapReduce计算框架融入到聚类中，利用并行遗传算法相比传统经典聚类算法的性能优势，在损失少量聚类准确度的情况下，极大提高了算法整体的运行速度，更有利于理论在实际中的应用。未来的工作将对阈值公式中距离比例系数做出适当的调整，尽量减少经验因素的影响。

[1]Jain A K. Data clustering: 50 years beyond K-means[J].Pattern Recognition Letters, 2010,31(8):651-666.

[2]傅景广,许刚,王裕国.基于遗传算法的聚类分析[J].计算机工程，2004，30(4):122-124.

[3]张婧,杨炳儒.基于混合遗传算法的聚类模式数据挖掘方法[J].微计算机信息，2006,22(6)：219-221.

[4]何东晓,周栩,王佐,等.复杂网络社区挖掘—基于聚类融合的遗传算法[J].自动化学报，2010，36(8)：1160-1170.

[5]何宏,谭永红.一种基于动态遗传算法的聚类新方法[J].电子学报，2012，40(2)：254-259.

[6]刘晓平,安竹林,郑利平.基于 MPI 的主从式并行遗传算法框架[J].系统仿真学报，2004，16(9):1938-1940.

[7]刘向东,刘奎,胡飞翔,等.基于MapReduce的并行聚类算法设计与实现[J].计算机应用与软件，2014，31(11):251-256.

[8]贾瑞玉,管玉勇,李亚龙.基于MapReduce模型的并行遗传k-means聚类算法[J].计算机工程与设计，2014，35(2)：657-660.

[9]李兰英,董义明,孔银,等.改进K-means算法的MapReduce并行化研究[J].哈尔滨理工大学学报，2016，21(1):31-35.

[10] 李建明,迟忠先,万单领.一种基于GPU加速细粒度并行遗传算法的实现方法[J].控制与决策，2008，23(6):697-700.

[11] 程兴国,肖南峰.粗粒度并行遗传算法的MapReduce并行化实现[J].重庆理工大学学报，2013，27(10)：66-70.

[12] 刘正龙，杨艳梅，罗玉军.基于遗传算法的非线性系统辩识的研究[J].黑龙江大学自然科学学报，2014，31(3)：416-420.

[13] Davies D L,Bouldin D W.A cluster separation measure[C].IEEE Trans.Pattern Anal.Mach.Intelligence，1979，1:224-227.

[14] Xia G M，Zeng J C.Stochastic particle swarm optimization algorithm based on genetic algorithm of tournament selection[J].Computer Engineering & Applications，2007，43(4):51-84.

Improvement of large data clustering method based on Hadoop MapReduce and coarse grain parallel genetic algorithm

GUO Chen-Chen,ZHU Hong-Kang*

(Schoolofmathematicsandcomputerscience,ShanxiNormalUniversity,Linfen041000,China)

Parallel design of coarse grain genetic algorithm based on MapReduce computing framework is proposed in the Hadoop to improve the time efficiency of parallel genetic algorithm in large data clustering,by using the idea of parallel genetic algorithm.This idea is mainly derived from the huge amount of large data, a huge amount of time consumption of clustering algorithm.Parallelism is the solution to the lack of a more effective method. Experimental results show that parallel genetic algorithm in dealing with large data clustering compared to the traditional serial processing in time consumption has decreased significantly.

large data;clustering;MapReduce;data mining;parallel;coarse-grain genetic algorithm

10.13524/j.2095-008x.2016.03.047

2016-05-27;

2016-07-07

山西省自然科学基金资助项目(2015011040)

郭晨晨(1992-)，男，山西长治人，硕士研究生，研究方向：计算机应用，E-mail:1341290300@qq.com；*通讯作者：朱红康(1975-)，男，山西汾西人，副教授，博士，硕士研究生导师，研究方向：数据挖掘，E-mail:zhuhkyx@126.com。

TP18

A

2095-008X(2016)03-0087-05