摘  要： 在分析傳統(tǒng)的網(wǎng)絡(luò)蜘蛛搜索特點(diǎn)的基礎(chǔ)上,，充分利用Web資源分布的特點(diǎn)，提出了基于在線增量自適應(yīng)算法的搜索策略。該算法一方面避免了過(guò)早陷入Web搜索最優(yōu)子空間的陷阱,；另一方面不斷對(duì)爬蟲數(shù)據(jù)庫(kù)更新,，以提高其對(duì)鏈接主題的判斷能力。通過(guò)對(duì)四所著名大學(xué)計(jì)算機(jī)網(wǎng)站做的搜索實(shí)驗(yàn),，表明新的算法可以有效地提高網(wǎng)絡(luò)蜘蛛的搜索性能,。
關(guān)鍵詞： 網(wǎng)絡(luò)蜘蛛；搜索策略,；在線增量自適應(yīng)

    隨著Internet的快速發(fā)展,，Web上的信息資源也呈指數(shù)級(jí)增長(zhǎng)，搜索引擎已經(jīng)成為網(wǎng)絡(luò)用戶獲取各種信息的必備工具,。對(duì)于搜索引擎來(lái)說(shuō),，要抓取互聯(lián)網(wǎng)上的所有信息幾乎是不可能的，從公布的數(shù)據(jù)來(lái)看,，容量最大的搜索引擎也只不過(guò)是抓取了整個(gè)網(wǎng)絡(luò)信息的40%左右。傳統(tǒng)的搜索引擎(如Google,、Baidu,、Yahoo等)大多數(shù)都是面向所有信息的搜索引擎，是一種通用搜索引擎,。這種通用搜索引擎已經(jīng)不能滿足特定用戶更深入的查詢需求,，他們對(duì)信息的需求往往是面對(duì)特定領(lǐng)域和特定主題的。面對(duì)挑戰(zhàn),，適應(yīng)特定人群需要的專業(yè)搜索引擎逐漸引起研究學(xué)者的重視,。
    主題網(wǎng)絡(luò)蜘蛛是最近幾年興起的研究熱點(diǎn)，它針對(duì)某個(gè)專門的領(lǐng)域進(jìn)行搜索,，以滿足特定人群的個(gè)性化需求,。網(wǎng)絡(luò)蜘蛛研究的核心是解決頁(yè)面和URL的主題相關(guān)性判別的問(wèn)題，因此如何評(píng)價(jià)鏈接價(jià)值就成了網(wǎng)絡(luò)蜘蛛爬進(jìn)效率的關(guān)鍵,。鏈接價(jià)值可以分為兩類,，即基于立即回報(bào)價(jià)值和基于未來(lái)回報(bào)價(jià)值。
    立即回報(bào)價(jià)值算法是依據(jù)搜索時(shí)在線獲得的文本或Web結(jié)構(gòu)來(lái)對(duì)鏈接的頁(yè)面重要程度進(jìn)行預(yù)測(cè),，進(jìn)而決定鏈接訪問(wèn)順序,。這類方法理論基礎(chǔ)好，計(jì)算簡(jiǎn)單,，在距離相關(guān)頁(yè)面比較近的時(shí)候表現(xiàn)出良好的性能,。但它很難反映Web的整體情況，網(wǎng)絡(luò)蜘蛛在距離相關(guān)頁(yè)面比較遠(yuǎn)的時(shí)候容易迷失方向,?；谖磥?lái)價(jià)值的算法利用Web上的信息分布在某種程度的相似性，對(duì)網(wǎng)絡(luò)蜘蛛先進(jìn)行訓(xùn)練，使其具有一些經(jīng)驗(yàn)信息,，對(duì)未來(lái)搜索具有一定的預(yù)測(cè)性。但其預(yù)測(cè)能力有限,，而且需要用戶選擇種子集,，搜索時(shí)不靈活，容易引起主題漂移[1-4],。
