基于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.