[摘要]主題爬行是專業(yè)搜索引擎的基礎(chǔ)，爬行策略與爬行算法是主題爬行技術(shù)的核心，通過分析主題爬行的基本原理，對爬行策略與爬行算法進行分類比較，展示爬行策略與爬行算法的研究進展及當(dāng)前研究熱點，為主題爬行技術(shù)的進一步研究提供參考。
　　[關(guān)鍵詞]搜索引擎　主題爬行　爬行策略　爬行算法
　　[分類號]TP391
　　
　　搜索引擎技術(shù)自誕生之日起就成為互聯(lián)網(wǎng)中最吸引人的技術(shù)之一，各種商業(yè)化的搜索引擎已經(jīng)成了人們使用互聯(lián)網(wǎng)時不可缺少的工具。傳統(tǒng)搜索引擎的工作原理是服務(wù)提供商利用網(wǎng)絡(luò)爬蟲(Web crawler，也被稱作網(wǎng)絡(luò)蜘蛛(Web spider)或網(wǎng)絡(luò)機器人(robot)，通過一些種子站點按照深度優(yōu)先或者廣度優(yōu)先的搜索策略對可以爬行到的資源進行掃描、下載，并將下載的信息以快照或全文方式存儲在數(shù)據(jù)庫中，建立相關(guān)索引，當(dāng)用戶在搜索引擎的用戶界面中輸入搜索關(guān)鍵字后，搜索引擎訪問數(shù)據(jù)庫，返回數(shù)據(jù)庫中與搜索關(guān)鍵字匹配的紀(jì)錄。隨著互聯(lián)網(wǎng)中網(wǎng)頁資源的快速增長，傳統(tǒng)的搜索引擎在某些方面的缺陷也越來越明顯：①搜索結(jié)果不夠全面。傳統(tǒng)搜索引擎希望鏡像整個Web世界，搜索引擎追求的是盡量多的處理及存儲網(wǎng)絡(luò)爬蟲爬回的網(wǎng)頁，但不同的搜索引擎由于受到服務(wù)器位置、網(wǎng)絡(luò)帶寬、爬行算法、服務(wù)器容量等因素的影響，服務(wù)器中存儲的資源是有限的，任何一個搜索引擎不可能存儲并索引網(wǎng)絡(luò)上所有的網(wǎng)頁信息。即使是全球最大的搜索引擎Google，其索引的頁面數(shù)量也僅占Web總量的40％左右。②搜索周期增加，影響信息的實效性。隨著Web資源的快速增長，傳統(tǒng)搜索引擎網(wǎng)絡(luò)爬蟲的爬行周期不斷增加，數(shù)據(jù)庫更新時間越來越長。每一個網(wǎng)頁都有自己的生命周期，網(wǎng)頁的更新速度可能會快于搜索引擎數(shù)據(jù)庫的更新速度，當(dāng)搜索引擎把數(shù)據(jù)庫中已經(jīng)過期的信息反饋給用戶時，用戶可能根本無法打開相關(guān)鏈接或者打開的是過期的網(wǎng)頁。③搜索結(jié)果的針對性不強。用戶輸入一個關(guān)鍵字后返回很多結(jié)果，但存在大量重復(fù)，很多結(jié)果并不是用戶需要的。通過對歐洲和美國9個主要的搜索引擎日志的統(tǒng)計分析，認(rèn)為用戶對于搜索結(jié)果的查看呈減少趨勢。普通用戶僅僅會察看搜索引擎返回的前若干條數(shù)據(jù)，對于其他搜索結(jié)果，很多用戶沒有耐性全部看完。不同專業(yè)背景的人，對于同一個關(guān)鍵詞的理解可能大相徑庭，同樣的“蘋果”一詞，有人可能理解成為食品，有人可能理解成為蘋果公司或者其IT產(chǎn)品。
　　鑒于傳統(tǒng)搜索引擎的這些缺陷，一些學(xué)者提出了垂直式搜索引擎的概念，即該搜索引擎不以爬行所有的Web頁面為目標(biāo)，僅僅在互聯(lián)網(wǎng)中快速爬行某一部分Web頁面并存儲，這樣的搜索引擎既可以節(jié)約網(wǎng)絡(luò)帶寬資源，又可以縮短搜索引擎數(shù)據(jù)庫的更新周期，使搜索引擎得到實時性更好的網(wǎng)頁。De Bra等最先提出的主題爬行(topic crawling)搜索引擎通過限定爬行主題，提高了搜索精度，成為垂直式搜索引擎的代表。主題爬行技術(shù)的核心是爬行策略與算法，本文從主題爬行技術(shù)的基本原理出發(fā)，對其策略進行分類，沿著爬行策略及算法的改進，分析了主題爬行策略與算法的研究熱點，為主題爬行技術(shù)的進一步研究提供參考。
　　
　　1　主題爬行原理
　　
　　主題爬行是在傳統(tǒng)網(wǎng)絡(luò)爬行技術(shù)基礎(chǔ)上，加入文本分類、聚類以及Web挖掘等相關(guān)技術(shù)用于捕獲特定主題的Web信息。主題爬行技術(shù)的應(yīng)用可以提高搜索精度，降低搜索引擎對網(wǎng)絡(luò)資源的占用，縮短搜索引擎數(shù)據(jù)庫的更新周期�；�于主題爬行技術(shù)的搜索引擎與傳統(tǒng)搜索引擎最大的區(qū)別在于：該搜索引擎的網(wǎng)絡(luò)爬蟲是面向主題的。傳統(tǒng)搜索引擎的網(wǎng)絡(luò)爬蟲在爬行過程中采用的是“通吃”策略，不分類別、不分內(nèi)容全部爬行并下載；基于主題的網(wǎng)絡(luò)爬蟲在爬行前或者爬行過程中根據(jù)已經(jīng)爬行的結(jié)果有選擇性的進行預(yù)測下一步爬行并下載。
　　主題爬行過程通常由三部分構(gòu)成：①分類器(clas―sifter)，主要對已抓取網(wǎng)頁的元素進行計算，判斷其主題相關(guān)度，確定是否對該網(wǎng)頁中所包含的超級鏈接進一步抓取；②提取器(distilIer)，該模塊存儲待下載隊列，并確定待下載隊列的優(yōu)先級；③爬行器(crawler)，該模塊在分類器和提取器的指導(dǎo)下，執(zhí)行網(wǎng)頁抓取工作。主題爬蟲的爬行過程為爬行器根據(jù)不同的爬行策略執(zhí)行爬行操作，抓取網(wǎng)頁送人分類器中，分類器對已經(jīng)抓取的網(wǎng)頁進行處理，根據(jù)設(shè)定主題及其域值判斷該網(wǎng)頁的主題相關(guān)性，結(jié)合其他參數(shù)，確定是否對該網(wǎng)頁包含的超級鏈接進一步爬行。如果爬行，則送入提取器中的隊列，由提取器根據(jù)隊列規(guī)則確定其爬行優(yōu)先極。Chakrabarti等人 1999年正式提出了個性化主題搜索引擎的概念，該搜索引擎不以傳統(tǒng)的關(guān)鍵詞作為搜索內(nèi)容，而是在某一限定范圍內(nèi)，通過計算Web頁面內(nèi)容與主題的相關(guān)性，決定主題爬蟲是否值得進一步搜索。其中，主題是由一些范例文檔來確定的，該主題爬蟲實時查找與文檔詞典有相關(guān)性的網(wǎng)頁，保證了搜索頁面的時效性與針對性。
　　
　　2　主題爬行基本爬行策略與算法
　　
　　主題爬行技術(shù)的核心是爬行的策略與算法，由于主題爬蟲與傳統(tǒng)網(wǎng)絡(luò)爬蟲在爬行目標(biāo)上有很大差別，因此，除了采用傳統(tǒng)網(wǎng)絡(luò)爬蟲的爬行策略之外，主題爬蟲在爬行過程中還要采用有效爬行策略與算法盡快爬到并抓取與主題相關(guān)的網(wǎng)頁。Sotiris Batsakis等人將主題爬行策略分成三類：經(jīng)典主題爬行策略、改進的主題爬行策略、基于語義的主題爬行策略。經(jīng)典爬行策略主要指主題爬行的“魚群搜索策略”(fish search)，改進的主題爬行策略主要指“鯊魚搜索策略”(sharksearch)、“最優(yōu)最先(best first)搜索策略”等。
　　魚群搜索策略是以“魚群搜索算法”(fish algo―rithm)為基礎(chǔ)的主題爬行策略，魚群搜索算法是一種基于群體動物行為的智能優(yōu)化算法，該算法模仿魚群在覓食和繁殖時的表現(xiàn)，動態(tài)調(diào)整種群的個數(shù)。在魚群搜索策略中，每個網(wǎng)頁相當(dāng)于一條魚，如果遇到滿足給定條件的相關(guān)網(wǎng)頁，則該魚繁殖小魚，并對該網(wǎng)頁發(fā)出的鏈接進一步探索；否則食物減少，如果一條魚的食物減為零，則該魚將停止尋食并放棄對該鏈接的爬行。魚群搜索策略中某一超級鏈接是否放人提取器中待下載，取決于該鏈接的父鏈接與主題的相關(guān)性。關(guān)于待下載鏈接與主題的相關(guān)性，De Bra L”提出了通過比較已下載網(wǎng)頁內(nèi)容與主題關(guān)鍵字是否匹配，引入二元分類方法(1代表相關(guān)，O代表不相關(guān))來計量相關(guān)性。
　　改進的主題爬行策略是基于魚群搜索策略基礎(chǔ)的改進，Hersoviei M”。提出采用向量空間模型(vectorspace model)來計量相關(guān)性，向量空間模型不以整數(shù)0、1來計量相關(guān)性，而是通過多個參數(shù)比較，采用O一1之間的實數(shù)來計量。該方法除了用已下載網(wǎng)頁內(nèi)容和主題關(guān)鍵詞是否簡單匹配來判斷相關(guān)性，還通過計算 錨文本(anchor)等其他參數(shù)與主題的相關(guān)性來計量。這種改進的搜索策略比魚群搜索策略在爬行的準(zhǔn)確率(precision rate)和召回率(recall rate)上有很大的進步，該搜索策略被稱之為“鯊魚搜索策略”(shark search)。在“鯊魚搜索策略”中，已下載網(wǎng)頁中頁面內(nèi)容、錨文本內(nèi)容、鏈接內(nèi)容(URL)及父頁(指向包含鏈接頁面的Web頁)的相關(guān)性等都作為主要參數(shù)用來計量待下載網(wǎng)頁與主題的相關(guān)性，通過計算確定待下載網(wǎng)頁是否進人提取器隊列中。關(guān)于參數(shù)向量的選擇，Cho J等提出了重要度向量，該重要度向量由幾個部分構(gòu)成：①已下載頁面逆文獻頻率法(inverse document frequency，IDF)的關(guān)鍵詞相關(guān)度；②已下載Web頁的重要鏈接指向個數(shù)(backlink count)；③已下載頁面指向鏈接的重要度值(pagerank)；⑧URL位置矩陣(10cation metrics)等四個參數(shù)作為衡量相關(guān)性的向量。
　　隨著研究的不斷深入，“鯊魚搜索策略”也不斷完善，該方法中向量空間模型的參數(shù)越多，相關(guān)性計量越準(zhǔn)確，但參數(shù)增加使計算量也隨之增加，因此，過多的參數(shù)對爬行速度有一定影響。但Zhumin Chen等”。對各種主題爬蟲的運行時間進行了實驗分析比較，該學(xué)者認(rèn)為，相對于網(wǎng)絡(luò)中的下載等待時間來說，相關(guān)性計算的時間很少，有時甚至不到下載時間的十分之一，因此頁面相關(guān)性的計算對爬行速度的影響是可以忽略的。在“鯊魚搜索策略”的基礎(chǔ)上，Menczer F等提出了“最優(yōu)最先”(best first)搜索策略，這一策略通過計算向量空間的相關(guān)性，把相關(guān)性“最好”的頁面放入最優(yōu)先下載的隊列，另外，“最優(yōu)最先”搜索策略采用了術(shù)語頻度(TF)值計算文本相似度，減少了部分計算量。根據(jù)文獻，由于只選擇與主題相關(guān)性很大的鏈接，而忽略某些當(dāng)前相關(guān)性不高但下級鏈接中包含很高相關(guān)性鏈接的網(wǎng)頁，最優(yōu)最先算法具有很大的貪婪性，該算法只能找到局部范圍內(nèi)的最優(yōu)解，難以得到全局范圍內(nèi)的最優(yōu)解。因此，該搜索策略只適用于小范圍內(nèi)的主題爬行，對于大范圍的主題爬行，容易過早地陷入Web空間中局部最優(yōu)子空間的陷阱。
　　作為一種有效表現(xiàn)概念層次結(jié)構(gòu)和語義的模型，本體論(ontology)被廣泛地應(yīng)用到計算機科學(xué)的眾多領(lǐng)域。美國斯坦福大學(xué)的知識系統(tǒng)實驗室學(xué)者TomGruber提出了本體是概念化的顯式表示，Studer在Gruber的基礎(chǔ)上擴展了本體的概念，提出本體是共享概念模型的明確形式化規(guī)范說明。本體具有良好的概念層次結(jié)構(gòu)和對邏輯推理的支持，可以解決信息源之間結(jié)構(gòu)和語義的異構(gòu)，W3C在2004年提出了Web本體語言(Web ontology language，OWL)的標(biāo)準(zhǔn)。基于本體的網(wǎng)絡(luò)爬蟲認(rèn)為概念上使用相似術(shù)語的頁面應(yīng)具有一定的相關(guān)性。M.Ehrig等學(xué)者將本體應(yīng)用于主題爬蟲的分離器中，首先通過定義術(shù)語的相關(guān)性，建立本體術(shù)語集合，通過對已下載網(wǎng)頁處理并對本體庫的比較分析，計算其相關(guān)性，確定是否將待下載鏈接放入分離器，提高了主題爬行的準(zhǔn)確度與召回率。Jason J.Jung提出基于語義主題爬行的開放式?jīng)Q策支持系統(tǒng)，該開放系統(tǒng)主要包括基于上下文語義的主題爬蟲通過域內(nèi)鏈接進行區(qū)域內(nèi)知識發(fā)現(xiàn)及知識的處理，為開放式?jīng)Q策支持系統(tǒng)迅速提供知識�；�于語義的主題爬行技術(shù)中，本體庫的構(gòu)建及完善是一項復(fù)雜的工作，因此應(yīng)用范圍有限。
　　
　　3　爬行策略與爬行算法的改進
　　
　　雖然魚群搜索策略、鯊魚搜索策略、最優(yōu)最先搜索策略是主題爬蟲常用的搜索策略，但由于互聯(lián)網(wǎng)中網(wǎng)站結(jié)構(gòu)的多樣性及復(fù)雜性，很多學(xué)者在主題爬行算法中嘗試采用其他的搜索算法實現(xiàn)較高準(zhǔn)確率與召回率。相繼提出了采用模糊算法、人工神經(jīng)網(wǎng)絡(luò)、遺傳算法、粗集理論等方法指導(dǎo)主題爬蟲的爬行過程。
　　作為最優(yōu)最先搜索策略的改進，李學(xué)勇等采用模擬退火算法作為爬行的啟發(fā)式搜索算法，與爬行中的“隧道技術(shù)”結(jié)合改進主題爬蟲。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機尋找目標(biāo)函數(shù)的全局最優(yōu)解。該算法在選擇優(yōu)化解方面具有非貪婪性，在爬蟲搜索過程中，每次除了選擇評價值最優(yōu)的鏈接，還以一定概率有限度地接收評價值次優(yōu)的鏈接，確保有一定價值的鏈接有機會被選中。“隧道技術(shù)”使爬蟲有機會穿過相關(guān)性低的區(qū)域進入相關(guān)性高的區(qū)域，當(dāng)頁面內(nèi)容的相關(guān)度低于設(shè)定的閾值時，通過擴大主題范圍，使更多的相關(guān)鏈接加入到鏈接優(yōu)先級隊列，提高相關(guān)網(wǎng)頁的召回率。模擬退火算法是一種隨機算法，雖然可以比較快地找到問題的近似最優(yōu)解，但不一定能找到全局的最優(yōu)解。因此，將模擬退火算法應(yīng)用于最優(yōu)最先搜索策略并不能完全保證主題爬行的魯棒性。
　　遺傳算法(genetic algorithm)是模擬生物進化論與遺傳學(xué)結(jié)合的計算模型，在最優(yōu)解搜索領(lǐng)域具有一定優(yōu)勢，自從密西根大學(xué)的Holland教授提出該算法后，由于其魯棒性、自組織性強等優(yōu)點，在很多方面有廣泛的應(yīng)用。Jialun Qin等學(xué)者采用遺傳算法實現(xiàn)主題爬蟲在特定域內(nèi)的爬行，通過初始化、內(nèi)容分析選擇、鏈接分析雜交、變異等幾個步驟實現(xiàn)主題爬蟲在特定域內(nèi)的爬行。根據(jù)文獻，該算法的應(yīng)用在某些Web頁的主題爬行中具有較好的準(zhǔn)確率與召回率。遺傳算法應(yīng)用于主題爬行技術(shù)中存在編碼方式的確定、適應(yīng)性函數(shù)的確定等問題，由于網(wǎng)站結(jié)構(gòu)、網(wǎng)頁類型的不同需要采取不同的標(biāo)準(zhǔn)。遺傳算法也存在局部最優(yōu)陷阱問題，單純使用遺傳算法進行主題爬行時也會存在無法穿越隧道的問題。
　　隱馬爾柯夫模型(HMM)作為一種統(tǒng)計分析模型，在信號識別等領(lǐng)域有廣泛的應(yīng)用，隱馬爾柯夫鏈在相關(guān)性評估應(yīng)用中具有一定優(yōu)勢。Hongyu Liu等提出基于隱馬爾柯夫模型的算法來評估待下載頁面與主題之間的相關(guān)性。該系統(tǒng)包括三個步驟：①進行數(shù)據(jù)收集；②依據(jù)相關(guān)性模式建模；③根據(jù)模型對待下載頁面評估并進行主題爬行。該算法的應(yīng)用可以提高主題爬蟲在分離器中的處理精度，但由于計算量的增加，會降低處理效率。
　　人工神經(jīng)網(wǎng)絡(luò)近來日益受到人們的關(guān)注，因為它特有的非線性、自適應(yīng)性、自學(xué)習(xí)性為解決復(fù)雜問題提供了一種相對比較有效的簡單方法。Hai-Tao Zhengr提出采用基于本體的人工神經(jīng)網(wǎng)絡(luò)(ANN)實現(xiàn)自學(xué)習(xí)爬行，系統(tǒng)框架分為三個步驟：①進行數(shù)據(jù)準(zhǔn)備；②通過現(xiàn)有的數(shù)據(jù)集對人工神經(jīng)網(wǎng)絡(luò)進行訓(xùn)l練；③將訓(xùn)練過的主題爬蟲應(yīng)用于實際爬行，取得較高的準(zhǔn)確率與召回率。人工神經(jīng)網(wǎng)絡(luò)存在訓(xùn)練時間長、學(xué)習(xí)算法的通用性低等缺點，所以，將人工神經(jīng)網(wǎng)絡(luò)應(yīng)用于主題爬行中，也存在樣本學(xué)習(xí)時間長，學(xué)習(xí)算法不具有通用性等缺點。因此，人工神經(jīng)網(wǎng)絡(luò)僅僅適用于小范圍的主題爬行。
　　除以上算法的改進，很多學(xué)者還嘗試采用其他計 算方法改善主題爬蟲的搜索性能，Suman Saha等。應(yīng)用粗集理論對未下載的Web頁面進行預(yù)測，判斷其與主題相關(guān)性，該方法提高了爬行頁面的準(zhǔn)確率，降低了噪聲。Huaxiang Zhang等提出利用Q學(xué)習(xí)及在線半監(jiān)督學(xué)習(xí)理論在待訪問的URL列表中選擇與主題最相關(guān)的URL，相關(guān)值的計算基于模糊理論及Q值理論。
　　雖然很多學(xué)者嘗試通過不同的軟計算方法改進主題爬蟲，但由于互聯(lián)網(wǎng)中網(wǎng)站結(jié)構(gòu)與網(wǎng)站內(nèi)容多樣復(fù)雜，這些算法往往應(yīng)用于某些網(wǎng)站時具有較高的準(zhǔn)確率與召回率，但是應(yīng)用于另一些網(wǎng)站時準(zhǔn)確率與召回率會下降。主題爬蟲的準(zhǔn)確率與召回率除了受網(wǎng)站結(jié)構(gòu)、主題爬蟲的爬行策略與算法等因素的影響，還受爬行入口位置、Web服務(wù)器性能等其他相關(guān)因素影響。
　　
　　4　主題爬行策略與算法的研究熱點
　　
　　鑒于主題爬行技術(shù)的不斷發(fā)展，主題爬行策略及算法也在不斷完善。目前關(guān)于主題爬行策略與算法的研究主要集中于以下幾個方面：①爬行策略與爬行算法的通用性研究�；ヂ�(lián)網(wǎng)中不同類型網(wǎng)站的網(wǎng)頁間組織形式相差很大，如何從已經(jīng)下載的網(wǎng)頁中高效、準(zhǔn)確地判斷待下載頁面與主題的相關(guān)性，并根據(jù)相關(guān)性修改下載隊列，是主題爬行技術(shù)能否成功的關(guān)鍵。目前主要通過修改爬行策略及利用各種軟計算方法來實現(xiàn)，但很多時候?qū)τ谀承┚W(wǎng)站具有很高的召回率和準(zhǔn)確率的方法，對于另一些網(wǎng)站可能并不適用。主題爬行的準(zhǔn)確率與召回率有時候與種子URL的起始位置等其他相關(guān)因素有很大關(guān)系。②“隧道技術(shù)”的研究。很多時候主題爬蟲需要穿過若干個與爬行主題相關(guān)性很低的頁面后才會發(fā)現(xiàn)一組與主題相關(guān)性很高的頁面群，穿越中間相關(guān)性很低的頁面需要隧道技術(shù)，如何實現(xiàn)隧道穿越、提高主題爬行準(zhǔn)確度是目前很多學(xué)者研究的內(nèi)容。③對于深度Web(deep Web)資源爬行策略的研究。許多深度Web資源存放在數(shù)據(jù)庫中，這些數(shù)據(jù)庫的訪問需要用戶名、密碼等信息，目前常采用半人工輔助方法使主題爬蟲訪問數(shù)據(jù)庫，如何快速、自動地發(fā)現(xiàn)這些數(shù)據(jù)庫并訪問這些深度Web資源，也是當(dāng)前主題爬行技術(shù)的研究熱點。
　　
　　5　結(jié)語、
　　
　　隨著人們對個性化信息服務(wù)需求的增長，專業(yè)搜索引擎的發(fā)展將成為搜索引擎發(fā)展的趨勢之一，主題爬行技術(shù)是專業(yè)搜索引擎的研究重點，也是數(shù)字圖書館、智能商業(yè)信息檢索的技術(shù)基礎(chǔ)。主題爬行技術(shù)的關(guān)鍵是如何讓網(wǎng)絡(luò)爬蟲迅速找到并抓取與主題相關(guān)的頁面，解決這一問題需要爬行策略與爬行算法的不斷改進。本文在分析主題爬行技術(shù)基本原理的基礎(chǔ)上，對現(xiàn)有的主題爬行策略及算法做了分類，系統(tǒng)分析、比較了不同爬行策略及算法的特點及優(yōu)缺點，對主題爬行技術(shù)的進一步研究進行了展望，以期為主題爬行技術(shù)的研究和主題搜索引擎的不斷完善提供一定參考。

相關(guān)熱詞搜索：爬行 算法 綜述 主題爬行策略與算法研究綜述 酒店營銷策略研究綜述 促銷策略研究文獻綜述