姜 琨,朱 磊,王一川
(西安理工大學 計算機科學與工程學院,西安 710048)
互聯網網頁的聚集特性表明主題頁面容易聚集出現,因主題相關或相近而鏈接在一起的互聯網網頁被稱為主題島或者主題團.主題爬蟲依據主題團的聚集特性對網頁進行采集.然而,并非所有的主題相關網頁都是鏈接在一起的,它們之間可能要跨過幾個主題不相關頁面的鏈接.許多主題島被這些主題無關的頁面鏈接,使主題島之間被分隔,這種現象被稱為主題孤島.如圖1 所示,這些無關頁面的鏈接分布在互聯網上待采集的主題團之間,形成連接主題孤島的一個隧道,這就是Web 頁面的隧道特性[1,2].實際的Web 中存在大量這樣的主題孤島,如果主題爬蟲系統只通過父頁面來預測子頁面的相關度,只提取主題相關頁面中的超鏈接作為種子鏈接,那么就會丟失大量的主題孤島.因為如果子頁面是主題無關的,爬蟲就可能不會訪問該頁面中的超鏈接,這些鏈接可能穿過數次鏈接而連著另一個主題孤島.

圖1 主題孤島問題示意圖
如果為了提高爬蟲采集頁面的準確度而提高爬行策略中的相關度閾值,則會過濾掉大量的隧道,這樣就訪問不到隧道另一端可能存在的主題孤島,導致爬蟲的對主題網頁的召回率較低.為了提高爬蟲一次爬行過程所采集主題相關頁面的數量,往往會降低爬行策略中判斷主題相關與否的相關度閾值.如果這個隧道很長,那么降低相關度閾值去訪問這些主題孤島,又會采集隧道路徑上的大量主題無關頁面,但是有一定概率發現新的主題相關頁面[2].
本文在分析現有主題爬蟲爬行策略特點的基礎上,針對現有主題爬行策略不能很好解決主題孤島問題,提出一種能在爬蟲爬行過程中對不相關頁面中提取的URL 鏈接對應頁面的主題相關度進行預測,并動態調整隧道長度的主題爬行策略模型,從而可以挖掘不相關網頁信息及發現隱藏的主題團相關鏈接.
普通網頁爬蟲一般采用廣度或者深度優先的爬行策略,而主題爬蟲采用的爬行策略按照判斷網頁相關度的不同分為:基于內容分析的爬行策略、基于鏈接分析的爬行策略和基于語境圖的爬行策略等[3].
基于內容分析的主題爬行策略主要是利用頁面或者鏈接的內容特征對頁面與主題的相關程度進行打分評價,進而對待采集網頁和爬行方向進行優化選擇[4].基于內容分析的主題爬行策略主要有:最佳優先搜索(Best First Search,BFS)、Fish Search、Shark Search 等3 種策略[5].
BFS 策略的基本思想是利用主題團特征,通過分析當前已經獲取的頁面,使用一定的打分策略來預測與其連接的頁面的主題相關度,然后使用最好優先的原則每次優先選擇主題相關度最高的頁面作為下一個處理的對象.與主題關系比較密切的頁面,它所包含鏈接的優先級就高,這樣就確定了等待處理的鏈接隊列中鏈接的前后順序.該策略每次添加到爬蟲種子優先級隊列的鏈接的優先級分數是相同的.
在Fish Search 策略中,當通過某一鏈接發現主題相關頁面時,沿著這個方向的爬行深度增加,且后代鏈接的爬行深度保持不變.如果沒有發現主題相關頁面,這個鏈接的爬行深度不變,但是后代鏈接的爬行深度遞減.如果沿著某個方向經過多次采集仍然沒有找到主題相關頁面,那么它的爬行深度會逐漸降低直至為零.Fish Search 策略在主題不相關方向上的采集具有一定的動態特性,但是其主題相關性的判斷僅僅是一種二值分類判斷,不能評價相關程度的高低.
Shark Search 策略是對Fish Search 策略中主題相關度打分策略的改進,其頁面與主題之間的相關程度是一個介于0 到1 之間的連續值,這一改進的優點是可以獲得一個URL 與主題的相關程度.然而,因為Shark Search 和Fish Search 策略在主題不相關頁面方向上采用了降低爬行深度的數據采集,而且對主題不相關頁面采取了和之前頁面相同的分析方法,因而導致其提升召回率的代價是犧牲了爬蟲的準確率.
基于鏈接分析的爬行策略主要是依據網頁之間的引用關系和頁面已知重要度分數來判斷網頁之間的重要程度.基于鏈接分析的爬行策略主要是基于以下兩個條件:(1)如果在網頁A 中包含網頁B 的鏈接,則表明網頁A 對網頁B 重要性的推薦;(2)此時,如果在網頁B 中也同時包含網頁A 的鏈接,則網頁A 和網頁B 一般有共同的主題.比較有代表性的基于鏈接分析的爬行策略如:基于PageRank 的鏈接分析方法等.
PageRank(PR)[6]用于搜索引擎中對查詢結果進行排序,近年來也被用于預測主題爬蟲的鏈接優先級.PR 鏈接分析方法對網頁重要性的打分評價主要依據3 個方面:(1)內鏈越多的網頁越重要,即其他網頁對該網頁的推薦較多;(2)內鏈的網頁重要度越高,被這些高質量網頁的鏈接指向的網頁也越重要;(3)外鏈數越少的網頁相對越重要,即一般重要網頁中的鏈接都是其子鏈接.然而,為了降低動態計算每個待爬取隊列里URL 鏈接的PR 值的代價,實際獲得PR 值都是非精確的.
基于內容分析的爬行策略和基于鏈接分析的爬行策略都屬于立即回報型爬行策略,這類爬行算法通過分析當前的頁面內容或者鏈接信息,目的是要通過這樣的分析來及時指導緊接著的爬行方向.這類主題爬行策略雖然在主題頁面附近的時候能夠表現出較好的性能,但是對那些有潛在主題相關性的鏈接不夠關注甚至過早丟棄,所以在距離主題頁面較遠的地方就有可能會出現“主題漂移”的現象,也難以有效解決主題孤島問題[5].
為了解決有效主題孤島問題,研究人員提出語境圖爬行策略(context graph)[7].這種策略的訓練過程首先要給系統提供一組種子主題頁面,然后利用Google反向鏈接服務尋找到所有擁有指向種子頁面鏈接的頁面作為第一層頁面,而所有擁有指向第一層頁面鏈接的頁面被稱作第二層頁面,依次類推,層數由用戶控制.圖2 展示了一個深度為2 的語境圖.當每一個種子頁面都建立好一個語境圖后,將不同的語境圖的相應各層進行合并,形成一個合并語境圖(merged context graph).然后為合并語境圖的每一層訓練一個貝葉斯分類器.在爬行過程中,分類器被用來確定所要爬行的頁面應該屬于哪一層,從而有效識別主題相關度較低網頁的所屬的層數并計算爬行優先分數.
基于語境圖的爬行策略避免了立即回報型爬行策略只關注能帶來立即效益鏈接的缺點.然而基于語境圖的爬行策略需要為其建立語境圖模型,因此這種方法無疑加重了主題搜索引擎的復雜度.本文在考慮到基于語境圖的爬行策略的在線復雜度和其采用的利用Google 反向鏈接服務的局限性,受基于語境圖的爬行策略中采用的主題層次思想降低隧道長度的啟發,提出一種新的主題爬行策略,其可以通過預測URL 鏈接相關度方法分析隱含的主題層次結構,并動態維護各個主題層次的隧道長度,并使爬行過程具有較低在線復雜度和更好可操作性.

