基于MapReduce的GEP_K均值聚类算法

古凌岚

（广东轻工职业技术学院计算机工程系，广州　510300）

基于MapReduce的GEP_K均值聚类算法

古凌岚

（广东轻工职业技术学院计算机工程系，广州510300）

0　引言

K均值算法是一种简单有效的聚类分析方法，但存在k值难以确定、易陷入局部最优和大数据量效率低等问题［1］，在实际应用中有一定的局限性。基因表达式编程（Gene Expression Programming，GEP）是借鉴生物选择和进化机制发展起来的一种通用的、简单高效的随机搜索算法，具有全局寻优能力，能够在缺乏先验知识的情况下，自动挖掘数据间隐含的关系。将GEP引入K均值算法，可以克服其初始值敏感、易陷入局部最优的缺陷。文献［2，3］将GEP的全局寻优能力与K均值的局部搜索能力相结合，提出了GEP_K均值自动聚类算法。该算法无需事先确定K值，且在收敛速度和寻优精度上都有较大的提高，但计算效率较低，主要表现在从染色体生成聚类中心时表达式树（ET）的构建和遍历的时空复杂度高，适应度评价中各数据点到簇中心距离的计算环节较为耗时，随着问题规模的不断扩大，时间和空间上的消耗将会明显增加，导致算法的处理效率大幅下降。

MapReduce是一种简化的分布式编程模型和高效的任务调度模型［4］。它通过Map（映射）过程先对已分割成相互独立的数据块高度并行处理，再经Reduce（归并）汇集整理形成结果。使得用户编写的程序可在由普通机器组成的大规模集群上运行，且执行性能高。现已有研究用MapReduce设计实现进化算法和K均值的并行化，如文献［5］基于MapReduce框架实现遗传算法（Genetic Algorithms，GA）的并行化，提高了进化效率。文献［6］将MapReduce与GA结合，提出了适合于大规模变量的并行遗传算法，得到了较好的加速比。文献［7］用实验验证了在MapReduce框架下实现的K均值算法，能够实现大规模数据的有效聚类，且算法效率也得到了明显提高。这些成果为改善算法的效率提供了有用的借鉴和参考。

本文提出了基于MapReduce的基因表达式编程K均值聚类算法（MRGEP_K均值）。首先，提出一种快速操作染色体生成聚类中心的方法，无需构建和遍历ET树，借助线性数据结构即可完成；其次，利用MapReduce编程模型，设计实现适应度评价并行化；最后，在Hadoop平台上对于UCI和人工数据集进行实验，以验证算法在处理效率上的提升。

1　MRGEP_K均值聚类算法

GEP_K均值算法［2-3］的主要步骤为：随机生成初始种群；GEP染色体编码/解码生成可能的簇中心；计算个体适应度；遗传操作进化种群。重复上述步骤直到达到迭代次数。本文利用MapReduce框架优化GEP_K均值算法（MRGEP_K均值）的基本思路是：采用直接操作基因的方法，完成GEP染色体基因的表达求解计算，得到可能的簇中心点，避免构建聚类ET树（编码）和多次遍历聚类ET树（解码）的繁复操作；利用Map和Reduce任务实现各数据点到各簇中心距离计算过程的并行化，完成适应度评价，提高计算效率，以适应处理大规模数据的需要。MRGEP_K均值算法流程如图1所示。

图1　MRGEP_K均值算法的并行实现流程

1.1染色体基因表达求解方法的改进

构建和遍历聚类ET树的目的是实现簇的合并与分割［2-3］，若能从基因结构中发现聚类运算符（F）节点及其操作对象（T）节点，就可实现相应的簇合并与分割。因此，本文引入动态数组arrayList1、arrayList2，利用arrayList1存放基因元素，arrayList2存放参与合并操作的节点位置编号序列，通过对两个数组各遍历一次，完成簇的合并与分割，得到聚类簇的中心点。算法步骤为：

Reduce阶段

（1）读取染色体R＝f1f2…fhx1x2…xt，其中fi∈F，xi∈T，F=｛f|f为聚类运算符∪和∩｝，∪为分割，∩为合并，T= ｛x|x为数据点｝，存入arrayList1，初始化变量r=2，由r定位F节点的第一个操作节点的位置，初始化arrayList2，并定义辅助数组arrayList3保存所生成的聚类中心点。

