基于遺傳算法的聚焦爬蟲搜索策略設計與研究

陳 悅, 陳 運, 楊義先, 胡 迪

(1.成都信息工程學院信息安全研究所,四川成都610225;2.北京郵電大學信息安全中心,北京100083)

1 引言

互聯網上的網頁數以億計,并以指數級的速度增長。要從上億的網頁中快速、準確地找出想要的網頁,對于通用搜索引擎來說是一項困難的任務。聚焦爬蟲是專為查詢某一領域或主題信息而出現的網頁抓取工具。與通用網絡爬蟲不同,聚焦網絡爬蟲旨在抓取與某一特定主題內容相關的網頁。因此,在搜索過程中無須追求最大覆蓋率,對整個網絡進行遍歷,只需選擇與主題相關的網頁進行訪問。所以,對于聚焦爬蟲首要解決的問題是如何判斷一個網頁是否與主題相關,以及根據主題的相關度用怎樣的搜索策略來爬取盡可能多的相關網頁,并且保證較高的查全率和查準率。目前主要用的聚焦爬蟲搜索策略有[1]：基于內容評價的搜索策略和基于鏈接結構評價的搜索策略。以上兩種搜索策略雖各有優點,但也存在不少局限,一種好的搜索策略需要在有限的時間內,以較少的網絡資源、存儲資源和計算資源來獲取較多的與主題相關的頁面。所以,搜索策略應該在提高鏈接價值預測的準確性、降低計算的時空復雜性,以及增加網絡爬蟲的自適應性等方面有所發展,有所突破[2]。

2 遺傳算法在聚焦爬蟲中的應用

2.1 遺傳算法簡介

傳統的遺傳算法采用的都是固定的參數,由于遺傳算法其本質是一種動態自適應的進化過程,固定的參數設置容易導致進化過程中最優個體的概率遺失而使算法收斂于局部最優,產生“早熟”現象。自適應遺傳算法(Adaptive GA,AGA)中的交叉概率Pc和變異概率Pm會隨著個體的適應度值自動的改變。當種群中各個體適應度值達到一致或趨于局部最優時,使Pc和Pm增加,而當種群的適應度值比較分散時,使Pc和Pm減少。同時,對于適應度值高于種群平均適應度值的個體,應該給予保護進入下一代繼續繁殖,而對低于平均適應度值的個體應將其淘汰。因此,自適應遺傳算法能夠在保持種群多樣性的同時,保證遺傳算法的收斂性。

2.2 相關研究工作現狀

遺傳算法從問題的一組解開始搜索,而非單個解開始,搜索方向有多個,而非單個。較傳統的單點、單方向搜索算法,遺傳算法具有良好的并行性,而且搜索的覆蓋面大,減少了陷入局部最優的風險,利于全局擇優。因此,將遺傳算法的思想應用于聚焦爬蟲的搜索策略中吸引了不少國內外學者。文獻[3]設計的客戶端智能搜索引擎,在搜索過程中就利用了遺傳算法的變異操作,將相關度高的網頁作為新個體加入下一代群體,在一定程度上擴大了網頁的搜索范圍。文獻[4]通過改進遺傳算子提出的一種新的主題爬蟲搜索策略,在合理選擇種子集合時,不僅能擴大搜索范圍,而且在抓取的網頁中主題相關的網頁數量多。文獻[5]提出的一種結合內容評價和鏈接結構搜索策略的優點并利用小生境遺傳算法進行全局尋優的搜索策略。通過改進遺傳算子和小生境遺傳算法,采用概率變遷規則和小生境淘汰運算引導搜索方向,在抓取主題相關網頁時具有更高的查準率和查全率。以上搜索策略的特點及不足如表1所示。

表1

從上面的分析來看,在聚焦爬蟲的搜索過程中引入遺傳算法,利用它簡單、高效、并行和全局尋優的特點,指導聚焦爬蟲的搜索方向。將待搜索網頁的URL作為遺傳個體,通過交叉、變異、選擇操作,采用概率的變遷規則,用適應度函數值來評估個體,然后將其作為新個體加入種群中,進入下一代遺傳進化。采用的自適應遺傳算法,通過Pc和Pm的自適應調整,對遺傳算子進行了新的定義,具有更好的自適應性。

3 基于自適應遺傳算法的聚焦爬蟲方案設計

3.1 基于自適應遺傳算法的聚焦爬蟲設計思想

目前網絡上的信息一般按照某個主題歸為一類,這樣,如一網頁信息與某一主題相關,那么它所在的網站或者鏈接的網站也可能包含與該主題相關的信息。結合網頁內容評價、Web鏈接結構以及自適應遺傳算法的優點,設計出一種在保持種群多樣性的同時通過自動調整Pc和Pm來保證遺傳算法收斂性的聚焦爬蟲。其基本思想是：通過自適應選擇操作,選出適應度高的個體(URL)作為下一代種子,減少新種子的數量,縮小搜索范圍;通過對優勢個體采用較小的變異概率,對劣勢個體采用較大的變異概率這樣的變異操作來保證有足夠新個體結構的同時遺傳算法不變成隨機搜索算法;通過在進化的不同時期采用不同的交叉概率對父代個體進行基因重組,來保證新個體產生的同時不破壞遺傳算法的遺傳模式。基于自適應遺傳算法的聚焦爬蟲以普通聚焦爬蟲作為原型,在爬蟲的搜索策略中運用自適應遺傳算法,更好的指導爬蟲的搜索路徑。該爬蟲設計的流程如圖1所示。

