歐炳華

（桂林電子科技大學數(shù)學與計算科學學院，廣西 桂林541004）

0 前言

互聯(lián)網(wǎng)的快速發(fā)展帶來了大量數(shù)據(jù)，依靠單機技術(shù)已經(jīng)很難處理如此海量的數(shù)據(jù)，并行技術(shù)是處理海量數(shù)據(jù)的重要方法。鑒于小波在時頻域上的局部化分析能力，以及小波聚類算法在數(shù)據(jù)處理中的良好表現(xiàn)，研究多機并行環(huán)境下的小波聚類算法具有重要意義。

1 MapReduce編程模型

MapReduce是海量數(shù)據(jù)分布式并行運算的編程模型[1]。該模型把海量數(shù)據(jù)運算問題分成多個數(shù)據(jù)塊并行運算問題[2]，而在并行運算中的任務(wù)啟動、任務(wù)調(diào)度、網(wǎng)絡(luò)通信等復(fù)雜問題，都由MapReduce編程模型解決，使用者只需編寫map和reduce函數(shù)代碼就可以運算海量數(shù)據(jù)。圖1是MapReduce編程模型，輸入數(shù)據(jù)集被劃分成多個分片（split），每個分片（split）被分配到指定的Map任務(wù)節(jié)點，Map任務(wù)節(jié)點讀取指定分片（split）內(nèi)容并解析成鍵值對＜k1,v1＞，map函數(shù)代碼處理每一條鍵值對＜k1,v1＞，獲得另一組鍵值對[3]＜k2,v2＞，按照k2排序后把鍵值對復(fù)制到Reduce任務(wù)節(jié)點。Reduce任務(wù)節(jié)點合并所有從Map任務(wù)節(jié)點復(fù)制過來的數(shù)據(jù)，得到＜k2,list＜v2＞＞，然后執(zhí)行reduce函數(shù)代碼，把運算結(jié)果存儲到分布式文件系統(tǒng)（HDFS）[3]。

圖1 MapReduce編程模型

2 小波聚類算法

小波變換是在克服傅里葉變換和窗口傅里葉變換缺陷的基礎(chǔ)上發(fā)展起來的一種新的變換[4]。在不違背測不準原理的情況下，因提供了一種靈活可變的時頻窗而被廣泛應(yīng)用于非平穩(wěn)信號處理中[5]。聚類是數(shù)據(jù)挖掘的重要技術(shù)[6]，依據(jù)數(shù)據(jù)本身屬性劃分數(shù)據(jù)集。常用的聚類算法有K-means算法、BIRCH算法、DBSCAN算法和小波聚類算法等。

小波聚類是基于小波變換的聚類算法[7-8]，該算法有許多優(yōu)點，例如能夠處理離群值、發(fā)現(xiàn)任意形狀的簇等。在小波聚類算法中，數(shù)據(jù)等同于信號，通過應(yīng)用小波變換，數(shù)據(jù)被分解為不同頻率的子波段，根據(jù)波段頻率的不同，數(shù)據(jù)點被劃分為高頻部分的數(shù)據(jù)點和低頻部分的數(shù)據(jù)點，其中高頻部分的數(shù)據(jù)點是聚類邊界，低頻部分的數(shù)據(jù)點是聚類本身。

小波聚類算法分為三個階段。第一階段是量化特征空間，該階段又分為構(gòu)造網(wǎng)格單元、確定數(shù)據(jù)對象落入的網(wǎng)格單元和匯總每個網(wǎng)格單元中數(shù)據(jù)對象形成特征空間。第二階段是在特征空間上應(yīng)用小波變換，獲得新特征空間，在新特征空間上檢測連通單元（簇），并給連通單元（簇）分配類標簽。第三階段是構(gòu)造新特征空間單元與舊特征空間單元之間的映射關(guān)系，并把每個數(shù)據(jù)對象標明類標簽。圖2是小波聚類流程圖。

圖2 小波聚類流程圖

3 并行小波聚類算法

小波聚類算法處理海量數(shù)據(jù)需要耗費大量的運行時間。因此，本文在此基礎(chǔ)上，結(jié)合MapReduce編程模型，提出了基于MapReduce的并行小波聚類算法，達到快速聚類目的。并行小波聚類算法在涉及到海量數(shù)據(jù)的階段使用了4個MapReduce編程模型。第一階段量化特征空間使用了3個MapReduce編程模型，由于第二階段不涉及到海量數(shù)據(jù)，所以不使用MapReduce編程模型，第三階段使用一個MapReduce編程模型。圖3是并行小波聚類算法流程。

