趙艷萍+徐勝超

摘 要： 為了提高傳統(tǒng)數(shù)據(jù)聚類算法在大數(shù)據(jù)挖掘應(yīng)用中的性能，借助云計算的相關(guān)技術(shù)，并結(jié)合非負矩陣分解方法設(shè)計并實現(xiàn)了一種并行的數(shù)據(jù)層次聚類算法。該算法采用MapReduce編程平臺，利用Hadoop的HDFS存儲大容量的電信運營商數(shù)據(jù)；描述了MapReduce的數(shù)據(jù)分級聚類并行處理的工作機制與流程；通過Map和Reduce這種主?從編程模式很方便地使數(shù)據(jù)分級聚類的子任務(wù)在Hadoop的PC集群上運行。實驗結(jié)果表明，該方法比傳統(tǒng)用于數(shù)據(jù)聚類的非負矩陣方法具有更好的運行時間與加速比，能夠在可以接受的時間范圍內(nèi)完成電信運營商的大數(shù)據(jù)處理。

關(guān)鍵詞： 云計算； 分級聚類； MapReduce； 非負矩陣分解； 聚類算法； 并行數(shù)據(jù)

中圖分類號： TN911.1?34； TP393.03 文獻標識碼： A 文章編號： 1004?373X（2018）05?0056?05

Abstract： In order to improve the performance of traditional data clustering methods on big data mining application， a parallel data hierarchical clustering algorithm was designed and realized by means of the correlation technologies of cloud computing and non?negative matrix factorization （NMF） method. The MapReduce programming platform is used in the algorithm. The HDFS （Hadoop distributed file system） based on Hadoop is used to store the large?capacity data of telecom operators. The working mechanism and flow of data hierarchical clustering based on MapReduce are described in detail. The master?slave programming mode based on Map and Reduce makes the subtask of data hierarchical clustering operating on PC clusters based on Hadoop easily. The experimental results show that， in comparison with the traditional non?negative matrix method used in data clustering， the proposed method has shorter run time and smaller speedup ratio， and can realize the big data processing of telecom operator within the acceptable time.

Keywords： cloud computing； hierarchical clustering； MapReduce； non?negative matrix factorization； clustering algorithm； parallel data

0 引 言

近年來移動互聯(lián)網(wǎng)與物聯(lián)網(wǎng)的急速發(fā)展積累了大量的數(shù)據(jù)資源，這些海量數(shù)據(jù)中蘊藏著大量可以應(yīng)用于個性化商務(wù)的有效信息[1?3]，然而傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)是主要應(yīng)用于中小規(guī)模數(shù)據(jù)中的信息挖掘，為了從海量數(shù)據(jù)資源中挖掘出有用信息，必須采用新型的數(shù)據(jù)挖掘技術(shù)，其中基于多維數(shù)據(jù)相似性的數(shù)據(jù)聚類作為一種新型數(shù)據(jù)挖掘技術(shù)正好解決上述問題。

非負矩陣分解NMF（Non?negative Matrix Factorization）方法在多維數(shù)據(jù)相似性的數(shù)據(jù)聚類、文本聚類、社交網(wǎng)絡(luò)聚類中都得到了廣泛應(yīng)用，但其串行計算的時間復(fù)雜度較高，很難勝任大數(shù)據(jù)處理任務(wù)。早期在多維數(shù)據(jù)相似性的數(shù)據(jù)聚類并行處理領(lǐng)域中，有集群計算機與共享內(nèi)存計算的方式，還有網(wǎng)格計算、對等計算、廣域分布式計算等模式，這些模型都取得了很好的成果。但是在云計算、大數(shù)據(jù)時代，前期的分布式計算模式對海量的PB級的數(shù)據(jù)處理往往顯得不足[4?5]，所以基于云計算的數(shù)據(jù)分級聚類應(yīng)該得到足夠的重視[6]。因此本文試圖探索利用云計算方式優(yōu)化傳統(tǒng)的基于非負矩陣分解的數(shù)據(jù)相似性聚類方法。

云計算中的MapReduce技術(shù)[7]最早被Google用于大數(shù)據(jù)并行處理，其基本思想是將大數(shù)據(jù)集分解為成百上千的小數(shù)據(jù)集splits，采用Mapper和Reducer形式的類似主?從（Master?Slave）模式的并行處理。這一方法由于可以實現(xiàn)海量數(shù)據(jù)的并行處理，通過PC機就可以實現(xiàn)大型機才能完成的計算任務(wù)，因此近年來得到了廣泛應(yīng)用。

