薛娟

摘要：云計算是基于互聯(lián)網(wǎng)的一種超級計算模式，能夠為將Web中的所有數(shù)據(jù)信息集中在一起，為其提供各種服務(wù)。數(shù)據(jù)挖掘是獲取Web網(wǎng)頁中的有用的信息，隨著互聯(lián)網(wǎng)的快速發(fā)展，Web網(wǎng)頁中的數(shù)據(jù)信息量顯著增加，傳統(tǒng)挖掘算法已經(jīng)無法滿足用戶的實際需求，基于云計算的Web結(jié)構(gòu)挖掘算法，能夠打破傳統(tǒng)挖掘算法的桎梏，對于Web網(wǎng)頁信息和知識的發(fā)現(xiàn)提供了很大的便利。文章分析了云計算的特點(diǎn)以及服務(wù)模式，探析了一種基于云計算的Web結(jié)構(gòu)挖掘算法，即基于MapReduce的PageRank算法，以供參考。

關(guān)鍵詞：云計算；Web；結(jié)構(gòu)挖掘算法

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）06-0010-02

數(shù)據(jù)挖掘指的是對大量、復(fù)雜的數(shù)據(jù)信息進(jìn)行分析，然后從中獲取有用的數(shù)據(jù)信息?，F(xiàn)如今，重要的數(shù)據(jù)信息都儲存在Web網(wǎng)頁上，由此可見研究Web數(shù)據(jù)挖掘的重要性。但是，隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，Web網(wǎng)頁上的數(shù)據(jù)信息量不斷地增加，網(wǎng)絡(luò)環(huán)境也越來越復(fù)雜，想要從Web網(wǎng)頁中挖掘出有用的信息，傳統(tǒng)的節(jié)點(diǎn)計算、儲存算法已經(jīng)遠(yuǎn)遠(yuǎn)不能滿足需求，基于云計算的Web結(jié)構(gòu)挖掘算法，能夠有效地解決傳統(tǒng)算法存在的問題，例如，基于MapReduce的PageRank算法，以其強(qiáng)大的網(wǎng)絡(luò)數(shù)據(jù)信息獲取能力、計算能力、儲存能力，能夠更加快速、高效的挖掘、計算和儲存Web網(wǎng)頁的信息和知識。因此，文章針對基于云計算的Web結(jié)構(gòu)挖掘算法的研究具有非常重要的現(xiàn)實意義。

1 云計算的特點(diǎn)以及服務(wù)模式分析

1.1 云計算的特點(diǎn)

云計算是一種基于用戶需求，為用戶提供主動服務(wù)的超級計算模式。云計算能夠為用戶提供共享的服務(wù)模式，并且能夠支持多個用戶的不同需求。云計算能夠滿足不同規(guī)模的計算需求，由信息和資源處理中心對需求進(jìn)行快速的分析和調(diào)節(jié)，并進(jìn)行云計算。云計算采用按量計費(fèi)的方式，用戶不需要對沒有消費(fèi)的服務(wù)買單，這樣既能夠降低成本，又能夠避免造成浪費(fèi)。

1.2 云計算的服務(wù)模式分析

云計算的服務(wù)模式主要包括以下幾個方面：

1）IaaS，Infraslruelure as a Service——基礎(chǔ)設(shè)施即服務(wù)，根據(jù)用戶權(quán)限，可以直接方位云計算提供的網(wǎng)絡(luò)寬帶、分布式儲存、并行運(yùn)算等基礎(chǔ)設(shè)置，同時可以根據(jù)自己的需求，搭建負(fù)荷自己需求的平臺；

2）PaaS，Platform as a Service——平臺即服務(wù)，云計算能夠為用戶提供一個平臺，包括工具集與軟件開發(fā)語言，其能夠為用戶組建一個虛擬的操作系統(tǒng)，用戶根據(jù)自己的需求在該平臺上開發(fā)以及部署相應(yīng)的平臺與應(yīng)用；

