姜金川，王 沖

桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院，廣西 桂林541004

1 引言

伴隨著網(wǎng)絡(luò)信息技術(shù)的飛速發(fā)展，越來(lái)越多的信息資源出現(xiàn)在網(wǎng)絡(luò)上，如何高效、快速、便捷地向用戶(hù)提供相關(guān)信息以滿(mǎn)足他們的需求成為當(dāng)前搜索引擎的首要目標(biāo)。當(dāng)用戶(hù)提交檢索關(guān)鍵詞時(shí)，搜索引擎會(huì)返回大量的搜索結(jié)果集，用戶(hù)需要從這些返回的結(jié)果集中搜尋自己需要的信息，這無(wú)疑會(huì)浪費(fèi)大量的時(shí)間。Page和Brin[1]提出的PageRank算法被用于Google搜索引擎中，它通過(guò)分析鏈接來(lái)衡量頁(yè)面的重要性。雖然PageRank算法已成功運(yùn)用于Google中，但是它仍然存在一個(gè)問(wèn)題：在實(shí)際的網(wǎng)頁(yè)中，網(wǎng)頁(yè)中的某些鏈接可能比其他鏈接更重要。

本文通過(guò)對(duì)經(jīng)典PageRank算法進(jìn)行深入的研究分析，發(fā)現(xiàn)PageRank算法主要存在以下不足：（1）由于與查詢(xún)關(guān)鍵詞無(wú)關(guān)而導(dǎo)致查詢(xún)到的網(wǎng)頁(yè)P(yáng)R值高但是不符合用戶(hù)檢索意向的主題漂移問(wèn)題；（2）對(duì)鏈接到本頁(yè)面的網(wǎng)頁(yè)不考慮網(wǎng)頁(yè)權(quán)威度而采用的平分鏈接權(quán)重的問(wèn)題；（3）忽略用戶(hù)瀏覽行為而造成的忽略用戶(hù)興趣問(wèn)題；（4）由于舊網(wǎng)頁(yè)在網(wǎng)絡(luò)中存在的時(shí)間長(zhǎng)，獲得網(wǎng)頁(yè)鏈接幾率更大，導(dǎo)致PR值越高的偏重舊網(wǎng)頁(yè)問(wèn)題。本文著重針對(duì)PageRank算法存在的平分鏈接權(quán)重和忽略用戶(hù)興趣問(wèn)題，提出了一種基于學(xué)習(xí)自動(dòng)機(jī)和用戶(hù)興趣的頁(yè)面排序算法LUPR（Page Rank based on Learning Automata and User Interest）。

本文首先介紹了PageRank算法、WPR算法以及相關(guān)改進(jìn)算法和學(xué)習(xí)自動(dòng)機(jī)。其次，對(duì)LUPR算法進(jìn)行了詳細(xì)的闡述，一方面使用學(xué)習(xí)自動(dòng)機(jī)確定網(wǎng)頁(yè)之間超鏈接的權(quán)重；另一方面通過(guò)對(duì)用戶(hù)行為的進(jìn)一步分析和提取，獲得興趣度因子。然后，通過(guò)MyEclipse、Heritrix和Lucene工具搭建仿真環(huán)境，對(duì)比實(shí)驗(yàn)驗(yàn)證排序質(zhì)量。最后對(duì)本文的改進(jìn)算法進(jìn)行了總結(jié)并給出了下一步的研究工作。

2 相關(guān)算法及技術(shù)

2.1 PageRank算法

PageRank算法[2]是一種基于網(wǎng)絡(luò)鏈接關(guān)系的網(wǎng)頁(yè)排序算法，在圖1中，節(jié)點(diǎn)代表網(wǎng)頁(yè)，箭頭表示各網(wǎng)頁(yè)間的鏈接關(guān)系。圖中V1存在一個(gè)指向U的箭頭，意味著網(wǎng)頁(yè)V1有一個(gè)前向鏈接是U，該算法認(rèn)為網(wǎng)絡(luò)中任意一個(gè)頁(yè)面的PageRank值是其反向鏈接的所有頁(yè)面貢獻(xiàn)值的累加和。如圖1所示，Vn有三個(gè)前向鏈接，則網(wǎng)頁(yè)Vn對(duì)U的貢獻(xiàn)值是Vn本身PR值的1/3。顯然，V本身的值越高，對(duì)U的貢獻(xiàn)值越大，并且U獲得的PR值越高，同時(shí)，頁(yè)面U反向鏈接的數(shù)量越多，U的PR值則越高。

