基于遺傳算法的聚焦爬蟲搜索策略設(shè)計(jì)與研究

陳 悅, 陳 運(yùn), 楊義先, 胡 迪

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

1 引言

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

2 遺傳算法在聚焦爬蟲中的應(yīng)用

2.1 遺傳算法簡(jiǎn)介

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

2.2 相關(guān)研究工作現(xiàn)狀

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

表1

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

3 基于自適應(yīng)遺傳算法的聚焦爬蟲方案設(shè)計(jì)

3.1 基于自適應(yīng)遺傳算法的聚焦爬蟲設(shè)計(jì)思想

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

3.2 主題相關(guān)度的判斷

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

圖1 基于自適應(yīng)遺傳算法的聚焦爬蟲流程圖

在查詢?cè)~項(xiàng)的權(quán)重計(jì)算中,通常還會(huì)考慮詞項(xiàng)在文檔中出現(xiàn)的頻率,即詞頻 tf,詞項(xiàng)在查詢中出現(xiàn)的頻率qtf,以及文檔的長(zhǎng)度dl等信息對(duì)相關(guān)度的影響[7]。最后采用泊松模型對(duì)文檔相關(guān)度進(jìn)行計(jì)算,計(jì)算公式為：

式中,N為文檔集中文檔的數(shù)量;n為文檔集中包含詞項(xiàng)t的文檔數(shù)目;R為對(duì)于查詢Q相關(guān)的文檔數(shù)量;r為包含詞項(xiàng)t的相關(guān)文檔數(shù)目;tfij為文檔i中詞j的詞頻;qtfj為查詢Q中詞j的詞頻;dli為文檔i中詞的數(shù)量;|Q|為查詢中詞的數(shù)量;Δ為平均文檔長(zhǎng)度;k1,k2,k3,K為調(diào)節(jié)參數(shù)。

3.3 適應(yīng)度函數(shù)的計(jì)算

種群中適應(yīng)度函數(shù)的選取將直接決定優(yōu)于種群平均適應(yīng)度的個(gè)體和數(shù)目。在算法運(yùn)行的初級(jí)階段,群體中可能會(huì)出現(xiàn)一些適應(yīng)度高的個(gè)體,隨著遺傳代數(shù)的增加,這些適應(yīng)度高的個(gè)體及后代將成為群體中的大部分。這樣,使得群體中的新個(gè)體減少,種群的多樣性降低,遺傳算法提前收斂到某個(gè)局部最優(yōu)解,導(dǎo)致“早熟”現(xiàn)象?？紤]網(wǎng)頁的內(nèi)容和鏈接結(jié)構(gòu)兩方面,在自適應(yīng)遺傳算法中選用網(wǎng)頁及其父網(wǎng)頁的相關(guān)度值來作為個(gè)體的適應(yīng)度函數(shù)值。則個(gè)體適應(yīng)度函數(shù)計(jì)算公式為：

其中Fit(linki)是第i個(gè)URL對(duì)應(yīng)的適應(yīng)度值;rpi是linki對(duì)應(yīng)的父網(wǎng)頁的相關(guān)度值;rli是第i個(gè)URL對(duì)應(yīng)相關(guān)度值;k是linki對(duì)應(yīng)的父網(wǎng)頁鏈接出的網(wǎng)頁個(gè)數(shù)。

3.4 初始種子的選取

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

3.5 遺傳算子的設(shè)計(jì)

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

3.5.1 選擇算子的設(shè)計(jì)

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

3.5.2 交叉算子的設(shè)計(jì)

交叉操作在遺傳算法中的作用是產(chǎn)生新的個(gè)體,以便出現(xiàn)新的基因模式。計(jì)算抓取網(wǎng)頁的適應(yīng)度值,按降序排序,對(duì)適應(yīng)度值大于種群平均適應(yīng)度值的URL以較大的Pc進(jìn)行交叉操作,而對(duì)于適應(yīng)度值小于種群平均適應(yīng)度值的URL以較小的Pm進(jìn)行交叉操作。選出前 n×Pc個(gè)URL作為交叉結(jié)果得到集合S1∪S2。交叉概率的調(diào)整通過以下公式實(shí)現(xiàn)：

3.5.3 變異算子的設(shè)計(jì)

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

式中,fmax為群體中最大的適應(yīng)度值;favg為每代群體的平均適應(yīng)度值;f′為要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值;f為要變異個(gè)體的適應(yīng)度值;k1,k2,k3,k4為調(diào)整參數(shù),選(0,1)區(qū)間的值。

4 實(shí)驗(yàn)設(shè)計(jì)及數(shù)據(jù)分析、對(duì)比

4.1 實(shí)驗(yàn)的設(shè)計(jì)

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

4.2 實(shí)驗(yàn)結(jié)果分析、對(duì)比

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

圖2 下載總頁面數(shù)量與相關(guān)頁面數(shù)量的關(guān)系

圖3 平均相關(guān)度與頁面數(shù)量的關(guān)系

5 結(jié)束語

爬蟲以何種搜索策略對(duì)網(wǎng)頁進(jìn)行搜索是聚焦爬蟲搜索相關(guān)網(wǎng)頁數(shù)量以及質(zhì)量的保證。文中采用的自適應(yīng)遺傳算法通過動(dòng)態(tài)調(diào)整遺傳算子,使聚焦爬蟲具有較高的查準(zhǔn)率和查全率。但是,按照主題關(guān)鍵字的方式來搜索網(wǎng)頁,對(duì)于某些主題或者以圖片為主的網(wǎng)頁,并不能保證很好的結(jié)果。因此,結(jié)合領(lǐng)域本體對(duì)網(wǎng)頁內(nèi)容進(jìn)行語義分析以此表示網(wǎng)頁的相關(guān)度,再利用自適應(yīng)遺傳算法對(duì)網(wǎng)頁進(jìn)行搜索是下一步工作。

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

[2]劉世濤.簡(jiǎn)析搜索引擎中網(wǎng)絡(luò)爬蟲的搜索策略[J].阜陽師范學(xué)院學(xué)報(bào),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]劉國(guó)靖,康麗,羅長(zhǎng)壽.基于遺傳箅法的主題爬蟲策略[J].計(jì)算機(jī)應(yīng)用,2007,27(12)：173-174.

[5]曾廣樸,范會(huì)聯(lián).基于遺傳算法的聚焦爬蟲搜索策略[J].計(jì)算機(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信息主題采集技術(shù)研究[J].圖書情報(bào)工作,2005,49(4)：77-80.

[9]王小平,曹立明.遺傳算法：理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社,2002：73-74.