本文以基于非負矩陣分解的高維數(shù)據(jù)相似性聚類算法作為研究對象，以某電信運營商的大容量數(shù)據(jù)作為實驗對象，設(shè)計了一種層次聚類方法并實現(xiàn)了數(shù)據(jù)聚類方法的MapReduce并行化，同時將該算法在Hadoop平臺上進行實驗和評估，最后的實驗結(jié)果驗證了該算法的高效性與可擴展性。

1 預(yù)備知識

1.1 高維數(shù)據(jù)相似性聚類與非負矩陣分解

相似性聚類[8]是基于數(shù)據(jù)在不同維度上的相似程度而對數(shù)據(jù)進行分類，兩個數(shù)據(jù)點是否歸于同一類，判斷它們的相似度如何。當它們之間的相似度大于某一值時，則歸于同一聚類；否則，兩個數(shù)據(jù)點則分屬不同的聚類。endprint

由于實際問題中大規(guī)模數(shù)據(jù)的存在，使得存儲這類大數(shù)據(jù)的矩陣非常龐大，且存放的信息分布不均勻，導(dǎo)致現(xiàn)有方法很難高效快速地處理矩陣存放的數(shù)據(jù)。為了更好地處理這類數(shù)據(jù)，一類有效的方法是對矩陣進行分解，從而使得描述問題的維度大大消減，同時也能夠?qū)?shù)據(jù)進行壓縮和概括。針對這一點，目前已有很多矩陣分解方法，如奇異值分解、獨立成分分析、主成分分析等?；诜秦摼仃嚪纸鈁9]的聚類分析所輸出的分解結(jié)果可以保證其元素非負，代表真實的物理意義，因此近年來得到特別關(guān)注。

基于非負矩陣分解NMF的聚類[10]方法如下：考慮到數(shù)據(jù)集可以表示為一個向量集而每一個向量代表維數(shù)據(jù)點， NMF方法的目的是將劃分為兩個非負低秩矩陣和可通過盡量優(yōu)化如下公式實現(xiàn)：

根據(jù)文獻[10]，可以通過以下的乘法更新規(guī)則得到：

經(jīng)過迭代處理后，得到大小為的網(wǎng)絡(luò)的分割矩陣，其中第行對應(yīng)第個單元在聚類類型中的成員關(guān)系。進一步將標準化，使這樣就對應(yīng)于第個單元屬于第個數(shù)據(jù)聚類的后驗概率。

1.2 MapReduce編程模型

Hadoop是一個分布式系統(tǒng)基礎(chǔ)框架，它的核心是分布式文件系統(tǒng)機制HDFS（Hadoop Distributed File System）和MapReduce的主?從模式（Master?Slave）的編程機制。MapReduce框架由JobTracker和TaskTracker共同組成，它們分別擔任管理節(jié)點和執(zhí)行任務(wù)節(jié)點的角色，這兩個有機結(jié)合，從而實現(xiàn)MapReduce的正常運轉(zhuǎn)，保證任務(wù)的執(zhí)行。

MapReduce數(shù)據(jù)相似性聚類并行處理的工作機制與流程如圖1所示，具體步驟如下：

1） 對輸入的大數(shù)據(jù)文件進行設(shè)置與切片；

2） 主節(jié)點（Master）調(diào)度從屬節(jié)點（Worker）執(zhí)行Map子任務(wù)；

3） 從屬節(jié)點讀取輸入源片段；

4） 從屬節(jié)點執(zhí)行Map子任務(wù)，并將臨時結(jié)果文件保存在本地；

5） 主節(jié)點調(diào)度從節(jié)點執(zhí)行Reduce子任務(wù)，Reduce階段的從屬節(jié)點讀取Map子任務(wù)的輸出文件；

6） 執(zhí)行Reduce子任務(wù)，將最后的結(jié)果保存到HDFS分布式文件系統(tǒng)中。

有了這6個步驟，數(shù)據(jù)分級聚類的編程人員就可以擺脫本身分布式計算的編程細節(jié)，可以使用高級語言在規(guī)定時間內(nèi)完成大規(guī)模的數(shù)據(jù)分級聚類。

另外，要實現(xiàn)本文的并行數(shù)據(jù)聚類算法，必須用到Hadoop的開源實現(xiàn)，目前比較好的是Apache的Hadoop實現(xiàn)，訪問地址為http：//hadoop.apache.org/，Apache的Hadoop基于Java環(huán)境，它實現(xiàn)了HDFS文件系統(tǒng)和MapReduce。用戶只要繼承MapReduceBase，提供分別實現(xiàn)Map和Reduce的兩個類，并注冊Job即可實現(xiàn)自動分布式運行。