本文基于兩類評(píng)價(jià)方法,，提出了一種在線學(xué)習(xí)的自適應(yīng)綜合價(jià)值的網(wǎng)絡(luò)蜘蛛搜索算法，利用Web資源分布的某些相似性和鏈接價(jià)值的關(guān)系,，將立即價(jià)值和未來(lái)價(jià)值的評(píng)價(jià)方法相結(jié)合,，在爬行過(guò)程中不斷自身提高鏈接主題相關(guān)性的判斷能力，從而改進(jìn)網(wǎng)絡(luò)蜘蛛的性能,。
1 主題爬行策略
    根據(jù)評(píng)價(jià)鏈接價(jià)值所采用的不同方法,，現(xiàn)有的網(wǎng)絡(luò)蜘蛛的搜索策略分為兩大類：基于立即回報(bào)價(jià)值評(píng)價(jià)的搜索策略和基于未來(lái)回報(bào)價(jià)值的搜索策略。本文采用基于內(nèi)容評(píng)價(jià)的策略(基于立即價(jià)值)和基于鞏固學(xué)習(xí)的搜索策略(基于未來(lái)價(jià)值),。
基于內(nèi)容評(píng)價(jià)的搜索策略,，主要是根據(jù)主題與鏈接文本“語(yǔ)義”的相似度來(lái)評(píng)價(jià)鏈接價(jià)值的高低。鏈接文本是指周圍的說(shuō)明文字和和鏈接URLs上的文字信息,。相似度的評(píng)價(jià)一般采用下面的公式：

其中,，q代表主題關(guān)鍵詞集合，p代表頁(yè)面鏈接文本集合,，Wkp代表d中單詞對(duì)某一主題的重要程度,，Wkp通常采用tf×idf公式計(jì)算。
    基于鞏固學(xué)習(xí)的搜索策略,，鞏固學(xué)習(xí)的優(yōu)勢(shì)在于能預(yù)測(cè)遠(yuǎn)期的回報(bào)價(jià)值(也稱未來(lái)價(jià)值),。未來(lái)價(jià)值用Q來(lái)表示，這種方法的核心就是如何計(jì)算鏈接的Q價(jià)值,。為此,，搜索過(guò)程被分為訓(xùn)練和搜索兩個(gè)階段。訓(xùn)練階段用鞏固學(xué)習(xí)算法計(jì)算每個(gè)鏈接的Q價(jià)值,，按價(jià)值的大小分為若干類,，并用每一類中的文本信息訓(xùn)練一個(gè)Naive Bayes分類器；在搜索階段,，面對(duì)價(jià)值未知的鏈接,，則根據(jù)鏈接文本，用Naive Bayes分類器計(jì)算鏈接落在每一類中的概率,，并以這個(gè)概率為權(quán)值來(lái)計(jì)算鏈接的Q價(jià)值,。因?yàn)镼價(jià)值反映的是未來(lái)的回報(bào)預(yù)測(cè)值,，所以當(dāng)搜索的頁(yè)面與主題不相關(guān)時(shí)，網(wǎng)路蜘蛛也可以根據(jù)未來(lái)回報(bào)的預(yù)測(cè)值來(lái)確定正確的搜索方向,。
該模型的核心就是如何計(jì)算鏈接的Q價(jià)值,。Q價(jià)值的計(jì)算公式[５]：

