基于貝葉斯分類器的主題爬蟲研究

摘 要:主題爬蟲是實現定題搜索引擎的核心技術。提出了基于貝葉斯分類器實現主題爬蟲的方法，介紹了基于貝葉斯分類器的主題爬蟲的系統結構以及系統關鍵部分的實現，包括URL隊列、爬行歷史、頁面下載以及頁面分析，并重點介紹了基于貝葉斯分類器的主題相關度算法。爬蟲使用改進的TF-IDF算法來提取網頁內容的特征，并采用貝葉斯分類器計算其主題相關度。實驗結果表明，在搜索大量網絡資源的情況下，貝葉斯分類器比PageRank算法更適合用于實現主題爬蟲。

關鍵詞:貝葉斯; 分類器; 主題爬蟲; 主題相關度

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2009)09-3418-03

doi:10.3969/j.issn.1001-3695.2009.09.061

Research on focused crawler based on Bayes classifier

ZOU Yong-bina， CHEN Xing-shua， WANG Wen-xiana，b

(a.Network Trusted Computing Institute， Computer College， b.Institute of Information Security， Sichuan University， Chengdu 610064， China)

Abstract:Focused crawler is the core technology to implement a focused search engine. This paper made a research on focused crawler based on Bayes classifier， introduced the system architecture and key implementation of a focused crawler based on Bayes classifier. The key parts of the crawler include URL queue， crawling history， page downloader and page analyzer. This paper focused on the page ranking algorithm based on Bayes classifier.Used an improved TF-IDF algorithm to extract the characteristics of the page content， and adopted Bayes classifier to compute the page rank. The experiment results show that Bayes classifier is a better choice than PageRank algorithm to implement a focused crawler， under the condition of large network of resources.

Key words:Bayes; classifier; focused crawler; page ranking

0引言

隨著互聯網上資源的幾何級數增長，對網絡信息的采集面臨著索引規模、更新速度和個性化需求等多方面的挑戰[1]。針對這種情況，目前對主題爬蟲的研究漸漸成為網絡數據挖掘領域最熱門的方向之一。主題爬蟲是一種特殊的爬蟲，其主要目標是在有限的時間與網絡帶寬限制下盡可能多地采集與指定主題相關的高質量網頁，忽略與主題無關或低質量的網頁。因此，實現主題爬蟲的關鍵在于如何判斷網頁與主題的相關性。判斷網頁的主題相關度主要有兩種方式，即基于鏈接分析和基于內容分析。基于鏈接分析的方法基于網頁之間的鏈接來對其有直接或間接鏈接關系的對象作出評價。PageRank算法[2]和HITS算法[3]是最常見的鏈接分析算法，兩者都是通過對網頁間鏈接度的遞歸和規范化計算得到每一個網頁的重要度評價。目前的主題爬蟲大多采用基于鏈接分析的方法實現，實驗表明，這種方法更適合發現權威網頁，而不適合發現主題資源，而且其計算量一般都很大，嚴重影響了爬行器的爬行速度。

基于網頁內容的分析方法指的是利用網頁內容(文本、數據等資源)特征進行的網頁評價方法。這種方法的核心在于文本聚類算法的實現，常用的聚類算法有樸素貝葉斯、支持向量機(SVM)以及神經網絡等。其中，樸素貝葉斯的分類精度較高，且運行速度較快，能夠很好地滿足主題爬蟲對速度和準確度的要求。本文通過對網絡爬蟲與聚類算法的研究，實現了一個基于樸素貝葉斯分類器的主題爬蟲。經實驗表明，爬蟲的運行性能良好。

1 系統設計

主題爬蟲是對普通爬蟲的擴展，它在普通爬蟲的基礎上增加了特征提取和相關度分析模塊。特征提取模塊提取頁面的特征并將其表示成一個帶權的向量，而相關度分析模塊則將頁面的特征與目標主題進行相關度分析，并根據分析結果確定鏈接的優先級。優先級高的鏈接將被優先處理，從而能夠保證與主題的相關度最高的高質量頁面能夠在短時間內被獲取。

主題爬蟲的運行過程(圖1)如下:a)輸入需要爬行的主題和起始站點;b)相關度分析模塊對輸入的主題進行分析，得到目標主題的向量表示;c)爬蟲從URL隊列中獲取最佳站點地址并下載相應頁面;d)分析頁面，提取出其中的鏈接與鏈接所在的上下文;e)提取鏈接上下文的特征，得到其帶權的向量表示;f)相關度分析模塊計算鏈接上下文與目標主題的相關度，并根據相關度大小計算鏈接的優先級;g)跳至c)重新開始循環。

1.1 URL隊列

