融合本體和改進(jìn)禁忌搜索策略的氣象災(zāi)害主題爬蟲方法

劉景發(fā) ，顧瑤平 ，劉文杰

（1. 南京信息工程大學(xué)計(jì)算機(jī)與軟件學(xué)院，南京210044； 2. 廣東外語外貿(mào)大學(xué)信息科學(xué)與技術(shù)學(xué)院，廣州510006）

0 引言

氣象災(zāi)害頻繁多發(fā)且對(duì)人類造成的損失不可估量，因此需要做好災(zāi)前預(yù)警和災(zāi)后應(yīng)急處理。相比其他氣象災(zāi)害，暴雨災(zāi)害和臺(tái)風(fēng)災(zāi)害發(fā)生頻率較高且造成影響較大?；ヂ?lián)網(wǎng)網(wǎng)頁中存在許多與氣象災(zāi)害相關(guān)的文本信息，這些信息復(fù)雜多樣且更新頻率快。為了在眾多網(wǎng)頁中高效、準(zhǔn)確地獲取互聯(lián)網(wǎng)上的暴雨災(zāi)害和臺(tái)風(fēng)災(zāi)害信息，許多學(xué)者開始關(guān)注研究網(wǎng)絡(luò)主題爬蟲［1-2］。

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

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

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

1 主題相關(guān)度計(jì)算

主題爬蟲首先要解決主題描述問題，然后構(gòu)建主題詞權(quán)重向量和網(wǎng)頁文本特征詞權(quán)重向量，并應(yīng)用向量空間模型（Vector Space Model，VSM）分別計(jì)算頁面主題相關(guān)度和錨文本主題相關(guān)度以及鏈接指向網(wǎng)頁的PR值，最后綜合分析等待隊(duì)列中鏈接的綜合優(yōu)先度來評(píng)價(jià)鏈接。

1.1 構(gòu)建主題詞權(quán)重向量和網(wǎng)頁文本特征詞權(quán)重向量

1.1.1 主題語義權(quán)重向量獲取

Gruber 在1993 年將本體（Ontology）引入計(jì)算機(jī)科學(xué)與信息科學(xué)領(lǐng)域，本體能夠?qū)崿F(xiàn)特定領(lǐng)域中某些概念及其相互之間關(guān)系的形式化表達(dá)，不僅可以解決傳統(tǒng)主題描述存在的未考慮語義的問題［4］，且相比目前常用的主題描述方法（根據(jù)領(lǐng)域?qū)＜医?jīng)驗(yàn)給出主題詞）［18］能更準(zhǔn)確地描述主題。本文在沒有結(jié)構(gòu)化主題詞表的情況下，在CNKI數(shù)據(jù)庫中分別以暴雨災(zāi)害和臺(tái)風(fēng)災(zāi)害為主題檢索核心論文，抽取最能反映文章內(nèi)容的標(biāo)題、關(guān)鍵詞和摘要作為領(lǐng)域術(shù)語候選集合，并利用ICTCLAS2016分詞系統(tǒng)進(jìn)行分詞處理，接著利用形式概念分析（Formal Concept Analysis，F(xiàn)CA）［19］和 本 體 Web 語 言（Ontology Web Language，OWL）形成本體結(jié)構(gòu)，最后使用Protégé 將本體進(jìn)行可視化。圖1為暴雨災(zāi)害本體關(guān)系圖，圖2為臺(tái)風(fēng)災(zāi)害本體關(guān)系圖，圖中均包含多個(gè)概念和多種語義關(guān)系。

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

其中：L 表示概念C1和C2之間最短路徑上的邊數(shù)；Ci表示路徑上第i個(gè)概念；V(Ci，F(xiàn)Ci)表示概念Ci與其祖先概念FCi之間的有向邊權(quán)重。

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

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

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

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

1.1.2 網(wǎng)頁文本特征詞權(quán)重向量獲取

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

