基于Nutch的頁面排序算法研究

胡維華，曹奇峰

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，浙江杭州310018)

0 引言

如何高效、快速、準(zhǔn)確地查找所需信息是當(dāng)前搜索引擎最需要考慮的問題。搜索引擎根據(jù)用戶提交的檢索詞會返回海量結(jié)果集，找到所需的信息需耗費(fèi)大量時間。基于隨機(jī)游走模型的PageRank算法［1］曾經(jīng)很成功地解決了頁面排序問題，但隨著互聯(lián)網(wǎng)幾何級的數(shù)據(jù)增長，經(jīng)典PageRank算法［2］已經(jīng)無法滿足用戶的需求。許多學(xué)者根據(jù)該算法提出了自己的改進(jìn)方案。Topic-Sensitive PageRank算法［3］和MP-PageRank算法［4］通過改變平均權(quán)值的方式，一定程度上修正了主題漂移問題。Nutch［5］作為開源的搜索引擎為研究人員提供了很好的選擇。Nutch的排序算法［6－7］是針對通用搜索引擎設(shè)計(jì)的一種類似PageRank的在線分析算法。該排序算法有明顯不足:平分鏈出網(wǎng)頁的權(quán)值;偏重歷史網(wǎng)頁;忽略網(wǎng)頁內(nèi)容的相關(guān)性。這些因素都會影響網(wǎng)頁的排序質(zhì)量。本文做了一些改進(jìn):區(qū)分站內(nèi)與站外鏈接的權(quán)值;加入時間因素，加速陳舊頁面權(quán)值下降速率;基于向量空間模型計(jì)算頁面內(nèi)容相似性。

1 相關(guān)工作

網(wǎng)頁搜索結(jié)果排序算法是搜索引擎最關(guān)鍵的技術(shù)構(gòu)成，影響結(jié)果排序有多種因素，其中最重要的是用戶查詢和網(wǎng)頁內(nèi)容的主題相關(guān)性以及網(wǎng)頁鏈接權(quán)威性。

1.1 向量空間模型

向量空間模型把每個文檔表示成向量形式［8］。假如有主題詞庫K(k1，k2，k3，…kn)和頁面Pi(Wi1，Wi2，Wi3，…Win)，n為主題詞庫K中關(guān)鍵詞個數(shù)，Wij是主題詞庫中關(guān)鍵詞kj在頁面Pi中的權(quán)值，它反映了kj對文本信息的表達(dá)能力。Wij采用Tf－IDF算法計(jì)算，其公式為:

由式1知，如果關(guān)鍵詞kj在一個文檔中出現(xiàn)的頻率越高，在其他文檔中出現(xiàn)的頻率越低，則該關(guān)鍵詞包含的信息量高，權(quán)重就越大。

1.2 RageRank算法

PageRank算法可以看做用戶在網(wǎng)絡(luò)拓?fù)鋱D中的隨機(jī)游走模型來解釋。假設(shè)用戶每次按統(tǒng)一概率d在當(dāng)前頁面提供的超鏈接中選擇下一步要訪問的鏈接，當(dāng)用戶在瀏覽到某一網(wǎng)頁放棄繼續(xù)點(diǎn)擊超鏈接，以概率1－d開始新的游走行為，在任何時刻，用戶在網(wǎng)頁P(yáng)的概率為:

2 基于PageRank算法改進(jìn)的頁面排序算法

2.1 區(qū)分站內(nèi)和站外鏈接

經(jīng)典的PageRank算法將網(wǎng)頁P(yáng)的PR值平均的分配給網(wǎng)頁P(yáng)所指向的鏈接網(wǎng)頁，但并不區(qū)分鏈接出去的頁面的權(quán)威度。也就是說，一個頁面P的PR值只與頁面P的入度和指向P的頁面的PR值有關(guān)，因此網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)決定了節(jié)點(diǎn)的重要性。然而，一個網(wǎng)頁中鏈出網(wǎng)頁的權(quán)威度參差不齊。不能很客觀的反映出鏈接內(nèi)容的重要性。而且，有些網(wǎng)頁設(shè)計(jì)者會利用添加本站的導(dǎo)航和廣告網(wǎng)頁鏈接進(jìn)行作弊行為，用來提高本站的搜索排名。因此經(jīng)典PageRank算法平均分配頁面權(quán)值是不合理的。本文對式2進(jìn)行改進(jìn)如下:

