改進的Shark-search算法在網(wǎng)絡采集中的應用

張 玲，祁玉娟，姜 華

(湖南省第一師范學院 信息科學與工程學院,湖南 長沙 410205)

改進的Shark-search算法在網(wǎng)絡采集中的應用

張 玲，祁玉娟，姜 華

(湖南省第一師范學院 信息科學與工程學院,湖南 長沙 410205)

Shark-search是一種依據(jù)鏈接價值的高低進行優(yōu)先采集的算法，用于主題信息采集系統(tǒng)時由于只考慮了網(wǎng)頁文本和鏈接錨文本與主題的相關性而忽略了網(wǎng)頁的組織結(jié)構特性，在抓取有較多噪音鏈接的網(wǎng)頁時效果欠佳?；诰W(wǎng)頁組織結(jié)構特性的分析研究，提出了一種基于網(wǎng)頁主題分塊的Shark-search算法。該算法在經(jīng)典Shark-search算法的基礎上依據(jù)網(wǎng)頁組織結(jié)構根據(jù)網(wǎng)頁布局標簽對頁面內(nèi)容進行分塊，從網(wǎng)頁，塊和鏈接三個層面與主題的相關性得到鏈接的綜合價值，因而具有自學習功能，能統(tǒng)計學習與主題相關性較大的塊特征，并在發(fā)生主題漂移的時候具有自調(diào)整功能，給予主題相關性較大的父頁面上的鏈接更多被抓取的機會。采集實驗結(jié)果表明，所提出的算法在經(jīng)典Shark-search的基礎上能較好地改進主題信息采集的查準率，能夠更靈活地針對實際的Web資源狀況進行自調(diào)整。

Shark-search算法；網(wǎng)頁分塊；Web信息搜集；鏈接價值；主題漂移

0 引 言

近年來，互聯(lián)網(wǎng)技術發(fā)展迅速，搜索引擎的功能要求越來越豐富，傳統(tǒng)的搜索引擎已不能滿足人們的個性化服務需求[1]。因此，“專業(yè)搜索引擎”(Topic-Specific Search Engine)成為研究熱點[2]。http://search.sz.gov.cn/was40/szgonline/szgov_advsearch.jsp就是一個專用搜索引擎的例子。該網(wǎng)站以200多個深圳市政府相關網(wǎng)站作為信息源，利用網(wǎng)絡蜘蛛抓取上面的網(wǎng)頁，最大限度地過濾信息垃圾，返回給人們權威的專門信息。與此類似的還有企業(yè)和專業(yè)網(wǎng)站的搜索服務。專業(yè)搜索引擎搜索的內(nèi)容只限于專門領域，追求更高的搜索效率和準確率[3]，在專業(yè)搜索引擎中主題網(wǎng)絡爬蟲負責采集主題頁面，它的研究主要圍繞四個問題展開：

(1)怎樣定義待搜索的主題?

(2)怎樣決定待爬行URL的訪問次序?

(3)怎樣計算網(wǎng)頁與主題的相關性?

(4)怎樣盡快穿過與主題無關的網(wǎng)頁，找到主題相關的頁面?

主題網(wǎng)絡爬蟲一般根據(jù)鏈接文本內(nèi)容或者Web超鏈圖來判斷鏈接的價值，決定待爬行鏈接的訪問次序。判斷鏈接與主題的相關性有多種方法，主要是根據(jù)主題信息與鏈接錨文本的“語義”相似度來決定鏈接價值的大小，相似度較大的被賦予較高的鏈接價值。利用Web超鏈圖來判斷鏈接價值的主要算法有BackLink、Hits、PageRank等，主要是依據(jù)網(wǎng)頁的相互引用關系來決定鏈接價值[4]。另外，還有利用機器學習預測鏈接未來價值，利用貝葉斯分類器和遺傳算法來優(yōu)化網(wǎng)絡爬蟲等多種方法[5]。

在經(jīng)典Shark-search算法的基礎上，將頁面進行分塊，由鏈接所在父頁面、鏈接所在塊和鏈接錨文本相關性共同決定待搜索鏈接的綜合價值，以決定搜索的深度。該算法具有反饋機制，通過建立一個塊標志庫，將指向相關頁面的塊標志信息作為特征信息統(tǒng)計加入，用來輔助后續(xù)采集時的相關塊的判斷。在遇到主題漂移時，該算法會根據(jù)反饋自動調(diào)整各特征權值，重新計算隊列中鏈接的價值，給主題相關性較大的父頁面上的鏈接更多機會。

