張 玲，祁玉娟，姜 華

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

改進(jìn)的Shark-search算法在網(wǎng)絡(luò)采集中的應(yīng)用

張 玲，祁玉娟，姜 華

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

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

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

0 引 言

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 算法描述

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

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

2.2 相關(guān)性計(jì)算

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

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

(1)

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

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

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

(2)

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

2.3 反饋機(jī)制

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

2.4 主題漂移情況的處理

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

3 實(shí) 驗(yàn)

為了比較算法性能，文中比較了兩種Web采集者。一種是傳統(tǒng)的Shark-search，一種是提出的綜合了頁面分塊和反饋調(diào)整的Shark-search。實(shí)驗(yàn)?zāi)康氖遣杉黝}“計(jì)算機(jī)軟件”的頁面，采用搜索精度來比較算法性能，公式如下[13]：

(3)

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

(4)

圖1為搜索精度比較圖。

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

圖1 搜索精度比較圖

4 結(jié)束語

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

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

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

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

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

[4] 李廣麗.基于網(wǎng)頁內(nèi)容評價和Web圖的啟發(fā)式垂直搜索策略的設(shè)計(jì)[J].情報(bào)理論與實(shí)踐,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] 羅方芳,陳國龍,郭文忠.基于改進(jìn)的Fish-search算法的信息檢索研究[J].福州大學(xué)學(xué)報(bào),2006,34(2):184-188.

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

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

[9] 張瑞雪，宋明秋，公衍磊.逆序解析DOM樹及網(wǎng)頁正文信息提取[J].計(jì)算機(jī)科學(xué)，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].計(jì)算機(jī)應(yīng)用,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é)構(gòu)挖掘質(zhì)量的新方法[J].計(jì)算機(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)絡(luò)出版時間：2017-06-05

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

張 玲(1979-),女(土家族)，講師，碩士，研究方向?yàn)闄C(jī)器學(xué)習(xí)、智能信息處理、搜索引擎。

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