其中：fi表示第i個(gè)主題詞在網(wǎng)頁文本中出現(xiàn)的詞頻；WP 表示已爬取到的總網(wǎng)頁數(shù)；WPi表示爬取網(wǎng)頁中包含的第i 個(gè)主題詞的網(wǎng)頁數(shù)；a ＞1。

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

其中：wfi，k表示第i 個(gè)主題詞在網(wǎng)頁文本的第k 組標(biāo)簽的詞頻；WFi，k表示第i個(gè)主題詞在第k組標(biāo)簽上的詞頻。

1.2 文本主題相關(guān)度計(jì)算

本文采用VSM 計(jì)算主題語義權(quán)重向量T與網(wǎng)頁P(yáng)的文本特征詞權(quán)重向量D的主題相關(guān)度值，如式（6）所示。

設(shè)網(wǎng)頁的文本主題相關(guān)度的閾值為φ，如果R（P）＞φ，則認(rèn)為網(wǎng)頁P(yáng)與主題相關(guān)。

1.3 網(wǎng)頁P(yáng)R值及鏈接綜合優(yōu)先度計(jì)算

PageRank 算法是反映未訪問鏈接價(jià)值的重要算法，本文為了克服傳統(tǒng)PageRank 算法存在的“主題漂移”現(xiàn)象，將錨文本主題相關(guān)度融入到PageRank 算法中，提出一種改進(jìn)的網(wǎng)頁P(yáng)的PR值計(jì)算公式：

其中：ω 為調(diào)節(jié)因子；d 為阻尼系數(shù)（本文設(shè)置為0.2）；Pi表示指向網(wǎng)頁P(yáng) 的第i 個(gè)入鏈網(wǎng)頁，PR(Pi)表示網(wǎng)頁P(yáng)i的PR 值，C(Pi)表示網(wǎng)頁 Pi出鏈的總數(shù)；R（Ai）表示 Pi對(duì)應(yīng)的鏈接錨文本Ai的主題相關(guān)度，由于錨文本與網(wǎng)頁文本不同，其沒有位置權(quán)重信息，因此本文中錨文本特征詞權(quán)重采用式（4）計(jì)算，錨文本的主題相關(guān)度采用式（6）計(jì)算。

綜合分析鏈接l 指向網(wǎng)頁P(yáng) 的PR(P)值、鏈接l 的網(wǎng)頁文本主題相關(guān)度以及鏈接的錨文本主題相關(guān)度，得到該鏈接的綜合優(yōu)先度p（l）：

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

其中：m 表示鏈接l 入鏈網(wǎng)頁的數(shù)量；Pl為鏈接l 指向的網(wǎng)頁文本特征詞權(quán)重向量；Al為鏈接l對(duì)應(yīng)的錨文本特征詞權(quán)重向量；μ1+ μ2+ μ3= 1。

對(duì)于每一個(gè)未訪問的鏈接，若其綜合優(yōu)先度大于預(yù)先設(shè)定的閾值η，則被認(rèn)為是合格鏈接，將其加入等待隊(duì)列；否則舍棄該鏈接。

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

2.1 禁忌搜索算法

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

2.2 鏈接的鄰域集和擴(kuò)展鄰域集

定義1 鄰域集。對(duì)于當(dāng)前鏈接Curl，稱Curl指向網(wǎng)頁上所有鏈接的集合為Curl的鄰域集，記為N（Curl）。

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

定義3 擴(kuò)展鄰域集。對(duì)于當(dāng)前鏈接Curl，若其所在網(wǎng)頁上的鏈接的綜合優(yōu)先度大于閾值η，則這樣的鏈接組成的集合為Curl的擴(kuò)展鄰域集，記為E（Curl）。

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

2.3 禁忌對(duì)象

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

2.4 藐視準(zhǔn)則與改進(jìn)的接受原則

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

