基于Map Reduce的并行小波聚类

欧炳华

（桂林电子科技大学数学与计算科学学院，广西 桂林541004）

0 前言

互联网的快速发展带来了大量数据，依靠单机技术已经很难处理如此海量的数据，并行技术是处理海量数据的重要方法。鉴于小波在时频域上的局部化分析能力，以及小波聚类算法在数据处理中的良好表现，研究多机并行环境下的小波聚类算法具有重要意义。

1 MapReduce编程模型

MapReduce是海量数据分布式并行运算的编程模型[1]。该模型把海量数据运算问题分成多个数据块并行运算问题[2]，而在并行运算中的任务启动、任务调度、网络通信等复杂问题，都由MapReduce编程模型解决，使用者只需编写map和reduce函数代码就可以运算海量数据。图1是MapReduce编程模型，输入数据集被划分成多个分片（split），每个分片（split）被分配到指定的Map任务节点，Map任务节点读取指定分片（split）内容并解析成键值对＜k1,v1＞，map函数代码处理每一条键值对＜k1,v1＞，获得另一组键值对[3]＜k2,v2＞，按照k2排序后把键值对复制到Reduce任务节点。Reduce任务节点合并所有从Map任务节点复制过来的数据，得到＜k2,list＜v2＞＞，然后执行reduce函数代码，把运算结果存储到分布式文件系统（HDFS）[3]。

图1 MapReduce编程模型

2 小波聚类算法

小波变换是在克服傅里叶变换和窗口傅里叶变换缺陷的基础上发展起来的一种新的变换[4]。在不违背测不准原理的情况下，因提供了一种灵活可变的时频窗而被广泛应用于非平稳信号处理中[5]。聚类是数据挖掘的重要技术[6]，依据数据本身属性划分数据集。常用的聚类算法有K-means算法、BIRCH算法、DBSCAN算法和小波聚类算法等。

小波聚类是基于小波变换的聚类算法[7-8]，该算法有许多优点，例如能够处理离群值、发现任意形状的簇等。在小波聚类算法中，数据等同于信号，通过应用小波变换，数据被分解为不同频率的子波段，根据波段频率的不同，数据点被划分为高频部分的数据点和低频部分的数据点，其中高频部分的数据点是聚类边界，低频部分的数据点是聚类本身。

小波聚类算法分为三个阶段。第一阶段是量化特征空间，该阶段又分为构造网格单元、确定数据对象落入的网格单元和汇总每个网格单元中数据对象形成特征空间。第二阶段是在特征空间上应用小波变换，获得新特征空间，在新特征空间上检测连通单元（簇），并给连通单元（簇）分配类标签。第三阶段是构造新特征空间单元与旧特征空间单元之间的映射关系，并把每个数据对象标明类标签。图2是小波聚类流程图。

图2 小波聚类流程图

3 并行小波聚类算法

小波聚类算法处理海量数据需要耗费大量的运行时间。因此，本文在此基础上，结合MapReduce编程模型，提出了基于MapReduce的并行小波聚类算法，达到快速聚类目的。并行小波聚类算法在涉及到海量数据的阶段使用了4个MapReduce编程模型。第一阶段量化特征空间使用了3个MapReduce编程模型，由于第二阶段不涉及到海量数据，所以不使用MapReduce编程模型，第三阶段使用一个MapReduce编程模型。图3是并行小波聚类算法流程。

图3 并行小波聚类算法流程

第一个MapReduce输入一个d维特征空间含有N个数据对象O={o1,o2,…,oN}的数据集，其中oi=＜oi1,oi2,…,oid＞，1≤i≤N。Map函数获取每个分片数据集每个维的最大值pt=＜pt1,pt2,…,ptd＞和最小值qt=＜qt1,qt2,…,qtd＞，1≤t≤T，T是Mapper任务节点数，ptj是第t个分片数据集第j维的最大值，qtj是第t个分片数据集第j维的最小值，1≤j≤d。reduce在map函数返回的结果中获取最大值max=＜max1,max2,…,maxd＞和最小值min=＜min1,min2,…,mind＞,maxj是ptj的最大值，minj是qtj的最小值，1≤t≤T，1≤j≤d。返回max和min。完成这个MapReduce后，计算网格单元间隔距离d，本文假设所有维都是划分m个间隔。