1 相關工作

Fish search是經(jīng)典的網(wǎng)絡遍歷算法，算法將進行網(wǎng)絡遍歷的網(wǎng)絡采集者比做水里的魚群。當采集者發(fā)現(xiàn)相關信息時，就產(chǎn)生更多的副本，尋找更多的相關信息；當沒有相關信息時，它們就結(jié)束爬行。當一個網(wǎng)頁被抓取后，抽取其上所有的鏈接，這些鏈接指向的網(wǎng)頁稱為孩子頁面。如果抓取的網(wǎng)頁是相關頁，則孩子頁面的抓取深度(depth)被設成一個預定義的值；否則孩子頁面的抓取深度就被設置成一個小于其父親網(wǎng)頁深度的值。隨著抓取的深入，當這個深度減為零時，順著該方向的搜索就停止[6]。

Shark search算法是Fish search的改進算法。在Fish search中，主題相關性的判斷是二值的，而在Shark算法中相關性的判斷更加量化，取值范圍為0～1[7]。Shark search算法不但考慮了父頁面與主題的相關值，還考慮了錨文字和錨文字的上下文等信息。Shark search算法相對于Fish search能更好地保證搜索朝正確的方向進行，提高主題信息的發(fā)現(xiàn)率。

經(jīng)過對很多專業(yè)主題的網(wǎng)頁分析可知，雖然網(wǎng)頁上有很多種類型的鏈接，但網(wǎng)頁上的鏈接一般都是組織有序的，與頁面同主題的鏈接被組織為一個一個的塊，例如“相關文章”、“同被引文獻”、“推薦閱讀”等。這些塊里面的有些鏈接即使本身的錨文本沒有包含明顯的主題信息，也依然有很大可能指向相關文檔。網(wǎng)頁上除了相關塊以外還有其他一些特定用途的塊，如導航塊、廣告塊等，對主題搜索來說被稱為“噪聲”塊。文中的意圖是通過網(wǎng)頁分塊技術，區(qū)分出相關塊和無關塊，并建立一個相關塊的特征庫來指導以后的爬行。

目前實現(xiàn)Web頁面分塊比較常見的技術是html標簽分類法和DOM樹分類法[8]，這兩種分類法都是根據(jù)網(wǎng)頁結(jié)構來進行分類。文中利用標簽布局將頁面中含有的鏈接進行分塊，并將一個塊中所有鏈接的錨文本組合起來判斷塊的相關性。當塊中某個鏈接被訪問后，根據(jù)它的實際主題相關性還可以反饋修改該塊的相關性判斷，從而修正該塊中其他鏈接的搜索深度。此外，還建立了一個塊特征庫，學習具有相關性指向意義的塊描述短語，例如“相關文章”、“相關文檔”、“同被引文獻”、“推薦閱讀”等，用來輔導相關塊的判斷。

2 算法描述

2.1 網(wǎng)絡蜘蛛模型

文中算法的網(wǎng)絡蜘蛛首先對抓取頁面進行頁面相關性分析，再按照Dom樹結(jié)構對網(wǎng)頁進行分塊[9]，最后根據(jù)網(wǎng)頁相關性、塊相關性和鏈接相關性進行綜合計算，得到鏈接的綜合價值，決定鏈接的爬行深度[10]。如果鏈接價值大于某閾值，則爬行深度被設為一預定義的值，否則爬行深度被設為一小于其父親網(wǎng)頁爬行深度的值，直到爬行深度為零。

2.2 相關性計算

待采集鏈接的預測價值由三部分組成：父頁面主題相關性、所在塊的主題相關性和自身錨文本的主題相關性。

頁面信息與主題的相似度，采用向量間夾角余弦公式[11]:

(1)

其中，q為主題關鍵字項；p為頁面塊文字項；fkd為項k在d中出現(xiàn)的頻率。

一個頁面被網(wǎng)絡爬蟲抓取后，即由式(1)計算出它與主題的相關性，若與主題相關性較大，則被判為主題相關頁，進入索引庫，同時根據(jù)它的相關性大小反饋修改與它同屬一個塊的兄弟鏈接的價值，并根據(jù)網(wǎng)頁布局標簽進行分塊[12]。位于同一分塊下面的所有鏈接錨文本組成本塊的特征文本，也按式(1)進行相關性計算，得到塊的相關性價值。鏈接本身錨文本則直接統(tǒng)計主題關鍵詞項在錨文本中出現(xiàn)的頻率。鏈接最終的價值由式(2)得到：

