王嶸冰，劉 鶴

(遼寧大學(xué) 信息學(xué)院，遼寧 沈陽110036)

0 引言

在信息技術(shù)蓬勃發(fā)展的今天，如何快速并且準(zhǔn)確地查詢到自己想要瀏覽的信息已成為一種挑戰(zhàn).Web鏈接結(jié)構(gòu)分析算法是搜索引擎的一部分，對人們所獲取的Web網(wǎng)頁信息有著重要的評估作用.網(wǎng)絡(luò)節(jié)點重要性排序是網(wǎng)絡(luò)科學(xué)領(lǐng)域最基本的問題之一，節(jié)點排序算法在搜索引擎、社交網(wǎng)絡(luò)和推薦系統(tǒng)等許多應(yīng)用場景中都是必不可少的一部分，代表性排序算法為PageRank算法和Hyperlink-Induced Topic Search(HITS)算法[1-2].為了改進(jìn)傳統(tǒng)排序算法的排序效果，相關(guān)研究從用戶歷史行為角度出發(fā)，將用戶興趣度因子融入頁面排序算法中[3]，考慮到用戶對網(wǎng)頁的訪問量、網(wǎng)頁轉(zhuǎn)載次數(shù)等，提高了搜索結(jié)果的準(zhǔn)確性.但是具體來說，現(xiàn)有研究并未考慮影響頁面流量質(zhì)量這一重要指標(biāo)，降低無關(guān)頁面對排序質(zhì)量的影響.即使網(wǎng)頁訪問量較多但僅憑該條件并不能說明網(wǎng)頁的權(quán)威性，如果一個用戶只是點擊進(jìn)入了該頁面，但并沒有點擊該頁面的任何鏈接就直接跳出，這只是增加了頁面訪問量.本文考慮了評估網(wǎng)頁內(nèi)容黏性突出的指標(biāo)——跳出率[4]，將它以網(wǎng)頁權(quán)重因子的形式融入傳統(tǒng)網(wǎng)頁排序算法HITS中，從而可對權(quán)威頁面進(jìn)行鑒別，更新融入頁面跳出率的權(quán)威頁面鑒別算法的Authority值.本文擬搭建實驗環(huán)境，對比實驗驗證搜索結(jié)果相關(guān)度情況，以期提高搜索結(jié)果的查準(zhǔn)率.

1 相關(guān)研究

1.1 傳統(tǒng)的HITS算法

HITS 算法是由康奈爾大學(xué)的JonKleinberg 博士于1997 年首先提出的[5]，它的主要思想是根據(jù)網(wǎng)頁的入度與出度來判斷網(wǎng)頁的重要程度，如果一個網(wǎng)頁具有很高的權(quán)威性，那么這個網(wǎng)頁所指向的其他網(wǎng)頁也具有較高的權(quán)威性；如果這個重要性高的網(wǎng)頁被其他的網(wǎng)頁所指，那么指向這個網(wǎng)頁的其他網(wǎng)頁也具有著較高的權(quán)威性.在HITS算法中，Authority值也稱為權(quán)威值，Authority值a(p)與Hub值h(p)的公式如下[5]：

(1)

(2)

圖1 將根集拓展為基集

對于每個網(wǎng)頁p，權(quán)威值更新為所有導(dǎo)入鏈接所在的頁面中樞紐值的和，樞紐值更新為網(wǎng)頁p上所有導(dǎo)出鏈接指向網(wǎng)頁的權(quán)威值的和.在反復(fù)迭代后，確定節(jié)點的最終權(quán)威值與樞紐值.由于直接按照兩者的更新規(guī)則進(jìn)行迭代會導(dǎo)致結(jié)果值出現(xiàn)偏差，因此有必要在每次迭代后進(jìn)行歸一化，使最終獲得的值收斂.

HITS算法是基于一小部分網(wǎng)頁進(jìn)行計算的：首先通過文本搜索找到相關(guān)網(wǎng)頁得到根集，然后找到與這些根集直接相連的網(wǎng)頁得到基集.圖1展示了將根集拓展為基集的示例[5].