2 NMF算法的MapReduce并行化實現(xiàn)

2.1 基于非負矩陣分解的并行式分級聚類

現(xiàn)有的基于相似性的數(shù)據(jù)聚類往往根據(jù)任意兩個高維數(shù)據(jù)在各個維度上的歐幾里德距離的緊密程度將數(shù)據(jù)劃分為幾個不同的聚類，屬于同一聚類的數(shù)據(jù)之間的相似度較高，屬于不同聚類的數(shù)據(jù)之間的相似度相對較低。然而這一方法的局限在于，無法像模塊度算法[11]那樣計算聚類的模塊度；無法對聚類內(nèi)部的相似程度進行排序。

因此，提出基于合適的相似性度量指標來構(gòu)建高維數(shù)據(jù)的相似性矩陣，通過對數(shù)據(jù)集的相似性矩陣進行非負矩陣分解來聚類相似程度較高的數(shù)據(jù)集合，將新的聚類視為新的數(shù)據(jù)點，從而在縮小數(shù)據(jù)規(guī)模的同時增加數(shù)據(jù)的維度，然后重新計算當前數(shù)據(jù)的相似性矩陣進行非負矩陣分解，反復(fù)迭代，直至得到一個較優(yōu)的聚類序列。在這一計算過程中，計算量較大的階段是反復(fù)計算數(shù)據(jù)點彼此之間的相似程度。由于數(shù)據(jù)是多維的，其相似程度往往需要用給定維度數(shù)值的歐幾里德距離或余弦相似性來描述，在重構(gòu)相似性矩陣時的計算量非常大，因此，本文在此階段借用MapReduce分布式編程模型的優(yōu)勢，極大地提高了計算效率。

2.2 基于MapReduce的并行數(shù)據(jù)處理

首先是大數(shù)據(jù)存儲的問題，可以參考利用HDFS來管理這些海量數(shù)據(jù)。HDFS的設(shè)計本質(zhì)上是為了大量的數(shù)據(jù)能橫跨成百上千臺機器，但是看到的是一個文件系統(tǒng)而不是很多文件系統(tǒng)，對用戶透明。例如，MapReduce系統(tǒng)要獲取/hdfs/tmp/file1的數(shù)據(jù)，程序設(shè)計中引用的是一個文件路徑，但是實際的數(shù)據(jù)存放在很多不同的機器上。HDFS為用戶管理這些海量數(shù)據(jù)，并通過MapReduce編程模式讓其在Hadoop集群上分布運行[12]。

考慮到影響分級聚類算法性能的主要因素是如何計算高維數(shù)據(jù)彼此之間的相似性，由于該相似性需要同時度量單一數(shù)據(jù)點在多個數(shù)據(jù)維度上與其他所有數(shù)據(jù)點的差異，因此，很適合使用MapReduce進行計算。給定迭代次數(shù)，即分級次。級聚類算法表述如下：

步驟1： 將初始聚類序列分割為給定的個片段，對應(yīng)分配到個Map任務(wù)，基于給定指標計算聚類上下文的相似性，利用Reduce框架輸出各聚類對之間的相似性集合，重構(gòu)當前聚類之間的相似性矩陣；

步驟2：輸入上一級聚類的相似性矩陣，基于非負矩陣分解輸出當前對應(yīng)聚類ID的歸屬度。重構(gòu)當前級別下的聚類序列，輸出當前級別下的聚類集合；

步驟3： 重構(gòu)當前聚類的上下文。重復(fù)步驟1， 步驟2共次；

步驟4：輸出最終分級聚類結(jié)果。

整個算法的框架圖如圖2所示。

利用本文非負矩陣分解的并行數(shù)據(jù)處理中Map函數(shù)相應(yīng)的偽代碼如下：

Input： text key，vector value

Output：context context

Begin

1： for i=0 to n （cluster sequence） do

2： t=findCatalog（i）；

3： for all k（* textfile） do

4： distance=cosinedistance（k，ji）；

5： context， write（key， vector（t，Distance））；

6： end for

7： end for

End

Reduce函數(shù)相應(yīng)的偽代碼如下：

Input： text key， vector value

Output： text key， vector value， context context

Begin

1： for all key and value do

2： array list （vector（t，value））；

3： sort（array list）；

4： new arraylist result

5： if k

6： for i=0 to k do

7： result， add（key，arraylist.get（i））；

8： else

9： system.out，println（“no sufficient training smaples”）