v=w1*vp+w2*vb+w3*vl

(2)

其中，v為待搜索鏈接的價值；vp為鏈接所在的父頁面相關性；vb為鏈接所在塊的相關性；vl為根據(jù)鏈接錨文本計算得到的鏈接相關性；w1、w2、w3為權值，權值越大意味著對應信息對預測鏈接的相關性越重要，文中經(jīng)過反復實驗比較取w1=0.3，w2=0.3，w3=0.4。如果塊標簽上具有塊特征庫里的信息，諸如“推薦文章”、“相關文檔”、“同被引文獻”等文本，則w1會被乘以大于1的系數(shù)，以增強塊同父頁面的相關性，而w3則相應地減少權值。

2.3 反饋機制

由式(1)計算出的塊的相關性價值只是根據(jù)塊中的鏈接錨文本與主題的文本相似性預測出來的，文中在鏈接被訪問得到實際的網(wǎng)頁相關性后對其所在的鏈接塊的價值進行修正，消除預測所引起的偏差，用于指導計算塊中還未采集鏈接的價值。如果預測的鏈接所在的塊價值較低但是指向的網(wǎng)頁相關度較高，則適度增大塊價值，反之，適度減少塊價值。塊價值得到修正后，塊上的鏈接價值也根據(jù)式(2)重新計算。對與主題相關性很大的塊，還建立了一個塊特征庫，學習具有相關性指向意義的塊描述短語，用來輔助后續(xù)采集時的相關塊的判斷。

2.4 主題漂移情況的處理

網(wǎng)絡爬蟲根據(jù)式(2)計算得到的鏈接價值進行網(wǎng)頁采集，鏈接價值越大的預測網(wǎng)頁與主題的相關性就越大，網(wǎng)絡爬蟲進行優(yōu)先采集。但是網(wǎng)絡爬蟲難免遇到主題漂移的情況，即被大量無關網(wǎng)頁包圍，網(wǎng)頁上很難再采集到鏈接價值較大的鏈接，采集隊列里充斥著大量價值較低的鏈接。文中在遇到主題漂移時，網(wǎng)絡爬蟲會根據(jù)反饋自動調(diào)整式(2)的各權值，重新計算隊列中鏈接的價值，適當增加式(2)中w1和w2的權值，減少w3的權值，即給主題相關性較大的父頁面上的鏈接更多機會，即使此鏈接本身的錨文本價值并不高。

3 實 驗

為了比較算法性能，文中比較了兩種Web采集者。一種是傳統(tǒng)的Shark-search，一種是提出的綜合了頁面分塊和反饋調(diào)整的Shark-search。實驗目的是采集主題“計算機軟件”的頁面，采用搜索精度來比較算法性能，公式如下[13]：

(3)

分別統(tǒng)計這兩種算法的網(wǎng)絡采集者抓取的頁面數(shù)和采集的相關計算機軟件網(wǎng)頁數(shù)，并計算兩者比例。搜索精度計算如下：

(4)

圖1為搜索精度比較圖。

由圖1可以看出，改進的Shark-search在采集精度上整體優(yōu)于傳統(tǒng)Shark-search算法，例如，當訪問了50%的頁面時，改進的Shark-search比傳統(tǒng)的Shark-search多采集了15%的主題相關頁面，具有更高的搜索效率，能夠更靈活地針對實際的Web資源狀況進行自調(diào)整。

圖1 搜索精度比較圖

4 結(jié)束語

為了更好地解決Shark-search算法在抓取網(wǎng)頁時由于只考慮網(wǎng)頁和鏈接文本與主題的相關性而忽略網(wǎng)頁的組織結(jié)構造成的主題漂移問題，在分析了Shark-search算法和網(wǎng)頁分塊技術之后，提出了一種基于網(wǎng)頁分塊的Shark-search算法。該算法利用網(wǎng)頁分塊技術對網(wǎng)頁進行分塊，并計算鏈接所處塊的主題相關性，鏈接的主題相關性由父頁面價值、鏈接所在塊價值和鏈接價值綜合計算得到，既考慮了網(wǎng)頁間的鏈接關系，也利用了網(wǎng)頁的組織結(jié)構和主題信息，很大程度上提高了信息采集的查全率，同時也過濾了大量的噪音鏈接，提高了搜索效率。