圖1 PageRank原理圖

2.2 Weighted PageRank算法

Weighted PageRank算法[3]是Xing等人通過(guò)對(duì)網(wǎng)頁(yè)的鏈接結(jié)構(gòu)進(jìn)一步分析，綜合考慮了網(wǎng)頁(yè)的鏈入、鏈出結(jié)構(gòu)，提出的一種加權(quán)PageRank算法（WPR算法），它是PageRank算法的一種擴(kuò)展算法。傳統(tǒng)的PageRank算法僅僅考慮了網(wǎng)頁(yè)鏈接結(jié)構(gòu)中的鏈出結(jié)構(gòu)，而WPR算法不僅研究了網(wǎng)頁(yè)的鏈出結(jié)構(gòu)，也對(duì)網(wǎng)頁(yè)的鏈入結(jié)構(gòu)進(jìn)行了分析。WPR算法改善了傳統(tǒng)RageRank算法中的平分鏈接權(quán)重的不足，Xing等的研究表明，WPR算法較傳統(tǒng)的RageRank算法排序結(jié)果較為理想，但WPR算法仍然僅考慮了網(wǎng)頁(yè)的鏈接結(jié)構(gòu)，與傳統(tǒng)RageRank算法相比同樣存在著主題漂移、偏重舊網(wǎng)頁(yè)以及忽略用戶(hù)興趣的不足。

2.3 相關(guān)改進(jìn)算法

針對(duì)PageRank算法出現(xiàn)的主題漂移問(wèn)題，Tan[4]提出了一種基于向量空間的改進(jìn)PageRank算法，此算法將矢量空間檢索評(píng)估模型進(jìn)行了融合，考慮到網(wǎng)頁(yè)鏈接結(jié)構(gòu)和主題內(nèi)容的相關(guān)性，將主題內(nèi)容的相似度與經(jīng)典PageRank算法相結(jié)合，加權(quán)融合后得到新的PR值，但該算法未考慮到源網(wǎng)頁(yè)與出鏈網(wǎng)頁(yè)之間的權(quán)值分配問(wèn)題。Yang等人[5]提出了一種基于時(shí)間反饋和主題相似度的改進(jìn)PageRank算法，該算法通過(guò)添加頁(yè)面更新率因子、主題相關(guān)因子和網(wǎng)頁(yè)相似度對(duì)PageRank算法進(jìn)行改進(jìn)，但并未考慮用戶(hù)興趣對(duì)網(wǎng)頁(yè)排序的重要性。文獻(xiàn)[6]提出一種基于比率的加權(quán)PageRank算法，使用基于比率的方法在其引用的節(jié)點(diǎn)之間劃分節(jié)點(diǎn)的PageRank值，使每個(gè)節(jié)點(diǎn)根據(jù)其自身權(quán)重獲得相應(yīng)權(quán)值，但算法未考慮沒(méi)有出鏈的懸掛節(jié)點(diǎn)，顯然是不合理的。文獻(xiàn)[7]提出了一種基于資源分配（IPRA）的改進(jìn)PageRank算法，該算法雖然在定向網(wǎng)絡(luò)中識(shí)別了更具有影響力的網(wǎng)頁(yè)，但也大大提高了計(jì)算復(fù)雜度。針對(duì)忽略用戶(hù)興趣問(wèn)題，王旭陽(yáng)等[8]提出了基于用戶(hù)行為與頁(yè)面分析的改進(jìn)PageRank算法，該算法考慮了網(wǎng)頁(yè)瀏覽者對(duì)頁(yè)面的點(diǎn)擊行為，缺點(diǎn)是未對(duì)用戶(hù)的點(diǎn)擊次數(shù)做有效性驗(yàn)證。文獻(xiàn)[9]通過(guò)對(duì)不同用戶(hù)的已發(fā)表文章和轉(zhuǎn)載信息等內(nèi)容的相似性分析獲取用戶(hù)的關(guān)系結(jié)構(gòu)，但是因不同網(wǎng)頁(yè)瀏覽者的頁(yè)面?zhèn)鞑ニ俾什灰粯?，?duì)很少訪問(wèn)互聯(lián)網(wǎng)的人群影響力權(quán)值分配為0是不合理的，其次，存在數(shù)據(jù)識(shí)別問(wèn)題，其中由于用戶(hù)信息被盜取而導(dǎo)致的錯(cuò)誤信息被發(fā)布占據(jù)相當(dāng)大的比重。文獻(xiàn)[10]基于大量數(shù)據(jù)，該算法通過(guò)分析用戶(hù)的歷史行為給出相應(yīng)的用戶(hù)預(yù)測(cè)，從而獲得用戶(hù)關(guān)系結(jié)構(gòu)，但在提高用戶(hù)查詢(xún)準(zhǔn)確度的同時(shí)也增大了算法的時(shí)間復(fù)雜度。

