ＰａｇｅＲａｎｋ算法在網(wǎng)頁(yè)搜索中的實(shí)現(xiàn)

摘 要： 本文首先介紹了Web結(jié)構(gòu)挖掘技術(shù)在Web中的應(yīng)用，其次陳述了Web結(jié)構(gòu)挖掘技術(shù)中的經(jīng)典鏈接分析算法PageRank，最后分析了PageRank在網(wǎng)頁(yè)搜索中具體實(shí)現(xiàn)的方法。

關(guān)鍵詞： Web結(jié)構(gòu)挖掘 PageRank算法 網(wǎng)頁(yè)搜索

1.引言

Web是人們獲取信息的重要資源之一，傳統(tǒng)的搜索引擎在技術(shù)上已經(jīng)不適應(yīng)海量的Web資源查詢，為解決Web搜索引擎所存在的問題，人們提出了Web數(shù)據(jù)挖掘概念，并在實(shí)踐中取得了很好的效果。

Web結(jié)構(gòu)挖掘，簡(jiǎn)稱WSM，指通過(guò)分析不同頁(yè)面之間的超鏈接結(jié)構(gòu)，網(wǎng)頁(yè)內(nèi)部的可以用XML、HTML表示成樹形結(jié)構(gòu)，以及文檔URL中的目錄路徑結(jié)構(gòu)等，發(fā)現(xiàn)許多蘊(yùn)涵在Web內(nèi)容之外的、對(duì)我們有潛在價(jià)值的模式和知識(shí)的過(guò)程。

目前WSM主要應(yīng)用有：

*搜索引擎查詢結(jié)果的排序；

*查找相關(guān)文檔；

*計(jì)算Web頁(yè)面Reputation；

*確定某站點(diǎn)的主要內(nèi)容和特征；

*Web Crawler的URL爬行的優(yōu)先順序。

2.WSM的鏈接分析技術(shù)

用戶在Web上使用搜索引擎進(jìn)行信息搜索時(shí)，最關(guān)心的并不是返回結(jié)果的多少，而是檢索結(jié)果是符合自己的需求。許多研究者發(fā)現(xiàn)，Web頁(yè)面的鏈接結(jié)構(gòu)是非常豐富和重要的資源，如果能夠充分利用，可以極大地提高檢索結(jié)果的質(zhì)量。

Web頁(yè)面有三個(gè)重要組成部分：網(wǎng)面內(nèi)容、網(wǎng)頁(yè)所含的超文本標(biāo)記及網(wǎng)頁(yè)間的超鏈接。一般說(shuō)來(lái)，Web文檔中的超鏈接包含了兩種信息：首先，它為用戶提供了瀏覽Web的導(dǎo)航信息，用來(lái)指引訪問者在各頁(yè)面之間跳轉(zhuǎn)；其次，頁(yè)面中的超鏈接往往是文檔作者對(duì)于某一文檔的推薦，被推薦的目的文檔往往與該文檔有相似內(nèi)容而且被作者所認(rèn)同。后者構(gòu)成了鏈接分析的基礎(chǔ)，即某一文檔的重要性不由文檔的內(nèi)容決定，而取決于被其他文檔鏈接（或者引用）的次數(shù)。這種評(píng)價(jià)機(jī)制類似于科學(xué)論文中的參考文獻(xiàn)：被引用次數(shù)多的論文其重要性比引用次數(shù)少的論文要高。在Web檢索中，除了被其他文檔鏈接的次數(shù)外，鏈接源文檔的質(zhì)量也是評(píng)價(jià)被鏈接文檔質(zhì)量的一個(gè)參考因子：被高質(zhì)量文檔鏈接或者推薦的文檔往往具有更高的權(quán)威性。這就是Web結(jié)構(gòu)挖掘中基于超鏈接結(jié)構(gòu)的鏈接分析技術(shù)的理論基礎(chǔ)。

3.獨(dú)立于查詢的算法——PageRank

PageRank算法是Web超鏈接結(jié)構(gòu)分析中最成功的代表之一，是評(píng)價(jià)網(wǎng)頁(yè)權(quán)威性的一種重要工具。搜索引擎Google就是利用該算法和anchor text標(biāo)記、詞頻統(tǒng)計(jì)等因素結(jié)合的方法對(duì)檢索出來(lái)的大量結(jié)果進(jìn)行基于權(quán)威值的排序處理，使最重要的網(wǎng)頁(yè)出現(xiàn)在結(jié)果的最前面。其中，PR值（權(quán)威度）越高的網(wǎng)頁(yè)，在結(jié)果中出現(xiàn)的位置越前。

PageRank的理論基礎(chǔ)是：忽略掉Web頁(yè)面上的文本和其它內(nèi)容，只考慮頁(yè)面間的超鏈接，把Web看成一個(gè)巨大的有向圖。

