基于社區(qū)增量自適應(yīng)爬蟲(chóng)研究

馬 睿

(暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院，廣東 廣州 510632)

隨著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)特定人群需要的專(zhuān)業(yè)搜索引擎逐漸引起研究學(xué)者的重視。

主題網(wǎng)絡(luò)蜘蛛是最近幾年興起的研究熱點(diǎn)，它針對(duì)某個(gè)專(zhuān)門(mén)的領(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à)值可以分為兩類(lèi)，即基于立即回報(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)順序。這類(lèi)方法理論基礎(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]。

本文基于兩類(lèi)評(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ò)蜘蛛的搜索策略分為兩大類(lèi)：基于立即回報(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à)值的高低。鏈接文本是指周?chē)恼f(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à)值(也稱(chēng)未來(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à)值的大小分為若干類(lèi)，并用每一類(lèi)中的文本信息訓(xùn)練一個(gè)Naive Bayes分類(lèi)器；在搜索階段，面對(duì)價(jià)值未知的鏈接，則根據(jù)鏈接文本，用Naive Bayes分類(lèi)器計(jì)算鏈接落在每一類(lèi)中的概率，并以這個(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ì)算公式[5]：

其中Q(m)t是各鏈接前瞻n步的折算積累回報(bào)，該Q(λ)函數(shù)使用常量 λ(0≤λ≤1)來(lái)合并從不同前瞻距離中獲得的回報(bào)。

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ò)中，把這些群體稱(chēng)為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í)不斷“自我更新”，以提高爬行的效率和精度。

圖1 Web信息資源分布特點(diǎn)示意圖

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)選取爬蟲(chóng)數(shù)據(jù)庫(kù)中爬行到的與主題相關(guān)度高前100名的頁(yè)面，與其對(duì)應(yīng)的正向鏈接信息組成的實(shí)例加入鏈接分類(lèi)器的訓(xùn)練數(shù)據(jù)。鏈接分類(lèi)器一旦訓(xùn)練完成，就可以對(duì)新產(chǎn)生的鏈接進(jìn)行相關(guān)度分析。自身通過(guò)爬蟲(chóng)數(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ò)爬蟲(chóng)數(shù)據(jù)庫(kù)新進(jìn)的主題相關(guān)度高的頁(yè)面和頁(yè)面的正向鏈接信息修正，提高鏈接主題相關(guān)性判斷能力。本文利用Java技術(shù)，算法實(shí)現(xiàn)過(guò)程如下：

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)開(kāi)始，返回步驟(2)。

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

另外每隔T的時(shí)間后，手動(dòng)選擇與主題相關(guān)度高前100的頁(yè)面加入鏈接分析器進(jìn)行訓(xùn)練，對(duì)爬蟲(chóng)數(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ī)專(zhuān)業(yè)詞匯，并進(jìn)行了一些擴(kuò)充。從站點(diǎn)的主頁(yè)出發(fā)，對(duì)上述四所大學(xué)Web服務(wù)器進(jìn)行了實(shí)際的搜索測(cè)試，共找到了15 034篇與計(jì)算機(jī)相關(guān)的論文。

表1 四所大學(xué)計(jì)算機(jī)Web服務(wù)器名稱(chēng)

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)異的性能。

圖2 三種蜘蛛的查全率

圖3中基于在線增量自適應(yīng)算法的網(wǎng)絡(luò)蜘蛛查準(zhǔn)率顯然高于其他兩種。除了最初的階段外，其余時(shí)間的查準(zhǔn)率都高于50%。其原因在于每隔一定的時(shí)間，爬蟲(chóng)數(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)率不高。

圖3 三種蜘蛛的查準(zhǔn)率

本文將基于改進(jìn)的鞏固學(xué)習(xí)方法的行動(dòng)策略的在線增量自適應(yīng)算法引入搜索引擎中，避免了過(guò)早陷入Web搜索局部最優(yōu)子空間的陷阱。同時(shí)，不斷更新爬蟲(chóng)數(shù)據(jù)庫(kù)，提高了其對(duì)主題相關(guān)性的判斷能力，從而提高了搜索引擎的查準(zhǔn)率。實(shí)驗(yàn)表明，該算法的查全率不但大大高于兩種傳統(tǒng)的單一算法，同時(shí)也整體提高了搜索引擎的性能。

[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 forspecifying 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.