基于動(dòng)力粒子群算法的網(wǎng)絡(luò)蜘蛛搜索策略研究

摘要：傳統(tǒng)的基于單一價(jià)值評(píng)價(jià)的網(wǎng)絡(luò)蜘蛛搜索策略存在主題漂移，不能有效利用鏈接結(jié)構(gòu)信息，容易迷失方向，過于依賴關(guān)鍵詞集等不足。提出一種基于動(dòng)力粒子群算法的啟發(fā)式網(wǎng)絡(luò)蜘蛛搜索算法，新算法充分考慮Web站點(diǎn)信息資源分布的特點(diǎn)，給合了兩類評(píng)價(jià)標(biāo)準(zhǔn)的優(yōu)勢(shì)，根據(jù)實(shí)際的搜索情況，在線調(diào)整兩種價(jià)值的權(quán)重，具有自適應(yīng)性。實(shí)驗(yàn)表明，新算法具有較高的查全率和查準(zhǔn)率，能較好地解決現(xiàn)存問題。

關(guān)鍵詞：網(wǎng)絡(luò)蜘蛛； Web社區(qū)； 動(dòng)力粒子群； 立即價(jià)值； 未來價(jià)值

中圖分類號(hào)：TP311.1文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)05-1374-04

0引言

網(wǎng)絡(luò)蜘蛛是垂直搜索引擎中最重要的一個(gè)組成部分，是一種智能化軟件，其任務(wù)是獲取符合要求的Web頁面返給用戶或保存在索引庫中，并決定鏈接訪問順序。如何全面而準(zhǔn)確地采集特定領(lǐng)域的相關(guān)內(nèi)容是垂直搜索引擎的一個(gè)研究重點(diǎn)。網(wǎng)絡(luò)蜘蛛常采用最好優(yōu)先原則即每次選擇最有價(jià)值的鏈接進(jìn)行訪問，因此一些啟發(fā)式規(guī)則被運(yùn)用到搜索策略的研究之中，如1999年Chakrabarti等人采用鞏固學(xué)習(xí)的方法來對(duì)即將爬行的網(wǎng)頁作出智能性判斷與選擇；2001年Chau和Chen等人用 Hopfield網(wǎng)絡(luò)學(xué)習(xí)與競(jìng)爭(zhēng)機(jī)制實(shí)現(xiàn)Hopfield Net Spider；2002年王靖等人和2004年李學(xué)勇等人報(bào)告了基于模擬退火機(jī)制的網(wǎng)絡(luò)蜘蛛，這些在某種程度提高了網(wǎng)絡(luò)蜘蛛的智能化程度。

本質(zhì)上說，網(wǎng)絡(luò)蜘蛛的搜索問題是一個(gè)多目標(biāo)規(guī)劃問題，在合理的時(shí)間限度內(nèi)，以較少的網(wǎng)絡(luò)資源、存儲(chǔ)資源和計(jì)算資源獲得更多的主題相關(guān)頁面。網(wǎng)絡(luò)蜘蛛研究的核心是解決頁面和URL的主題相關(guān)性判別問題，因此如何評(píng)價(jià)鏈接價(jià)值是決定此類網(wǎng)絡(luò)蜘蛛爬行效率的關(guān)鍵。鏈接價(jià)值評(píng)價(jià)算法可分為兩類，即基于立即回報(bào)價(jià)值（簡(jiǎn)稱立即價(jià)值）和基于未來回報(bào)價(jià)值（簡(jiǎn)稱未來價(jià)值）的評(píng)價(jià)算法。