如果頁(yè)面u包含一個(gè)指向頁(yè)面v的超鏈接，即存在link(u，v)。這里頁(yè)面間的超鏈接構(gòu)成了一個(gè)有向圖G：對(duì)于每個(gè)頁(yè)面構(gòu)成有向圖G的一個(gè)節(jié)點(diǎn)；當(dāng)且僅當(dāng)u中包含指向頁(yè)面v的超鏈接時(shí)，存在著從u到v的有向邊（u，v）。有向圖G如圖1：

對(duì)于節(jié)點(diǎn)v來(lái)說(shuō)，節(jié)點(diǎn)b，c，u對(duì)于v的權(quán)值大小有貢獻(xiàn)，因?yàn)檫@三個(gè)節(jié)點(diǎn)都存在到v的有向邊。指向某一節(jié)點(diǎn)的有向邊越多，其節(jié)點(diǎn)（頁(yè)面）質(zhì)量越高。這種簡(jiǎn)單的算法的主要缺點(diǎn)是僅僅考慮的鏈接數(shù)量——所有的鏈接都是等價(jià)的，而沒有考慮源節(jié)點(diǎn)自身的質(zhì)量即權(quán)值高低。Web中文檔之間超鏈接的情況往往是高質(zhì)量的文檔中包含高質(zhì)量的鏈接，源節(jié)點(diǎn)的質(zhì)量對(duì)于被鏈接文檔質(zhì)量評(píng)價(jià)的作用往往高于數(shù)量上的影響。

為了解決鏈接數(shù)量和源節(jié)點(diǎn)的質(zhì)量問題，Sergey Brin和Lawrence Page提出了PageRank算法：某一Web頁(yè)面的PageRank值等于所有包含指向該頁(yè)面的源文檔的PageRank值與頁(yè)面鏈接總數(shù)之比的和，即：

outlink（j）為網(wǎng)頁(yè)集合j指向所有節(jié)點(diǎn)的超鏈接數(shù)目；

PR（v）為節(jié)點(diǎn)v的權(quán)威度。

PageRank算法的實(shí)現(xiàn)過(guò)程為：將網(wǎng)頁(yè)的URL對(duì)應(yīng)成唯一的整數(shù)，把每一個(gè)超鏈接用其整數(shù)ID存放到索引數(shù)據(jù)庫(kù)中，經(jīng)過(guò)預(yù)處理（如去除數(shù)據(jù)庫(kù)中的懸擺指針）之后，設(shè)每一個(gè)頁(yè)面的PR值為1，通過(guò)以上的遞歸算法計(jì)算每一個(gè)網(wǎng)頁(yè)的PR值，反復(fù)進(jìn)行迭代，直到結(jié)果收斂。

PageRank算法除了對(duì)搜索結(jié)果進(jìn)行排序外，還可以應(yīng)用到其它方面，如估算網(wǎng)絡(luò)流量，向后鏈接的預(yù)測(cè)器，為用戶導(dǎo)航等。

Google是結(jié)合文本的方法來(lái)實(shí)現(xiàn)PageRank算法的，所以只返回包含查詢項(xiàng)的網(wǎng)頁(yè)，然后根據(jù)網(wǎng)頁(yè)的PR值對(duì)搜索到的結(jié)果進(jìn)行排序，把PR值最高的網(wǎng)頁(yè)放置到最前面，但是如果最重要的網(wǎng)頁(yè)不在結(jié)果網(wǎng)頁(yè)集中，PageRank算法就無(wú)能為力了。

4.結(jié)語(yǔ)

在Web結(jié)構(gòu)挖掘中，對(duì)超鏈接的分析算法是重要的研究方向。“權(quán)威性”是鏈接分析算法的對(duì)頁(yè)面進(jìn)行自動(dòng)分析的重點(diǎn)，但目前的算法都是對(duì)不同的鏈接賦予相同的權(quán)重，如何根據(jù)文本內(nèi)容的相關(guān)性，為相應(yīng)的超鏈接賦予不同的權(quán)重，即把Web內(nèi)容挖掘和Web結(jié)構(gòu)挖掘進(jìn)行合理結(jié)合，是一個(gè)值得繼續(xù)深入研究的問題。

參考文獻(xiàn)：

［1］王曉宇，周傲英.萬(wàn)維網(wǎng)的鏈接結(jié)構(gòu)分析及其應(yīng)用綜述［N］.軟件學(xué)報(bào)，2003，14(10)：1768-1780.

［2］宋建康，張禮平.Web結(jié)構(gòu)挖掘算法探討［N］.華東理工大學(xué)學(xué)報(bào)，2003，28(5)：537-540.

［3］曹軍.Google的PageRankWeb技術(shù)剖析［N］.情報(bào)雜志，2002，10：15-18.

［4］WEB超鏈分析算法縱覽.http：//www.reeyee.org/news/20041025214603.htm.