劉麗杰，許楠，李盼池

（1.黑龍江八一農(nóng)墾大學(xué)信息技術(shù)學(xué)院，大慶163319；2.東北石油大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院）

隨著網(wǎng)絡(luò)信息資源的急劇增長(zhǎng)，越來(lái)越多的信息涌到人們的面前，而同用搜索引擎已經(jīng)不能滿足人們對(duì)個(gè)性化信息檢索服務(wù)日益增長(zhǎng)的需要。針對(duì)這種狀況，近年來(lái)，人們提出了對(duì)某一特定領(lǐng)域的主題型搜索引擎，它可以提供分類更細(xì)致精確、數(shù)據(jù)更全面深入、更新更及時(shí)的因特網(wǎng)搜索服務(wù)[1]，同時(shí)在指定的領(lǐng)域取得比綜合型搜索引擎更滿意的結(jié)果。而聚焦爬蟲是專為查詢某一領(lǐng)域或主題信息而出現(xiàn)的網(wǎng)頁(yè)抓取工具，與通用網(wǎng)絡(luò)爬蟲不同，聚焦爬蟲旨在抓取與某一特定主題內(nèi)容相關(guān)的網(wǎng)頁(yè)。因此，在搜索過(guò)程中無(wú)須追求最大覆蓋率，對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行遍歷，只需選擇與主題相關(guān)的網(wǎng)頁(yè)進(jìn)行訪問(wèn)。目前主要使用的聚焦爬蟲搜索策略[2]有：基于內(nèi)容評(píng)價(jià)的搜索策略和基于鏈接結(jié)構(gòu)評(píng)價(jià)的搜索策略[3]。

基于內(nèi)容評(píng)價(jià)的策略以De Bra、Herseovici等人的研究Fish及Shark[4]為代表，最近的研究表明，這類網(wǎng)絡(luò)蜘蛛在距離相關(guān)頁(yè)面集較近的地方搜索時(shí)表現(xiàn)出良好的性能。但由于頁(yè)面中的文本信息缺乏“全局性”，很難反映Web的整體情況，而且它忽略了鏈接結(jié)構(gòu)信息，在預(yù)測(cè)鏈接價(jià)值的準(zhǔn)確性方面存在不足。而以PageRank為代表的基于Web鏈接結(jié)構(gòu)的搜索策略，則通過(guò)分析Web頁(yè)面之間的相互引用來(lái)決定網(wǎng)頁(yè)的重要性，從而決定鏈接的訪問(wèn)順序，這類搜索策略的優(yōu)點(diǎn)是考慮了鏈接的結(jié)構(gòu)特征，但它忽略了頁(yè)面與主題的相關(guān)性，在某些情況下，會(huì)出現(xiàn)搜索偏離主題的“主題漂移”問(wèn)題，同時(shí)它的計(jì)算量也相當(dāng)大，嚴(yán)重影響了爬蟲的爬行速度，因此不適合發(fā)現(xiàn)主題資源。

1 相關(guān)知識(shí)與原理

1.1 聚焦爬蟲

聚焦爬蟲（Focusing Crawler）是一個(gè)自動(dòng)下載網(wǎng)頁(yè)的程序，它根據(jù)既定的抓取目標(biāo)，有選擇地訪問(wèn)萬(wàn)維網(wǎng)上的網(wǎng)頁(yè)與相關(guān)的鏈接，獲取所需要的信息。與通用爬蟲（general purpose web crawler）不同，聚焦爬蟲首先需要判斷當(dāng)前所抓取的網(wǎng)頁(yè)是否與預(yù)先設(shè)定的主題相關(guān)，然后再使用某種搜索策略來(lái)抓取網(wǎng)頁(yè)，在采用搜索策略時(shí)往往不是深度優(yōu)先或廣度優(yōu)先搜索策略，而是按照相似度的大小來(lái)抓取網(wǎng)頁(yè)。也就是說(shuō)，聚焦爬蟲并不追求大的覆蓋，而將目標(biāo)定為抓取與某一特定主題內(nèi)容相關(guān)的網(wǎng)頁(yè)，為面向主題的用戶查詢準(zhǔn)備數(shù)據(jù)資源。因此，聚焦爬蟲比通用爬蟲極大地節(jié)省了硬件和網(wǎng)絡(luò)資源，保存的頁(yè)面也由于數(shù)量少而更新快，還可以很好地滿足一些特定人群對(duì)一些特定領(lǐng)域的需求。

