南京航空航天大學(xué) 周 萍

?

基于T-Graph算法的鏈接和內(nèi)容相結(jié)合的聚焦爬蟲模型

南京航空航天大學(xué) 周 萍

【摘要】聚焦網(wǎng)絡(luò)爬蟲的兩大重要目標(biāo)就是尋找主題相關(guān)的網(wǎng)頁，并優(yōu)先下載主題相關(guān)度高的網(wǎng)頁。首先，讀取并分析網(wǎng)頁的有效HTML元素，并根據(jù)高準(zhǔn)確率來預(yù)測和抽取每個(gè)未被訪問的網(wǎng)頁的主題內(nèi)容。然后，根據(jù)T-Graph來計(jì)算URLs的主題相關(guān)度，并按照相關(guān)度大小進(jìn)行排序。本文提出的基于T-Graph的算法綜合了多方面的元素，通過實(shí)驗(yàn)得到了較高的查準(zhǔn)率和查全率，因此，該算法具有重要的意義。

【關(guān)鍵詞】聚焦網(wǎng)絡(luò)爬蟲；T-Graph；HTML元素；信息檢索；搜索引擎

0 引言

網(wǎng)絡(luò)爬蟲的主要任務(wù)是從Web上獲取網(wǎng)頁文檔，并為這些數(shù)據(jù)創(chuàng)建索引，索引的更新是通過分布式爬行實(shí)現(xiàn)的。傳統(tǒng)的網(wǎng)絡(luò)爬蟲并不能輕松地?cái)U(kuò)展爬行，因?yàn)閃eb是不受人為控制的。而且，傳統(tǒng)的爬蟲也不能根據(jù)特定的主題目標(biāo)建立正確的索引，索引庫因此也得不到及時(shí)的更新。為了解決這些弊端，具有重要意義的聚焦爬蟲應(yīng)運(yùn)而生[1]。

1 基于T-Graph算法的聚焦爬蟲模型的設(shè)計(jì)

聚焦爬蟲模型的設(shè)計(jì)主要涉及兩個(gè)問題，第一個(gè)問題就是在下載網(wǎng)頁內(nèi)容之前預(yù)估未被爬行的網(wǎng)頁的主題目標(biāo)。本文通過把父網(wǎng)頁的HTML標(biāo)簽元素和錨文本想結(jié)合，來預(yù)測未被訪問的鏈接的主題相關(guān)性。第二個(gè)問題就是將鏈接庫的URLs按照主題相關(guān)度進(jìn)行排序。本文通過T-Graph（Treasure Graph）來評(píng)估URLs的主題優(yōu)先級(jí)，并假定T-Graph的結(jié)構(gòu)是自頂向下的。

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

通過數(shù)據(jù)挖掘來獲取主題關(guān)鍵詞的方法很多，本文采用了一種既簡單又有效的方法，該方法需要綜合考慮三個(gè)因素。第一，單詞的數(shù)量決定了主題的重要程度。第二，D-number （Dewey system，杜威十進(jìn)分類法）的長度決定了主題的精確性。第三，錨文本中的關(guān)鍵詞有更高的主題相關(guān)性。以上三種因素的影響力比普通文本高40%[2]。

分塊計(jì)算主題權(quán)重的方法相對(duì)于同時(shí)計(jì)算結(jié)點(diǎn)的個(gè)數(shù)、D-number的長度以及錨文本的主題關(guān)鍵詞的方法來說，具有重要的意義。而且，相對(duì)于異常值檢測法來說，該方法能夠降低整個(gè)系統(tǒng)的計(jì)算負(fù)擔(dān)，因?yàn)橛?jì)算過程只是通過簡單的字符串過濾來實(shí)現(xiàn)的[3]。

如果未被訪問的鏈接具有主題相關(guān)性，那么該鏈接可以利用T-Graph來計(jì)算主題相關(guān)性。否則，該鏈接就被賦予較低的優(yōu)先級(jí)。只有這樣，主題爬蟲才能盡可能多地訪問主題相關(guān)的網(wǎng)頁。

1.2 基于T-Graph算法的聚焦爬蟲的框架結(jié)構(gòu)