圖2 一個兩層的語境圖模型
基于語境圖的爬行策略為我們提供了一個發現隱藏主題相關鏈接的很好的思路,對于爬蟲發現的主題不相關鏈接也不能輕易拋棄,而是要看它是否屬于主題相關鏈接的前驅鏈接.如果一個爬蟲的目標是獲取與“體育”主題相關的網頁內容,那么一些體育高校的主頁可能是很有價值的,雖然這些頁面本身并不一定直接與“體育”的主題有關系,但是這些主頁可能會鏈接到某些和“體育”相關的新聞頁面,在這些新聞的頁面中則對應的著“體育”主題相關的頁面.如:“北京體育大學”主頁中包含“媒體北體”頁面,然后進一步鏈接到“新華社”等多個“體育”主題相關新聞網站.在這種情況下,體育高校的主頁、學校的新聞頁面或者論壇主頁等與“體育”主題相關或相近的頁面和“體育”主題目標頁面之間就形成了一種既有聯系又有區別的層次結構,而在這種層次結構中就隱含了能夠找到目標主題頁面的爬行路徑.互聯網網頁的主題相關層次示意圖如圖3.
基于語境圖的爬行策略認為主題爬蟲在互聯網上查找某個特定主題的信息時,如果發現某一網頁的主題和給定主題存在某種預定義的相關性時,就可以認為沿著這些在層次結構中的相近頁面必定能找到更多的主題頁面.在爬蟲實現中,通過建立主題相關詞典模型和主題相近詞典模型,對主題不相關鏈接進行進一步語義挖掘,就可能發現更多的主題團,從而在一定程度上解決主題孤島問題.本節采用URL 鏈接相關度預測的方法進行定量的語義挖掘,得出在兩個詞袋(bagof-words)模型下不相關網頁的相似度,結合動態隧道模型來確定爬蟲在不相關網頁上的預測深度.