3.2 主題相關度的判斷

聚焦爬蟲在其爬取網頁的過程中需要根據一定的網頁分析算法過濾掉與主題無關的鏈接,為了確定一個網頁是否與主題相關,需要計算所查網頁與搜索請求的相關度。采用概率檢索模型[6]通過計算文檔與查詢相關的概率來表示網頁的相關度。設有3個隨機變量R、Q、D,相關度R,記我們估計特定文檔D與查詢Q相關的可能性為P(R|Q,D);查詢 Q,它包含 s個詞項(q1,q2,…,qs),其中 qi表示第i個查詢詞項;文檔D,它包含 t個詞項(w1,w2,…,wt),其中 wj表示第j個詞項導致文檔相關的估計概率,可以理解為它對估計整篇文檔相關所作的“貢獻”。在實際操作中假定詞項在相關文檔中的分布是相互獨立的并且在非相關文檔中的分布也是相互獨立的,而相關的可能性是基于文檔中出現的查詢詞項和未出現的查詢詞項。那么,每個詞項的權重為：

圖1 基于自適應遺傳算法的聚焦爬蟲流程圖

在查詢詞項的權重計算中,通常還會考慮詞項在文檔中出現的頻率,即詞頻 tf,詞項在查詢中出現的頻率qtf,以及文檔的長度dl等信息對相關度的影響[7]。最后采用泊松模型對文檔相關度進行計算,計算公式為：

式中,N為文檔集中文檔的數量;n為文檔集中包含詞項t的文檔數目;R為對于查詢Q相關的文檔數量;r為包含詞項t的相關文檔數目;tfij為文檔i中詞j的詞頻;qtfj為查詢Q中詞j的詞頻;dli為文檔i中詞的數量;|Q|為查詢中詞的數量;Δ為平均文檔長度;k1,k2,k3,K為調節參數。

3.3 適應度函數的計算

種群中適應度函數的選取將直接決定優于種群平均適應度的個體和數目。在算法運行的初級階段,群體中可能會出現一些適應度高的個體,隨著遺傳代數的增加,這些適應度高的個體及后代將成為群體中的大部分。這樣,使得群體中的新個體減少,種群的多樣性降低,遺傳算法提前收斂到某個局部最優解,導致“早熟”現象。考慮網頁的內容和鏈接結構兩方面,在自適應遺傳算法中選用網頁及其父網頁的相關度值來作為個體的適應度函數值。則個體適應度函數計算公式為：

其中Fit(linki)是第i個URL對應的適應度值;rpi是linki對應的父網頁的相關度值;rli是第i個URL對應相關度值;k是linki對應的父網頁鏈接出的網頁個數。

3.4 初始種子的選取

種子頁面的選擇將直接影響信息采集的質量以及采集工作的效率,為此,要求種子頁面具有較高的主題相關度以及主題鏈接的中心度[8]。具體做法是：(1)用分類詞庫里面的主題詞作為關鍵字在百度、谷歌等網站搜索獲得可能相關的URL,取各自的Top100URL。(2)從排名網站Alexa、Ranking等獲取相應主題的網頁,取各自的Top100URL。(3)將通過以上方式獲取到的URL匯總,從中選出n個與主題相關的URL作為種子頁面。

3.5 遺傳算子的設計

遺傳算法的參數中交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關鍵所在,直接影響算法的收斂性[9]。傳統遺傳算法的交叉概率和選擇概率的參數是事先確定的,而這兩個參數的選擇對于優勢個體的產生影響較大。因此,選擇不當,容易出現局部最優解,產生“早熟”現象。自適應遺傳算法中的Pc和Pm是隨適應度值動態改變的。所以,根據具體的優化問題——聚焦爬蟲的路徑選擇問題,重新設計了遺傳算子,以便使聚焦爬蟲爬取到更多的主題相關度高的網頁。

3.5.1 選擇算子的設計

選擇操作模擬生物的“優勝劣汰”機制。在遺傳算法中,以較大的概率將相關度高的URL作為下一代個體的種子頁面,繼續繁殖,而相關度低的URL則可能面臨被淘汰的危險。對于集合S進行以下處理：(1)根據計算出的網頁相關度值,選擇相關度高于閾值r0的網頁,淘汰低于閾值r0的網頁;(2)根據網頁的適應度值,分別對適應度值高于和低于平均適應度值的網頁以不同的 Pc和Pm進行交叉和變異操作。(3)去除交叉、變異后的種群集合S中重復、無效以及已經查找過的URL。

3.5.2 交叉算子的設計