2.4 學(xué)習(xí)自動(dòng)機(jī)（LA）

自動(dòng)機(jī)可以被看作是一個(gè)具有有限動(dòng)作集的抽象模型。學(xué)習(xí)自動(dòng)機(jī)[11-12]通過(guò)不斷地與隨機(jī)環(huán)境進(jìn)行交互并獲得經(jīng)驗(yàn)來(lái)改善其行為，隨機(jī)環(huán)境通過(guò)評(píng)估動(dòng)作，給出自動(dòng)機(jī)所選動(dòng)作的概率。自動(dòng)機(jī)使用來(lái)自環(huán)境的響應(yīng)（即動(dòng)作概率）來(lái)選擇其下一個(gè)動(dòng)作。通過(guò)繼續(xù)此過(guò)程，在可選動(dòng)作中選擇該環(huán)境下的最佳動(dòng)作。其工作原理如圖2所示。

圖2 學(xué)習(xí)自動(dòng)機(jī)工作原理圖

環(huán)境是一個(gè)三元組＜α,β,c＞，其中：α={α1,α2,…,αr}是學(xué)習(xí)自動(dòng)機(jī)的r個(gè)動(dòng)作集合；β={β1,β2,…,βm}代表環(huán)境的反應(yīng)集；c={c1,c2,…,cr}是r個(gè)動(dòng)作的懲罰概率，其中元素ci對(duì)應(yīng)于動(dòng)作集α中的動(dòng)作αi。學(xué)習(xí)自動(dòng)機(jī)的輸出集α中的αn在t=n時(shí)刻應(yīng)用于環(huán)境。

可變結(jié)構(gòu)學(xué)習(xí)自動(dòng)機(jī)[13]可由一組四元組＜β,α,T,P＞表示，其中α={α1,α2,…,αr}代表一組待選動(dòng)作；β={0,1}表示環(huán)境的反饋；其中0表示獎(jiǎng)勵(lì)，1表示懲罰；T是學(xué)習(xí)自動(dòng)機(jī)的更新規(guī)則；p(n+1)=T[α(n),β(n),p(n)]是學(xué)習(xí)算法。參數(shù)p是與α一一對(duì)應(yīng)的一組概率值，p={p1(n),p2(n),…,pr(n)}是動(dòng)作概率向量，其中pi(n)代表在時(shí)刻n選擇動(dòng)作αi的概率。在自動(dòng)機(jī)中，如果在第n階段選擇動(dòng)作αi并從環(huán)境中收到理想響應(yīng)，則pi(n)的概率增加，其他概率減小，反之pi(n)減少，其他概率增加。以下學(xué)習(xí)算法是更新動(dòng)作概率的方案，定義如下。

理想響應(yīng)：

非理想響應(yīng)：

