一種新的面向主題的爬行算法
2009-01-01 00:00:00李衛疆趙鐵軍樸星海
計算機應用研究 2009年5期
（1.昆明理工大學 云南省計算機應用重點實驗室 昆明 650051； 2.哈爾濱工業大學 計算機科學與技術學院 哈爾濱 150001）
摘 要：雖然通用網絡爬行器已經給人們提供了極大的便利，但由于它的綜合性不具備面向專業的特點，在準確性和速度等方面存在不足；面向主題的爬行器能彌補這些不足。主要研究面向主題網絡爬行器兩個方面的問題，即如何充分地定義主題和有效地排序爬行器待下載鏈接隊列中的鏈接，使得只需訪問很少的不相關頁面就能夠得到很多相關的頁面鏈接。結合網頁的半結構化信息特征，提出了一種新的基于內容的爬行策略，實驗結果顯示是一種尋找主題相關頁面很有效的方法。
關鍵詞：爬行器； 主題； 面向主題
中圖分類號：TP301.6; TP393文獻標志碼：A
文章編號：1001-3695(2009)05-1663-04
New algorithm of topicoriented crawler
LI Weijiang1 ZHAO Tiejun2 PIAO Xinghai2
(1.Computer Application Key Laboratory of Yunnan Province Kunming University of Science Technology Kunming 650051 China; 2.School of Computer Science Technology Harbin Institute of Technology Harbin 150001 China)
Abstract:The general crawler provides more help to people for finding information in WWW. However it has some drawback in terms of precision and efficiency because of its generality and no specialty. This paper addressed two issues of the topicoriented Web crawler. One is how to make the definition of the topic the other is how to sort of links to be downloaded in the queue efficiently. It aimed to visit only relevant pages and got a great scale of hyperlinks which link to the relevant pages. The crawl method is a novel one which was based on the semistructured features of the website and content information. The results of experiment show that it is a very effective method for focused crawler.
Key words：crawler; topic; topicoriented
0 引言
目前，互聯網是人們獲得相關信息的最好途徑之一。隨著網絡信息內容的迅速增長及信息環境的日趨復雜，現有的以覆蓋所有網頁為目標的搜索引擎正面臨著嚴峻的挑戰。首先是網頁數量呈現爆炸性增長趨勢，搜索引擎無法索引所有的頁面，即使是目前全球最大的搜索引擎Google，其索引的頁面數量也僅占Web總量的40%左右[1]。另一方面，Web信息資源是動態變化的，而像Google這樣的搜索引擎為了維護其龐大的數據庫，其網頁信息的平均更新周期長達一個月左右，這樣的結果使得搜索引擎對用戶的返回結果中有相當一定比例是過時甚至是打不開的網頁。再次，傳統的搜索引擎提供的信息檢索服務，不能滿足人們日益增長的對個性化服務的需求。所以，面向主題的搜索研究就成為下一代信息檢索的研究熱點。
面向主題就是只針對一類主題或網頁，如文學、醫學、體育、音樂、MP3、軟件等進行搜集。也就是說只搜集網絡的一個子集。它有選擇性地在網絡上搜集與事先確定的主題相關的網頁。主題，也就是用戶所要搜集的類型定義，可以由用戶指定的一系列網頁來確定，也可以由一系列描述類型特征的特征詞來確定。它所涉及的主要技術有信息挖掘、文本分類、文本提取、網絡搜集等。 一般而言 先由用戶確定一系列的樣本網頁來確定所搜集的主題； 然后進行特征提取 分析樣本網頁，提取特征信息；之后在搜集過程中，根據這些特征信息，對每一個搜集的網頁均賦予一定的相關度。相關度越高，就說明與主題越相似。
面向主題的爬行技術是構造主題搜索系統的核心，針對特定主題研究如何利用爬行程序在網上進行有選擇的訪問，在Web中只下載那些與預定義的主題內容相關的頁面。這些預定義的主題不僅僅是使用一些關鍵字，還需要提供樣本文檔。不同于搜索所有Web頁面，對所有問題進行解答的通用搜索引擎，主題爬行分析每個頁面的鏈接，判斷哪些鏈接指向的頁面可能是與預定主題相關，對這些鏈接進行優先爬行，舍棄與主題無關的鏈接。它的目標是盡可能地收集與特定主題相關的網頁，同時最大限度地避免無關網頁的下載，這些對于節省硬件和網絡資源都是有明顯意義的。
主題爬行最早由Bra等人[2]提出，該方法通過二元分類方法對關鍵詞的簡單匹配來判斷網頁的相關性。在此基礎上，Hersovici等人[3]將此方法延伸，綜合考慮網頁以及鏈接錨文本的相關性對網頁中的URLs按照優先權進行排列，通過乘上一個衰減因子來繼承父親頁面的相關性。與Bra等人的方法不同，該方法在向量空間模型并且可以在0~1的實數上任意取值，錨文本和上下文也要進行相似性計算。Cho等人[4]也對寬度優先方法進行了改進，改進不是很大，但是該方法在計算URLs優先權值時采用了PageRank[5]方法。作為網絡信息檢索工具，主題爬行技術近幾年來確實得到了越來越多的研究人員的關注[6，7]。
目前國內的面向主題的搜索系統還處于起步階段，尚沒有很成熟的系統。 各大網站所提供的目錄式搜索(即分類搜索)，一般都是采用人工分類的形式。 只要面向主題的搜集算法足夠好，在很大程度上可以代替這種人工分類的方法。
1 相關工作
1.1 通用網絡爬行器
網絡爬行器又稱為Robots、Crawler、Spiders和Wanderers，幾乎與網絡同時出現。第一個網絡爬行器是MatthewGray的Wanderer在1993提出來的。在開始的兩屆國際萬維網會議上出現過數篇關于網絡爬行器的論文，如文獻[8，9]，但是那時候互聯網上的信息規模比現在要小得多，它們并沒有闡述如何處理現在所面臨的海量網絡信息的技術。每個搜索引擎的后臺，都有相應的網絡爬行器在工作著，但是出于互相競爭的原因，這些網絡爬行器的設計并沒有公開，除了Google Crawler、Internet Archive Crawler以及Mercator[10]。
搜索引擎Google中采用了多臺機器進行分布式爬行[10]。它的網絡爬行器包括五個功能模塊，分別運行在不同的進程中。一個URLServer進程負責從一個文件里讀取URL（uniform resource locator），并把它們分發給多個crawler進程。每個crawler進程運行在不同的機器上，采用單線程和異步I/O同時從近300個網站上獲取數據。所有的crawler將下載來的數據傳輸到同一個StoreServer進程，它將這些頁面壓縮并存放在磁盤上。Indexer進程將這些頁面從磁盤上讀出，它將URL從HTML頁面中抽取出來，并將它們存放在另一個磁盤文件中。一個URLResolver進程讀取這個存放鏈接的文件，將其中的相對鏈接轉換為絕對鏈接，然后存入一個文件，這個文件供URLServer進程讀取。典型的，3、4臺機器用于爬行，整個系統大概需要4～8臺機器。
Internet ArchiveCrawler也使用多臺機器進行爬行[11]。每個crawler進程可分配64個站點同時爬行，并且每個站點最多只分配給一個crawler來爬行。每個單線程的crawler進程從磁盤中讀取分配給其爬行的站點的種子URL，把它們發送到各自站點的爬行隊列中；然后采用異步I/O從這些隊列讀取鏈接，下載對應的網頁。一旦一個HTML網頁下載下來，crawler就將包含在其中的鏈接抽取出來。如果鏈接指向同一個網站，那就將該鏈接加入到該站點的隊列中；否則，就將該鏈接存放到磁盤中。一個批處理進程周期地將這些鏈接進行過濾，去除重復鏈接，并把它們放入相應站點的隊列中。
1.2 面向主題的網絡爬行器
目前，Web主題信息搜集的主要方法來源于Chakrabarti等人[12]于1999年構建的Focused Crawling系統。該系統采用基于樣例網頁驅動的主題信息搜集方法，所搜集的主題信息由用戶通過選定樣例網頁來確定，并基于如下的假設：如果頁面u是一個與主題相關的頁面（正例），u到頁面v有一個超鏈接，則頁面v是正例的概率遠遠大于在Web上隨機抽取的一個頁面。
Focused Crawling系統抓取網頁的過程如下：首先由用戶從某一開放的分類目錄體系如Yahoo!中選取若干個子類節點作為主題信息，這些節點所包含的一些頁面作為訓練集，構造一個分類器。當抓取到一個新的頁面u時，首先提交到分類器進行相關度預測，如果頁面u是一個正例（頁面與主題信息的相關度超過某一個閾值），則由u指向的鏈接放入工作池（workpool）作為待抓取的鏈接；否則u被剪枝，其所指向的超鏈接亦不進一步抓取。
上面的系統中，分類器的選擇不是必需的，如Aggarwal等人[13]的Intelligent Crawling系統就是通過若干關鍵詞來定義主題信息的，但其效果在搜集頁面達到相當規模后才能體現出來，且對主題關鍵字較敏感。用戶也可以自己挑選若干樣例網頁作為主題信息的定義，但其效果往往低于從某一開放的分類目錄體系中選擇樣例，并構造分類器的結果。這主要在于幾個詞或頁面不能較好地特征化一個主題信息，特別是負例的選擇面太廣。
文獻[14]中詳細地描述了如何排序待下載隊列中的鏈接來最先取得更重要的頁面，或與主題最相關的頁面。這里的基本想法是，某個頁面如果與某個主題相關，那么該頁面上的鏈接也與這個主題相關。鏈接文本（anchor text）和鏈接周圍的文字可以很好地指示出這個鏈接所指向的頁面類型。還有一種基于鏈接的判斷頁面是否重要的方法，是利用頁面的出度、入度等網絡的結構化信息來計算。
通過排序待下載隊列中的鏈接方法來實現限定主題爬行的最大問題是缺少對挖道策略的支持。PageRank最著名的應用是在搜索引擎Google中用來對檢索所返回的文檔集合中的文檔排序[15]，它主要是一種采用頁面之間的鏈接結構來計算頁面重要度的方法。最近，也有一些研究采用PageRank來指導爬行器[14]和用來評估頁面的質量[16]。文獻[17]中用增強學習（reinforcement learning）的方法訓練一個爬行器，使得它可以有效地挖道。文獻[18]中用一個分類器和一個提純器作為主要的組件實現了一個限定主題的爬行器。這里的分類器用來確定是否與預定的主題相關；提純器可以找到那些包含大量相關鏈接的頁面（hubs）。
當前，面向主題的爬行器算法常用的方法是綜合網頁內容與鏈接文本方法。這種方法中比較有代表性的算法有FishSearch和SharkSearch算法。FishSearch魚群搜索算法由Bra等人[2]提出，算法模仿海中的魚群覓食現象，當食物（相關信息）找到時，魚（網絡爬行器）被繁殖繼續尋找食物，當食物缺乏（沒有相關信息）或水被污染（網絡帶寬不足）時，魚死掉。針對FishSearch存在的問題，Hersovici等人[3]進行改進，提出了SharkSearch算法，主要改進了頁面和查詢q的相關度計算和Potential Score的計算方法。
2 面向主題的爬行算法
2.1 主題確定
限定主題是面向主題的網絡爬行器與一般的網絡爬行器的最大區別。如何定義主題類是一個如何完整地規范用戶需求的問題。如果只是泛泛地告訴爬行器去把Web上關于籃球的頁面都找出來，爬行器可能不知道一個關于姚明的頁面是否應該屬于這一類；爬行器對于籃球這個領域的了解僅僅是籃球這個詞本身。更復雜的時候，可能用戶需要找到Web上的關于北京和非典，但卻不包括禽流感的頁面，這時候更需要有好的辦法來定義主題，了解用戶的興趣。
在本文中主題特征分為兩個層次，各為一個詞組的集合。第一個層次叫做主關鍵詞組；第二個層次叫做次關鍵詞組。
首先將用戶輸入的主題內容（一句或一段描述主題的文本）作為一個查詢輸入給百度（http://www.baidu.com），將百度給出的前二十個網頁結果抓取下來，作為與主題相關的典型網頁（訓練集）；然后分別對用戶輸入的主題內容和抓取得到的訓練集進行分詞、去停用詞和詞頻統計分析等處理；提取出現頻率較高的詞，刪除其中的常用普通詞和無意義的詞后，將它們作為該主題的相關特征。這樣形成了兩個集合，用戶輸入的主題內容對應的是主關鍵詞組，抓取得到的訓練集對應的是次關鍵詞組，這些就構成了后面判斷的基礎。
2.2 爬行算法
本文主要采用了基于內容的爬行策略，考慮了網頁內容和鏈接文本兩部分，同時輔以網頁的半結構化特征和網絡拓撲結構的相關特征。爬行算法如下：
輸入：主題t、頁面內容相關度閾值t1、鏈接文本相關度閾值t2、爬行頁數閾值t3；
輸出：下載的主題相關網頁
begin
a)如果鏈接隊列不為空，或爬行頁數＜t3;
b)取出一個相關度最高鏈接，并下載該鏈接所指頁面文檔內容p，對該頁面計算其與主題的相關度
relevance(p)=similarity(p，t);
c)if relevance(p)＜t1，丟掉該網頁以及網頁中的所有鏈接，轉h)；
d)對該網頁鏈接a進行評分，直到所有鏈接都被處理
relevance(a)=similarity(a，t);
e)if relevance(a)＜t2，丟掉該鏈接，轉g）；
f)如果該鏈接沒有被搜索過，把鏈接加入搜索隊列；
g）轉d）；
h）轉a）；
end
首先，根據網頁內容對鏈接評分。這種方法最基本的思想是計算某個頁面p與主題t的相似度來估計頁面p中的鏈接是否與主題t相關。通常，主題t可以表示為一些例子頁面，因此可以綜合成一個文本的形式。頁面p與主題t之間的相似度通常采用余弦相似度來計算。采用這樣的爬行策略還可以通過鏈接的分值來控制待下載隊列的大小，即當待下載隊列超過給定的閾值時，拋棄那些分值小的鏈接。
根據鏈接文本對鏈接評分。鏈接上的文本是網頁的作者對該鏈接指向內容的最簡短且明確的描述，因此，鏈接文本對于指導網絡爬行器的爬行很有意義。根據鏈接文本對鏈接進行評分時，計算鏈接文本a與主題t之間的相似度，以估計該鏈接是否與主題相關。同樣地，這種方法也可以很容易地拋棄分值低的鏈接。
由于網頁采用了半結構化的HTML語言，包含有豐富的結構信息，網頁中不同部分代表文檔的能力是不一樣的，
在抽取網頁的主題內容時應加以利用。位于〈head〉〈title〉〈meta〉以及〈a href =…〉等標記之內的關鍵詞無疑應該加以重視，賦予不同的權重評測系數。在對大量網頁的實際操作中發現，在諸多網頁標記中最能夠反映網頁內容的并不是直觀認為的〈title〉或〈meta〉間的文字，而是〈a href =…〉與〈/a〉之間的超鏈接文字。這主要是因為許多網頁的〈title〉并非經過作者的仔細推敲，有的是由網頁制作工具自動生成（如為index1，index2等），有的是作者賦予與主題無關的title（如“歡迎你的到來”），還有的是為了提升在搜索引擎結果中的排名，而故意欺騙網絡爬蟲（這種現象被稱為spider persuasion）。尤其是在〈meta〉標記中，對網絡爬蟲的欺騙更為常見。
在考慮了網頁的半結構化特征情況下，本文對于主關鍵詞在網頁中的權重作了如下的定義：
func(ti)=15 在超鏈接文字中10 在/head/title/H1/H2中9 在meta中5 其他（1）
對于次關鍵詞的定義如下：
func(ti)=11 在超鏈接文字中6 在/head/title/H1/H2中5 在meta中1 其他（2）
考慮到在一個頁面中，往往含有多個指向其他頁面的鏈接，這些鏈接中只有一部分是指向主題相關網頁的，或根據網頁的鏈接錨文本表明其具有較高重要性，其余的為大量的無關鏈接或廣告鏈接，如果把相關網頁中獲取的所有鏈接都進行下載的話，自然會大大影響爬行器的效率。根據觀察發現，頁面的相關鏈接是成塊集中放在一起的，而反映在其對應的HTML文件上就是它們處于緊密相連的位置上。因此本文將相關網頁中的鏈接分割成不同的塊，對于分割出來的無關鏈接塊和廣告鏈接塊就舍棄掉，只對那些相關鏈接塊中的鏈接進行下載。這樣做的好處是提高了效率，可以更快地獲得更多的相關網頁，不利之處在于很有可能會漏掉一些相關頁面。
3 實驗結果與分析
由于當前面向主題的搜索研究正處于起步探索階段，這方面的公共測試數據集很缺乏，為了驗證本文方法的效用，根據項目的實際，人為選定了一些主題，并搜集了一些網頁作為測試集。同時，這方面公開的最新算法也未見到，因此把本文的方法與通用搜索引擎算法進行了比較。
實驗包括6個主題，共9 128篇文檔，如表1所示。
表1 實驗數據表
主 題頁面數
電信運營商設備代維分析911
中國電信制造商走出國門的對策 617
中國電信軟件企業的發展思考1 227
3G與增值業務 3 192
非對稱管制對中國電信運營商企業運營的影響 669
日韓電信增值業務的發展比較2 512
本文選用了通用網絡爬行器中最常用的廣度優先算法（breadthfirst algorithm）和面向主題網絡爬行器中綜合網頁內容與鏈接文本的算法來對比實驗。采用不同搜索算法的爬行器依次對給定主題進行了搜索，下載的網頁根據網頁相關度分析算法來計算與主題的相似度。實驗分析結果如圖1所示。圖中給出了搜集的網頁數對應的相關網頁數。
結果表明本文所提出的算法相比其他兩種算法能夠較顯著地提高搜索到的相關網頁的數量，提高了面向主題搜索的效率。筆者很難得到整個網絡的主題分布情況，因此很難精確計算主題網絡爬行器的召回率，甚至可以認為是不可能的。但是可以用如下方法近似估算召回率：可以選擇一個比較大的門戶網站，如新浪、搜狐等，統計在一定范圍內與主題相關的網頁數，并把這個數作為與這個主題相關的所有頁面數，然后用本文的面向主題的網絡爬行器，在相同范圍內所抓取到的相關頁面數除以這個總數，就可以近似得到爬行器的召回率。
recalltopic=topicRelevant/count(Sina，Sohu)
其中：topicRelevant表示下載的與主題相關的網頁數；count(Sina，Sohu)表示在新浪、搜狐統計的與主題相關的網頁數。
在已經下載的網頁中，計算相關主題頁面個數與所下載的所有網頁個數的百分比所得到的結果就是面向主題網絡爬行器的精確率。
precisionTopic=topicRelevant/CrawledPages
其中：CrawledPages表示下載的網頁數。實驗結果如表2所示。
表2 爬行策略比較實驗
算法精確率/%召回率/%
廣度優先算法38.135.3
綜合網頁內容及鏈接文本的算法 54.773.2
本文的算法61.871.3
4 結束語
針對通用爬行器的不足，本文提出了一種面向主題的爬行算法。與通用爬行策略(廣度優先算法)相比，準確率由38.1%，提高到61.8%。同時，也優于流行的主題爬行算法(綜合網頁內容和鏈接文本的算法)的準確率54.7%，從而說明本文提出的算法是有效的。
參考文獻：
［1］LAWRENCE S GILES C L. Accessibility and distribution of information the Web[J]. Nature 1999，400:107-109.
[2]BRA P D HOUDBEN G KORNATZKY Y et al. Information retrieval in distributed hypertexts[C]//Proc of the 4th RIAO Conference.New York:[s.n.] 1994:481-491.
[3]HERSOVICI M JACOVI M MAAREK Y S et al. TheSharkSearch algorithm an application:tailored Web site mapping[C]//Proc of the 7th International World Wide Web Conference. 1998:317-326.
[4]CHO J. Efficient crawling through URL ordering[J]. Computer Networks and ISDN Systems 1998 30(1-7):161-172.
[5]PAGE L BRIN S MOTWANI R et al. The PageRank citation ranking:bringing order to the web[R]. Stanford:Stanford Digital Library Technologies Project 1998.
[6]GANT G SRINIVASAN P. Topicdriven crawlers:machine learning issues[C]//Proc of ACM TOIT. 2004.
[7]EHRIG M MAEDCHE A. Ontologyfocused crawling of Web documents[C]//Proc of the 2003 ACM Symposium on Applied Computing. 2003.
[8]McBRYAN O A. GENVL and WWWW: tools for taming the Web[C]//Proc of the 1st International World Wide Web Conference. 1994.
[9]PINKERTON B. Finding what people want: experiences with the Web Crawler[C]//Proc of the 1st International World Wide Web Conference. 1994.
[10]潘春華 常敏，武港山. 面向Web的信息收集工具的設計與開發[J]. 計算機應用研究 2002 19(6): 144-147.
[11]BURNER M. Crawling towards eternity: building an archive of the World Wide Web[J]. Web Techniques Magazine，1997，2(5):37-40.
[12]CHARKRABARTI S BERG M van den DOM B. Focused crawling: a new approach to topicspecific Web resource discovery[J]. Computer Networks ，1999，31(11-16):1623-1640.
[13]AGGARWAL C C AlGARAWI F YU P S. Intelligent crawling on the World Wide Web with arbitrary predicates[C]//Proc of the 10th International World Wide Web Conference. 2001:96-105.
[14]MENCZER F PANT G SRINIVASAN P et al. Evaluating topicdriven Web crawlers[C]//Proc ofthe 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 2001:241-249.
[15]BRIN S PAGE L. The anatomy of a largescale hypertextual Web search engine[J]. Computer Networks and ISDN Systems 1998，30(1-7):107-117.
[16]HENZINGER M HEYDON A MITZENMACHER M et al. Measuring search engine quality using random walks on the Web[C]//Proc of the 8th International World Wide Web Conference. 2001:213-225.
[17]RENNIE J McCALLUM A K. Using reinforcement learning to spider the Web efficiently[C]//Proc ofthe 16th International Conference on Machine Learning. San Francisco: Morgan Kaufmann 1999:335-343.
[18]沈紅芳. 互聯網搜索引擎及其功能優化模型[J]. 情報科學 2000，18(1):7-9.
