基于Nutch的網(wǎng)頁排序算法研究

武警七臺(tái)河支隊(duì) 徐再林武警杭州士官學(xué)院 陸明昕

?

基于Nutch的網(wǎng)頁排序算法研究

武警七臺(tái)河支隊(duì) 徐再林
武警杭州士官學(xué)院 陸明昕

【摘要】網(wǎng)頁排序算法對(duì)根據(jù)用戶查詢?cè)~搜索到的大量頁面進(jìn)行排序，從而返回給用戶，因此排序算法對(duì)搜索引擎的好壞起著關(guān)鍵作用。Nutch搜索引擎只實(shí)現(xiàn)了基本的綜合排序模型，針對(duì)Nutch默認(rèn)排序算法的不足，在PageRank算法中加入時(shí)間因子、鏈接權(quán)重因子，并結(jié)合HowNet來計(jì)算網(wǎng)頁的語義相似度，將改進(jìn)后的PageRank算法和基于語義的主題相關(guān)度算法應(yīng)用在Nutch排序算法中。實(shí)驗(yàn)結(jié)果表明：改進(jìn)的排序算法使得Nutch的搜索結(jié)果排序準(zhǔn)確率和首頁命中率都有了明顯提升。

【關(guān)鍵詞】網(wǎng)頁排序算法；Nutch；PageRank；語義相似度

1 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展，互聯(lián)網(wǎng)平臺(tái)上的數(shù)據(jù)呈現(xiàn)出指數(shù)增長的趨勢，人們對(duì)于搜索引擎的依賴性日益顯示出來。如何更快更準(zhǔn)確的檢索網(wǎng)絡(luò)中的海量信息，并將人們最需要的信息優(yōu)先返回給用戶，成了國內(nèi)外專家研究的熱點(diǎn)。Nutch作為網(wǎng)絡(luò)爬蟲和Lucene索引器的結(jié)合，功能強(qiáng)大。但Nutch存在以下缺陷[1-2]：沒有實(shí)現(xiàn)Google經(jīng)典PageRank算法，其自身網(wǎng)頁在線排序算法沒有衡量網(wǎng)頁重要性，偏重歷史網(wǎng)頁，沒有考慮網(wǎng)頁內(nèi)容相關(guān)性，沒有真正考慮到用戶的需求，影響了搜索的質(zhì)量和用戶的檢索體驗(yàn)。

基于以上問題，本文做出了一些相關(guān)改進(jìn)：首先，在PageRank算法中考慮時(shí)間和鏈接權(quán)重因素，并結(jié)合HowNet來計(jì)算語義相似度，從而實(shí)現(xiàn)將語義因素加入到主題相關(guān)度算法中，最后將改進(jìn)后的PageRank算法和基于語義的主題相關(guān)度算法結(jié)合起來，在Nutch中實(shí)現(xiàn)排序算法的改進(jìn)。

2 算法思想

2.1 PageRank 算法改進(jìn)

PageRank[3]算法是Google利用網(wǎng)絡(luò)拓?fù)鋱D離線計(jì)算網(wǎng)頁等級(jí)的排序算法，算法的主要思想是：被高

度鏈接的網(wǎng)頁可能是優(yōu)秀網(wǎng)頁；被優(yōu)質(zhì)網(wǎng)頁鏈接的網(wǎng)頁可能是優(yōu)秀網(wǎng)頁，其算法為公式(1)：

公式中,PR(A)是網(wǎng)頁A的PageRank值；PR(Ti)是鏈接指向網(wǎng)頁A的網(wǎng)頁Ti自身的PageRank值；NTi是網(wǎng)頁Ti的出鏈接總數(shù)；d為阻尼系數(shù)，一般取值為0.85。

針對(duì)PageRank原始算法的缺陷進(jìn)行以下改進(jìn)：

1）加入時(shí)間因子。針對(duì)PageRank算法注重舊網(wǎng)頁在公式中加入時(shí)間衰減因子：Δ=eλ/t,其中λ為時(shí)間的常數(shù)因子，t為網(wǎng)頁存在的時(shí)間，通過時(shí)間因子Δ能有效控制網(wǎng)站上存在時(shí)間比較長的網(wǎng)頁權(quán)重的增長速度，防止偏重舊網(wǎng)頁忽略了新網(wǎng)頁。

2）加入鏈接權(quán)重因子。PageRank算法的特點(diǎn)[4]是平均分配一個(gè)網(wǎng)頁的PR值，沒有區(qū)分鏈接出去的網(wǎng)頁的權(quán)威度，導(dǎo)致有些商家利用自身網(wǎng)站的導(dǎo)航和廣告鏈接來進(jìn)行網(wǎng)頁作弊行為[5]從而提高網(wǎng)站的搜索排名。針對(duì)以上缺陷，在PageRank算法中加入鏈接權(quán)重因子：

SA是指鏈接到當(dāng)前網(wǎng)頁A的前向鏈接數(shù)，將由網(wǎng)頁i出發(fā)鏈接到網(wǎng)絡(luò)中所有網(wǎng)頁組成一個(gè)序列，SK表示第k個(gè)網(wǎng)頁的前向鏈接數(shù)。鏈接權(quán)重因子使得網(wǎng)頁不再是根據(jù)鏈接數(shù)平均分配PR值，而是根據(jù)網(wǎng)頁前向鏈接數(shù)在所有競爭網(wǎng)頁前向鏈接總數(shù)中的比例來確定該網(wǎng)頁獲得PR值的比例，即確定當(dāng)前網(wǎng)頁前向鏈接的權(quán)重。

