劉娟娟　丁嘉寧

1(天津天獅學(xué)院信息與自動(dòng)化學(xué)院　天津 301700)

2(天津大學(xué)港口與海洋工程天津市重點(diǎn)實(shí)驗(yàn)室　天津 300072)

3(軍事交通運(yùn)輸研究所　天津 300161)

?

基于分布式集群環(huán)境的圖聚類信息高效處理方案

劉娟娟1丁嘉寧2,3

1(天津天獅學(xué)院信息與自動(dòng)化學(xué)院天津 301700)

2(天津大學(xué)港口與海洋工程天津市重點(diǎn)實(shí)驗(yàn)室天津 300072)

3(軍事交通運(yùn)輸研究所天津 300161)

摘要針對(duì)人工智能領(lǐng)域圖聚類數(shù)據(jù)分析與處理能力無法適應(yīng)于日益復(fù)雜的分布式集群環(huán)境等問題，設(shè)計(jì)出一種基于并行計(jì)算的高效率圖聚類信息處理方案。通過對(duì)Minhash算法以MapReduce架構(gòu)理論進(jìn)行改進(jìn)，使其實(shí)現(xiàn)對(duì)數(shù)據(jù)的并行化分析處理，以確保其能夠在日益復(fù)雜的分布式集群計(jì)算環(huán)境下高效處理圖聚類數(shù)據(jù)信息。通過相關(guān)實(shí)驗(yàn)表明，該方案不僅可行，而且能夠?qū)D聚類數(shù)據(jù)信息進(jìn)行快速稀疏化處理，具有一定的高效性。

關(guān)鍵詞人工智能數(shù)據(jù)挖掘MapReduce圖聚類Minhash

EFFICIENT GRAPH CLUSTERING INFORMATION PROCESSING SCHEME BASED ON DISTRIBUTED CLUSTER ENVIRONMENT

Liu Juanjuan1Ding Jianing2,3

1(College of Information and Automation,Tianshi College,Tianjin 301700,China)2(Key Lab of Harbor and Ocean Engineering of Tianjin,Tianjin University,Tianjin 300072,China)3(Military Transportation Institute of the General Logistics Department,Tianjin 300161,China)

AbstractIn order to solve the problem that the analysing and processing abilities of graph clustering data in artificial intelligence field can’t adapt to the increasingly complex distributed cluster environment, we design a parallel computing-based efficient graph clustering information processing scheme. In this scheme, the Minhash algorithm is improved based on MapReduce framework theory to enable it to achieve the paralleled analyses and processing on the data, so as to guarantee it being able to efficiently process graph clustering data information in increasingly complex distributed cluster environment. It is indicated by related experiment that this scheme is more than feasible, it can also quickly carry out sparseness processing on graph clustering data information, and has certain high efficiency.

KeywordsArtificial intelligenceData miningMapReduceGraph clusteringMinhash

0引言

網(wǎng)絡(luò)交互體系變得越來越復(fù)雜，將其建模成圖模型[1]是其必然的趨勢。在這種圖模型里面，各結(jié)點(diǎn)主要用來描述對(duì)象實(shí)體，而各邊主要是描述對(duì)象實(shí)體的關(guān)系。例如社交網(wǎng)絡(luò)體系即屬于無向圖模型結(jié)構(gòu)的范疇，各結(jié)點(diǎn)所指代的內(nèi)容為社交個(gè)體或群體，各邊指代社交個(gè)體或者群體間的關(guān)聯(lián)，主要包括朋友、同事等[2]?，F(xiàn)階段，伴隨信息技術(shù)和網(wǎng)絡(luò)的日益發(fā)展，尤其是Web3.0網(wǎng)絡(luò)的問世，各種虛擬網(wǎng)絡(luò)應(yīng)用產(chǎn)品在實(shí)踐中得到普及，例如微博等，其圖數(shù)據(jù)信息的處理量不斷增加，形成了海量圖數(shù)據(jù)信息，從而使圖數(shù)據(jù)挖掘與分析應(yīng)用能力面臨一系列非常嚴(yán)峻的挑戰(zhàn)[3-5]。

作為圖數(shù)據(jù)挖掘與分析應(yīng)用的重要作用之一，圖聚類主要根據(jù)聚簇對(duì)圖模型中的各結(jié)點(diǎn)實(shí)施分類操作，同時(shí)增加同類聚簇圖結(jié)點(diǎn)對(duì)象實(shí)體的關(guān)聯(lián)性，減小異類的關(guān)聯(lián)性。現(xiàn)階段，圖聚類在實(shí)踐中已經(jīng)普及，如交通運(yùn)輸規(guī)劃分析等。因此，伴隨各種超大規(guī)模圖數(shù)據(jù)信息與處理機(jī)制的問世，怎樣科學(xué)合理地進(jìn)行圖聚類分析與處理，在此基礎(chǔ)上，對(duì)其中潛在的有效數(shù)據(jù)進(jìn)行挖掘，已經(jīng)發(fā)展成為該領(lǐng)域的一個(gè)重要課題[6]。

