汪儉華，陳守維

（黔東南州大數(shù)據(jù)發(fā)展中心，貴州凱里 556000）

大數(shù)據(jù)最早是由IBM 公司于2010 年提出的，其具有海量數(shù)據(jù)、高速響應(yīng)、多樣化、價(jià)值密度低等特性[1]，如何將海量的原始數(shù)據(jù)轉(zhuǎn)換成為有用的數(shù)據(jù)是當(dāng)下的熱點(diǎn)問(wèn)題。在這些海量數(shù)據(jù)內(nèi)部都包含了具有一定規(guī)律的社團(tuán)結(jié)構(gòu)，針對(duì)這一特性，該研究利用仿射傳播聚類算法遷移到云平臺(tái)上實(shí)現(xiàn)并行化來(lái)改進(jìn)對(duì)海量數(shù)據(jù)的處理效率[2-3]，提升用戶體驗(yàn)。

1 云計(jì)算技術(shù)

1.1 社團(tuán)結(jié)構(gòu)

社團(tuán)結(jié)構(gòu)，是網(wǎng)絡(luò)中的一個(gè)共性特征，指網(wǎng)絡(luò)中的頂點(diǎn)可以形成分組，每個(gè)組內(nèi)頂點(diǎn)之間的相互連接緊密，而不同組間的頂點(diǎn)之間的相互連接則相對(duì)稀疏。在海量數(shù)據(jù)網(wǎng)絡(luò)中，對(duì)社團(tuán)結(jié)構(gòu)的研究分析可以優(yōu)化在并行計(jì)算中分配任務(wù)的合理性，從而減少各個(gè)計(jì)算節(jié)點(diǎn)之間的通信成本，提高大規(guī)模計(jì)算的效率。目前用于劃分網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的算法主要包括基于圖論、基于模塊度優(yōu)化、基于動(dòng)態(tài)、基于重疊社團(tuán)4 類算法。

以上幾類發(fā)現(xiàn)算法中的典型代表是K-means 法（劃分類聚算法），但都存在復(fù)雜度較高，無(wú)法處理海量數(shù)據(jù)網(wǎng)絡(luò)，獲得結(jié)果不穩(wěn)定等問(wèn)題[4]。通過(guò)利用云計(jì)算技術(shù)實(shí)現(xiàn)仿射傳播聚類算法的并行化，能夠有效處理海量數(shù)據(jù)網(wǎng)絡(luò)。

1.2 Hadoop系統(tǒng)

Hadoop 系統(tǒng)作為云計(jì)算技術(shù)的基礎(chǔ)設(shè)施，可以部署服務(wù)器集群在大量廉價(jià)的硬件設(shè)備上，系統(tǒng)的底層用于對(duì)服務(wù)器集群進(jìn)行管理，系統(tǒng)的上層能夠十分便捷地構(gòu)建應(yīng)用，可以動(dòng)態(tài)地調(diào)整分布式節(jié)點(diǎn)[5-8]。Hadoop 系統(tǒng)由HDFS、MapReduce 和HBase 3 個(gè)部分構(gòu)成，HDFS 用于在多臺(tái)設(shè)備上保存和復(fù)制文件，MapReduce 主要是運(yùn)行并行程序任務(wù)，HBase 是一個(gè)開源的分布式儲(chǔ)存數(shù)據(jù)庫(kù)。

HDFS（Hadoop Distributed File System）是一種具有高度容錯(cuò)性的分布式文件存儲(chǔ)系統(tǒng)，具有master/slave 的結(jié)構(gòu)，Name node 是主節(jié)點(diǎn)，Data node 是從節(jié)點(diǎn)[9]。前者用于維護(hù)存儲(chǔ)在HDFS 中的數(shù)據(jù)，包含文件的block 及其Data Node 信息；后者將HDFS 中的文件實(shí)際存儲(chǔ)在本地。

MapReduce 是一種基于集群進(jìn)行海量數(shù)據(jù)并行計(jì)算的模型，可以便捷地實(shí)現(xiàn)對(duì)并行計(jì)算的開發(fā)及應(yīng)用[10]。其主要由Map 和Reduce 操作構(gòu)成，Map 操作用于處理一個(gè)Key 并得到一組中間結(jié)果Key/Value值，Reduce 操作則利用得到的中間結(jié)果來(lái)處理最終的結(jié)果。

HBase 是一個(gè)開源的分布式數(shù)據(jù)庫(kù)，其原理與Google 的BigTable 相似，運(yùn)行在HDFS 上，為Hadoop提供BigTable 服務(wù)，能夠部署大規(guī)模結(jié)構(gòu)化儲(chǔ)存群集到廉價(jià)的設(shè)備上[11-13]。

1.3 Mahout學(xué)習(xí)庫(kù)

Apache Mahout 是一款開源、可擴(kuò)展的機(jī)器學(xué)習(xí)庫(kù)，包含許多實(shí)現(xiàn)、集群、分類和進(jìn)化程序，可以利用Hadoop 快速有效地?cái)U(kuò)展到云平臺(tái)中[14-15]。

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

2.1 仿射傳播聚類算法