2 在線增量自適應(yīng)算法網(wǎng)絡(luò)蜘蛛搜索策略
2.1 Web資源分布和鏈接價(jià)值的關(guān)系
    雖然整個(gè)網(wǎng)絡(luò)資源的分布是無(wú)序的，但近年來(lái)的研究表明,，與某一主題相關(guān)的頁(yè)面以不同群聚群體的方式分散在網(wǎng)絡(luò)中,，把這些群體稱為Web社區(qū)[6]。圖1中顯示了這種Web社區(qū)的分布關(guān)系,。在網(wǎng)頁(yè)的設(shè)計(jì)過(guò)程中不可能把所有相關(guān)的網(wǎng)頁(yè)鏈接在一起,，網(wǎng)頁(yè)中只包含了極少部分與該主題相關(guān)的網(wǎng)頁(yè)鏈接，這些資源信息一起構(gòu)成了一個(gè)與某一主題相關(guān)的Web社區(qū),。在某一站點(diǎn)附近有很多緊密聯(lián)系的站點(diǎn),，它們都能基本地反映某個(gè)主題。但在網(wǎng)頁(yè)的發(fā)布過(guò)程中,，可能會(huì)出現(xiàn)與之有一定關(guān)聯(lián)但又與主題不相關(guān)的無(wú)關(guān)網(wǎng)頁(yè)，這些無(wú)關(guān)網(wǎng)頁(yè)在網(wǎng)絡(luò)蜘蛛的爬行過(guò)程中會(huì)導(dǎo)致中心主題發(fā)生漂移,。正是由于這些無(wú)關(guān)網(wǎng)頁(yè)的“干擾”,，使得網(wǎng)絡(luò)蜘蛛在爬行的過(guò)程中隨著時(shí)間的推移，爬行出來(lái)的鏈接會(huì)與最初鏈接的主題相關(guān)性差別越來(lái)越大,，系統(tǒng)爬行到的網(wǎng)頁(yè)也越來(lái)越少。這就要求在網(wǎng)絡(luò)蜘蛛的爬行過(guò)程中,，一方面能盡可能地覆蓋所有相關(guān)網(wǎng)頁(yè),；另一方面又要在爬行的過(guò)程中不斷“更新”,，以提高主題相關(guān)性的判斷能力,。這就要求網(wǎng)絡(luò)蜘蛛在不同的階段采用不同的搜索策略，同時(shí)不斷“自我更新”,，以提高爬行的效率和精度,。

2.2 算法思想
    根據(jù)Web資源的分布信息，本文把網(wǎng)絡(luò)蜘蛛爬行的過(guò)程人為地分為兩個(gè)階段：挖掘和探索,。在Web社區(qū)內(nèi),，由于和主題相關(guān)的網(wǎng)頁(yè)比較多,，立即價(jià)值比較大,，這個(gè)時(shí)候就要求能盡快地挖掘Web社區(qū)內(nèi)與主題相關(guān)的網(wǎng)頁(yè)信息。這個(gè)時(shí)候適合選取注重發(fā)掘立即價(jià)值的搜索策略,。而在Web社區(qū)之間,，由于存在大量與主題無(wú)關(guān)的網(wǎng)頁(yè)，這個(gè)時(shí)候要注重探索,，盡可能地探索到與主題相關(guān)的Web社區(qū),。但這個(gè)時(shí)候鏈接的立即價(jià)值會(huì)很小，適合選取基于未來(lái)價(jià)值的搜索策略,，本文采用基于鞏固學(xué)習(xí)的搜索策略。同時(shí)為減少網(wǎng)絡(luò)蜘蛛在爬行過(guò)程中的主題漂移,，提高主題相關(guān)性的判斷能力,，在每爬完N個(gè)Web社區(qū)后(本文用爬行一個(gè)固定時(shí)間段來(lái)表示)，系統(tǒng)選取爬蟲數(shù)據(jù)庫(kù)中爬行到的與主題相關(guān)度高前100名的頁(yè)面,，與其對(duì)應(yīng)的正向鏈接信息組成的實(shí)例加入鏈接分類器的訓(xùn)練數(shù)據(jù),。鏈接分類器一旦訓(xùn)練完成，就可以對(duì)新產(chǎn)生的鏈接進(jìn)行相關(guān)度分析,。自身通過(guò)爬蟲數(shù)據(jù)庫(kù)新進(jìn)的主題相關(guān)度高的頁(yè)面和頁(yè)面正向鏈接信息不斷修正,，提高主題相關(guān)性的判斷能力。
2.3 在線增量自適應(yīng)算法的設(shè)計(jì)和實(shí)現(xiàn)
    在線增量自適應(yīng)算法的本質(zhì)是：通過(guò)網(wǎng)路蜘蛛的爬行,，在Web社區(qū)內(nèi)盡可能地挖掘和主題相關(guān)的頁(yè)面,，而在社區(qū)外獲取那些具有較高的未來(lái)Q價(jià)值的鏈接。反過(guò)來(lái),，在搜索時(shí)又根據(jù)鏈接文本的Q價(jià)值估算出鏈接的價(jià)值,，決定選擇行動(dòng)的概率。同時(shí),，不斷通過(guò)爬蟲數(shù)據(jù)庫(kù)新進(jìn)的主題相關(guān)度高的頁(yè)面和頁(yè)面的正向鏈接信息修正,，提高鏈接主題相關(guān)性判斷能力。本文利用Java技術(shù),，算法實(shí)現(xiàn)過(guò)程如下：
