徐昊 沈江明
摘 要:聚焦爬蟲(Focused Crawler)又稱為主題爬蟲,是從網(wǎng)絡(luò)上獲取特定主題數(shù)據(jù)的有效工具。為了避免傳統(tǒng)聚焦爬蟲預(yù)訓(xùn)練主題相關(guān)性分類器的繁復(fù)工作,提出一種自舉聚焦爬蟲(Bootstrapping Focused Crawler),用于從特定網(wǎng)站群中收集主題數(shù)據(jù)。自舉聚焦爬蟲省略了預(yù)先訓(xùn)練分類器的步驟,轉(zhuǎn)而采用一些樣本頁(yè)面以相似度排序的方式替代分類器功能。在實(shí)驗(yàn)中,自舉聚焦爬蟲以犧牲一定準(zhǔn)確率為代價(jià),取得了0.62的召回率以及0.45的F1值,表現(xiàn)優(yōu)于傳統(tǒng)聚焦爬蟲(召回率0.16、F1值0.25)。對(duì)于網(wǎng)站群主題數(shù)據(jù)采集任務(wù),采用相似度排序替代主題分類器,不僅可以減輕分類器訓(xùn)練負(fù)擔(dān),還可以達(dá)到更好的效果。
關(guān)鍵詞:爬蟲技術(shù);信息檢索;自舉聚焦爬蟲
DOI:10. 11907/rjdk. 201564 開放科學(xué)(資源服務(wù))標(biāo)識(shí)碼(OSID):
中圖分類號(hào):TP393文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1672-7800(2020)008-0109-04
Abstract: Focused crawler (also known as theme crawler) is an effective tool to get data in any specific domain from Web. However, conventional focused crawlers need a classifier to filter out the irrelevant webpages, and to get such a classifier is usually labor-intensive. In this paper, we propose a Bootstrapping Focused Crawler (BFC) for collecting information from a group of websites in the same category. Instead of pre-training a tailored classifier, BFC adopts a ranking module to do the classification. In the experiments, the recall and F1-score of BFC is significantly better than conventional focused crawler, from which we could draw the conclusion that our approach is more effective for the crawling tasks within a group of similar websites.
Key Words: Web crawler; information retrieval; bootstrapping focused crawler
0 引言
從Web上收集特定主題數(shù)據(jù)的技術(shù)可分為兩類:①基于搜索的發(fā)現(xiàn)技術(shù)[1-3],主要依靠搜索引擎查找網(wǎng)頁(yè);②基于爬行的發(fā)現(xiàn)技術(shù)[4-6],主要利用Web鏈接結(jié)構(gòu)從已下載的網(wǎng)頁(yè)中提取新鏈接,從而發(fā)現(xiàn)更多潛在的目標(biāo)網(wǎng)頁(yè)。前者適用于存在一些關(guān)鍵字可區(qū)分主題數(shù)據(jù)和其它數(shù)據(jù)的情況,后者靈活性更強(qiáng),代表技術(shù)就是聚焦爬蟲。
與普通爬蟲相比,聚焦爬蟲有明確的目標(biāo)指向性,在爬取網(wǎng)頁(yè)過程中能夠丟棄不相關(guān)頁(yè)面,并始終跟蹤可能導(dǎo)向“相關(guān)”頁(yè)面的超鏈接,因而能更有效地收集特定主題的數(shù)據(jù)。聚焦爬蟲框架與一般爬蟲基本相同,也即是說,它從幾個(gè)種子鏈接(Seed URL)開始,下載相關(guān)頁(yè)面并提取其中包含的超鏈接,然后跟蹤這些超鏈接以獲取更多頁(yè)面。不斷重復(fù)該過程,直到無(wú)法以這種方式找到更多網(wǎng)頁(yè)。聚焦爬蟲的特殊之處在于,其會(huì)引入兩個(gè)分類器——路徑判別器和目標(biāo)判別器,以決定某個(gè)超鏈接是否值得進(jìn)一步訪問,以及某頁(yè)面是否值得保存。其中,路徑判別器負(fù)責(zé)判斷鏈接值得跟蹤與否,目標(biāo)判別器負(fù)責(zé)根據(jù)網(wǎng)頁(yè)與主題相關(guān)與否對(duì)其進(jìn)行歸類。
聚焦爬蟲研究主要集中在3個(gè)方面:一是如何獲得更有效的分類器,例如使用在線學(xué)習(xí)策略構(gòu)建路徑判別器(目標(biāo)判別器依然需要進(jìn)行預(yù)訓(xùn)練)[7,14-18];二是如何獲得更好的種子鏈接,例如維埃拉等[3]利用Bing搜索引擎,使用相關(guān)反饋(Relevance Feedback)收集種子;三是如何設(shè)計(jì)更好的爬行策略[8-12,19-22]。盡管這些研究從各個(gè)方面對(duì)聚焦爬蟲進(jìn)行了改進(jìn),預(yù)先訓(xùn)練分類器的工作仍不可省略,因此造成了爬蟲使用的不便。由于其分類器是任務(wù)相關(guān)的,換一個(gè)目標(biāo)主題就要重新手動(dòng)構(gòu)建數(shù)據(jù)集進(jìn)行訓(xùn)練。
最近,KIEN[13]將聚焦爬行描述為一個(gè)排序問題,其跳過分類器訓(xùn)練,只使用一些示例網(wǎng)站作為輸入。從樣本網(wǎng)站中提取關(guān)鍵詞,再通過關(guān)鍵字搜索、前向爬行和后向爬行擴(kuò)展樣本網(wǎng)站集,其設(shè)計(jì)的系統(tǒng)根據(jù)與當(dāng)前樣本網(wǎng)站的相似性選擇新的樣本網(wǎng)站。結(jié)果表明,通過適當(dāng)?shù)南嗨菩远攘?,基于排序的聚焦爬蟲可取得與基于分類器的聚焦爬蟲相似的性能表現(xiàn)。但其問題設(shè)置與本文不同,其目標(biāo)是得到相關(guān)網(wǎng)站,而不是網(wǎng)頁(yè)。因此,以上實(shí)踐啟發(fā)了本文用排序器替換預(yù)訓(xùn)練分類器構(gòu)建自舉聚焦爬蟲,以解決網(wǎng)站群內(nèi)部的主題網(wǎng)頁(yè)發(fā)現(xiàn)問題。
本文設(shè)計(jì)一種自舉聚焦爬蟲(Bootstrapping Focused Crawler,簡(jiǎn)稱BFC),該方法為聚焦爬蟲提供一些示例網(wǎng)頁(yè),而不是預(yù)先訓(xùn)練的分類器,從而可略過繁復(fù)的分類器訓(xùn)練過程。該方法適用于特定網(wǎng)站群中的主題數(shù)據(jù)收集,例如收集各大學(xué)錄取信息、各公司招聘信息、各政府網(wǎng)站的政策信息等。圖1展示了兩個(gè)爬取任務(wù)示例。任務(wù)難點(diǎn)在于,上千所高校、公司雖然網(wǎng)站架構(gòu)類似,但每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的超鏈接文字用詞千差萬(wàn)別,路徑深度與目標(biāo)頁(yè)面特征也存在顯著差異。因此,在不預(yù)訓(xùn)練分類器的前提下,只提供少量樣例網(wǎng)頁(yè)充當(dāng)爬蟲向?qū)?,是一種新的嘗試。
由于特定網(wǎng)站群是眾多一手信息的源頭,如果能及時(shí)、有效地收集相關(guān)信息并匯聚起來,將極大地降低信息瀏覽門檻,并催生出數(shù)據(jù)可視化等應(yīng)用。因此,本文提出的網(wǎng)站群爬蟲具有很強(qiáng)的現(xiàn)實(shí)意義。
1 自舉聚焦爬蟲
自舉聚焦爬蟲框架如圖2所示。
程序有兩個(gè)輸入:一個(gè)是網(wǎng)站群站點(diǎn)(Website)列表,一個(gè)是少量樣例網(wǎng)頁(yè),每個(gè)樣例網(wǎng)頁(yè)包含其所在站點(diǎn)的根鏈接和自身鏈接這一對(duì)元素。首先,對(duì)樣例網(wǎng)頁(yè)進(jìn)行路徑提取與特征提取。在傳統(tǒng)聚焦爬蟲框架下,需要一個(gè)能引導(dǎo)爬蟲到目標(biāo)節(jié)點(diǎn)的向?qū)В窂脚袆e器),以及能夠區(qū)分目標(biāo)節(jié)點(diǎn)與其它節(jié)點(diǎn)的評(píng)委(目標(biāo)判別器)。路徑提取目標(biāo)是構(gòu)建路徑判別器,而特征提取目標(biāo)是構(gòu)建目標(biāo)判別器。區(qū)別在于,本文提出的自舉聚焦爬蟲用相似度排序模塊替代傳統(tǒng)框架下的目標(biāo)判別器,用類似于強(qiáng)化學(xué)習(xí)的手段在線構(gòu)建路徑判別器。然后利用兩個(gè)判別器從輸入的網(wǎng)站群根節(jié)點(diǎn)開始循環(huán)抓取網(wǎng)頁(yè),并不斷把最相關(guān)的網(wǎng)頁(yè)加入網(wǎng)頁(yè)樣例庫(kù),用于更新兩個(gè)判別器。該流程循環(huán)進(jìn)行,直到無(wú)法發(fā)現(xiàn)更多網(wǎng)頁(yè)或達(dá)到迭代次數(shù)上限為止。
1.1 路徑判別器
路徑判別器本質(zhì)上是一個(gè)二分類器:輸入一個(gè)超鏈接短文本,輸出其是否與要爬取的主題相關(guān),或沿著該鏈接是否能找到與主題相關(guān)網(wǎng)頁(yè)。在網(wǎng)站群爬蟲這個(gè)具體應(yīng)用場(chǎng)景中,存在一條從站點(diǎn)根節(jié)點(diǎn)到當(dāng)前頁(yè)面的超鏈接路徑(見圖1),可利用這條路徑上的前序文本增強(qiáng)當(dāng)前鏈接短文本的判斷準(zhǔn)確度。因此,本文通過路徑提取將傳統(tǒng)路徑判別器的單一短文本輸入擴(kuò)充為短文本列表。
2 爬取效果
2.1 實(shí)驗(yàn)任務(wù)與數(shù)據(jù)集
本文按照中國(guó)大學(xué)排行榜,收集了中國(guó)排名前200的大學(xué)官方網(wǎng)站頁(yè)面集合作為實(shí)驗(yàn)數(shù)據(jù)集。為檢驗(yàn)爬蟲性能,定義主題爬取任務(wù)如下:獲取高校歷史錄取分?jǐn)?shù)相關(guān)頁(yè)面。本文手動(dòng)標(biāo)記每個(gè)站點(diǎn)與所需主題相關(guān)頁(yè)面(URL)作為真實(shí)標(biāo)簽,數(shù)據(jù)集頁(yè)面總數(shù)為41 600,其中正樣本數(shù)量為1 033。
為得到樣例網(wǎng)頁(yè)庫(kù)作為算法輸入,本文從200個(gè)網(wǎng)站中隨機(jī)抽取3個(gè)網(wǎng)站,并為每個(gè)網(wǎng)站標(biāo)記一個(gè)示例頁(yè)面,得到3個(gè)樣例(每個(gè)樣例含有一對(duì)數(shù)據(jù),即目標(biāo)網(wǎng)頁(yè)的URL以及所在網(wǎng)站根節(jié)點(diǎn)的URL)。通過對(duì)4組使用不同樣例集的爬蟲計(jì)算平均得分,得到BFC性能得分。
2.2 效果展示
本文選取傳統(tǒng)聚焦爬蟲(FC)作為基線算法進(jìn)行對(duì)比。出于公平性考慮,F(xiàn)C所需分類器基于樣例網(wǎng)頁(yè)庫(kù)的少量正樣本,采用KNN算法獲得。本文提出的自舉聚焦爬蟲(BFC)與基線算法FC在高校歷史錄取分?jǐn)?shù)爬取任務(wù)中的表現(xiàn)對(duì)比如表1所示。
由表1可以看到,BFC的準(zhǔn)確率(Precision)比傳統(tǒng)方法FC低很多,其原因是FC爬取頁(yè)面數(shù)量較少,以極低的召回率(Recall)為代價(jià)獲得了較高準(zhǔn)確率。然而,在爬蟲實(shí)際使用過程中,召回率更為重要,因?yàn)橐M可能全面地收集所需信息,而在自動(dòng)篩選環(huán)節(jié)一旦遺漏相關(guān)信息,就很難再找到目標(biāo)網(wǎng)頁(yè)。在召回率方面,BFC的表現(xiàn)遠(yuǎn)好于FC。綜合準(zhǔn)確率和召回率的指標(biāo)F1-Score也顯示BFC的性能優(yōu)于FC。
爬取部分結(jié)果如圖3所示。圖中name列輸出爬取站點(diǎn),url列輸出任務(wù)相關(guān)頁(yè)面網(wǎng)址,path列輸出從網(wǎng)站根節(jié)點(diǎn)到頁(yè)面的路徑,score是該頁(yè)面相關(guān)性得分。
3 結(jié)語(yǔ)
本文設(shè)計(jì)一種自舉聚焦爬蟲用于特定網(wǎng)站群中的主題數(shù)據(jù)收集,該方法以聚焦爬蟲為基礎(chǔ),替代了預(yù)先訓(xùn)練路徑分類器和目標(biāo)分類器的步驟,轉(zhuǎn)而通過提供一些示例網(wǎng)頁(yè),通過排序模塊進(jìn)行相關(guān)性判別工作。在大學(xué)錄取信息爬取任務(wù)中,本文方法獲得了62%的召回率,遠(yuǎn)高于傳統(tǒng)方法。因此,針對(duì)網(wǎng)站群主題數(shù)據(jù)采集任務(wù),實(shí)驗(yàn)結(jié)果表明,采用相似度排序替代主題分類器不僅可以減輕分類器訓(xùn)練負(fù)擔(dān),還可以達(dá)到更好的效果。對(duì)于一般性的主題數(shù)據(jù)采集任務(wù),也可以嘗試?yán)帽疚乃悸贰?/p>
參考文獻(xiàn):
[1] DISHENG Q, LUCIANO B, XIN L,et al. Dexter: large-scale discovery and extraction of product specifications on the web[C]. Proceedings of the VLDB Endowment, 2015:2194-2205.
[2] XUEZHI W, CONG Y, SIMON B,et al. Relevant document discovery for fact-checking articles[C]. ?In Companion Proceedings of the Web Conference, 2018: 525-533.
[3] KARANE V, LUCIANO B, ALTIGRAN S D S, et al. Finding seeds to bootstrap focused crawlers[C]. ?In The World Wide Web Conference, 2016: 449-474.
[4] LUCIANO B, SRINIVAS B,VIVEK K R S. Crawling back and forth: using back and out links to locate bilingual sites[C]. ?In Proceedings of 5th International Joint Conference on Natural Language Processing, 2011:429-437.
[5] TSUYOSHI M. Finding related web pages based on connectivity information from a search engine[C]. ?In WWW Posters, 2001.
[6] LUCIANO B. Harvesting forum pages from seed sites[C]. ?In International Conference on Web Engineering, 2017: 457-468.
[7] MCCALLUM A, NIGAM K, RENNIE J, et al. A machine learning approach to building domain-specific search engines[C]. ?Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence,1999:662-667.
[8] MICHAEL H, MICHAL J, YOELLE S M,et al. The shark-search algorithm. An application: tailored Web site mapping[J]. ?Computer Networks & Isdn Systems, 1998, 30(1-7):317-326.
[9] BERGMARK D, LAGOZE C, SBITYAKOV A. Focused crawls, tunneling, and digital libraries [C]. Proceedings of the 6th European Conference on Research and Advanced Technology for Digital Libraries,2002.
[10] MARISTELLA A, COSTANTINO T. Research and Advanced Technology of digital libraries[M]. Springer Berlin Heidelberg, 2002:91-106.
[11] 葉勤勇. 基于URL規(guī)則的聚焦爬蟲及其應(yīng)用[D]. 杭州:浙江大學(xué), 2007
[12] BRA P M E D,POST R D J. Information retrieval in the World-Wide Web: making client-based searching feasible[J]. Computer Networks & Isdn Systems, 1994, 27(2):183-192.
[13] KIEN P, AECIO S, JULIANA F. Bootstrapping domain-speci c content discovery on the Web[C]. In The World Wide Web Conference, 2019: 1476-1486.
[14] 傅向華,馮博琴,馬兆豐,等. 可在線增量自學(xué)習(xí)的聚焦爬行方法[J]. 西安交通大學(xué)學(xué)報(bào),2004,38(6):599-602.
[15] 劉國(guó)靖,康麗,羅長(zhǎng)壽. 基于遺傳算法的主題爬蟲策略[J]. 計(jì)算機(jī)應(yīng)用,2007,27(12):172-174.
[16] 曾廣樸,范會(huì)聯(lián). 基于遺傳算法的聚焦爬蟲搜索策略[J]. 計(jì)算機(jī)工程,2010,36(11):167-169.
[17] 童亞拉. 自適應(yīng)動(dòng)態(tài)演化粒子群算法在Web主題信息搜索中的應(yīng)用[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2008,33(12):1296-1299.
[18] 賀晟,程家興,蔡欣寶. 基于模擬退火算法的主題爬蟲[J]. 計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(12):55-58.
[19] 宋海洋,劉曉然,錢??? 一種新的主題網(wǎng)絡(luò)爬蟲爬行策略[J]. 計(jì)算機(jī)應(yīng)用與軟件,2011,28(11):264-267.
[20] 謝志妮. 一種新的基于概念樹的主題網(wǎng)絡(luò)爬蟲方法[J]. 計(jì)算機(jī)與現(xiàn)代化,2010,176(4):103-106.
[21] 左薇,張熹,董紅娟,等. 主題網(wǎng)絡(luò)爬蟲研究綜述[J]. 軟件導(dǎo)刊,2020,19 (2): 278-281.
[22] 韓瑞昕. 基于時(shí)效性的爬蟲調(diào)度[J]. 軟件導(dǎo)刊,2020,19(1):108-112.
(責(zé)任編輯:黃 ?。?/p>