基于動態(tài)隧道技術(shù)的主題爬行策略①

姜 琨,朱 磊,王一川

(西安理工大學(xué) 計算機科學(xué)與工程學(xué)院,西安 710048)

互聯(lián)網(wǎng)網(wǎng)頁的聚集特性表明主題頁面容易聚集出現(xiàn),因主題相關(guān)或相近而鏈接在一起的互聯(lián)網(wǎng)網(wǎng)頁被稱為主題島或者主題團.主題爬蟲依據(jù)主題團的聚集特性對網(wǎng)頁進行采集.然而,并非所有的主題相關(guān)網(wǎng)頁都是鏈接在一起的,它們之間可能要跨過幾個主題不相關(guān)頁面的鏈接.許多主題島被這些主題無關(guān)的頁面鏈接,使主題島之間被分隔,這種現(xiàn)象被稱為主題孤島.如圖1 所示,這些無關(guān)頁面的鏈接分布在互聯(lián)網(wǎng)上待采集的主題團之間,形成連接主題孤島的一個隧道,這就是Web 頁面的隧道特性[1,2].實際的Web 中存在大量這樣的主題孤島,如果主題爬蟲系統(tǒng)只通過父頁面來預(yù)測子頁面的相關(guān)度,只提取主題相關(guān)頁面中的超鏈接作為種子鏈接,那么就會丟失大量的主題孤島.因為如果子頁面是主題無關(guān)的,爬蟲就可能不會訪問該頁面中的超鏈接,這些鏈接可能穿過數(shù)次鏈接而連著另一個主題孤島.

圖1 主題孤島問題示意圖

如果為了提高爬蟲采集頁面的準確度而提高爬行策略中的相關(guān)度閾值,則會過濾掉大量的隧道,這樣就訪問不到隧道另一端可能存在的主題孤島,導(dǎo)致爬蟲的對主題網(wǎng)頁的召回率較低.為了提高爬蟲一次爬行過程所采集主題相關(guān)頁面的數(shù)量,往往會降低爬行策略中判斷主題相關(guān)與否的相關(guān)度閾值.如果這個隧道很長,那么降低相關(guān)度閾值去訪問這些主題孤島,又會采集隧道路徑上的大量主題無關(guān)頁面,但是有一定概率發(fā)現(xiàn)新的主題相關(guān)頁面[2].

本文在分析現(xiàn)有主題爬蟲爬行策略特點的基礎(chǔ)上,針對現(xiàn)有主題爬行策略不能很好解決主題孤島問題,提出一種能在爬蟲爬行過程中對不相關(guān)頁面中提取的URL 鏈接對應(yīng)頁面的主題相關(guān)度進行預(yù)測,并動態(tài)調(diào)整隧道長度的主題爬行策略模型,從而可以挖掘不相關(guān)網(wǎng)頁信息及發(fā)現(xiàn)隱藏的主題團相關(guān)鏈接.

1 主題爬行策略研究現(xiàn)狀

普通網(wǎng)頁爬蟲一般采用廣度或者深度優(yōu)先的爬行策略,而主題爬蟲采用的爬行策略按照判斷網(wǎng)頁相關(guān)度的不同分為:基于內(nèi)容分析的爬行策略、基于鏈接分析的爬行策略和基于語境圖的爬行策略等[3].

1.1 基于內(nèi)容分析的爬行策略

基于內(nèi)容分析的主題爬行策略主要是利用頁面或者鏈接的內(nèi)容特征對頁面與主題的相關(guān)程度進行打分評價,進而對待采集網(wǎng)頁和爬行方向進行優(yōu)化選擇[4].基于內(nèi)容分析的主題爬行策略主要有:最佳優(yōu)先搜索(Best First Search,BFS)、Fish Search、Shark Search 等3 種策略[5].

BFS 策略的基本思想是利用主題團特征,通過分析當(dāng)前已經(jīng)獲取的頁面,使用一定的打分策略來預(yù)測與其連接的頁面的主題相關(guān)度,然后使用最好優(yōu)先的原則每次優(yōu)先選擇主題相關(guān)度最高的頁面作為下一個處理的對象.與主題關(guān)系比較密切的頁面,它所包含鏈接的優(yōu)先級就高,這樣就確定了等待處理的鏈接隊列中鏈接的前后順序.該策略每次添加到爬蟲種子優(yōu)先級隊列的鏈接的優(yōu)先級分數(shù)是相同的.

