摘要： 在研究Web結(jié)構(gòu)挖掘經(jīng)典算法Pagerank和云計算關(guān)鍵技術(shù)Mapreduce的基礎(chǔ)上，將Pagerank算法與Mapreduce編程模型結(jié)合，針對基于并行Pagerank算法運行大數(shù)據(jù)集時面臨的每次迭代訪問HDFS導(dǎo)致I/O消耗增加、每次迭代在混合階段和排序階段時耗過多的問題提出了兩個改進(jìn)算法。一個是利用矩陣分塊思想的并行Pagerank改進(jìn)算法；另一個是減少HDFS訪問次數(shù)的并行Pagerank改進(jìn)算法。最后利用Hadoop搭建云環(huán)境，在實驗環(huán)境下分析了不同的BlockSize參數(shù)對于計算性能的影響。并在云環(huán)境下面向不同的Web數(shù)據(jù)集，測試了原算法和改進(jìn)算法的性能。結(jié)果表明，改進(jìn)后的算法分別在結(jié)果集的空間占用方面和總迭代時間方面具有一定的優(yōu)越性。

關(guān)鍵詞： 云計算； Web結(jié)構(gòu)挖掘； 分布式計算； Mapreduce； Hadoop； Pagerank

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228(2012)10-30-04

引言

Web結(jié)構(gòu)挖掘是通過研究網(wǎng)頁之間的鏈接結(jié)構(gòu)來發(fā)現(xiàn)網(wǎng)絡(luò)的組織結(jié)構(gòu)和鏈接關(guān)系中隱藏的知識。隨著互聯(lián)網(wǎng)的迅猛發(fā)展和快速普及，Web上蘊藏的海量信息為數(shù)據(jù)挖掘提供了無比豐富的資源，而對Web信息進(jìn)行有效的知識發(fā)現(xiàn)具有極大的挑戰(zhàn)性。云計算(cloud computing)是分布式處理、并行計算和網(wǎng)格計算的發(fā)展，或者說是這些計算機科學(xué)概念的商業(yè)實現(xiàn)。它是一種新興的共享基礎(chǔ)架構(gòu)的方法，可以將巨大的系統(tǒng)池連接在一起以提供各種IT服務(wù)。很多因素推動了對這類環(huán)境的需求，其中包括連接設(shè)備、實時數(shù)據(jù)流、SOA的采用，以及搜索、開放協(xié)作、社會網(wǎng)絡(luò)和移動商務(wù)等這樣的Web2.0應(yīng)用的急劇增長。鑒于云計算的發(fā)展前景，將相關(guān)領(lǐng)域的研究工作與云計算研究工作相結(jié)合是當(dāng)前研究的一個熱點。本文的研究工作源于上述背景，目的是對Web結(jié)構(gòu)挖掘技術(shù)進(jìn)行深入的學(xué)習(xí)研究，探討Web結(jié)構(gòu)挖掘中的關(guān)鍵算法PageRank，將Pagerank算法與云計算領(lǐng)域相關(guān)技術(shù)結(jié)合，改進(jìn)算法，以使Web結(jié)構(gòu)挖掘適應(yīng)對海量數(shù)據(jù)分析與挖掘。經(jīng)典的Web結(jié)構(gòu)挖掘算法如Pagerank

1.1 Pagerank算法思想

Google的PageRank算法就是一種基于隨機網(wǎng)絡(luò)的檢索策略。假設(shè)讀者在Web上無目的瀏覽，其以1-d的概率沿本頁面的一個鏈接進(jìn)行訪問，以d的概率輸入一個隨機的網(wǎng)址，這樣不同的網(wǎng)頁就有不同的訪問率。最終，那些入鏈很多的網(wǎng)頁就是流行網(wǎng)頁。在PageRank算法中，假定網(wǎng)頁P1…Pn有鏈接指向網(wǎng)頁A，設(shè)PR(A)，PR(P1)…PR(Pn)分別表示網(wǎng)頁A，P1…Pn的 PageRank值，參數(shù)d為一個跳轉(zhuǎn)系數(shù)，介于0～1之間，通常取0.85，o(A)被定義為A的出度，則網(wǎng)頁A的PageRank值PR(A)可由公式⑴計算得到。

1.2 Pagerank算法的不足和改進(jìn)

⑴ 由于網(wǎng)頁數(shù)量劇增導(dǎo)致的Web圖鄰接矩陣擴(kuò)大，而鄰接矩陣又多數(shù)是一個稀疏矩陣，造成了大量存儲資源和計算資源的浪費。