吳江等[6]在HITS算法的基礎(chǔ)上，運用網(wǎng)頁排序改進(jìn)算法識別意見領(lǐng)袖，從而衡量用戶影響力.HITS算法不僅提供了網(wǎng)絡(luò)節(jié)點的排名，還有助于了解不同域上的權(quán)威節(jié)點.基于HITS算法，李文靜等[7]提出節(jié)點群發(fā)現(xiàn)算法HubsRank，基于引文網(wǎng)絡(luò)中節(jié)點影響力，通過多輪迭代，得到引文網(wǎng)絡(luò)中多主題覆蓋的樞紐節(jié)點群，使提取樞紐節(jié)點群的速率得到了提高.此外，Liu等[8]提出了一種HITS結(jié)合PageRank進(jìn)行蛋白質(zhì)遠(yuǎn)程同源性檢測的HITS-PR-HHBLITS預(yù)測方法.隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，針對頁面排序算法在符號網(wǎng)絡(luò)中的局限，陳曉威等[9]提出其改進(jìn)算法，以識別社會網(wǎng)絡(luò)中的關(guān)鍵節(jié)點.

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

HITS算法和PageRank算法是兩種具有代表性的排序算法[10]，相關(guān)學(xué)者的研究大多基于這兩種算法開展的.早期的HITS算法還存在著很多不足，例如主題漂移、網(wǎng)頁欺詐、忽略用戶行為的個性化需求.HITS算法利用內(nèi)容權(quán)威和鏈接權(quán)威兩個相互影響的權(quán)重來評估網(wǎng)絡(luò)內(nèi)容的價值和網(wǎng)絡(luò)中超鏈接的價值[11-12].超鏈接多樣性分析的網(wǎng)頁排序算法，能夠在尋找優(yōu)質(zhì)頁面的同時抑制網(wǎng)頁排名的作弊[13].楊博等[14]通過引入時間權(quán)值函數(shù)、分段函數(shù)、網(wǎng)頁權(quán)值比函數(shù)、興趣度函數(shù)改進(jìn)頁面排序算法中存在的問題.由于Web結(jié)構(gòu)挖掘中HITS算法只考慮頁面之間的鏈接關(guān)系而忽視了頁面的具體內(nèi)容，影響了搜索結(jié)果，為了抑制主題偏離現(xiàn)象，Wang等[15]把超鏈接信息檢索方法與頁面內(nèi)容相結(jié)合，提出了一種改進(jìn)的基于內(nèi)容相關(guān)性改進(jìn)的HITS算法(GHITS)，雖然搜索結(jié)果與主題的相關(guān)度得到了提高，但未考慮無用鏈接對算法的干擾.

亓國濤[16]通過Web日志對用戶網(wǎng)頁瀏覽行為的訪問頁數(shù)、訪問時長、訪問深度、網(wǎng)頁跳出率進(jìn)行分析，并將用戶停留頁面時長與該頁面平均停留時長的比值作為權(quán)重因子融入到網(wǎng)頁排序算法中，但是即使在該頁面的停留時間較長，但不再對該頁面進(jìn)行任何點擊便跳出，上述情況說明該頁面仍存在著網(wǎng)頁排序質(zhì)量的問題，其質(zhì)量需要進(jìn)一步提高.

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

本文的目標(biāo)是改善頁面排序質(zhì)量，使得搜索結(jié)果與主題相關(guān)度得到提高，而影響頁面流量質(zhì)量的重要指標(biāo)為跳出率.文獻(xiàn)[17]使用百度統(tǒng)計軟件采集網(wǎng)站訪問者行為數(shù)據(jù)，應(yīng)用回歸分析模型研究訪客跳出率及網(wǎng)站流量的關(guān)聯(lián)指標(biāo)，得出訪客跳出率與平均訪問頁面數(shù)有關(guān)，而網(wǎng)站流量與訪問次數(shù)、新訪客數(shù)、平均訪問頁數(shù)相關(guān).因此考慮到頁面跳出率因素，本文擬將其以網(wǎng)頁權(quán)重因子形式融入頁面排序算法HITS中，更新融入頁面跳出率的權(quán)威頁面鑒別算法的Authority值.

