基于T－Graph算法的主題爬蟲研究

張 環(huán)，劉乃文，段會(huì)川

（山東師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 濟(jì)南250014）

0 引 言

針對通用網(wǎng)絡(luò)爬蟲查準(zhǔn)率低、信息冗余大等缺點(diǎn)，主題網(wǎng)絡(luò)爬蟲應(yīng)運(yùn)而生。主題爬行算法主要分為基于內(nèi)容分析的主題相關(guān)性算法和基于鏈接結(jié)構(gòu)的主題相關(guān)性算法兩大類。基于內(nèi)容分析的主題相關(guān)性算法有Best First Search、Fish Search以及Shark Search等算法，這類算法只注重文本內(nèi)容在主題搜索上的重要性，忽略了Web超鏈接結(jié)構(gòu)的作用，易出現(xiàn) “隧道”問題。基于鏈接結(jié)構(gòu)的主題相關(guān)性算法主要有PageRank算法和HITS算法，這類算法只考慮了鏈接的結(jié)構(gòu)特征，忽略了頁面內(nèi)容對爬行的影響，易出現(xiàn) “主題漂移”問題?；赥－Graph （treasure graph）算法的主題爬蟲策略［1］綜合考慮了頁面內(nèi)容與鏈接結(jié)構(gòu)對爬行的影響，通過分析候選鏈接的主題邊緣文本預(yù)測鏈接的相關(guān)性，這種方法比將網(wǎng)頁的全部內(nèi)容進(jìn)行預(yù)測要準(zhǔn)確，效率更高。

T－Graph算法采用TD－IDF方法提取特征項(xiàng)，該方法基于關(guān)鍵詞的出現(xiàn)頻率對文本中的詞匯進(jìn)行機(jī)械的匹配，沒有對詞語進(jìn)行語義分析就認(rèn)定詞語是文本的特征項(xiàng)；相似度計(jì)算時(shí)，沒有區(qū)分網(wǎng)頁中不同位置文本的重要程度?；谝陨纤伎?，針對傳統(tǒng)算法存在的不足進(jìn)行調(diào)整和改進(jìn)，并在此基礎(chǔ)上驗(yàn)證改進(jìn)后算法的效果。

1 T－Graph的構(gòu)建

收集特定主題的樣例節(jié)點(diǎn)，把樣例節(jié)點(diǎn)按層次進(jìn)行鏈接，目標(biāo)頁面所在的層為第零層，鏈接目標(biāo)頁面的層為第一層，以此類推，重復(fù)這個(gè)過程，直到相當(dāng)多的節(jié)點(diǎn)被建立。最高層的節(jié)點(diǎn)可以直接鏈接最底層的目標(biāo)頁面，同一層的節(jié)點(diǎn)之間不存在鏈接，任意層的節(jié)點(diǎn)至少有一個(gè)鏈接指向它的低層節(jié)點(diǎn)。T－Graph中存在特殊節(jié)點(diǎn)，對它進(jìn)行相似度計(jì)算，跟隨它的指向路徑并不能找到目標(biāo)頁面，這樣的節(jié)點(diǎn)稱為死節(jié)點(diǎn)，在構(gòu)建T－Graph時(shí)盡量避免死節(jié)點(diǎn)。T－Graph的工作性能用一個(gè)已知的文檔進(jìn)行測試，如果預(yù)期的標(biāo)準(zhǔn)沒有達(dá)到，這個(gè)模型需要被重復(fù)構(gòu)建。

T－Graph的節(jié)點(diǎn)有5種屬性：主標(biāo)題 （MH）、小節(jié)標(biāo)題 （SH）、子標(biāo)題 （ISH）、數(shù)據(jù)組件 （DC）、目標(biāo)信息組件（DIC）。DC中存放候選鏈接的主題邊緣文本信息。DIC中存放到達(dá)目標(biāo)頁面之前所需要下載網(wǎng)頁的數(shù)量信息。抓取一個(gè)網(wǎng)頁，提取網(wǎng)頁候選鏈接的MH、SH、ISH 以及DC這4種屬性與T－Graph節(jié)點(diǎn)的4種屬性進(jìn)行相似度的計(jì)算，如果找到匹配的節(jié)點(diǎn)，則按照相似度的大小將鏈接存入抓取隊(duì)列，網(wǎng)頁存入倉庫中；如果沒有找到匹配的節(jié)點(diǎn)，賦予鏈接較小的優(yōu)先級存入抓取隊(duì)。T－Graph的結(jié)構(gòu)如圖1所示。

圖1 T－Graph結(jié)構(gòu)

