基于主題相似度改進的PageRank 算法研究*

劉 齊 黃樹成

（江蘇科技大學計算機學院 鎮(zhèn)江 212000）

1 引言

隨著互聯(lián)網技術的快速發(fā)展，用戶獲取信息的途徑越來越多，但面對龐大的信息資源，如何快速準確地獲取對自己有用的信息成為一個難題。在Web數(shù)據挖掘技術的支撐下，個性化信息推薦技術已經成為提高信息利用率和信息服務水平的一種有效工具［1］。通過分析網頁間的鏈接關系，結合用戶搜索主題，能為用戶提供更全面、更精確的信息。

在眾多搜索引擎技術所采用的算法中，超鏈接分析技術是很多學者研究的方向，其中以Google采用的PageRank 算法最為著名。從實際應用來看，該算法能有效地幫助用戶搜尋目標網頁，提高了信息檢索效率，但仍然存在主題漂移、偏重舊網頁等不足［2］。

因此，本文提出了一種基于相似度和時間因子的改進算法，改進后的PageRank 算法能有效改善主題漂移和偏重舊網頁兩個方面的不足。

2 PageRank相關研究

2.1 PageRank算法

PageRank 算法是Google 用于搜索的網站排名算法，是根據網頁超鏈接相互關系來衡量網頁重要性的測量算法，其算法核心思想是：被許多網頁或者比較權威的網頁鏈接的網頁也是重要的網頁［3］。

PageRank 算法簡單描述如下：假設Sv作為網頁u的入鏈集合，頁面v的出鏈數(shù)量為N，該網頁的PageRank 值為PR(v)，那么頁面v每個出鏈的權值為PR(v)/N，然后將頁面u所有入鏈網頁的PR 值相加，就可得到該網頁的PR 值［4］。計算公式如下：

式（1）就是網頁PR 值計算的基本公式。但在現(xiàn)實網絡中，存在鏈入和鏈出為零或者環(huán)形鏈路的情況，這就會造成等級下沉（Rank Sink）和等級泄露（Rank Leak）的現(xiàn)象，導致PR 值異常［5］。為了解決這一問題，對PageRank 的計算公式進了改進，加入了隨機跳轉模型的概念，該模型假設用戶瀏覽網頁時，隨機跳轉到其他頁面的概率為(1-d)，用戶繼續(xù)在當前頁面或者當前頁面的鏈接中瀏覽的概率為d，則網頁PR值計算公式如下：

式（2）中，d也稱為阻尼系數(shù)，一般取值為0.85。從計算公式可以看出，PageRank 算法判定網頁的權威性僅依賴于網頁的鏈接關系，忽略了主題內容、時效等方面的因素，雖然在一定程度上可以衡量出該網頁的重要程度，而且各頁面PR 值的計算過程是在離線時就已經完成，能有效提高查詢效率和響應時間，但仍然存在主題漂移和偏重舊網頁的不足之處。

2.2 PageRank算法現(xiàn)有改進

針對PageRank 算法存在的問題，越來越多的學者開始對該算法進行研究，對存在的不足之處提出了不同的改進方法。有學者提出基于用戶興趣的改進方法，收集分析用戶的使用數(shù)據，判斷用戶的興趣方向，能提高推薦內容的準確度；另一個改進方向是從頁面相似度出發(fā)，目前主要分為兩個類別，一種是利用空間向量模型對本頁面和鏈入頁面進行相似度計算，給相似度大的頁面分配更多的權值，解決平均權值的問題；另一個方向是基于內容過濾的改進方法，對頁面錨文本和HTML 標簽等進行計算，使查詢結果更加準確［6～8］。這些方法，都在一定程度上解決了主題漂移的問題。

3 改進的PageRank算法

本文在分析上述改進思想的基礎上，從主題漂移和偏重舊網頁兩個方面進行改進，對頁面和正向鏈接頁面的關鍵字進行提取，引入新的BM25 概率檢索模型進行主題相似度的改進，然后通過相似度給正向鏈接分配合理的PR值。

3.1 基于相似度的改進

網頁的PR 值就是網頁在排序時的重要依據，主要參考了鏈入網頁數(shù)量和鏈入網頁重要性兩個因素，本文在此基礎上增加了主題相似度的影響因子。改進的主要思想是：一個網頁的主題內容與它正向鏈接的網頁主題越相關，則分配的PR 值就越大［9］。