基于立即價(jià)值的評(píng)價(jià)算法主要是依據(jù)搜索時(shí)在線獲得的文本或Web結(jié)構(gòu)信息來對(duì)鏈接頁面的重要性進(jìn)行預(yù)測(cè)。文獻(xiàn)[1~4]通過對(duì)頁面間相互引用關(guān)系的分析和計(jì)算主題與鏈接文本內(nèi)容的相似度大小來確定鏈接的重要性，進(jìn)而決定鏈接訪問順序。這類方法優(yōu)點(diǎn)是理論基礎(chǔ)較好，計(jì)算簡(jiǎn)單，在距離相關(guān)頁面較近的地方搜索時(shí)表現(xiàn)出良好的性能[5]，但也存在一些缺陷：頁面文本缺乏全局性，很難反映Web的整體情況，網(wǎng)絡(luò)蜘蛛在距離相關(guān)頁面集較遠(yuǎn)搜索時(shí)易迷失方向[6]；忽略了半結(jié)構(gòu)文檔所蘊(yùn)涵的許多信息；評(píng)價(jià)的準(zhǔn)確性依賴對(duì)主題關(guān)鍵字集的選擇和構(gòu)建[7]。基于未來價(jià)值的評(píng)價(jià)算法利用Web上信息資源分布的某種程度的相似性，先對(duì)網(wǎng)絡(luò)蜘蛛進(jìn)行訓(xùn)練，使其具備一些經(jīng)驗(yàn)信息，對(duì)未來搜索具有一定的傾向性，目前代表性的方法是基于鞏固學(xué)習(xí)的搜索策略[8]，這類搜索策略能發(fā)掘鏈接文本中隱含的結(jié)構(gòu)信息，但其預(yù)測(cè)能力有限，且這種離線訓(xùn)練方式需要選擇典型站點(diǎn)或種子集，加重了用戶的負(fù)擔(dān)，更重要的是搜索時(shí)不靈活，搜索不集中，容易引起主題漂移。考慮到采用單一評(píng)價(jià)方法不能有效預(yù)測(cè)鏈接的真實(shí)價(jià)值，近年來有學(xué)者提出了基于綜合價(jià)值評(píng)價(jià)的搜索策略，如文獻(xiàn)[9]綜合了基于內(nèi)容和鏈接結(jié)構(gòu)的評(píng)價(jià)方法，提出了混合評(píng)價(jià)機(jī)制；文獻(xiàn)[10]提出了結(jié)合模擬退火的啟發(fā)式搜索算法來調(diào)節(jié)立即回報(bào)價(jià)值和未來回報(bào)價(jià)值的信任度比例；文獻(xiàn)[11]報(bào)告了一種改進(jìn)遺傳算法來動(dòng)態(tài)調(diào)整兩種策略的權(quán)重，這些算法的實(shí)驗(yàn)表明采用基于綜合價(jià)值評(píng)價(jià)的搜索策略可有效提高搜索效率。

本文在分析了兩類評(píng)價(jià)方法并參考相關(guān)學(xué)者研究成果的基礎(chǔ)上，在動(dòng)力粒子群框架內(nèi)提出了一種基于綜合價(jià)值的網(wǎng)絡(luò)蜘蛛搜索算法，它利用了Web資源分布與鏈接價(jià)值關(guān)系，將基于立即價(jià)值和未來價(jià)值的評(píng)價(jià)方法相結(jié)合，在信息采集過程中動(dòng)態(tài)地改變立即價(jià)值和未來價(jià)值在綜合價(jià)值中的比例關(guān)系，從而改進(jìn)網(wǎng)絡(luò)蜘蛛的性能。

1預(yù)備知識(shí)

為了方便描述鏈接價(jià)值間關(guān)系的挖掘方法，先給出相關(guān)定義：

定義1鏈接的立即價(jià)值。給定搜索主題s，設(shè)頁面p中有一鏈接a，若a所指向的頁面q與主題s相關(guān)，則稱頁面q具有與主題s相關(guān)的立即價(jià)值；根據(jù)立即價(jià)值的評(píng)價(jià)算法來預(yù)測(cè)的鏈接a所指向頁面q與主題相關(guān)的程度，稱鏈接a與主題s相關(guān)的大小為Is(a)的立即價(jià)值，通常利用文本相似度或Web結(jié)構(gòu)信息來獲得鏈接的立即價(jià)值。

定義2鏈接的未來價(jià)值。給定搜索主題s，設(shè)頁面p中有一鏈接a，若a所指向的頁面q與主題s無關(guān)，但經(jīng)q依次訪問若干頁面后可獲得與s相關(guān)的頁面r，則稱頁面q具有與s相關(guān)的未來價(jià)值。根據(jù)未來價(jià)值的評(píng)價(jià)算法來預(yù)測(cè)指向頁面q的鏈接a與主題相關(guān)的程度，稱鏈接a與主題s相關(guān)的大小為Ms(a)的未來價(jià)值，一般用鞏固學(xué)習(xí)的方法來評(píng)價(jià)鏈接的未來價(jià)值。

定義3鏈接的綜合價(jià)值。給定搜索主題s，設(shè)頁面p中有一鏈接a，a關(guān)于s的立即價(jià)值為Is(a)，a關(guān)于s的未來價(jià)值為Ms(a)，則a關(guān)于s的綜合價(jià)值為