⑵ 隨著互聯(lián)網(wǎng)發(fā)展，網(wǎng)頁的信息已成為一種海量的數(shù)據(jù)，保存并計算網(wǎng)頁鏈接的關(guān)系也需要通過大型的并行系統(tǒng)實現(xiàn)，并且由于Pagerank算法需要多次迭代，所以Pagerank算法的并行化也成為必然。在Pagerank的并行算法的問題上已經(jīng)有許多學(xué)者進(jìn)行了研究，Google提出的MapReduce分布式計算框架已經(jīng)被廣泛應(yīng)用在了云計算平臺的部署上，因此，基于開源云計算基礎(chǔ)架構(gòu)Hadoop將Pagerank算法與Mapreduce框架結(jié)合并對算法的運行效率、時空開銷、即收斂性加以研究，將會對開發(fā)部署在云計算平臺上的搜索引擎服務(wù)提供幫助。這也是本文研究的目的。

2 云計算與Mapreduce編程模型

2.1 云計算

云計算是新興的技術(shù)，目前還沒有標(biāo)準(zhǔn)化或規(guī)范。眾多IT廠商均在連續(xù)大力投資云計算的研究，推廣各自的云計算服務(wù)和產(chǎn)品。云計算的標(biāo)準(zhǔn)化研究、技術(shù)研究、服務(wù)產(chǎn)品完善以及各IT廠商的云計算技術(shù)和服務(wù)融合是一種趨勢。而MapReduce是云計算的關(guān)鍵技術(shù)之一，最先由Google提出的分布式計算構(gòu)架，它可以支持大數(shù)據(jù)量的分布式處理[3]。

2.2 Mapreduce編程模型

Mapreduce由google提出，它是一種并行編程模型。用戶可利用Mapreduce將應(yīng)用編程為相應(yīng)的map和reduce操作，以實現(xiàn)應(yīng)用的大規(guī)模并行化計算。

⑴ map：接收輸入數(shù)據(jù)被切片產(chǎn)生的對，然后產(chǎn)生一系列中間對集，MapReduce庫把具有相同key的中間value分別聚合在一起，然后發(fā)送給reduce函數(shù)。

Map過程輸入輸出：

3 基于Mapreduce的并行Pagerank算法研究

3.1 算法提出

⑴ 隨著Web網(wǎng)頁趨向海量，Pagerank算法會造成巨大空間和性能開銷。

⑵ 基于Mapreduce原理，一方面可以解決海量Web網(wǎng)頁存儲的困難，另一方面還可將集中計算分布在集群中各節(jié)點上平攤計算消耗。

3.2 基于Mapreduce的Pagerank算法實現(xiàn)

Pagerank迭代階段的map方法對輸入文件中每一個行記錄的目標(biāo)節(jié)點序列中每個目標(biāo)節(jié)點的輸出為。

Mapreduce框架收集map方法的輸出按每個key歸類其相應(yīng)value。在reduce方法中，對每個key：頁面y，把其list of [partialx]中每一項加和，并帶入公式⑸得到并輸出每個頁面新的Pagerank。把結(jié)果保存在HDFS中，用作下一次迭代。并行Pagerank算法原理如圖1所示。

迭代階段Mapper實現(xiàn)對每個起始點x的目標(biāo)點序列生成一個與目標(biāo)點對應(yīng)的partialx，并為其賦值為Pagerank(x)/目標(biāo)節(jié)點的數(shù)量，最后將這些partialx發(fā)送給Mapreduce框架。

迭代階段Reducer完成對每個節(jié)點partialx的相加并計算新的Px=dPx+(1-d)，將新的Pagerank向量輸出到HDFS。

算法存在的問題：

⑴ 迭代過程執(zhí)行速度方面

Map過程分為讀階段、緩沖階段和寫階段 ，Reduce過程分為混合階段、排序階段和約減階段。Reduce階段的額外性能消耗來自于混合階段和排序階段。當(dāng)任務(wù)在排序階段處理的key關(guān)鍵字越多性能消耗就越大，如果計算Pagerank的過程中將網(wǎng)頁節(jié)點分塊表示將可以在排序階段把性能消耗降低到原來的1/分塊數(shù)。

⑵ 算法總迭代次數(shù)方面

Hadoop下的并行Pagerank算法由于每次迭代需要在集群間通信和訪問HDFS，達(dá)到所需收斂次數(shù)要花費大量時間。如果能夠減少并行Pagerank迭代計算的次數(shù)，增加每次迭代的計算量，也就減少了與迭代次數(shù)相關(guān)的大量通信和訪問HDFS的I/O操作的時間。

3.3 利用矩陣分塊思想的并行Pagerank算法

⑴ 算法思想