a(0＜a＜1)為控制站內(nèi)和站外鏈接的比重因子。一般站外鏈接比站內(nèi)鏈接更能客觀體現(xiàn)鏈接內(nèi)容的重要性，a取0.75。V1表示頁面P的所有入鏈中與P不是同一站點(diǎn)的網(wǎng)頁集合，Ci，Cj分別表示投票頁面i和j的所有鏈出頁面的鏈接數(shù)。V2表示網(wǎng)頁P(yáng)的所有入鏈中與P是同一站點(diǎn)的網(wǎng)頁集合。通過控制站外與站內(nèi)鏈接的比重來重新分配權(quán)值。避免了經(jīng)典算法中平均分配權(quán)值，考慮設(shè)計(jì)者通過作弊手段提高本站地址的權(quán)重，提高查找質(zhì)量。

2.2 時間衰減因子

經(jīng)典的PageRank算法通過鏈接關(guān)系來對網(wǎng)頁進(jìn)行權(quán)重分配。在互聯(lián)網(wǎng)上存在時間越長的頁面越容易被更多的頁面鏈接。新的頁面即使網(wǎng)頁內(nèi)容比較重要，被其他網(wǎng)頁鏈接也需要一個過程。針對PageRank偏重歷史頁面的問題，引入時間因子來對舊網(wǎng)頁做一個權(quán)值衰減過程。在式3的基礎(chǔ)上改進(jìn)如下:

式中，t為頁面存在的時間，λ為常數(shù)因子。通過加入時間衰減因子λ，能有效抑制互聯(lián)網(wǎng)上存在久的網(wǎng)站的權(quán)重增長的速度，使得新站不被老站埋沒。

2.3 內(nèi)容相似性計(jì)算

PageRank算法是利用網(wǎng)絡(luò)結(jié)構(gòu)中的反向鏈接信息對網(wǎng)頁進(jìn)行排序，它是一種與主題無關(guān)的排序算法。然而用戶瀏覽網(wǎng)頁時，一般都選擇與當(dāng)前頁面主題相關(guān)度較大的鏈接進(jìn)行頁面跳轉(zhuǎn)。針對經(jīng)典PageRank存在主題漂移的問題，在算法中加入主題相關(guān)度因子來提高主題相關(guān)頁面的權(quán)重。假設(shè)有頁面 P1(W11，W12，W13，…W1n)和主題向量 P2(W21，W22，W23，…W2n)，則網(wǎng)頁 P1的主題相似性利用特征向量之間的余弦夾角公式得:

式中，Wij為根據(jù)式1計(jì)算的相應(yīng)權(quán)值。

最后網(wǎng)頁綜合排序模型對得到的主題向量和本頁面的主題相關(guān)度Sim(P)和改進(jìn)的PR值賦予不同的權(quán)重，則網(wǎng)頁的相似性評分函數(shù)由式4、5得:

r1、r2分別為主題相關(guān)度的權(quán)重和PR值的權(quán)重，r1+r2=1。將主題相關(guān)度和鏈接分析相結(jié)合，不僅能夠體現(xiàn)鏈接的權(quán)威性，還能體現(xiàn)網(wǎng)站主題的相關(guān)性，可以提高排序結(jié)果的質(zhì)量，增強(qiáng)用戶的檢索體驗(yàn)。

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)基于Nutch網(wǎng)絡(luò)爬蟲技術(shù)，對互聯(lián)網(wǎng)上的食品安全信息進(jìn)行數(shù)據(jù)采集和正文信息抽取，然后基于Lucene［9］的全文檢索工具包，對本地?cái)?shù)據(jù)進(jìn)行分詞、倒排索引、索引檢索和改進(jìn)的相關(guān)度排序等處理，最終設(shè)計(jì)實(shí)現(xiàn)了一個面向食品安全信息垂直搜索引擎。