其中：α、 β為動(dòng)態(tài)權(quán)值，根據(jù)網(wǎng)絡(luò)蜘蛛在線獲得的Web狀態(tài)信息動(dòng)態(tài)調(diào)整。當(dāng)α=1、 β=0時(shí)，鏈接的綜合價(jià)值等于立即價(jià)值；當(dāng)α=0、 β=1時(shí)，鏈接的綜合價(jià)值即等于未來價(jià)值。公式表明：網(wǎng)絡(luò)蜘蛛對(duì)立即價(jià)值和未來價(jià)值的分配由α、 β決定，算法每次總是選擇綜合價(jià)值函數(shù)值最高的鏈接。

2基于動(dòng)力粒子群算法的網(wǎng)絡(luò)蜘蛛搜索策略

2．1Web資源分布與鏈接價(jià)值關(guān)系

近年的研究表明，Web拓?fù)浣Y(jié)構(gòu)呈現(xiàn)一張網(wǎng)的形式，頁面與頁面的超鏈對(duì)應(yīng)網(wǎng)中的弧，而網(wǎng)中的節(jié)點(diǎn)代表一個(gè)頁面，與某一主題相關(guān)的頁面以不同群聚群體的方式分散在網(wǎng)絡(luò)中，這些群體稱為Web社區(qū)。圖1中某一站點(diǎn)及與之緊密聯(lián)系的相關(guān)站點(diǎn)的信息[10]能基本反映某個(gè)主題。由于超鏈的存在，在網(wǎng)頁發(fā)布過程中可能會(huì)出現(xiàn)許多與之有一定的關(guān)聯(lián)但又與主題基本不相關(guān)的網(wǎng)頁，從而導(dǎo)致中心主題發(fā)生漂移；在網(wǎng)頁設(shè)計(jì)過程中不可能將所有相關(guān)網(wǎng)頁全部鏈接在一起，網(wǎng)頁中只包含了極少與主題相關(guān)的其他站點(diǎn)信息，這些資源信息組織在一起構(gòu)成了一個(gè)與主題相關(guān)的社區(qū)，Web信息資源分布的特征要求網(wǎng)絡(luò)蜘蛛能一方面能在整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中快速有效地找出這些分散的社區(qū)；另一方面在社區(qū)中搜索時(shí)盡可能地覆蓋所有相關(guān)頁面，即要求網(wǎng)絡(luò)蜘蛛在不同搜索階段采用不同的評(píng)價(jià)標(biāo)準(zhǔn)及不同的搜索策略，以提高整體搜索效率。

2．2算法思想

根據(jù)Web信息資源分布的群聚性特點(diǎn)，將搜索過程劃分為兩個(gè)部分，即探測(cè)(exploration)和發(fā)掘(exploitation)。在相關(guān)社區(qū)中搜索時(shí)要求網(wǎng)絡(luò)蜘蛛能高效地發(fā)掘出相關(guān)信息，也就是說當(dāng)在相關(guān)頁面集中搜索時(shí)，由于其中頁面和主題相關(guān)蘊(yùn)涵了較多的相關(guān)信息，鏈接的立即價(jià)值較大，適合選用注重發(fā)掘的基于立即價(jià)值的搜索策略；而在社區(qū)之間搜索時(shí)要求能快速地探測(cè)定位相關(guān)社區(qū)，亦即無關(guān)頁面集中可利用的相關(guān)信息少，鏈接的立即價(jià)值都很小，基于立即價(jià)值的網(wǎng)絡(luò)蜘蛛易迷失搜索方向，而基于未來價(jià)值的網(wǎng)絡(luò)蜘蛛注重探索，能利用經(jīng)驗(yàn)信息來預(yù)測(cè)鏈接的未來價(jià)值，適合引導(dǎo)搜索從無關(guān)社區(qū)過渡到相關(guān)社區(qū)。發(fā)掘與探測(cè)的權(quán)衡問題廣泛存在于機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)和遺傳算法等人工智能領(lǐng)域。網(wǎng)絡(luò)蜘蛛在其生命周期內(nèi)，必須能獨(dú)立地決定何時(shí)基于立即價(jià)值發(fā)掘資源，何時(shí)基于未來價(jià)值探測(cè)資源。綜合這兩種方法，筆者提出了一種結(jié)合動(dòng)力粒子群演化算法的啟發(fā)式搜索算法。實(shí)驗(yàn)表明，新算法具有很高搜索效率。

