融合本體和改進禁忌搜索策略的氣象災害主題爬蟲方法

劉景發 ，顧瑤平 ，劉文杰

（1. 南京信息工程大學計算機與軟件學院，南京210044； 2. 廣東外語外貿大學信息科學與技術學院，廣州510006）

0 引言

氣象災害頻繁多發且對人類造成的損失不可估量，因此需要做好災前預警和災后應急處理。相比其他氣象災害，暴雨災害和臺風災害發生頻率較高且造成影響較大。互聯網網頁中存在許多與氣象災害相關的文本信息，這些信息復雜多樣且更新頻率快。為了在眾多網頁中高效、準確地獲取互聯網上的暴雨災害和臺風災害信息，許多學者開始關注研究網絡主題爬蟲［1-2］。

主題爬蟲研究的兩個關鍵問題為主題描述和爬蟲方法。Du 等［3］使用概念背景圖描述主題，但是背景圖的大多數構造方法依賴于早期訓練結果或用戶的歷史爬蟲信息，若用戶知識儲備不夠會影響背景圖的質量。費晨杰等［4］通過隱含狄利克雷分布（Latent Dirichlet Allocation，LDA）模型訓練主題文檔擴充主題詞。LDA能有效識別大規模文檔集或語料庫潛藏的主題信息，但是對于描述單個主題效果不好且工作量大。

主題爬蟲方法主要包括：1）傳統啟發式爬蟲方法。這類爬蟲方法一般遵循兩種搜索策略，即基于網頁內容的搜索策略和基于鏈接結構的分析策略。Shark-Search 算法［5］、基于Bayes算法［6］的概率模型和基于語義相似性的向量空間模型［7］都是基于網頁文本分析的評價方法。此類方法考慮了網頁的文本內容與主題的相關性，但缺乏評估鏈接結構對相關性的影響。目前PageRank 算法［8］、基于超鏈接分析的主題搜索（Hyperlink-Induced Topic Search，HITS）算法［9］是基于鏈接結構的評價方法。Yuan 等［10］在經典PageRank 算法基礎上提出了一種基于作弊相似性和相關性的改進PageRank 算法。Zhang等［11］通過對Hub值和Authority值的計算方法進行優化，提出了一種HITS 算法的改進版本I-HITS 算法。基于鏈接結構的分析策略側重于評價網頁中鏈接的權威性，容易出現“主題漂移”現象［12］。2）智能優化爬蟲方法。最常見的智能優化爬蟲方法有廣度優先搜索（Breadth First Search，BFS）算法［13］和最佳優先搜索（Optimal Priority Search，OPS）算法［14］。BFS算法將網頁中的超鏈接提取出來，利用先進先出隊列輔助搜索網頁，該方法雖然保證了網絡覆蓋率，但卻忽視了鏈接的優先權；OPS 算法優先抓取價值度高的鏈接，屬于一種貪心策略，容易陷入局部最優而錯過更多與主題相關的網頁。此外，遺傳算法［15］、蟻群算法［16］等一些全局搜索算法也被應用于爬蟲中。這類方法中的一些操作算子（如交叉、變異）應用不完全，只是重復選擇操作，并未產生新的鏈接，因此效果往往一般。最近，東熠等［17］將尋找一組Pareto 最優鏈接的方法融入蟻群算法，提出了一種基于多目標蟻群算法的主題爬蟲策略；但是由于蟻群算法固有的基于信息素的尋優方式，以及基于多目標的爬行方法難以保證鏈接分布的多樣性和均勻性，所以仍然容易陷入局部最優。