2 爬行階段

圖2是基于T－Graph 的爬蟲系統(tǒng)結(jié)構(gòu)?；赥－Graph的爬蟲抓取網(wǎng)頁的事件順序如下：

（1a）從抓取隊(duì)列中抓取優(yōu)先級高的鏈接，向Web網(wǎng)絡(luò)發(fā)送下載對應(yīng)網(wǎng)頁的請求。

（1b）爬蟲從Web獲取相應(yīng)的網(wǎng)頁。

（2）爬蟲將抓取的網(wǎng)頁存放在應(yīng)答隊(duì)列中。

（3）、（4）從應(yīng)答隊(duì)列中提取網(wǎng)頁中的鏈接與T－Graph中的節(jié)點(diǎn)進(jìn)行相似度計(jì)算。

（5）若網(wǎng)頁中的鏈接匹配T－Graph的節(jié)點(diǎn)，將此網(wǎng)頁下載到倉庫進(jìn)行存儲(chǔ)。

（6）提取網(wǎng)頁中的鏈接，按照優(yōu)先級的順序放到抓取隊(duì)列中。

（7）爬蟲從抓取隊(duì)列中選擇優(yōu)先級高的鏈接進(jìn)行優(yōu)先爬取。

圖2 基于T－Graph算法的爬蟲系統(tǒng)結(jié)構(gòu)

應(yīng)答隊(duì)列存放爬蟲抓取的網(wǎng)頁和HTTP 的響應(yīng)。如果由于網(wǎng)絡(luò)中斷或者鏈接過舊，抓取的網(wǎng)頁不能下載，系統(tǒng)仍然維持當(dāng)前的HTTP響應(yīng)的詳情，執(zhí)行相似度的計(jì)算。

如果T－Graph中沒有節(jié)點(diǎn)與網(wǎng)頁中的鏈接匹配，仍然將網(wǎng)頁中的鏈接存入抓取隊(duì)列中，但是賦予這條鏈接較低的優(yōu)先級。這種方法在一定程度上避免了過早丟棄與主題無關(guān)但與目的頁面相連接的前驅(qū)節(jié)點(diǎn)，提高了查全率。

3 中文圖書分類法提取候選鏈接的主題邊緣文本

3.1 中文圖書分類法

中文圖書分類法是賴永祥參照杜威十進(jìn)制圖書分類法改進(jìn)的。此圖書分類法更適用于中文書籍，特別是中國歷史和中國文學(xué)。中文圖書分類法主要分為十大類，覆蓋了世界上各個(gè)領(lǐng)域的知識：

000 總類

100 哲學(xué)類

200 宗教類

300 科學(xué)類

400 應(yīng)用科學(xué)類

500 社會(huì)科學(xué)類

600 中國史地類

700 世界史地類

800 語言文學(xué)類

900 藝術(shù)類

以上十大類中的每一類可以進(jìn)一步的細(xì)分，添加小數(shù)點(diǎn)使分類更加明確。中文圖書分類法是一種層次分類方法，每一個(gè)概念對應(yīng)于一個(gè)惟一的分類號碼 （如圖3所示），分類號碼決定2個(gè)詞組是否屬于同一個(gè)主題或者相關(guān)的主題。例如，關(guān)鍵詞1，關(guān)鍵詞2，關(guān)鍵詞3對應(yīng)的中文圖書分類號分別為917.1026，917.1029和383.512，可以直觀的判斷出關(guān)鍵詞1和關(guān)鍵詞2屬于同一個(gè)主題，關(guān)鍵詞3與前2個(gè)關(guān)鍵詞不屬于同一個(gè)主題。

圖3 口琴的分類號

3.2 主題邊緣文本的提取

建立二維坐標(biāo)，橫坐標(biāo)代表分類號碼的長度，縱坐標(biāo)代表分類號碼。本文運(yùn)用ICTCLAS3.0分詞系統(tǒng)將文本分成關(guān)鍵詞，由于每一個(gè)關(guān)鍵詞有一個(gè)或者多個(gè)概念，所以每一個(gè)關(guān)鍵詞都對應(yīng)一個(gè)或者多個(gè)中文圖書分類號碼，在二維坐標(biāo)中，對應(yīng)一個(gè)或者多個(gè)點(diǎn)。

圖4展示了運(yùn)用中文圖書分類法提取候選鏈接主題邊緣文本的示例圖。圖中紅色的點(diǎn)對應(yīng)于錨文本的關(guān)鍵詞，黑色的點(diǎn)對應(yīng)于其它文本的關(guān)鍵詞。點(diǎn)主要集中于圓圈內(nèi)，這種現(xiàn)象稱為星系。星系中的點(diǎn)對應(yīng)的關(guān)鍵詞稱為候選鏈接的主題邊緣文本。