搜索引擎查詢結(jié)果的效果通常由查準(zhǔn)率來衡量查找過濾不相關(guān)文檔的能力，本實(shí)驗(yàn)重點(diǎn)檢查排序算法改進(jìn)后的查準(zhǔn)率，即前N個查詢結(jié)果中和查詢相關(guān)的網(wǎng)頁數(shù)與N的比率。本實(shí)驗(yàn)將一些食品安全的網(wǎng)站(中國食品安全網(wǎng)、擲出窗外等)首頁地址作為Nutch爬蟲的入口地址集合，總共爬取了11 275張網(wǎng)頁，把這些網(wǎng)頁作為實(shí)驗(yàn)文檔集。對Nutch網(wǎng)頁排序算法改進(jìn)之后，通過在搜索頁面輸入查詢詞，進(jìn)行Nutch改進(jìn)前后查準(zhǔn)率和排序效果的對比實(shí)驗(yàn)。在實(shí)驗(yàn)中選擇了食品安全方面的4個關(guān)鍵字進(jìn)行搜索。對每十條記錄進(jìn)行一次查準(zhǔn)率分析比較，結(jié)果如圖1所示。

圖1 算法改進(jìn)后各關(guān)鍵詞查準(zhǔn)率對比

將4個關(guān)鍵詞按算法改進(jìn)前進(jìn)行搜索，并計(jì)算其平均值，與圖1的結(jié)果平均值進(jìn)行比較，比較結(jié)果如圖2所示。

圖2 算法改進(jìn)前和改進(jìn)后平均查準(zhǔn)率對比

從圖1可以看出，每個關(guān)鍵詞得出的查準(zhǔn)率不相同，并且前十條記錄的查準(zhǔn)率基本上都在0.6之上，說明改進(jìn)的排序算法能夠很好的區(qū)分網(wǎng)頁，將相關(guān)度較高的網(wǎng)頁排在搜索結(jié)果的前面。

從圖2可以看出，通過修改排序算法，Nutch改進(jìn)后的查準(zhǔn)率明顯要高于改進(jìn)前，尤其是搜索結(jié)果的前列，改進(jìn)后的算法要優(yōu)于改進(jìn)前。說明該算法優(yōu)化了排序質(zhì)量，更符合廣大用戶的需求，具有現(xiàn)實(shí)可行性。

4 結(jié)束語

基于Nutch的垂直搜索引擎對網(wǎng)頁排序算法的主題相似性要求非常高。經(jīng)典的PageRank算法平均分配鏈出的PR值，沒有考慮鏈出頁面的權(quán)威性，并且忽略查詢的主題與內(nèi)容，容易導(dǎo)致主題漂移等問題。本文在分析和研究原始算法的基礎(chǔ)上，區(qū)分站內(nèi)與站外鏈接的權(quán)重，修正算法中偏重歷史網(wǎng)頁的問題，并且加入內(nèi)容相似性計(jì)算。實(shí)驗(yàn)表明，改進(jìn)后的算法可以明顯提高用戶的查準(zhǔn)率，提高用戶搜索的效果。下一步的工作是考慮在Nutch評分中加入用戶使用習(xí)慣的因素，進(jìn)一步改進(jìn)排序效果。

［1］Sergey Brin，Lawrence Page.The PageRank Citation Ranking:Bring Order to the Web［C］.Stanford:Computer Science Department，1998:107 －117.

［2］Pasquinelli M.Google's pagerank algorithm:a diagram of cognitive capitalism and the rentier of the common intellect［J］.Deep Search，2009(3):152 －162.

［3］Haveliwala.Topic-Sensitive PageRank:A Context-Sensitive Ranking Algorithm for Web Search［J］.IEEE Transactions on knowledge and data engineering，2003，15(4):784 －796.

［4］Richardson M，Domingos P.The intelligent surfer:probabilistic combination of link and content informaionin in PageRank［J］.Advances in Neural Information Processing Systems，2002，14(3):1 441 －1 448.

［5］張文龍，劉一偉，孫杰.基于Nutch的垂直搜索引擎的研究［J］.南開大學(xué)學(xué)報(bào)(自然科學(xué)版)，2012，45(2):37－44.

［6］陶林，諶超，強(qiáng)保華，等.基于Hadoop的Nutch網(wǎng)頁排序算法研究與實(shí)現(xiàn)［J］.桂林電子科技大學(xué)學(xué)報(bào)，2013，33(2):139－143.

［7］潘濤，梁正友.Nutch中網(wǎng)頁排序效果的改進(jìn)方法［J］.計(jì)算機(jī)工程，2010，26(13):42－44.

［8］Eric J Glover，Kostas Tsioutsiouliklis，Steve Lawrence，etal.Using web structure for classifying and describing web pages［C］.New York:Proceedings of the 11th international conference on World Wide Web，2002:562 －569.

［9］李永春，丁華福.Lucene的全文檢索的研究與應(yīng)用［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2010，20(2):12－15.