⑵ 矩陣分塊較4.2算法的優(yōu)勢

在時間上，Reduce階段的額外性能消耗來自于混合階段和排序階段。當(dāng)任務(wù)在排序階段處理的Key關(guān)鍵字越多性能的消耗就越大，將塊大小設(shè)為b時，Mapreduce處理的矩陣塊的數(shù)量和向量塊的條數(shù)就分別減少到了原來的1/b2和1/b，在第4章節(jié)兩種算法的運行時間對比中也可以看到其優(yōu)勢。

在空間上，由于改進(jìn)后的一條向量塊記錄可以代表之前b條向量的記錄，并且如果向量塊里的節(jié)點都無外鏈接，就無需生成此塊的記錄，這對于稀疏鄰接矩陣可以節(jié)省很多空間。因此可以極大地減少存儲中間結(jié)果時的空間消耗，在章節(jié)4將會對比兩種算法生成結(jié)果的占用空間。另一方面由于生成記錄的總條數(shù)減少，也就減少了內(nèi)存的占用量，從而降低了在Map中因為中間信息超過緩沖區(qū)上限而Partition到本地磁盤并排序所造成的額外I/O消耗，以及Reduce過程因為待排序記錄超過內(nèi)存容量而溢出到磁盤上對Key進(jìn)行外部排序的可能。

3.4 低迭代并行Pagerank改進(jìn)算法

3.4.1 算法分析

首先要分析Pagrank算法的原始計算公式并將該公式加以遞推，如公式⑶：

其中AT是公式⑶表示的矩陣的轉(zhuǎn)置矩陣，Pk為第k次迭代后的如公式⑵所表示的Pagerank向量。因此希望通過初始向量P0快速推導(dǎo)第k次迭代的向量Pk，遞推過程如下：

這里可以通過增加每次迭代Pagerank向量的計算量來達(dá)到盡量減少與迭代次數(shù)有關(guān)的集群節(jié)點間大量通信和訪問HDFS的I/O操作，來加快總的并行Pagerank算法的計算速度。本文將在后面詳細(xì)介紹該加速收斂過程的Mapreduce實現(xiàn)過程。

如公式⑸所表示，對于跨度為2的加速收斂計算P0→P2，可表示為：

3.4.2 算法實現(xiàn)過程

⑴ 首先要預(yù)先生成與跨度k有關(guān)的鄰接矩陣(AT)…(AT)5，因此當(dāng)k=2時，第一步Mapreduce過程計算AT；第二步Mapreduce過程利用第一步中的AT計算出(AT)2；第三步Mapreduce過程每次迭代都將AT、(AT)2和初始Pagerank向量作為輸入文件，生成新的Pagerank向量。并在下次迭代中用新的Pagerank向量代替初始Pagrank向量，反復(fù)迭代下去直至結(jié)果收斂，如圖3所示。

圖3 加速收斂Mapreduce：Pagerank計算框架

⑵ “移動計算比移動數(shù)據(jù)更經(jīng)濟(jì)”是HDFS的特點之一。按照這一思想，應(yīng)盡量避免每輪迭代后修改或移動大數(shù)據(jù)文件，而最好保持輸入數(shù)據(jù)位置不變，以使要被計算的數(shù)據(jù)在所存儲的位置來進(jìn)行計算，這樣可以消除網(wǎng)絡(luò)的擁堵，提高系統(tǒng)的整體吞吐量。因此，AT、(AT)2存儲在HDFS始終不隨迭代改變，如圖3中用Web圖表示的內(nèi)容。Pagerank向量相對空間占用較小，所以每次迭代結(jié)束以新Pagerank向量帶取代舊值。這種實現(xiàn)方法充分利用了HDFS“移動計算比移動數(shù)據(jù)更經(jīng)濟(jì)”的思想。用于迭代計算Pagerank向量，每次迭代跨度為2，Pk→Pk+2。

首先mapper把1和2階段的輸出AT和(AT)2作為輸入，每個mapper執(zhí)行之前判斷讀入文件塊的路徑，如果是AT輸入，則計算(1-d)e+d(1-d)ATe，針對每個目標(biāo)節(jié)點Key，其Value如公式⑹：

輸出結(jié)果文件就構(gòu)成了新的Pagerank向量Pk+2。

最后在所有Mapreduce階段運行完成后Run方法結(jié)束前，將新的Pagerank向量Pk+2保存在HDFS中作為靜態(tài)文件刪除之前保存Pk的靜態(tài)文件，以便于下次迭代中的Mapper配置階段讀取。這里我們使用到了Hadoop提供的重要應(yīng)用。