圖3 互聯網網頁主題相關層次圖
Bergmark 等提出了隧道技術來描述和解決主題孤島問題[8].使用隧道技術的主題爬蟲在碰到主題不相關的網頁時會繼續在該鏈接方向上向前探索k步.這樣主題爬蟲可以從一個主題團游走到另外一個主題團,其中可能經過多層主題相關度較低的頁面.如果在兩個主題團之間的距離不大的前提下,就可能發現互聯網中所有與預定義主題相關的網頁.Bergmark 在對500 000 個網頁的分析表明主題孤島現象的普遍性以及大多數屬于主題孤島的距離在1 和12 之間,平均距離是5.然而,采用隧道技術的主題爬蟲在遇到主題相關度較低的頁面時會擴大探索范圍.也就是說,爬蟲以種子集為圓心,以k為半徑的圓周范圍中探索其它主題團,隨著半徑k的增大,發現其它主題團的概率也在增大,但是需要處理的主題無關網頁也以顯著增加.實際上,當k無限增大時,主題爬蟲對每個預測不相關的網頁都要進行采集,這樣的主題爬蟲就成為了通用爬蟲.因此可以說,這種方法是放松了對主題爬蟲的定義來提高召回率,從而極大地降低了爬蟲的效率[9].
盡管可以采用人工動態調整主題相關閾值的辦法來改變一個鏈接的主題相關情況,但也只有鏈接相關和不相關兩種情況.因而該技術在檢測頁面不相關時,對該方向上的鏈接爬行深度的設定完全沒有考慮到在該方向上爬行每層頁面的動態情況.因此,Bergmark 等提出的隧道技術屬于在主題相關度較低鏈接方向上的靜態探索技術,即在主題不相關時仍然搜索k步,而不去關注這k步的搜索中獲取的鏈接的反饋信息.而Fish Search 策略的動態隧道思想表現在如果出現鏈接主題不相關,則減少該方向上下一個鏈接的隧道長度.如果遇到潛在的URL 鏈接相關度較高,但是頁面主題相關性不夠高的情況,那么原來的方法難以將這一信息及時反饋到主題爬蟲.這一問題很大限制了主題爬蟲發現主題孤島的能力.
互聯網網頁的主題相關層次表明,對于主題不相關網頁還需要進一步分析其是否屬于主題語境圖中的某一層.如果該鏈接屬于語境圖層次結構中的某一層時,沿著這個鏈接方向的爬行深度增加,并且后代鏈接的爬行深度保持不變.如果通過該鏈接不屬于主題層次結構的任何一層,則這個鏈接本身的爬行深度不變,但是后代鏈接的爬行深度才需要遞減.因此,采用動態控制主題不相關方向上的搜索深度,可以發現潛在的優質主題URL 鏈接,從而增加發現主題孤島的可能性.
結合主題相關層次和隧道長度的分析,本文提出的解決主題孤島問題的爬行策略的主要思想為:爬蟲在遇到主題相關頁面時,將該頁面中的所有URL 鏈接和其優先值pv(pv=主題相關度)送到爬蟲的優先級隊列,相關度越高的頁面其URL 外鏈優先級越高,在優先級隊列中也應當被優先采集;此時候選URL 鏈接非常多,爬蟲不可能出現優先隊列空的現象;此時采用廣度優先的方式對相同頁面的相同優先級的頁面進行采集.
主題爬蟲通過式(1)計算得到主題不相關的頁面時(pv=0),并不是停止獲取其頁面中的URL 外鏈,而是繼續在所獲取的URL 外鏈上向前探索k步路徑.對于路徑上的每一層頁面,若在此路徑上通過下一節所闡述的URL 鏈接相關度預測方法發現潛在主題相關頁面(pv=0),爬蟲在這個鏈接方向上的爬行深度保持不變,否則k值遞減.此時采用深度優先的方法判斷獲得的頁面是否仍然是不相關頁面,直到達到某一個主題相關頁面為止(pv=主題相關度).策略流程如圖4所示,工作流程為:對采集到的某網頁去噪之后得到正文內容,之后調用主題詞庫進行相關度計算.如果與主題相關,則將當前爬行深度設為 ∞,表示按照原有方式進行采集.如果與主題不相關,檢查爬行深度值k.如果k=0,表示在此鏈接方向上已經無需再采集,并停止采集.如果k=∞,表示k值未被設置過,并設置k=kdepth,遞減k值之后交由后續模塊處理.如果 0 ≤k<∞,調用下節所述的URL 鏈接相關度預測方法進行頁面相關度計算,在這種情況下,要URL 和主題內容相關,則使當前深度不變,并交后續模塊處理;要是不相關,則使爬行深度遞減,并交后續模塊處理.