爬蟲作為一種常用的互聯網數據獲取工具，盡管近年來已經積累了大量可用的開源爬蟲框架系統，如Scrapy、Pyspider、WebCollector 等，但是普遍存在爬準率不高的缺陷。為克服傳統主題爬蟲方法中主題描述的不足和開源爬蟲系統爬準率不高的缺陷，本文采用領域本體描述暴雨災害和臺風災害主題，并提出一種基于頁面主題相關度、錨文本主題相關度以及鏈接指向網頁PR（PageRank）值的鏈接綜合優先度的評估方法；針對目前智能爬蟲方法容易迂回搜索、陷入局部最優的缺陷，本文將禁忌搜索策略引入主題爬蟲，并對其關鍵搜索機制（禁忌對象和接受原則）進行改進，通過將改進的禁忌搜索策略（Improved Tabu Search，ITS）與本體（Ontology）技術相結合，提出了一種融合本體和改進禁忌搜索策略的主題爬蟲方法On-ITS。On-ITS 爬蟲方法利用ITS 能盡量避免爬蟲迂回搜索，從而盡可能拓寬有效搜索途徑，是一種較理想的具有全局搜索能力的智能爬蟲方法。實驗結果表明，本文的On-ITS網絡主題爬蟲方法能爬取更多與主題相關的網頁。

1 主題相關度計算

主題爬蟲首先要解決主題描述問題，然后構建主題詞權重向量和網頁文本特征詞權重向量，并應用向量空間模型（Vector Space Model，VSM）分別計算頁面主題相關度和錨文本主題相關度以及鏈接指向網頁的PR值，最后綜合分析等待隊列中鏈接的綜合優先度來評價鏈接。

1.1 構建主題詞權重向量和網頁文本特征詞權重向量

1.1.1 主題語義權重向量獲取

Gruber 在1993 年將本體（Ontology）引入計算機科學與信息科學領域，本體能夠實現特定領域中某些概念及其相互之間關系的形式化表達，不僅可以解決傳統主題描述存在的未考慮語義的問題［4］，且相比目前常用的主題描述方法（根據領域專家經驗給出主題詞）［18］能更準確地描述主題。本文在沒有結構化主題詞表的情況下，在CNKI數據庫中分別以暴雨災害和臺風災害為主題檢索核心論文，抽取最能反映文章內容的標題、關鍵詞和摘要作為領域術語候選集合，并利用ICTCLAS2016分詞系統進行分詞處理，接著利用形式概念分析（Formal Concept Analysis，FCA）［19］和 本 體 Web 語 言（Ontology Web Language，OWL）形成本體結構，最后使用Protégé 將本體進行可視化。圖1為暴雨災害本體關系圖，圖2為臺風災害本體關系圖，圖中均包含多個概念和多種語義關系。

根據本體的結構特征，綜合語義距離IFDis、概念密度IFDen、概念深度IFDep、概念重合度IFCoi和概念語義關系IFRel五項影響因子來衡量概念間的語義相似度值［20-21］。IFDis、IFDen、IFDep以及IFCoi的計算方法參見文獻［21］，與文獻［21］中定義的概念語義關系不同的是，本文除了考慮到同義（Synonym）關系和繼承（Is-a）關系外，還考慮引發（Includes）關系。計算概念C1和C2語義關系影響因子IFRel的公式如下：

其中：L 表示概念C1和C2之間最短路徑上的邊數；Ci表示路徑上第i個概念；V(Ci，FCi)表示概念Ci與其祖先概念FCi之間的有向邊權重。

綜合考慮以上所有影響因子，定義概念C1和C2的語義相似度值為：

其中：α、β、γ、δ、ε的總和為1。

假設主題關鍵詞集合為t =(t1，t2，…，tn)，n 表示描述主題的主題詞數量。根據式（3），主題語義權重向量為：

其中，wti(i = 1，2，…，n)表示主題關鍵詞集合中第i 個主題詞的權重，即對應的主題關鍵詞概念ti與主題概念C之間的語義相似度值Sim(C，ti)。

1.1.2 網頁文本特征詞權重向量獲取

傳統的網頁文本特征詞權重向量獲取方法通常只考慮詞頻，很多學者采用的方法為詞頻-逆文檔頻率（Term Frequency-Inverse Document Frequency，TF-IDF）［22］計算模型。若某個概念（特征詞）在文檔中的權重大小wdi使用式（4）計算，那么網頁P的特征詞權重向量為

其中：fi表示第i個主題詞在網頁文本中出現的詞頻；WP 表示已爬取到的總網頁數；WPi表示爬取網頁中包含的第i 個主題詞的網頁數；a ＞1。

