基于Map Reduce的并行小波聚類(lèi)

歐炳華

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

0 前言

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

1 MapReduce編程模型

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

圖1 MapReduce編程模型

2 小波聚類(lèi)算法

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

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

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

圖2 小波聚類(lèi)流程圖

3 并行小波聚類(lèi)算法

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

圖3 并行小波聚類(lèi)算法流程

第一個(gè)MapReduce輸入一個(gè)d維特征空間含有N個(gè)數(shù)據(jù)對(duì)象O={o1,o2,…,oN}的數(shù)據(jù)集，其中oi=＜o(jì)i1,oi2,…,oid＞，1≤i≤N。Map函數(shù)獲取每個(gè)分片數(shù)據(jù)集每個(gè)維的最大值pt=＜pt1,pt2,…,ptd＞和最小值qt=＜qt1,qt2,…,qtd＞，1≤t≤T，T是Mapper任務(wù)節(jié)點(diǎn)數(shù)，ptj是第t個(gè)分片數(shù)據(jù)集第j維的最大值，qtj是第t個(gè)分片數(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。完成這個(gè)MapReduce后，計(jì)算網(wǎng)格單元間隔距離d，本文假設(shè)所有維都是劃分m個(gè)間隔。

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

第三個(gè)MapReduce輸入鍵值對(duì)＜o(jì)i,ci＞，1≤i≤N。map函數(shù)將＜o(jì)i,ci＞變?yōu)殒I值對(duì)＜ci,1＞。使用combiner排序。reduce函數(shù)將相同的鍵ck=＜ck1,ck2,…,ckd＞對(duì)應(yīng)的值相加，得到落入單元ck數(shù)據(jù)對(duì)象的數(shù)量sum_k，1≤ckj≤m，1≤k≤md，md是特征空間單元數(shù)目。輸出鍵值對(duì)＜ck,sum_k＞。完成MapReduce后，對(duì)特征空間實(shí)施l次小波變換，獲得新特征空間單元ch=＜ch1,ch2,…,chd＞，1≤ckj≤，檢測(cè)連通單元和標(biāo)類(lèi)，得到?ω,?ch,ch∈ω?lch=ωn，其中ω是簇，ωn是簇序號(hào)，lch是單元ch的標(biāo)類(lèi)。

第四個(gè)MapReduce輸入鍵值對(duì)＜o(jì)i,ci＞，1≤i≤N。map函數(shù)獲取單元根據(jù)數(shù)據(jù)對(duì)象oi映射到cf，cf映射到ch，ch映射到ωn，得到oi映射到ωn，ωn是簇序號(hào)，map函數(shù)輸出鍵值對(duì)＜o(jì)i,ωn＞。Reduce不執(zhí)行任何操作。

4 實(shí)驗(yàn)分析

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

圖4 實(shí)驗(yàn)結(jié)果

5 結(jié)束語(yǔ)

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

［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è)計(jì)與實(shí)現(xiàn)原理[M].北京:機(jī)械工業(yè)出版社,2013.

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

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

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