在Fish Search 策略中,當(dāng)通過某一鏈接發(fā)現(xiàn)主題相關(guān)頁面時,沿著這個方向的爬行深度增加,且后代鏈接的爬行深度保持不變.如果沒有發(fā)現(xiàn)主題相關(guān)頁面,這個鏈接的爬行深度不變,但是后代鏈接的爬行深度遞減.如果沿著某個方向經(jīng)過多次采集仍然沒有找到主題相關(guān)頁面,那么它的爬行深度會逐漸降低直至為零.Fish Search 策略在主題不相關(guān)方向上的采集具有一定的動態(tài)特性,但是其主題相關(guān)性的判斷僅僅是一種二值分類判斷,不能評價相關(guān)程度的高低.

Shark Search 策略是對Fish Search 策略中主題相關(guān)度打分策略的改進,其頁面與主題之間的相關(guān)程度是一個介于0 到1 之間的連續(xù)值,這一改進的優(yōu)點是可以獲得一個URL 與主題的相關(guān)程度.然而,因為Shark Search 和Fish Search 策略在主題不相關(guān)頁面方向上采用了降低爬行深度的數(shù)據(jù)采集,而且對主題不相關(guān)頁面采取了和之前頁面相同的分析方法,因而導(dǎo)致其提升召回率的代價是犧牲了爬蟲的準確率.

1.2 基于鏈接分析的爬行策略

基于鏈接分析的爬行策略主要是依據(jù)網(wǎng)頁之間的引用關(guān)系和頁面已知重要度分數(shù)來判斷網(wǎng)頁之間的重要程度.基于鏈接分析的爬行策略主要是基于以下兩個條件:(1)如果在網(wǎng)頁A 中包含網(wǎng)頁B 的鏈接,則表明網(wǎng)頁A 對網(wǎng)頁B 重要性的推薦;(2)此時,如果在網(wǎng)頁B 中也同時包含網(wǎng)頁A 的鏈接,則網(wǎng)頁A 和網(wǎng)頁B 一般有共同的主題.比較有代表性的基于鏈接分析的爬行策略如:基于PageRank 的鏈接分析方法等.

PageRank(PR)[6]用于搜索引擎中對查詢結(jié)果進行排序,近年來也被用于預(yù)測主題爬蟲的鏈接優(yōu)先級.PR 鏈接分析方法對網(wǎng)頁重要性的打分評價主要依據(jù)3 個方面:(1)內(nèi)鏈越多的網(wǎng)頁越重要,即其他網(wǎng)頁對該網(wǎng)頁的推薦較多;(2)內(nèi)鏈的網(wǎng)頁重要度越高,被這些高質(zhì)量網(wǎng)頁的鏈接指向的網(wǎng)頁也越重要;(3)外鏈數(shù)越少的網(wǎng)頁相對越重要,即一般重要網(wǎng)頁中的鏈接都是其子鏈接.然而,為了降低動態(tài)計算每個待爬取隊列里URL 鏈接的PR 值的代價,實際獲得PR 值都是非精確的.

基于內(nèi)容分析的爬行策略和基于鏈接分析的爬行策略都屬于立即回報型爬行策略,這類爬行算法通過分析當(dāng)前的頁面內(nèi)容或者鏈接信息,目的是要通過這樣的分析來及時指導(dǎo)緊接著的爬行方向.這類主題爬行策略雖然在主題頁面附近的時候能夠表現(xiàn)出較好的性能,但是對那些有潛在主題相關(guān)性的鏈接不夠關(guān)注甚至過早丟棄,所以在距離主題頁面較遠的地方就有可能會出現(xiàn)“主題漂移”的現(xiàn)象,也難以有效解決主題孤島問題[5].

1.3 基于語境圖的爬行策略

