武警七臺河支隊 徐再林武警杭州士官學院 陸明昕

?

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

武警七臺河支隊 徐再林
武警杭州士官學院 陸明昕

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

【關鍵詞】網頁排序算法；Nutch；PageRank；語義相似度

1 引言

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

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

2 算法思想

2.1 PageRank 算法改進

PageRank[3]算法是Google利用網絡拓撲圖離線計算網頁等級的排序算法，算法的主要思想是：被高

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

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

針對PageRank原始算法的缺陷進行以下改進：

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

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

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

2.2 基于語義的主題相關度算法

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

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

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

2.3 Nutch的排序算法改進

在進行網頁排序時，綜合考慮PageRank值與語義相似度，對每一個網頁設定一個價值V,該V值反應了網頁與用戶需求之間的相關度，V值越大，則用戶需求度越大，進行網頁排名時，則越靠前。其計算公式如公式(4)：

其中，V(A)表示網頁A的價值，β表示算法所占的權重，β取值0.8。

3 實驗與分析

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

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

4 小結

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

參考文獻

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

[2]施磊磊,施化吉等.基于Hadoop和HBased的Nutch網頁排序算法研究[J].軟件導刊,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ā)升,張菊琴.結合PCM聚類算法的網頁排序[J].計算機工程與科學,2013,35(4):144-145.

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

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

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

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