第二个MapReduce和第一个MapReduce输入相同。map函数确定数据对象oi=＜oi1,oi2,…,oid＞落入的网格单元ci=＜ci1,ci2,…,cid＞,其中，floor()表示取上整，1≤cij≤m，1≤i≤N，1≤j≤d。Reduce不执行任何操作，最后输出键值对＜oi,ci＞。

第三个MapReduce输入键值对＜oi,ci＞，1≤i≤N。map函数将＜oi,ci＞变为键值对＜ci,1＞。使用combiner排序。reduce函数将相同的键ck=＜ck1,ck2,…,ckd＞对应的值相加，得到落入单元ck数据对象的数量sum_k，1≤ckj≤m，1≤k≤md，md是特征空间单元数目。输出键值对＜ck,sum_k＞。完成MapReduce后，对特征空间实施l次小波变换，获得新特征空间单元ch=＜ch1,ch2,…,chd＞，1≤ckj≤，检测连通单元和标类，得到∀ω,∀ch,ch∈ω⇒lch=ωn，其中ω是簇，ωn是簇序号，lch是单元ch的标类。

第四个MapReduce输入键值对＜oi,ci＞，1≤i≤N。map函数获取单元根据数据对象oi映射到cf，cf映射到ch，ch映射到ωn，得到oi映射到ωn，ωn是簇序号，map函数输出键值对＜oi,ωn＞。Reduce不执行任何操作。

4 实验分析

实验使用5台配置相同的电脑，CPU型号是G1620，内存容量是2GB，操作系统是ubuntu 14.04LTS，采用hadoop-1.2.1版本，jdk版本是jdk-8u11-linux-x64。使用加速比评价并行小波聚类性能，计算公式是是串行算法（单节点）消耗的时间，Tp是并行p个节点消耗的时间,理想的加速比是线性加速比[9]。实验数据来源于合成的2.75GB数据，分别计算任务节点是1、2、3、4的加速比。图4是实验结果。结果表明：在相同规模数据情况下，增加节点数可以提高加速比，从而显著地减少程序运行时间；根据实验得到的加速比，可以确定实际加速比在较好的状态，并没有达到理想状态，原因在于MapReduce框架存在通信、任务启动、任务调度、故障处理等时间开销，任务节点数越多，实际加速比与理想加速比差距越大。

图4 实验结果

5 结束语

本文应用MapReduce并行运算模型，结合小波聚类算法特点，设计并实现了基于MapReduce的并行小波聚类算法，通过实验验证并行小波聚类算法性能，结果表明：并行小波聚类算法具有较好的加速比。

［1］Li,C.H.,Zhang,X.F.and H.Jin.Mapreduce:a new programming model for distributed parallel computing [J].Computer Engineeringffamp;Science,2011,33(3):129-135.

［2］董西成.Hadoop技术内幕：深入解析MapReduce架构设计与实现原理[M].北京:机械工业出版社,2013.

［3］[美]怀特.Hadoop权威指南[M].2版.周敏奇,王晓玲,金澈清,等,译.北京:清华大学出版社,2011.

［4］蒋英春.小波分析基本原理[M].天津:天津大学出版社,2012.

［5］[美]博格斯,马科维奇.小波与傅里叶分析基础[M].芮国胜,康健,译.北京:电子工业出版社,2013.

［6］Trevor,H.,Robert,T.and F.Jerome.The Elements of Statistical Learning:Data Mining,Inference and Prediction[M].Springer-Verlag,2009.

［7］Sheikholeslami,G.and A.Zhang.Approach to clustering large visual databases using wavelet transform[J].SPIE Proceedings,1997,3017(4):322-333.

［8］Sheikholeslami,G.,Chattrjee,S.and A.Zhang.Wavecluster:a wavelet-based clustering approach for spatial data in very large databases[J].The VLDB Journal,2000,8(3-4):289-304.

［9］张雪萍,龚康莉,赵广才.基于MapReduce的K-Medoids并行算法[J].计算机应用,2013,33(4):1023-1025.