為了解決有效主題孤島問題,研究人員提出語境圖爬行策略(context graph)[7].這種策略的訓(xùn)練過程首先要給系統(tǒng)提供一組種子主題頁面,然后利用Google反向鏈接服務(wù)尋找到所有擁有指向種子頁面鏈接的頁面作為第一層頁面,而所有擁有指向第一層頁面鏈接的頁面被稱作第二層頁面,依次類推,層數(shù)由用戶控制.圖2 展示了一個深度為2 的語境圖.當(dāng)每一個種子頁面都建立好一個語境圖后,將不同的語境圖的相應(yīng)各層進行合并,形成一個合并語境圖(merged context graph).然后為合并語境圖的每一層訓(xùn)練一個貝葉斯分類器.在爬行過程中,分類器被用來確定所要爬行的頁面應(yīng)該屬于哪一層,從而有效識別主題相關(guān)度較低網(wǎng)頁的所屬的層數(shù)并計算爬行優(yōu)先分數(shù).

基于語境圖的爬行策略避免了立即回報型爬行策略只關(guān)注能帶來立即效益鏈接的缺點.然而基于語境圖的爬行策略需要為其建立語境圖模型,因此這種方法無疑加重了主題搜索引擎的復(fù)雜度.本文在考慮到基于語境圖的爬行策略的在線復(fù)雜度和其采用的利用Google 反向鏈接服務(wù)的局限性,受基于語境圖的爬行策略中采用的主題層次思想降低隧道長度的啟發(fā),提出一種新的主題爬行策略,其可以通過預(yù)測URL 鏈接相關(guān)度方法分析隱含的主題層次結(jié)構(gòu),并動態(tài)維護各個主題層次的隧道長度,并使爬行過程具有較低在線復(fù)雜度和更好可操作性.

圖2 一個兩層的語境圖模型

2 基于動態(tài)隧道技術(shù)的爬行策略

基于語境圖的爬行策略為我們提供了一個發(fā)現(xiàn)隱藏主題相關(guān)鏈接的很好的思路,對于爬蟲發(fā)現(xiàn)的主題不相關(guān)鏈接也不能輕易拋棄,而是要看它是否屬于主題相關(guān)鏈接的前驅(qū)鏈接.如果一個爬蟲的目標是獲取與“體育”主題相關(guān)的網(wǎng)頁內(nèi)容,那么一些體育高校的主頁可能是很有價值的,雖然這些頁面本身并不一定直接與“體育”的主題有關(guān)系,但是這些主頁可能會鏈接到某些和“體育”相關(guān)的新聞頁面,在這些新聞的頁面中則對應(yīng)的著“體育”主題相關(guān)的頁面.如:“北京體育大學(xué)”主頁中包含“媒體北體”頁面,然后進一步鏈接到“新華社”等多個“體育”主題相關(guān)新聞網(wǎng)站.在這種情況下,體育高校的主頁、學(xué)校的新聞頁面或者論壇主頁等與“體育”主題相關(guān)或相近的頁面和“體育”主題目標頁面之間就形成了一種既有聯(lián)系又有區(qū)別的層次結(jié)構(gòu),而在這種層次結(jié)構(gòu)中就隱含了能夠找到目標主題頁面的爬行路徑.互聯(lián)網(wǎng)網(wǎng)頁的主題相關(guān)層次示意圖如圖3.

基于語境圖的爬行策略認為主題爬蟲在互聯(lián)網(wǎng)上查找某個特定主題的信息時,如果發(fā)現(xiàn)某一網(wǎng)頁的主題和給定主題存在某種預(yù)定義的相關(guān)性時,就可以認為沿著這些在層次結(jié)構(gòu)中的相近頁面必定能找到更多的主題頁面.在爬蟲實現(xiàn)中,通過建立主題相關(guān)詞典模型和主題相近詞典模型,對主題不相關(guān)鏈接進行進一步語義挖掘,就可能發(fā)現(xiàn)更多的主題團,從而在一定程度上解決主題孤島問題.本節(jié)采用URL 鏈接相關(guān)度預(yù)測的方法進行定量的語義挖掘,得出在兩個詞袋(bagof-words)模型下不相關(guān)網(wǎng)頁的相似度,結(jié)合動態(tài)隧道模型來確定爬蟲在不相關(guān)網(wǎng)頁上的預(yù)測深度.