分布式學(xué)習(xí)自動(dòng)機(jī)[14]（Distributed Learning Automata，DLA）是由一組相互協(xié)作的學(xué)習(xí)自動(dòng)機(jī)構(gòu)成的網(wǎng)絡(luò)，它們共同合作解決特定問(wèn)題。在DLA中，任何LA的動(dòng)作數(shù)量等于該LA所連接的LA數(shù)目（出邊數(shù)量）。當(dāng)自動(dòng)機(jī)選擇其中一個(gè)動(dòng)作時(shí)，將激活與此動(dòng)作相對(duì)應(yīng)的自動(dòng)機(jī)。任何時(shí)候網(wǎng)絡(luò)中只有一臺(tái)自動(dòng)機(jī)將會(huì)被激活。形式上，具有n個(gè)學(xué)習(xí)自動(dòng)機(jī)的DLA可以被描述為圖(V,E)。其中，V={LA1,LA2,…,LAn}是n個(gè)學(xué)習(xí)自動(dòng)機(jī)的集合，E是圖中邊的集合，邊(LAi,LAj)對(duì)應(yīng)于自動(dòng)機(jī)LAi的動(dòng)作αj即LAj經(jīng)LAi選擇動(dòng)作αj后被激活。

3改進(jìn)的PageRank算法：LUPR

算法包括兩個(gè)步驟，第一步計(jì)算基于學(xué)習(xí)自動(dòng)機(jī)的網(wǎng)頁(yè)之間每個(gè)超鏈接的權(quán)重，使用已存儲(chǔ)在日志文件中每個(gè)用戶(hù)導(dǎo)航路徑來(lái)計(jì)算網(wǎng)頁(yè)之間超鏈接的權(quán)重；第二步計(jì)算網(wǎng)頁(yè)興趣度因子，使用網(wǎng)頁(yè)瀏覽者搜索網(wǎng)頁(yè)的等待時(shí)長(zhǎng)以及瀏覽時(shí)長(zhǎng)，網(wǎng)頁(yè)的瀏覽時(shí)間越長(zhǎng)，在某種程度上可以代表網(wǎng)頁(yè)瀏覽者對(duì)此頁(yè)面越感興趣。

將wi→j定義為頁(yè)面i和j之間的超鏈接權(quán)重，這個(gè)權(quán)重由學(xué)習(xí)自動(dòng)機(jī)確定，將TD(k)定義為興趣度因子，該因子基于瀏覽網(wǎng)絡(luò)的用戶(hù)行為確定用戶(hù)的興趣度。將DLA視為N×N的矩陣，其中每一行表示一個(gè)網(wǎng)頁(yè)（引入自動(dòng)機(jī)i），每列j表示自動(dòng)機(jī)i的第j個(gè)動(dòng)作。矩陣M的每個(gè)元素mij的值是(1/N)，當(dāng)用戶(hù)進(jìn)入系統(tǒng)并瀏覽網(wǎng)頁(yè)P(yáng)i時(shí)，該頁(yè)面的學(xué)習(xí)自動(dòng)機(jī)（即LAi）被激活。當(dāng)用戶(hù)從頁(yè)面Pi移動(dòng)到Pj時(shí)，LAi自動(dòng)機(jī)中的動(dòng)作被選擇。根據(jù)馬爾科夫理論的特點(diǎn)和PageRank計(jì)算，所提算法公式如下所示：

其中，LAk是頁(yè)面k的學(xué)習(xí)自動(dòng)機(jī)，V(LAi,k)是LAi自動(dòng)機(jī)中動(dòng)作概率k的值，這個(gè)概率值顯示了網(wǎng)頁(yè)之間超鏈接的權(quán)重，TD(k)代表興趣度因子，參數(shù)m是網(wǎng)頁(yè)數(shù)量，d是阻尼系數(shù)，一般取值0.85[15]。

3.1 基于學(xué)習(xí)自動(dòng)機(jī)確定網(wǎng)頁(yè)間的超鏈接權(quán)重

