基于仿射傳播聚類算法的大數據并行化分析研究

汪儉華，陳守維

（黔東南州大數據發展中心，貴州凱里 556000）

大數據最早是由IBM 公司于2010 年提出的，其具有海量數據、高速響應、多樣化、價值密度低等特性[1]，如何將海量的原始數據轉換成為有用的數據是當下的熱點問題。在這些海量數據內部都包含了具有一定規律的社團結構，針對這一特性，該研究利用仿射傳播聚類算法遷移到云平臺上實現并行化來改進對海量數據的處理效率[2-3]，提升用戶體驗。

1 云計算技術

1.1 社團結構

社團結構，是網絡中的一個共性特征，指網絡中的頂點可以形成分組，每個組內頂點之間的相互連接緊密，而不同組間的頂點之間的相互連接則相對稀疏。在海量數據網絡中，對社團結構的研究分析可以優化在并行計算中分配任務的合理性，從而減少各個計算節點之間的通信成本，提高大規模計算的效率。目前用于劃分網絡中社團結構的算法主要包括基于圖論、基于模塊度優化、基于動態、基于重疊社團4 類算法。

以上幾類發現算法中的典型代表是K-means 法（劃分類聚算法），但都存在復雜度較高，無法處理海量數據網絡，獲得結果不穩定等問題[4]。通過利用云計算技術實現仿射傳播聚類算法的并行化，能夠有效處理海量數據網絡。

1.2 Hadoop系統

Hadoop 系統作為云計算技術的基礎設施，可以部署服務器集群在大量廉價的硬件設備上，系統的底層用于對服務器集群進行管理，系統的上層能夠十分便捷地構建應用，可以動態地調整分布式節點[5-8]。Hadoop 系統由HDFS、MapReduce 和HBase 3 個部分構成，HDFS 用于在多臺設備上保存和復制文件，MapReduce 主要是運行并行程序任務，HBase 是一個開源的分布式儲存數據庫。

HDFS（Hadoop Distributed File System）是一種具有高度容錯性的分布式文件存儲系統，具有master/slave 的結構，Name node 是主節點，Data node 是從節點[9]。前者用于維護存儲在HDFS 中的數據，包含文件的block 及其Data Node 信息；后者將HDFS 中的文件實際存儲在本地。

MapReduce 是一種基于集群進行海量數據并行計算的模型，可以便捷地實現對并行計算的開發及應用[10]。其主要由Map 和Reduce 操作構成，Map 操作用于處理一個Key 并得到一組中間結果Key/Value值，Reduce 操作則利用得到的中間結果來處理最終的結果。

HBase 是一個開源的分布式數據庫，其原理與Google 的BigTable 相似，運行在HDFS 上，為Hadoop提供BigTable 服務，能夠部署大規模結構化儲存群集到廉價的設備上[11-13]。

1.3 Mahout學習庫

Apache Mahout 是一款開源、可擴展的機器學習庫，包含許多實現、集群、分類和進化程序，可以利用Hadoop 快速有效地擴展到云平臺中[14-15]。

2 仿射傳播聚類算法并行化研究

2.1 仿射傳播聚類算法

仿射傳播聚類算法利用各個數據點傳播消息，可以自動發現聚類中心，從而實現數據點的自動聚類。仿射傳播聚類算法較傳統的類聚算法，不需要對類聚的類別、類聚中心進行預設，每一個數據點都視為潛在的聚類中心，其類聚中心是在迭代計算的過程中自動優化結果生成的，所得到的類聚結果更準確[16]。

1）仿射傳播聚類的輸入首先需要計算相似度矩陣，該矩陣由節點之間的相似度組成，在這個矩陣中的每個元素s(i,j)表示節點i與j之間的相似度，也定義了節點j作為i的聚類中心的適配度。其計算公式如下：

Xik表示節點之間的鄰接矩陣X第i行第k列的元素，n表示矩陣中節點的總數。

與傳統的聚類算法需預設類簇的個數不同，仿射傳播將一對多節點k賦值為s(k,k)，該值反映相似矩陣s對角線上第k行的元素，這些對角線上的值稱為傾向值，其與第k個節點作為聚類中心，呈正相關[17]。仿射傳播中所有的節點作為潛在聚類中心的概率均相同，使所有節點傾向值都應相同，“傾向值”的選擇與最后獲得類簇的數量呈負相關。

