基于改進的Page Rank算法的網頁主題相關度分析研究

普措才仁 齊愛琴

摘要 基于鏈接分析的經典算法Page Rank，其頁面轉移概率被平均分配到鏈出頁面，新頁面鏈接較少，所以PR值較低，出現在最后反饋結果中的排序靠后，影響用戶信息獲取效率和準確度，而冗余信息對用戶的干擾使用是信息檢索領域探究的焦點。文章分析經典算法Page Rank的優缺點，并提出基于主題相關性的PageRank算法改進策略，實施重新排序，結果證明改進后的算法提高查詢效率和質量，具有良好的穩定性，具備可拓展性。

【關鍵詞】改進PageRank 算法 網頁主題相關度 主題漂移

信息技術的發展使網絡搜索引擎呈幾何式增長，而人們的搜索習慣還是喜歡依靠排名篩選有用的信息。利用超鏈接結構對網頁進行分析提出的Page Rank算法，是目前最權威的網頁排序算法，發展也最成熟，但應用缺陷也十分明顯，主要存在鏈出權重平均，沒有將鏈接的重要性考慮在內。忽略檢索詞和網頁主題的相關性，導致主體漂移。不能根據網絡動態及時更新，面對網絡提供的豐富資源，高質量的服務能提高用戶滿意度。在此基礎上進行改進，幫助用戶提高獲取信息的準確率成為搜索引擎的重要工作。

1 基于傳統Page Rank算法的改進

由于人們總是檢索新頁面而傳統計算算法提供的反饋結果不能滿足用戶需求，因此，浙江大學的黃教授提出基于時間反饋的PageRank改進算法。用戶對某類網頁進行檢索，如文獻檢索，由于互聯網上存在的時間越久，重要性信息的在結果中的排序也會不斷下降，在基礎網頁排序算法中考慮時間影響因素，最終反饋網頁的PR值也會結合信息發布時間長短動態浮動。但改進后的算法缺乏對網頁權威性的考慮，導致PR值分配不合理。反饋結果中鏈接的質量也是影響網頁排名和使用滿意度的重要因素，實時上鏈入或鏈出界面中鏈接的網頁越多越能吸引訪問者點擊頁面，因此，有學者基于網頁的結構提出網頁權重排序算法（WPR），分析網頁的重要性，然后給予不同權重，最終反饋的結果就會使重要性更高的網頁獲得較高的排序，但該算法沒有考慮信息更新的時間和網頁排名，因此，反饋結果多存在舊網頁，網頁時效性不高。學者黃德才提出基于主題相似度模型和虛擬文檔的主題相似度模擬的算法，極大的提高主題擬合度，確保用戶使用結果效率提高，減少主題漂移現象，且該算法不需要添加額外的文信息，基于時間復雜度的運算也不須考慮，就能提高服務質量和效率。

2 改進的網頁主題相關度算法

網頁排序算法的指導思想是，當用戶隨機檢索的網頁T中存在鏈出鏈接指向網頁A，將頁面T的重要性賦予網頁A。該算法將定向連接的網絡定義為設有向圖G=

（1）式中d為衰減系數，取值為[O，1]，一般衰減系數設定為0.85?；谟脩綦S機沖浪模型分析，假設用戶的網頁瀏覽行為隨機，則不斷隨機點擊某鏈接的概率為d，由于鏈出網頁的概率相同，所以該模式下用戶隨機沖浪至另一頁面的概率為l-d，概率也相同。頁面i指向的其它頁面用Fi表示，網頁Fi鏈出的數目用C（Fi）表示。

2.1 改進主題權重PageRank算法

在經典網頁排序算法的基礎上提兩點改進，同時引入主題相關度和權重影響因子提高網頁排序質量，改進后依據主題相關度和鏈接權重的算法（ Topic WeightedPagerRank，TEPR），描述如下。

網頁超鏈接用Link（i，j）描述，表示網頁i與網頁j的超鏈接關系。鏈出度用Out（i）描述，指頁面i指向的超鏈接總數，鏈入度In（i）描述，表示其他頁面指向網頁節點i的超鏈接總數。

其中頁面i指向所有頁面的集合為Fi，Fi={pl，p2.…，pn），n=Out （i）;集合Bi表示所有頁面指向頁面i，Bi={pl，p2¨.，pm}m=ln （i）?？梢约僭O某個用戶不關心頁面內容，在某一時刻h，隨機訪問某頁面i，則停止瀏覽該頁面并通過頁面i鏈接至頁面j的概率為

2.2 基于網頁主題相關度和權重的算法步驟

算法計算步驟簡述如下：首先，借用網絡蜘蛛獲取測試頁面的信息;其次，對干擾鏈接進行過濾，排除干擾，對不參與計算的頁面進行預處理;然后，在概率e情況下，計算任一頁面的鏈入和鏈出數量，獲取頁面的修改時間;接著，在計算基于主題相關度因素的概率轉移矩陣，運用公式（3）進行主題相關性評價。與主題相關度較小或者無關的網頁獲得的PR值較小，因此在反饋結果中的排序靠后;最后，計算改進后的PR值，根據PR值對結果進行重新排序，獲得最終PR值，并將最終搜索結果反饋給客戶。

3 實驗測試與結果分析

為了驗證主題相關度和權重因素對改進后算法服務質量的影響，進行了實驗測試，以新聞中心，騰訊網的網站進行測試，測試中采用爬蟲采集軟件進行爬行，一共獲得13296張有效的新聞圖片，并根據網站主頁的分類包括國內外新聞、社會、軍事、歷史、文化、旅游、公益等鍵入關鍵詞：微博、財經、考研、十九大、天壇、大學生、論語、孟子、姚明、體育。將經典網頁排序算法與改進后的主題權重網頁排序算法分別對上述10個主題進行檢索，并將最終檢索結果的前100項作為測試樣本。測試結果顯示，在網頁數量不斷增加時，改進后的主題權重算法耗時不斷減少，而反饋結果的準確率逐漸提高，并且基于網頁主題權重的排序算法具有較好的穩定性，具有拓展空間。

傳統的PageRank算法主要存在主題漂移、網頁權值平均以及新網頁更新較少的問題，改進后的算法加入主題相關限度因子和重要性權重，提出一種基于主題相關性權重的改進算法，并將其應用在新聞用戶主題詞搜索的排序中，文章根據主題爬蟲采集軟件進行測試，并對結果進行分析。測驗結果表明改進后的算法具有較好的排序效果，并可以應用在跟大規模的數據集上。

4 結束語

本文主要在傳統超鏈接網頁排序算法的基礎上既考慮關鍵詞和網頁的主題相關度也考慮網頁鏈接重要性，從網頁鏈接權重和主題相關度提出改進的排序算法，測試結果表明，質量較高網頁排序提前，改進后算法在應用中縮短搜索時間，提高搜索準確率。實際網頁排名的影響因素很多，今后將會對其他影響因素進行改進，為用戶提供更高質的搜索服務。

參考文獻

[1]周秋麗，基于改進PageRank算法的網頁排序問題研究[D].哈爾濱理工大學，2016.

[2]楊格蘭，涂立.基于主題相關性和鏈接權重的PageRank算法[J].華中科技大學學報（自然科學版），2012，40 （Sl）： 300-303.

[3]王旭陽，任國盛，基于用戶行為與頁面分析的改進PageRank算法[J]，計算機工程，2016 （02）：164-168.

[4]朱顥東，丁溫雪，楊立志等，微博環境下基于用戶行為與主題相似度的改進PageRank算法[J].計算機工程，2017 （05）：179-184.