數(shù)據(jù)抽樣[7]屬于其中非常有效的一個(gè)方式。其大致步驟為：抽取整體數(shù)據(jù)集合里面的局部樣本，利用這種方式實(shí)施數(shù)據(jù)挖掘處理與分析，旨在實(shí)現(xiàn)時(shí)間和挖掘處理結(jié)果的高性能比。在分析過程中，應(yīng)當(dāng)先依次對(duì)圖模型里面包含的各結(jié)點(diǎn)和邊實(shí)施數(shù)據(jù)抽樣操作，通常情況下，這個(gè)步驟叫做圖稀疏化處理；然后對(duì)上一步得出的結(jié)果實(shí)施圖聚類分析，這樣就可以使圖聚類分析與處理的有效性有所提升。

作為圖聚類中非常關(guān)鍵的步驟之一，圖稀疏化處理機(jī)制[8]已經(jīng)在諸多領(lǐng)域中得到應(yīng)用。針對(duì)小區(qū)域范圍、小規(guī)模的圖模型數(shù)據(jù)信息，當(dāng)前業(yè)界形成的圖稀疏化處理機(jī)制大體上涉及到k-最近鄰圖、L-Spar等技術(shù)。但是，當(dāng)前的技術(shù)均無法滿足較大區(qū)域與規(guī)模圖模型數(shù)據(jù)信息的需要，除此之外，還無法在分布式集群計(jì)算環(huán)境中有效應(yīng)用。

考慮到當(dāng)前圖模型應(yīng)用產(chǎn)品的日益更新，其應(yīng)用規(guī)模同樣逐漸增加，數(shù)據(jù)信息逐漸增大，單一的計(jì)算環(huán)境無法充分適用數(shù)據(jù)分析與處理，同時(shí)導(dǎo)致圖稀疏化處理機(jī)制不能發(fā)揮作用。所以，引入MapReduce并行計(jì)算理論已成為目前一個(gè)明顯趨勢，其能夠關(guān)聯(lián)操作大規(guī)模服務(wù)終端，可以充分解決大規(guī)模數(shù)據(jù)分析與處理的需要。鑒于這個(gè)方面的原因，筆者主要闡述了基于并行計(jì)算的高效圖稀疏化處理算法。

傳統(tǒng)的最小哈希算法[9](Minhash)基本上是用來求解若干數(shù)據(jù)集合間的相似程度，目前為止，該種方法在諸多熱門課題中得到應(yīng)用[10]。具體來說，該種算法基本上是參考Jaccard相似度，通過K個(gè)Hash函數(shù)分別對(duì)2個(gè)數(shù)據(jù)集A、B實(shí)施Hash操作，兩者分別得到K個(gè)Minhash參數(shù)值。這樣，兩者的相似值即Minhash參數(shù)值一樣的元素?cái)?shù)和總體元素?cái)?shù)之比。截至目前，業(yè)界許多相關(guān)專家已經(jīng)對(duì)圖聚類的性質(zhì)展開探討，得到一種啟發(fā)式圖聚類規(guī)則集合，叫做同一聚簇條件下的各結(jié)點(diǎn)相似的鄰居結(jié)點(diǎn)集合。因此，鄰居結(jié)點(diǎn)集合內(nèi)的相似結(jié)點(diǎn)非常有可能處在同個(gè)聚簇之中。在稀疏化處理機(jī)制中，該種規(guī)則集合即2個(gè)關(guān)聯(lián)結(jié)點(diǎn)存在的邊能夠被存儲(chǔ)。不同的是，要是2個(gè)結(jié)點(diǎn)的鄰居結(jié)點(diǎn)集合具有相對(duì)偏低的相似程度，在這種情況下，則2個(gè)關(guān)聯(lián)結(jié)點(diǎn)的邊將被刪除。這與Minhash算法大致相似。

基于上文中提出的基本原理，筆者細(xì)致深入地探討了在分布式集群計(jì)算環(huán)境下對(duì)超大規(guī)模、超大區(qū)域范圍圖數(shù)據(jù)信息的稀疏化分析與處理機(jī)制的改進(jìn)[11]。筆者主要是基于MapReduce理論，對(duì)Minhash算法實(shí)施并行化分析，通過研究，闡明了以并行計(jì)算為基礎(chǔ)的高效圖稀疏化處理方案。自技術(shù)層面入手，該方案通過并行計(jì)算MapReduce框架結(jié)構(gòu)[12]，對(duì)諸多任務(wù)的推算進(jìn)行研究：(1) Minhash算法簽名推演；(2) 鄰居結(jié)點(diǎn)數(shù)據(jù)集合推算；(3) 各結(jié)點(diǎn)相互間的簽名哈希存儲(chǔ)；(4) 稀疏化處理計(jì)算。除此之外，筆者在Hadoop計(jì)算環(huán)境下，對(duì)方案的性能實(shí)施相應(yīng)的實(shí)驗(yàn)，通過研究發(fā)現(xiàn)，在圖聚類稀疏化分析與處理機(jī)制中，引入該方案為機(jī)制的高效性能提供了堅(jiān)實(shí)的保障。