網頁是一個包含HTML 標簽的文本，網頁的所有內容均寫在標簽內部，主題詞出現在不同標簽中的權重是不一樣的。因此，本文采用文獻［18］中的方法設置標簽位置權重系數，將HTML標簽分為5組，并給予主題詞在不同標簽組中的權重系數為Wk(k = 1，2，…，K，K = 5)。概念di在網頁文本中的權重大小wdi可以使用式（5）表示。

其中：wfi，k表示第i 個主題詞在網頁文本的第k 組標簽的詞頻；WFi，k表示第i個主題詞在第k組標簽上的詞頻。

1.2 文本主題相關度計算

本文采用VSM 計算主題語義權重向量T與網頁P的文本特征詞權重向量D的主題相關度值，如式（6）所示。

設網頁的文本主題相關度的閾值為φ，如果R（P）＞φ，則認為網頁P與主題相關。

1.3 網頁PR值及鏈接綜合優先度計算

PageRank 算法是反映未訪問鏈接價值的重要算法，本文為了克服傳統PageRank 算法存在的“主題漂移”現象，將錨文本主題相關度融入到PageRank 算法中，提出一種改進的網頁P的PR值計算公式：

其中：ω 為調節因子；d 為阻尼系數（本文設置為0.2）；Pi表示指向網頁P 的第i 個入鏈網頁，PR(Pi)表示網頁Pi的PR 值，C(Pi)表示網頁 Pi出鏈的總數；R（Ai）表示 Pi對應的鏈接錨文本Ai的主題相關度，由于錨文本與網頁文本不同，其沒有位置權重信息，因此本文中錨文本特征詞權重采用式（4）計算，錨文本的主題相關度采用式（6）計算。

綜合分析鏈接l 指向網頁P 的PR(P)值、鏈接l 的網頁文本主題相關度以及鏈接的錨文本主題相關度，得到該鏈接的綜合優先度p（l）：

p(l)= μ1× PR(P)+

其中：m 表示鏈接l 入鏈網頁的數量；Pl為鏈接l 指向的網頁文本特征詞權重向量；Al為鏈接l對應的錨文本特征詞權重向量；μ1+ μ2+ μ3= 1。

對于每一個未訪問的鏈接，若其綜合優先度大于預先設定的閾值η，則被認為是合格鏈接，將其加入等待隊列；否則舍棄該鏈接。

2 基于On-ITS策略的主題爬蟲方法

2.1 禁忌搜索算法

TS 算法［23］是一種超啟發式算法，由美國科羅拉多大學教授Fred Glover 在1986 年提出。TS 算法是一種局部鄰域搜索算法，其基本流程是：給定一個初始解X，從X 的鄰域中確定若干候選解N，若最優候選解N 優于X，則忽略N 的禁忌屬性，將N 替換成為新的當前解和當前最優解，且將其對應的對象放入禁忌表中，更新禁忌表中各對象的任期；否則在N中選出未加入禁忌表的最優解作為新的當前解X，將其對象加入禁忌表中并更新禁忌表；如此進行上述過程的迭代搜索，直到滿足算法終止條件。

2.2 鏈接的鄰域集和擴展鄰域集

定義1 鄰域集。對于當前鏈接Curl，稱Curl指向網頁上所有鏈接的集合為Curl的鄰域集，記為N（Curl）。

定義2 候選鄰域集。對于當前鏈接Curl，若其指向網頁上的鏈接的綜合優先度大于設定的閾值η，則這樣的鏈接組成的集合為Curl 的候選鄰域集，記為C（Curl）。顯然，C(Curl) ? N(Curl)。

定義3 擴展鄰域集。對于當前鏈接Curl，若其所在網頁上的鏈接的綜合優先度大于閾值η，則這樣的鏈接組成的集合為Curl的擴展鄰域集，記為E（Curl）。

在整個爬蟲過程中，常規的鄰域搜索通常只考慮鏈接所指向網頁上的鏈接。但是，為了利用On-ITS 方法擴大爬蟲的搜索范圍，在訪問當前鏈接Curl 的候選鄰域集的迭代次數達到設定的次數后，則從Curl 的擴展鄰域集中重新選擇一個鏈接作為新的當前鏈接。

