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

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

1.引言

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

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

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

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

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

*計算Web頁面Reputation；

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

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

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

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

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

3.獨立于查詢的算法——PageRank

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

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

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

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

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

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

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

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

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

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

4.結(jié)語

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

參考文獻：

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

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

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

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