1相關(guān)研究

這一部分細(xì)致深入地闡述了Minhash算法和并行計(jì)算MapReduce架構(gòu)理論等相關(guān)內(nèi)容。

1.1Minhash算法

上文中我們已經(jīng)提及，Minhash算法基本上是參考Jaccard相似度實(shí)施的推算。Jaccard為相似參數(shù)值，主要是在檢測若干數(shù)據(jù)集合相互間相似度的過程中應(yīng)用。例如利用其對(duì)A、B數(shù)據(jù)集合實(shí)施相應(yīng)的操作，就能夠得出：

(1)

式中，Jaccard參數(shù)值為A、B的對(duì)比數(shù)值?？梢钥闯觯?個(gè)數(shù)據(jù)集合相似度越高與Jaccard參數(shù)值呈正比例關(guān)系。但是，當(dāng)數(shù)據(jù)集合相對(duì)較大時(shí)，Jaccard參數(shù)值將為交并集合的規(guī)模所限制，它的效率就不能增加。

Minhash算法主要參考Jaccard參數(shù)值有關(guān)理論，首先，通過Hash函數(shù)求解兩個(gè)數(shù)據(jù)集合的總元素?cái)?shù)量，其次，得到相關(guān)結(jié)果信息，也就是Minhash(A)和Minhash(B)，因此：

(2)

這樣，在這一個(gè)算法里面，相似度問題就轉(zhuǎn)變?yōu)槿舾蓴?shù)據(jù)集合的等值概率數(shù)學(xué)問題，最終在很大程度上優(yōu)化了計(jì)算效率。

1.2并行計(jì)算理論

谷歌最早闡明了分布式框架理論體系，基本上是在超大規(guī)模、超大區(qū)域范圍的數(shù)據(jù)集合分析與處理機(jī)制中應(yīng)用。作為并行計(jì)算的一個(gè)重要架構(gòu)，MapReduce能夠使相關(guān)人員在并行編程過程中，僅僅需要側(cè)重其應(yīng)用體系內(nèi)的分析與處理機(jī)制就可以，根本不必考慮那些冗余、繁瑣的分布式事務(wù)。這同樣屬于并行計(jì)算理論所具有的一個(gè)非常明顯的優(yōu)勢。

MapReduce并行計(jì)算的操作步驟如圖1所示。

圖1　MapReduce并行計(jì)算工作流程

通過圖1得知，一般情況下，MapReduce分布式任務(wù)往往都離不開有關(guān)分析與處理過程，大致步驟如下：

(1) Mapping環(huán)節(jié)：利用這一個(gè)步驟，任一Map函數(shù)操作若干Split數(shù)據(jù)集合，在此基礎(chǔ)上，將有關(guān)參數(shù)值輸出，也就是若干鍵值對(duì)數(shù)據(jù)信息；

(2) Combine環(huán)節(jié)：對(duì)第一步中若干鍵值對(duì)數(shù)據(jù)信息實(shí)施排列、分類組合操作；

(3) Reducing環(huán)節(jié)：這一個(gè)步驟主要是對(duì)上文中經(jīng)過有關(guān)處理的若干鍵值對(duì)數(shù)據(jù)信息實(shí)施遍歷操作，把唯一性鍵值操作有關(guān)Reduce函數(shù)，得到有關(guān)輸出結(jié)果。

Hadoop為并行計(jì)算工具，目前已經(jīng)得到普及推廣。筆者在這里主要通過Hadoop實(shí)現(xiàn)本文所設(shè)計(jì)方案的模擬實(shí)驗(yàn)處理過程。模擬實(shí)驗(yàn)操作于Hadoop平臺(tái)下的MapReduce應(yīng)用程序，其大體上包括Mapping類(1個(gè))、Reducer類、新建的JobConf驅(qū)動(dòng)方法及關(guān)聯(lián)Combiner類。

2問題描述

當(dāng)前業(yè)界研究結(jié)果中，L-Spar算法的原理如下所示：就圖模型的邊v(i,j)來說，根據(jù)i和j兩個(gè)結(jié)點(diǎn)間的Jaccard參數(shù)值來選擇相應(yīng)的刪除或存儲(chǔ)方法。按照式(1)能夠求解出i和j兩個(gè)結(jié)點(diǎn)的Jaccard參數(shù)值，則有：

(3)