網(wǎng)頁(yè)和用戶(hù)扮演DLA中現(xiàn)有學(xué)習(xí)自動(dòng)機(jī)的隨機(jī)環(huán)境的角色。在網(wǎng)絡(luò)中每個(gè)網(wǎng)頁(yè)P(yáng)i，即對(duì)應(yīng)一個(gè)學(xué)習(xí)自動(dòng)機(jī)LAi。如果網(wǎng)絡(luò)中有m個(gè)網(wǎng)頁(yè)，那么自動(dòng)機(jī)就有m-1個(gè)動(dòng)作。當(dāng)用戶(hù)從頁(yè)面Pi移動(dòng)到頁(yè)面Pj時(shí)，激活DLA中LAi自動(dòng)機(jī)的第j個(gè)動(dòng)作，并根據(jù)學(xué)習(xí)算法更新LAi自動(dòng)機(jī)的動(dòng)作概率向量。這個(gè)動(dòng)作概率向量顯示了網(wǎng)頁(yè)i和網(wǎng)頁(yè)j之間的超鏈接的權(quán)重。設(shè)pkm(n)為在時(shí)刻n時(shí)學(xué)習(xí)自動(dòng)機(jī)LAk選擇動(dòng)作αm的概率。如果用戶(hù)從頁(yè)面Dk移動(dòng)到頁(yè)面Dm(Dk→Dm)，則學(xué)習(xí)自動(dòng)機(jī)LAk根據(jù)學(xué)習(xí)算法更新其動(dòng)作概率向量。例如，如果學(xué)習(xí)自動(dòng)機(jī)LA1中的動(dòng)作向量和其動(dòng)作概率向量分別為(A2,A3,A4)，（0.2，0.5，0.3）用戶(hù)從D1移動(dòng)到D2，則：

那么LA1的動(dòng)作概率向量則更新為（0.35，0.42，0.23）算法描述如下：

（1）根據(jù)網(wǎng)頁(yè)結(jié)構(gòu)創(chuàng)建一個(gè)分布式學(xué)習(xí)自動(dòng)機(jī)DLA。

（2）對(duì)每個(gè)學(xué)習(xí)自動(dòng)機(jī)，初始化動(dòng)作概率向量。

（3）對(duì)用戶(hù)日志文件中每個(gè)用戶(hù)訪問(wèn)路徑，如果用戶(hù)從Dk移動(dòng)到Dm則根據(jù)如下學(xué)習(xí)算法更新LAk自動(dòng)機(jī)的動(dòng)作概率向量。

3.2 興趣度因子

興趣度因子主要是通過(guò)分析網(wǎng)頁(yè)沖浪者的搜索行為，獲取用戶(hù)搜索頁(yè)面時(shí)的行為信息。在關(guān)鍵詞Key下，對(duì)用戶(hù)訪問(wèn)過(guò)的網(wǎng)頁(yè)集合中的每個(gè)網(wǎng)頁(yè)，系統(tǒng)需要采集的用戶(hù)數(shù)據(jù)包括：（1）等待行為：用戶(hù)獲取頁(yè)面全部?jī)?nèi)容所需要等待的時(shí)間ts；（2）瀏覽行為：網(wǎng)頁(yè)處于激活狀態(tài)時(shí)普通人正常閱讀網(wǎng)頁(yè)的整個(gè)內(nèi)容繼而進(jìn)行評(píng)論和思考的時(shí)間。

用戶(hù)在頁(yè)面上花費(fèi)的時(shí)長(zhǎng)需要考慮網(wǎng)頁(yè)內(nèi)容和篇幅因素的影響，如果頁(yè)面瀏覽者對(duì)該網(wǎng)頁(yè)感興趣，則需要花費(fèi)更多的時(shí)間來(lái)瀏覽頁(yè)面，停留時(shí)間的長(zhǎng)短與頁(yè)面的文字、圖片及視頻的數(shù)量以及瀏覽者是否對(duì)該頁(yè)面感興趣等因素密切相關(guān)。當(dāng)用戶(hù)搜索到相關(guān)網(wǎng)頁(yè)時(shí)，獲取全部網(wǎng)頁(yè)內(nèi)容需等待的時(shí)間為ts，經(jīng)統(tǒng)計(jì)顯示，當(dāng)網(wǎng)絡(luò)通暢時(shí)，ts≤3 s，設(shè)置閾值平均時(shí)間ts=5 s，當(dāng)用戶(hù)的等待時(shí)間超過(guò)5 s時(shí)，用戶(hù)對(duì)頁(yè)面內(nèi)容的興趣度將減少，則可能在該網(wǎng)頁(yè)上的停留時(shí)間會(huì)相應(yīng)縮短。

