针对K-means算法处理海量数据存在严重的内存不足，提出利用MapReduce并行化K-means，但是普通的K均值存在收敛速度慢、易陷入局部最优和对初始聚类中心的选取等局限性，因此选择了经ACO改进过的ACO-K-means聚类算法。实验结果表明，经MapReduce并行化的ACO-K-means，不仅具有良好的加速比和扩展性，其收敛性以及聚类精度均得到了改善。
虞倩倩,戴月明,李晶晶:基于 MapReduce bACo-K- means并行聚类算法 2013,49(16)119 41Map数的设计 每次 Reduce任务结束之后,判断偏离误差ξ是否小于 Map函数的任务是完成每一个蚂蚁到信息源的信息素给定的阙值,若小于,则算法收敛结束。反之,则用本轮的 的计算,由此得到何一只蚂蚁的转移概率,最后重新标记聚类中心文件替换上一轮的中心文件,并启动新一轮的 其属于的新聚类类别,其输入为待聚类所有记录数据和上 Mapreduce Job 轮迭代(或初始聚类)的聚类中心,输入数据记录 图3为基于 Mapreduce的ACO-k- means算法处理数据 (key,wale)对的形式为(行偏移量,记录行);每个Map函的流程图。在 Reduce务之前,可对Map任务执行节点本地 数都读入聚类中心描述文件,Map函数对输入的每个记录的中间结果进行shum排序,以提高 Reduce务的效率。 点计算出到所有中心点的转移概率 Transp? obabilit;,输 (开始 出中间绐果(key, value)对的形式为( centerindex,poin), 其中, centerIndex,为第i中心点的索引号, point为当前i 输入 lev, value)) 计算转移 (key, value)→ 录点的坐标。Map函数的伪代码如下: 数据集(行偏移量,坐标)概率密度 (中心点索引 号i,坐标j void map( Writeable key, Text point)( 不 for( int i=0; i<k;il 1)i 变化小于给 (key,wle)→(中(kegy,vale)→(中心 定阙值 点索引号新点索引号,标1 dislance-Distance( puinL, center[i]); 的中心点坐标)坐标2,…,坐标刀) 计算每个妈蚁到聚类中心的信息素 计算转移概P(l) 结束 if(P2(t)>P0){ 图3基于 Mapreduce的并行ACO- K-means聚类算法的处理 currentCluster ID=i 5实验和结果分析 Emit. Intcrmcdiatc( currentClustcr ID. point) 5.1实验环境 实验环境由江南大学物联网工程学院提供如图4。实 验用11个节点测试ACO-K- means并行聚类算法,其中 42 Reduce函数的设计 台作为 master,其他10台作为 slaves。每台节点硬件配置如 educe kk数的任务是根据Map函数得到的中间结果下:CPU型号为 Intel CoreTM i3M30,主频240GIz;内 计算出新的聚类屮心,供下一轮 Mapreduce Job使用,输存为4GB;硬盘为2TB;板载 Broadcom NetLink Gigabit 入数据(key, value)对的形式为( centerindex,poin);所有 Ethernet网卡型号。软什配置如下: Linux red hat As ke相同的记录(即有相同类别D的记录送给一个 Reduce60;JDK1.6.0.29; Hadoop0.210. master上部署 Hadoop的 任务—累加key相同的点个数和各记录分量的和,求各分 NamcNodc和 Job tracker, slaves上部署 Task Tracker和 量的均值。得到新的聚类屮心喵述文件:输出结果(key, value) Datanodc o 对的形式为( centerPoint, points),其中 centerinaex 为第i 1 Submit joh「 Namenode master Client 中心点的索引号, points为隶属于第i中心点的所有数据 Job Tracker1921680.1 Reduce所数的伪代码如下 heartbeat /hearbeat hearbeat void reduce( Writable key, Iterator Point Writable poinLs DataNod Datanode DataNode Num=0 Task Tracker TaskTracker Tasktracker while( points has Next) slave slave Point Writable currentPoint" points next(): l92.1680.2 92.16×.0.3 192.168.0}.ll Num i=currentPoint get Num() 图4实验室的云计算平台 for(i=0: i< dimension: i- 5.,2单机处理比较实验 um[]+=currentPoint point[1]; 521收敛速度的比较 实验内容为比较ACO-K- mcans聚类算法与K- mcans for(i-0: i<dimension i mean i]=sum i]/Num 聚类算法在处理相同数据的条作下,它们各自完成聚类所 需要迭代的次数。处理数据集为分成8类具有20000个数 Emit( key, mean 据集的二维数据。出表1可知,ACO- K-mcans聚类算法具 有较快的收敛速度,这是因为ACO具有很好的全局收敛 性,且减小了 K-means对初始聚类中心选择的影响。 120 013,49(16) Computer Engineering and Applications计算机工程与应用 表1收敛速度比较 53集群加速比性能实验 尝试次数K- neans聚类算法ACO-K- means聚类算法 加速比是同一个任务在单处理器系统和并行处理器 系统中运行消耗的时间的比率,用来衡量并行系统或程序 并行化的性能和效果以及扩展性。 本文实验数据是有关大规模地震资料的数据。利用 基于 Mapreduce的ACO-K- means聚类算法对今年发生的 地震的类别进行聚类实验。实验分别采用3组地震资料数 7 据集,如表3所示,每条记录均由3维数值型的数据组成, 要求生成8个聚类类别,初始聚类屮心随机产生 522单机处理数据负荷比较 实验內容为比较 Hadoop集样屮的1个运算节点与 表3实验数据集情况 ACO-K- means聚类算法在处埋相同规模数据以及相同哽 数据果大小MB记录数/0数据占用HDFS 原始文件 块数空间MB 件配置环境下,从数据读入到完成ACO-K- means聚类所需 1392.64 5.18406 14976 要的时问。实验屮,ACO-K- means聚类算法由Java实现。 ABC 4048.7410.369715162 31104 该算法的缺点是当数据量逐渐增大时,算法的时间复杂度 6533.12 2.049332313 0096 会急剧増长且会出现内存不足等现象。运行时,将JM的 实验1将10个 Task tracker节点逐渐参与计算,并观 内存设置为IGB,以及 Mapreduce所利用的JM同样设察它们各自完成聚类所消耗时间的加速比。实验时,根据 管为1GB。单机实验数据来自于UCI官方网站提供的聚样本数的大小,调节每个节点运行时的最大map数和最大 类数据,试验中,将数据逐渐增大,观察实验所耗时间,实 reduce数,以充分利用 Hadoop的集群能力。实验结果如图 验情况见表1(x1为单机上使用 ACO-K-means聚类算法所5所小。从图中可以看出:当随着节点数增加时,相同数据 用时间;x,为1个运算节点完成 ACO-K-mcans聚类算法听集的聚类所消耗时间具有良好的加速比,且当数据规模逐 用时间),其中1-3为2维数据,生成4个聚类类别。4-8为渐增加时,加速比具有良好的稳定性,这说明基于 Mapreduce 3维数据,生成8个聚类类别,初始聚类中心随机产生。 的ACO-K- means聚类算法具有处理大规模数据的能力。 由上述实验结果可以看出,随着输入数据的增长, ACO-K- means的运行内存等资源消耗增大,致使机器性能 下降,直至报告内存不足且不能完成计算任务。单机 三 Hadoop的实验结果可以看出当数据量很小时, Hadoop的 运算能力远远不如 ACO-K-means聚类算法,这是因为 12345678910 MapReduce每次启动map和 reduce消耗的时问比例较大, 节点数 而实际的计算时间在总消耗时间中所占比例较小。但是, 图5某于 Mapreduce的ACO-K- m cans的 加速比实验结果 同样可以看出,当 ACO-K-means聚类算法达到内存不是而 不能计算时, Hadoop依然能进行聚类运算,由此可初步看 实验2分别选择3,6,9个 Task tracker节点,对应选择A, 出,利用 MapReduce并行化ACO-k- eans聚类算法之后 B和C数据集进行计算,实验结果如图6所示,从图中可以看 具有处理大规模数据的能力。 出:当节点数和处理数据的规模呈正比增长时, Mapreduce 处理数据的能力基本保持稳定,表现出了良好的扩展性。 表2单机处理实验结果 实验次数文件大小B样本数10° TI/S 840 芒1.0 251904 l3312 120.09 26726.4 l6.0 76.69 131.21 节点数 66867 内存不足 184 图6基于 Mapreduce的ACO-K- means的扩展性实验 668672 400 内存不足1945 (下转