圖4 動態隧道技術策略流程圖
這種策略的優點在于,在不相關頁面方向上設定的爬行深度是動態變化的,它把不相關頁面方向上的信息反饋到對隧道爬行深度k的動態控制,因此被稱為動態隧道技術(Dynamic Tunneling Heuristic,DTH).因此,該策略減少了在此方向上的搜索,這樣可以有效的降低了主題爬蟲的在主題無關方向上的爬行范圍;而對于通過URL 鏈接相關度預測后發現可能有潛在主題相關的鏈接,該策略加大了在此方向上的爬行深度,這樣能進一步發現隱藏的主題團.因此,該策略利用URL 鏈接相關度預測和動態隧道控制技術對潛在的主題團進行搜索.
主題爬蟲如果僅僅采用頁面主題相關度計算方法,則隨著爬蟲不斷的爬取新的主題頁面,新的主題關鍵詞會不斷加入主題詞庫并獲得新的權重,從而出現“主題漂移”現象.這主要是因為主題頁面的缺失導致的,此時雖然出現大量主題無關頁面,但是主題爬蟲卻無法發現新的主題團,因此會制約主題爬蟲的準確率.本文方法對主題無關頁面進行URL 鏈接相關度分析,能夠提升主題爬蟲發現新主題頁面的準確率.如果將頁面主題相關度計算和URL 鏈接主題相關度計算結合,則會明顯影響主題爬蟲在主題團內部爬取主題頁面時的性能.
主題爬蟲系統的主題相關度判斷方法:爬蟲系統需要維護一個主題詞庫,其中包括了由大量主題相關的關鍵詞組成的主題向量和每個主題詞出現在網頁中的個數IDF.主題詞典的關鍵詞來源是預先給定的網頁頁面,包括爬蟲系統初始化時給定URL 鏈接種子對應的頁面和主題詞庫更新過程中添加的該領域比較有代表性的網頁.
主題爬蟲系統運行過程中對于主題頁面的選擇規則如下:含有“default”、“index”等信息的URL 鏈接可以初步作為主題頁面;不能作為主題頁面的規則為:入鏈小于一定閾值的頁面;錨文本過長的頁面;錨文本中包含“下一頁”、“更多”等信息的頁面;URL 過長的頁面等.對于利用上述規則選擇的多個主題頁面,再通過TextRank 策略進行主題向量抽取,形成主題詞庫.主題向量T是由基于TextRank 的關鍵詞抽取方法提取的關鍵詞及其權重wi,r組成.TextRank 是一種非監督式的主題抽取策略,不依賴于其他語料,直接從文本中抽取主題關鍵詞;適用于對于少量網頁文本的主題關鍵詞進行分析.主題詞典可以在爬蟲未啟動時進行更新維護,輸入發現的新的網頁正文進行重新計算.
本文在對網頁Pj進行正文提取后首先采用向量空間模型(VSM)來計算網頁內容與主題的相關度,即利用基于TextRank 的抽取得到的主題向量和給定網頁特征向量計算當前頁面的主題相關度,計算公式如下:

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