2.3 禁忌對象

當采用N（Curl）更新爬取隊列時，為了避免算法迂回搜索，防止在N（Curl）中反復挑選而找不到合適的鏈接，則將Curl 放入禁忌表中，暫時禁止操作，設置為禁忌對象。然而，通常的禁忌搜索算法設置禁忌對象是從鄰域集中選擇綜合優先度最高的鏈接，若其優先度高于“best so far”鏈接的優先度，則無視該鏈接的禁忌屬性，將該鏈接作為禁忌對象存放至禁忌表中；否則從鄰域集中選擇非禁忌的具有最高綜合優先度的鏈接作為新的當前鏈接，并將該鏈接放入禁忌表中。與該策略不同，本文忽略鏈接Curl 原來是否是禁忌對象，只要從Curl 的候選鄰域集中隨機選擇出不同的5 個（或所有）鏈接的綜合優先度都沒有Curl 的優先度高，則將Curl 設置為禁忌對象，并從Curl 的擴展鄰域集中隨機挑選一個非禁忌的鏈接作為新的當前鏈接。顯然，當再次從擴展鄰域集中選擇鏈接時，就不會再選擇Curl，從而能有效地搜索不同的路徑，給當前局部搜索更多的尋優機會。本文中，禁忌長度設置為5。

2.4 藐視準則與改進的接受原則

藐視準則是指在某禁忌鏈接的綜合優先度大于已訪問所有鏈接的最大綜合優先度時，則無視其禁忌屬性，接受該鏈接為當前鏈接。在通常的禁忌搜索方法中，當不存在某禁忌鏈接的綜合優先度優于已訪問過的所有鏈接的最大綜合優先度時，就從當前鏈接Curl的N（Curl）中選擇非禁忌的綜合優先度p 最高的鏈接為當前鏈接。這種策略沒有給接近最高優先度的鏈接足夠機會從它出發爬取它的子鏈接，容易陷入局部最優。本文在留藐視準則的情況下，對這種Curl 的接受原則作了如下改進：

1）若從當前鏈接 Curl 的 C（Curl）中選擇的鏈接 Surl 是禁忌對象，且它的p 大于已訪問過的所有鏈接的最大綜合優先度時，則解禁Surl，并將Surl設置成當前鏈接。

2）若鏈接Surl是禁忌對象，且它的p小于已訪問過的所有鏈接的最大優先度時，則從Curl的N（Curl）中重新隨機選擇一個鏈接作為當前鏈接。

3）若鏈接Surl 不是禁忌對象，且Surl 綜合優先度大于當前鏈接的優先度，將設置Surl為當前鏈接Curl。

4）若鏈接Surl 不是禁忌對象，且Surl 綜合優先度小于當前鏈接的優先度，則從Curl的N（Curl）中隨機選擇一個鏈接作為當前鏈接。

2.5 主題爬蟲設計

融合本體和改進禁忌搜索策略（On-ITS）的主題爬蟲具體步驟如下：

1）選擇30 個初始種子鏈接作為種子鏈接群，將之放入等待隊列WaitQueue中，令Hurl為種子鏈接群中綜合優先度最高的鏈接，初始化閾值φ，設置禁忌表為空。

2）在WaitQueue中隨機選取一個URL作為當前鏈接Curl，令該鏈接訪問次數T = 1。

3）從Curl 的候選鄰域集C（Curl）中隨機挑選一個鏈接Surl，令 C(Curl) = C(Curl) -{Surl}。

4）如果Surl是禁忌對象，則：

如果p(Surl) ＞p(Hurl)，則從禁忌表中釋放Surl，令Hurl =Surl，Curl = Surl，同時將禁忌表中各禁忌對象的任期減1，釋放任期為0的對象，轉6）；否則令T = T + 1，轉5）。

否則，如果 p(Surl) ＞ p(Curl)，則令 Curl = Surl，同時將禁忌表中各禁忌對象的任期減1，釋放任期為0 的對象，此時若p(Surl) ＞p(Hurl)，則 令 Hurl = Surl，轉 6） ；否 則 ，令T = T + 1，轉5）。