（2）从前向后遍历arrayList1，每次读取元素ei、er+1和er+2的位置编号，即运算符节点及其操作对象节点的位置，在arrayList2查找是否存在包含序号i的元素，若存在则用r+1，r+2替换之，否则①当编号i对应∩运算符时，则将 ei、er+1和 er+2的位置编号序列加入 arrayList2；②当编号i对应∪运算符，且r+1，r+2对应的元素均为T时，则将r+1，r+2对应的T节点加入arrayList3，实现簇分割。然后设置r=r+2以定位i+1个F节点的第一个操作节点的位置，直到i=h，h为基因头部长度，从而得到一（多）组参与合并操作的节点的位置编号序列。

（3）从前向后遍历arrayList2，对于每个元素中的位置编号序列，计算对应的T节点均值，并加入arrayList3，实现簇的合并。

（4）将簇中心点写入聚类中心信息文件。

由于T类元素是操作对象，必然是聚类ET树中的叶子节点，因而，②只需遍历前h个F节点即可。图2是实现簇的合并与分割的示意图。图2（a）i=1，其子节点为序号2，3的F节点，因arrayList2无元素，到达图2 （b）i=2的节点为∩，将序号2，4，5加入arrayList2，图2 （c）i=3的节点为∪，且其节点为T，将x1、x2加入arrayList3，实现簇的分割，图2（d）i=4的节点为∩，用序号8，9替换arrayList2中的序号4，类似地图2（d）序号5被替换，图2（f）遍历arrayList2，得到序号2对应T节点（序号8、9、10、11）的均值，实现簇的合并。

1.2适应度评价的并行化

Map阶段完成各数据点到簇中心的距离，以及簇划分。map函数输出中间结果＜key，value＞对的形式为＜个体号，数据点信息＞，value包括中心点号、数据对象、到簇中心的最小距离；Reduce阶段完成个体适应度的计算。reduce函数输出结果＜key，value＞对的形式为确良＜个体号，适应度＞，保存在适应度值信息文件中。算法步骤：

Map阶段

①加载从Job1得到的k个聚类中心C，接收分块数据集D；

②计算每个数据点Dj与C1，C2，…，Ck的距离Dist （j，1），Dist（j，2），…，Dist（j，k）；

③将数据点Dj划分到Distmin（j，i）对应的簇i中；

④输出聚类簇划分，及各点到其簇中心最小距离。

Reduce阶段

①接收Map阶段的聚类划分，及各点到其簇中心最小距离；

③输出适应度f。

图2　染色体基因表达求解示意图

1.3遗传操作的实现

Reduce阶段加载Job2得到的个体适应度值，对种群进行进化操作，生成新一代种群。输出结果＜key，value＞对的形式为＜个体号，个体信息＞，更新种群信息文件。该步无Map。

Reduce阶段

①读取种群信息文件和个体适应度值信息文件；

②保留最优个体；

③按照一定策略进行选择、交叉和变异操作；

④输出新种群。

1.4算法的复杂度分析

GEP_K均值的时间复杂度为O（mks+ts），m为样本数，k为分类数，s为迭代次数，t为染色体基因长度，空间复杂度O（t+1），MRGEP_K均值算法利用线性数据结构，完成基因的表达求解，无需动态开辟和维护额外空间，空间复杂度为O（1），串行执行的时间复杂度为O （mks+hs），h为基因头部长度，在MapReduce框架下，数据点到各簇中心距离的计算被分散到多个Mapper节点并行处理，当节点数为n时，时间复杂度为O（mks/ n+hs），计算时间复杂度大幅降低，随着集群规模的增大，运行效率会有更明显的提高。

2　实验结果与分析

2.1实验环境、数据集和评价指标