式中，Adj(i)表示和i結(jié)點(diǎn)的鄰居數(shù)據(jù)集合，與之相同，Adj(j)則表示和j結(jié)點(diǎn)的鄰居數(shù)據(jù)集合。

Sim(i,j)輸出數(shù)值的高效計(jì)算應(yīng)用了最小哈希函數(shù)在數(shù)據(jù)集合相似程度求解過程中的優(yōu)勢。其具體求解過程見圖2所示。

圖2　L-Spar算法具體描述圖

對(duì)于L-Spar算法來說，其基本上是基于小規(guī)模環(huán)境中的圖聚類稀疏化分析與處理機(jī)制。當(dāng)其處于超大規(guī)模分布式集群計(jì)算條件下時(shí)，在這種情況下，它的算法優(yōu)勢將不能得到充分發(fā)揮。所以，為妥善解決超大區(qū)域范圍、超大規(guī)模的分布式集群計(jì)算問題，筆者在這里主要基于并行計(jì)算MapReduce架構(gòu)理論體系，在此基礎(chǔ)上，優(yōu)化L-Spar算法，然后把它引入到圖聚類的稀疏化分析與處理機(jī)制，最終得到以并行計(jì)算為基礎(chǔ)的高效圖稀疏化處理方案。筆者在后文會(huì)細(xì)致深入地對(duì)該方案進(jìn)行闡述。

3高效處理方案

針對(duì)超大規(guī)模、超大區(qū)域范圍的分布式集群計(jì)算條件提出的方案，其具體操作步驟大體上涉及到4方面內(nèi)容，分別為：(1) Minhash算法簽名推演；(2) 鄰居結(jié)點(diǎn)數(shù)據(jù)集合推算；(3) 各結(jié)點(diǎn)相互間的簽名哈希存儲(chǔ)；(4) 稀疏化處理計(jì)算。

3.1鄰居結(jié)點(diǎn)數(shù)據(jù)集合推算

本文所設(shè)計(jì)方案的首個(gè)環(huán)節(jié)是對(duì)一組Map任務(wù)得出圖模型中任一邊結(jié)點(diǎn)的鄰居結(jié)點(diǎn)數(shù)據(jù)集合，具體來說，其操作步驟見圖3所示。

圖3　鄰居結(jié)點(diǎn)數(shù)據(jù)集合推算流程

通過圖3得知，Map任務(wù)獲取一組鍵值對(duì)數(shù)據(jù)信息，結(jié)點(diǎn)信息為vi和vj。經(jīng)由求解發(fā)現(xiàn)，輸出鍵值對(duì)數(shù)據(jù)信息為，在這里vi的鄰居結(jié)點(diǎn)數(shù)據(jù)集合為list[Ni]，在HDFS平臺(tái)中引入輸出參數(shù)值。其Map任務(wù)可以通過下面的方式進(jìn)行表示：

Map:

→

3.2Minhash算法簽名推演

本文所設(shè)計(jì)方案的第二個(gè)環(huán)節(jié)是對(duì)圖模型中任意結(jié)點(diǎn)的Minhash算法簽名數(shù)據(jù)信息進(jìn)行推算。鑒于此，本文所設(shè)計(jì)方案可結(jié)合Map和Reduce任務(wù)，在此基礎(chǔ)上，推算Minhash算法簽名數(shù)據(jù)信息，具體來說，其操作步驟見圖4所示。

圖4　結(jié)點(diǎn)Minhash算法簽名推算流程

在這里，Map任務(wù)的輸入?yún)?shù)值為首個(gè)環(huán)節(jié)得到的輸出結(jié)果。通過上面的圖形，Map任務(wù)主要是將若干Minhash函數(shù)(k個(gè))當(dāng)作其輸入?yún)?shù)值，在此基礎(chǔ)上，利用Hash推算，就能夠得到其鍵值對(duì)數(shù)據(jù)信息(m=1,2,…,k)，在這里，Hm(Ni)代表最小哈希函數(shù)的列表信息。該部分輸出結(jié)果為Reduce任務(wù)的輸入?yún)?shù)值，利用Reduce推算得到鍵值對(duì)數(shù)據(jù)信息，在這里，Sig[i][m]為二元形式化數(shù)組，描述vi的算法簽名序列。從而把Sig[i][m]引入到HDFS平臺(tái)里面。具體可以通過下面方式進(jìn)行描述：

Map:

→

(m=1,2,…,k)

Reduce:

→

此部分的操作步驟包括若干子環(huán)節(jié)，接下來筆者將進(jìn)行闡述：

(1) Map任務(wù)處理描述

輸入，其中key=vi是圖中的結(jié)點(diǎn)，value=list[Ni]是結(jié)點(diǎn)的鄰居結(jié)點(diǎn)數(shù)據(jù)集合；k個(gè)不同的Minhash函數(shù)。