ZX-ZL(topic,，startUrls){
        Link_1=fetch link(startUrls)；
        While(visited<MAX_PAGES){
    //小于爬蟲最大訪問(wèn)量
score_r1=sim(topic,， doc),；  //計(jì)算立即價(jià)值
If(socre_r1>r1)
enqueue_1(frontier，extract_links(doc),，score_1)；
else{
score_r2=Q(topic,， doc),；   //計(jì)算未來(lái)價(jià)值
if(score_2>r2)
continue；
else
enqueue_2(links),；
}
}
}
2.4 算法過(guò)程描述
    (1)網(wǎng)絡(luò)蜘蛛首先從一個(gè)“種子集”出發(fā),，并選擇其中的一個(gè)鏈接訪問(wèn),。
    (2)按照式(1)計(jì)算鏈接節(jié)點(diǎn)的立即價(jià)值。
    (3)判斷所得的立即價(jià)值是否大于系統(tǒng)給定的閾值r1,，如果大于給定閾值,，則將該鏈接加入到候選URL列表里。如果小于給定的閾值r1,，就利用式(2)計(jì)算此鏈接的未來(lái)價(jià)值,。
    (4)如果經(jīng)計(jì)算所得未來(lái)價(jià)值大于系統(tǒng)給定的閾值r2，系統(tǒng)就并發(fā)另一個(gè)線程從此節(jié)點(diǎn)開始,，返回步驟(2),。
    (5)如果所得的未來(lái)價(jià)值小于給定的閾值r2，將該鏈接列入被舍棄的URL列表里,。結(jié)束此線程,。
    另外每隔T的時(shí)間后，手動(dòng)選擇與主題相關(guān)度高前100的頁(yè)面加入鏈接分析器進(jìn)行訓(xùn)練,，對(duì)爬蟲數(shù)據(jù)庫(kù)進(jìn)行更新[7],。
3 實(shí)驗(yàn)與結(jié)果分析
3.1 實(shí)驗(yàn)背景
    本文選取了如表1所示的美國(guó)四所大學(xué)的計(jì)算機(jī)網(wǎng)站做了實(shí)際的搜索實(shí)驗(yàn)，搜索目的是尋找本地服務(wù)器中的計(jì)算機(jī)論文,，以PDF和.PS結(jié)尾的計(jì)算機(jī)論文定義為相關(guān)文檔,。采用基于立即價(jià)值、未來(lái)價(jià)值和基于本文所描述的在線增量學(xué)習(xí)的自適應(yīng)算法三種不同搜索策略的網(wǎng)絡(luò)蜘蛛,，在線統(tǒng)計(jì)Web上與計(jì)算機(jī)相關(guān)的論文數(shù),，并計(jì)算各自的查全率和查準(zhǔn)率。本文采用FOLDOC在線計(jì)算機(jī)字典作為主題關(guān)鍵字集合[8],。其中包括13 000個(gè)計(jì)算機(jī)專業(yè)詞匯,，并進(jìn)行了一些擴(kuò)充。從站點(diǎn)的主頁(yè)出發(fā),，對(duì)上述四所大學(xué)Web服務(wù)器進(jìn)行了實(shí)際的搜索測(cè)試，共找到了15 034篇與計(jì)算機(jī)相關(guān)的論文,。