設(shè)正常人閱讀完整個(gè)頁(yè)面的內(nèi)容并進(jìn)行思考和評(píng)論的時(shí)間為tc，其中tc的計(jì)算公式如下：

其中，Cw、Cp和Cv分別代表頁(yè)面正文文本量、頁(yè)面中圖片個(gè)數(shù)以及頁(yè)面視頻的個(gè)數(shù)。為了便于計(jì)算，這里將圖片與視頻依據(jù)其含義轉(zhuǎn)化為描述的文字量，分別近似于50和100個(gè)字，正常人一般閱讀速度為280字?jǐn)?shù)/min，k是評(píng)論系數(shù)，取值為1.2～1.5。興趣度因子的計(jì)算如下：

其中，tr是用戶(hù)訪問(wèn)當(dāng)前網(wǎng)頁(yè)的實(shí)際瀏覽時(shí)間；tr/tc是網(wǎng)頁(yè)瀏覽者的基本興趣度；(ts-5)×0.1為基本興趣度的偏移量。通過(guò)分析用戶(hù)的搜索行為，獲得用戶(hù)瀏覽頁(yè)面的行為信息，增加興趣度因子。

4 實(shí)驗(yàn)仿真

4.1 主要實(shí)驗(yàn)步驟

本文使用Java作為前端開(kāi)發(fā)，編譯環(huán)境使用MyEclipse、Lucene 3.0jar包和Heritrix等，對(duì)LUPR算法進(jìn)行實(shí)驗(yàn)仿真，步驟如下：

（1）用戶(hù)數(shù)據(jù)收集。使用Heritrix網(wǎng)頁(yè)爬蟲(chóng)工具從“巨細(xì)熱點(diǎn)網(wǎng)站”抓取5 000個(gè)IP用戶(hù)近一個(gè)月的訪問(wèn)信息。

（2）網(wǎng)頁(yè)數(shù)據(jù)收集。根據(jù)抓取的網(wǎng)頁(yè)數(shù)據(jù)，生成網(wǎng)頁(yè)鏈接結(jié)構(gòu)圖，獲取鏈接關(guān)系，將其作為記錄存入數(shù)據(jù)庫(kù)中。

（3）搭建MyEclipse實(shí)驗(yàn)平臺(tái)，在實(shí)驗(yàn)項(xiàng)目中添加Lucene 3.0jar包，添加中文分詞器IKAnalyzer3.2.8.jar包，配置相關(guān)停用詞，放在項(xiàng)目的根目錄中。

（4）在既定環(huán)境中，使用Java語(yǔ)言分別實(shí)現(xiàn)傳統(tǒng)的PageRank算法，WPR算法和本文提出的LUPR算法，LUPR算法在本實(shí)驗(yàn)中，k取1.35。

（5）比較并分析查詢(xún)得到的頁(yè)面。

4.2 實(shí)驗(yàn)結(jié)果

為了對(duì)比算法的優(yōu)越性，將用三種不同的查詢(xún)算法對(duì)同一查詢(xún)關(guān)鍵詞進(jìn)行實(shí)驗(yàn)分析，為了突出LUPR算法的優(yōu)越性，以下是可以顯著突出用戶(hù)查詢(xún)需求的關(guān)鍵字：“轉(zhuǎn)基因”。為了節(jié)省文章篇幅下面給出了查詢(xún)結(jié)果排名前十的排序結(jié)果。查詢(xún)結(jié)果如圖3～5所示。

圖3 PageRank基于“轉(zhuǎn)基因”關(guān)鍵詞查詢(xún)結(jié)果