实验环境为Hadoop平台，由7台普通PC构成，其中1台为主节点，另6台为从节点，硬件配置为Intel Core i3 CPU，4GB RAM，软件配置为Java1.6和Hadoop 1.2.1。算法的基本参数设置为种群规模N=40，交叉概率Pc=0.77，变异概率Pm=0.05，迭代次数t＝50。测试数据采用UCI的3个数据集（见表1），其中Iris是测试无监督聚类方法效果的典型数据集。另外，为了进一步验证算法的并行性能，将Iris扩展为10维样本数5×105、1× 106、2×106的3个数据集DW1、DW2、DW3，规模分别为20M、50M、100M。

表1　实验样本数据集

对于算法的计算效率，本文通过运行时间和占用内存进行评价。对于算法的并行性能，则采用加速比和可扩展性来衡量。

2.2实验结果分析

（1）改进的基因表达求解方法性能分析

通过两组实验，对GEP_K均值（算法1）、MRGEP _K均值 （算法2）中基因表达求解方法的性能进行比较，随机产生测试基因，对于每组参数，进行10次实验，结果取平均值。第一组，测试当基因长度变化时，算法执行时间变化情况，设置N=1000，h为10～60的6组参数；第二组，测试当种群规模增长时，算法运行时间和内存占用情况的变化，设置h=20，N为10000-60000 的6组参数。两组实验的运行结果如表2所示。

表2　基因表达求解方法性能分析实验结果

由实验结果可知，无论是基因长度增长，还是种群规模扩大，算法2的运行时间都远远小于算法1，前者仅为后者的1/3～1/4；在内存占用方面，算法1内存消耗是算法2的4倍以上，同时随着种群规模的增长，算法1内存消耗明显增加，当N＝60000时，内存溢出，而算法2的内存消耗基本不变。由此可见，在运行时间开销上算法2比算法1提高了3～4倍，且没有额外的空间开销。

（2）并行MRGEP_K均值的有效性分析

对于表1中3个数据集，采用串行MRGEP_K均值和并行MRGEP_K均值（单机处理）分别运行20次，得到的结果平均值如表3所示。

表3　有效性分析实验结果

由表3可知，就执行时间而言，并行MRGEP_K均值时间明显较长，原因是MapReduce操作启动map和reduce任务的时间代价较大，因而，单个运算节点MapReduce处理小数据量，不具优势，但它与其串行算法的聚类效果较为一致，实验结果数据非常接近，说明并行MapReduce框架并未影响算法的聚类质量。

（3）并行混合聚类算法的加速比分析

加速比反映了算法的并行性使运行时间减少所获得的性能提升，其计算公式为S=Ts/Tp，其中Ts、Tp分别表示串行和并行算法计算所消耗的时间。采用DW1、DW2、DW3数据集，分别选择1、2、4、6个运算节点参与计算，T为30次，进行多次测试，算法的平均运行时间与节点数的关系如图3所示，对应的加速比结果如图4所示。由实验数据可知，随着集群中计算机节点的增加，平均运行时间不断降低，降幅逐步减少，表明算法具有较好的加速比，能够明显提高数据的处理能力，但节点数增加的同时，也会增多节点间通信消耗；随着数据集规模的扩大，加速比也随之增加，则说明算法对于大规模数据的处理效率更高。

图3　运行时间与节点数关系

图4　加速比实验结果

（4）并行MRGEP_K均值算法的可扩展性分析

可扩展性是指并行算法有效利用集群中运算节点增加的能力，其计算公式为E=S/P，其中S为加速比，P为集群节点数。分别选择2、4、6个运算节点，以及不同规模的DW1、DW2和DW3数据集，计算并行效率。计算结果如图5所示。计算结果表明，对于较大的数据集，其并行效率更高，最高达到0.86；当数据规模和节点数都增加时，并行处理能力稳定，表现出较好的可扩展性。

图5　可扩展性实验结果

3　结语

本文采用MapReduce并行编程模型，实现适应度评价的并行化，借助线性数据结构改善基因表达求解环节的计算复杂度，构建了基于MapReduce的GEP_K均值聚类算法。实验结果表明，本文算法与GEP_K均值相比，迭代处理的时间明显减少，尤其是较大规模的数据集，运行效率的提高更为明显。对于高维数据集，采用欧氏距离函数作为聚类准则，很难度量数据对象间的相似性，优化聚类准则提高聚类质量将是下一步研究工作的重点。

