王 沖 姜金川

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

0 引 言

尋找高質量的網頁是搜索引擎的重要目的之一，頁面的質量是根據(jù)用戶的請求和偏好定義的。通常，每個查詢請求都有數(shù)百萬個相關頁面，但是用戶特別感興趣的只是這些頁面中的10到20個。網頁根據(jù)其質量進行排序，目前關于網頁排序的算法多種多樣，主要分為以下3類：(1) 基于鏈接結構分析的排序算法；(2) 基于網頁內容分析的排序算法；(3) 基于網絡用戶行為分析的優(yōu)化排序算法。傳統(tǒng)的基于Web內容分析的排序算法因其僅考慮網頁之間的內容相關性而降低了排序效果。基于網絡用戶行為分析的優(yōu)化排序算法尚未成熟，主要是在過濾虛假網頁鏈接作弊、忽略用戶興趣等方面存在不足。例如：網頁主題詞之間的多次故意鏈接并沒有得到有效過濾，用戶點擊量高、瀏覽時間長、用戶轉載回復次數(shù)多甚至下載量大等體現(xiàn)用戶興趣的網頁并沒有獲得相應的影響因子及合理權值。PageRank算法基于網頁間鏈接結構中隱含的信息進行網頁排序，其成功運用于Google搜索引擎，證實了它所具有的實踐應用價值和理論研究價值。

本文在綜合分析與比較經典網頁排序模型Page-Rank算法及其相關研究的基礎上，一方面利用頁面內容的相似性、頁面之間的超鏈接和用戶遍歷的路徑使用分布式學習自動機來確定網頁之間的超鏈接權重，以緩解PageRank算法平分鏈接權重和主題漂移的問題；另一方面選取用戶的轉載、回復以及有效點擊特征作為用戶的行為特征，獲得用戶反饋因子，以緩解忽略用戶興趣問題。仿真環(huán)境通過MyEclipse、Heritrix和Lucene工具搭建，對比PageRank、WPR算法驗證DUPR算法的排序質量，并以查準率和用戶滿意度評估網頁排序效果。

1 相關算法及技術

1.1 PageRank算法

傳統(tǒng)的PageRank算法是一種完全依賴網頁鏈接結構的網頁排序算法，它根據(jù)鏈接到該頁面的網頁鏈接數(shù)量和對網頁的貢獻值對其進行排序。該算法的主要思想為：網絡中的網頁通過超鏈接鏈接到其他網頁，代表該網頁投給鏈向網頁一票，并將其網頁的Page-Rank值均等分配給鏈向網頁。顯然，網頁自身PR值越高，其對于鏈出網頁的貢獻值就越大，鏈出網頁獲得的PageRank值也就越高；頁面的反向超鏈接數(shù)目越多，它的PR值也就越高；一個網頁鏈入頁面的鏈出數(shù)量越少，該頁面獲得的PR值也就越高。PageRank算法的計算公式如下：

(1)

式中：U代表當前要計算PR值的頁面；d是阻尼系數(shù)，代表用戶停留在當前網頁的概率，介于0到1之間，通常為0.85[1]；N代表網絡中總網頁數(shù)；Out(Vn)表示網頁Vn的出鏈數(shù)量。

雖然PageRank算法已成功運用于Google中，但是它仍然存在以下不足：

(1) 權值平均分配。傳統(tǒng)的PageRank算法鏈接權重均等分配，導致無法區(qū)分權威頁面與普通頁面。

(2) 忽略用戶反饋。用戶反饋包含大量有價值的信息，但PageRank算法卻沒有對其作出分析，導致忽略用戶興趣和網頁欺詐等問題。

(3) 主題漂移問題。由于與查詢詞無關，導致查詢到的網頁雖然PR值高但與查詢意圖并不相關。

1.2 學習自動機

學習自動機[2-6]是在未知的隨機環(huán)境下運行的自適應決策設備，自動學習的方法涉及從一組允許的動作中確定一個最佳的動作。一個自動機可以被認為是一個具有有限動作數(shù)量的抽象模型。在每個決策過程中，自動機從其有限的動作集中選擇一個合適的動作，此動作適用于隨機環(huán)境。隨機環(huán)境對所選動作進行評估并給出自動機應用動作的等級，環(huán)境的隨機響應(即動作等級)被自動機用于進一步的動作選擇，通過繼續(xù)這個過程，自動機選擇最佳等級的動作。作用于未知的隨機環(huán)境下并通過某種特定的方式改善其性能的自動機，稱為學習自動機LA(Learning Automata)。學習自動機主要分為兩類：一類是固定結構學習自動機；另一類是可變結構學習自動機，因可變結構學習自動機能夠適應環(huán)境條件改變其狀態(tài)，收斂速度更快，可達到自適應學習的目的。故本文使用可變結構學習自動機。

