改進的Shark-search算法在網絡采集中的應用

張 玲，祁玉娟，姜 華

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

改進的Shark-search算法在網絡采集中的應用

張 玲，祁玉娟，姜 華

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

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

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

0 引 言

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

2 算法描述

2.1 網絡蜘蛛模型

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

2.2 相關性計算

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

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

(1)

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

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

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

(2)

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

2.3 反饋機制

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

2.4 主題漂移情況的處理

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

3 實 驗

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

(3)

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

(4)

圖1為搜索精度比較圖。

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

圖1 搜索精度比較圖

4 結束語

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

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

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

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

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

[4] 李廣麗.基于網頁內容評價和Web圖的啟發式垂直搜索策略的設計[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樹及網頁正文信息提取[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] 黃文蓓，楊 靜，顧君忠.基于分塊的網頁正文信息提取算法研究[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結構挖掘質量的新方法[J].計算機研究與發展,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 網絡出版時間：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