1.2 PageRank算法

使用PageRank算法來(lái)計(jì)算基于鏈接結(jié)構(gòu)的網(wǎng)頁(yè)的重要度，該算法最初用于Google搜索引擎信息檢索中對(duì)查詢結(jié)果的排序過(guò)程，近年來(lái)被應(yīng)用于網(wǎng)絡(luò)爬蟲對(duì)鏈接重要性的評(píng)價(jià)。標(biāo)準(zhǔn)的PageRank算法的原理為：如果一個(gè)頁(yè)面被多次引用，或者它沒(méi)有被多次引用但被權(quán)威的網(wǎng)頁(yè)引用，那么這個(gè)頁(yè)面可能是重要頁(yè)面。在標(biāo)準(zhǔn)的PageRank算法中，一個(gè)頁(yè)面的重要性被平均地傳遞到了此頁(yè)面中每一個(gè)鏈接指向的頁(yè)面。PageRank算法用公式（1）來(lái)實(shí)現(xiàn)為：

其中，Ti表示鏈接到P的網(wǎng)頁(yè)；C（Ti）則表示網(wǎng)頁(yè)Ti向外的鏈接數(shù)量；PR（P）表示在運(yùn)算中網(wǎng)頁(yè)P(yáng)的PageRank值；d為值在0～1之間的衰退因子，它的引人是為了減小Ti對(duì)頁(yè)面P的影響，一般取0.85；1～d是為了彌補(bǔ)阻尼掉的權(quán)值為防止網(wǎng)頁(yè)無(wú)外部鏈接時(shí)初始PR值為0；PR（Ti）/C（Ti）為網(wǎng)頁(yè)Ti的權(quán)值PR（Ti）被平均分成C（Ti）份后對(duì)網(wǎng)頁(yè)P(yáng)的投票。

基于PageRank算法的網(wǎng)絡(luò)爬蟲在搜索過(guò)程中，通過(guò)計(jì)算每個(gè)已訪問(wèn)頁(yè)面的PageRank值來(lái)確定頁(yè)面的價(jià)值，并優(yōu)先選擇PageRank值大的頁(yè)面中的鏈接進(jìn)行訪問(wèn)。它主要是通過(guò)網(wǎng)頁(yè)的鏈接信息來(lái)判斷的。

1.3 向量空間模型算法

基于內(nèi)容評(píng)價(jià)的搜索策略，主要是根據(jù)主題（如關(guān)鍵詞、主題相關(guān)文檔）與鏈接文本的相似度來(lái)評(píng)價(jià)鏈接價(jià)值的高低，并以此決定其搜索策略。采用向量[5]空間模型（Vector Space Model，VSM）來(lái)計(jì)算主題相關(guān)度的大小。它的基本思想是假設(shè)網(wǎng)頁(yè)文檔是由一組詞（T1，T2，…，Tn）構(gòu)成，其中根據(jù)每一個(gè)詞Ti在文檔中的重要程度來(lái)將其賦予一定的權(quán)重值Wi，權(quán)重越大，則表示該詞對(duì)于該文檔來(lái)說(shuō)越重要，同時(shí)將（T1，T2，…，Tn）看作為一個(gè)n維的坐標(biāo)系，而（W1，W2，…，Wn）就是對(duì)應(yīng)的坐標(biāo)值，因此對(duì)于每一個(gè)網(wǎng)頁(yè)文檔來(lái)說(shuō)都可看作一個(gè)點(diǎn)，它是在向量空間中由一組詞條的矢量構(gòu)成的。

