基于學(xué)習(xí)自動(dòng)機(jī)和用戶興趣的PageRank算法研究

姜金川，王 沖

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

1 引言

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

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

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

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

2.1 PageRank算法

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

圖1 PageRank原理圖

2.2 Weighted PageRank算法

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

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

針對PageRank算法出現(xiàn)的主題漂移問題，Tan[4]提出了一種基于向量空間的改進(jìn)PageRank算法，此算法將矢量空間檢索評估模型進(jìn)行了融合，考慮到網(wǎng)頁鏈接結(jié)構(gòu)和主題內(nèi)容的相關(guān)性，將主題內(nèi)容的相似度與經(jīng)典PageRank算法相結(jié)合，加權(quán)融合后得到新的PR值，但該算法未考慮到源網(wǎng)頁與出鏈網(wǎng)頁之間的權(quán)值分配問題。Yang等人[5]提出了一種基于時(shí)間反饋和主題相似度的改進(jìn)PageRank算法，該算法通過添加頁面更新率因子、主題相關(guān)因子和網(wǎng)頁相似度對PageRank算法進(jìn)行改進(jìn)，但并未考慮用戶興趣對網(wǎng)頁排序的重要性。文獻(xiàn)[6]提出一種基于比率的加權(quán)PageRank算法，使用基于比率的方法在其引用的節(jié)點(diǎn)之間劃分節(jié)點(diǎn)的PageRank值，使每個(gè)節(jié)點(diǎn)根據(jù)其自身權(quán)重獲得相應(yīng)權(quán)值，但算法未考慮沒有出鏈的懸掛節(jié)點(diǎn)，顯然是不合理的。文獻(xiàn)[7]提出了一種基于資源分配（IPRA）的改進(jìn)PageRank算法，該算法雖然在定向網(wǎng)絡(luò)中識別了更具有影響力的網(wǎng)頁，但也大大提高了計(jì)算復(fù)雜度。針對忽略用戶興趣問題，王旭陽等[8]提出了基于用戶行為與頁面分析的改進(jìn)PageRank算法，該算法考慮了網(wǎng)頁瀏覽者對頁面的點(diǎn)擊行為，缺點(diǎn)是未對用戶的點(diǎn)擊次數(shù)做有效性驗(yàn)證。文獻(xiàn)[9]通過對不同用戶的已發(fā)表文章和轉(zhuǎn)載信息等內(nèi)容的相似性分析獲取用戶的關(guān)系結(jié)構(gòu)，但是因不同網(wǎng)頁瀏覽者的頁面?zhèn)鞑ニ俾什灰粯?，對很少訪問互聯(lián)網(wǎng)的人群影響力權(quán)值分配為0是不合理的，其次，存在數(shù)據(jù)識別問題，其中由于用戶信息被盜取而導(dǎo)致的錯(cuò)誤信息被發(fā)布占據(jù)相當(dāng)大的比重。文獻(xiàn)[10]基于大量數(shù)據(jù)，該算法通過分析用戶的歷史行為給出相應(yīng)的用戶預(yù)測，從而獲得用戶關(guān)系結(jié)構(gòu)，但在提高用戶查詢準(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]通過不斷地與隨機(jī)環(huán)境進(jìn)行交互并獲得經(jīng)驗(yàn)來改善其行為，隨機(jī)環(huán)境通過評估動(dòng)作，給出自動(dòng)機(jī)所選動(dòng)作的概率。自動(dòng)機(jī)使用來自環(huán)境的響應(yīng)（即動(dòng)作概率）來選擇其下一個(gè)動(dòng)作。通過繼續(xù)此過程，在可選動(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對應(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是與α一一對應(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ò)，它們共同合作解決特定問題。在DLA中，任何LA的動(dòng)作數(shù)量等于該LA所連接的LA數(shù)目（出邊數(shù)量）。當(dāng)自動(dòng)機(jī)選擇其中一個(gè)動(dòng)作時(shí)，將激活與此動(dòng)作相對應(yīng)的自動(dòng)機(jī)。任何時(shí)候網(wǎng)絡(luò)中只有一臺自動(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)對應(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)頁之間每個(gè)超鏈接的權(quán)重，使用已存儲(chǔ)在日志文件中每個(gè)用戶導(dǎo)航路徑來計(jì)算網(wǎng)頁之間超鏈接的權(quán)重；第二步計(jì)算網(wǎng)頁興趣度因子，使用網(wǎng)頁瀏覽者搜索網(wǎng)頁的等待時(shí)長以及瀏覽時(shí)長，網(wǎng)頁的瀏覽時(shí)間越長，在某種程度上可以代表網(wǎng)頁瀏覽者對此頁面越感興趣。

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

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

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

網(wǎng)頁和用戶扮演DLA中現(xiàn)有學(xué)習(xí)自動(dòng)機(jī)的隨機(jī)環(huán)境的角色。在網(wǎng)絡(luò)中每個(gè)網(wǎng)頁P(yáng)i，即對應(yīng)一個(gè)學(xué)習(xí)自動(dòng)機(jī)LAi。如果網(wǎng)絡(luò)中有m個(gè)網(wǎng)頁，那么自動(dòng)機(jī)就有m-1個(gè)動(dòng)作。當(dāng)用戶從頁面Pi移動(dòng)到頁面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)頁i和網(wǎng)頁j之間的超鏈接的權(quán)重。設(shè)pkm(n)為在時(shí)刻n時(shí)學(xué)習(xí)自動(dòng)機(jī)LAk選擇動(dòng)作αm的概率。如果用戶從頁面Dk移動(dòng)到頁面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）用戶從D1移動(dòng)到D2，則：

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

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

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

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

3.2 興趣度因子

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

用戶在頁面上花費(fèi)的時(shí)長需要考慮網(wǎng)頁內(nèi)容和篇幅因素的影響，如果頁面瀏覽者對該網(wǎng)頁感興趣，則需要花費(fèi)更多的時(shí)間來瀏覽頁面，停留時(shí)間的長短與頁面的文字、圖片及視頻的數(shù)量以及瀏覽者是否對該頁面感興趣等因素密切相關(guān)。當(dāng)用戶搜索到相關(guān)網(wǎng)頁時(shí)，獲取全部網(wǎng)頁內(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)用戶的等待時(shí)間超過5 s時(shí)，用戶對頁面內(nèi)容的興趣度將減少，則可能在該網(wǎng)頁上的停留時(shí)間會(huì)相應(yīng)縮短。

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

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

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

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

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

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

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

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

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

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

（5）比較并分析查詢得到的頁面。

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

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

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

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

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

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

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

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

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

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

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

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

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

用戶滿意度評估[16]：評估公式如公式（11）所示：

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

圖11 三種算法的用戶滿意度對比圖

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

5 結(jié)束語

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