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