在向量空間模型中，文檔的相似度是用主題特征和網(wǎng)頁(yè)文檔這兩個(gè)向量之間的夾角余弦值來(lái)表示，相似度的值越大則該文檔越符合相應(yīng)主題，并且計(jì)算出的相似度的值要在0到1之間，則其計(jì)算公式如（2）所示：

其中T表示為主題向量，D表示文檔向量，SP表示文檔向量與主題向量的相關(guān)度值。

2 基于自適應(yīng)免疫進(jìn)化算法的聚焦爬蟲設(shè)計(jì)

2.1 設(shè)計(jì)思想

自適應(yīng)免疫進(jìn)化算法 （Adaptive immune evolutionary algorithm）是通過(guò)一系列的操作來(lái)模擬免疫系統(tǒng)的學(xué)習(xí)過(guò)程并對(duì)其進(jìn)行優(yōu)化，這一系列的操作包括選擇、擴(kuò)展、突變和替換。自適應(yīng)免疫進(jìn)化算法在全局范圍內(nèi)搜索評(píng)價(jià)值較高區(qū)域的同時(shí)，也在該區(qū)域局部搜索最優(yōu)解，實(shí)現(xiàn)了從全局到局部的兩層領(lǐng)域搜索機(jī)制，從而使算法具有較強(qiáng)的全局和局部搜索能力。

算法中自適應(yīng)表示根據(jù)個(gè)體的主題相關(guān)度大小自動(dòng)調(diào)節(jié)算法參數(shù)，其調(diào)整過(guò)程為：當(dāng)搜索算法陷入到局部最優(yōu)時(shí)，搜索區(qū)域的多樣性小，此時(shí)希望擴(kuò)大選擇比例，使得個(gè)體擴(kuò)展和突變的空間變得更大、更廣，這樣群體的多樣性就會(huì)增加，可以避免算法陷入局部最優(yōu)中[6]。當(dāng)算法處于發(fā)散狀態(tài)時(shí)，搜索空間和區(qū)域的的多樣性就會(huì)變大，此時(shí)希望算法中的選擇比例小一些。如果想提高搜索算法的尋優(yōu)能力，同時(shí)又想保證群體的進(jìn)化，則需要適當(dāng)調(diào)節(jié)算法中的各參數(shù)。提出了算法中各參數(shù)的調(diào)節(jié)方法，是根據(jù)主題的相關(guān)度進(jìn)行自適應(yīng)調(diào)節(jié)的，其方法如下：

其中（a，b）為選擇比率取值范圍，是預(yù)先根據(jù)實(shí)際情況已經(jīng)選取的，假設(shè)有100個(gè)URL地址，我想選擇其中的10%到30%進(jìn)行擴(kuò)展等操作，則此時(shí)a取值應(yīng)為0.1，而b取值為0.3；x是某個(gè)網(wǎng)頁(yè)URL的相關(guān)度值，xmax和xmin則分別表示計(jì)算出來(lái)的所有相關(guān)度中的最大值和最小值；X只是作為一個(gè)中間變量出現(xiàn)，是為了求得α值的取值范圍在（a，b）在之間的同時(shí)再滿足自適應(yīng)調(diào)節(jié)功能，α取值到底取多少根據(jù)公式（3）和公式（4）可以計(jì)算得出，即如果某個(gè)網(wǎng)頁(yè)鏈接URL的相關(guān)度值x較大時(shí)則α的取值就會(huì)較大，爬蟲就會(huì)在較大的范圍內(nèi)進(jìn)行選擇，否則若x值較小則計(jì)算得出的α值就會(huì)較小，相應(yīng)的爬蟲爬行的范圍也會(huì)縮小。