1.3 可變結構學習自動機

可變結構學習自動機[7]可以用一組四元組<α，β，P，T>表示，其中：α={α1，α2，…，αr}是學習自動機的r個動作集合；β={β1，β2，…，βr}是環(huán)境響應集合；P={p1，p2，…，pr}是包含r個概率的概率集，分別是在當前內部狀態(tài)下執(zhí)行每個動作的概率；T是強化算法，其功能是針對所執(zhí)行的動作和所接收的響應來修改動作概率向量p。如果環(huán)境響應β僅有兩個值，即β={0,1}，這樣的環(huán)境稱為P模型。如果β有兩個以上元素的有限輸出集合，則這樣的環(huán)境稱為Q模型，如果環(huán)境的輸出是在[0，1]區(qū)間內連續(xù)的隨機值，該環(huán)境稱為S模型。更新動作概率的學習算法是影響可變結構學習自動機性能的關鍵因素。設α是在步驟n中被選擇的動作，作為概率分布p的一個樣本實現(xiàn)。其更新動作概率向量p的遞歸方案定義如下：

(1) 獎勵響應：

pi(n+1)=pi(n)+a[1-pi(n)] ?jj≠ipj(n+1)=(1-a)pj(n)

(2)

(2) 懲罰響應：

(3)

在一些實際應用中，我們需要LA有更多的動作，一個具有變化動作數(shù)量的LA在任何時刻n都可以從一組活動動作V(n)中選擇一個動作。對于所選動作，學習自動機首先計算其動作概率的和，然后計算向量p^(n)。自動機根據(jù)動作概率隨機選擇其活動動作，自動機將所選動作應用于環(huán)境并獲得響應，對于響應的理想與否，更新向量p^(n)。然后進入第n+1次循環(huán)，最后學習自動機根據(jù)向量p^(n+1)更新動作概率向量p(n)。

1.4 分布式學習自動機

圖1 分布式學習自動機

2 改進的PageRank算法

本文方法中，用戶扮演DLA中當前自動機隨機環(huán)境的角色。為了確定網絡文檔的結構，使用具有n個學習自動機的DLA，其表示n個網頁，每個學習自動機都有n-1個動作。DLA中可用自動機的內部結構根據(jù)學習算法更新，對于每個學習自動機，任何時候只有一個動作子集被激活。

算法包括兩大步驟：第一步使用已存儲在日志文件中每個用戶導航路徑和頁面之間的相似度以及網頁鏈接基于分布式學習自動機計算網頁超鏈接之間的權重，改善PageRank算法中的鏈接權重均等分配和主題漂移問題；第二步計算用戶反饋因子，選取用戶的轉載、回復以及有效點擊特征作為用戶的行為特征，該特征反應了用戶對搜索主題下的網頁質量、內容等的認可度，緩解忽略用戶興趣和網頁欺詐等問題，算法公式如下所示：

(4)

式中：N是系統(tǒng)中所有網頁的數(shù)量；d是阻尼系數(shù)；DLA(V，U)是兩個頁面V和U之間的鏈接權重；R(U)是用戶反饋因子。

2.1 基于分布式學習自動機確定網頁超鏈接權重

(1) 用戶遍歷的路徑；

(2) 頁面之間存在鏈接；

(3) 頁面之間的相似度。

所選動作的懲罰取決于2個因素：

(1) 用戶移動路徑中存在環(huán)路；

(2) 用戶移動路徑中的頁面之間缺乏相似性。

學習自動機動作的獎勵或懲罰是根據(jù)式(2)和式(3)的學習算法完成的。因此通過使用懲罰或獎勵，自動機的動作概率將會被更新。用戶從頁面i移動到頁面j，當頁面i與j之間的相似度大于0.45時，相應的動作將得到獎勵，獎勵值根據(jù)頁面相似度的大小和兩頁之間的鏈接確定。獎勵系數(shù)公式如下：

a=sim(i,j)×ω+γ

(5)

式中：sim(i，j)是網頁i和網頁j之間的相似值；ω和γ為調整系數(shù)，如果網頁i和網頁j之間沒有鏈接則為0。

本文中的頁面相似性度量方法采用向量空間模型中的余弦相似度[10]，如果文檔i和文檔j的文檔向量是I=(i1,i2,…,in)，J=(j1,j2,…,jn)，則它們的相關程度計算公式如下：

(6)

如果用戶在行進路徑中存在環(huán)路則表示用戶可能對遍歷路徑的不滿意而導致用戶返回已訪問過的頁面并開始再次瀏覽該頁面。對于用戶在循環(huán)中移動的動作將受到懲罰。懲罰步長與周期中的頁面i和頁面j的距離成比例，因此環(huán)路中的存在頁面根據(jù)式(7)受到懲罰。