圖3 并行小波聚類算法流程

第一個MapReduce輸入一個d維特征空間含有N個數(shù)據(jù)對象O={o1,o2,…,oN}的數(shù)據(jù)集，其中oi=＜oi1,oi2,…,oid＞，1≤i≤N。Map函數(shù)獲取每個分片數(shù)據(jù)集每個維的最大值pt=＜pt1,pt2,…,ptd＞和最小值qt=＜qt1,qt2,…,qtd＞，1≤t≤T，T是Mapper任務(wù)節(jié)點數(shù)，ptj是第t個分片數(shù)據(jù)集第j維的最大值，qtj是第t個分片數(shù)據(jù)集第j維的最小值，1≤j≤d。reduce在map函數(shù)返回的結(jié)果中獲取最大值max=＜max1,max2,…,maxd＞和最小值min=＜min1,min2,…,mind＞,maxj是ptj的最大值，minj是qtj的最小值，1≤t≤T，1≤j≤d。返回max和min。完成這個MapReduce后，計算網(wǎng)格單元間隔距離d，本文假設(shè)所有維都是劃分m個間隔。

第二個MapReduce和第一個MapReduce輸入相同。map函數(shù)確定數(shù)據(jù)對象oi=＜oi1,oi2,…,oid＞落入的網(wǎng)格單元ci=＜ci1,ci2,…,cid＞,其中，floor()表示取上整，1≤cij≤m，1≤i≤N，1≤j≤d。Reduce不執(zhí)行任何操作，最后輸出鍵值對＜oi,ci＞。

第三個MapReduce輸入鍵值對＜oi,ci＞，1≤i≤N。map函數(shù)將＜oi,ci＞變?yōu)殒I值對＜ci,1＞。使用combiner排序。reduce函數(shù)將相同的鍵ck=＜ck1,ck2,…,ckd＞對應(yīng)的值相加，得到落入單元ck數(shù)據(jù)對象的數(shù)量sum_k，1≤ckj≤m，1≤k≤md，md是特征空間單元數(shù)目。輸出鍵值對＜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函數(shù)獲取單元根據(jù)數(shù)據(jù)對象oi映射到cf，cf映射到ch，ch映射到ωn，得到oi映射到ωn，ωn是簇序號，map函數(shù)輸出鍵值對＜oi,ωn＞。Reduce不執(zhí)行任何操作。

4 實驗分析

實驗使用5臺配置相同的電腦，CPU型號是G1620，內(nèi)存容量是2GB，操作系統(tǒng)是ubuntu 14.04LTS，采用hadoop-1.2.1版本，jdk版本是jdk-8u11-linux-x64。使用加速比評價并行小波聚類性能，計算公式是是串行算法（單節(jié)點）消耗的時間，Tp是并行p個節(jié)點消耗的時間,理想的加速比是線性加速比[9]。實驗數(shù)據(jù)來源于合成的2.75GB數(shù)據(jù)，分別計算任務(wù)節(jié)點是1、2、3、4的加速比。圖4是實驗結(jié)果。結(jié)果表明：在相同規(guī)模數(shù)據(jù)情況下，增加節(jié)點數(shù)可以提高加速比，從而顯著地減少程序運行時間；根據(jù)實驗得到的加速比，可以確定實際加速比在較好的狀態(tài)，并沒有達到理想狀態(tài)，原因在于MapReduce框架存在通信、任務(wù)啟動、任務(wù)調(diào)度、故障處理等時間開銷，任務(wù)節(jié)點數(shù)越多，實際加速比與理想加速比差距越大。

圖4 實驗結(jié)果

5 結(jié)束語

本文應(yīng)用MapReduce并行運算模型，結(jié)合小波聚類算法特點，設(shè)計并實現(xiàn)了基于MapReduce的并行小波聚類算法，通過實驗驗證并行小波聚類算法性能，結(jié)果表明：并行小波聚類算法具有較好的加速比。

［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技術(shù)內(nèi)幕：深入解析MapReduce架構(gòu)設(shè)計與實現(xiàn)原理[M].北京:機械工業(yè)出版社,2013.

［3］[美]懷特.Hadoop權(quán)威指南[M].2版.周敏奇,王曉玲,金澈清,等,譯.北京:清華大學出版社,2011.

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

［5］[美]博格斯,馬科維奇.小波與傅里葉分析基礎(chǔ)[M].芮國勝,康健,譯.北京:電子工業(yè)出版社,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].計算機應(yīng)用,2013,33(4):1023-1025.