圖3 互聯(lián)網(wǎng)網(wǎng)頁主題相關(guān)層次圖

2.1 動態(tài)隧道長度

Bergmark 等提出了隧道技術(shù)來描述和解決主題孤島問題[8].使用隧道技術(shù)的主題爬蟲在碰到主題不相關(guān)的網(wǎng)頁時會繼續(xù)在該鏈接方向上向前探索k步.這樣主題爬蟲可以從一個主題團游走到另外一個主題團,其中可能經(jīng)過多層主題相關(guān)度較低的頁面.如果在兩個主題團之間的距離不大的前提下,就可能發(fā)現(xiàn)互聯(lián)網(wǎng)中所有與預(yù)定義主題相關(guān)的網(wǎng)頁.Bergmark 在對500 000 個網(wǎng)頁的分析表明主題孤島現(xiàn)象的普遍性以及大多數(shù)屬于主題孤島的距離在1 和12 之間,平均距離是5.然而,采用隧道技術(shù)的主題爬蟲在遇到主題相關(guān)度較低的頁面時會擴大探索范圍.也就是說,爬蟲以種子集為圓心,以k為半徑的圓周范圍中探索其它主題團,隨著半徑k的增大,發(fā)現(xiàn)其它主題團的概率也在增大,但是需要處理的主題無關(guān)網(wǎng)頁也以顯著增加.實際上,當(dāng)k無限增大時,主題爬蟲對每個預(yù)測不相關(guān)的網(wǎng)頁都要進行采集,這樣的主題爬蟲就成為了通用爬蟲.因此可以說,這種方法是放松了對主題爬蟲的定義來提高召回率,從而極大地降低了爬蟲的效率[9].

盡管可以采用人工動態(tài)調(diào)整主題相關(guān)閾值的辦法來改變一個鏈接的主題相關(guān)情況,但也只有鏈接相關(guān)和不相關(guān)兩種情況.因而該技術(shù)在檢測頁面不相關(guān)時,對該方向上的鏈接爬行深度的設(shè)定完全沒有考慮到在該方向上爬行每層頁面的動態(tài)情況.因此,Bergmark 等提出的隧道技術(shù)屬于在主題相關(guān)度較低鏈接方向上的靜態(tài)探索技術(shù),即在主題不相關(guān)時仍然搜索k步,而不去關(guān)注這k步的搜索中獲取的鏈接的反饋信息.而Fish Search 策略的動態(tài)隧道思想表現(xiàn)在如果出現(xiàn)鏈接主題不相關(guān),則減少該方向上下一個鏈接的隧道長度.如果遇到潛在的URL 鏈接相關(guān)度較高,但是頁面主題相關(guān)性不夠高的情況,那么原來的方法難以將這一信息及時反饋到主題爬蟲.這一問題很大限制了主題爬蟲發(fā)現(xiàn)主題孤島的能力.

互聯(lián)網(wǎng)網(wǎng)頁的主題相關(guān)層次表明,對于主題不相關(guān)網(wǎng)頁還需要進一步分析其是否屬于主題語境圖中的某一層.如果該鏈接屬于語境圖層次結(jié)構(gòu)中的某一層時,沿著這個鏈接方向的爬行深度增加,并且后代鏈接的爬行深度保持不變.如果通過該鏈接不屬于主題層次結(jié)構(gòu)的任何一層,則這個鏈接本身的爬行深度不變,但是后代鏈接的爬行深度才需要遞減.因此,采用動態(tài)控制主題不相關(guān)方向上的搜索深度,可以發(fā)現(xiàn)潛在的優(yōu)質(zhì)主題URL 鏈接,從而增加發(fā)現(xiàn)主題孤島的可能性.

2.2 主題爬行模型