仿射傳播聚類算法利用各個(gè)數(shù)據(jù)點(diǎn)傳播消息，可以自動(dòng)發(fā)現(xiàn)聚類中心，從而實(shí)現(xiàn)數(shù)據(jù)點(diǎn)的自動(dòng)聚類。仿射傳播聚類算法較傳統(tǒng)的類聚算法，不需要對(duì)類聚的類別、類聚中心進(jìn)行預(yù)設(shè)，每一個(gè)數(shù)據(jù)點(diǎn)都視為潛在的聚類中心，其類聚中心是在迭代計(jì)算的過(guò)程中自動(dòng)優(yōu)化結(jié)果生成的，所得到的類聚結(jié)果更準(zhǔn)確[16]。

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

Xik表示節(jié)點(diǎn)之間的鄰接矩陣X第i行第k列的元素，n表示矩陣中節(jié)點(diǎn)的總數(shù)。

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

2）仿射傳播聚類算法在每個(gè)節(jié)點(diǎn)之間傳播吸引值和歸屬值。

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

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

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

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

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

Step.2 計(jì)算獲得節(jié)點(diǎn)k對(duì)于節(jié)點(diǎn)i的吸引值：

Step.3 計(jì)算節(jié)點(diǎn)i對(duì)于節(jié)點(diǎn)k的歸屬值：

Step.4 通過(guò)迭代Step.2、Step.3，直至得到計(jì)算結(jié)果，此時(shí)得到的最優(yōu)結(jié)果就是類聚中心。

2.2 利用MapReduce實(shí)現(xiàn)并行化

仿射傳播聚類首先需要獲得相似度矩陣，然后進(jìn)行多次迭代計(jì)算矩陣值，在此過(guò)程中要多次調(diào)用mapreduce job，單次迭代過(guò)程包括獲得吸引值、計(jì)算歸屬值和對(duì)歸屬值矩陣的行列文件進(jìn)行轉(zhuǎn)置，當(dāng)?shù)^(guò)程停止或聚類中心穩(wěn)定不再變化后，發(fā)現(xiàn)聚類中心并劃分節(jié)點(diǎn)[18]。

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

3.1 實(shí)驗(yàn)環(huán)境搭建

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

實(shí)驗(yàn)數(shù)據(jù)采用美國(guó)Minnesota 大學(xué)計(jì)算機(jī)學(xué)院GroupLens 項(xiàng)目組創(chuàng)建的MovieLens 數(shù)據(jù)，該數(shù)據(jù)由3萬(wàn)名用戶對(duì)3.5 萬(wàn)部電影做出的2 500 萬(wàn)個(gè)評(píng)分以及50 萬(wàn)個(gè)標(biāo)簽組成，數(shù)據(jù)版本為4.4.1。

3.2 算法模型設(shè)計(jì)

該實(shí)驗(yàn)以基于仿射傳播聚類算法為例，對(duì)MovieLens 數(shù)據(jù)進(jìn)行資源調(diào)度實(shí)驗(yàn)，并與基于劃分類聚算法進(jìn)行比較，請(qǐng)求服務(wù)分別為100、500、1 000、2 000、4 000 次，運(yùn)行時(shí)間實(shí)驗(yàn)對(duì)比如圖1 所示，所需內(nèi)存實(shí)驗(yàn)對(duì)比如圖2 所示，CPU 利用率實(shí)驗(yàn)對(duì)比如圖3 所示。

圖1 運(yùn)行時(shí)間實(shí)驗(yàn)對(duì)比圖

圖2 所需內(nèi)存實(shí)驗(yàn)對(duì)比圖

圖3 CPU利用率實(shí)驗(yàn)對(duì)比圖

從上述實(shí)驗(yàn)可知?jiǎng)澐志垲愃惴ǚ治鲞^(guò)程中，隨著實(shí)驗(yàn)規(guī)模的增大而導(dǎo)致效率低、資源占用率高、運(yùn)行時(shí)間長(zhǎng)、所需內(nèi)存多和占用CPU 率高等缺點(diǎn)，這是因?yàn)閯澐志垲愃惴ㄐ枰冗x擇一個(gè)聚類中心，如果聚類中心選擇不恰當(dāng)，則會(huì)影響分析過(guò)程?；诜律鋫鞑ゾ垲愃惴ǖ牟⑿谢治?，使用該算法不需要先選擇聚類中心，減少了不必要的操作，使得運(yùn)行時(shí)間和資源占用率大幅得到改善。

4 結(jié)論

該文在基于仿射傳播聚類算法的基礎(chǔ)上搭建了MapReduce 并行化平臺(tái)，詳細(xì)論述了分析中涉及的關(guān)鍵技術(shù)。通過(guò)對(duì)比實(shí)驗(yàn)來(lái)進(jìn)行評(píng)估，仿射傳播聚類算法并行化后具有節(jié)省運(yùn)行時(shí)間、降低內(nèi)存使用量和CPU 利用率等優(yōu)勢(shì)，具有較高的實(shí)用性。下一步研究工作是將該算法進(jìn)行可視化應(yīng)用，以方便用戶的使用，帶來(lái)更佳的體驗(yàn)。