URL隊列是爬蟲的待執行任務列表，它保存了未訪問頁面的URL。URL隊列的底層是由動態數組實現的，數組的元素根據未訪問URL的估計優先級來進行排序，優先級相同的未訪問URL則根據發現的順序進行排序。如果所有的URL優先級相同或者沒有優先級，URL隊列的默認實現采用的是FIFO隊列，而廣度優先爬蟲則僅僅是本文所實現的最佳優先爬蟲的一種特例。

每次爬行一個頁面時，優先級最高的URL從隊首獲得。該URL所對應的頁面被下載后，頁面中的鏈接將被提取出來并根據啟發式算法計算其優先級，然后加入到URL隊列的優先級隊列中。為了防止URL隊列中出現重復的鏈接，還另外保存了一個hash表以供查詢，如圖2所示。

根據可用的內存數量可以決定URL隊列的最大容量。由于目前的PC普遍擁有大容量內存，保存10萬條以上URL的URL隊列并不少見，本文在所有實驗中采用的URL隊列大小均為10萬。在爬行過程中URL隊列會很快被填滿，假設每個頁面有7條鏈接，那么在爬行完成1萬個頁面時，URL隊列中大約會有6萬條URL[4]。如果鏈接的數量超過了URL隊列的最大容量(max)，URL隊列中僅保存max個優先級最高的URL，其余的URL將被忽略。如果爬蟲發現當它需要下一個URL時URL隊列為空，則爬行過程中止。

如果存在有大量URL指向同一個網頁的情況，則爬蟲很可能被陷入[5]。緩解這種問題的一種方法是限制爬蟲可以從一個域名中獲取到的網頁數量。在本文的解決方案中，URL隊列保證對于所爬行的k(如100)個頁面均來自k個不同的域名。這種方法的優點是使爬蟲給網站服務器造成的負載被大幅減小，而且所爬行的頁面內容更加多樣化。

1.2 爬行歷史

爬行歷史是一個已經被爬蟲下載過的URL列表，其中還包括了下載URL的時間，它展示了一個頁面到另一個頁面的爬行路徑。當URL所指向的頁面被下載后，該URL將被加入到爬行歷史中。爬行歷史可以被用來進行爬行后的分析，例如，可以為每個頁面關聯一個值，從而表示一些特殊事件(如發現了一些特別的資源)。為了在爬行完成后可以利用爬行歷史進行數據分析，爬行歷史在爬行完成時將被保存在磁盤上。

每當一個頁面被下載時，它可以被緩存以供進一步處理。本文實現了一個頁面倉庫用來將爬行過的頁面保存成獨立的文件，為此，每一個頁面需要映射到一個惟一的文件名。通過使用一個低碰撞率的hash函數(為了確保文件名惟一)，將頁面的URL映射成一個字符串，而該字符串就作為保存頁面的文件名。本文采用MD5算法來為每個URL生成一個128 bit的hash碼，該128 bit的hash值被轉換成16進制的32個字符，從而得到文件名，如http://www.scu.edu.cn/的內容被保存在名為355bd40a1cffbb871d1fce0048a19972的文件中。頁面倉庫還可以被用來檢查一個URL所指向的文件是否已經存在。如果頁面倉庫緩存了以前爬行的頁面，這些頁面沒有必要重新從網絡下載而可以直接使用。

1.3 頁面下載

頁面下載模塊負責從URL隊列獲得下一個(優先級最高的)URL并從網絡或本地的網頁倉庫獲取頁面。為了下載一個網頁，頁面下載模塊包含一個HTTP客戶端用來向服務器發送HTTP請求并讀取響應，該客戶端需要設置超時時間來保證不會在速度慢的服務器或讀取大文件上花費太多的時間。本文將HTTP客戶端限制為僅下載頁面的前10 KB。

爬行頁面時的另一個重要考慮是robot排除協議[6]。該協議提供了一種Web服務器管理員定義文件訪問策略的機制，用來詳細地指明哪些文件不能被爬蟲所訪問。Robot協議通過在Web服務器的根目錄下保存一個名為robots.txt的文件來實現(如http://www.163.com/robots.txt)，該文件定義了針對不同用戶代理(機器人或爬蟲)的訪問策略。當爬蟲從Web服務器下載一個頁面時，它必須先獲取合適的robots.txt文件并檢查要下載的URL是否被禁止。可以將最近訪問的服務器的robots.txt文件緩存以提升效率，從而避免每下載一個URL都去重新下載該文件，同時又必須保證所緩存的文件是最新的。本文的爬蟲實現遵循robot排除協議并緩存了最近訪問的1 000個服務器的robots文件。

1.4 頁面分析

當一個頁面被下載時，需要分析它的內容及提取信息，從而確定將來的爬行路徑。頁面分析和鏈接提取簡單來說負責提取超鏈接或URL，主要包括以下過程:清理HTML內容以分析HTML標簽樹;將提取到的鏈接轉換成一種規范形式;從頁面內容中刪除無用詞和提取剩下的文字。

對應于同一個網頁的不同URL可以被映射成一種規范形式，這可以用來防止重復獲取同一個URL。下面是本文實現所使用的URL規范化的步驟:

a)將協議和主機名轉換成小寫形式。例如，HTTP://www.SCU.edu.cn轉換成http://www.scu.edu.cn。