5）如果T ＞ 5，則將Curl加入到禁忌表中，并在E（Curl）中隨機挑選一個鏈接重新作為當前鏈接Curl，轉3）；否則當前鏈接Curl保持不變，轉3）。

6）將Curl 指向網頁保存到下載頁面集合PageDown 中，Curl放入 WaitQueue。

7）計算鏈接Curl 指向頁面的主題相關度，如果該頁面主題相關度大于閾值φ，則將之保存到主題相關網頁集合PageSave中。

8）如果PageDown 中下載的網頁數量達到15 000，則算法結束；否則，轉2）。

3 實驗結果與分析

實驗環境：處理器為Intel Core i5-6500；開發工具為Eclipse4.6.1+JDK1.8.0；本體編輯工具為Protégé 5.2；分詞工具為ICTCLAS2016。采用Java語言編程實現爬蟲系統。

爬行主題：暴雨災害和臺風災害。

實驗數據：分別以暴雨災害和臺風災害為主題詞在搜索引擎上搜索，各選取排列靠前的50 個鏈接構成候選鏈接群，再由專家進行篩選，得到能分別充分表現暴雨災害主題和臺風災害主題特征的各30個鏈接作為爬蟲的初始種子鏈接群。

實驗參數：在爬蟲算法中，參數的設置會直接影響實驗結果。經反復實驗后，確定參數設置如下：φ = 0.62，τ = 34，α =0.8，β = 0.04，γ = 0.06，δ = 0.03，ε = 0.07，η = 0.15，ω = 0.6，μ1= 0.55，μ2= 0.25，μ3= 0.20。

3.1 算法評價指標

評價爬蟲算法的指標主要有爬全率（Recall）和爬準率（Accuracy），計算公式如下：

其中：LG 表示已被下載的網頁中與主題相關的網頁數；TG 表示互聯網中與爬行主題相關的網頁總數；DG表示已爬取的網頁總數。由于互聯網中與某一主題相關的網頁總數難以統計，因此本文選擇爬準率來評價算法。此外，本文還將使用下載網頁的平均相關度AR 和標準差SD 測試算法的性能，計算公式見式（11）、（12）。

其中R（Pi）為網頁Pi的主題相關度。

3.2 結果分析

本文采用相同的種子鏈接群與評價標準，分別對比測試了本文提出的基于On-ITS 策略的主題爬蟲方法、未加本體的ITS 方法與寬度優先搜索（Breadth First Search，BFS）算法［13］、最佳優先搜索（Optimal Priority Search，OPS）算法［14］和模擬退火（Simulated Annealing，SA）算法［18］。圖 3（a）、（b）分別為暴雨災害主題和臺風災害主題在五種不同爬蟲方法下的爬準率。從圖3可以看出，當爬取的網頁數量大于7 000時，On-ITS的爬準率明顯高于其他算法。當爬取的網頁數量達到15 000時，在暴雨災害主題爬蟲中，BFS 算法的爬準率在20%左右，OPS算法在60%左右，SA 算法在70%左右，ITS方法在74%左右，On-ITS 方法的爬準率穩定在78%左右；在臺風災害主題爬蟲中，BFS 算法的爬準率在30%左右，OPS 算法在70%左右，SA 算法在75%左右，ITS 方法在78%左右，而On-ITS 方法的爬準率穩定在82%左右。

圖3 BFS、OPS、SA、ITS與On-ITS主題爬蟲方法爬準率比較Fig.3 Accuracy comparison of BFS，OPS，SA，ITS and On-ITS focused crawler methods

圖4 （a）、（b）分別為暴雨災害主題和臺風災害主題的五種不同主題爬蟲方法爬取相關網頁數量的對比。由圖4 可知，在爬取相同網頁數量時，On-ITS方法相較ITS方法、SA算法和OPS 算法能爬取更多與主題相關的網頁，而BFS 算法爬取的相關網頁數量是最少的。

圖4 BFS、OPS、SA、ITS與On-ITS主題爬蟲方法爬取相關網頁數量比較Fig.4 Comparison of related Web pages crawled by BFS，OPS，SA，ITS and On-ITS focused crawler methods