輸出，其中value=list[Hm(Ni)]是結(jié)點(diǎn)的Minhash值列表。

1. list[Hm]←φ/*初始化結(jié)點(diǎn)的鄰居結(jié)點(diǎn)數(shù)據(jù)集合的Minhash值列表*/

2. foreach vi in Graph do

for m in k

/*對(duì)結(jié)點(diǎn)的鄰居結(jié)點(diǎn)數(shù)據(jù)集合進(jìn)行k次Minhash計(jì)算，并將hash結(jié)果存儲(chǔ)于Hm列表中*/

Hm=Minhash(list[Ni])

end for

end foreach

(2) Reduce任務(wù)處理描述

輸入，結(jié)點(diǎn)的Minhash值列表。

輸出，即圖模型中結(jié)點(diǎn)的簽名矩陣。

1. Sig[i][m]←φ/*初始化結(jié)點(diǎn)的簽名矩陣*/

2. foreach vi in Graph do

Sig[i]=sortSig(Hm)

/*對(duì)結(jié)點(diǎn)的hash值列表排序，依次存儲(chǔ)結(jié)點(diǎn)的簽名矩陣*/

end foreach

3.3結(jié)點(diǎn)簽名之間的哈希存儲(chǔ)

本文所設(shè)計(jì)方案處理操作的這一個(gè)部分旨在判斷圖模型里面每一結(jié)點(diǎn)關(guān)聯(lián)鄰接邊是否為圖聚類稀疏化結(jié)構(gòu)。實(shí)質(zhì)而言，其主要是通過結(jié)合Map和Reduce的方式推算任一個(gè)結(jié)點(diǎn)，其具體描述步驟如圖5所示。

圖5　結(jié)點(diǎn)簽名的哈希存儲(chǔ)處理流程

通過圖5得知，這個(gè)環(huán)節(jié)的Map任務(wù)環(huán)節(jié)輸入為該方案的首個(gè)環(huán)節(jié)中獲取的鍵值對(duì)數(shù)據(jù)信息和算法簽名二元數(shù)組集合Sig[i][m]，獲取有關(guān)中間參數(shù)值，其當(dāng)做Reduce任務(wù)步驟的輸入，并且哈希函數(shù)同樣屬于一個(gè)輸入?yún)?shù)值，這樣的獲取輸出為。這一個(gè)環(huán)節(jié)的形式化表達(dá)見下文所示：

Map:

→

Reduce:

→

這一個(gè)部分與該方案的第二環(huán)節(jié)一樣，其處理步驟同樣包括若干子環(huán)節(jié)，見下文所示：

(1) Map階段處理描述

輸入，其中key=vi是圖中的結(jié)點(diǎn)，value=list[Ni]是結(jié)點(diǎn)的鄰居結(jié)點(diǎn)數(shù)據(jù)集合；結(jié)點(diǎn)的簽名矩陣Sig[i][m]。

輸出，其中value=list[S(Sig[i],Sig[j])]表示結(jié)點(diǎn)鄰接邊的簽名數(shù)據(jù)集合。

1. list[S]←φ/*初始化結(jié)點(diǎn)的鄰接邊的簽名數(shù)據(jù)集合列表*/

2. foreach vi in Graph do

for vj in list[Ni]

/*分別找出對(duì)應(yīng)于結(jié)點(diǎn)和鄰居結(jié)點(diǎn)數(shù)據(jù)集合中的結(jié)點(diǎn)的簽名序列*/

temp1=FindSignature(vi,Sig)

temp2=FindSignature(vj,Sig)

/*函數(shù)FindSignature(x,Sig)返回在簽名矩陣Sig中x結(jié)點(diǎn)的簽名序列*/

S(Sig[i],Sig[j])=Integration(temp1,temp2)

/*函數(shù)Integration(x,y)返回x與y結(jié)合的集合*/

end for

end foreach

(2) Reduce階段處理描述

輸入，其中key=vi是圖中的結(jié)點(diǎn)，value=list[S(Sig[i],Sig[j])]表示結(jié)點(diǎn)鄰接邊的簽名數(shù)據(jù)集合。

輸出，其中value=list[SortCij]表示經(jīng)過排序后的結(jié)點(diǎn)與鄰接結(jié)點(diǎn)的匹配數(shù)量。

1. list[SortCij]←φ/*初始化排序后的結(jié)點(diǎn)與鄰居結(jié)點(diǎn)簽名匹配列表*/

2. foreach vi in Graph do

foreach in list[S]

/*分別對(duì)結(jié)點(diǎn)與鄰居結(jié)點(diǎn)的簽名進(jìn)行hash操作*/

hashtable1=Minhash(Sig[i])

hashtable2=Minhash(Sig[j])

Countij=MatchTable(hashtable1,hashtable2)

/*函數(shù)MatchTable(x,y)返回x與y之間相同數(shù)量*/

