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

南京航空航天大學 周 萍

?

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

南京航空航天大學 周 萍

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

（3）主標題（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)先級的計算

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

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

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

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

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

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

3 結(jié)論

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

參考文獻

[1]季春,姜琴,吳錚悅.垂直搜索引擎關(guān)鍵技術(shù)研究綜述[J].情報探索,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.