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

劉娟娟　丁嘉寧

1(天津天獅學院信息與自動化學院　天津 301700)

2(天津大學港口與海洋工程天津市重點實驗室　天津 300072)

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

?

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

劉娟娟1丁嘉寧2,3

1(天津天獅學院信息與自動化學院天津 301700)

2(天津大學港口與海洋工程天津市重點實驗室天津 300072)

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

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

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

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

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

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

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

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

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

1相關研究

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

1.1Minhash算法

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

(1)

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

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

(2)

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

1.2并行計算理論

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

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

圖1　MapReduce并行計算工作流程

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

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

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

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

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

2問題描述

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

(3)

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

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

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

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

3高效處理方案

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

3.1鄰居結點數(shù)據(jù)集合推算

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

圖3　鄰居結點數(shù)據(jù)集合推算流程

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

Map:

→

3.2Minhash算法簽名推演

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

圖4　結點Minhash算法簽名推算流程

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

Map:

→

(m=1,2,…,k)

Reduce:

→

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

(1) Map任務處理描述

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

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

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

2. foreach vi in Graph do

for m in k

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

Hm=Minhash(list[Ni])

end for

end foreach

(2) Reduce任務處理描述

輸入，結點的Minhash值列表。

輸出，即圖模型中結點的簽名矩陣。

1. Sig[i][m]←φ/*初始化結點的簽名矩陣*/

2. foreach vi in Graph do

Sig[i]=sortSig(Hm)

/*對結點的hash值列表排序，依次存儲結點的簽名矩陣*/

end foreach

3.3結點簽名之間的哈希存儲

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

圖5　結點簽名的哈希存儲處理流程

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

Map:

→

Reduce:

→

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

(1) Map階段處理描述

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

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

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

2. foreach vi in Graph do

for vj in list[Ni]

/*分別找出對應于結點和鄰居結點數(shù)據(jù)集合中的結點的簽名序列*/

temp1=FindSignature(vi,Sig)

temp2=FindSignature(vj,Sig)

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

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

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

end for

end foreach

(2) Reduce階段處理描述

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

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

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

2. foreach vi in Graph do

foreach in list[S]

/*分別對結點與鄰居結點的簽名進行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圖聚類過程中的稀疏化處理計算

圖6　保留存儲結點處理流程

Map:

→

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

輸出,其中value=list[top]表示需要保留下來的結點的鄰居結點。

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

2. foreach vi in Graph do

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

end foreach

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

4模擬實驗

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

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

4.1相關配置

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

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

Sspeedup=Ti/T1

(4)

上面的式子里面，Ti指第i個分布式集群計算條件下結點對圖模型稀疏化分析與處理所用時間，T1指單機條件下對圖模型稀疏化分析與處理所用時間。

4.2操作和分析

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

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

圖7　模擬實驗分析結果

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

4.3算法聚類能力準確度分析

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

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

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

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

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

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

表1　實驗基礎數(shù)據(jù)

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

表2　F度量值對比值

4.4方案運行時間分析

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

表3　運行時間對比圖　　　　　　　單位：s

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

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

5結語

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

參考文獻

[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] 溫菊屏,鐘勇.圖聚類的算法及其在社會關系網(wǎng)絡中的應用[J].計算機應用與軟件,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瓦片地圖集的研究與實現(xiàn)[J].計算機應用與軟件,2013,30(12):232-235.

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

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

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

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

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

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

中圖分類號TP311

文獻標識碼A

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

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