2．3動(dòng)力粒子群算法的網(wǎng)絡(luò)蜘蛛搜索的設(shè)計(jì)與實(shí)現(xiàn)

2．3．1基本粒子群算法PSO

PSO算法是一種源于鳥群捕食行為而發(fā)明的進(jìn)化計(jì)算技術(shù)，它首先在目標(biāo)函數(shù)空間生成隨機(jī)粒子，每個(gè)粒子代表優(yōu)化問題的一個(gè)可行解，它有自己的位置和速度，位置Xi=(xi1，xi2，…，xid)代表d維解空間的候選解，解的優(yōu)劣程度由適應(yīng)函數(shù)決定；速度Vi=(vi1，vi2，…，vid)決定第i個(gè)粒子在解空間搜索時(shí)單位迭代次數(shù)的位移。粒子在解空間運(yùn)動(dòng)，在粒子個(gè)體歷史最優(yōu)值Pi=(pi1，pi2，…，pid)和種群歷史最優(yōu)解Pg=(pg1，pg2，…，pgd)指導(dǎo)下更新其速度和位置，從而達(dá)到尋優(yōu)的目的[12，13]。迭代方程為

vid(t+1)=ωvid(t)+c1×rand1()×(lbest[i]d-xid)+

c2×rand2()(gbestd-xid)(3)

xid(t+1)=xid(t)+vid; 1≤i≤n， 1≤d≤D(4)

其中：ω為慣性權(quán)重，取值為0．729 8；rand1()和rand2()是隨機(jī)函數(shù)，在[0，1]內(nèi)產(chǎn)生隨機(jī)數(shù);c1和c2加速因子，取值為1．496；lbest[i]表示粒子i的鄰域最優(yōu)值，粒子鄰域由種群中索引號(hào)相鄰的五個(gè)粒子所組成；pbest[i]是優(yōu)化過程中所搜索到的當(dāng)前全局最優(yōu)粒子的位置。

2．3．2動(dòng)力學(xué)粒子群算法

動(dòng)力學(xué)演化算法DEA是2002年由李元香教授和鄒秀芬博士提出的，是基于統(tǒng)計(jì)物理中的自由能極小化原理而設(shè)計(jì)，引入動(dòng)量和活動(dòng)量的概念[14]，將種群看做一個(gè)動(dòng)力學(xué)系統(tǒng)，以一種獨(dú)特的選擇策略保持種群的多樣性[15]。

由于粒子群算法與熱力學(xué)系統(tǒng)有很多相似性，如熱力學(xué)系統(tǒng)能量最小化對(duì)應(yīng)粒子群算法中種群收斂到最小值，系統(tǒng)熵增過程對(duì)應(yīng)粒子群保持多樣性的過程等。針對(duì)標(biāo)準(zhǔn)PSO算法收斂速度較快，整個(gè)粒子群容易受當(dāng)前全局最優(yōu)粒子的強(qiáng)烈吸引聚集而陷入局部最優(yōu)的特性，筆者在動(dòng)力學(xué)算法思想的啟發(fā)下，借鑒統(tǒng)計(jì)力學(xué)中能量最小化時(shí)熵增概念，結(jié)合DEA中種群個(gè)體的動(dòng)態(tài)選擇機(jī)制，提出動(dòng)力學(xué)粒子群算法，以增加種群的多樣性，提高算法的全局搜索能力[16] 。

設(shè)動(dòng)力粒子群優(yōu)化算法的種群規(guī)模為n，記為x1，x2，…，xn，連續(xù)演化代數(shù)為時(shí)間t， f(t，xi)表示時(shí)間t時(shí)粒子xi的適應(yīng)值，稱為粒子i在時(shí)間t的狀態(tài)。

定義4p(t，xi)為粒子xi在時(shí)刻t時(shí)的動(dòng)量（Momentum）:

p(t，xi)=f(t，xi)-f(t-1，xi)(5)

定義5a(t，xi)為粒子xi在時(shí)刻t時(shí)的活動(dòng)量(activity)，如果粒子xi在時(shí)刻t時(shí)被選擇slct(t，xi)參加飛行，則a(t，xi)=a(t-1，xi)+1；否則a(t，xi)=a(t-1，xi)。

定義6新的自適應(yīng)動(dòng)態(tài)選擇表達(dá)式：