圖4 WPR基于“轉(zhuǎn)基因”關(guān)鍵詞查詢(xún)結(jié)果

圖5 LUPR基于“轉(zhuǎn)基因”關(guān)鍵詞查詢(xún)結(jié)果

其中，圖3是完全基于鏈接關(guān)系的傳統(tǒng)PageRank算法基于“轉(zhuǎn)基因”關(guān)鍵詞的頁(yè)面排序結(jié)果，而圖4是改進(jìn)了權(quán)值均等分配缺點(diǎn)的WPR算法基于“轉(zhuǎn)基因”關(guān)鍵詞的網(wǎng)頁(yè)排序結(jié)果，可以看到WPR算法對(duì)于權(quán)威度高的網(wǎng)頁(yè)并沒(méi)有做出很大的調(diào)整，依然排在頁(yè)面很靠前的位置。圖5是本文的LUPR算法，可以看出與主題無(wú)關(guān)的網(wǎng)頁(yè)數(shù)量大大減少，完全與主題無(wú)關(guān)的網(wǎng)頁(yè)已經(jīng)退出了前十的位置；另外，排名前十的網(wǎng)頁(yè)中出現(xiàn)了9條和用戶(hù)查詢(xún)相關(guān)的網(wǎng)頁(yè)，PR值很高但是用戶(hù)興趣度不高的網(wǎng)頁(yè)得到了下降，例如：網(wǎng)頁(yè)標(biāo)題為“瑞士批準(zhǔn)埃博拉疫苗臨床實(shí)驗(yàn)”的網(wǎng)頁(yè)排名位置由PageRank算法的第1位下降到了第3位，而用戶(hù)興趣度高的網(wǎng)頁(yè)得到了提升，例如：圖5中的網(wǎng)頁(yè)標(biāo)題為“中國(guó)限制轉(zhuǎn)基因食品‘另有隱情’的用戶(hù)興趣度高的網(wǎng)頁(yè)（興趣指數(shù)TD(k)=1.100 034 5）已經(jīng)較PageRank算法的排名第24位（如圖6），WPR算法的第22位（如圖7），均有較大的提高。

圖6 PageRank排名第24位的網(wǎng)頁(yè)

圖7 WPR排名第22位的網(wǎng)頁(yè)

通過(guò)查準(zhǔn)率說(shuō)明本文LUPR算法的排序質(zhì)量。本文研究的查準(zhǔn)率是指通過(guò)小規(guī)模的仿真實(shí)驗(yàn)獲得的統(tǒng)計(jì)結(jié)果，其含義是，在采樣的樣本數(shù)量中用戶(hù)對(duì)查詢(xún)結(jié)果滿(mǎn)意的樣本數(shù)量占總樣本數(shù)量的百分比，是根據(jù)網(wǎng)頁(yè)瀏覽者的主觀判斷，確定查詢(xún)結(jié)果與瀏覽者需求相關(guān)度的一個(gè)衡量標(biāo)準(zhǔn)。其中對(duì)用戶(hù)評(píng)價(jià)分為四個(gè)不同級(jí)別：不滿(mǎn)意、較滿(mǎn)意、滿(mǎn)意、非常滿(mǎn)意，對(duì)結(jié)果為滿(mǎn)意、較滿(mǎn)意和非常滿(mǎn)意的頁(yè)面，就標(biāo)記該頁(yè)面為和用戶(hù)查詢(xún)主題相關(guān)的頁(yè)面。查準(zhǔn)率的計(jì)算公式如式（10）所示：

本實(shí)驗(yàn)為測(cè)試查詢(xún)結(jié)果中的前30個(gè)頁(yè)面，隨機(jī)選取1 217名學(xué)生進(jìn)行測(cè)試查詢(xún)信息，對(duì)5個(gè)查詢(xún)關(guān)鍵詞分別為“轉(zhuǎn)基因”、“蘋(píng)果手機(jī)”、“中國(guó)制造”、“食品安全”、“流行病”的查詢(xún)結(jié)果進(jìn)行測(cè)評(píng)，測(cè)試結(jié)果如圖8所示。

