基于動力粒子群算法的網絡蜘蛛搜索策略研究
2008-01-01 00:00:00童亞拉李元香沈顯君
計算機應用研究 2008年5期
摘要：傳統的基于單一價值評價的網絡蜘蛛搜索策略存在主題漂移，不能有效利用鏈接結構信息，容易迷失方向，過于依賴關鍵詞集等不足。提出一種基于動力粒子群算法的啟發式網絡蜘蛛搜索算法，新算法充分考慮Web站點信息資源分布的特點，給合了兩類評價標準的優勢，根據實際的搜索情況，在線調整兩種價值的權重，具有自適應性。實驗表明，新算法具有較高的查全率和查準率，能較好地解決現存問題。
關鍵詞：網絡蜘蛛； Web社區； 動力粒子群； 立即價值； 未來價值
中圖分類號：TP311.1文獻標志碼：A
文章編號：1001-3695(2008)05-1374-04
0引言
網絡蜘蛛是垂直搜索引擎中最重要的一個組成部分，是一種智能化軟件，其任務是獲取符合要求的Web頁面返給用戶或保存在索引庫中，并決定鏈接訪問順序。如何全面而準確地采集特定領域的相關內容是垂直搜索引擎的一個研究重點。網絡蜘蛛常采用最好優先原則即每次選擇最有價值的鏈接進行訪問，因此一些啟發式規則被運用到搜索策略的研究之中，如1999年Chakrabarti等人采用鞏固學習的方法來對即將爬行的網頁作出智能性判斷與選擇；2001年Chau和Chen等人用 Hopfield網絡學習與競爭機制實現Hopfield Net Spider；2002年王靖等人和2004年李學勇等人報告了基于模擬退火機制的網絡蜘蛛，這些在某種程度提高了網絡蜘蛛的智能化程度。
本質上說，網絡蜘蛛的搜索問題是一個多目標規劃問題，在合理的時間限度內，以較少的網絡資源、存儲資源和計算資源獲得更多的主題相關頁面。網絡蜘蛛研究的核心是解決頁面和URL的主題相關性判別問題，因此如何評價鏈接價值是決定此類網絡蜘蛛爬行效率的關鍵。鏈接價值評價算法可分為兩類，即基于立即回報價值（簡稱立即價值）和基于未來回報價值（簡稱未來價值）的評價算法。
基于立即價值的評價算法主要是依據搜索時在線獲得的文本或Web結構信息來對鏈接頁面的重要性進行預測。文獻[1~4]通過對頁面間相互引用關系的分析和計算主題與鏈接文本內容的相似度大小來確定鏈接的重要性，進而決定鏈接訪問順序。這類方法優點是理論基礎較好，計算簡單，在距離相關頁面較近的地方搜索時表現出良好的性能[5]，但也存在一些缺陷：頁面文本缺乏全局性，很難反映Web的整體情況，網絡蜘蛛在距離相關頁面集較遠搜索時易迷失方向[6]；忽略了半結構文檔所蘊涵的許多信息；評價的準確性依賴對主題關鍵字集的選擇和構建[7]。基于未來價值的評價算法利用Web上信息資源分布的某種程度的相似性，先對網絡蜘蛛進行訓練，使其具備一些經驗信息，對未來搜索具有一定的傾向性，目前代表性的方法是基于鞏固學習的搜索策略[8]，這類搜索策略能發掘鏈接文本中隱含的結構信息，但其預測能力有限，且這種離線訓練方式需要選擇典型站點或種子集，加重了用戶的負擔，更重要的是搜索時不靈活，搜索不集中，容易引起主題漂移。考慮到采用單一評價方法不能有效預測鏈接的真實價值，近年來有學者提出了基于綜合價值評價的搜索策略，如文獻[9]綜合了基于內容和鏈接結構的評價方法，提出了混合評價機制；文獻[10]提出了結合模擬退火的啟發式搜索算法來調節立即回報價值和未來回報價值的信任度比例；文獻[11]報告了一種改進遺傳算法來動態調整兩種策略的權重，這些算法的實驗表明采用基于綜合價值評價的搜索策略可有效提高搜索效率。
本文在分析了兩類評價方法并參考相關學者研究成果的基礎上，在動力粒子群框架內提出了一種基于綜合價值的網絡蜘蛛搜索算法，它利用了Web資源分布與鏈接價值關系，將基于立即價值和未來價值的評價方法相結合，在信息采集過程中動態地改變立即價值和未來價值在綜合價值中的比例關系，從而改進網絡蜘蛛的性能。
1預備知識
為了方便描述鏈接價值間關系的挖掘方法，先給出相關定義：
定義1鏈接的立即價值。給定搜索主題s，設頁面p中有一鏈接a，若a所指向的頁面q與主題s相關，則稱頁面q具有與主題s相關的立即價值；根據立即價值的評價算法來預測的鏈接a所指向頁面q與主題相關的程度，稱鏈接a與主題s相關的大小為Is(a)的立即價值，通常利用文本相似度或Web結構信息來獲得鏈接的立即價值。
定義2鏈接的未來價值。給定搜索主題s，設頁面p中有一鏈接a，若a所指向的頁面q與主題s無關，但經q依次訪問若干頁面后可獲得與s相關的頁面r，則稱頁面q具有與s相關的未來價值。根據未來價值的評價算法來預測指向頁面q的鏈接a與主題相關的程度，稱鏈接a與主題s相關的大小為Ms(a)的未來價值，一般用鞏固學習的方法來評價鏈接的未來價值。
定義3鏈接的綜合價值。給定搜索主題s，設頁面p中有一鏈接a，a關于s的立即價值為Is(a)，a關于s的未來價值為Ms(a)，則a關于s的綜合價值為
其中：α、 β為動態權值，根據網絡蜘蛛在線獲得的Web狀態信息動態調整。當α=1、 β=0時，鏈接的綜合價值等于立即價值；當α=0、 β=1時，鏈接的綜合價值即等于未來價值。公式表明：網絡蜘蛛對立即價值和未來價值的分配由α、 β決定，算法每次總是選擇綜合價值函數值最高的鏈接。
2基于動力粒子群算法的網絡蜘蛛搜索策略
2．1Web資源分布與鏈接價值關系
近年的研究表明，Web拓撲結構呈現一張網的形式，頁面與頁面的超鏈對應網中的弧，而網中的節點代表一個頁面，與某一主題相關的頁面以不同群聚群體的方式分散在網絡中，這些群體稱為Web社區。圖1中某一站點及與之緊密聯系的相關站點的信息[10]能基本反映某個主題。由于超鏈的存在，在網頁發布過程中可能會出現許多與之有一定的關聯但又與主題基本不相關的網頁，從而導致中心主題發生漂移；在網頁設計過程中不可能將所有相關網頁全部鏈接在一起，網頁中只包含了極少與主題相關的其他站點信息，這些資源信息組織在一起構成了一個與主題相關的社區，Web信息資源分布的特征要求網絡蜘蛛能一方面能在整個網絡拓撲結構中快速有效地找出這些分散的社區；另一方面在社區中搜索時盡可能地覆蓋所有相關頁面，即要求網絡蜘蛛在不同搜索階段采用不同的評價標準及不同的搜索策略，以提高整體搜索效率。
2．2算法思想
根據Web信息資源分布的群聚性特點，將搜索過程劃分為兩個部分，即探測(exploration)和發掘(exploitation)。在相關社區中搜索時要求網絡蜘蛛能高效地發掘出相關信息，也就是說當在相關頁面集中搜索時，由于其中頁面和主題相關蘊涵了較多的相關信息，鏈接的立即價值較大，適合選用注重發掘的基于立即價值的搜索策略；而在社區之間搜索時要求能快速地探測定位相關社區，亦即無關頁面集中可利用的相關信息少，鏈接的立即價值都很小，基于立即價值的網絡蜘蛛易迷失搜索方向，而基于未來價值的網絡蜘蛛注重探索，能利用經驗信息來預測鏈接的未來價值，適合引導搜索從無關社區過渡到相關社區。發掘與探測的權衡問題廣泛存在于機器學習、神經網絡和遺傳算法等人工智能領域。網絡蜘蛛在其生命周期內，必須能獨立地決定何時基于立即價值發掘資源，何時基于未來價值探測資源。綜合這兩種方法，筆者提出了一種結合動力粒子群演化算法的啟發式搜索算法。實驗表明，新算法具有很高搜索效率。
2．3動力粒子群算法的網絡蜘蛛搜索的設計與實現
2．3．1基本粒子群算法PSO
PSO算法是一種源于鳥群捕食行為而發明的進化計算技術，它首先在目標函數空間生成隨機粒子，每個粒子代表優化問題的一個可行解，它有自己的位置和速度，位置Xi=(xi1，xi2，…，xid)代表d維解空間的候選解，解的優劣程度由適應函數決定；速度Vi=(vi1，vi2，…，vid)決定第i個粒子在解空間搜索時單位迭代次數的位移。粒子在解空間運動，在粒子個體歷史最優值Pi=(pi1，pi2，…，pid)和種群歷史最優解Pg=(pg1，pg2，…，pgd)指導下更新其速度和位置，從而達到尋優的目的[12，13]。迭代方程為
vid(t+1)=ωvid(t)+c1×rand1()×(lbest[i]d-xid)+
c2×rand2()(gbestd-xid)(3)
xid(t+1)=xid(t)+vid; 1≤i≤n， 1≤d≤D(4)
其中：ω為慣性權重，取值為0．729 8；rand1()和rand2()是隨機函數，在[0，1]內產生隨機數;c1和c2加速因子，取值為1．496；lbest[i]表示粒子i的鄰域最優值，粒子鄰域由種群中索引號相鄰的五個粒子所組成；pbest[i]是優化過程中所搜索到的當前全局最優粒子的位置。
2．3．2動力學粒子群算法
動力學演化算法DEA是2002年由李元香教授和鄒秀芬博士提出的，是基于統計物理中的自由能極小化原理而設計，引入動量和活動量的概念[14]，將種群看做一個動力學系統，以一種獨特的選擇策略保持種群的多樣性[15]。
由于粒子群算法與熱力學系統有很多相似性，如熱力學系統能量最小化對應粒子群算法中種群收斂到最小值，系統熵增過程對應粒子群保持多樣性的過程等。針對標準PSO算法收斂速度較快，整個粒子群容易受當前全局最優粒子的強烈吸引聚集而陷入局部最優的特性，筆者在動力學算法思想的啟發下，借鑒統計力學中能量最小化時熵增概念，結合DEA中種群個體的動態選擇機制，提出動力學粒子群算法，以增加種群的多樣性，提高算法的全局搜索能力[16] 。
設動力粒子群優化算法的種群規模為n，記為x1，x2，…，xn，連續演化代數為時間t， f(t，xi)表示時間t時粒子xi的適應值，稱為粒子i在時間t的狀態。
定義4p(t，xi)為粒子xi在時刻t時的動量（Momentum）:
p(t，xi)=f(t，xi)-f(t-1，xi)(5)
定義5a(t，xi)為粒子xi在時刻t時的活動量(activity)，如果粒子xi在時刻t時被選擇slct(t，xi)參加飛行，則a(t，xi)=a(t-1，xi)+1；否則a(t，xi)=a(t-1，xi)。
定義6新的自適應動態選擇表達式：
slct(t，xi)=∑tk=0|p(k，xi)|+λlog a(t，xi)(6)
其中：λ是一個可調參數（通常設為1．0）
式中第一項相當于粒子的能量，當粒子能量較小時在下一時刻被優先選擇參加飛行，使系統最大限度地釋放或耗散能量，讓系統朝能量減少的方向發展，逼近最優解。第二項相當于熵，當粒子活動量較小時，slct(t，xi)的值較小，下一時刻優先被選擇參加飛行，迫使系統的熵增加。由于粒子的活動頻繁，種群中所有粒子均有機會被選擇參加飛行，但種群中較弱的粒子被選擇機會增多，使算法在解空間的探索區域增大，粒子在最優區域停留時間增長，提高了算法的局部搜索能力，避免了種群過快聚集，保持種群的多樣化。在本算法中，slct(t，xi)按照從小到大的次序排序，slct(t，xi)最小的粒子被選擇，保證每個粒子每個時刻都有機會被選擇參加飛行，且這種選擇機制是動態的，一旦種群發現有好的全局個體，將被保留下來，以此來提高多樣性和全局搜索能力。
2．3．3編碼方案與適應值函數的選取
動力粒子群將待優化的參數作為粒子的各個維，在優化過程中通過粒子速度和位置的更新來改變待優化的參數值，從而直接在解空間中搜索。對綜合價值函數參數的優化實質是對二維函數優化，對綜合價值評估函數參數尋優的粒子直接進行編碼采用的形式為[α， β]。
粒子中每個變量均用實數表示，變量的取值范圍為[0，1]，通過算法在該范圍內尋求上述變量的最優解，以此使綜合價值評估函數值最大。
一組好的綜合價值評估函數控制參數α、 β組合能使網絡蜘蛛總是沿著價值最高的鏈接搜索，同時其優化算法定義的適應度函數值最大。因此本文采用的優化評價標準是適應度函數直接選取目標函數：
g)算法結束。
3仿真實驗
3．1實驗方法
筆者選取了MIT、Princeton、Oxford、Toronto四所大學計算機系的網站作實際的搜索實驗，搜索的目的是尋找本地服務器中的計算機論文，即將以“.PDF”“.PS”結尾的計算機論文定義為相關文檔。采用立即價值、未來價值和動力粒子群三種不同搜索策略的網絡蜘蛛，在線統計Web網絡上與計算機相關的論文數，并計算各自的查準率和查全率。
為了計算未來回報價值Ms(a)，先用基于增強學習的網絡蜘蛛對相似的計算機網絡進行搜索，再建立文字/未來價值映射庫，將鏈接中所有文字的未來價值累加起來便是鏈接的未來價值[17]。為了計算鏈接的立即價值，本文采用FOLDOC在線計算機字典作為主題關鍵字集合[18]。其中包括13 000個計算機專業詞匯，并進行了一些擴充。用文獻[19]中所描述的相似度計算方法來計算鏈接周圍文字的立即價值，相似度的評價能采用以下公式：
3．3實驗結果及性能分析
取四所大學的計算結果的平均值，分別繪出動力粒子群算法與傳統的基于單一評價標準的算法之間的性能比較如圖。
圖2中三種不同搜索策略在不同階段查全率不同。其原因是在尋找無關頁面集過程中，未來價值對預見遠期回報很有幫助，這類網絡蜘蛛可以很快找到論文所在的目錄，因而早期的回報率很高。基于立即價值的網絡蜘蛛在找無關頁面集時容易迷失方向，開始找到論文目錄需要較長時間，但它更注重開發，在主題相關的社區中的搜索效率卻很高，因而效率增長很快，但在一個Web社區搜索完畢進入另一個Web社區的能力較弱，查全率會降低。而基于動力粒子群算法的網絡蜘蛛的性能優勢顯著，除了在搜索初期其發現能力略低于基于未來價值的網絡蜘蛛外，其性能很快增長并超過其他兩種算法，這一結果證實本文提出的啟發式搜索算法的有效性。
圖3中基于動力粒子群算法的網絡蜘蛛的查準率顯然高于其他兩者。除了最初階段，其余時間的查準率均高于50%。其原因在于基于動力粒子群算法的網絡蜘蛛采用了一種選擇機制，每次除選擇價值最優的鏈接外，還挑選一些次優的鏈接，即保證每一個粒子每一時刻都有機會被選擇參加飛行，一旦種群發現有好的全局最優個體，將被保留下來，避免了局部最優，這樣網絡蜘蛛依靠在線信息動態調立即價值和未來價值的比重，從而獲得較高的查準率。而基于未來價值的網絡蜘蛛具有一定的跨Web社區能力，但在跨越與主題無關的Web社區時采集了大量與主題無關的文檔，同時在主題相關的社區內搜索時其搜索能力又比較低，因而查準率相對較低。基于立即價值的網絡蜘蛛僅根據鏈接文本和鏈接結構來指導爬行，在主題相關的Web社區里搜索能較準確地找到相關論文，一旦跨越本社區時則常常會偏離主題，容易導致局部最優。
4結束語
本文詳細分析研究了基于機器學習的網絡蜘蛛的兩大類算法，即基于立即價值和基于未來價值的算法，指出了這兩種算法優勢與不足，提出了一種基于動力粒子群算法的新的啟發式搜索算法。新算法充分考慮Web站點信息資源分布的特點，結合了兩類評價標準的優勢，根據網絡蜘蛛實際搜索情況，在線調整兩種價值的權重，具有自適應性。網絡蜘蛛在主題相關的Web社區搜索時適合選用基于立即價值的搜索策略，而在從無關社區過渡到相關社區的過程中提高未來價值的鏈接比重，既提高網絡蜘蛛跨越主題無關社區的能力，又提高了搜索相關主題文檔的精度。實驗表明，新算法具有較高的性能。
參考文獻：
[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]陳治平.智能搜索引擎理論與應用研究[D].長沙:湖南大學，2003.
[11]唐志，王成良.遺傳算法在主題Web信息采集中的應用研究[J].計算機科學， 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]免費在線計算字典[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.
“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