圖4 主題邊緣文本的提取

4 基于詞義分析的相似度計(jì)算

針對傳統(tǒng)算法的不足，對傳統(tǒng)算法進(jìn)行了改進(jìn)，綜合考慮了不同位置文本的權(quán)重，采用語義分析的特征項(xiàng)提取算法對特征項(xiàng)進(jìn)行提取。

對ISH、SH、MH 和DC 進(jìn)行相似度計(jì)算，記為simISH、simSH、simMH和simDC，根據(jù)它們在網(wǎng)頁中所處的位置賦予不同的位置權(quán)重。候選鏈接CL的相似度為式 （1）

式 （2）是對文本關(guān)鍵詞的機(jī)械匹配，存在一定的語義偏差，影響相似度的準(zhǔn)確性，在此基礎(chǔ)上，利用維基百科的相關(guān)知識，引入了關(guān)鍵詞的語義計(jì)算和義原的概念，從關(guān)鍵詞的語義層次對候選鏈接進(jìn)行語義的相似度計(jì)算。在維基百科中，有2個(gè)重要的概念，即 “概念”和 “義原”?！案拍睢笔菍υ~匯語義的一種描述。義原是描述概念的最小意義單位。

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

5.1 評估指標(biāo)

主題網(wǎng)絡(luò)爬蟲常用的性能判斷指標(biāo)為：查準(zhǔn)率和查全率。查準(zhǔn)率公式為：Precision＝K／N，K 為抓取的與主題相關(guān)的頁面數(shù)量，N 為抓取到的全部頁面數(shù)。查全率又叫召回率，計(jì)算公式為：Recall＝K／R，R 為網(wǎng)絡(luò)中存在的所有與主題相關(guān)的頁面數(shù)。查全率需要知道網(wǎng)絡(luò)中存在的所有與主題相關(guān)的頁面數(shù)，而這一點(diǎn)很難辦到，所以主要從查準(zhǔn)率這一方面對實(shí)驗(yàn)效果進(jìn)行評估。

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

介紹了傳統(tǒng)的T－Graph算法以及改進(jìn)的T－Graph算法，基于理論基礎(chǔ)，分別對2種算法進(jìn)行實(shí)驗(yàn)驗(yàn)證。分詞工具采用ICTCLAS 3.0版本，語料庫采用維基百科語料庫。設(shè)定位置權(quán)重系數(shù)P1＝P2＝P3＝P4＝1／4，模型的層數(shù)為5層，以音樂為主題，URL＝http：／／zh.Wikipedia.org／wiki／Wikipedia：%E9%A6%96%E9%A1%B5 為種子鏈接進(jìn)行爬取，下載頁面總數(shù)為4000個(gè)，每隔500個(gè)頁面統(tǒng)計(jì)一次獲取與主題相關(guān)的頁面數(shù)量。傳統(tǒng)的T－Graph算法和改進(jìn)的T－Graph算法的爬蟲實(shí)驗(yàn)結(jié)果如圖5和圖6所示。

圖5 2種算法的查準(zhǔn)率實(shí)驗(yàn)對比

從圖5可知，在查準(zhǔn)率方面，改進(jìn)的T－Graph算法優(yōu)于傳統(tǒng)的T－Graph算法。傳統(tǒng)的T－Graph算法的查準(zhǔn)率在0.6上下浮動(dòng)，改進(jìn)的T－Graph算法的查準(zhǔn)率在0.7～0.8上下浮動(dòng)，改進(jìn)的T－Graph算法的查準(zhǔn)率始終高于傳統(tǒng)的T－Graph算法。在爬蟲抓取頁面的初期，2種算法查準(zhǔn)率的差距很小，隨著抓取網(wǎng)頁數(shù)量的增多，改進(jìn)的T－Graph算法的查準(zhǔn)率與傳統(tǒng)T－Graph算法的查準(zhǔn)率之間的差距逐漸拉開，改進(jìn)的T－Graph算法的優(yōu)勢越來越明顯。從圖6可知，在抓取相同數(shù)目網(wǎng)頁的情況下，改進(jìn)的T－Graph算法所獲得的與主題相關(guān)網(wǎng)頁要比傳統(tǒng)的T－Graph算法獲取的主題相關(guān)網(wǎng)頁多。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的T－Graph算法使爬蟲的性能得到了提升。