2.2 網(wǎng)頁(yè)主題相關(guān)度計(jì)算

PageRank算法主要是通過(guò)網(wǎng)頁(yè)之間的鏈接關(guān)系來(lái)確定網(wǎng)頁(yè)的重要程度，也就是說(shuō)，它的思想就是主要依賴于網(wǎng)頁(yè)之間的鏈接關(guān)系，然而它的最大缺點(diǎn)就是在搜索時(shí)會(huì)出現(xiàn)“主題漂移”現(xiàn)象，因?yàn)樗雎粤隧?yè)面與主題的相關(guān)性。向量空間模型的優(yōu)點(diǎn)是計(jì)算簡(jiǎn)單，并且具有很好的理論基礎(chǔ)，但它在預(yù)測(cè)鏈接網(wǎng)頁(yè)的價(jià)值方面存在不足。綜合考慮了上述情況后，提出了一種改進(jìn)的主題爬行策略，即基于自適應(yīng)免疫進(jìn)化算法的一種爬行策略。在該策略中使用PageRank算法來(lái)計(jì)算網(wǎng)頁(yè)的重要程度，再根據(jù)網(wǎng)頁(yè)上處于不同位置的內(nèi)容信息來(lái)判斷其主題相關(guān)性，綜合考慮這兩項(xiàng)來(lái)估測(cè)待下載網(wǎng)頁(yè)的綜合價(jià)值，同時(shí)通過(guò)自適應(yīng)免疫進(jìn)化算法的選擇、擴(kuò)展、突變和替換操作指導(dǎo)爬蟲的爬行，實(shí)驗(yàn)證明使用新算法之后使得爬行得到的網(wǎng)頁(yè)其重要性和主題相關(guān)度都有了一定程度的提高。

網(wǎng)頁(yè)主題相關(guān)度評(píng)價(jià)計(jì)算公式如（5）所示：

在這個(gè)公式中，Sp表示頁(yè)面內(nèi)容的主題相關(guān)度；PR（p）表示基于鏈接結(jié)構(gòu)而表現(xiàn)出的頁(yè)面的重要性；ω（0≤ω≤1）表示重要性的加權(quán)參數(shù)，它的值只能人為的設(shè)定，可以根據(jù)經(jīng)驗(yàn)和具體的實(shí)驗(yàn)情況進(jìn)行修改。

2.3 聚焦爬蟲爬行策略

自適應(yīng)免疫進(jìn)化算法的聚焦爬蟲爬行策略首先通過(guò)選擇操作從URL列表中選出一部分與主題相關(guān)度較大的URL，然后通過(guò)擴(kuò)展操作對(duì)選擇操作選出的每個(gè)URL在其搜索鄰域內(nèi)隨機(jī)產(chǎn)生若干新的URL進(jìn)行局部搜索，產(chǎn)生主題相關(guān)度值較大的URL保留，將與主題相關(guān)度不大的URL在較大鄰域內(nèi)進(jìn)行突變操作產(chǎn)生其他的URL，而替換操作主要是對(duì)URL的未來(lái)價(jià)值進(jìn)行探索。具體搜索算法描述如下：

輸入：初始URLs的種子站點(diǎn)數(shù)量n；選擇閾值r0，選擇比例范圍（a，b），變異概率為Pm，替換比例d；

輸出：主題相關(guān)度大于給定值的頁(yè)面主題信息內(nèi)容集合和對(duì)應(yīng)的下載的url隊(duì)列。

（1）選取m個(gè)初始站點(diǎn)種子集中的URL，計(jì)算這m個(gè)URL的主題相關(guān)度，根據(jù)計(jì)算結(jié)果選出Integer（α*m）個(gè)評(píng)價(jià)值最高的URL來(lái)組成一個(gè)新的URL集合U1，其中0≤α≤1，這里α是選擇比例，此操作可以在優(yōu)選URL中繼續(xù)挖掘與主題相關(guān)的網(wǎng)頁(yè)。