slct(t，xi)=∑tk=0|p(k，xi)|+λlog a(t，xi)(6)

其中：λ是一個(gè)可調(diào)參數(shù)（通常設(shè)為1．0）

式中第一項(xiàng)相當(dāng)于粒子的能量，當(dāng)粒子能量較小時(shí)在下一時(shí)刻被優(yōu)先選擇參加飛行，使系統(tǒng)最大限度地釋放或耗散能量，讓系統(tǒng)朝能量減少的方向發(fā)展，逼近最優(yōu)解。第二項(xiàng)相當(dāng)于熵，當(dāng)粒子活動(dòng)量較小時(shí)，slct(t，xi)的值較小，下一時(shí)刻優(yōu)先被選擇參加飛行，迫使系統(tǒng)的熵增加。由于粒子的活動(dòng)頻繁，種群中所有粒子均有機(jī)會(huì)被選擇參加飛行，但種群中較弱的粒子被選擇機(jī)會(huì)增多，使算法在解空間的探索區(qū)域增大，粒子在最優(yōu)區(qū)域停留時(shí)間增長(zhǎng)，提高了算法的局部搜索能力，避免了種群過快聚集，保持種群的多樣化。在本算法中，slct(t，xi)按照從小到大的次序排序，slct(t，xi)最小的粒子被選擇，保證每個(gè)粒子每個(gè)時(shí)刻都有機(jī)會(huì)被選擇參加飛行，且這種選擇機(jī)制是動(dòng)態(tài)的，一旦種群發(fā)現(xiàn)有好的全局個(gè)體，將被保留下來，以此來提高多樣性和全局搜索能力。

2．3．3編碼方案與適應(yīng)值函數(shù)的選取

動(dòng)力粒子群將待優(yōu)化的參數(shù)作為粒子的各個(gè)維，在優(yōu)化過程中通過粒子速度和位置的更新來改變待優(yōu)化的參數(shù)值，從而直接在解空間中搜索。對(duì)綜合價(jià)值函數(shù)參數(shù)的優(yōu)化實(shí)質(zhì)是對(duì)二維函數(shù)優(yōu)化，對(duì)綜合價(jià)值評(píng)估函數(shù)參數(shù)尋優(yōu)的粒子直接進(jìn)行編碼采用的形式為[α， β]。

粒子中每個(gè)變量均用實(shí)數(shù)表示，變量的取值范圍為[0，1]，通過算法在該范圍內(nèi)尋求上述變量的最優(yōu)解，以此使綜合價(jià)值評(píng)估函數(shù)值最大。

一組好的綜合價(jià)值評(píng)估函數(shù)控制參數(shù)α、 β組合能使網(wǎng)絡(luò)蜘蛛總是沿著價(jià)值最高的鏈接搜索，同時(shí)其優(yōu)化算法定義的適應(yīng)度函數(shù)值最大。因此本文采用的優(yōu)化評(píng)價(jià)標(biāo)準(zhǔn)是適應(yīng)度函數(shù)直接選取目標(biāo)函數(shù)：

g)算法結(jié)束。

3仿真實(shí)驗(yàn)

3．1實(shí)驗(yàn)方法

筆者選取了MIT、Princeton、Oxford、Toronto四所大學(xué)計(jì)算機(jī)系的網(wǎng)站作實(shí)際的搜索實(shí)驗(yàn)，搜索的目的是尋找本地服務(wù)器中的計(jì)算機(jī)論文，即將以“.PDF”“.PS”結(jié)尾的計(jì)算機(jī)論文定義為相關(guān)文檔。采用立即價(jià)值、未來價(jià)值和動(dòng)力粒子群三種不同搜索策略的網(wǎng)絡(luò)蜘蛛，在線統(tǒng)計(jì)Web網(wǎng)絡(luò)上與計(jì)算機(jī)相關(guān)的論文數(shù)，并計(jì)算各自的查準(zhǔn)率和查全率。

