普措才仁 齊愛琴

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

【關(guān)鍵詞】改進(jìn)PageRank 算法 網(wǎng)頁主題相關(guān)度 主題漂移

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

1 基于傳統(tǒng)Page Rank算法的改進(jìn)

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

2 改進(jìn)的網(wǎng)頁主題相關(guān)度算法

網(wǎng)頁排序算法的指導(dǎo)思想是，當(dāng)用戶隨機(jī)檢索的網(wǎng)頁T中存在鏈出鏈接指向網(wǎng)頁A，將頁面T的重要性賦予網(wǎng)頁A。該算法將定向連接的網(wǎng)絡(luò)定義為設(shè)有向圖G=

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

2.1 改進(jìn)主題權(quán)重PageRank算法

在經(jīng)典網(wǎng)頁排序算法的基礎(chǔ)上提兩點(diǎn)改進(jìn)，同時(shí)引入主題相關(guān)度和權(quán)重影響因子提高網(wǎng)頁排序質(zhì)量，改進(jìn)后依據(jù)主題相關(guān)度和鏈接權(quán)重的算法（ Topic WeightedPagerRank，TEPR），描述如下。

網(wǎng)頁超鏈接用Link（i，j）描述，表示網(wǎng)頁i與網(wǎng)頁j的超鏈接關(guān)系。鏈出度用Out（i）描述，指頁面i指向的超鏈接總數(shù)，鏈入度In（i）描述，表示其他頁面指向網(wǎng)頁節(jié)點(diǎn)i的超鏈接總數(shù)。

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

2.2 基于網(wǎng)頁主題相關(guān)度和權(quán)重的算法步驟

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

3 實(shí)驗(yàn)測試與結(jié)果分析

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

傳統(tǒng)的PageRank算法主要存在主題漂移、網(wǎng)頁權(quán)值平均以及新網(wǎng)頁更新較少的問題，改進(jìn)后的算法加入主題相關(guān)限度因子和重要性權(quán)重，提出一種基于主題相關(guān)性權(quán)重的改進(jìn)算法，并將其應(yīng)用在新聞?dòng)脩糁黝}詞搜索的排序中，文章根據(jù)主題爬蟲采集軟件進(jìn)行測試，并對結(jié)果進(jìn)行分析。測驗(yàn)結(jié)果表明改進(jìn)后的算法具有較好的排序效果，并可以應(yīng)用在跟大規(guī)模的數(shù)據(jù)集上。

4 結(jié)束語

本文主要在傳統(tǒng)超鏈接網(wǎng)頁排序算法的基礎(chǔ)上既考慮關(guān)鍵詞和網(wǎng)頁的主題相關(guān)度也考慮網(wǎng)頁鏈接重要性，從網(wǎng)頁鏈接權(quán)重和主題相關(guān)度提出改進(jìn)的排序算法，測試結(jié)果表明，質(zhì)量較高網(wǎng)頁排序提前，改進(jìn)后算法在應(yīng)用中縮短搜索時(shí)間，提高搜索準(zhǔn)確率。實(shí)際網(wǎng)頁排名的影響因素很多，今后將會(huì)對其他影響因素進(jìn)行改進(jìn)，為用戶提供更高質(zhì)的搜索服務(wù)。

參考文獻(xiàn)

[1]周秋麗，基于改進(jìn)PageRank算法的網(wǎng)頁排序問題研究[D].哈爾濱理工大學(xué)，2016.

[2]楊格蘭，涂立.基于主題相關(guān)性和鏈接權(quán)重的PageRank算法[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，40 （Sl）： 300-303.

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

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