傳統(tǒng)相似度的比較，大多使用空間向量模型（VSM）來計算，而本文選用了一種準確率更高的文本相似度計算方法——BM25 文本相似度算法，基于TF-IDF 改進而來［10］。該算法的基本思想是：計算查詢內容和文檔的相關度，先將查詢內容進行語素解析，計算各個語素和查詢文檔的相關性得分，然后進行加權計算得到最終的結果。BM25算法的一般性公式如下：

式（3）中，q是給定的查詢內容，qi是其中的某一個語素，D是查詢的文檔。Score(D，q)就是所需要計算的評分。其中IDF計算公式如下：

式（4）中，N為索引中的全部文檔數(shù)，n(qi)為包含了qi的文檔數(shù)。式（3）中，R(qi，D)表示語素qi與文檔D的相關性得分，其公式如下：

式（5）中，k1，b為調節(jié)因子，也稱為經驗參數(shù)，通常參數(shù)設置為：k1=2，b=0.75。fi為qi在文檔D中出現(xiàn)的頻率，dl為文檔D的長度，avgdl為所有文檔的平均長度。

綜上可得，BM25算法的相關性得分公式為

從BM25 概率檢索模型的計算公式中可以看出，該算法在計算相似度的時候，不僅考慮了單詞在查詢文檔中的權值，還考慮了單詞在搜索內容中的權重［11］。用IDF 的值表示單詞的權值，但詞頻和相關性不是線性關系，所以增加了單詞和文檔相關性的計算。每一個詞對于文檔相關性的分數(shù)不會超過一個特定的閾值，所以我們做了標準化的處理，即R(qi，D)的計算，得到單詞在文檔中的權重。對于兩個頁面來說，匹配詞d 在文檔Q 中的權重越大且出現(xiàn)的次數(shù)越多，則它們的主題越相關。Score(q，D)的值也就越大，但是由于受到閾值影響，一般會收斂于特定值。

3.2 基于時間因子的改進

針對新出來的高質量的網頁，由于出現(xiàn)時間比較晚，鏈入它的網頁自然較少，這會導致該網頁的PR 值較低從而影響它最終的推薦順序。針對這一問題，本文采用時間反饋因子對舊網頁進行PR 值的補償，即在PageRank 計算公式中加入時間反饋因子Wt，該方法的基本思想是：如果網頁在同一搜索周期內被搜索到多次，也只算一次。這樣對于新發(fā)布的網頁來說，在計算PR值時，可以獲得較大的時間因子，從而補償因鏈入網頁數(shù)量較少導致PR值過低的現(xiàn)象［12］。其計算公式如下：

式（7）中，e T即為網頁時間反饋因子的計算表達式，表示網頁被搜索引擎搜索到的頻次，e通常取0.15n，n為網頁總數(shù)，且e的大小不影響最后的PR值的分布，但影響算法迭代過程，能有效改善新網頁PR值過低的情況。

3.3 改進后的算法

基于相似度和時間因子改進的基本思想為：根據當前網頁及所鏈接網頁的相似度分配PR 值，不采取平均分配的策略，同時加入時間反饋因子對新網頁進行補償。

改進后的計算公式如下：

式（8）中，Sv代表指向網頁u的集合；Topic(Q，v)用來計算查詢內容和查詢結果相似度的評分，α是用來調節(jié)該評分影響權重大小的參數(shù)，一般取值為0.3；Wt為網頁u的時間反饋因子。從改進后的計算公式可以看出，網頁u的PR值，除了有鏈入網頁v的貢獻，還有檢索排名的過程中，查詢主題相關度和時間因子的貢獻。

4 實驗結果與分析

4.1 實驗步驟

為了驗證改進后的PageRank 算法的正確性和有效性，本文使用了Nutch、Lucene 和MyEclipse 等工具來搭建實驗環(huán)境，從搜狐新聞門戶網站（http：//news.sohu.com/）爬取網頁，作為實驗數(shù)據，驗證算法的綜合效果［13］。主要步驟如下：

1）通過在Windows環(huán)境下安裝Cgywin工具，使用Nutch 在網站上抓取約5000 個頁面，進行去重、去除無效信息等預處理。

2）提取網頁的頁面內容、標題摘要及關鍵字等，為每個頁面建立一個關鍵字列表，過濾沒有關鍵字列表的頁面。