跳出率指瀏覽了一個頁面便離開網(wǎng)站的訪問次數(shù)占總的訪問次數(shù)的百分比.頁面跳出率可通過百度統(tǒng)計網(wǎng)站獲取JavaScript跟蹤代碼，并復(fù)制此代碼.如果是自己編寫的一般網(wǎng)站，通常將跟蹤代碼粘貼到要跟蹤的網(wǎng)頁底部的標(biāo)記之前，且緊臨該標(biāo)記[18].這樣便可以跟蹤該網(wǎng)站每一個頁面的流量分析報告，其中就包括需要進(jìn)行統(tǒng)計頁面的跳出率情況.本文權(quán)值w(u)反映了統(tǒng)計頁面的跳出率，w(u)的值越大，表明該頁面質(zhì)量越低.因此本文擬將該權(quán)值融入HITS算法之中，進(jìn)而讓Authority值受跳出率的影響，這樣頁面的排序結(jié)果就進(jìn)一步反映了頁面的質(zhì)量，達(dá)到改善頁面排序質(zhì)量的目的.

在HITS算法中融入頁面跳出率權(quán)重，得到融入頁面跳出率的權(quán)威頁面鑒別算法，叫做BRHITS(Bounce Rate HITS)算法，其計算公式如下：

(3)

根據(jù)式(3)計算得到的Authority值受頁面跳出率的影響.BRHITS算法中頁面之間的鏈接關(guān)系可以建立有向圖模型，用符號G(V，E)表示，V表示節(jié)點所代表的頁面集合，E表示節(jié)點之間有向邊的集合.

BRHITS算法描述如下：

Input：擴(kuò)展集合G(V，E，W)，其中V表示節(jié)點集合，E表示邊集合，W表示節(jié)點的跳出率.

Output：節(jié)點V所對應(yīng)的Authority值和Hub值.

Step 1：初始化V中每個節(jié)點v的Authority值和Hub值為1，即a0=1，h0=1；

Step 2:初始化計數(shù)變量count為1；

Step 3：更新集合V中每個節(jié)點v的Authority值和Hub值，具體計算如下：

Step 4:標(biāo)準(zhǔn)化節(jié)點v第t次迭代所得Authority值和Hub值，具體計算如下：

at=at/‖at‖

ht=ht/‖ht‖

Step 5：計算變量count=count+1；

Step 6：如果‖at-at-1‖+‖ht-ht-1‖<ε成立，則收斂，返回(at，ht)；否則，跳至Step 3.

3 實驗實施與結(jié)果分析

3.1 實驗條件

實驗環(huán)境為Windows 10，Pycharm框架下Python 3.7軟件，以及Screaming Frog SEO Spider鏈接分析軟件，將URL地址輸入其中便能夠得到相應(yīng)的入鏈與出鏈.百度統(tǒng)計網(wǎng)站是其他網(wǎng)站平臺的流量分析工具，通過它獲取JavaScript代碼，對目標(biāo)網(wǎng)站的網(wǎng)頁進(jìn)行跟蹤統(tǒng)計.

數(shù)據(jù)來源為http：//www.rank-tennis.com目標(biāo)網(wǎng)站入口頁面，以及與其頁面相對應(yīng)的4月7日至4月14日的百度統(tǒng)計報告，以“tennis”為主題的20個根集頁面及頁面跳出率擴(kuò)展成的403個基集頁面，然后通過鏈接分析軟件將上述基集頁面構(gòu)造成了含有2 059條邊的鏈接分析圖.

3.2 實驗步驟

1)本文針對http：//www.rank-tennis.com網(wǎng)站中入口頁面根據(jù)頁面貢獻(xiàn)瀏覽量獲得它的排行，數(shù)據(jù)來源于百度統(tǒng)計報告(見表1)，將獲得的前20個頁面作為根集R；2)從根集進(jìn)一步擴(kuò)展獲得構(gòu)造頁面鏈接關(guān)系圖所需的基集網(wǎng)頁；3)以Screaming Frog SEO Spider為鏈接分析軟件，將根集R的URL鏈接輸入到該網(wǎng)站中，可以獲得該URL頁面的入鏈與出鏈，將根集頁面R所鏈接的所有頁面以及指向該根集頁面的前50個頁面作為基集.擴(kuò)展成的基集頁面共包含403個網(wǎng)頁，提取基集頁面的鏈接關(guān)系后構(gòu)造頁面鏈接分析圖，圖中邊的總數(shù)為2 059；4)然后用BRHITS算法計算頁面的Authority值，進(jìn)行排序；5)對排序所得到的結(jié)果進(jìn)行評估.

表1 百度統(tǒng)計報告

頁面跳出率可通過百度統(tǒng)計網(wǎng)站進(jìn)行搜索，統(tǒng)計“tennis”查詢主題下所構(gòu)成的基集頁面在2021年4月14日近7天的頁面跳出率情況.