SortCij=sortCount(Countij)

/*函數(shù)sortCount(x)返回降序排序的x列表*/

end foreach

end foreach

3.4圖聚類過程中的稀疏化處理計(jì)算

圖6　保留存儲(chǔ)結(jié)點(diǎn)處理流程

Map:

→

這一個(gè)部分的處理步驟見下文所示：

輸出,其中value=list[top]表示需要保留下來的結(jié)點(diǎn)的鄰居結(jié)點(diǎn)。

1. list[top]←φ/*初始化結(jié)點(diǎn)需要保留的鄰居結(jié)點(diǎn)數(shù)據(jù)集合*/

2. foreach vi in Graph do

/*函數(shù)ToSave(x,y)返回x列表中前y條邊，并且根據(jù)邊找到其所含的結(jié)點(diǎn)，并記錄下來*/

end foreach

在該方案的最后一個(gè)環(huán)節(jié)實(shí)施以后，圖模型里面的各結(jié)點(diǎn)都對(duì)e大于1的邊的數(shù)量進(jìn)行存儲(chǔ)，這樣就為圖模型處于連通狀態(tài)提供了保障。

4模擬實(shí)驗(yàn)

現(xiàn)簡要模擬本文所設(shè)計(jì)方案，并通過對(duì)比檢驗(yàn)其效率。

Hadoop平臺(tái)主要是由最基礎(chǔ)最重要的兩種組成元素組成，底層為用于存儲(chǔ)集群中所有存儲(chǔ)節(jié)點(diǎn)文件的文件系統(tǒng)HDFS (Hadoop Distributed File System)，上層由用來執(zhí)行 MapReduce 程序的 MapReduce 引擎[13]。HDFS 是一個(gè)分布式文件系統(tǒng)， 具有高容錯(cuò)性的特點(diǎn)，能夠完整展現(xiàn)出分布式集群環(huán)境中集群的特點(diǎn)[14];按照計(jì)算機(jī)分布式思想，分布式計(jì)算是指將巨量的計(jì)算任務(wù)分配成許多小任務(wù)并由眾多的計(jì)算機(jī)進(jìn)行處理，Hadoop平臺(tái)上的MapReduce 編程架構(gòu)可以實(shí)現(xiàn)任務(wù)的分配，并把分配后任務(wù)的運(yùn)算結(jié)果匯總，完全可以實(shí)現(xiàn)對(duì)分布式集群環(huán)境運(yùn)算模式的仿真，因此本文選擇Hadoop平臺(tái)正是基于以上目的，有效體現(xiàn)分布式集群環(huán)境的特點(diǎn)，并對(duì)其可能存在影響因素通過在Hadoop仿真平臺(tái)進(jìn)行實(shí)踐。

4.1相關(guān)配置

筆者在這里采用MapReduce，將其引入到Hadoop分布式集群計(jì)算條件中。主要包括若干服務(wù)器和終端等方面，其中包括主機(jī)1臺(tái)，別的均為附屬機(jī)，計(jì)算環(huán)境下的每一結(jié)點(diǎn)CPU處理器工作頻率始終處于3.20 GHz，因特爾雙核處理芯片，內(nèi)存必須≥1 GB。Hadoop分布式計(jì)算環(huán)境版本為1.0.5，OS，Java語言。數(shù)據(jù)信息源為新浪微博社交虛擬網(wǎng)絡(luò)的關(guān)聯(lián)圖模型。

模擬過程中主要通過Speedup參數(shù)值描述本文所設(shè)計(jì)方案的性能指標(biāo)參數(shù)變化。其具體可以通過下面的公式進(jìn)行描述：

Sspeedup=Ti/T1

(4)

上面的式子里面，Ti指第i個(gè)分布式集群計(jì)算條件下結(jié)點(diǎn)對(duì)圖模型稀疏化分析與處理所用時(shí)間，T1指單機(jī)條件下對(duì)圖模型稀疏化分析與處理所用時(shí)間。

4.2操作和分析

模擬過程中選擇不同的圖模型稀疏化處理機(jī)制，得到的圖模型稀疏化比率參數(shù)值e同樣存在著一定的差異，為解決各種數(shù)據(jù)信息量和分類的圖模型數(shù)據(jù)信息，對(duì)應(yīng)的最合理的e值同樣存在一定的差異。筆者在這里取e為0.15，在此基礎(chǔ)上實(shí)施有關(guān)操作。

為體現(xiàn)本文設(shè)計(jì)方案在超大規(guī)模、超大區(qū)域范圍的分布式集群計(jì)算環(huán)境下的高效性能，模擬過程中筆者主要使用不同并行計(jì)算條件下的執(zhí)行算法。該方案第一步是對(duì)Map和Reduce任務(wù)階段實(shí)施過程處理，接著分析了圖模型數(shù)據(jù)信息，完成稀疏化分析與處理機(jī)制。模擬過程中涉及到的數(shù)據(jù)信息如圖7所示。

