隨著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ù)都是面向所有信息的搜索引擎，是一種通用搜索引擎。

　　主題網(wǎng)絡(luò)蜘蛛是近幾年興起的研究熱點(diǎn)，當(dāng)"蜘蛛"程序出現(xiàn)時(shí)，現(xiàn)代意義上的搜索引擎才初露端倪。它實(shí)際上是一種電腦"機(jī)器人",電腦"機(jī)器人"是指某個(gè)能以人類無(wú)法達(dá)到的速度不間斷地執(zhí)行某項(xiàng)任務(wù)的軟件程序。由于專門用于檢索信息的"機(jī)器人"程序就象蜘蛛一樣在網(wǎng)絡(luò)間爬來(lái)爬去，反反復(fù)復(fù)，不知疲倦。網(wǎng)絡(luò)蜘蛛即Web Spider,是一個(gè)很形象的名字。把互聯(lián)網(wǎng)比喻成一個(gè)蜘蛛網(wǎng)，那么Spider就是在網(wǎng)上爬來(lái)爬去的蜘蛛。網(wǎng)絡(luò)蜘蛛是通過(guò)網(wǎng)頁(yè)的鏈接地址來(lái)尋找網(wǎng)頁(yè)。如果把整個(gè)互聯(lián)網(wǎng)當(dāng)成一個(gè)網(wǎng)站，那么網(wǎng)絡(luò)蜘蛛就可以用這個(gè)原理把互聯(lián)網(wǎng)上所有的網(wǎng)頁(yè)都抓取下來(lái)。 所以，搜索引擎的"機(jī)器人"程序就被稱為"蜘蛛"程序。它針對(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í)不靈活，容易引起主題漂移。

　　本文基于兩類評(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à)值用Q來(lái)表示，這種方法的就是如何計(jì)算鏈接的Q價(jià)值。為此，搜索過(guò)程被分為訓(xùn)練和搜索兩個(gè)階段。訓(xùn)練階段用鞏固學(xué)習(xí)算法計(jì)算每個(gè)鏈接的Q價(jià)值，按價(jià)值的大小分為若干類，并用每一類中的文本信息訓(xùn)練一個(gè)Naive Bayes分類器； 分類器是一種計(jì)算機(jī)程序。他的設(shè)計(jì)目標(biāo)是在通過(guò)學(xué)習(xí)后，可自動(dòng)將數(shù)據(jù)分到已知類別。應(yīng)用在搜索引擎以及各種檢索程序中。同時(shí)也大量應(yīng)于數(shù)據(jù)分析與預(yù)測(cè)領(lǐng)域。   分類器是一種機(jī)器學(xué)習(xí)程序，因此歸為人工智能的范疇中。人工智能的多個(gè)領(lǐng)域，包括數(shù)據(jù)挖掘，系統(tǒng)，模式識(shí)別都用到此類程序。 在搜索階段，面對(duì)價(jià)值未知的鏈接，則根據(jù)鏈接文本，因?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ū)。圖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)越少。

　　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ū)后，系統(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)度分析。網(wǎng)絡(luò)爬蟲（又被稱為網(wǎng)頁(yè)蜘蛛，網(wǎng)絡(luò)機(jī)器人，在FOAF社區(qū)中間，更經(jīng)常的稱為網(wǎng)頁(yè)追逐者），是一種按照一定的規(guī)則，自動(dòng)的抓取萬(wàn)維網(wǎng)信息的程序或者腳本。隨著網(wǎng)絡(luò)的迅速發(fā)展，萬(wàn)維網(wǎng)成為大量信息的載體，如何有效地提取并利用這些信息成為一個(gè)巨大的挑戰(zhàn)。搜索引擎（Search Engine），例如傳統(tǒng)的通用搜索引擎AltaVista,Yahoo!和Google等，作為一個(gè)輔助人們檢索信息的工具成為用戶訪問(wèn)萬(wàn)維網(wǎng)的入口和指南。自身通過(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 5.0是自Java出現(xiàn)以來(lái)重要的版本。隨著對(duì)Java語(yǔ)言的主要修改和Java平臺(tái)中重要的新API的出現(xiàn)，需要精通的新特性有很多。Java,是由Sun Microsystems公司于1995年5月推出的Java程序設(shè)計(jì)語(yǔ)言和Java平臺(tái)的總稱。用Java實(shí)現(xiàn)的HotJava瀏覽器（支持Java applet）顯示了Java的魅力：跨平臺(tái)、動(dòng)態(tài)的Web、Internet計(jì)算。從此，Java被廣泛接受并推動(dòng)了Web的迅速發(fā)展，常用的瀏覽器現(xiàn)在均支持Java applet.本文利用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à)值。

　?。?）判斷所得的立即價(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）。

　?。?）如果所得的未來(lái)價(jià)值小于給定的閾值r2,將該鏈接列入被舍棄的URL列表里。結(jié)束此線程。

　　另外每隔T的時(shí)間后，手動(dòng)選擇與主題相關(guān)度高前100的頁(yè)面加入鏈接分析器進(jìn)行訓(xùn)練，對(duì)爬蟲數(shù)據(jù)庫(kù)進(jìn)行更新。

　　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)鍵字集合。其中包括13 000個(gè)計(jì)算機(jī)詞匯，并進(jìn)行了一些擴(kuò)充。

　　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ù)見(jiàn)遠(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)致局部?；谖磥?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搜索局部子空間的陷阱。同時(shí)，不斷更新爬蟲數(shù)據(jù)庫(kù)，提高了其對(duì)主題相關(guān)性的判斷能力，從而提高了搜索引擎的查準(zhǔn)率。實(shí)驗(yàn)表明，該算法的查全率不但大大高于兩種傳統(tǒng)的單一算法，同時(shí)也整體提高了搜索引擎的性能。