3）用Java 語言分別實現(xiàn)傳統(tǒng)的PageRank 算法和改進后的PageRank 算法，對每個網頁計算其PR值。

4）使用Lucene 工具進行全文檢索，模擬用戶輸入不同的關鍵字進行查詢，比較兩種算法下查詢得到的頁面排序情況。

4.2 實驗方案

本文中的實驗結果評估指標主要有兩項：準確率和權威值［14］。

數(shù)據準備階段，對門戶網站上爬取的結果建立相關索引并將其存入數(shù)據庫中，索引簡歷后對關鍵字進行搜索，并用傳統(tǒng)的PageRank 算法和改進后的PageRank 算法計算網頁的PR 值，將這些PR 值保存到數(shù)據庫中。在模擬用戶對關鍵字進行查詢時，根據需要找到的文件，按照PR值的降序返回結果［15］。

設計三組對比試驗來驗證，首先，對主題“閱兵”搜索到的網頁進行PR 值的計算，分別用原始PageRank 算法和改進的PageRank 算法，對比排序結果前八的網頁的PR值分布情況；其次，對“閱兵”主題的排序結果進行準確度統(tǒng)計，統(tǒng)計兩種算法下，推薦頁面中符合查詢結果的頁面數(shù)量；最后，對多個主題進行準確度驗證，檢驗多個主題下改進算法的準確度。

4.3 結果分析

實驗一，以“閱兵”為主題查詢結果選取前8 個頁面，分別按照A-H 編號，各頁面之間的鏈接關系如圖1所示。

圖1 以“閱兵”為主題的頁面鏈接關系

利用傳統(tǒng)PageRank 算法和改進后的PageRank算法計算得到的PR值如表1所示。

表1 兩種算法得到的PR值

從圖1和表1中可以看出來，所選頁面里PR值最高的是H頁面，其次為F、G。由表1可以看出，較原始算法，改進后的算法給每個頁面的PR 值出現(xiàn)了變化，例如頁面A、頁面B和頁面D等，PR值都有所降低，相反，頁面H、頁面F和頁面G等PR值都有所升高。這是因為在采用根據相似度分配PR 值后，不再是平均權值，所以一些主題差異較大的頁面獲得的PR 值較之前更少，而相似度高的所獲PR值較之前更多。

實驗二，在實驗一的基礎上，針對“閱兵”主題，分析了傳統(tǒng)PageRank 算法和加入主題相似度的算法、同時加入主題相似度和時間因子的算法的排序結果。計算返回的前N 個頁面中符合要求的網頁的數(shù)量分布情況。橫坐標表示的是在返回結果中PR 值排在前N 張的網頁；縱坐標表示的是在前N張網頁中符合要求的網頁數(shù)量。實驗結果如圖2。

從圖2 中可以看出，隨著返回結果頁面數(shù)的增加，加入主題相似度的改進后，符合要求的網頁數(shù)都要比原始PageRank 算法多，即準確率更高。而加入了時間反饋因子后，準確率小幅提高，這是因為排序結果中會出現(xiàn)一些PR值偏低的質量高的新網頁，而時間因子的出現(xiàn)不會影響算法的迭代，只是在PR值上有所補償。

圖2 改進因子對查詢準確率的影響

實驗三，對多個主題進行查詢結果分析，對比原始算法、增加主題相似度和同時增加主題相似度和時間因子的結果，分別取各主題排序的前100 個頁面，分析其返回結果符合主題的情況。實驗結果如圖3所示。

圖3 不同主題符合查詢結果分布情況

從圖3的結果來看，本文改進后的PageRank算法與傳統(tǒng)的PageRank 算法相比，改進后的算法在不同主題中返回的結果符合查詢主題要求的網頁數(shù)量都要多于傳統(tǒng)算法，即準確率更高。

5 結語

本文在分析傳統(tǒng)PageRank 算法存在的不足上，采用BM25 概率檢索模型進行相似度的改進，在一定程度上優(yōu)化了主題漂移的現(xiàn)象；加入時間反饋因子Wt，解決了偏重舊網頁的問題。通過實驗證明，改進后的算法在一定程度上提升了網頁的準確度，改善了新網頁PR 值分配偏低的問題。接下來在此基礎上，會繼續(xù)對改進的算法進行更深一步的研究，由于該算法在查詢時需要計算相似度，在數(shù)據量更大的情況下，時間性能有待研究。