基于分布式學(xué)習(xí)自動(dòng)機(jī)和用戶反饋的網(wǎng)頁(yè)排序算法研究

王 沖 姜金川

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

0 引 言

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

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

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

1.1 PageRank算法

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

(1)

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

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

(1) 權(quán)值平均分配。傳統(tǒng)的PageRank算法鏈接權(quán)重均等分配，導(dǎo)致無(wú)法區(qū)分權(quán)威頁(yè)面與普通頁(yè)面。

(2) 忽略用戶反饋。用戶反饋包含大量有價(jià)值的信息，但PageRank算法卻沒有對(duì)其作出分析，導(dǎo)致忽略用戶興趣和網(wǎng)頁(yè)欺詐等問(wèn)題。

(3) 主題漂移問(wèn)題。由于與查詢?cè)~無(wú)關(guān)，導(dǎo)致查詢到的網(wǎng)頁(yè)雖然PR值高但與查詢意圖并不相關(guān)。

1.2 學(xué)習(xí)自動(dòng)機(jī)

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

1.3 可變結(jié)構(gòu)學(xué)習(xí)自動(dòng)機(jī)

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

(1) 獎(jiǎng)勵(lì)響應(yīng)：

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

(2)

(2) 懲罰響應(yīng)：

(3)

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

1.4 分布式學(xué)習(xí)自動(dòng)機(jī)

圖1 分布式學(xué)習(xí)自動(dòng)機(jī)

2 改進(jìn)的PageRank算法

本文方法中，用戶扮演DLA中當(dāng)前自動(dòng)機(jī)隨機(jī)環(huán)境的角色。為了確定網(wǎng)絡(luò)文檔的結(jié)構(gòu)，使用具有n個(gè)學(xué)習(xí)自動(dòng)機(jī)的DLA，其表示n個(gè)網(wǎng)頁(yè)，每個(gè)學(xué)習(xí)自動(dòng)機(jī)都有n-1個(gè)動(dòng)作。DLA中可用自動(dòng)機(jī)的內(nèi)部結(jié)構(gòu)根據(jù)學(xué)習(xí)算法更新，對(duì)于每個(gè)學(xué)習(xí)自動(dòng)機(jī)，任何時(shí)候只有一個(gè)動(dòng)作子集被激活。

算法包括兩大步驟：第一步使用已存儲(chǔ)在日志文件中每個(gè)用戶導(dǎo)航路徑和頁(yè)面之間的相似度以及網(wǎng)頁(yè)鏈接基于分布式學(xué)習(xí)自動(dòng)機(jī)計(jì)算網(wǎng)頁(yè)超鏈接之間的權(quán)重，改善PageRank算法中的鏈接權(quán)重均等分配和主題漂移問(wèn)題；第二步計(jì)算用戶反饋因子，選取用戶的轉(zhuǎn)載、回復(fù)以及有效點(diǎn)擊特征作為用戶的行為特征，該特征反應(yīng)了用戶對(duì)搜索主題下的網(wǎng)頁(yè)質(zhì)量、內(nèi)容等的認(rèn)可度，緩解忽略用戶興趣和網(wǎng)頁(yè)欺詐等問(wèn)題，算法公式如下所示：

(4)

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

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

(1) 用戶遍歷的路徑；

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

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

所選動(dòng)作的懲罰取決于2個(gè)因素：

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

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

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

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

(5)

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

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

(6)

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

b=d(i,j)×β

(7)

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

b=β

(8)

2.2 用戶反饋因子

為了增加PR值，某些網(wǎng)頁(yè)存在人為的多次鏈接作弊，忽略了網(wǎng)頁(yè)本身的質(zhì)量。用戶對(duì)網(wǎng)頁(yè)的響應(yīng)，例如回復(fù)、收藏、評(píng)論、轉(zhuǎn)載等，反映了用戶對(duì)搜索主題下的網(wǎng)頁(yè)質(zhì)量和內(nèi)容的認(rèn)可度。用戶反饋因子選取用戶的轉(zhuǎn)載、回復(fù)以及有效點(diǎn)擊特征作為用戶的行為特征，用戶反饋因子的公式如下：

(9)

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

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

(10)

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

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

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

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

(1) 用戶數(shù)據(jù)收集。使用Heritrix網(wǎng)頁(yè)爬蟲工具從“巨細(xì)熱點(diǎn)網(wǎng)站”抓取5 000個(gè)IP用戶近一個(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.0 jar包，添加中文分詞器IKAnalyzer3.2.8 jar包，配置相關(guān)停用詞，放在項(xiàng)目的根目錄中。

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

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

表1 λ,?,不同值對(duì)應(yīng)的用戶滿意度

表1 λ,?,不同值對(duì)應(yīng)的用戶滿意度

(λ,,?)(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

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

圖2 PageRank基于“旅游”關(guān)鍵詞查詢結(jié)果

圖3 WPR基于“旅游”關(guān)鍵詞查詢結(jié)果

圖4 本文算法基于“旅游”關(guān)鍵詞查詢結(jié)果

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

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

(11)

本實(shí)驗(yàn)為測(cè)試查詢結(jié)果中的前30個(gè)網(wǎng)頁(yè)，隨機(jī)選取1 217名學(xué)生來(lái)測(cè)試查詢信息，對(duì)查詢關(guān)鍵詞為“旅游”、“Iphone”、“理財(cái)”、“手機(jī)”、“疫苗”的查詢結(jié)果進(jìn)行查準(zhǔn)率測(cè)評(píng)。測(cè)試結(jié)果如圖5所示。

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

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

用戶滿意度評(píng)估[12]公式如下：

(12)

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

圖6 三種算法的用戶滿意度對(duì)比圖

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

4 結(jié) 語(yǔ)

本文提出一種基于分布式學(xué)習(xí)自動(dòng)機(jī)和用戶反饋的頁(yè)面排序算法。該算法首先基于分布式學(xué)習(xí)自動(dòng)機(jī)確定網(wǎng)頁(yè)間的超鏈接權(quán)重，以緩解PageRank算法平分鏈接權(quán)重和主題漂移問(wèn)題，計(jì)算超鏈接權(quán)重是根據(jù)頁(yè)面內(nèi)容的相似性、相關(guān)鏈接的存在以及用戶遍歷的路徑；其次考慮到用戶反饋中包含大量的價(jià)值信息，其某些行為反應(yīng)了用戶對(duì)搜索主題下的網(wǎng)頁(yè)質(zhì)量、內(nèi)容等的認(rèn)可度，選取用戶的轉(zhuǎn)載、回復(fù)以及有效點(diǎn)擊特征作為用戶的行為特征，獲得用戶反饋因子。仿真實(shí)驗(yàn)表明，該算法在一定程度上提升了信息檢索的精準(zhǔn)度和用戶滿意度。下一步工作是考慮嘗試在學(xué)習(xí)自動(dòng)機(jī)中使用用戶在網(wǎng)頁(yè)中的停留時(shí)間作為獎(jiǎng)勵(lì)進(jìn)行網(wǎng)頁(yè)排序?qū)λ惴ㄟM(jìn)行改進(jìn)。