圖5 （a）、（b）分別為暴雨災害主題和臺風災害主題的五種主題爬蟲方法爬取網頁的平均相關度對比。在整個爬蟲過程中，On-ITS方法爬取的網頁平均相關度都比較高且比較穩定，均優于對比算法，由此看出，On-ITS方法比其他四種算法抓取網頁的質量更高。

圖5 BFS、OPS、SA、ITS與On-ITS主題爬蟲方法爬取網頁的平均相關度比較Fig.5 Comparison of average relevance of Web pages crawled by BFS，OPS，SA，ITS and On-ITS focused crawler methods

圖6 （a）、（b）分別為暴雨災害主題和臺風災害主題的五種主題爬蟲方法爬取網頁相關度的標準差比較。如圖6 所示，隨著爬取網頁數量的增加，On-ITS 方法的標準差在減小。當網頁數達到15 000時，在暴雨災害主題爬蟲中，On-ITS方法的標準差在 0.11 左右，而 BFS、OPS、SA、ITS 的標準差分別在0.24、0.23、0.19、0.16 左右；在臺風災害主題爬蟲中，On-ITS方法的標準差在0.13 左右，而 BFS、OPS、SA、ITS 的標準差分別在0.31、0.27、0.2、0.15左右，由此可見On-ITS方法的穩定性也比較好。

圖6 BFS、OPS、SA、ITS與On-ITS主題爬蟲方法爬取網頁的相關度標準差比較Fig.6 Comparison of relevance standard deviation of Web pages crawled by BFS，OPS，SA，TS and On-ITS focused crawler methods

從圖3～6 不難看出，當爬取網頁數量達到8 000 以后，各爬蟲方法的性能優劣開始顯現。設定爬取網頁的目標數量為15 000 是為了顯示各算法性能逐漸趨于穩定的過程。事實上，隨著爬取網頁數量的增加，On-ITS相較其他幾個算法的優勢愈加明顯。

實驗結果表明，由于BFS 算法沒有對網頁的主題相關度進行預判，所以整個爬蟲過程中BFS 算法的爬準率偏低。OPS 算法每次都下載相關度最高的網頁，因此在前期的爬蟲過程中其爬準率比較高，但隨著爬取網頁數量的增加，OPS算法的貪心策略導致其在后期陷入了局部最優。SA 算法采用一定的概率來選擇與主題不相關的網頁，具有全局搜索的優點；但該算法通過人工手動給出關鍵詞的主題描述方式，對主題描述不夠準確，且也有可能重復訪問已搜索過的鏈接，因此會影響它的結果。本文的On-ITS 方法采用本體描述主題，構建的暴雨災害本體（圖1）和臺風災害本體（圖2）分別包含46個和41 個主題詞（屬于小規模本體），對主題的描述相對準確；而且統計顯示，采用本體計算鏈接文本主題相關度平均耗時5 320 169 ns，因此對算法的效率影響并不大。通過與未采用本體描述主題的ITS 算法的對比結果表明，構建本體不僅對爬蟲系統的進程影響不大，而且能有效提高爬蟲爬取網頁的相關度。On-ITS 方法不僅能爬取更多與主題相關的網頁，具有較高的爬準率，爬蟲性能也比較穩定。

4 結語

本文分別以暴雨災害和臺風災害為主題，提出了一種融合本體和改進禁忌搜索策略的主題爬蟲方法On-ITS。本文利用本體語義相似度計算主題語義向量，基于HTML 網頁文本特征位置加權方法計算網頁文本特征向量，并結合鏈接的錨文本相關度和網頁的PR 值計算鏈接的綜合優先度。利用On-ITS方法進行全局搜索，能防止爬蟲陷入局部最優，盡可能避免爬取已訪問過的鏈接，從而提高爬蟲系統的性能。最后對比了 BFS 算法、OPS 算法、SA 算法與本文提出的 ITS 方法和On-ITS 方法，結果表明On-ITS 方法有較高的爬準率和較好的穩定性。在下一階段中，將在主題描述方法和主題爬蟲效率方面作進一步的研究。