在下一步的工作中，將研究采用新的網(wǎng)頁分析技術更精確地分析網(wǎng)頁文本信息與網(wǎng)頁結(jié)構[14]，以期進一步提高預測鏈接價值的精確性。

[1] 傅 欣.第三代搜索引擎的智能化趨勢研究[J].現(xiàn)代圖書情報技術,2002(6):28-30.

[2] 張俊林.這就是搜索引擎:核心技術詳解[M].北京:電子工業(yè)出版社,2002.

[3] 張 博,蔡皖東.面向主題的網(wǎng)絡蜘蛛技術研究及系統(tǒng)實現(xiàn)[J].微電子學與計算機,2009,26(5):52-55.

[4] 李廣麗.基于網(wǎng)頁內(nèi)容評價和Web圖的啟發(fā)式垂直搜索策略的設計[J].情報理論與實踐,2009,32(9):121-124.

[5] Angiulli F,Pizzuti C.Outliermining in large high-dimensional data sets[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(2):203-215.

[6] 羅方芳,陳國龍,郭文忠.基于改進的Fish-search算法的信息檢索研究[J].福州大學學報,2006,34(2):184-188.

[7] 蘇 祺,項 錕,孫 斌.基于鏈接聚類的Shark-Search算法[J].山東大學學報:理學版,2006,41(3):139-143.

[8] 黃 歆,桑 楠.基于DOM樹和遞歸X-Y分割算法的Zone樹模型[J].計算機工程,2009,35(5):53-55.

[9] 張瑞雪，宋明秋，公衍磊.逆序解析DOM樹及網(wǎng)頁正文信息提取[J].計算機科學，2011,38(4):213-215.

[10] Brin S,Page L.The anatomy of a large-scale hypertextual Web search engine[C]//International conference on WWW.[s.l.]:[s.n.],1998:107-117.

[11] Srinivasan P,Pant G,Menczer F.Target seeking crawlers and their topical performance[C]//Proceedings of the 25th annual international ACM SIGIR conference on research and development in information retrieval.Tampere,Finland:ACM Press,2002:113-117.

[12] 黃文蓓，楊 靜，顧君忠.基于分塊的網(wǎng)頁正文信息提取算法研究[J].計算機應用,2007,27:24-26.

[13] Diligenti M,Coetzee F M,Lawrence S,et al.Focused crawling using context graphs[C]//Proceedings of the 26th international conference on very large databases.Cairo,Egypt:[s.n.],2000:527-534.

[14] 張 嶺,馬范援.加速評估算法:一種提高Web結(jié)構挖掘質(zhì)量的新方法[J].計算機研究與發(fā)展,2004,41(1):98-103.

Application of Improved Shark-search Algorithm in Web Crawler

ZHANG Ling,QI Yu-juan,JIANG Hua

(College of Information Science and Engineering,Hunan First Normal University,Changsha 410205,China)

The Shark-search algorithm ranks Web linkages based on their topic value,which only estimates the linkage’s value by pages’ text content and linkages’ anchor text,not taking into account the link structure of the Web and has not good enough performance in crawling web pages including many linkages irrelevant to topic.An improved Shark-search algorithm based on topical segments has been proposed,which segments the Web page into blocks on the basis of the page’s structure.The linkage’s integrated value is comprised of the parent page’s value,the block’s value and the linkage’s value.Moreover,it regards the visited out links as feedback to modify the block’s relevance resulting with self-learning to statistical the characteristic of blocks.It has the ability of self-adjusting in the case of topic-drift to give more chance to the linkages in the web pages more relevant to the topic.The results of experiment in Web crawler show the algorithm proposed can well improve the precision of topical information acquisition on the basis of the classical Shark-search and more flexibly adjusts according to actual Web resources status.

Shark-search algorithm;web page blocking;Web crawler;linkages’ value;topic-drfit

2016-04-19

2016-08-04 網(wǎng)絡出版時間：2017-06-05

湖南省教育科研基金(15C0284)

張 玲(1979-),女(土家族)，講師，碩士，研究方向為機器學習、智能信息處理、搜索引擎。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170605.1506.012.html

G354

A

1673-629X(2017)08-0192-03

10.3969/j.issn.1673-629X.2017.08.040