為了計(jì)算未來回報(bào)價(jià)值Ms(a)，先用基于增強(qiáng)學(xué)習(xí)的網(wǎng)絡(luò)蜘蛛對(duì)相似的計(jì)算機(jī)網(wǎng)絡(luò)進(jìn)行搜索，再建立文字/未來價(jià)值映射庫，將鏈接中所有文字的未來價(jià)值累加起來便是鏈接的未來價(jià)值[17]。為了計(jì)算鏈接的立即價(jià)值，本文采用FOLDOC在線計(jì)算機(jī)字典作為主題關(guān)鍵字集合[18]。其中包括13 000個(gè)計(jì)算機(jī)專業(yè)詞匯，并進(jìn)行了一些擴(kuò)充。用文獻(xiàn)[19]中所描述的相似度計(jì)算方法來計(jì)算鏈接周圍文字的立即價(jià)值，相似度的評(píng)價(jià)能采用以下公式：

3．3實(shí)驗(yàn)結(jié)果及性能分析

取四所大學(xué)的計(jì)算結(jié)果的平均值，分別繪出動(dòng)力粒子群算法與傳統(tǒng)的基于單一評(píng)價(jià)標(biāo)準(zhǔn)的算法之間的性能比較如圖。 

圖2中三種不同搜索策略在不同階段查全率不同。其原因是在尋找無關(guān)頁面集過程中，未來價(jià)值對(duì)預(yù)見遠(yuǎn)期回報(bào)很有幫助，這類網(wǎng)絡(luò)蜘蛛可以很快找到論文所在的目錄，因而早期的回報(bào)率很高。基于立即價(jià)值的網(wǎng)絡(luò)蜘蛛在找無關(guān)頁面集時(shí)容易迷失方向，開始找到論文目錄需要較長(zhǎng)時(shí)間，但它更注重開發(fā)，在主題相關(guān)的社區(qū)中的搜索效率卻很高，因而效率增長(zhǎng)很快，但在一個(gè)Web社區(qū)搜索完畢進(jìn)入另一個(gè)Web社區(qū)的能力較弱，查全率會(huì)降低。而基于動(dòng)力粒子群算法的網(wǎng)絡(luò)蜘蛛的性能優(yōu)勢(shì)顯著，除了在搜索初期其發(fā)現(xiàn)能力略低于基于未來價(jià)值的網(wǎng)絡(luò)蜘蛛外，其性能很快增長(zhǎng)并超過其他兩種算法，這一結(jié)果證實(shí)本文提出的啟發(fā)式搜索算法的有效性。

圖3中基于動(dòng)力粒子群算法的網(wǎng)絡(luò)蜘蛛的查準(zhǔn)率顯然高于其他兩者。除了最初階段，其余時(shí)間的查準(zhǔn)率均高于50%。其原因在于基于動(dòng)力粒子群算法的網(wǎng)絡(luò)蜘蛛采用了一種選擇機(jī)制，每次除選擇價(jià)值最優(yōu)的鏈接外，還挑選一些次優(yōu)的鏈接，即保證每一個(gè)粒子每一時(shí)刻都有機(jī)會(huì)被選擇參加飛行，一旦種群發(fā)現(xiàn)有好的全局最優(yōu)個(gè)體，將被保留下來，避免了局部最優(yōu)，這樣網(wǎng)絡(luò)蜘蛛依靠在線信息動(dòng)態(tài)調(diào)立即價(jià)值和未來價(jià)值的比重，從而獲得較高的查準(zhǔn)率。而基于未來價(jià)值的網(wǎng)絡(luò)蜘蛛具有一定的跨Web社區(qū)能力，但在跨越與主題無關(guān)的Web社區(qū)時(shí)采集了大量與主題無關(guān)的文檔，同時(shí)在主題相關(guān)的社區(qū)內(nèi)搜索時(shí)其搜索能力又比較低，因而查準(zhǔn)率相對(duì)較低。基于立即價(jià)值的網(wǎng)絡(luò)蜘蛛僅根據(jù)鏈接文本和鏈接結(jié)構(gòu)來指導(dǎo)爬行，在主題相關(guān)的Web社區(qū)里搜索能較準(zhǔn)確地找到相關(guān)論文，一旦跨越本社區(qū)時(shí)則常常會(huì)偏離主題，容易導(dǎo)致局部最優(yōu)。

4結(jié)束語