圖8 三種算法查準(zhǔn)率對(duì)比圖

通過(guò)選取更多的查詢(xún)關(guān)鍵詞，進(jìn)一步說(shuō)明本文LUPR算法的排序質(zhì)量。選取當(dāng)前社會(huì)熱點(diǎn)、網(wǎng)絡(luò)熱詞等與當(dāng)今社會(huì)息息相關(guān)的50個(gè)關(guān)鍵詞進(jìn)行測(cè)評(píng)，首先統(tǒng)計(jì)單個(gè)關(guān)鍵詞的查準(zhǔn)率，然后以5、10、20、30、50為單位逐步擴(kuò)大關(guān)鍵詞的個(gè)數(shù)，求取三種算法的平均查準(zhǔn)率，目的是為了消除個(gè)別關(guān)鍵詞的差異性，更好說(shuō)明LUPR算法的排序質(zhì)量，測(cè)試結(jié)果如圖9所示。

圖9 三種算法平均查準(zhǔn)率對(duì)比圖

用戶(hù)滿(mǎn)意度評(píng)估[16]：評(píng)估公式如公式（11）所示：

查詢(xún)結(jié)果分為四個(gè)不同級(jí)別：非常滿(mǎn)意、滿(mǎn)意、較滿(mǎn)意和不滿(mǎn)意。Si是滿(mǎn)意度系數(shù)，不同級(jí)別的滿(mǎn)意度系數(shù)分別是：1.0，0.6，0.2，0.0。其中n是頁(yè)面總數(shù)，在此實(shí)驗(yàn)中n是不同排序算法結(jié)果中的前30個(gè)頁(yè)面，i是計(jì)數(shù)器。通過(guò)用戶(hù)滿(mǎn)意度評(píng)估公式與算法測(cè)試結(jié)果，結(jié)果比較如圖10、11所示，可以看出改進(jìn)的LUPR算法在用戶(hù)滿(mǎn)意度上遠(yuǎn)遠(yuǎn)高于其他三種算法。

圖11 三種算法的用戶(hù)滿(mǎn)意度對(duì)比圖

仿真實(shí)驗(yàn)證明，LUPR算法在一定程度上可以提高網(wǎng)頁(yè)排序質(zhì)量、信息查詢(xún)的精準(zhǔn)度和用戶(hù)檢索的滿(mǎn)意度。

5 結(jié)束語(yǔ)

本文提出了一種基于學(xué)習(xí)自動(dòng)機(jī)和用戶(hù)興趣的頁(yè)面排序算法LUPR，該算法根據(jù)學(xué)習(xí)自動(dòng)機(jī)確定頁(yè)面間的超鏈接權(quán)重，以緩解PageRank算法平分鏈接權(quán)重問(wèn)題；考慮到網(wǎng)頁(yè)排序的結(jié)果不能僅僅依靠網(wǎng)頁(yè)的自身因素（網(wǎng)頁(yè)的權(quán)威性、重要性等），還應(yīng)該充分權(quán)衡網(wǎng)頁(yè)用戶(hù)的興趣度，通過(guò)對(duì)網(wǎng)頁(yè)瀏覽者行為的分析和提取，以瀏覽者的瀏覽行為衡量瀏覽者對(duì)頁(yè)面的興趣度，獲得興趣度因子。仿真實(shí)驗(yàn)表明，該算法在一定程度上提升了信息檢索的精準(zhǔn)度和用戶(hù)滿(mǎn)意度。下一步工作是考慮嘗試在學(xué)習(xí)自動(dòng)機(jī)中使用網(wǎng)頁(yè)相似度和用戶(hù)停留時(shí)間作為獎(jiǎng)勵(lì)進(jìn)行網(wǎng)頁(yè)排序，或使用可變動(dòng)作的學(xué)習(xí)自動(dòng)機(jī)對(duì)所提算法進(jìn)行改進(jìn)，這對(duì)于動(dòng)態(tài)網(wǎng)頁(yè)中頁(yè)面或鏈接的動(dòng)態(tài)變化將非常有用。