主題網絡爬蟲研究綜述
2007-12-31 00:00:00劉金紅陸余良
計算機應用研究 2007年10期
摘要：首先給出了主題網絡爬蟲的定義和研究目標；然后系統分析了近年來國內外主題爬蟲的研究方法和技術，包括基于文字內容的方法、基于超鏈分析的方法、基于分類器預測的方法以及其他主題爬行方法，并比較了各種方法優缺點；最后對未來的研究方向進行了展望。
關鍵詞：主題網絡爬蟲；信息檢索；Web挖掘
中圖分類號：TP391文獻標志碼：A
文章編號：1001-3695(2007)10-0026-04
0引言
隨著網絡上海量信息的爆炸式增長，通用搜索引擎面臨著索引規模、更新速度和個性化需求等多方面的挑戰[1，2]。面對這些挑戰，適應特定主題和個性化搜索的主題網絡爬蟲(focused crawler or topical crawler)應運而生[3，4]?；谥黝}網絡爬蟲的搜索引擎（即第四代搜索引擎)已經成為當前搜索引擎和Web 信息挖掘中的一個研究熱點和難點。
通用網絡爬蟲的目標就是盡可能多地采集信息頁面，而在這一過程中它并不太在意頁面采集的順序和被采集頁面的相關主題。這需要消耗非常多的系統資源和網絡帶寬，并且對這些資源的消耗并沒有換來采集頁面的較高利用率。主題網絡爬蟲則是指盡可能快地爬行、采集盡可能多的與預先定義好的主題相關的網頁。主題網絡爬蟲可以通過對整個Web按主題分塊采集，并將不同塊的采集結果整合到一起，以提高整個Web的采集覆蓋率和頁面利用率。
1主題爬蟲的定義和研究目標
定義1網絡爬蟲是一個自動提取網頁的程序，它為搜索引擎從Web上下載網頁，是搜索引擎的重要組成部分。通用網絡爬蟲從一個或若干初始網頁的URL開始，獲得初始網頁上的URL列表；在抓取網頁的過程中，不斷從當前頁面上抽取新的URL放入待爬行隊列，直到滿足系統的停止條件。
定義2主題網絡爬蟲就是根據一定的網頁分析算法過濾與主題無關的鏈接，保留主題相關的鏈接并將其放入待抓取的URL隊列中；然后根據一定的搜索策略從隊列中選擇下一步要抓取的網頁URL，并重復上述過程，直到達到系統的某一條件時停止。所有被網絡爬蟲抓取的網頁將會被系統存儲，進行一定的分析、過濾，并建立索引，對于主題網絡爬蟲來說，這一過程所得到的分析結果還可能對后續的抓取過程進行反饋和指導。
定義3如果網頁p中包含超鏈接l，則p稱為鏈接l的父網頁。
定義4如果超鏈接l指向網頁t，則網頁t稱為子網頁，又稱為目標網頁。
主題網絡爬蟲的基本思路就是按照事先給出的主題，分析超鏈接和已經下載的網頁內容，預測下一個待抓取的URL以及當前網頁的主題相關度，保證盡可能多地爬行、下載與主題相關的網頁，盡可能少地下載無關網頁。相對于通用網絡爬蟲，主題網絡爬蟲需要解決以下四個主要問題：
a)如何描述或定義感興趣的主題（即抓取目標）？
b)怎樣決定待爬行URL的訪問次序？許多主題網絡爬蟲根據己下載網頁的相關度，按照一定原則將相關度進行衰減，分配給該網頁中的子網頁，而后將其插入到優先級隊列中。此時的爬行次序就不是簡單地以深度優先或廣度優先順序，而是按照相關度大小排序，優先訪問相關度大的URL。不同主題網絡爬蟲之間的區別之一就是如何計算URL的爬行次序。
c)如何判斷一個網頁是否與主題相關？對于待爬行或己下載的網頁可以獲取它的文本內容，所以可以采用文本挖掘技術來實現。因此不同主題網絡爬蟲間的區別之二就是如何計算當前爬行網頁的主題相關度。
d)怎樣提高主題網絡爬蟲的覆蓋度？如何穿過質量不好(與主題不相關)的網頁得到與用戶感興趣主題相關的網頁，從而提高主題資源的覆蓋度？
對于主題網絡爬蟲性能的評價，目前主要是基于harvest rate來評價。Harvest rate就是主題相關網頁數目占所有抽取網頁總數的比率:
harvest rate=numbers of relevantpages/numbers of all retrival pages(1)
2主題網絡爬蟲研究進展
為了高效地抓取與主題相關的網絡資源，研究者提出了許多主題定制爬行策略和相關算法，使得網絡爬蟲盡可能多地爬行主題相關的網頁，盡可能少地爬行無關網頁，并且確保網頁的質量。通過對這些方法進行比較分析，本文將它們分為如下四類。
2．1基于文字內容的啟發式方法
基于文字內容的啟發策略主要是利用了Web網頁文本內容、URL字符串、錨文字等文字內容信息。不同的分析方法構成了不同的啟發式策略和相應的算法。主要包括：
a）Best first search方法?；舅枷胧墙o定一個待爬行URL隊列，從中挑選最好的URL優先爬行。爬行主題采用關鍵詞集合來描述，待爬行URL的優先級是根據主題詞和已爬行網頁p的文字內容來計算，用它們的相關度來估計p所指向網頁的相關度。相關度大的網頁，它所指向的網頁優先級就高，從而決定了待爬行隊列中URL的優先級順序。如果待爬行隊列的緩沖區滿了，則將優先級最低的URL從該隊列中移去。它采用式（2）來計算網頁與主題間的相關度。
b）Fish search方法。1994年由學者De Bra等人[8]提出。它將在網絡上遍歷的網絡爬蟲比喻成海里的一群魚。當它們發現食物(相關信息)時，這些魚就繼續繁殖，尋找新的食物；當沒有食物時(沒有相關信息)或水被污染(帶寬不夠)時，它們就死掉。該算法的關鍵是根據代表用戶感興趣主題的種子站點和主題關鍵詞，動態地維護待爬行的URL優先級隊列。
當一個網頁抓取過來后，抽取它所有的 URL，這些URL所對應的網頁，稱為其孩子網頁。如果抓取的網頁相關，孩子網頁的深度(depth)設成一個預先定義的值；否則孩子網頁的深度設置成一個小于父親網頁深度的值。當這個深度為零時，該方向的搜索就停止。
Fish search算法的入口參數包含種子站點、查詢式(主題)、查詢寬度width、深度depth。深度大于0的孩子網頁的URL按照如下啟發策略插入到url_queue中：
a） 相關網頁的前面α×width個孩子(α是預定義的大于1的常量)加入到url_queue的頂部;
b）無關網頁的前width個孩子URL加入到url_queue隊列中，緊靠著相關網頁孩子節點的后面;
c）剩下的孩子URL加入到url_queue的尾部(即只有在時間允許的情況下，才有可能爬行到)。
上述三種情況可以用一個變量potential_score來等價描述它們。第一種，potential_score設置為1；第二種設置為0.5；第三種設置為0，待爬行URL隊列就按照potential_score來排序。
該算法是一種基于客戶端的搜索算法。因為其模式簡單、動態搜索，有一定的吸引力，但存在如下缺點：只使用簡單的字符串匹配分配potential_score的值，并且該值是離散的(只有1、0.5和0三種)；分配的值并不能完全代表與主題的相關度。在url_queue中，優先級值之間的差別太小。當很多URL(節點)具有相同的優先級并且在爬行時間受到限制時，可能后面更重要的網頁被忽略掉了。另外，使用width參數來調節刪除網頁后面URL的個數也有點過于武斷，可能導致丟掉很多主題相關的重要資源。
c）Shark search方法[9]。它在fish search算法的基礎上進行了如下改進：
(a)在fish算法中，只有是否相關的二值判斷，而在shark算法中引入了相似度度量方法，取值為0~1。
（b）在計算URL的potential_ score上，不但繼承了雙親的值，而且充分利用了錨文字和錨文字的上下文。錨文字的上下文是指圍繞在錨文字周圍一定距離的文字。
與fish算法相比，shark算法精度更高，能更好地保證爬行器正確的搜索方向，提高相關信息的發現率。
2．2基于Web超鏈圖評價的方法
基于文字內容的算法只是利用網頁、URL、錨文字等文字信息，沒有考慮到通過超鏈而形成的Web有向圖對主題網絡爬蟲的影響?；赪eb圖的啟發策略的基本思想來自于文獻計量學的引文分析理論。盡管引文分析理論的應用環境與Web并不相同，但到目前為止，網頁之間的超鏈還是比較有價值的一種信息。基于Web超鏈圖評價的爬行算法有以下幾種：
a)BackLink。一個網頁被其他網頁所引用的次數越多，就說明越重要。待爬行URL隊列按照BackLink的數量來排序，數量大的優先爬行。
b)PageRank。基于Web圖，按照式（2）來計算每個網頁的PageRank值，然后對待爬行URL隊列按照PageRank的值進行排序。
PageRank算法是由Google的創始人S. Brin和L. Page提出的，它是一種與查詢式無關的算法[10]。在PageRank算法中，一個網頁的鏈入網頁數量越大，它的重要性就越大，而沒有考慮入鏈的質量問題。實際上，不同質量的網頁對網頁重要性的貢獻是不同的。簡單地說，按照BackLink算法，要想提高某網頁的重要性，只要建立許多網頁指向它就可以了。S. Brin和L. Page提出的PageRank算法就是為克服BackLink的這種不足而設計的。這種計算網頁權威度的具體計算方法如下：
每下載一個網頁后，抽取其中包含的超鏈，Web圖都需要作相應的改變，相應的優先級也需要重新計算?；赪eb圖的啟發策略計算量一般都很大，所以在實際的網絡爬蟲設計中，需要進行緩沖，只有下載網頁的數量達到設定的閾值后，才重新計算待爬行隊列的優先級值。
基于Web超鏈圖評價的啟發策略有如下缺點：存在很多的導航用超鏈，順著這些超鏈并不能發現更多的主題資源；PageRank更適合發現權威網頁，而不適合發現主題資源；基于圖的啟發策略的計算量一般都很大，嚴重影響了爬行器的爬行速度。
2．3基于分類器預測的方法
為了克服基于文字內容難以精確描述用戶感興趣的主題，以及基于Web超鏈圖分析的低效率，研究者提出了基于分類器導引的主題網絡爬蟲[11]，從而可以基于分類模型來描述用戶感興趣的主題和預測網頁的主題相關度。通過文本分類模型可以從更深的層次來描述用戶感興趣的主題信息，并可以更加準確地計算網頁的主題相關性，而不只停留在基于關鍵詞的匹配上。文本分類技術應用于主題信息搜索中有利于提高主題搜索的正確率和準確率。有關實驗結果[12~14]表明，使用主題分類器來指導網絡爬蟲爬行主題相關網頁的效果要好得多。
Chakrabarti等人[15]敘述了一些有關主題網絡爬蟲的實驗。他們的研究目標包括網頁的鏈接關系和半監督式學習等。該文中網絡爬蟲使用規范的主題分類，從用戶指定的起點(書簽)開始。用戶將感興趣的網頁做上標記，并將它們歸類，如同Yahoo的目錄層次結構。其主題網絡爬蟲的主要組成部分包括分類器、過濾器和爬行器。分類器對網頁作相關性判斷來決定訪問哪些鏈接；過濾器決定訪問網頁的優先級；爬行器是基于鏈接的分析。其中使用的評價指標稱為獲取率，獲取率表示的是獲取相關網頁的頻率，以及如何有效過濾不相關網頁。
Chakrabarti等人[16]提出了分別基于兩種不同的模型來計算網頁主題相關性和URL訪問次序。計算網頁主題相關性的模型可以是任何二值分類器，而計算URL訪問次序的模型（簡稱為apprentice）是通過包含父網頁和子網頁及其相關度的訓練樣本集合在線訓練得到的。對于每一個抽取的網頁，apprentice模型根據基本分類器（即二值分類器，以此確定父網頁屬于某一類別的概率）和父網頁鏈接周圍的特征進行訓練，以此來預測父網頁指向網頁的主題相關度。 然后基于這些相關度預測信息對待爬行隊列中的URL進行排序。實驗結果表明，爬行錯誤網頁的數目極大地減少了（大約減少了30%~90%）。
傅向華等人[12]將Web爬行看做執行序列動作的過程，結合改進的快速Q學習和半監督貝葉斯分類器，提出了一種新的具有在線增量自學習能力的聚焦爬行方法。該方法從獲取的網頁中抽取特征文本，根據特征文本評估網頁的主題相關性，預測鏈接的Q值，然后基于Q值過濾無關鏈接。當得到主題相關網頁時產生回報，然后將回報沿鏈接鏈路反饋，更新鏈路上所有鏈接的Q值，并選擇相應的特征文本作為訓練樣本，增量地改善主題評估器和Q值預測器。實驗結果表明，該方法具有很快的自學習能力，獲取的網頁數目和精度均優于離線聚焦爬行方法，更符合Web資源發現的要求。
李盛韜等人[17]在分析主題Web信息采集基本問題的基礎上，提出了主題網絡爬蟲的難點以及相關的解決方案，并在此基礎上設計實現了“天達”主題Web信息采集系統。李衛等人[18]以全信息理論為支撐，吸收傳統向量空間模型的思想，采用基于概念的向量空間模型，從詞的語義層次對文本進行主題相關性分析，研究并實現了一個基于主題的智能信息采集系統IFWC。其使用擴展元數據的語義相關性判定算法，對頁面內的URL進行主題相關性預測。
目前國內外對于基于主題分類器來引導主題Web爬蟲的研究還非常少[13]。S .Chakrabarti等人[11]第一次提出基于樸素貝葉斯分類模型引導主題Web爬蟲。Johnson等人[19]提出了基于SVM（support vector machine，支持向量機）分類模型來進行主題爬行。文獻[12，14]中通過實驗對比表明，基于線性SVM分類模型的主題Web爬蟲要比樸素貝葉斯分類模型的主題爬行效果好很多。
2．4其他主題爬行方法
J. Cho等人[7]提出通過先爬行更重要的網頁使得爬行更有效，而提出了各種計算網頁重要性的方法，如網頁與查找項的相關性、指向該頁的網頁個數(BackLinks)、該網頁的PageRank值和該網頁所處的位置。一個網頁的PageRank被遞歸地定義為指向該網頁所有網頁的PageRank權值之和。他們使用了基于這些重要性測量的排序機制實現了網絡爬蟲。該網絡爬蟲對斯坦福大學的網站(大約225 000個網頁)進行了測試。他們發現使用BackLink重要性測量的網絡爬蟲類似深度優先查找，在繼續訪問前先訪問特定簇里的網頁，并經常受起始點左右。使用PageRank的網絡爬蟲卻不受起始點影響，并結合了寬度優先和廣度優先，能更好地爬行。同時也發現在較小的網頁域中（如網頁的子集中），使用BackLink計數的網絡爬蟲執行效果不好。
文獻[5]中對不同的主題爬行策略進行了評價，它為每一百個主題建立一個分類器，用于評價已爬行過的網頁。作者認為一個好的主題網絡爬蟲在向量空間中也應該保證主題相關。他們畫了一個隨時間變化的拋物線圖，根據網絡爬蟲是否能保持主題相關來評價一個網絡爬蟲的性能。文中評價了三種不同爬行策略的網絡爬蟲：
a）BestFirst 網絡爬蟲。根據主題和網頁的相關性排列URLs的優先級隊列。
b)PageRank 網絡爬蟲。以PageRank的次序排列URLs，每25個網頁重新計算網頁的PageRank值。
c）InfoSpiders。采用后向傳播的中樞神經網絡，考慮鏈接周圍的文本。
最后實驗結果發現，BestFirst執行效果最好，其次是Infospiders，最后是PageRank。研究者認為PageRank在主題爬行任務中過于全面，所以效果不好。
M. Diligenti等人[20]提出了使用上下文圖表來引導主題網絡爬蟲。作者認為該領域主要的問題是在爬行中把任務分配給網頁。例如，一些偏離主題的網頁指向符合主題的網頁，結果形成頁層次結構?；谶@些問題，提出了基于上下文的網絡爬蟲?；谏舷挛牡木W絡爬蟲使用一個通用搜索引擎來獲取鏈接到專門文本的網頁，并為該文本建立上下文圖表。該上下文圖表用于訓練一組分類器，根據與目標的鏈接距離的預測值將文本歸類。每個種子頁都有相應的上下文圖和分類器，并能夠逐層建立直到特定的等級。這樣網絡爬蟲能夠獲取與目標主題直接或間接相關的內容，以及通向目標非常簡單的路徑模型。與普通的寬度優先和傳統的主題網絡爬蟲相比，上下文主題網絡爬蟲 (CFC)的每一層都使用貝葉斯分類器，最先使用最短路徑。使用的評價機制是下載的相關網頁的比率。實驗表明，CFC維護了更高的相關性。
C. Aggarwal等人[21]提出了Web主題管理系統(WTMS)。他們使用主題爬行技術，只下載相關網頁附近的網頁(如雙親、孩子和兄弟)。它基于對網頁的向量空間表示，網絡爬蟲下載所有包含主題關鍵詞的URLs。最后，它為每個特定的類固定了一個相關性域值。如果相關性值下降到某個特定值，將停止下載。該論文的另外一個方面是使用基于Hubs和Authorities對站點進行邏輯分組的方法，講述了如何可視化主題。
A. McCallum等人[22]提出了使用加強學習的方法建立專門域的搜索引擎。貝葉斯分類器根據整個網頁的文本和鏈接文本對超鏈接進行分類。這樣為每個鏈接計算出了獎勵值，用于通過加強學習的方法來訓練網絡爬蟲。通過對計算機系站點的測試表明，與普通的寬度優先網絡爬蟲相比，主題網絡爬蟲在更少的時間里發現了更多的研究論文。
M. Ehrig等人[23]提出了一種基于ontology的相關度計算和主題爬行體系框架。首先經過網頁進行預處理后， 從網頁中抽取實體（即ontology中出現的關鍵詞）并進行頻率統計；然后針對用戶選擇的感興趣實體，在ontology圖上基于多種策略來計算主題相關度，即直接匹配方法、類別關系和復雜關系計算等方法。通過實驗與基本的主題爬蟲（即簡單通過關鍵詞的布爾匹配來計算主題相關度）進行比較。結果證明該方法harvest rate有了很大提高，但是它沒有與其他類型的主題爬蟲進行比較。
3主題網絡爬蟲的研究趨勢
綜上分析可知，未來主題網絡爬蟲的研究主要是圍繞如何提高鏈接主題預測的準確性，降低計算的時空復雜度，以及增加主題網絡爬蟲自適應性這幾個方面展開。
提高鏈接價值預測的準確性一直是近年來研究的焦點。將各類評價方法相結合，尤其是基于分類器的主題相關度預測和基于在線訓練、反饋的主題爬行方法值得進一步訓究。將目前信息檢索領域中的概念檢索理論應用于鏈接價值的計算，是一個新的嘗試方向。網絡爬蟲的爬行具有重復性，如何將Web動態變化的規律與先前搜索的統計結果相結合，以提高價值計算的準確性，是一個值得研究的問題。降低網絡蜘蛛在訓練、搜索過程中的計算復雜性，也是有待進一步研究的問題。目前的網絡爬蟲通常采用固定的搜索策略，缺乏適應性，如何提高網絡爬蟲的自適應性有待進一步研究。
4結束語
隨著人們對個性化信息服務需要的日益增長，基于主題爬蟲的專業搜索引擎的發展將成為搜索引擎發展的主要趨勢之一。主題網絡爬蟲爬行策略的研究，對專業搜索引擎的應用和發展具有重要意義。本文在給出主題網絡爬蟲的定義和研究目標的基礎上，對現有的主題爬行策略進行了分類，系統分析了它們的定制方法，比較了它們的優缺點。最后，給出了若干值得進一步研究的問題。
參考文獻：
［1］MURRAY B，MOORE A. Sizing the Internet[M].[S.l.]:Cyveillance Inc，2000.
[2]LAWRENCE S，GILES L.Accessibility and distribution of information on the Web[J].Nature，1999，400(8）：107109.
[3]CHO J， CARCIA M H. The evolution of theWebandimplication foran incremental crawler[C]//Proc of the 26th InternationalConference on Very Large Databases (NVLDB00).2000.
[4]BREWINGTON B E，CYBENKO C. How dynamic is the Web[C]//Proc of the 9th International World Wide Web Conference.2000.
[5]MENCZER F，PANT C，RUIZ M E.Evaluating topicdriven Web crawlers[C]//Proc of SIGIR’01. New Orleans， Louisiana:[s.n.]，2001:241-249.
[6]MENCZER F，PANTC，SRINIVASAN P.Topicdriven crawlers:machine learning issues[EB/OL].(2002-05-15).http://dollar.biz.uiowa.edu/~fil/papers.html.
[7]CHO J，GARCIAM H，PAGE L.Efficient crawling through URL ordering[J].Computer Networks and ISDN Systems，1998，30(17):161172.
[8]DeBRA P，HOUBEN G，KORNATZKY Y，et al.Information retrieval in distributed hypertexts[C]//Proc of the 4th RIAO Conference.New York:[s.n.]，1994:481-491.
[9]HERSOVICI M，JACOVI M，MAAREK Y S，et al.The sharksearch algorithm:an application: tailored Web site mapping[C]//Proc of the 7th International World Wide Web Conference.Brisbane:[s.n.]，1998:6574.
[10]BRIN S，PAGE L.The anatomy of a largescale hypertexual Web search engine[C]//Proc of the 7th World Wide Web Conference. Brisbane:[s.n.]，1998.
[11]CHAKRABARTI S，DOM B，INDYK P.Enhanced hypertext categorization using hyperlinks[C]//Proc of the ACM SIGMOD International Conference on Management of Data.Seattle:[s.n.]，1998:307-318.
[12]傅向華， 馮博琴， 馬兆豐，等.可在線增量自學習的聚焦爬行方法[J].西安交通大學學報，2004，38（6）：599-602.
[13]PANT G，SRINIVASAN P.Link contexts in classifierguided topical crawlers[J].IEEE Transactions on Knowledge and Data Engineering，2006，18(1):107122.
[14]PANT G，SRINIVASAN P.Learning to crawl:comparing classification schemes[J].ACM Trans Information Systems，2005，23(4):430-462.
[15]CHAKRABARTI S，BERG M van den，DOM B.Focused crawling：a new approach to topicspecific Web resource discovery[C]//Proc of the 8th tnternational Conference.Toronto:[s.n.]，1999.
[16] CHAKRABARTI S，PUNERA K，SUBRAMANYAM M.Acceleratedfocused crawlingthrough online relevance feedback[C]//Proc of the 11th International World Wide Web Conference.Hawaii:[s.n.]，2002.[17]李盛韜，趙章界，余智華. 基于主題的Web信息采集系統的設計與實現[J].計算機工程，2003，29(17):102104.
[18]李衛，劉建毅，何華燦，等.基于主題的智能Web信息采集系統的研究與實現[J].計算機應用研究，2006，23（2）：163166.
[19]JOHNSON J，TSIOUTSIOULIKLIS K，GILES C L.Evolving strategies for focused Web crawling[C]//Proc of Int’l Conf Machine Learning.2003.
[20]DILIGENTI M，COETZEE F，LAWRENCE S，et al.Focused crawling using context graphs[C]//Proc ofthe 26th InternationalConferenceonVery LargeDatabases(VLDB2000).Cairo:[s.n.]，2000.
[21]AGGARWAL C，ALGARAWI F，YU P.Intelligent crawling on the world wide Web with arbitrary predicates[C]//Proc ofthe 10th International World Wide Web Conference.Hong Kong:[s.n.]，2001.
[22]MCALLUM A，NIGAM K，RENNIE J，et al.Building domainspecific search engines with machine learning techniques[C]//Proc of 1999 AAAI Spring Symposium on Intelligent Agents in Cyberspace.Stanford， CA:Stanford University，1999.
[23]EHRIG M，MAEDCHE A.Ontologyfocused crawling of Web documents[C]//Proc of ACM Symposium on Applied Computing.2003.
“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
