基于云計算與非負矩陣分解的數據分級聚類

趙艷萍+徐勝超

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

關鍵詞： 云計算； 分級聚類； MapReduce； 非負矩陣分解； 聚類算法； 并行數據

中圖分類號： 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 引 言

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

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

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

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

1 預備知識

1.1 高維數據相似性聚類與非負矩陣分解

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

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

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

根據文獻[10]，可以通過以下的乘法更新規則得到：

經過迭代處理后，得到大小為的網絡的分割矩陣，其中第行對應第個單元在聚類類型中的成員關系。進一步將標準化，使這樣就對應于第個單元屬于第個數據聚類的后驗概率。

1.2 MapReduce編程模型

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

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

1） 對輸入的大數據文件進行設置與切片；

2） 主節點（Master）調度從屬節點（Worker）執行Map子任務；

3） 從屬節點讀取輸入源片段；

4） 從屬節點執行Map子任務，并將臨時結果文件保存在本地；

5） 主節點調度從節點執行Reduce子任務，Reduce階段的從屬節點讀取Map子任務的輸出文件；

6） 執行Reduce子任務，將最后的結果保存到HDFS分布式文件系統中。

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

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

2 NMF算法的MapReduce并行化實現

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

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

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

2.2 基于MapReduce的并行數據處理

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

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

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

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

步驟3： 重構當前聚類的上下文。重復步驟1， 步驟2共次；

步驟4：輸出最終分級聚類結果。

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

利用本文非負矩陣分解的并行數據處理中Map函數相應的偽代碼如下：

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函數相應的偽代碼如下：

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將大數據分割成若干blocks，然后存儲在不同的節點上。每個節點根據Map函數指定的操作在本地完成相應的功能。

3 實驗結果與討論

3.1 實驗數據的選取

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

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

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

8個節點上均是RedHat系統，其中Master機器主要配置NameNode和JobTracker，NameNode負責對文件系統的命名空間進行管理，JobTracker負責任務的調度和分發。7個Slave機器主要配置DataNode和TaskTracker，DataNode負責對數據進行分布式存儲，TaskTracker主要負責接收JobTracker分發的任務并執行具體的數據處理任務。

3.2 實驗結果分析

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

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

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

加速比是衡量一個系統擴展性優劣的主要指標，其表達式為：

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

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

從圖4中可看出，多臺計算機能夠很好地縮短所需時間，這說明MapReduce在處理數據聚類分析算法上具有較好的加速比，當節點數更多時，這種性能優勢將更加明顯。在一定的規模范圍內，系統具有很好的可擴展性。

4 結 論

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

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

參考文獻

[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] 李應安.基于MapReduce的聚類算法的并行化研究[D].廣州：中山大學，2011.

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

[3] 曹澤文，周姚.基于MapReduce的JP算法設計與實現[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] 楊燕，王全根，黃波.蟻群聚類算法的并行化設計與實現[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算法的海量數據分析技術研究[J].微電子學與計算機，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] 吳詩極，李川，唐常杰.面向大規模信息網絡的高效自適應聚類算法[J].計算機科學與探索，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] 任重魯，李金明.非負矩陣分解在微陣列數據分類和聚類發現中的應用[J].計算機工程與科學，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] 徐森，盧志茂，顧國昌.結合K均值和非負矩陣分解集成文本聚類算法[J].吉林大學學報（工學版），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] 羅明偉，姚宏亮，李俊照，等.一種基于節點相異度的社團層次劃分算法[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