［1］孙吉贵，刘杰，赵连宇.聚类算法的研究［J］.软件学报，2008，19（1）：49-60.

［2］陈瑜，唐常杰，叶尚玉，等.基于基因表达式编程的自动聚类方法［J］.四川大学学报：工程科学版，2007，39（2）：107-112.

［3］姜代红，张三友.基于基因表达式编程的K均值自动聚类算法［J］.计算机仿真，2010，27（12）：216-219.

［4］李成华，张新访，金海，等.MapReduce：新型的分布式并行计算编程模型［J］.计算机工程与科学，2011，33（3）：129-135.

［5］VERMA A，LLORA X，GOLDBERG D E，et al.Scaling genetic algorithms using MapReduce［C］//ISDA'09：Intelligent Systems Design and Applications，2009 9th International Conference on.IEEE，2009：13-18.

［6］李东，潘志松.一种适用于大规模变量的并行遗传算法研究［J］.计算机科学，2012，39（7）：182-184.

［7］AMRESH K，KIRAN M，B.R.PRATHAP.Verification and validation of MapReduce program model for parallel K-means algorithm on Hadoop cluster［C］//2013 International Conference on Computing，Communications and Networking Technologies.Tiruchengode：IEEE，2013：1-8.

［8］KEMILLY D G，MURILO C N.Multiple parallel MapReduce K-means clustering with validation and selection［C］.2014 Brazilian Conference on Intelligent Systems.Sao Paulo：IEEE，2014：432-437.

［9］彭昱忠，元昌安，麦雄发，等.基因表达式编程的理论研究综述［J］.计算机应用研究，2011，2（28）：414-438.

［10］张雪萍，龚康莉，赵广才.基于MapReduce的K-Medoids并行算法［J］.计算机应用，2013，33（4）：1023-1025，1035.

［11］Mukhopadhyay A，Maulik U，Bandyopadhyay S.An interactive approach to multiobjective clustering of Gene Expression Patterns［J］. IEEE Transactions on Biomedical Engineering，2013，60（1）：35-41.

［12］王小平，曹立明.遗传算法：理论、应用与软件实现［M］.西安：西安交通大学出版社，2002.

K-means；Gene Expression Programming（GEP）；MapReduce；Parallel；Massive Data

GEP_K-means Clustering Algorithm Based on MapReduce

GU Ling-lan
（Department of Computer Engineering，Guangdong Industry Technical College，Guangzhou 510300）

1007-1423（2015）20-0010-06

10.3969/j.issn.1007-1423.2015.20.003

古凌岚（1965-），女，广东梅州人，本科，副教授，研究方向为数据挖掘、Web服务2015-05-12

2015-07-04

针对基于基因表达式编程的K均值聚类算法（GEP_K均值）中聚类中心生成和适应度评价环节的计算效率较低的问题，提出一种基于MapReduce框架的GEP_K均值聚类算法。采用MapReduce分布式并行编程模式，对适应度评价环节进行并行化改进，以减少算法处理时间，借助线性数据结构直接操作染色体基因，以降低染色体基因表达求解生成聚类中心的时间和空间复杂度，并在Hadoop平台上通过仿真实验对算法的性能进行验证。实验结果表明，该算法获得了较好的加速比和可扩展性，且无需额外空间开销，适用于聚类数未知的大规模数据集的聚类分析。

K均值；基因表达式编程；MapReduce；并行；大数据集

广东省档案局科研技项目（YDK-95-2014）

In order to improve the computation efficiency of cluster center generation and fitness evaluation in K-means clustering algorithm based on Gene Expression Programming.Proposes a hybrid clustering algorithm of K-means and GEP based on MapReduce framework.As a distributional parallel programming model，MapReduce is used to parallel the computation of fitness evaluation in order to reduce processing time，and uses linear data structure to operated directly on chromosome genes in order to reduce the time and space complexities of genes expression to solve the cluster center.Verifies the algorithm on Hadoop by simulations.Experimental results show that the algorithm has high speedup and good stability，and no extra space overhead，fits to clustering analysis on massive data.