摘  要： 在分析傳統的網絡蜘蛛搜索特點的基礎上，充分利用Web資源分布的特點，提出了基于在線增量自適應算法的搜索策略。該算法一方面避免了過早陷入Web搜索最優子空間的陷阱；另一方面不斷對爬蟲數據庫更新，以提高其對鏈接主題的判斷能力。通過對四所著名大學計算機網站做的搜索實驗，表明新的算法可以有效地提高網絡蜘蛛的搜索性能。
關鍵詞： 網絡蜘蛛；搜索策略；在線增量自適應

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

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

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

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

3.2 實驗結果和性能分析
    圖2中，三種不同搜索策略在不同階段的查全率不同。其原因在于，基于立即價值的搜索策略在相關社區中的搜索率很高，可以很快地找到相關網頁，所以其增長率很快。但在找無關網頁集合時容易迷失方向，從一個Web社區搜索完畢后進入另一個Web社區的能力較弱，查全率會降低；基于未來價值的搜索策略，在尋找無關頁面集合中，未來價值對預見遠期回報很有幫助，它可以很快地找到論文的目錄所在，但早期的回報率不高；基于在線增量自適應算法采用綜合的搜索策略，除在搜索初期其回報略低于基于立即價值的網絡蜘蛛外，其增長率很快超過兩種算法。不論是在社區內的搜索還是過度無關網頁來獲取遠期回報，它都表現出了優異的性能。

    圖3中基于在線增量自適應算法的網絡蜘蛛查準率顯然高于其他兩種。除了最初的階段外，其余時間的查準率都高于50%。其原因在于每隔一定的時間，爬蟲數據庫不斷自我更新，提高主題相關性的判斷能力。在Web社區外，在一定程度上避免了采集大量的無關文檔；在主題相關的Web社區內又提高了其搜索能力，因此其查準率很高。而基于立即價值的網絡蜘蛛在跨越Web社區時常常會發生主題偏移，容易導致局部最優。基于未來價值的網絡蜘蛛在跨越Web社區時采集了大量與主題無關的文檔，同時在主題相關社區內的搜索能力又比較低，因此查準率不高。

    本文將基于改進的鞏固學習方法的行動策略的在線增量自適應算法引入搜索引擎中，避免了過早陷入Web搜索局部最優子空間的陷阱。同時，不斷更新爬蟲數據庫，提高了其對主題相關性的判斷能力，從而提高了搜索引擎的查準率。實驗表明，該算法的查全率不但大大高于兩種傳統的單一算法，同時也整體提高了搜索引擎的性能。
參考文獻
[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] 陳治平.智能搜索引擎理論與應用研究[D].長沙：湖南大學，2003.
[6] 傅向華，馮博琴，馬兆豐，等.可在線增量自學習的聚焦爬行方法[J].西安交通大學學報，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.