結(jié)合主題相關(guān)層次和隧道長度的分析,本文提出的解決主題孤島問題的爬行策略的主要思想為:爬蟲在遇到主題相關(guān)頁面時,將該頁面中的所有URL 鏈接和其優(yōu)先值pv(pv=主題相關(guān)度)送到爬蟲的優(yōu)先級隊列,相關(guān)度越高的頁面其URL 外鏈優(yōu)先級越高,在優(yōu)先級隊列中也應(yīng)當(dāng)被優(yōu)先采集;此時候選URL 鏈接非常多,爬蟲不可能出現(xiàn)優(yōu)先隊列空的現(xiàn)象;此時采用廣度優(yōu)先的方式對相同頁面的相同優(yōu)先級的頁面進行采集.

主題爬蟲通過式(1)計算得到主題不相關(guān)的頁面時(pv=0),并不是停止獲取其頁面中的URL 外鏈,而是繼續(xù)在所獲取的URL 外鏈上向前探索k步路徑.對于路徑上的每一層頁面,若在此路徑上通過下一節(jié)所闡述的URL 鏈接相關(guān)度預(yù)測方法發(fā)現(xiàn)潛在主題相關(guān)頁面(pv=0),爬蟲在這個鏈接方向上的爬行深度保持不變,否則k值遞減.此時采用深度優(yōu)先的方法判斷獲得的頁面是否仍然是不相關(guān)頁面,直到達到某一個主題相關(guān)頁面為止(pv=主題相關(guān)度).策略流程如圖4所示,工作流程為:對采集到的某網(wǎng)頁去噪之后得到正文內(nèi)容,之后調(diào)用主題詞庫進行相關(guān)度計算.如果與主題相關(guān),則將當(dāng)前爬行深度設(shè)為 ∞,表示按照原有方式進行采集.如果與主題不相關(guān),檢查爬行深度值k.如果k=0,表示在此鏈接方向上已經(jīng)無需再采集,并停止采集.如果k=∞,表示k值未被設(shè)置過,并設(shè)置k=kdepth,遞減k值之后交由后續(xù)模塊處理.如果 0 ≤k＜∞,調(diào)用下節(jié)所述的URL 鏈接相關(guān)度預(yù)測方法進行頁面相關(guān)度計算,在這種情況下,要URL 和主題內(nèi)容相關(guān),則使當(dāng)前深度不變,并交后續(xù)模塊處理;要是不相關(guān),則使爬行深度遞減,并交后續(xù)模塊處理.

圖4 動態(tài)隧道技術(shù)策略流程圖

這種策略的優(yōu)點在于,在不相關(guān)頁面方向上設(shè)定的爬行深度是動態(tài)變化的,它把不相關(guān)頁面方向上的信息反饋到對隧道爬行深度k的動態(tài)控制,因此被稱為動態(tài)隧道技術(shù)(Dynamic Tunneling Heuristic,DTH).因此,該策略減少了在此方向上的搜索,這樣可以有效的降低了主題爬蟲的在主題無關(guān)方向上的爬行范圍;而對于通過URL 鏈接相關(guān)度預(yù)測后發(fā)現(xiàn)可能有潛在主題相關(guān)的鏈接,該策略加大了在此方向上的爬行深度,這樣能進一步發(fā)現(xiàn)隱藏的主題團.因此,該策略利用URL 鏈接相關(guān)度預(yù)測和動態(tài)隧道控制技術(shù)對潛在的主題團進行搜索.

主題爬蟲如果僅僅采用頁面主題相關(guān)度計算方法,則隨著爬蟲不斷的爬取新的主題頁面,新的主題關(guān)鍵詞會不斷加入主題詞庫并獲得新的權(quán)重,從而出現(xiàn)“主題漂移”現(xiàn)象.這主要是因為主題頁面的缺失導(dǎo)致的,此時雖然出現(xiàn)大量主題無關(guān)頁面,但是主題爬蟲卻無法發(fā)現(xiàn)新的主題團,因此會制約主題爬蟲的準確率.本文方法對主題無關(guān)頁面進行URL 鏈接相關(guān)度分析,能夠提升主題爬蟲發(fā)現(xiàn)新主題頁面的準確率.如果將頁面主題相關(guān)度計算和URL 鏈接主題相關(guān)度計算結(jié)合,則會明顯影響主題爬蟲在主題團內(nèi)部爬取主題頁面時的性能.