2）仿射傳播聚類算法在每個節點之間傳播吸引值和歸屬值。

吸引值是從節點i傳播到作為潛在聚類中心的節點k的信息，r(i,k)為節點k對于節點i的吸引值，該值是節點k與其他節點k′相互競爭后，作為節點i的聚類中心的適配程度。r(i,k)需要引入節點i對其他潛在聚類中心節點k′的歸屬值a(i,k′)來獲得，其計算式如下:

歸屬值是從潛在的類聚中心節點k傳遞到節點i的信息，a(i,k)為節點i對節點k的歸屬值，該值反映的是節點i選擇節點k作為其類聚中心的適配程度，表示的是將潛在類聚中心的節點k與其他節點i′的吸引值進行比較的結果，其計算式如下:

基于非負的其他節點與候選節點k的吸引值的計算結果用a(k,k)定義，該值反映了節點k作為潛在類聚中心的能力，其計算式如下:

仿射傳播聚類算法流程如下：

Step.1 初始化，將所有節點的a(i,k)全部設置為零，輸入相似矩陣s，其中，s(i,k)是節點i與節點k之間的相似值，而s(k,k)則是k點作為潛在類聚中心的傾向值。

Step.2 計算獲得節點k對于節點i的吸引值：

Step.3 計算節點i對于節點k的歸屬值：

Step.4 通過迭代Step.2、Step.3，直至得到計算結果，此時得到的最優結果就是類聚中心。

2.2 利用MapReduce實現并行化

仿射傳播聚類首先需要獲得相似度矩陣，然后進行多次迭代計算矩陣值，在此過程中要多次調用mapreduce job，單次迭代過程包括獲得吸引值、計算歸屬值和對歸屬值矩陣的行列文件進行轉置，當迭代過程停止或聚類中心穩定不再變化后，發現聚類中心并劃分節點[18]。

3 實驗分析

3.1 實驗環境搭建

實驗平臺：一臺Master 操作系統為Ubuntu 16.04 LTS 64 位、Java SE 11.0.2（LTS）、CPU 為Intel Xeon E-2699 v4 2.20 GHz、內存容量為64 GB 3 200 MHz、硬盤容量為4 TB；4 臺Slave 操作系統為Windows 2012 R2、CPU 為Intel core i5-4590 3.30 GHz、內存容量為16 GB 3 200 MHz、硬盤容量為1 TB。虛擬機設置：操作系統為Ubuntu 16.04 LTS 64 位、Java SE 11.0.2（LTS）、CPU 為Intel core i5-4590 3.30 GHz、內存容量為8 GB 3 200 MHz、硬盤容量為1 TB。

實驗數據采用美國Minnesota 大學計算機學院GroupLens 項目組創建的MovieLens 數據，該數據由3萬名用戶對3.5 萬部電影做出的2 500 萬個評分以及50 萬個標簽組成，數據版本為4.4.1。

3.2 算法模型設計

該實驗以基于仿射傳播聚類算法為例，對MovieLens 數據進行資源調度實驗，并與基于劃分類聚算法進行比較，請求服務分別為100、500、1 000、2 000、4 000 次，運行時間實驗對比如圖1 所示，所需內存實驗對比如圖2 所示，CPU 利用率實驗對比如圖3 所示。

圖1 運行時間實驗對比圖

圖2 所需內存實驗對比圖

圖3 CPU利用率實驗對比圖

從上述實驗可知劃分聚類算法分析過程中，隨著實驗規模的增大而導致效率低、資源占用率高、運行時間長、所需內存多和占用CPU 率高等缺點，這是因為劃分聚類算法需要先選擇一個聚類中心，如果聚類中心選擇不恰當，則會影響分析過程。基于仿射傳播聚類算法的并行化分析，使用該算法不需要先選擇聚類中心，減少了不必要的操作，使得運行時間和資源占用率大幅得到改善。

4 結論

該文在基于仿射傳播聚類算法的基礎上搭建了MapReduce 并行化平臺，詳細論述了分析中涉及的關鍵技術。通過對比實驗來進行評估，仿射傳播聚類算法并行化后具有節省運行時間、降低內存使用量和CPU 利用率等優勢，具有較高的實用性。下一步研究工作是將該算法進行可視化應用，以方便用戶的使用，帶來更佳的體驗。