云計算在Web結構挖掘算法中的運用研究
2012-12-31 00:00:00藍昊慧
計算機時代 2012年10期
摘要： 在研究Web結構挖掘經典算法Pagerank和云計算關鍵技術Mapreduce的基礎上，將Pagerank算法與Mapreduce編程模型結合，針對基于并行Pagerank算法運行大數據集時面臨的每次迭代訪問HDFS導致I/O消耗增加、每次迭代在混合階段和排序階段時耗過多的問題提出了兩個改進算法。一個是利用矩陣分塊思想的并行Pagerank改進算法；另一個是減少HDFS訪問次數的并行Pagerank改進算法。最后利用Hadoop搭建云環境，在實驗環境下分析了不同的BlockSize參數對于計算性能的影響。并在云環境下面向不同的Web數據集，測試了原算法和改進算法的性能。結果表明，改進后的算法分別在結果集的空間占用方面和總迭代時間方面具有一定的優越性。
關鍵詞： 云計算； Web結構挖掘； 分布式計算； Mapreduce； Hadoop； Pagerank
中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228(2012)10-30-04
引言
Web結構挖掘是通過研究網頁之間的鏈接結構來發現網絡的組織結構和鏈接關系中隱藏的知識。隨著互聯網的迅猛發展和快速普及，Web上蘊藏的海量信息為數據挖掘提供了無比豐富的資源，而對Web信息進行有效的知識發現具有極大的挑戰性。云計算(cloud computing)是分布式處理、并行計算和網格計算的發展，或者說是這些計算機科學概念的商業實現。它是一種新興的共享基礎架構的方法，可以將巨大的系統池連接在一起以提供各種IT服務。很多因素推動了對這類環境的需求，其中包括連接設備、實時數據流、SOA的采用，以及搜索、開放協作、社會網絡和移動商務等這樣的Web2.0應用的急劇增長。鑒于云計算的發展前景，將相關領域的研究工作與云計算研究工作相結合是當前研究的一個熱點。本文的研究工作源于上述背景，目的是對Web結構挖掘技術進行深入的學習研究，探討Web結構挖掘中的關鍵算法PageRank，將Pagerank算法與云計算領域相關技術結合，改進算法，以使Web結構挖掘適應對海量數據分析與挖掘。經典的Web結構挖掘算法如Pagerank
1.1 Pagerank算法思想
Google的PageRank算法就是一種基于隨機網絡的檢索策略。假設讀者在Web上無目的瀏覽，其以1-d的概率沿本頁面的一個鏈接進行訪問，以d的概率輸入一個隨機的網址，這樣不同的網頁就有不同的訪問率。最終，那些入鏈很多的網頁就是流行網頁。在PageRank算法中，假定網頁P1…Pn有鏈接指向網頁A，設PR(A)，PR(P1)…PR(Pn)分別表示網頁A，P1…Pn的 PageRank值，參數d為一個跳轉系數，介于0～1之間，通常取0.85，o(A)被定義為A的出度，則網頁A的PageRank值PR(A)可由公式⑴計算得到。
1.2 Pagerank算法的不足和改進
⑴ 由于網頁數量劇增導致的Web圖鄰接矩陣擴大，而鄰接矩陣又多數是一個稀疏矩陣，造成了大量存儲資源和計算資源的浪費。
⑵ 隨著互聯網發展，網頁的信息已成為一種海量的數據，保存并計算網頁鏈接的關系也需要通過大型的并行系統實現，并且由于Pagerank算法需要多次迭代，所以Pagerank算法的并行化也成為必然。在Pagerank的并行算法的問題上已經有許多學者進行了研究，Google提出的MapReduce分布式計算框架已經被廣泛應用在了云計算平臺的部署上，因此，基于開源云計算基礎架構Hadoop將Pagerank算法與Mapreduce框架結合并對算法的運行效率、時空開銷、即收斂性加以研究，將會對開發部署在云計算平臺上的搜索引擎服務提供幫助。這也是本文研究的目的。
2 云計算與Mapreduce編程模型
2.1 云計算
云計算是新興的技術，目前還沒有標準化或規范。眾多IT廠商均在連續大力投資云計算的研究，推廣各自的云計算服務和產品。云計算的標準化研究、技術研究、服務產品完善以及各IT廠商的云計算技術和服務融合是一種趨勢。而MapReduce是云計算的關鍵技術之一，最先由Google提出的分布式計算構架，它可以支持大數據量的分布式處理[3]。
2.2 Mapreduce編程模型
Mapreduce由google提出，它是一種并行編程模型。用戶可利用Mapreduce將應用編程為相應的map和reduce操作，以實現應用的大規模并行化計算。
⑴ map：接收輸入數據被切片產生的
Map過程輸入輸出：
3 基于Mapreduce的并行Pagerank算法研究
3.1 算法提出
⑴ 隨著Web網頁趨向海量，Pagerank算法會造成巨大空間和性能開銷。
⑵ 基于Mapreduce原理，一方面可以解決海量Web網頁存儲的困難，另一方面還可將集中計算分布在集群中各節點上平攤計算消耗。
3.2 基于Mapreduce的Pagerank算法實現
Pagerank迭代階段的map方法對輸入文件中每一個行記錄的目標節點序列中每個目標節點的輸出為
Mapreduce框架收集map方法的輸出按每個key歸類其相應value。在reduce方法中，對每個key：頁面y，把其list of [partialx]中每一項加和，并帶入公式⑸得到并輸出每個頁面新的Pagerank。把結果保存在HDFS中，用作下一次迭代。并行Pagerank算法原理如圖1所示。
迭代階段Mapper實現對每個起始點x的目標點序列生成一個與目標點對應的partialx，并為其賦值為Pagerank(x)/目標節點的數量，最后將這些partialx發送給Mapreduce框架。
迭代階段Reducer完成對每個節點partialx的相加并計算新的Px=dPx+(1-d)，將新的Pagerank向量輸出到HDFS。
算法存在的問題：
⑴ 迭代過程執行速度方面
Map過程分為讀階段、緩沖階段和寫階段 ，Reduce過程分為混合階段、排序階段和約減階段。Reduce階段的額外性能消耗來自于混合階段和排序階段。當任務在排序階段處理的key關鍵字越多性能消耗就越大，如果計算Pagerank的過程中將網頁節點分塊表示將可以在排序階段把性能消耗降低到原來的1/分塊數。
⑵ 算法總迭代次數方面
Hadoop下的并行Pagerank算法由于每次迭代需要在集群間通信和訪問HDFS，達到所需收斂次數要花費大量時間。如果能夠減少并行Pagerank迭代計算的次數，增加每次迭代的計算量，也就減少了與迭代次數相關的大量通信和訪問HDFS的I/O操作的時間。
3.3 利用矩陣分塊思想的并行Pagerank算法
⑴ 算法思想
⑵ 矩陣分塊較4.2算法的優勢
在時間上，Reduce階段的額外性能消耗來自于混合階段和排序階段。當任務在排序階段處理的Key關鍵字越多性能的消耗就越大，將塊大小設為b時，Mapreduce處理的矩陣塊的數量和向量塊的條數就分別減少到了原來的1/b2和1/b，在第4章節兩種算法的運行時間對比中也可以看到其優勢。
在空間上，由于改進后的一條向量塊記錄可以代表之前b條向量的記錄，并且如果向量塊里的節點都無外鏈接，就無需生成此塊的記錄，這對于稀疏鄰接矩陣可以節省很多空間。因此可以極大地減少存儲中間結果時的空間消耗，在章節4將會對比兩種算法生成結果的占用空間。另一方面由于生成記錄的總條數減少，也就減少了內存的占用量，從而降低了在Map中因為中間信息超過緩沖區上限而Partition到本地磁盤并排序所造成的額外I/O消耗，以及Reduce過程因為待排序記錄超過內存容量而溢出到磁盤上對Key進行外部排序的可能。
3.4 低迭代并行Pagerank改進算法
3.4.1 算法分析
首先要分析Pagrank算法的原始計算公式并將該公式加以遞推，如公式⑶：
其中AT是公式⑶表示的矩陣的轉置矩陣，Pk為第k次迭代后的如公式⑵所表示的Pagerank向量。因此希望通過初始向量P0快速推導第k次迭代的向量Pk，遞推過程如下：
這里可以通過增加每次迭代Pagerank向量的計算量來達到盡量減少與迭代次數有關的集群節點間大量通信和訪問HDFS的I/O操作，來加快總的并行Pagerank算法的計算速度。本文將在后面詳細介紹該加速收斂過程的Mapreduce實現過程。
如公式⑸所表示，對于跨度為2的加速收斂計算P0→P2，可表示為：
3.4.2 算法實現過程
⑴ 首先要預先生成與跨度k有關的鄰接矩陣(AT)…(AT)5，因此當k=2時，第一步Mapreduce過程計算AT；第二步Mapreduce過程利用第一步中的AT計算出(AT)2；第三步Mapreduce過程每次迭代都將AT、(AT)2和初始Pagerank向量作為輸入文件，生成新的Pagerank向量。并在下次迭代中用新的Pagerank向量代替初始Pagrank向量，反復迭代下去直至結果收斂，如圖3所示。
圖3 加速收斂Mapreduce：Pagerank計算框架
⑵ “移動計算比移動數據更經濟”是HDFS的特點之一。按照這一思想，應盡量避免每輪迭代后修改或移動大數據文件，而最好保持輸入數據位置不變，以使要被計算的數據在所存儲的位置來進行計算，這樣可以消除網絡的擁堵，提高系統的整體吞吐量。因此，AT、(AT)2存儲在HDFS始終不隨迭代改變，如圖3中用Web圖表示的內容。Pagerank向量相對空間占用較小，所以每次迭代結束以新Pagerank向量帶取代舊值。這種實現方法充分利用了HDFS“移動計算比移動數據更經濟”的思想。用于迭代計算Pagerank向量，每次迭代跨度為2，Pk→Pk+2。
首先mapper把1和2階段的輸出AT和(AT)2作為輸入，每個mapper執行之前判斷讀入文件塊的路徑，如果是AT輸入，則計算(1-d)e+d(1-d)ATe，針對每個目標節點Key，其Value如公式⑹：
輸出結果文件就構成了新的Pagerank向量Pk+2。
最后在所有Mapreduce階段運行完成后Run方法結束前，將新的Pagerank向量Pk+2保存在HDFS中作為靜態文件刪除之前保存Pk的靜態文件，以便于下次迭代中的Mapper配置階段讀取。這里我們使用到了Hadoop提供的重要應用。
⑶ DistributedCache功能表示：DistributedCache可將具體應用相關的、大尺寸的、只讀的文件有效地分布放置，用來放置應用程序緩存執行過程中所需的文件。DistributedCache在JobConf中通過URI或Path指定需要被緩存的文件。Mapredcue框架在作業所有任務執行之前會把必要的文件拷貝到slave節點上。它運行高效是因為每個作業的文件只拷貝一次，并且為那些沒有文檔的slave節點緩存文檔。
3.4.3 算法的比較和擴展
4 實驗分析
4.1 實驗數據集
針對本次實驗的目的是在云計算實驗環境下測試基于Mapreduce的Pagerank算法，所以需要選取具有大容量，百萬或者千萬節點級別的Web圖作為實驗測試數據。而鑒于實驗條件和實際情況很難同互聯網上爬到如此海量的Web網頁并把其解析為鏈接關系，因此我們利用了Stanford大學社會網絡研究平臺提供的Web圖數據作為本次實驗數據集。
4.2 實驗平臺搭建
基于Hadoop的分布式云環境可以有兩種模式，一種是基于單機的Hadoop偽分布式模式，一種是Hadoop完全分布式模式。Cygwin是一個在Windows平臺上運行的Linux模擬環境。由于Hadoop運行需要shell命令的支持，所以如果節點操作系統是Windows則需要先安裝Cygwin。
本次實驗使用Hadoop0.18.3版本，下載JDK版本jdk1.6.0_13，Hadoop的運行需要JDK的支持。開發環境是MyEclipse 6.6+IBM MapReduce eclipse plug-in。
由于實驗條件有限，本實驗只用了兩臺PC搭建云環境。在這兩臺PC中，我們使用PC1作為namenode和jobtracker，PC2作為Datanode和Tasktracker。配置每臺機器的/etc/hosts目錄，masters:192.168.10.1，slaves:192.168.10.1，192.168.10.2。在這兩臺機器上創建相同用戶名用戶，利用ssh-keygen生成PC1的密鑰對，然后將其公鑰拷貝至各機器home/gx/.ssh目錄下的.authorized文件下，使得從PC1可以完成到各機器的無密碼ssh登錄。
4.3 實驗結果分析
⑴ 執行時間方面
由于分塊算法減少了數據條數，每條記錄節省了用于表示網頁節點號Integer類型記錄，所以分塊法相比傳統方法每塊節省了（塊大小-1）×4byte容量。表2顯示了兩種算法針對不同數據集生成中間文件大小比較。
傳統Pagerank算法需要將鄰接矩陣存入到內存中以迭代計算Pagerank向量，而基于Mapreduce的Pagerank計算由于每次迭代都需涉及讀取和寫入HDFS的大量I/O操作，因此在Web圖數據集比較小的相同條件下，傳統方法速度上比并行方法有很大優勢。但是傳統方法的問題在于，對于需要保存在內存中的鄰接矩陣，如果其規模達到了n×n×4byte大于內存容量的時候，程序便無法運行。對于本次實驗最小31M的數據集節點數為28萬，鄰近矩陣內存占用了28×28×108×4byte，要遠遠大于32位機器所能表示的最大4GB的內存空間，因此以上數據集都無法在傳統算法上運行。這也體現出了基于云計算的算法優勢。
5 結束語
本文在云環境下對Web結構挖掘中Pagerank算法進行研究，針對基于Mapreduce的并行Pagerank算法運行大數據集時存在的問題提出了改進算法。實驗結果表明，改進后的算法分別在結果集的空間占用和總迭代時間方面具有一定的優越性。本文的工作對于進一步研究云計算以及將相關理論應用于云計算領域具有很大的借鑒意義。