圖6 2種算法抓取與主題相關(guān)頁面的實(shí)驗(yàn)結(jié)果對比

6 結(jié)束語

基于T－Graph的主題爬蟲策略，通過分析候選鏈接的主題邊緣文本預(yù)測鏈接與主題的相關(guān)性，綜合考慮頁面內(nèi)容和鏈接分析，使主題爬行質(zhì)量得到了提高。然而傳統(tǒng)的T－Graph算法采用傳統(tǒng)的TD－IDF 算法進(jìn)行特征項(xiàng)的提取，沒有綜合考慮不同位置文本的權(quán)重問題。針對傳統(tǒng)算法的不足進(jìn)行了改進(jìn)，從語義層次對特征項(xiàng)進(jìn)行分析和提取，綜合考慮不同位置文本的權(quán)重。本文的研究工作有2個(gè)方面需要進(jìn)一步深入進(jìn)行：一是運(yùn)用中文圖書分類法獲取主題邊緣文本的過程需要手工進(jìn)行，比較繁瑣；二是需要找到一個(gè)更為有效的方法解決過早丟棄與主題無關(guān)、但與目標(biāo)頁面相連的前驅(qū)頁面的問題。

［1］Patel A.An adaptive updating topic specific Web search system using T－Graph ［J］.Journal of Computer Science，2010，6（4）：450－456.

［2］Sotiris Batsakis，Euripides GM Petrakis，Evangelos Milios.Improving the performance of focused Web crawlers［J］.Data＆Knowledge Engineering，2009，68 （10）：1001－1013.

［3］LIU Jinhong，LU Yuliang.Survey on topic－focused Web crawler［J］.Application Research of Computers，2007，24（10）：26－29 （in Chinese）.［劉金紅，陸余良.主題網(wǎng)絡(luò)爬蟲研究綜述 ［J］.計(jì)算機(jī)應(yīng)用研究，2007，24 （10）：26－29.］

［4］YE Yuxin，OUYANG Dantong.Semantic－based focused crawling ［J］.Journal of Software，2011，22 （9）：2075－2088 （in Chinese）. ［葉育鑫，歐陽丹彤.基于語義的主題爬行策略［J］.軟件學(xué)報(bào)，2011，22 （9）：2075－2088.］

［5］XIONG Zhongyang，SHI Yan，ZHANG Yufang.Wikipediabased focused crawling with page segmentation ［J］.Journal of Computer Application，2011，31 （12）：3624－3627 （in Chinese）.［熊忠陽，史艷，張玉芳.基于維基百科和網(wǎng)頁分塊的主題爬行策略 ［J］.計(jì)算機(jī)應(yīng)用，2011，31 （12）：3624－3627.］

［6］WANG Xiang，JIA Yan.Computing semantic relatedness using Chinese wikipedia links an taxonomy ［J］.Journal of Chinese Computer Systems，2011，32 （11）：2332－2342 （in Chinese）.［汪祥，賈焰.基于中文維基百科鏈接結(jié)構(gòu)與分類體系的語義相關(guān)度計(jì)算 ［J］.小微型計(jì)算機(jī)系統(tǒng)，2011，32 （11）：2332－2342.］

［7］Zheng Haitao，Kang Bo－yeong，Kim Hong－Gee.An ontologybased approach to learnable focused crawling ［J］.Information Sciences，2008，178 （23）：4512－4522.

［8］HUANG Li， WANG Chengliang，YANG Zheng.Focused crawling oriented intelligent tunneling algorithm research ［J］.Application Research of Computers，2009，26 （8）：2931－2933（in Chinese）.［黃莉，王成良，楊錚.面向主題網(wǎng)絡(luò)爬行的智能隧道穿越算法研究 ［J］.計(jì)算機(jī)應(yīng)用研究，2009，26 （8）：2931－2933.］

［9］Evgeniy Gabrilovich，Shaul Markovitch.Computer semantic relatedness using Wikipedia－based explicit semantic analysis［C］／／Proceeding of the 20th International Joint Conference on Artificial Intelligence，2007：1606－1611.

［10］Franziska Bussche，Klara Weiand.Not so creepy crawler：Easy crawler generation with standard XML queries ［C］／／Proceeding of the 19th International Conference on World Wide Web，2010：1305－1308.

［11］CHEN Xing.Research and implementation of focused crawler using Context Graphs ［J］.Computer Engineering and Design，2011，32 （3）：914－917 （in Chinese）. ［陳星.基于Context Graphs的主題爬蟲研究與實(shí)現(xiàn) ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2011，32 （3）：914－917.］