2.3 URL 鏈接相關(guān)度預(yù)測

主題爬蟲系統(tǒng)的主題相關(guān)度判斷方法:爬蟲系統(tǒng)需要維護一個主題詞庫,其中包括了由大量主題相關(guān)的關(guān)鍵詞組成的主題向量和每個主題詞出現(xiàn)在網(wǎng)頁中的個數(shù)IDF.主題詞典的關(guān)鍵詞來源是預(yù)先給定的網(wǎng)頁頁面,包括爬蟲系統(tǒng)初始化時給定URL 鏈接種子對應(yīng)的頁面和主題詞庫更新過程中添加的該領(lǐng)域比較有代表性的網(wǎng)頁.

主題爬蟲系統(tǒng)運行過程中對于主題頁面的選擇規(guī)則如下:含有“default”、“index”等信息的URL 鏈接可以初步作為主題頁面;不能作為主題頁面的規(guī)則為:入鏈小于一定閾值的頁面;錨文本過長的頁面;錨文本中包含“下一頁”、“更多”等信息的頁面;URL 過長的頁面等.對于利用上述規(guī)則選擇的多個主題頁面,再通過TextRank 策略進行主題向量抽取,形成主題詞庫.主題向量T是由基于TextRank 的關(guān)鍵詞抽取方法提取的關(guān)鍵詞及其權(quán)重wi,r組成.TextRank 是一種非監(jiān)督式的主題抽取策略,不依賴于其他語料,直接從文本中抽取主題關(guān)鍵詞;適用于對于少量網(wǎng)頁文本的主題關(guān)鍵詞進行分析.主題詞典可以在爬蟲未啟動時進行更新維護,輸入發(fā)現(xiàn)的新的網(wǎng)頁正文進行重新計算.

本文在對網(wǎng)頁Pj進行正文提取后首先采用向量空間模型(VSM)來計算網(wǎng)頁內(nèi)容與主題的相關(guān)度,即利用基于TextRank 的抽取得到的主題向量和給定網(wǎng)頁特征向量計算當(dāng)前頁面的主題相關(guān)度,計算公式如下:

其中,wi,j表示特征向量在給定網(wǎng)頁文本中的權(quán)重值,wi,r表示特征向量i在主題向量中的權(quán)值,T代表主題向量,Sim(Pj,T)表 示文本Pj與給定主題向量的相關(guān)度.計算文本權(quán)重值wi,j的策略是TF-IDF,即:

其中,t fi,j表示關(guān)鍵詞ti在給定網(wǎng)頁正文Pj中出現(xiàn)的次數(shù),dfi則 表明當(dāng)前關(guān)鍵詞ti在已經(jīng)采集的網(wǎng)頁中出現(xiàn)次數(shù),N為已經(jīng)采集的網(wǎng)頁數(shù)量.

在2.2 節(jié)的主題爬行模型中,如果當(dāng)前網(wǎng)頁通過式(1)計算得出是主題不相關(guān)的,則進一步對該網(wǎng)頁中的URL 鏈接的主題相關(guān)度進行預(yù)測.其中需要考慮URL 鏈接的錨文本本身、URL 鏈接的上下文環(huán)境以及URL 鏈接字符串的主題相關(guān)度等3 個因素.因此,待采集URL 鏈接p對應(yīng)頁面的主題相關(guān)度計算如下:

其中,w1+w2+w3=1.

RArchor(p)指的是URL 鏈接p對應(yīng)的錨文本的主題相關(guān)度.鏈接的錨文本一般都明顯包含了出鏈網(wǎng)頁的信息,因此有助于預(yù)測對應(yīng)網(wǎng)頁的主題相關(guān)度.RContext(p)指的是p對應(yīng)的URL 鏈接在當(dāng)前網(wǎng)頁中的附近文本信息的主題相關(guān)度.一個鏈接附近的信息也能在一定程度上說明該出鏈網(wǎng)頁的主題.以上兩部分基于主題向量和式(1)來計算主題相關(guān)度.RUrl(p)是鏈接p字符串信息的主題相關(guān)度.這是因為域名往往包含有該網(wǎng)頁的主題相關(guān)信息.比如對某頁面提取的URL 鏈接:https://sports.ifeng.com/,其中包括字符串sports,據(jù)此就可以推斷出該網(wǎng)頁主要描述的是“體育”類主題信息.本文在判斷未知鏈接字符串相關(guān)性時,采用了分析主題爬蟲采集的主題頁面URL 字符串,以及人工收集主題頁面URL 鏈接常用字符串的方法,但是最終通過人工確定所采用的URL 字符串集合.因為主題頁面URL 鏈接的主題字符串范圍比較小,通過上述方法基本能夠保證URL 鏈接主題字符串的全面性.