10： context.write（key，tradition KNN（result））；

11： end for

12： end if

End

在MapReduce編程模型中，HDFS將大數(shù)據(jù)分割成若干blocks，然后存儲在不同的節(jié)點上。每個節(jié)點根據(jù)Map函數(shù)指定的操作在本地完成相應(yīng)的功能。

3 實驗結(jié)果與討論

3.1 實驗數(shù)據(jù)的選取

作為積累大數(shù)據(jù)的典型行業(yè)，電信行業(yè)積累了大量的手機用戶行為數(shù)據(jù)，數(shù)據(jù)里包括用戶撥出電話的基站信息、通話時間、通話時長等豐富信息。這些數(shù)據(jù)可以用來研究用戶之間形成的社交網(wǎng)；另一方面，由于這些行為數(shù)據(jù)具有地理上下文，因此，也可以基于網(wǎng)絡(luò)理論結(jié)合地理屬性研究城市中不同區(qū)域之間的關(guān)系與功能。

然而，若將區(qū)域視為網(wǎng)絡(luò)中的點，則區(qū)域覆蓋的基站的數(shù)據(jù)容量使得該點擁有極高的數(shù)據(jù)維度，具有上十萬用戶、上百萬的通話記錄數(shù)，容量都是PB級的。如果用數(shù)據(jù)庫連接查詢以及普通的計算平臺來計算上述地理空間網(wǎng)絡(luò)，效率會比較低，甚至難以接受超長的時間，所以本文提取上述電信運營商數(shù)據(jù)作為實驗環(huán)境，構(gòu)造空間網(wǎng)絡(luò)關(guān)系的平臺是Hadoop集群。

本文搭建的集群中共有8個節(jié)點：1個Master節(jié)點和7個Slave節(jié)點，所有節(jié)點的硬件配置如下：CPU型號 為Intel Xeon E5 3.5 GHz； 內(nèi)存設(shè)為 8 GB。硬盤容量設(shè)為1 TB； 這些節(jié)點之間通過局域網(wǎng)內(nèi)的100M網(wǎng)卡連接，具體信息如表1所示。

8個節(jié)點上均是RedHat系統(tǒng)，其中Master機器主要配置NameNode和JobTracker，NameNode負責對文件系統(tǒng)的命名空間進行管理，JobTracker負責任務(wù)的調(diào)度和分發(fā)。7個Slave機器主要配置DataNode和TaskTracker，DataNode負責對數(shù)據(jù)進行分布式存儲，TaskTracker主要負責接收JobTracker分發(fā)的任務(wù)并執(zhí)行具體的數(shù)據(jù)處理任務(wù)。

3.2 實驗結(jié)果分析

利用某電信運營商的數(shù)據(jù)，表2列出了利用本文的數(shù)據(jù)聚類分析并行處理后的計算結(jié)果，從實驗結(jié)果可以看出，算法的測試結(jié)果符合預(yù)想的情況，在算法的步驟1階段，需要的時間比較長，差不多4 h，半個工作日內(nèi)能夠完成，并行處理基本能滿足實際大數(shù)據(jù)處理的需求，然而傳統(tǒng)的單機條件下需要30多個小時。在步驟3的階段比較短，雖然并行處理的時間超過了單機（因為有了通信開銷），但是相對于算法的整個過程是不影響速度的。

以上是并行處理與串行單機的比較結(jié)果，步驟1～步驟3一共只要4個多小時，而串行單機（一個節(jié)點）要30多個小時。但是結(jié)果是與串行的比較，而不是并行單節(jié)點的比較（接下來看到一個Master，一個Slave共需要的時間是50 h左右）。

接著同時測試了集群配置不同節(jié)點數(shù)量（2～8個，都只有1個Master，1～7個Slave）條件下算法的處理性能。圖3表明整個算法（步驟1～步驟3）隨著節(jié)點數(shù)的增加而運行時間相應(yīng)減少。

加速比是衡量一個系統(tǒng)擴展性優(yōu)劣的主要指標，其表達式為：

從圖3中可看出，整個數(shù)據(jù)聚類算法的時間隨著節(jié)點的增加而急劇減少。

圖4為聚類算法的可擴展性測試結(jié)果。

從圖4中可看出，多臺計算機能夠很好地縮短所需時間，這說明MapReduce在處理數(shù)據(jù)聚類分析算法上具有較好的加速比，當節(jié)點數(shù)更多時，這種性能優(yōu)勢將更加明顯。在一定的規(guī)模范圍內(nèi)，系統(tǒng)具有很好的可擴展性。