1）若從當(dāng)前鏈接 Curl 的 C（Curl）中選擇的鏈接 Surl 是禁忌對(duì)象，且它的p 大于已訪問過的所有鏈接的最大綜合優(yōu)先度時(shí)，則解禁Surl，并將Surl設(shè)置成當(dāng)前鏈接。

2）若鏈接Surl是禁忌對(duì)象，且它的p小于已訪問過的所有鏈接的最大優(yōu)先度時(shí)，則從Curl的N（Curl）中重新隨機(jī)選擇一個(gè)鏈接作為當(dāng)前鏈接。

3）若鏈接Surl 不是禁忌對(duì)象，且Surl 綜合優(yōu)先度大于當(dāng)前鏈接的優(yōu)先度，將設(shè)置Surl為當(dāng)前鏈接Curl。

4）若鏈接Surl 不是禁忌對(duì)象，且Surl 綜合優(yōu)先度小于當(dāng)前鏈接的優(yōu)先度，則從Curl的N（Curl）中隨機(jī)選擇一個(gè)鏈接作為當(dāng)前鏈接。

2.5 主題爬蟲設(shè)計(jì)

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

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

2）在WaitQueue中隨機(jī)選取一個(gè)URL作為當(dāng)前鏈接Curl，令該鏈接訪問次數(shù)T = 1。

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

4）如果Surl是禁忌對(duì)象，則：

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

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

5）如果T ＞ 5，則將Curl加入到禁忌表中，并在E（Curl）中隨機(jī)挑選一個(gè)鏈接重新作為當(dāng)前鏈接Curl，轉(zhuǎn)3）；否則當(dāng)前鏈接Curl保持不變，轉(zhuǎn)3）。

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

7）計(jì)算鏈接Curl 指向頁面的主題相關(guān)度，如果該頁面主題相關(guān)度大于閾值φ，則將之保存到主題相關(guān)網(wǎng)頁集合PageSave中。

8）如果PageDown 中下載的網(wǎng)頁數(shù)量達(dá)到15 000，則算法結(jié)束；否則，轉(zhuǎn)2）。

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)環(huán)境：處理器為Intel Core i5-6500；開發(fā)工具為Eclipse4.6.1+JDK1.8.0；本體編輯工具為Protégé 5.2；分詞工具為ICTCLAS2016。采用Java語言編程實(shí)現(xiàn)爬蟲系統(tǒng)。

爬行主題：暴雨災(zāi)害和臺(tái)風(fēng)災(zāi)害。

實(shí)驗(yàn)數(shù)據(jù)：分別以暴雨災(zāi)害和臺(tái)風(fēng)災(zāi)害為主題詞在搜索引擎上搜索，各選取排列靠前的50 個(gè)鏈接構(gòu)成候選鏈接群，再由專家進(jìn)行篩選，得到能分別充分表現(xiàn)暴雨災(zāi)害主題和臺(tái)風(fēng)災(zāi)害主題特征的各30個(gè)鏈接作為爬蟲的初始種子鏈接群。

實(shí)驗(yàn)參數(shù)：在爬蟲算法中，參數(shù)的設(shè)置會(huì)直接影響實(shí)驗(yàn)結(jié)果。經(jīng)反復(fù)實(shí)驗(yàn)后，確定參數(shù)設(shè)置如下：φ = 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 算法評(píng)價(jià)指標(biāo)

評(píng)價(jià)爬蟲算法的指標(biāo)主要有爬全率（Recall）和爬準(zhǔn)率（Accuracy），計(jì)算公式如下：

其中：LG 表示已被下載的網(wǎng)頁中與主題相關(guān)的網(wǎng)頁數(shù)；TG 表示互聯(lián)網(wǎng)中與爬行主題相關(guān)的網(wǎng)頁總數(shù)；DG表示已爬取的網(wǎng)頁總數(shù)。由于互聯(lián)網(wǎng)中與某一主題相關(guān)的網(wǎng)頁總數(shù)難以統(tǒng)計(jì)，因此本文選擇爬準(zhǔn)率來評(píng)價(jià)算法。此外，本文還將使用下載網(wǎng)頁的平均相關(guān)度AR 和標(biāo)準(zhǔn)差SD 測(cè)試算法的性能，計(jì)算公式見式（11）、（12）。