（2）將集合U1中的所有URL進(jìn)行擴(kuò)展操作，得到新的集合U2。每個(gè)URL可以擴(kuò)展出多少個(gè)新的URL主要由該URL的主題相關(guān)度的評(píng)價(jià)值確定，評(píng)價(jià)值越高，擴(kuò)展出的新的URL個(gè)數(shù)越多。如果想要確定每個(gè)URL擴(kuò)展出的數(shù)目則可以采用轉(zhuǎn)輪法，假設(shè)URL分別表示為ν1，ν2，…，r(α*m)，則每個(gè)URL擴(kuò)展出的新的URl的概率分別為：

（3）將初始站點(diǎn)種子集中剩余的URL與U2一起構(gòu)成集合U3，假設(shè)U3中共有元素N個(gè)，則對(duì)U3進(jìn)行主題相關(guān)度升序排序，根據(jù)變異概率Pm選取后面N*Pm個(gè)URL并對(duì)它們進(jìn)行分析比較，取出具有相同主題或者相似主題所對(duì)應(yīng)的URL（即http：//＜host＞或http：//＜host＞：＜port＞/＜Path＞中內(nèi)容構(gòu)成的URL）作為變異的結(jié)果，將結(jié)果集合設(shè)為U4。

（4）再對(duì)集合U3進(jìn)行主題相關(guān)度排序，對(duì)其中d*N（d為替換比例）個(gè)主題相關(guān)度最低的URL用其第m代子URL生成新的URL進(jìn)行替換，將替換后的URL設(shè)為集合U5，這一過(guò)程就相當(dāng)于在整個(gè)搜索空間內(nèi)進(jìn)行全局搜索以避免陷入到局部最優(yōu)解。如圖1所示：假設(shè)聚焦爬蟲從P0出發(fā)，如果選擇Url1這個(gè)鏈接則可以立即得到一個(gè)與主題相關(guān)的頁(yè)面，而選擇Url2這個(gè)鏈接則不能立即獲得相關(guān)頁(yè)面。然而，由于選擇Url2鏈接時(shí)訪問(wèn)頁(yè)面P1后會(huì)得到更多的相關(guān)頁(yè)面，因此使用r1，r2，…，rn中相關(guān)度值高的來(lái)代替P1。

圖1 網(wǎng)頁(yè)頁(yè)面相關(guān)示意圖Fig.1 Webpage correlation diagram

（5）最后將集合U3、U4和U5合并起來(lái)并去掉重復(fù)鏈接，根據(jù)適應(yīng)度函數(shù)判斷合并之后的集合中的URL的適應(yīng)性，選取適應(yīng)性大于給定適應(yīng)度閾值的URL組成新的URL集合。

（6）重復(fù)上述過(guò)程，直到URL集合中為空為止。

3 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析

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

以“石油勘探”為搜索主題，先在通用搜索引擎中獲得與搜索主題可能相關(guān)的Web站點(diǎn)URL，將重復(fù)的URL過(guò)濾掉之后，人工篩選剩下的URLs，選出與“石油勘探”相關(guān)的URLs作為初始采集種子站點(diǎn)集合。為了驗(yàn)證自適應(yīng)算法的性能，系統(tǒng)分別采用最佳搜索策略，廣度優(yōu)先搜索策略和基于自適應(yīng)免疫進(jìn)化算法的搜索策略這三種不同搜索策略進(jìn)行網(wǎng)頁(yè)數(shù)據(jù)的抓取，分別記錄了抓取的網(wǎng)頁(yè)總數(shù)和主題相關(guān)度高于預(yù)設(shè)值r0的頁(yè)面數(shù)量，并對(duì)抓取到的數(shù)據(jù)進(jìn)行分析比較。系統(tǒng)運(yùn)行參數(shù)設(shè)置如下：以“石油勘探”為特定主題，初始URLs的種子站點(diǎn)數(shù)量為15；選擇閾值 r0=0.000 2，選擇比例范圍（a，b）∈［0.1，0.3］，變異概率為Pm=0.1，替換比例d=0.08，網(wǎng)頁(yè)的相關(guān)度值采用公式（5）計(jì)算，線程數(shù)設(shè)為15，爬蟲終止的條件為沒(méi)有新的URL產(chǎn)生。