⑶ DistributedCache功能表示：DistributedCache可將具體應(yīng)用相關(guān)的、大尺寸的、只讀的文件有效地分布放置，用來放置應(yīng)用程序緩存執(zhí)行過程中所需的文件。DistributedCache在JobConf中通過URI或Path指定需要被緩存的文件。Mapredcue框架在作業(yè)所有任務(wù)執(zhí)行之前會把必要的文件拷貝到slave節(jié)點上。它運行高效是因為每個作業(yè)的文件只拷貝一次，并且為那些沒有文檔的slave節(jié)點緩存文檔。

3.4.3 算法的比較和擴(kuò)展

4 實驗分析

4.1 實驗數(shù)據(jù)集

針對本次實驗的目的是在云計算實驗環(huán)境下測試基于Mapreduce的Pagerank算法，所以需要選取具有大容量，百萬或者千萬節(jié)點級別的Web圖作為實驗測試數(shù)據(jù)。而鑒于實驗條件和實際情況很難同互聯(lián)網(wǎng)上爬到如此海量的Web網(wǎng)頁并把其解析為鏈接關(guān)系，因此我們利用了Stanford大學(xué)社會網(wǎng)絡(luò)研究平臺提供的Web圖數(shù)據(jù)作為本次實驗數(shù)據(jù)集。

4.2 實驗平臺搭建

基于Hadoop的分布式云環(huán)境可以有兩種模式，一種是基于單機的Hadoop偽分布式模式，一種是Hadoop完全分布式模式。Cygwin是一個在Windows平臺上運行的Linux模擬環(huán)境。由于Hadoop運行需要shell命令的支持，所以如果節(jié)點操作系統(tǒng)是Windows則需要先安裝Cygwin。

本次實驗使用Hadoop0.18.3版本，下載JDK版本jdk1.6.0_13，Hadoop的運行需要JDK的支持。開發(fā)環(huán)境是MyEclipse 6.6+IBM MapReduce eclipse plug-in。

由于實驗條件有限，本實驗只用了兩臺PC搭建云環(huán)境。在這兩臺PC中，我們使用PC1作為namenode和jobtracker，PC2作為Datanode和Tasktracker。配置每臺機器的/etc/hosts目錄，masters:192.168.10.1，slaves:192.168.10.1，192.168.10.2。在這兩臺機器上創(chuàng)建相同用戶名用戶，利用ssh-keygen生成PC1的密鑰對，然后將其公鑰拷貝至各機器home/gx/.ssh目錄下的.authorized文件下，使得從PC1可以完成到各機器的無密碼ssh登錄。

4.3 實驗結(jié)果分析

⑴ 執(zhí)行時間方面

由于分塊算法減少了數(shù)據(jù)條數(shù)，每條記錄節(jié)省了用于表示網(wǎng)頁節(jié)點號Integer類型記錄，所以分塊法相比傳統(tǒng)方法每塊節(jié)省了（塊大小-1）×4byte容量。表2顯示了兩種算法針對不同數(shù)據(jù)集生成中間文件大小比較。

傳統(tǒng)Pagerank算法需要將鄰接矩陣存入到內(nèi)存中以迭代計算Pagerank向量，而基于Mapreduce的Pagerank計算由于每次迭代都需涉及讀取和寫入HDFS的大量I/O操作，因此在Web圖數(shù)據(jù)集比較小的相同條件下，傳統(tǒng)方法速度上比并行方法有很大優(yōu)勢。但是傳統(tǒng)方法的問題在于，對于需要保存在內(nèi)存中的鄰接矩陣，如果其規(guī)模達(dá)到了n×n×4byte大于內(nèi)存容量的時候，程序便無法運行。對于本次實驗最小31M的數(shù)據(jù)集節(jié)點數(shù)為28萬，鄰近矩陣內(nèi)存占用了28×28×108×4byte，要遠(yuǎn)遠(yuǎn)大于32位機器所能表示的最大4GB的內(nèi)存空間，因此以上數(shù)據(jù)集都無法在傳統(tǒng)算法上運行。這也體現(xiàn)出了基于云計算的算法優(yōu)勢。

5 結(jié)束語

本文在云環(huán)境下對Web結(jié)構(gòu)挖掘中Pagerank算法進(jìn)行研究，針對基于Mapreduce的并行Pagerank算法運行大數(shù)據(jù)集時存在的問題提出了改進(jìn)算法。實驗結(jié)果表明，改進(jìn)后的算法分別在結(jié)果集的空間占用和總迭代時間方面具有一定的優(yōu)越性。本文的工作對于進(jìn)一步研究云計算以及將相關(guān)理論應(yīng)用于云計算領(lǐng)域具有很大的借鑒意義。