b=d(i,j)×β

(7)

式中：b是懲罰參數(shù)；d(i，j)是環(huán)路中的頁面i和頁面j之間的距離；β是懲罰參數(shù)的調節(jié)系數(shù)。如果用戶移動路徑中不存在環(huán)路，但兩頁間的余弦相似度小于0.45時，將發(fā)生第二種懲罰狀態(tài)，根據(jù)式(8)更新相應動作概率。

b=β

(8)

2.2 用戶反饋因子

為了增加PR值，某些網頁存在人為的多次鏈接作弊，忽略了網頁本身的質量。用戶對網頁的響應，例如回復、收藏、評論、轉載等，反映了用戶對搜索主題下的網頁質量和內容的認可度。用戶反饋因子選取用戶的轉載、回復以及有效點擊特征作為用戶的行為特征，用戶反饋因子的公式如下：

(9)

式中:λ、?、為特征系數(shù)，滿足三者算術相加之和等于1。在實際應用中，λ、?、三個特征系數(shù)應根據(jù)實際應用數(shù)據(jù)集的大小進行合理調整，本文中λ、?、的取值為本實驗數(shù)據(jù)集下對比結果的最優(yōu)值。Vc(p→k)表示網頁k獲得的有效點擊次數(shù)；Rs(p→k)表示用戶對頁面k的評論或回復的數(shù)量；Sh(p→k)表示用戶對頁面k的轉載次數(shù)；S(p)表示網頁的總數(shù)量。使用頁面k的有效點擊次數(shù)與總點擊次數(shù)的比率，即有效點擊率；網頁k的回復或評論數(shù)量在總網頁回復或評論數(shù)量中所占比例，即網頁回復率；網頁k的轉載量占總轉載量的比率，即網頁轉載率，衡量用戶對網頁的認可度。有效點擊率、回復率、轉載率越高，在一定程度上認為網頁沖浪者對網頁的認可度越高，即用戶反饋因子R(k)值越大，用戶對當前檢索結果的滿意度越高。

設置時間閾值，以用戶在網頁的停留時間來判斷用戶的此次點擊是否作為有效點擊從而將次數(shù)記入有效點擊量中。如果瀏覽者通過單擊超鏈接p→k瀏覽網頁的時間大于tc，則意味著該頁面可能會引起用戶的瀏覽興趣，則此次點擊應作為有效點擊計入有效點擊量中；如果瀏覽時間小于tc，則意味著瀏覽者對該網頁沒有興趣，即無效點擊，不會計入有效點擊量中。tc為普通正常人閱讀所有頁面內容以及思考和評論的時間，計算公式如下：

(10)

式中：cw、cp和cv分別代表網頁正文中的文本數(shù)量、網頁中的圖片數(shù)量以及網頁視頻的數(shù)量。為了便于計算，這里將圖片與視頻依據(jù)其含義轉化為描述的文字量，分別近似于50和100個字，正常人一般閱讀速度為280字數(shù)/分鐘[11]，k是評論系數(shù)，取值一般介于1.2到1.5之間。

3 實驗仿真

3.1 實驗主要步驟

本文使用Java作為前端開發(fā)，編譯環(huán)境使用My-Eclipse、Lucene 3.0 jar包和Heritrix等，對DUPR算法進行實驗仿真，步驟如下：

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

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

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

(4) 在既定環(huán)境中，使用Java語言分別實現(xiàn)傳統(tǒng)的PageRank算法、WPR算法和本文算法。在本文算法中，ω為0.01，γ為0.02，β為0.002，λ為0.3，?為0.4，為0.3。

(5) 比較并分析查詢得到的頁面。

3.2 實驗結果分析

為了顯示本文算法的優(yōu)越性，分別選取“旅游”、“Iphone”、“理財”、“手機”、“疫苗”作為五組關鍵詞進行對比實驗。首先確定用戶反饋因子中λ、?、的取值，隨機給出多組數(shù)據(jù)組合(λ,?,)進行實驗。多次查詢后觀察到，當其中一個因子的取值大于或等于0.5時，用戶滿意度大大降低，因此在精度為0.1的情況下，λ,?,∈(0.2,0.3,0.4)。由于λ、?、滿足三者算術相加之和等于1，也就是說(λ,?,)可以采取六組實驗數(shù)據(jù)。如表1第5和第7行所示，不同查詢關鍵字的多個查詢結果表明，當λ=0.3，?=0.4，=0.3時，即用戶反饋因子中的有效點擊率、回復率、轉載率的分配比重分別為0.3、0.4、0.3時用戶滿意度最高。查詢“旅游”關鍵字的一些實驗數(shù)據(jù)如表1所示。

表1 λ,?,不同值對應的用戶滿意度

表1 λ,?,不同值對應的用戶滿意度