3.2 數(shù)據(jù)分析

實(shí)驗(yàn)仿真結(jié)果如圖2所示，其中AIEA表示自適應(yīng)進(jìn)化免疫算法，是英文 Adaptive Immune Evolutionary Algorithm的縮寫，而OPS則表示最佳搜索策略，BFS表示廣度優(yōu)先搜索策略。圖中曲線表明：在搜索過(guò)程初期，文中所提出的自適應(yīng)免疫進(jìn)化算法搜集的主題相關(guān)網(wǎng)頁(yè)占整體下載頁(yè)面的比例低于其他兩種算法。但隨著聚焦爬蟲搜索空間進(jìn)一步深入，自適應(yīng)免疫進(jìn)化算法搜索性能優(yōu)勢(shì)明顯加強(qiáng)，下載主題相關(guān)網(wǎng)頁(yè)數(shù)所占比例明顯高于最佳搜索和廣度優(yōu)先搜索算法的比例，達(dá)到了預(yù)期的效果。

圖2 三種算法信息采集性能對(duì)比Fig.2 Three algorithms for information acquisition performance comparison

4 結(jié)束語(yǔ)

聚焦爬蟲采用何種策略進(jìn)行搜索是主題檢索的關(guān)鍵技術(shù)。提出了一種基于自適應(yīng)免疫進(jìn)化算法的聚焦爬蟲搜索策略。該策略引入PageRank算法來(lái)計(jì)算的網(wǎng)頁(yè)的重要性，同時(shí)引入向量空間模型來(lái)判斷網(wǎng)頁(yè)與主題的相關(guān)性，并綜合這兩項(xiàng)信息來(lái)評(píng)價(jià)待下載網(wǎng)頁(yè)的價(jià)值，同時(shí)算法模仿生物的免疫過(guò)程，具有較好的全局搜索和記憶能力。實(shí)驗(yàn)表明，該策略發(fā)現(xiàn)的主題相關(guān)網(wǎng)頁(yè)數(shù)所占比例超過(guò)最佳和廣度優(yōu)先的搜索策略，在一定程度上提高了爬蟲的搜索效率。

［1］林彤，江志軍.Internet的搜索引擎［J］.計(jì)算機(jī)工程與應(yīng)用，2000，36（15）：160-163.

［2］劉世濤.簡(jiǎn)析搜索引擎中網(wǎng)絡(luò)爬蟲的搜索策略［J］.阜陽(yáng)師范學(xué)院學(xué)報(bào)，2006，23（9）：59-62.

［3］李衛(wèi)疆，趙鐵軍，樸星海.一種新的面向主題的爬行算法［J］.計(jì)算機(jī)應(yīng)用研究，2009，26（5）：1663-1666.

［4］范玉順.工作流管理技術(shù)基礎(chǔ)［M］.北京：清華大學(xué)出版社，2001.

［5］袁玉萍，于曉秋，侯麗英.支持向量機(jī)模型在區(qū)域經(jīng)濟(jì)預(yù)測(cè)中的應(yīng)用及評(píng)價(jià)［J］.黑龍江八一農(nóng)墾大學(xué)學(xué)報(bào)，2009，21（1）：98-99.

［6］左興權(quán)，李士勇.一種用于優(yōu)化計(jì)算的自適應(yīng)免疫算法［J］.計(jì)算機(jī)工程與應(yīng)用，2003，39（20）：68-71.