3 實驗測試與結(jié)果分析

3.1 實驗設(shè)置

本實驗在Windows 10 下采用Java 語言實現(xiàn)了一個多線程的主題爬蟲原型系統(tǒng),采用了本文提出的基于動態(tài)隧道技術(shù)的DTH 主題爬行策略,對比策略為基于內(nèi)容分析的爬行策略BFS 和基于鏈接分析的PR 爬行策略.其中,BFS 策略實現(xiàn)過程中主要通過優(yōu)先級隊列實現(xiàn)對URL 鏈接的準確率,即優(yōu)先級高(主題相關(guān)度高)的URL 鏈接的外鏈的優(yōu)先級也要高.PR 值策略因為僅僅采用鏈接重要度來確定優(yōu)先級,因此實現(xiàn)過程中加入了主題相關(guān)度的檢測來避免“主題漂移”問題;此外,PR 值的計算范圍是當(dāng)前待爬取隊列的URL 鏈接.對于當(dāng)前每個爬取到的頁面,分析其包含的所有URL 是否存在于待爬取隊列中,如果存在則增加該URL 的PR 值;如果不存在則賦予其PR 初值.DTH 策略實現(xiàn)過程的特點主要是對不相關(guān)網(wǎng)頁的爬行路徑上“隧道”的深入挖掘和處理.

該爬蟲系統(tǒng)的輸入是特定領(lǐng)域的主題詞庫(采用結(jié)巴分詞所帶的TextRank 模塊進行主題關(guān)鍵詞抽取獲得[10])和一組種子URL 鏈接,輸出是主題相關(guān)的結(jié)果頁面集合.實驗從互聯(lián)網(wǎng)網(wǎng)站(如:新浪、搜狐、鳳凰、體育高校等)中采用上述爬行策略下載“體育”相關(guān)網(wǎng)頁.通過正文提取、中文分詞(采用“結(jié)巴”分詞器進行分詞[10])、除去停用詞等預(yù)處理步驟后構(gòu)建索引數(shù)據(jù).實驗測試中,分別統(tǒng)計采集頁面的數(shù)量在500、1000、1500、…、4000 時的情況.通過構(gòu)建不同網(wǎng)頁數(shù)量的倒排索引數(shù)據(jù),采用“體育”主題查詢詞集合在搜索引擎中進行主題關(guān)鍵詞的查詢.實驗評價指標是查詢的準確率和召回率主題頁面數(shù)量R,定義Precision=M/N,其中,M是搜索到的體育主題相關(guān)文檔數(shù),N是搜索到的全部文檔數(shù);R是系統(tǒng)采集的全部主題相關(guān)的文檔數(shù),表明爬蟲系統(tǒng)采集到主題網(wǎng)頁的能力.

3.2 結(jié)果分析

互聯(lián)網(wǎng)中各個話題相關(guān)的主題團為吸引用戶瀏覽不能獨立存在,必然是通過一定的鏈接相互聯(lián)系,而主題團之間的隧道長度究竟是多長.圖5 給出主題爬蟲原型系統(tǒng)在URL 鏈接主題不相關(guān)條件下(共100 000次)采用動態(tài)隧道技術(shù)DTH 找到新的主題團的爬行深度k的分布.實驗中不相關(guān)方向上的初始化最大爬行深度kdepth的值可以調(diào)整(初始設(shè)為12),實際隧道長度為為找到主題相關(guān)頁面時在該方向上的爬行深度.可以看出,對于找到主題相關(guān)頁面的情況,隧道長度平均值為4.考慮到主題爬蟲系統(tǒng)采集URL 鏈接的隨機性,可以得出大部分主題相關(guān)節(jié)點之間的最短距離不超過6(six degrees of separation).因此,可以初步推測這一現(xiàn)象可能符合Web 中主題團是小世界網(wǎng)絡(luò)(small world)的假設(shè).