其中R（Pi）為網(wǎng)頁P(yáng)i的主題相關(guān)度。

3.2 結(jié)果分析

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

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

圖4 （a）、（b）分別為暴雨災(zāi)害主題和臺(tái)風(fēng)災(zāi)害主題的五種不同主題爬蟲方法爬取相關(guān)網(wǎng)頁數(shù)量的對(duì)比。由圖4 可知，在爬取相同網(wǎng)頁數(shù)量時(shí)，On-ITS方法相較ITS方法、SA算法和OPS 算法能爬取更多與主題相關(guān)的網(wǎng)頁，而BFS 算法爬取的相關(guān)網(wǎng)頁數(shù)量是最少的。

圖4 BFS、OPS、SA、ITS與On-ITS主題爬蟲方法爬取相關(guān)網(wǎng)頁數(shù)量比較Fig.4 Comparison of related Web pages crawled by BFS，OPS，SA，ITS and On-ITS focused crawler methods

圖5 （a）、（b）分別為暴雨災(zāi)害主題和臺(tái)風(fēng)災(zāi)害主題的五種主題爬蟲方法爬取網(wǎng)頁的平均相關(guān)度對(duì)比。在整個(gè)爬蟲過程中，On-ITS方法爬取的網(wǎng)頁平均相關(guān)度都比較高且比較穩(wěn)定，均優(yōu)于對(duì)比算法，由此看出，On-ITS方法比其他四種算法抓取網(wǎng)頁的質(zhì)量更高。

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

圖6 （a）、（b）分別為暴雨災(zāi)害主題和臺(tái)風(fēng)災(zāi)害主題的五種主題爬蟲方法爬取網(wǎng)頁相關(guān)度的標(biāo)準(zhǔn)差比較。如圖6 所示，隨著爬取網(wǎng)頁數(shù)量的增加，On-ITS 方法的標(biāo)準(zhǔn)差在減小。當(dāng)網(wǎng)頁數(shù)達(dá)到15 000時(shí)，在暴雨災(zāi)害主題爬蟲中，On-ITS方法的標(biāo)準(zhǔn)差在 0.11 左右，而 BFS、OPS、SA、ITS 的標(biāo)準(zhǔn)差分別在0.24、0.23、0.19、0.16 左右；在臺(tái)風(fēng)災(zāi)害主題爬蟲中，On-ITS方法的標(biāo)準(zhǔn)差在0.13 左右，而 BFS、OPS、SA、ITS 的標(biāo)準(zhǔn)差分別在0.31、0.27、0.2、0.15左右，由此可見On-ITS方法的穩(wěn)定性也比較好。

圖6 BFS、OPS、SA、ITS與On-ITS主題爬蟲方法爬取網(wǎng)頁的相關(guān)度標(biāo)準(zhǔn)差比較Fig.6 Comparison of relevance standard deviation of Web pages crawled by BFS，OPS，SA，TS and On-ITS focused crawler methods

從圖3～6 不難看出，當(dāng)爬取網(wǎng)頁數(shù)量達(dá)到8 000 以后，各爬蟲方法的性能優(yōu)劣開始顯現(xiàn)。設(shè)定爬取網(wǎng)頁的目標(biāo)數(shù)量為15 000 是為了顯示各算法性能逐漸趨于穩(wěn)定的過程。事實(shí)上，隨著爬取網(wǎng)頁數(shù)量的增加，On-ITS相較其他幾個(gè)算法的優(yōu)勢(shì)愈加明顯。

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

4 結(jié)語

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