3.2 實(shí)驗(yàn)結(jié)果和性能分析
    圖2中,，三種不同搜索策略在不同階段的查全率不同。其原因在于,，基于立即價(jià)值的搜索策略在相關(guān)社區(qū)中的搜索率很高,，可以很快地找到相關(guān)網(wǎng)頁(yè)，所以其增長(zhǎng)率很快,。但在找無(wú)關(guān)網(wǎng)頁(yè)集合時(shí)容易迷失方向,，從一個(gè)Web社區(qū)搜索完畢后進(jìn)入另一個(gè)Web社區(qū)的能力較弱，查全率會(huì)降低,；基于未來(lái)價(jià)值的搜索策略,，在尋找無(wú)關(guān)頁(yè)面集合中,，未來(lái)價(jià)值對(duì)預(yù)見遠(yuǎn)期回報(bào)很有幫助，它可以很快地找到論文的目錄所在,，但早期的回報(bào)率不高,；基于在線增量自適應(yīng)算法采用綜合的搜索策略，除在搜索初期其回報(bào)略低于基于立即價(jià)值的網(wǎng)絡(luò)蜘蛛外,，其增長(zhǎng)率很快超過(guò)兩種算法,。不論是在社區(qū)內(nèi)的搜索還是過(guò)度無(wú)關(guān)網(wǎng)頁(yè)來(lái)獲取遠(yuǎn)期回報(bào)，它都表現(xiàn)出了優(yōu)異的性能,。

    圖3中基于在線增量自適應(yīng)算法的網(wǎng)絡(luò)蜘蛛查準(zhǔn)率顯然高于其他兩種,。除了最初的階段外，其余時(shí)間的查準(zhǔn)率都高于50%,。其原因在于每隔一定的時(shí)間,，爬蟲數(shù)據(jù)庫(kù)不斷自我更新，提高主題相關(guān)性的判斷能力,。在Web社區(qū)外,，在一定程度上避免了采集大量的無(wú)關(guān)文檔；在主題相關(guān)的Web社區(qū)內(nèi)又提高了其搜索能力,，因此其查準(zhǔn)率很高,。而基于立即價(jià)值的網(wǎng)絡(luò)蜘蛛在跨越Web社區(qū)時(shí)常常會(huì)發(fā)生主題偏移，容易導(dǎo)致局部最優(yōu),?；谖磥?lái)價(jià)值的網(wǎng)絡(luò)蜘蛛在跨越Web社區(qū)時(shí)采集了大量與主題無(wú)關(guān)的文檔，同時(shí)在主題相關(guān)社區(qū)內(nèi)的搜索能力又比較低,，因此查準(zhǔn)率不高,。

    本文將基于改進(jìn)的鞏固學(xué)習(xí)方法的行動(dòng)策略的在線增量自適應(yīng)算法引入搜索引擎中，避免了過(guò)早陷入Web搜索局部最優(yōu)子空間的陷阱,。同時(shí),，不斷更新爬蟲數(shù)據(jù)庫(kù)，提高了其對(duì)主題相關(guān)性的判斷能力,，從而提高了搜索引擎的查準(zhǔn)率,。實(shí)驗(yàn)表明，該算法的查全率不但大大高于兩種傳統(tǒng)的單一算法,，同時(shí)也整體提高了搜索引擎的性能,。
參考文獻(xiàn)
[1] MURRAY B H， MOORE A. Sizing the internet[M]. A White Paper： Cyveillance,， Inc. 2000.
[2] LAWRENCE S,， GILES L. Accessibility and distribution of information on the Web[J]. Nature， 1999,， 400(8)： 107-109.
[3] BREWINGTON B E,， CYBENK G. How dynamic is the Web[J]. Computer Networks,， 2000， 33(1-6). 257-276.
[4] ESTER M,， GROB M,， KRIEGEL H. Focused Web crawling： a generic framework for specifying the user interest and for adaptive crawling strategies[Z]. Proceeding of the International Conference on Very Large Database (VLDB’01)， 2001.
[5] 陳治平.智能搜索引擎理論與應(yīng)用研究[D].長(zhǎng)沙：湖南大學(xué),，2003.
[6] 傅向華,，馮博琴，馬兆豐,，等.可在線增量自學(xué)習(xí)的聚焦爬行方法[J].西安交通大學(xué)學(xué)報(bào),，2004，38(6)：599-602.
[7] HOWE D. Free on-line dictionary of computer[WZ]. http： //www. foldoc. org/. 2010.
[8] CHO J,， GARCIA-M H,， PAGE L. Efficient crawling through URL ordering[J]. Computer Networks， 1998,， 30(1-7)： 161-172.