如圖1.1所示，本文提出的Treasure-Crawler系統(tǒng)中，T-Graph的每個(gè)節(jié)點(diǎn)分別對(duì)應(yīng)著五大模塊。其中，Web網(wǎng)頁的HTML屬性所包含的五大模塊如下所示：

（1）簡短小節(jié)標(biāo)題（immediate sub-section heading，ISH）。

（2）包含ISH的小節(jié)標(biāo)題（section heading，SH）。

（3）主標(biāo)題（main heading，MH）。

（4）鏈接附近的文本數(shù)據(jù)模塊（data component，DC）。

（5）主題信息模塊（destination information component，DIC）。

圖1.1 T-Graph的分層結(jié)構(gòu)

1.3 鏈接URLs優(yōu)先級(jí)的計(jì)算

爬蟲抓取到網(wǎng)頁之后，需要對(duì)網(wǎng)頁的優(yōu)先級(jí)進(jìn)行計(jì)算。評(píng)估網(wǎng)頁優(yōu)先級(jí)的方法是，根據(jù)相似性算法把網(wǎng)頁的HTML元素和所有的T-Graph結(jié)點(diǎn)作比較。其中，通過使用HTML語法解析器來準(zhǔn)確地獲取網(wǎng)頁的HTML元素。

如果節(jié)點(diǎn)的OSM值在臨界值（設(shè)為0.05）之上，那么URL的優(yōu)先級(jí)如下所示：

如果節(jié)點(diǎn)的OSM值在臨界值（設(shè)為0.05）之下，那么URL的優(yōu)先級(jí)如下所示：

2 系統(tǒng)測試和驗(yàn)證

為了驗(yàn)證系統(tǒng)結(jié)構(gòu)的實(shí)用性，根據(jù)初始網(wǎng)頁建立了T-Graph，并向數(shù)據(jù)庫中輸入了相關(guān)數(shù)據(jù)。經(jīng)過測試和驗(yàn)證，本文提出的Treasure-Crawler系統(tǒng)滿足了基本需求，并且具有功能性和實(shí)用性。圖2.1展示了T-Graph和Context-Graph在召回率方面的對(duì)比結(jié)果。其中T-Graph（T）表示主題T-Graph，T-Graph（G）表示通用T-Graph。觀察曲線圖可發(fā)現(xiàn)，T-Graph（T）具有較高的召回率。

圖2.1 網(wǎng)頁的召回率（0.5）的增長趨勢(shì)

3 結(jié)論

本文提出的Treasure-Crawler系統(tǒng)架構(gòu)滿足了聚焦網(wǎng)絡(luò)爬蟲的需求，并能夠保持系統(tǒng)結(jié)構(gòu)和模型的穩(wěn)定性。其中，未被訪問的URLs的優(yōu)先級(jí)是通過T-Graph的分層結(jié)構(gòu)計(jì)算出來的，然后爬蟲根據(jù)URLs的優(yōu)先級(jí)來確定下一個(gè)待訪問的URL。

參考文獻(xiàn)

[1]季春,姜琴,吳錚悅.垂直搜索引擎關(guān)鍵技術(shù)研究綜述[J].情報(bào)探索,2013(10):91-93.

[2]Jamali M,Sayyadi H,Hariri B B,et al.A Method for Focused Crawling Using Combination of Link Structure and Content Similarity[C]//2006 IEEE/WIC/ACM International Conference on Web Intelligence(WI 2006),18-22 December 2006,Hong Kong, China.2006:753-756.

[3]Wang W,Chen X,Zou Y,et al.A Focused Crawler Based on Naive Bayes Classifier[C]//Proceedings of the 2010 Third International Symposium on Intelligent Information Technology and Security Informatics.IEEE Computer Society,2010:517-521.

[4]Patel A.An Adaptive Updating Topic Specific Web Search System Using T-Graph[J].Journal of Computer Science,2010,79(4):1-4.

[5]Diligenti M,Coetzee F,Lawrence S,et al.Focused Crawling Using Context Graphs[C]//Proceedings of the 26th International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc.,2000:527-534.

[6]Passerini A,Frasconi P,Soda G Evaluation Methods for Focused Crawling[C]//Proceedings of the 7th Congress of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence. Springer-Verlag,2001:33-39.