(λ,,?)(0.7,0.2,0.1)(0.1,0.7,0.2)(0.2,0.1,0.7)用戶滿意度551.4527.6562.4(λ,,?)(0.6,0.2,0.2)(0.3,0.6,0.1)(0.3,0.2,0.5)用戶滿意度533541.8563.2(λ,,?)(0.4,0.4,0.2)(0.4,0.3,0.3)(0.4,0.2,0.4)用戶滿意度632.6647.8634.8(λ,,?)(0.3,0.4,0.3)(0.3,0.3,0.4)(0.2,0.4,0.4)用戶滿意度651.2641.4624

對比3種不同查詢算法的結果并進行分析，以“旅游”為關鍵字的查詢結果如圖2-圖4所示。為了節(jié)省篇幅，給出了查詢結果排名前十的排序結果。

圖2 PageRank基于“旅游”關鍵詞查詢結果

圖3 WPR基于“旅游”關鍵詞查詢結果

圖4 本文算法基于“旅游”關鍵詞查詢結果

圖2是基于鏈接關系的傳統(tǒng)的PageRank算法基于“旅游”關鍵詞的網頁排序結果，可以看出與主題無關但權威度高的網頁占據(jù)了絕大部分。圖3是改進了權值均等分配缺點的WPR算法基于“旅游”關鍵詞的網頁排序結果，可以看到WPR算法對于權威度很高的網頁并沒有做出很大的調整，權威度高但與用戶查詢意圖無關的網頁依然排在很靠前的位置。圖4是本文算法，可以看出與主題無關的網頁數(shù)量大大減少，證明了本文算法有力地削弱了主題偏移現(xiàn)象。此外，前十個網頁中有9個和用戶相關的網頁，證明了本文算法更能篩選出用戶感興趣并且認可度高的頁面，使其排名得到提升，而與用戶查詢意圖完全無關的頁面使其排名得到下沉。例如，圖2和圖3中排名第1的頁面標題為“石材產業(yè)亮出你的文化牌”、排名第3的頁面標題為“中國酒店運營國際標準”等均得到了大幅下降。

通過查準率進一步說明本文算法的排序質量。本文研究的查準率是指通過小規(guī)模模擬實驗得到的統(tǒng)計結果，其語義含義是，在采樣的樣本數(shù)量中用戶對查詢結果滿意的樣本數(shù)量占總樣本數(shù)量的百分比，是根據(jù)用戶主觀判斷，確定查詢結果與用戶需求相關度的一個衡量標準。其中用戶評價分為4個不同級別：不滿意、較滿意、滿意和非常滿意，標記結果為滿意、較滿意和非常滿意的頁面為和用戶查詢主題相關的頁面。查準率的計算公式如下:

(11)

本實驗為測試查詢結果中的前30個網頁，隨機選取1 217名學生來測試查詢信息，對查詢關鍵詞為“旅游”、“Iphone”、“理財”、“手機”、“疫苗”的查詢結果進行查準率測評。測試結果如圖5所示。

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

從圖5實驗結果看出，本文算法的查準率平均值為93%左右，而傳統(tǒng)的PageRank算法的查準率平均值大約為63%，WPR算法的查準率平均值估計為73%。本文算法搜索結果的查準率明顯高于傳統(tǒng)PageRank算法和WPR算法，表明本文算法受到學習自動機和用戶反饋因子的影響，搜索結果更加具有合理性，更符合用戶的需求。

用戶滿意度評估[12]公式如下：

(12)

查詢結果分為4個級別：非常滿意、滿意、較滿意和不滿意。Si是滿意度系數(shù)，不同級別的滿意度系數(shù)分別為：1.0，0.6，0.2，0.0。其中n是頁面總數(shù)，在此實驗中n是不同排序算法結果中的前30個頁面，i是計數(shù)器。通過用戶滿意度評估公式與算法測試，比較結果如圖6所示。

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

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

4 結 語

本文提出一種基于分布式學習自動機和用戶反饋的頁面排序算法。該算法首先基于分布式學習自動機確定網頁間的超鏈接權重，以緩解PageRank算法平分鏈接權重和主題漂移問題，計算超鏈接權重是根據(jù)頁面內容的相似性、相關鏈接的存在以及用戶遍歷的路徑；其次考慮到用戶反饋中包含大量的價值信息，其某些行為反應了用戶對搜索主題下的網頁質量、內容等的認可度，選取用戶的轉載、回復以及有效點擊特征作為用戶的行為特征，獲得用戶反饋因子。仿真實驗表明，該算法在一定程度上提升了信息檢索的精準度和用戶滿意度。下一步工作是考慮嘗試在學習自動機中使用用戶在網頁中的停留時間作為獎勵進行網頁排序對算法進行改進。