b)刪除錨點鏈接的引用部分。因此，http://www.scu.edu.cn/fap.html#what將被轉換成http://www.scu.edu.cn/fap.html。

c)對于常用的一些字符，如“～”進行URL編碼，這可以防止爬蟲將http://www.scu.edu.cn/～robin/與http://www.scu.edu.cn/%7Erobin/看做兩個不同的鏈接。

d)使用啟發式算法來識別默認的網頁。對于形如index.html或index.htm的文件名可以從URL中刪除，因為它們是默認的文件，從而可以僅僅根據目錄形式的URL來下載。

e)刪除URL路徑中的“..”和它的上級目錄，因此，形如/%7Erobin/sc/Seeds/../a.dat將被轉換成/%7Erobin/sc/a.dat。

f)如果URL中的端口號是80，則刪除端口號;也可以采用另一種方法，即保存所有URL中的端口號，如果沒有指定端口號，則加上80作為端口號。

2 主題相關度算法

2.1 特征提取

特征提取模塊負責將提取到的內容轉換成抽象的數學表示，這些表示將被分類器模塊用來計算未訪問URL的優先級。一個鏈接上下文的內容可以被表示成一個n維的向量。其中每一個元素對應于詞匯表中的一個詞。鏈接上下文是與頁面中的鏈接相鄰的內容，它提示了目標頁面的主題。作為一種極端的情況，整個網頁均可被看做是其中所有超鏈接的鏈接上下文。網頁中由HTML標簽形成的等級結構也可以被用來傳遞鏈接上下文。

代表鏈接上下文的向量中每一個元素都是一個表明了對應詞組重要性的權重。常用的文本取權算法是TF-IDF。其中TF部分表明了一個詞組在給定鏈接上下文中出現的次數，IDF則使在頁面中出現次數很多的詞組權值下降。鏈接上下文中沒有出現的詞組在向量中的對應元素其權值為0。

對于每一個主題，將所有來自肯定和否定樣本中的詞組放到詞匯表V中，每一個肯定和否定樣本被一個向量所表示，向量的每一個元素對應于V中的一個詞組。因此，將一個網頁p表示為一個向量xp=(w1p，w2p，…，wNp)。其中，wsp為網頁p中詞組s的權重，N為詞匯表V的大小。詞組的權重由改進的TF-IDF算法計算得到[7]，使用的計算式如下:

其中:tfsp為詞組s在網頁p中出現的頻率，即詞頻;Tp為網頁p中所有詞組的集合;E為包含肯定樣本和否定樣本的集合;dfs為E中包含詞組s的文檔數量(文檔頻率)。

2.2 貝葉斯分類器

貝葉斯分類器是基于著名的貝葉斯公式[8]實現的。它假設在給定類別的情況下，數據x服從一定的概率分布，如果類型為正，則x出現的概率為p(x|class=+1)。因此，利用貝葉斯公式，后驗概率Pr(class=+1|x)可以使用如下公式計算:

Pr(class=+1|x)=P(x|class=+1)#8226;Pr(class=+1)/P(x)

其中:Pr(class=+1)是相關類別的先驗概率，因此對于一個二類問題，有如下公式:

P(x)=P(x|class=+1)+P(x|class=-1)

樸素貝葉斯分類器的另一個假設是數據x的屬性是獨立分布的，因此，上述公式可以寫成:

Pr(class=+1|x)=Ni=1P(xj|class=+1)Pr(class=+1)/P(x)

其中:xj是向量x的第j個元素。

根據一個類別在訓練數據中出現的頻率來計算先驗概率Pr(class=+1)和Pr(class=-1)，因此對于確定的x，P(x)是一個常數，而樸素貝葉斯算法的訓練過程則僅僅是估計給定類型的元素分布。例如，對于所有的j估計p(xj|class=+1)和p(xj|class=-1)，有兩種方式可以對這些分布進行估計:

a)正規密度。在這種情況下，假定在給定一個類別時，其中的元素值均趨于正態分布。因此，針對每個xj，p(xj|class=+1)和p(xj|class=-1)均為帶有均值和方差的正態分布，僅需要估計均值和方差。由于已經根據肯定和否定類別的樣本進行了訓練，可以使用訓練的結果來估計需要的參數。使用訓練數據的最大似然估計來得到分布的均值和方差，這些估計值是每一個類型元素的樣本均值和方差。

b)核密度。如果去除正態分布的假設，就可以得到另一種估計p(xj|class=+1)和p(xj|class=-1)分布更強大的模型。用來計算p(xj|class=+1)的公式[9]如下:

P(xj|class=+1)=(1/n+)#8226;∑n+i=1k(xj，μi+，σi+)

其中:n+是屬于相關類別的訓練樣本數量;xji是向量xi(第i個肯定樣本的向量表示)的第j個元素;k是一個正態函數，其均值為μi+=xji，標準方差為σi+=1/n+。在公式中，先取出一個對象x(鏈接上下文)的向量表示的一個元素值xj，計算它與每個肯定訓練樣本的對應元素的平均距離，從而得到p(xj|class=+1)，p(xj|class=-1)的計算方式與此類似。元素之間的距離是使用高斯核函數[10]來計算的(也可以使用其他核函數)，本文的主題爬蟲正是采用核密度估計實現的。

在Pr(class=+1|x)和Pr(class=-1|x)計算完成后，對x進行分類就很簡單了。如果Pr(class=+1|x)>Pr(class=-1|x)，則x的類別為正，否則其類別為負。

3 實驗結果

本文的實驗采用北京大學計算機網絡與分布式系統實驗室提供的中文網頁分類訓練集作為訓練樣本，對主題爬蟲的分類器進行訓練，并將訓練結果保存在一個文件中;然后，使用幾個國內知名的門戶網站(http://www.sina.cn，http://www.163.com，http://www.tom.com)作為種子URL進行爬行。為了方便測試，將爬行深度設為5。該系統運行在一臺裝有Windows XP操作系統的PC上，內存容量為1 GB，硬盤大小為80 GB。系統運行時啟動了20個守護線程。實驗結果如圖3所示。

實驗分別對基于采用核密度估計的貝葉斯分類算法、采用正規密度估計的貝葉斯分類算法，以及PageRank算法的主題爬蟲進行了對比。實驗結果表明，在搜索初期，基于貝葉斯分類器的主題爬蟲其收獲率低于基于PageRank算法的主題爬蟲。然而隨著搜索頁面數量的增多，基于PageRank算法的主題爬蟲的收獲率下降較快，而基于貝葉斯分類器的主題爬蟲的收獲率則比較穩定。因此，對于網絡資源數量較多的情況，基于樸素貝葉斯分類器顯然是一種更好的選擇。

4 結束語

經過本論文的研究，實現了一個基于貝葉斯分類器的主題爬蟲，創新之處在于采用貝葉斯分類器來計算主題相關度。實驗結果表明，貝葉斯分類器的速度和精度均較為良好，特別適合于實現主題爬蟲。以主題爬蟲為基礎可以進一步地實現搜索引擎，從而使得在時間和帶寬受限的情況下獲取大量相關信息成為可能。

參考文獻:

[1]MURRAY B，MOORE A. Sizing the Internet[EB/OL]. (2007-07) [2008-12-07]. http://www.cyveillance.com/web/us/downloads/Sizing_the_Internet.pdf.

[2]ZHU Yang-bo， YE Shao-zhi， LI Xing et al. Distributed PageRank computation based on iterative aggregation-disaggregation methods [C]//Proc of the 14th ACM International Conference on Information and Knowledge Management. New York:ACM Press， 2005:578-585.

[3]MCCALLUM A K， NIGAM K， RENNIE J， et al. Automating the construction of Internet portals with machine learning[J].Information Retrieval Journal， 2000， 3(2):127-163.

[4]KUMAR R， RAGHAVAN P， RAJAGOPALAN P， et al. Stochastic models for the Web graph[C]//Proc of the 41st Annual Symposium on Foundations of Computer Science. Washington DC:IEEE Compu-ter Society， 2000:57.

[5]HEYDON A， NAJORK M. Mercator: a scalable， extensible Web crawler[J]. World Wide Web， 1999， 2(4):219-229.

[6]KOSTER M. A standard for robot exclusion[EB/OL]. (2008-04-01) [2008-12-07]. http://www.robotstxt.org/wc/norobots.html.

[7]林永民， 呂震宇，趙爽，等. 文本特征加權方法TF-IDF的分析與改進[J]. 計算機工程與設計，2008，29(11):2923-2925， 11.

[8]PENG F P， DALE SCHUUMANS D， WANG shao-jun et al. Augmenting Naive Bayes Classifiers with Statistical Language Models [J]. Information Retrieval， 2004， 7(3):317-345.

[9]JOHN G H， LANGLEY P. Estimating continuous distributions in bayesian classifiers[C]//Proc of the 11th Annual Conference on Uncertainty in Artificial Intelligence. San Francisco: Morgan Kaufmann Publishers， 1995:338-345.

[10]WANG Wen-jian， XU Zong-ben， LU Wei-zhen， et al. Determination of the spread parameter in the Gaussian kernel for classification and regression[J]. Neurocomputing， 2003， 55(1):643-663.