3）SaaS，Software as a service——軟件即服務(wù)，用戶根據(jù)自己的需求，使用基于云計算架構(gòu)的應(yīng)用程序為自己服務(wù)，例如網(wǎng)絡(luò)儲存、在線表格、在線文檔、電子郵件等。

2 基于MapReduce的PageRank算法分析

2.1 基于MapReduce的PageRank算法的實現(xiàn)

2.1.1 算法數(shù)據(jù)準(zhǔn)備

按照鏈接結(jié)構(gòu)文件格式將文件轉(zhuǎn)換成針對每一個節(jié)點(diǎn)的出鏈接結(jié)構(gòu)文件，其中預(yù)處理數(shù)據(jù)包由網(wǎng)頁上的海量數(shù)據(jù)信息組成，在map執(zhí)行的過程中，按照map方法，生成所有起始節(jié)點(diǎn)的目標(biāo)點(diǎn)的，其中key表示起始節(jié)點(diǎn)，value表示目標(biāo)節(jié)點(diǎn)，每一個key為初始化PageRank值，然后輸出數(shù)據(jù)到HDFS。

2.1.2 算法的實現(xiàn)

PageRank算法輸出的每個節(jié)點(diǎn)，按照Map方法對輸入每一行記錄的目標(biāo)節(jié)點(diǎn)順序，按照每個key歸類MapReduce框架采集map方法對應(yīng)的value。按照reduce方法，將每一個key：頁面y，對的所有項進(jìn)行加和，然后帶入公式：Pk+1= dATPk+（1-d）（公式1）計算，其中，PK表示第k次迭代后的PageRank向量，AT表示矩陣的轉(zhuǎn)置矩陣，然后輸出所有頁面全新的PageRank，即獲得所有key初始化的PageRank值，在HDFS中儲存所有的計算結(jié)果，進(jìn)行下一次迭代計算。在迭代計算過程中，Mapper對所有起點(diǎn)的目標(biāo)點(diǎn)生成一個與之對應(yīng)的partial，然后把所有的partial傳送至Mapreduce中。

2.2 基于MapReduce的PageRank算法的改進(jìn)分析

2.2.1 迭代并行PageRank改進(jìn)算法分析

按照PageRank算法的傳統(tǒng)計算公式，推算PageRank算法的向量公式，即公式1，因此按照初始向量P0進(jìn)行向量Pk的遞推，過程表現(xiàn)為：

P1= dATP0+（1-d）e （公式2）

P2= d2（AT）2P0+d（1-d）ATe+（1-d）e （公式3）

Pk=+dk（AT）kP0+ dk-1（1-d）（AT）k-1e+…d（1-d）ATe+（1-d）e （公式4）

通過上述遞推過程，以跨度為2計算公式為：P2= d2（AT）2P0+d（1-d）ATe+（1-d）e

迭代并行PageRank改進(jìn)算法的過程表現(xiàn)為以下幾個方面：1）在計算之前，應(yīng)該先生成和跨度相關(guān)的鄰接矩陣，以k=2為例，采用MapReduce計算AT，根據(jù)MapReduce過程獲得（AT）2，MapReduce在迭代的過程中，以初始PageRank向量、AT以及（AT）2為輸入文件，最后生成相應(yīng)的PageRank向量，按照上述步驟進(jìn)行反復(fù)迭代，如圖1所示。按照“移動計算比移動數(shù)據(jù)更經(jīng)濟(jì)”的思想，應(yīng)該盡可能將被計算的數(shù)據(jù)儲存在原來的位置，避免出現(xiàn)數(shù)據(jù)大量移動的現(xiàn)象，這樣既能夠提高系統(tǒng)吞吐量，又不至于造成網(wǎng)絡(luò)的堵塞。因此，HDFS中儲存的AT以及（AT）2不會隨著迭代的改變而改變。當(dāng)k=2時，可將算法分為三個階段：1）輸入上述階段生成的鏈接構(gòu)成文件G，并用G代替鄰接矩陣的AT，將首列作為目標(biāo)節(jié)點(diǎn)，第i行，第j列節(jié)點(diǎn)用ATi，j表示；2）使用第一階段獲得的AT，生成相應(yīng)的鏈接結(jié)構(gòu)文件，然后獲得相應(yīng)的矩陣，通過計算獲得（AT）2；3）k=2，因此每次的迭代跨度都為2，采用迭代并行PageRank算法計算向量，輸入第一階段獲得的AT，計算d（1-d）ATe+（1-d）e，輸入第二階段獲得的（AT）2，計算d2（AT）2P0，獲得新的PageRank向量，并保存在HDPS中，再進(jìn)行下一次迭代計算。