圖7　模擬實(shí)驗(yàn)分析結(jié)果

通過圖7發(fā)現(xiàn)，對(duì)于超大規(guī)模、超大區(qū)域范圍的分布式集群計(jì)算環(huán)境下，引入Hadoopp并行計(jì)算平臺(tái)可以明顯減少時(shí)間損失，最終可以顯著提高Speedup。按照MapReduce理論，圖模型數(shù)據(jù)信息規(guī)模與圖聚類過程稀疏化比率參數(shù)值兩者存在正相性；但是伴隨分布式集群計(jì)算條件下每一結(jié)點(diǎn)的通信過于頻繁，同樣能夠消耗或多或少的數(shù)據(jù)信息性能，當(dāng)圖模型數(shù)據(jù)信息交互規(guī)模相對(duì)偏小時(shí)，在這種情況下，圖聚類過程稀疏化分析與處理機(jī)制效率將有所下降，對(duì)應(yīng)的e參數(shù)值同比降低。另一方面，當(dāng)Speedup和分布式集群計(jì)算環(huán)境不斷提高時(shí)，其圖聚類過程稀疏化分析與處理機(jī)制同樣不斷增加，其e參數(shù)值同比提高。

4.3算法聚類能力準(zhǔn)確度分析

為了體現(xiàn)本文算法在分布式集群環(huán)境中準(zhǔn)確度的優(yōu)勢，下面在Hadoop平臺(tái)上，將本文所設(shè)計(jì)方案與基于MapReduce的K-means聚類算法做對(duì)比(這種算法的實(shí)現(xiàn)見參考文獻(xiàn)[16])。在準(zhǔn)確度評(píng)價(jià)體系上，這里引入F度量值來衡量算法的聚類準(zhǔn)確度效果，具體涉及查準(zhǔn)率與查全率[17]，其中：

查準(zhǔn)率=(第i類的正確文本數(shù)/第i類的實(shí)際文本數(shù))*100%

查全率=(第i類的正確文本數(shù)/第i類的應(yīng)有文本數(shù))*100%

F度量值綜合查準(zhǔn)率和查全率，將兩者等同考慮，以此來衡量算法的聚類準(zhǔn)確度，第i類：

其中Pi是第i類的應(yīng)有文本數(shù)，P是文本數(shù)。

在本對(duì)比實(shí)驗(yàn)中，原始數(shù)據(jù)來自于國家超級(jí)計(jì)算機(jī)中心的數(shù)據(jù)庫的相應(yīng)的數(shù)據(jù)類別中隨機(jī)調(diào)取的部分?jǐn)?shù)據(jù)[18]，原始數(shù)據(jù)見表1所示。

表1　實(shí)驗(yàn)基礎(chǔ)數(shù)據(jù)

實(shí)驗(yàn)結(jié)果見表2所示，從表2可以看出本文所設(shè)計(jì)方案的F度量值要優(yōu)于基于MapReduce的K-maens聚類算法，即其聚類質(zhì)量占優(yōu)，同時(shí)其分類準(zhǔn)確率也相應(yīng)提高。

表2　F度量值對(duì)比值

4.4方案運(yùn)行時(shí)間分析

為了進(jìn)一步檢驗(yàn)本文所設(shè)計(jì)的算法的效率，下面將本文所設(shè)計(jì)稀疏化方案與基于k-medoids聚類算法局部圖稀疏化方案[19]，在運(yùn)行時(shí)間上做對(duì)比。k-medoids聚類算法具有收斂快、運(yùn)行簡單的特點(diǎn)，在業(yè)內(nèi)時(shí)間復(fù)雜度上有較為明顯的優(yōu)勢。運(yùn)行平臺(tái)與4.3節(jié)相同，實(shí)驗(yàn)素材采用DBLP數(shù)據(jù)集[20]，運(yùn)行時(shí)間對(duì)比數(shù)值見表3所示。

表3　運(yùn)行時(shí)間對(duì)比圖　　　　　　　單位：s

表3中e代表稀疏化比例參數(shù)，從表3可知，本文設(shè)計(jì)的方案，在與k-medoids聚類算法相比仍具有一定的時(shí)間優(yōu)勢，并且在不同的稀疏化比例條件下，其性能表現(xiàn)較為穩(wěn)定。

經(jīng)由模擬實(shí)驗(yàn)我們發(fā)現(xiàn)，本文所設(shè)計(jì)的方案更適合超大區(qū)域范圍、超大規(guī)模的分布式集群計(jì)算環(huán)境下的圖數(shù)據(jù)信息，因在該方案里面增設(shè)排序組合機(jī)制，正是這一個(gè)方面的原因，導(dǎo)致結(jié)點(diǎn)和鄰接結(jié)點(diǎn)間的通信消耗有所減小，也就是圖數(shù)據(jù)信息規(guī)模與算法效率性價(jià)比兩者呈正比例關(guān)系。

