姜 琨,朱 磊,王一川

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

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

圖1 主題孤島問題示意圖

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

本文在分析現(xiàn)有主題爬蟲爬行策略特點(diǎn)的基礎(chǔ)上,針對(duì)現(xiàn)有主題爬行策略不能很好解決主題孤島問題,提出一種能在爬蟲爬行過程中對(duì)不相關(guān)頁面中提取的URL 鏈接對(duì)應(yīng)頁面的主題相關(guān)度進(jìn)行預(yù)測(cè),并動(dòng)態(tài)調(diào)整隧道長(zhǎng)度的主題爬行策略模型,從而可以挖掘不相關(guān)網(wǎng)頁信息及發(fā)現(xiàn)隱藏的主題團(tuá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)容特征對(duì)頁面與主題的相關(guān)程度進(jìn)行打分評(píng)價(jià),進(jìn)而對(duì)待采集網(wǎng)頁和爬行方向進(jìn)行優(yōu)化選擇[4].基于內(nèi)容分析的主題爬行策略主要有:最佳優(yōu)先搜索(Best First Search,BFS)、Fish Search、Shark Search 等3 種策略[5].

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

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

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

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

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

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

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

1.3 基于語境圖的爬行策略

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

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

圖2 一個(gè)兩層的語境圖模型

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

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

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

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

2.1 動(dòng)態(tài)隧道長(zhǎng)度

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

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

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

2.2 主題爬行模型

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

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

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

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

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

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

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

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

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

其中,wi,j表示特征向量在給定網(wǎng)頁文本中的權(quán)重值,wi,r表示特征向量i在主題向量中的權(quán)值,T代表主題向量,Sim(Pj,T)表 示文本Pj與給定主題向量的相關(guān)度.計(jì)算文本權(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)計(jì)算得出是主題不相關(guān)的,則進(jìn)一步對(duì)該網(wǎng)頁中的URL 鏈接的主題相關(guān)度進(jìn)行預(yù)測(cè).其中需要考慮URL 鏈接的錨文本本身、URL 鏈接的上下文環(huán)境以及URL 鏈接字符串的主題相關(guān)度等3 個(gè)因素.因此,待采集URL 鏈接p對(duì)應(yīng)頁面的主題相關(guān)度計(jì)算如下:

其中,w1+w2+w3=1.

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

3 實(shí)驗(yàn)測(cè)試與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

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

該爬蟲系統(tǒng)的輸入是特定領(lǐng)域的主題詞庫(采用結(jié)巴分詞所帶的TextRank 模塊進(jìn)行主題關(guān)鍵詞抽取獲得[10])和一組種子URL 鏈接,輸出是主題相關(guān)的結(jié)果頁面集合.實(shí)驗(yàn)從互聯(lián)網(wǎng)網(wǎng)站(如:新浪、搜狐、鳳凰、體育高校等)中采用上述爬行策略下載“體育”相關(guān)網(wǎng)頁.通過正文提取、中文分詞(采用“結(jié)巴”分詞器進(jìn)行分詞[10])、除去停用詞等預(yù)處理步驟后構(gòu)建索引數(shù)據(jù).實(shí)驗(yàn)測(cè)試中,分別統(tǒng)計(jì)采集頁面的數(shù)量在500、1000、1500、…、4000 時(shí)的情況.通過構(gòu)建不同網(wǎng)頁數(shù)量的倒排索引數(shù)據(jù),采用“體育”主題查詢?cè)~集合在搜索引擎中進(jìn)行主題關(guān)鍵詞的查詢.實(shí)驗(yàn)評(píng)價(jià)指標(biāo)是查詢的準(zhǔ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)中各個(gè)話題相關(guān)的主題團(tuán)為吸引用戶瀏覽不能獨(dú)立存在,必然是通過一定的鏈接相互聯(lián)系,而主題團(tuán)之間的隧道長(zhǎng)度究竟是多長(zhǎng).圖5 給出主題爬蟲原型系統(tǒng)在URL 鏈接主題不相關(guān)條件下(共100 000次)采用動(dòng)態(tài)隧道技術(shù)DTH 找到新的主題團(tuán)的爬行深度k的分布.實(shí)驗(yàn)中不相關(guān)方向上的初始化最大爬行深度kdepth的值可以調(diào)整(初始設(shè)為12),實(shí)際隧道長(zhǎng)度為為找到主題相關(guān)頁面時(shí)在該方向上的爬行深度.可以看出,對(duì)于找到主題相關(guān)頁面的情況,隧道長(zhǎng)度平均值為4.考慮到主題爬蟲系統(tǒng)采集URL 鏈接的隨機(jī)性,可以得出大部分主題相關(guān)節(jié)點(diǎn)之間的最短距離不超過6(six degrees of separation).因此,可以初步推測(cè)這一現(xiàn)象可能符合Web 中主題團(tuán)是小世界網(wǎng)絡(luò)(small world)的假設(shè).

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

圖5 主題團(tuán)之間的隧道長(zhǎng)度k 的分布

圖6 主題查詢的準(zhǔn)確率的變化趨勢(shì)

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

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

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

4 結(jié)論

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