2.2.2 矩陣分塊并行PageRank改進(jìn)算法分析

矩陣分塊并行PageRank改進(jìn)算法，用矩陣如圖2所示，Reduce階段的額外性能消耗，通常來自于排序階段與混合階段，如果在排序階段中存在眾多key關(guān)鍵詞，將會消耗了大量的時間，如果將塊大小設(shè)定為b，通過MapReduce處理之后的向量塊、數(shù)量塊等將會減少為1/b。采用矩陣分塊并行PageRank算法進(jìn)行改進(jìn)之后，一個向量塊能夠表示b條向量塊，而且改進(jìn)之后向量塊之間并不存在外鏈接的節(jié)點(diǎn)，因此不會生成相應(yīng)的記錄，這樣能夠有效的節(jié)省大量鄰接矩陣空間，從而降低儲存空間的消耗。同時，由于不需要記錄之前b條向量，記錄的總條數(shù)明顯降低，占用的內(nèi)存量顯著降低，進(jìn)而境地I/O消耗，由此可見其優(yōu)勢。

3 結(jié)束語

總而言之，Web網(wǎng)頁上的信息量顯著增加，并且日增長量呈指數(shù)級發(fā)展，面對如此多的數(shù)據(jù)信息和龐大的Web信息資源庫，想要從中獲得用戶所需要的信息和知識，其難度可想而知。文章探析的一種基于云計算的Web結(jié)構(gòu)挖掘算法，即基于MapReduce的PageRank算法，能夠更加快速、準(zhǔn)確地從Web網(wǎng)頁中提取用戶所需要的信息和知識。同時，基于云計算的Web結(jié)構(gòu)挖掘算法的研究和應(yīng)用尚處在初級階段，還需要從以下幾個方面進(jìn)行研究：

1）研究能夠在高壓力、高并發(fā)以及大容量的Web環(huán)境中運(yùn)行的K-span算法。

2）加強(qiáng)對Hadoop調(diào)度機(jī)制的深入研究，使Hadoop算法變得更加準(zhǔn)確、高效。

3）實現(xiàn)算法從單機(jī)平臺向云計算平臺的轉(zhuǎn)移，充分利用云計算高效、準(zhǔn)確的優(yōu)勢。

雖然上述幾個方面還需要我們深入的研究，但是，基于云計算的Web結(jié)構(gòu)挖局算法，以其強(qiáng)大的計算與儲存能力，受到社會各界的廣泛關(guān)注。

參考文獻(xiàn)：

[1] 倪靖. 一種基于云計算的Web結(jié)構(gòu)挖掘算法[J]. 電腦知識與技術(shù)， 2011，7（24）：5933-5935.

[2] 藍(lán)昊慧. 云計算在Web結(jié)構(gòu)挖掘算法中的運(yùn)用研究[J]. 計算機(jī)時代， 2012（10）：30-32.

[3] 李遠(yuǎn)方. 基于云計算的Web結(jié)構(gòu)挖掘算法研究[D]. 云南： 云南大學(xué)， 2011.

[4] 胡或， 封俊. HadooP下的分布式搜索引擎[J]. 計算機(jī)系統(tǒng)應(yīng)用， 2010， 19（7）： 24-26.

[5] 王鵬. 云計算的關(guān)鍵技術(shù)與應(yīng)用實例[M]. 北京： 人民郵電出版社， 2010.

[6] 陳修寬. 數(shù)據(jù)挖掘綜述[J]. 山東輕工業(yè)學(xué)院學(xué)報， 2009， 23（3）：8-23.