基于學習自動機和用戶興趣的PageRank算法研究

姜金川，王 沖

桂林電子科技大學 計算機與信息安全學院，廣西 桂林541004

1 引言

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

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

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

2 相關算法及技術

2.1 PageRank算法

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

圖1 PageRank原理圖

2.2 Weighted PageRank算法

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

2.3 相關改進算法

針對PageRank算法出現的主題漂移問題，Tan[4]提出了一種基于向量空間的改進PageRank算法，此算法將矢量空間檢索評估模型進行了融合，考慮到網頁鏈接結構和主題內容的相關性，將主題內容的相似度與經典PageRank算法相結合，加權融合后得到新的PR值，但該算法未考慮到源網頁與出鏈網頁之間的權值分配問題。Yang等人[5]提出了一種基于時間反饋和主題相似度的改進PageRank算法，該算法通過添加頁面更新率因子、主題相關因子和網頁相似度對PageRank算法進行改進，但并未考慮用戶興趣對網頁排序的重要性。文獻[6]提出一種基于比率的加權PageRank算法，使用基于比率的方法在其引用的節點之間劃分節點的PageRank值，使每個節點根據其自身權重獲得相應權值，但算法未考慮沒有出鏈的懸掛節點，顯然是不合理的。文獻[7]提出了一種基于資源分配（IPRA）的改進PageRank算法，該算法雖然在定向網絡中識別了更具有影響力的網頁，但也大大提高了計算復雜度。針對忽略用戶興趣問題，王旭陽等[8]提出了基于用戶行為與頁面分析的改進PageRank算法，該算法考慮了網頁瀏覽者對頁面的點擊行為，缺點是未對用戶的點擊次數做有效性驗證。文獻[9]通過對不同用戶的已發表文章和轉載信息等內容的相似性分析獲取用戶的關系結構，但是因不同網頁瀏覽者的頁面傳播速率不一樣，對很少訪問互聯網的人群影響力權值分配為0是不合理的，其次，存在數據識別問題，其中由于用戶信息被盜取而導致的錯誤信息被發布占據相當大的比重。文獻[10]基于大量數據，該算法通過分析用戶的歷史行為給出相應的用戶預測，從而獲得用戶關系結構，但在提高用戶查詢準確度的同時也增大了算法的時間復雜度。

2.4 學習自動機（LA）

自動機可以被看作是一個具有有限動作集的抽象模型。學習自動機[11-12]通過不斷地與隨機環境進行交互并獲得經驗來改善其行為，隨機環境通過評估動作，給出自動機所選動作的概率。自動機使用來自環境的響應（即動作概率）來選擇其下一個動作。通過繼續此過程，在可選動作中選擇該環境下的最佳動作。其工作原理如圖2所示。

圖2 學習自動機工作原理圖

環境是一個三元組＜α,β,c＞，其中：α={α1,α2,…,αr}是學習自動機的r個動作集合；β={β1,β2,…,βm}代表環境的反應集；c={c1,c2,…,cr}是r個動作的懲罰概率，其中元素ci對應于動作集α中的動作αi。學習自動機的輸出集α中的αn在t=n時刻應用于環境。

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

理想響應：

非理想響應：

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

3改進的PageRank算法：LUPR

算法包括兩個步驟，第一步計算基于學習自動機的網頁之間每個超鏈接的權重，使用已存儲在日志文件中每個用戶導航路徑來計算網頁之間超鏈接的權重；第二步計算網頁興趣度因子，使用網頁瀏覽者搜索網頁的等待時長以及瀏覽時長，網頁的瀏覽時間越長，在某種程度上可以代表網頁瀏覽者對此頁面越感興趣。

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

其中，LAk是頁面k的學習自動機，V(LAi,k)是LAi自動機中動作概率k的值，這個概率值顯示了網頁之間超鏈接的權重，TD(k)代表興趣度因子，參數m是網頁數量，d是阻尼系數，一般取值0.85[15]。

3.1 基于學習自動機確定網頁間的超鏈接權重

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

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

（1）根據網頁結構創建一個分布式學習自動機DLA。

（2）對每個學習自動機，初始化動作概率向量。

（3）對用戶日志文件中每個用戶訪問路徑，如果用戶從Dk移動到Dm則根據如下學習算法更新LAk自動機的動作概率向量。

3.2 興趣度因子

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

用戶在頁面上花費的時長需要考慮網頁內容和篇幅因素的影響，如果頁面瀏覽者對該網頁感興趣，則需要花費更多的時間來瀏覽頁面，停留時間的長短與頁面的文字、圖片及視頻的數量以及瀏覽者是否對該頁面感興趣等因素密切相關。當用戶搜索到相關網頁時，獲取全部網頁內容需等待的時間為ts，經統計顯示，當網絡通暢時，ts≤3 s，設置閾值平均時間ts=5 s，當用戶的等待時間超過5 s時，用戶對頁面內容的興趣度將減少，則可能在該網頁上的停留時間會相應縮短。

設正常人閱讀完整個頁面的內容并進行思考和評論的時間為tc，其中tc的計算公式如下：

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

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

4 實驗仿真

4.1 主要實驗步驟

本文使用Java作為前端開發，編譯環境使用MyEclipse、Lucene 3.0jar包和Heritrix等，對LUPR算法進行實驗仿真，步驟如下：

（1）用戶數據收集。使用Heritrix網頁爬蟲工具從“巨細熱點網站”抓取5 000個IP用戶近一個月的訪問信息。

（2）網頁數據收集。根據抓取的網頁數據，生成網頁鏈接結構圖，獲取鏈接關系，將其作為記錄存入數據庫中。

（3）搭建MyEclipse實驗平臺，在實驗項目中添加Lucene 3.0jar包，添加中文分詞器IKAnalyzer3.2.8.jar包，配置相關停用詞，放在項目的根目錄中。

（4）在既定環境中，使用Java語言分別實現傳統的PageRank算法，WPR算法和本文提出的LUPR算法，LUPR算法在本實驗中，k取1.35。

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

4.2 實驗結果

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

圖3 PageRank基于“轉基因”關鍵詞查詢結果

圖4 WPR基于“轉基因”關鍵詞查詢結果

圖5 LUPR基于“轉基因”關鍵詞查詢結果

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

圖6 PageRank排名第24位的網頁

圖7 WPR排名第22位的網頁

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

本實驗為測試查詢結果中的前30個頁面，隨機選取1 217名學生進行測試查詢信息，對5個查詢關鍵詞分別為“轉基因”、“蘋果手機”、“中國制造”、“食品安全”、“流行病”的查詢結果進行測評，測試結果如圖8所示。

圖8 三種算法查準率對比圖

通過選取更多的查詢關鍵詞，進一步說明本文LUPR算法的排序質量。選取當前社會熱點、網絡熱詞等與當今社會息息相關的50個關鍵詞進行測評，首先統計單個關鍵詞的查準率，然后以5、10、20、30、50為單位逐步擴大關鍵詞的個數，求取三種算法的平均查準率，目的是為了消除個別關鍵詞的差異性，更好說明LUPR算法的排序質量，測試結果如圖9所示。

圖9 三種算法平均查準率對比圖

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

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

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

仿真實驗證明，LUPR算法在一定程度上可以提高網頁排序質量、信息查詢的精準度和用戶檢索的滿意度。

5 結束語

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