在這個實驗中，大部分用戶可能只對搜索結(jié)果中排名前20的頁面感興趣，本文利用融入頁面跳出率因素的改進(jìn)算法計算.這20個頁面的Authority值，頁面跳出率情況見表1.

3.3 實驗結(jié)果與分析

為了驗證算法的可行性，實驗一給出了兩種算法在相同查詢條件下的結(jié)果分析.實驗二進(jìn)一步驗證BRHITS算法能在一定程度上改善排序質(zhì)量，并通過搜索結(jié)果頁面的相關(guān)性及查準(zhǔn)率進(jìn)行了說明.

實驗一 相同查詢條件下的結(jié)果分析.

表2、表3為基于HITS算法和BRHITS算法對基集頁面進(jìn)行計算排名，并給出了前10個頁面的入鏈個數(shù)與Authority值.BRHITS算法與傳統(tǒng)的網(wǎng)頁排序HITS算法相比更能篩選出用戶滿意的頁面排序情況，頁面得到了提升，與用戶查詢相關(guān)度低的頁面排名下降.具體表現(xiàn)在HITS算法與BRHITS算法針對前10個頁面出現(xiàn)了不同的排名情況，名次提高的頁面為5、6、8、9、10，并且頁面1、5、6、8的Authority值都有提升；頁面2、3、4、7的Authority值減少，排名下降5名.頁面排序變化較大的為頁面2、3、4、7，即使權(quán)威值較高但并不一定是用戶滿意的排名結(jié)果，而在傳統(tǒng)的網(wǎng)頁排序HITS算法中其排名仍靠前.通過進(jìn)一步對2、3、4、7頁面進(jìn)行分析并獲得它們的入鏈集合可知，即使它們有較多的入鏈數(shù)，但入鏈頁面包含較多的存在著跳出率的入口頁面，例如頁面1、5、6、8、9、10均有指向其頁面的鏈接.此外，從URL頁面可知2、3、4、7頁面還是登錄頁面.所以只考慮基于入鏈數(shù)量計算的Authority值是片面的，頁面的排名還與入鏈頁面的跳出率有關(guān).

實驗二 搜索結(jié)果相關(guān)度對比.

用戶在搜索引擎中進(jìn)行信息查詢時，常常關(guān)注的是前n條搜索結(jié)果，比如：大多數(shù)用戶只關(guān)注搜索結(jié)果中的第一頁[19]，而提高搜索結(jié)果頁面中與用戶查詢相關(guān)的頁面排名也是改進(jìn)搜索引擎算法的目的.因此本實驗對搜索結(jié)果的前5、10、15、20的網(wǎng)頁中與查詢主題相關(guān)的頁面數(shù)以及查準(zhǔn)率進(jìn)行比較分析.查準(zhǔn)率為查詢主題相關(guān)的網(wǎng)頁數(shù)與查詢結(jié)果網(wǎng)頁總數(shù)的比值.在同一查詢主題“tennis”下對比HITS算法、GHITS算法(基于內(nèi)容相關(guān)性改進(jìn)的HITS算法)、BRHITS算法搜索結(jié)果的頁面排序情況，并進(jìn)行相關(guān)度的測評.實驗結(jié)果如表4、圖2、圖3所示.

表4 搜索結(jié)果相關(guān)性頁面與查準(zhǔn)率對比

圖2 三種算法搜索結(jié)果相關(guān)度對比

圖3 三種算法搜索結(jié)果查準(zhǔn)率對比

從圖2、圖3中可以看出運用BRHITS算法之后提高了搜索結(jié)果相關(guān)性，改善了搜索結(jié)果的排序質(zhì)量，排在前25的頁面相關(guān)度較高，查準(zhǔn)率提高10%～30%.

4 結(jié)語

本文提出的BRHITS算法考慮了評定頁面流量質(zhì)量的重要指標(biāo)頁面跳出率，將跳出率因子融入傳統(tǒng)的HITS算法中，優(yōu)化并得到了BRHITS算法.實驗結(jié)果表明，用戶在進(jìn)行主題查詢時頁面的排序質(zhì)量得到了提高，在一定程度上提升了檢索準(zhǔn)確度.在接下來的研究中將在不同查詢主題下進(jìn)行信息檢索，進(jìn)一步證明所提出的算法的有效性.