4 結(jié) 論

本文提出云計算環(huán)境下基于相似性高維數(shù)據(jù)的聚類算法的并行化實現(xiàn)。根據(jù)非負矩陣分解和聚類方法的特點設(shè)計了Map和Reduce函數(shù)，并將該算法在Hadoop平臺下進行性能測試。實驗結(jié)果表明，基于MapReduce的算法具有良好的擴展性和加速比。在數(shù)據(jù)量急劇增長的大數(shù)據(jù)時代，在云計算平臺上實現(xiàn)基于MapReduce的數(shù)據(jù)挖掘算法具有重要的意義。

注：本文通訊作者為徐勝超。

參考文獻

[1] ZHENG Y， CAPRA L， WOLFSON O， et al. Urban computing： concepts， methodologies， and applications [J]. ACM transactions on intelligent systems and technology， 2014（1）： 1?9.

[2] 李應(yīng)安.基于MapReduce的聚類算法的并行化研究[D].廣州：中山大學(xué)，2011.

LI Y A. Research on parallelization of clustering algorithm based on MapReduce [D]. Guangzhou： Sun Yat?sen University， 2011.

[3] 曹澤文，周姚.基于MapReduce的JP算法設(shè)計與實現(xiàn)[J].計算機工程，2012，38（24）：14?16.

CAO Z W， ZHOU Y. Design and implementation of JP algorithm based on MapReduce [J]. Computer engineering， 2012， 38（24）： 14?16.

[4] 楊燕，王全根，黃波.蟻群聚類算法的并行化設(shè)計與實現(xiàn)[J].控制工程，2013，20（3）：411?414.

YANG Yan， WANG Quangen， HUANG Bo. Parallel design and implementation of ant colony clustering algorithm [J]. Control engineering of China， 2013， 20（3）： 411?414.

[5] 楊慧中，董陶，陶洪峰.基于改進K?means聚類算法的組合模型建模[J].控制工程，2013，20（2）：201?203.

YANG Huizhong， DONG Tao， TAO Hongfeng. Combination model based on improved K?means clustering algorithm [J]. Control engineering of China， 2013， 20（2）： 201?203.

[6] 李歡，劉鋒，朱二周.基于改進K?means算法的海量數(shù)據(jù)分析技術(shù)研究[J].微電子學(xué)與計算機，2016，33（5）：52?57.

LI Huan， LIU Feng， ZHU Erzhou. Research of an improved K?means algorithm for analyzing mass data [J]. Microelectronics & computer， 2016， 33（5）： 52?57.

[7] LI F， OOI B C， ?ZSU M T， et al. Distributed data management using MapReduce [J]. ACM computing surveys， 2014， 46（3）： 31.

[8] 吳詩極，李川，唐常杰.面向大規(guī)模信息網(wǎng)絡(luò)的高效自適應(yīng)聚類算法[J].計算機科學(xué)與探索，2014，8（4）：406?416.

WU Shiji， LI Chuan， TANG Changjie. Efficient adaptive clustering algorithm for large scale information network [J]. Journal of frontiers of computer science & technology， 2014， 8（4）： 406?416.

[9] 任重魯，李金明.非負矩陣分解在微陣列數(shù)據(jù)分類和聚類發(fā)現(xiàn)中的應(yīng)用[J].計算機工程與科學(xué)，2014，36（7）：1389?1397.

REN Zhonglu， LI Jinming. Application of non?negative matrix factorization in microarray data classification and clustering discovery [J]. Computer engineering and science， 2014， 36（7）： 1389?1397.

[10] 徐森，盧志茂，顧國昌.結(jié)合K均值和非負矩陣分解集成文本聚類算法[J].吉林大學(xué)學(xué)報（工學(xué)版），2011，41（4）：1077?1082.

XU Sen， LU Zhimao， GU Guochang. Integrating K?means and non?negative matrix factorization to ensemble document clustering [J]. Journal of Jilin University （engineering and technology edition）， 2011， 41（4）： 1077?1082.

[11] 羅明偉，姚宏亮，李俊照，等.一種基于節(jié)點相異度的社團層次劃分算法[J].計算機工程，2014，40（1）：275?279.

LUO Mingwei， YAO Hongliang， LI Junzhao， et al. A hierarchical division algorithm for community based on node dissi?milarity [J]. Computer engineering， 2014， 40（1）： 275?279.

[12] Hadoop. Hadoop Open source Web site 2016 [EB/OL]. [2016?10?23]. http：//hadoop.apache.org/.endprint