交叉操作在遺傳算法中的作用是產生新的個體,以便出現新的基因模式。計算抓取網頁的適應度值,按降序排序,對適應度值大于種群平均適應度值的URL以較大的Pc進行交叉操作,而對于適應度值小于種群平均適應度值的URL以較小的Pm進行交叉操作。選出前 n×Pc個URL作為交叉結果得到集合S1∪S2。交叉概率的調整通過以下公式實現：

3.5.3 變異算子的設計

選擇算子在種群中變化,選擇的結果仍在種群中;交叉算子在包含種群的最小模式中變化,交叉的結果仍在這個模式中。因此,選擇和交叉僅在一個“子空間”中搜索,而變異操作是在不斷改變子空間,從而擴大了搜索范圍。因此,在自適應遺傳算法中,采用對適應度值大于種群平均適應度值的URL以較小Pm進行變異操作,對適應度值小于種群平均適應度值的URL以較大的Pm進行變異操作。最后選出m×Pm個URL作為變異結果得到集合S3∪S4。變異概率的調整通過以下公式實現：

式中,fmax為群體中最大的適應度值;favg為每代群體的平均適應度值;f′為要交叉的兩個個體中較大的適應度值;f為要變異個體的適應度值;k1,k2,k3,k4為調整參數,選(0,1)區間的值。

4 實驗設計及數據分析、對比

4.1 實驗的設計

為了測試基于自適應遺傳算法的聚焦爬蟲的性能,將該爬蟲爬取主題相關網頁的結果與廣度優先搜索策略(BFS)和最佳搜索策略(OPS)以及文獻[4]的結果比較。試驗中,初始種子URL設為30個,相關度閾值設為 r0=0.02。以“賭博”為主題,分別在谷歌和百度搜索相關網頁,記錄4種搜索策略抓取的網頁。雖然抓取是以“賭博”為主題的,但抓取到的網頁是否為賭博網站,并不能肯定,因此,對抓取到的網頁用McAfee,Blue coat及Webfilter分類,分類結果以兩個分類器相同的為準,3個分類器都不相同的或者未分類的網頁人工檢查,根據分類結果計算抓取網頁的準確率。

4.2 實驗結果分析、對比

實驗記錄了用4種搜索策略在谷歌、百度抓取到的相關網頁數量,如圖2所示。從圖中可以看出,在搜索的開始階段,AGA抓取到的相關網頁數量不及OPS以及文獻[4]的GA,但隨著算法的推進,AGA抓取到的相關網頁明顯高于OPS以及BFS,略高于GA。說明自適應遺傳算法通過遺傳算子的調整,在聚集爬蟲爬取網頁的過程中具有更大的覆蓋率,能夠抓取到更多的相關網頁,準確率較高。而在抓取到網頁的相關度上,對抓取到的網頁用分類器分類后,從圖3可以看出,BFS和OPS抓取到的網頁相關度隨著搜索的深入開始降低,而AGA會在持續一段時間后開始降低,說明AGA能夠抓取到更多的主題相關度高的網頁。

圖2 下載總頁面數量與相關頁面數量的關系

圖3 平均相關度與頁面數量的關系

5 結束語

爬蟲以何種搜索策略對網頁進行搜索是聚焦爬蟲搜索相關網頁數量以及質量的保證。文中采用的自適應遺傳算法通過動態調整遺傳算子,使聚焦爬蟲具有較高的查準率和查全率。但是,按照主題關鍵字的方式來搜索網頁,對于某些主題或者以圖片為主的網頁,并不能保證很好的結果。因此,結合領域本體對網頁內容進行語義分析以此表示網頁的相關度,再利用自適應遺傳算法對網頁進行搜索是下一步工作。

[1]歐陽柳波,李學勇.專業搜索引擎搜索策略綜述[J].計算機工程,2004,8(7)：32-33.

[2]劉世濤.簡析搜索引擎中網絡爬蟲的搜索策略[J].阜陽師范學院學報,2006,23(9)：59-62.

[3]Chengh.Chungym,Ramseym.An intelligent personal spider(agent)for dynamic Internet/Intranet marching[J].Decision Support Systems,1998,23(1)：41-58.

[4]劉國靖,康麗,羅長壽.基于遺傳箅法的主題爬蟲策略[J].計算機應用,2007,27(12)：173-174.

[5]曾廣樸,范會聯.基于遺傳算法的聚焦爬蟲搜索策略[J].計算機工程,2010,36(6)：167-169.

[6]Fuhr,Norbert.Probabilistic models in information retrieval[J].The Computer Journal,1992,35(3)：243-255.

[7]Robertson S,Walker S.Some simple effective approximations to the 2-Poisson model for probabilistic weighted retrieval[C].In Proceedings of the Seventeenth Annual International ACM SIGIRConference on Research and Development in Information Retrieval,1994,232-241.

[8]李春旺.Web信息主題采集技術研究[J].圖書情報工作,2005,49(4)：77-80.

[9]王小平,曹立明.遺傳算法：理論、應用與軟件實現[M].西安：西安交通大學出版社,2002：73-74.