2.2 基于語義的主題相關(guān)度算法

PageRank算法只考慮到網(wǎng)頁之間的鏈接關(guān)系[6]，并沒有考慮到網(wǎng)頁的主題相關(guān)度，容易陷入“主題漂移”。本文利用HowNet（知網(wǎng)）計(jì)算網(wǎng)頁的語義相似度，將語義因素加入到主題相關(guān)度算法中去，在一定程度上提升了用戶檢索結(jié)果的全面性和準(zhǔn)確性。HowNet通過對(duì)詞語按照語義關(guān)系構(gòu)建網(wǎng)狀結(jié)構(gòu)[7]，詞語對(duì)應(yīng)于網(wǎng)狀結(jié)構(gòu)中的各個(gè)節(jié)點(diǎn)， HowNet中表示不可分割的最小單元是義原，用戶的關(guān)鍵詞通常具有多個(gè)意義，表示為義項(xiàng)，義項(xiàng)可以用多個(gè)義原互相組合進(jìn)行表示。

本文采用Wu-Palmer語義相似度算法[8]，也就是基于長度來定義網(wǎng)頁的語義相似度，其計(jì)算公式(3)為：

其中，Sim(A)表示語義相似度，C表示從網(wǎng)頁A中抽取出的待計(jì)算相關(guān)度的義原，T表示關(guān)鍵詞的義原集合，ISO(C,T)表示C和T的最近共有的義原，depth表示義原在HowNet中的路徑深度。

2.3 Nutch的排序算法改進(jìn)

在進(jìn)行網(wǎng)頁排序時(shí)，綜合考慮PageRank值與語義相似度，對(duì)每一個(gè)網(wǎng)頁設(shè)定一個(gè)價(jià)值V,該V值反應(yīng)了網(wǎng)頁與用戶需求之間的相關(guān)度，V值越大，則用戶需求度越大，進(jìn)行網(wǎng)頁排名時(shí)，則越靠前。其計(jì)算公式如公式(4)：

其中，V(A)表示網(wǎng)頁A的價(jià)值，β表示算法所占的權(quán)重，β取值0.8。

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

為了驗(yàn)證算法的性能，本文采用Nutch-1.2為網(wǎng)頁抓取工具進(jìn)行增量抓取，采用“戶外運(yùn)動(dòng)”為抓取對(duì)象，共收集戶外運(yùn)動(dòng)相關(guān)網(wǎng)站20個(gè)，無關(guān)網(wǎng)站8個(gè)，構(gòu)成本次實(shí)驗(yàn)的測試集合，利用Lucene建立索引。以“登山”“滑雪”“帳篷”“攀巖”為搜索關(guān)鍵詞（編號(hào)1-4）進(jìn)行檢索，在Nutch中用Java語言實(shí)現(xiàn)迭代排序算法，將搜索結(jié)果返回給用戶。衡量標(biāo)準(zhǔn)采用TopN查準(zhǔn)率[9]，數(shù)據(jù)顯示，用戶點(diǎn)擊第一頁的概率比較大，因此本文N=20，即首頁命中率。

從查詢關(guān)鍵詞“登山”的返回結(jié)果看，在改進(jìn)前返回的前20個(gè)頁面中，近三個(gè)月的頁面占據(jù)比例是1/4，而改進(jìn)后的返回結(jié)果中近三個(gè)月的頁面占據(jù)比例是7/20，可以看出，改進(jìn)后的PageRank算法在一定程度上提升了新網(wǎng)頁的比重。

4 小結(jié)

目前，搜索引擎是人們從浩瀚的數(shù)據(jù)海洋中獲取信息的重要渠道，針對(duì)Nutch默認(rèn)的排序算法的不足，本文在PageRank算法中加入時(shí)間因子和鏈接權(quán)重因子的基礎(chǔ)上，結(jié)合HowNet在算法中考慮了語義相關(guān)度，對(duì) Nutch默認(rèn)的排序算法進(jìn)行改進(jìn)，提高了Nutch的查準(zhǔn)率。本文還有不足之處，如在搜索引擎算法的速度方面進(jìn)行提升，有待下一步的工作進(jìn)行研究。

參考文獻(xiàn)

[1]陶林,諶超等.基于Hadoop的Nutch網(wǎng)頁排序算法研究與實(shí)現(xiàn)[J].桂林電子科技大學(xué)學(xué)報(bào),2013,33(2):139-140.

[2]施磊磊,施化吉等.基于Hadoop和HBased的Nutch網(wǎng)頁排序算法研究[J].軟件導(dǎo)刊,2014,13(10):53-54.

[3]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.

[4]Luo Wu,Fang Kui,Zhu Xing-hui.The ranking algorithms of search engine[J].Huan Agricultural Science,2010(7):137-140.

[5]劉發(fā)升,張菊琴.結(jié)合PCM聚類算法的網(wǎng)頁排序[J].計(jì)算機(jī)工程與科學(xué),2013,35(4):144-145.

[6]郭小溪.基于PageRank算法的分布式搜索引擎技術(shù)研究[D].大連交通大學(xué),2013:22-27.

[7]劉群,李素建.基于知網(wǎng)的詞匯語義相似度計(jì)算[J].中文計(jì)算語言學(xué),2002,7(2):59-76.

[8]王清霞.基于領(lǐng)域本體的垂直搜索引擎頁面排序算法的研究[D].蘭州理工大學(xué),2014:23-24.

[9]胡維華,曹奇峰.基于Nutch的頁面排序算法研究[J].杭州電子科技大學(xué)學(xué)報(bào),2013,33(6):76-77.