5結(jié)語

針對(duì)超大規(guī)模、超大區(qū)域范圍的分布式集群計(jì)算環(huán)境，筆者主要是基于MapReduce理論，對(duì)Minhash算法實(shí)施并行化分析，通過研究，闡明了以并行計(jì)算為基礎(chǔ)的高效圖稀疏化處理方案。這一個(gè)方案可以對(duì)圖聚類數(shù)據(jù)信息進(jìn)行高效處理。經(jīng)由模擬實(shí)驗(yàn)可知，這一個(gè)算法具有較高的可操作性，同時(shí)可以快速稀疏化處理圖聚類數(shù)據(jù)信息，簡單高效。

參考文獻(xiàn)

[1] Lin J,Schataz M.Design patterns for efficient graph algorithms in mapreduce[C]//MLG,2010,22(3):78-85.

[2] Lv Qin,Josephson W,Wang Zhe,et al.Multi-probe LSH:efficient indexing for high-dimensional similarity search[C]//Pro of the 33rdInt Conf on Very Large Data Bases(VLDB’07).Vienna Austria:VLDB Endowment,2007,10(2):950-961.

[3] Yang H C,Dasdan A,Hsiao R L,et al.Map-Reduce-Merge: Simplified relational data processing[C]//Proc of ACM SIGMOD International Conference on Management of Data,New York:ACM,2007:1029-1040.

[4] Vrba Z,Halvorsen P,Griwodz C,et al.Kahn process networks are a flexible alternative to mapreduce[C]//Proc of IEEE International Conference on High Performance Computing and Communications,Piscataway:IEEE,2009:154-162.

[5] Sandholm T,Lai K.MapReduce optimization using regulated dynamic prioritization[J].Performance Evaluation Review,2009,37(1):299-310.

[6] Liu Q,Todman T, Luk W,et al.Combining optimizations in automated low power design[C]//Proc of Design, Automation&Test in Europe Conference&Exhibition,Piscataway:IEEE,2010:1791-1796.

[7] Chen Quan,Zhang Daqiang,Gao Mingi,et al.SAMR:A self-adaptive mapreduce scheduling algorithm in heterogeneous environment[C]//Proc of IEEE International Conference on Computer and Information Technology,Los Alamitos:IEEE computer society,2010:2736-2743.

[8] Nicolas Garcia-Pedrajas,Aida de Haro-Garcia.Scaling up data mining algorithms:Review and taxonomy[J].Process in Artificial Intelligence,2012,1(1):71-87.

[9] Satu Elisa Schaeffer.Scalable uniform graph sampling by local computation[J].SIAM Journal on Scientific Computing,2010,32(5):2937-2963.

[10] 溫菊屏,鐘勇.圖聚類的算法及其在社會(huì)關(guān)系網(wǎng)絡(luò)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件,2012,29(2):161-178.

[11] Arun S Maiya,Tanya Y Bergerwolf.Sampling community structure[C]//Raleigh,North Carolina,USA:WWW,2010:701-710.

[12] Choi Seung-Seok,Cha Sunghyuk,Charles C Tappert.A survey of binary similarity and distance measures[J].Systemics,Cybernetics and Informatics,2010,8(1):43-48.

[13] Apache.Apache hadoop[CP/OL].http://hadoop.apache.org/core/.

[14] 萬波,黨琦,楊林.基于HDFS管理MapGISK9瓦片地圖集的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(12):232-235.

[15] 丁祥武,李清炳,樂嘉錦.使用MapReduce構(gòu)建列存儲(chǔ)數(shù)據(jù)的索引[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(2):24-28.

[16] 江小平,李成華,向文,等.k-means聚類算法的MapReduce并行化實(shí)現(xiàn)[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2011,39(S1):120-124.

[17] 肖升,何炎祥.改進(jìn)的潛在語義分析中文摘錄方法[J].計(jì)算機(jī)應(yīng)用研究,2012,29(12):4507-4511.

[18] 高賀慶.一種適應(yīng)高速數(shù)據(jù)流的聚類算法研究[D].長沙:湖南大學(xué),2013.

[19] 溫菊屏,林冬梅.圖稀疏化:加速圖聚類的有效方法[J].計(jì)算機(jī)工程與設(shè)計(jì),2013,34(11):3934-3938.

[20] http://www.informatik.uni-trier.de/~ley/db/.

中圖分類號(hào)TP311

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.02.051

收稿日期：2014-04-26。國家自然科學(xué)基金創(chuàng)新研究群體科學(xué)基金項(xiàng)目(51021004)。劉娟娟，講師，主研領(lǐng)域：數(shù)字媒體技術(shù)。丁嘉寧，工程師。