本文詳細(xì)分析研究了基于機(jī)器學(xué)習(xí)的網(wǎng)絡(luò)蜘蛛的兩大類算法，即基于立即價(jià)值和基于未來價(jià)值的算法，指出了這兩種算法優(yōu)勢(shì)與不足，提出了一種基于動(dòng)力粒子群算法的新的啟發(fā)式搜索算法。新算法充分考慮Web站點(diǎn)信息資源分布的特點(diǎn)，結(jié)合了兩類評(píng)價(jià)標(biāo)準(zhǔn)的優(yōu)勢(shì)，根據(jù)網(wǎng)絡(luò)蜘蛛實(shí)際搜索情況，在線調(diào)整兩種價(jià)值的權(quán)重，具有自適應(yīng)性。網(wǎng)絡(luò)蜘蛛在主題相關(guān)的Web社區(qū)搜索時(shí)適合選用基于立即價(jià)值的搜索策略，而在從無關(guān)社區(qū)過渡到相關(guān)社區(qū)的過程中提高未來價(jià)值的鏈接比重，既提高網(wǎng)絡(luò)蜘蛛跨越主題無關(guān)社區(qū)的能力，又提高了搜索相關(guān)主題文檔的精度。實(shí)驗(yàn)表明，新算法具有較高的性能。

參考文獻(xiàn)：

[1]SPERTUS E. ParaSite: mining structural information on the Web[J]. Computer Networks and ISDN Systems， 1997，29(8－13):1205－1215.

[2]BRA D P， HOUBEN G， KORNATZKY. Information retrieval in distributed hypertexts[C]//Proc of the 4th RIAO Conference. 1994:481-491.

[3]HERSOVICI M， HEYDON A， MITZEMACHER M. The shark－search algorithm－an application[C]//Proc of Tailored Web Site Mapping World Wide Web Conference. 1998.

[4]CHO J， GARCIA－Molina H， PAGE L. Efficient crawling through URL ordering[J]. Computer Networks， 1998，30(127):161－172.

[5]SRINIVASAN P，PANT G，MENCZER F，et al.Target seeking craw-lers and their topical performance[C]//Proc of SIGIR Conference on Research and Development in Information Retrieval.[S.l.]: ACM Press， 2002.

[6]ESTER M， GROB M， KRIEGEL H. Focused Web crawling: a gene-ric framework for specifying the user interest and for adaptive crawling strategies[C]//Proc of International Conference on Very Large Database(VLDB’01). 2001.

[7]CHAKRABARTI S， VAN DEN BERG M， DOM B. Focused crawling: a new approach to topic－specific Web resource discovery[J]. Computer Networks， 1999，31(11－16):1623－1640.

[8]SUTTON R S， BARTO A G. Reinforcement learning: an introduction[M]. MA: MIT Press， 1998.

[9]PANT G， SRINIVASAN P， MENCZER F， et al. Exploration versus exploitation in topic driven crawler[C]//Proc of WWW Workshop on Web Dynamics. 2002.

[10]陳治平.智能搜索引擎理論與應(yīng)用研究[D].長(zhǎng)沙:湖南大學(xué)，2003.

[11]唐志，王成良.遺傳算法在主題Web信息采集中的應(yīng)用研究[J].計(jì)算機(jī)科學(xué)， 2006，33(7):71-74.

[12]KENNEDY J， EBERHART R. Particle swarm optimization[C]//Proc of IEEE International Conference Neural Networks. 1995:1942－1948.

[13]SHI Y， EBERHART R C. A modified particle swarm optimizer[C]//Proc of IEEE International Conference Evolution Comput. Anchorage， Alaska:[s.n.]， 1998:69-73.

[14]LI Yuan－xiang， ZOU Xiu－fen. Solving global optimal problems by using a dynamical evolutionary algorithm[C]//Proc of the 5th International Conference on Algorithms and Architectures for Parallel Processing.[S.l.]: IEEE Press， 2002:170－173.

[15]LI Yuan－xiang， ZOU Xiu－fen， KAN Li－shuan. A new dynamical evolutionary algorithm from statistical mechanics[J]. Journal of Computer Science and Technology， 2002，18(3):361-368.

[16]ZHENG Bin－bin，LI Yuan－xiang，SHEN Xian－jun.A new dynamic particle swarm optimizer[C]//Proc of the 6th International Conference Simulated Evolution and Learning. 2006:481-488.

[17]RENNIE J， McCALLUM A. Using reinforcement learning to spider the Web efficiently[C]//Proc of International Conference on Machine Learning. 1999.

[18]免費(fèi)在線計(jì)算字典[EB/OL].(2003).http://www.foldoc.org/.

[19]MENCZER F， PANT G， SRINIVASAN P. Topic Web crawlers: eva-luation adaptive algorithms[C]//Proc of Appear in ACM Trans on Internet Technologies. 2003.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”