其中,t fi,j表示關鍵詞ti在給定網頁正文Pj中出現的次數,dfi則 表明當前關鍵詞ti在已經采集的網頁中出現次數,N為已經采集的網頁數量.
在2.2 節的主題爬行模型中,如果當前網頁通過式(1)計算得出是主題不相關的,則進一步對該網頁中的URL 鏈接的主題相關度進行預測.其中需要考慮URL 鏈接的錨文本本身、URL 鏈接的上下文環境以及URL 鏈接字符串的主題相關度等3 個因素.因此,待采集URL 鏈接p對應頁面的主題相關度計算如下:

其中,w1+w2+w3=1.
RArchor(p)指的是URL 鏈接p對應的錨文本的主題相關度.鏈接的錨文本一般都明顯包含了出鏈網頁的信息,因此有助于預測對應網頁的主題相關度.RContext(p)指的是p對應的URL 鏈接在當前網頁中的附近文本信息的主題相關度.一個鏈接附近的信息也能在一定程度上說明該出鏈網頁的主題.以上兩部分基于主題向量和式(1)來計算主題相關度.RUrl(p)是鏈接p字符串信息的主題相關度.這是因為域名往往包含有該網頁的主題相關信息.比如對某頁面提取的URL 鏈接:https://sports.ifeng.com/,其中包括字符串sports,據此就可以推斷出該網頁主要描述的是“體育”類主題信息.本文在判斷未知鏈接字符串相關性時,采用了分析主題爬蟲采集的主題頁面URL 字符串,以及人工收集主題頁面URL 鏈接常用字符串的方法,但是最終通過人工確定所采用的URL 字符串集合.因為主題頁面URL 鏈接的主題字符串范圍比較小,通過上述方法基本能夠保證URL 鏈接主題字符串的全面性.
本實驗在Windows 10 下采用Java 語言實現了一個多線程的主題爬蟲原型系統,采用了本文提出的基于動態隧道技術的DTH 主題爬行策略,對比策略為基于內容分析的爬行策略BFS 和基于鏈接分析的PR 爬行策略.其中,BFS 策略實現過程中主要通過優先級隊列實現對URL 鏈接的準確率,即優先級高(主題相關度高)的URL 鏈接的外鏈的優先級也要高.PR 值策略因為僅僅采用鏈接重要度來確定優先級,因此實現過程中加入了主題相關度的檢測來避免“主題漂移”問題;此外,PR 值的計算范圍是當前待爬取隊列的URL 鏈接.對于當前每個爬取到的頁面,分析其包含的所有URL 是否存在于待爬取隊列中,如果存在則增加該URL 的PR 值;如果不存在則賦予其PR 初值.DTH 策略實現過程的特點主要是對不相關網頁的爬行路徑上“隧道”的深入挖掘和處理.
該爬蟲系統的輸入是特定領域的主題詞庫(采用結巴分詞所帶的TextRank 模塊進行主題關鍵詞抽取獲得[10])和一組種子URL 鏈接,輸出是主題相關的結果頁面集合.實驗從互聯網網站(如:新浪、搜狐、鳳凰、體育高校等)中采用上述爬行策略下載“體育”相關網頁.通過正文提取、中文分詞(采用“結巴”分詞器進行分詞[10])、除去停用詞等預處理步驟后構建索引數據.實驗測試中,分別統計采集頁面的數量在500、1000、1500、…、4000 時的情況.通過構建不同網頁數量的倒排索引數據,采用“體育”主題查詢詞集合在搜索引擎中進行主題關鍵詞的查詢.實驗評價指標是查詢的準確率和召回率主題頁面數量R,定義Precision=M/N,其中,M是搜索到的體育主題相關文檔數,N是搜索到的全部文檔數;R是系統采集的全部主題相關的文檔數,表明爬蟲系統采集到主題網頁的能力.
互聯網中各個話題相關的主題團為吸引用戶瀏覽不能獨立存在,必然是通過一定的鏈接相互聯系,而主題團之間的隧道長度究竟是多長.圖5 給出主題爬蟲原型系統在URL 鏈接主題不相關條件下(共100 000次)采用動態隧道技術DTH 找到新的主題團的爬行深度k的分布.實驗中不相關方向上的初始化最大爬行深度kdepth的值可以調整(初始設為12),實際隧道長度為為找到主題相關頁面時在該方向上的爬行深度.可以看出,對于找到主題相關頁面的情況,隧道長度平均值為4.考慮到主題爬蟲系統采集URL 鏈接的隨機性,可以得出大部分主題相關節點之間的最短距離不超過6(six degrees of separation).因此,可以初步推測這一現象可能符合Web 中主題團是小世界網絡(small world)的假設.
主題搜索引擎在采用不同爬行策略時的準確率隨采集頁面的變化趨勢如圖6 所示.實驗結果可以發現BFS 策略的準確率高于PR 策略.這是因為基于鏈接分析的PR 爬行策略只是依據頁面的PR 值來確定待爬行鏈接的優先級,而忽視了頁面內容的主題相關情況,隨著爬取深度的增加就容易出現主題漂移的情況,從而導致爬行策略的準確率較低.基于內容分析的BFS爬行策略可以比較有效的對頁面主題相關的程度進行預測,但是這種方法會忽略頁面之間的鏈接結構信息,對主題團內部鏈接的重要性區分不夠,制約了在給定URL 鏈接采集數量時策略的準確率.本文所提處的DTH策略能夠通過“隧道”到達新的主題團,進而發現更多的主題相關網頁,所以其準確率較前兩種策略要高,尤其是隨著下載網頁個數的增多這一優勢更加明顯.

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

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

圖7 主題頁面數量的變化趨勢
綜上,本文設計的主題搜索引擎原型系統的準確率不低于采用BFS 或者PR 爬行策略的主題搜索引擎,而召回率和采用BFS 或者PR 爬行策略的主題搜索引擎相比有了很大的提升.實驗進一步表明,本文提出的基于動態隧道技術的爬行策略對改進主題搜索引擎的性能是有效的.
針對現有主題爬行策略存在的主題孤島問題,提出了一種基于動態隧道技術的主題爬蟲爬行策略.該策略利用URL 鏈接相關度預測方法動態調整不相關鏈接方向上的爬行深度,使得爬蟲能夠進一步發現較多隱藏的主題相關鏈接.同時,該策略能有效防止主題爬蟲因采集過多的主題無關頁面而導致的主題漂移現象,從而可以實現在保持主題語義信息的爬行方向上的動態隧道控制.面向互聯網網頁的爬蟲采集實驗結果表明,基于動態隧道技術的主題爬行策略提升了主題搜索引擎的準確率和召回率,能夠比較好的解決現有主題爬蟲存在的主題孤島問題.