主題搜索引擎在采用不同爬行策略時的準確率隨采集頁面的變化趨勢如圖6 所示.實驗結(jié)果可以發(fā)現(xiàn)BFS 策略的準確率高于PR 策略.這是因為基于鏈接分析的PR 爬行策略只是依據(jù)頁面的PR 值來確定待爬行鏈接的優(yōu)先級,而忽視了頁面內(nèi)容的主題相關(guān)情況,隨著爬取深度的增加就容易出現(xiàn)主題漂移的情況,從而導(dǎo)致爬行策略的準確率較低.基于內(nèi)容分析的BFS爬行策略可以比較有效的對頁面主題相關(guān)的程度進行預(yù)測,但是這種方法會忽略頁面之間的鏈接結(jié)構(gòu)信息,對主題團內(nèi)部鏈接的重要性區(qū)分不夠,制約了在給定URL 鏈接采集數(shù)量時策略的準確率.本文所提處的DTH策略能夠通過“隧道”到達新的主題團,進而發(fā)現(xiàn)更多的主題相關(guān)網(wǎng)頁,所以其準確率較前兩種策略要高,尤其是隨著下載網(wǎng)頁個數(shù)的增多這一優(yōu)勢更加明顯.

圖5 主題團之間的隧道長度k 的分布

圖6 主題查詢的準確率的變化趨勢

主題搜索引擎在采用不同爬行策略時的返回頁面數(shù)隨總采集頁面的變化趨勢如圖7 所示.實驗結(jié)果可以發(fā)現(xiàn),BFS 策略返回頁面的數(shù)量略低于PR 策略,這是因為PR 策略發(fā)生主題漂移,卻有可能有利于發(fā)現(xiàn)新的鏈接.DTH 策略在2000 以下時的返回頁面數(shù)量和前兩者差不多,但是在2000 到3000 時就出現(xiàn)返回頁面數(shù)量的上升速度急劇下降,這可能是因為初始化URL 鏈接形成的主題團中的鏈接已經(jīng)采集完畢,而主題團的大小據(jù)統(tǒng)計一般在1500 到2000 之間.在此之后DTH 策略在3000 到4000 時上升的速度又能恢復(fù)正常,這可能因為在3000 到3500 之間時本文提出的爬行策略找到了新的主題團,前兩種策略卻在3000 到4000 之間沒有變化.

圖7 主題頁面數(shù)量的變化趨勢

綜上,本文設(shè)計的主題搜索引擎原型系統(tǒng)的準確率不低于采用BFS 或者PR 爬行策略的主題搜索引擎,而召回率和采用BFS 或者PR 爬行策略的主題搜索引擎相比有了很大的提升.實驗進一步表明,本文提出的基于動態(tài)隧道技術(shù)的爬行策略對改進主題搜索引擎的性能是有效的.

4 結(jié)論

針對現(xiàn)有主題爬行策略存在的主題孤島問題,提出了一種基于動態(tài)隧道技術(shù)的主題爬蟲爬行策略.該策略利用URL 鏈接相關(guān)度預(yù)測方法動態(tài)調(diào)整不相關(guān)鏈接方向上的爬行深度,使得爬蟲能夠進一步發(fā)現(xiàn)較多隱藏的主題相關(guān)鏈接.同時,該策略能有效防止主題爬蟲因采集過多的主題無關(guān)頁面而導(dǎo)致的主題漂移現(xiàn)象,從而可以實現(xiàn)在保持主題語義信息的爬行方向上的動態(tài)隧道控制.面向互聯(lián)網(wǎng)網(wǎng)頁的爬蟲采集實驗結(jié)果表明,基于動態(tài)隧道技術(shù)的主題爬行策略提升了主題搜索引擎的準確率和召回率,能夠比較好的解決現(xiàn)有主題爬蟲存在的主題孤島問題.