基于反向鏈接結(jié)合超鏈文本分析的定題搜索算法

基于反向鏈接結(jié)合超鏈文本分析的定題搜索算法

1定題搜索技術(shù)今天的世界是信息的世界。網(wǎng)絡(luò)信息資源正在迅速擴(kuò)張。如何快速檢索和獲取信息的需求信息已成為信息披露的最基本問題之一。網(wǎng)絡(luò)搜索引擎在網(wǎng)絡(luò)信息資源查找中起到了重要的作用,它可以幫助人們從數(shù)以億計(jì)的網(wǎng)絡(luò)信息中找到自己想要的信息。數(shù)據(jù)采集robot是搜索引擎的信息搜索代理,它順著超鏈接在網(wǎng)絡(luò)上爬行且將搜索到的網(wǎng)頁存儲到數(shù)據(jù)庫中。搜索引擎依靠robot的幫助獲取大量的網(wǎng)頁來進(jìn)行索引以供用戶查詢。目前常見的綜合型搜索引擎優(yōu)點(diǎn)是用戶可以查到范圍很廣的信息;不足之處在于由于其涉及領(lǐng)域太廣,因此在某些特定領(lǐng)域的查詢上則不夠深入和專業(yè)化。針對這種狀況,人們提出了對某一專題的定題搜索引擎,它可以在某些小范圍的領(lǐng)域取得比綜合型搜索引擎更滿意的結(jié)果,滿足了某些特定用戶的需要。采用定題搜索算法的Robot程序僅對給定主題相關(guān)的網(wǎng)頁文檔進(jìn)行搜集,搜索算法在訪問頁面之前進(jìn)行預(yù)測分析,能識別出這些頁面是否與主題相關(guān),決定是否采集或者制定采集的優(yōu)先順序,節(jié)約了網(wǎng)絡(luò)帶寬,提高信息搜索的效率。一個(gè)大型搜索引擎需要達(dá)到以下幾個(gè)要求:1)它必須要有一個(gè)好的爬行策略,即決定下一步要爬行那些網(wǎng)頁的策略,對于定題搜索引擎,這一點(diǎn)尤其重要。2)它必須要有一個(gè)高度優(yōu)化的系統(tǒng)結(jié)構(gòu),且健壯性、可控制性良好。對于定題搜索引擎,它還必須對下載的網(wǎng)頁進(jìn)行與搜索主題的相關(guān)度分析,以決定其是否符合定題搜索的要求。因此要有一個(gè)好的分析方法。本文以自主設(shè)計(jì)開發(fā)的定題搜索Robot系統(tǒng)NetBat2.02版為基礎(chǔ),詳細(xì)介紹它采用的一些關(guān)鍵技術(shù)與算法。2但是，搜索羅伯系統(tǒng)結(jié)構(gòu)2.1http條件分析本文所述的NetBat系統(tǒng),可以高效地采集與給定主題相關(guān)的信息。主要解決的問題有:系統(tǒng)結(jié)構(gòu)設(shè)計(jì)、搜索策略與算法、網(wǎng)頁相關(guān)度判斷等。當(dāng)給定相關(guān)主題及分類信息后,系統(tǒng)將在網(wǎng)絡(luò)上爬行搜索主題相關(guān)網(wǎng)頁,對下載下來的頁面進(jìn)行分析,決定存入數(shù)據(jù)庫或丟棄。NetBat2.02的界面如圖1所示。左圖為啟動時(shí),右圖為運(yùn)行時(shí)。2.2下載器的存儲系統(tǒng)的框架如圖2所示。中央控制器(CenterController)實(shí)現(xiàn)集中控制,各個(gè)下載器(DownloadAgent)并行采集。中央控制器根據(jù)當(dāng)前狀態(tài)和以前爬行的頁面來決定下一個(gè)要爬行的頁面,并且把所請求的URL流發(fā)給下載器,下載器把所請求的頁面下載下來并將其呈交給中央控制器來進(jìn)行分析和存儲。下載器數(shù)量動態(tài)可調(diào)。中央控制器的主要工作為以下內(nèi)容:●URL隊(duì)列管理:包括分配URL給下載器,合并下載器抽取出來的新URL列表等。●下載網(wǎng)頁的存儲:將下載頁面存儲到磁盤。●DNSCache管理:對已經(jīng)發(fā)現(xiàn)的網(wǎng)站,記錄IP地址,以后對此網(wǎng)站直接通過IP地址訪問,可以省去DNS解析的過程,加快爬行的速度。●機(jī)器人排斥協(xié)議及爬行速度控制:嚴(yán)格遵守REP(theRobotExclusionprotocol)協(xié)議,不訪問那些站點(diǎn)管理員不希望被爬行的頁面;以及通過輪詢與延時(shí)的方法避免對單一服務(wù)器短時(shí)間內(nèi)造成過大的負(fù)載。下載器的主要工作如下:●下載頁面,從中央控制器中得到請求的URL并將頁面取回?！矜溄映槿?取出該頁面的鏈接,將未被搜索的頁面鏈接加入到查詢隊(duì)列中?！耥撁娣治?抽取頁面特征,如title、hyperlink、AnchorText等信息及網(wǎng)頁相關(guān)度分析。3搜索策略與投降算法的決定3.1fish-搜索魚群搜索的研究方法定題信息搜索策略是定題搜索引擎技術(shù)的核心,現(xiàn)有的定題搜索策略中比較有代表性的算法主要有是Fish-Search算法和Shark-Search算法。Fish-Search魚群搜索算法由PaulDeBra提出,此算法模仿海中的魚群覓食現(xiàn)象,當(dāng)食物(即相關(guān)信息)找到時(shí),魚(即數(shù)據(jù)采集Robot)被繁殖繼續(xù)尋找食物,當(dāng)食物缺乏(即沒有相關(guān)信息)或者水被污染(即網(wǎng)絡(luò)帶寬不足)時(shí),魚死掉。算法具體細(xì)節(jié)如下:用戶給出搜索查詢條件及搜索起始URL,Robot動態(tài)建立一個(gè)后繼將要被訪問的URL(稱為節(jié)點(diǎn))的優(yōu)先級列表(開始被初始化為起始URL);搜索過程的每一步,列表的第一個(gè)節(jié)點(diǎn)被取出并訪問;每個(gè)被采集過的頁面通過分析判斷與用戶查詢的相關(guān)性(用0和1表示,1表示相關(guān),0表示不相關(guān)),并且頁面內(nèi)的超鏈URL(即這個(gè)頁面的子節(jié)點(diǎn))被抽取出來,將按照一定的規(guī)則插入待訪問URL列表中。每個(gè)待訪問的URL節(jié)點(diǎn)被賦予一個(gè)深度值和PotentialScore分值。如果頁面相關(guān),頁面子節(jié)點(diǎn)的深度值被賦予一個(gè)預(yù)定義的常數(shù),否則,子節(jié)點(diǎn)的深度值等于其父節(jié)點(diǎn)深度值減1。當(dāng)子節(jié)點(diǎn)的深度值為0時(shí),子節(jié)點(diǎn)對應(yīng)的URL不再插入到待搜索URL列表中,即此方向的搜索結(jié)束。對當(dāng)前正訪問頁面的每個(gè)子節(jié)點(diǎn),如果其深度值大于0,則根據(jù)以下的規(guī)則計(jì)算他們的PotentialScore分值:●對于相關(guān)節(jié)點(diǎn)的前α*width(α為大于1的預(yù)定值,width為預(yù)定義值)個(gè)孩子,PotentialScore為1;●對于不相關(guān)節(jié)點(diǎn)的前width個(gè)孩子,他們的PotentialScore為0.5;●對于其他子節(jié)點(diǎn),PotentialScore為0;根據(jù)子節(jié)點(diǎn)的PotentialScore值的大小順序,將子節(jié)點(diǎn)插入待搜索URL列表的相應(yīng)位置。Fish-Search魚群搜索算法的主要缺點(diǎn)是相關(guān)性計(jì)算過于簡單(只有0和1,即相關(guān)和不相關(guān)兩種),其次每個(gè)節(jié)點(diǎn)的PotentialScore精度不高,只有三種情況(0、0.5、1)。針對Fish-Search存在的問題,MichaelHersovici進(jìn)行改進(jìn),提出了Shark-Search算法,主要改進(jìn)了頁面和查詢q的相關(guān)度計(jì)算和PotentialScore的計(jì)算方法。具體改進(jìn)如下:●引入向量空間模型,計(jì)算頁面與用戶查詢之間的相似度,細(xì)化量度;●考慮超鏈附近文字AnchorText包含的提示信息,計(jì)算它與用戶提問之間的相似度;子節(jié)點(diǎn)的PotentialScore計(jì)算公式綜合考慮上述二個(gè)因素。3.2搜索和搜索網(wǎng)頁b、d、e上文論述的Fish-Search和Shark-Search算法雖然具有很強(qiáng)的搜索相關(guān)網(wǎng)頁的能力,但仍然存在一些問題。它們搜索路徑的選擇多基于如下假設(shè):相關(guān)或重要的網(wǎng)頁相互鏈接。事實(shí)上,存在許多相關(guān)網(wǎng)頁鏈接在不相關(guān)的網(wǎng)頁之后,使用這些算法將使這些網(wǎng)頁搜索優(yōu)先權(quán)偏低,甚至失去被搜索的機(jī)會。如圖3所示。目的是搜索與網(wǎng)頁A相關(guān)的其它網(wǎng)頁,經(jīng)過計(jì)算網(wǎng)頁B和網(wǎng)頁A相關(guān)度很低,可是網(wǎng)頁B所指向的網(wǎng)頁C、D、E都和網(wǎng)頁A相似度很高。不論是Fish-Search還是Shark-Search算法,都可能搜索不到網(wǎng)頁C、D、E。對于這個(gè)問題,我們的解決的思路是利用反向鏈接搜索算法結(jié)合超鏈附近文本分析。充分利用網(wǎng)頁A的隱含信息,找到有超鏈接指向A的網(wǎng)頁,也就是利用A的反方向鏈接(ReverseLink),對所有指向A的網(wǎng)頁分別根據(jù)它們的主題分類,最終的主題集合為{C1,C2,……,Cn},在搜索過程中,對于那些可以分類到{C1,C2,……,Cn}中的網(wǎng)頁,仍做進(jìn)一步的搜索。因?yàn)閷儆谶@些類別的網(wǎng)頁很可能會指向與A非常相似的網(wǎng)頁。對于仍然不在搜索范圍內(nèi)的網(wǎng)頁中提取出來的超鏈,分析其超鏈附近文本,如出現(xiàn)與主題相關(guān)的概念,則將其加入到URL列表,其余超鏈將其丟棄。我們稱該算法為ReverseLinkandHyperLinkAnalyze-BasedSearch,實(shí)現(xiàn)過程如圖4所示。4網(wǎng)絡(luò)相關(guān)性分析vsm算法4.1特征空間坐標(biāo)系的確定搜索引擎根源是傳統(tǒng)全文檢索技術(shù),沿用了傳統(tǒng)的信息檢索模型。傳統(tǒng)的計(jì)算文檔相似度的算法中,Salton教授提出的向量空間模型(VectorSpaceModel)應(yīng)用最為廣泛。在向量空間模型中,信息庫中的每一篇文獻(xiàn)都參照文獻(xiàn)庫特征屬性向量T=(t1,t2,……,tm)標(biāo)引成相應(yīng)的文獻(xiàn)向量:di=[wi1,wi2,…,wim](1)式中,m表示索引詞的個(gè)數(shù),wij表示詞項(xiàng)tj在文檔di中出項(xiàng)的次數(shù),即詞頻。同樣,用戶檢索提問也被表示成向量形式。由此文檔信息的匹配問題則轉(zhuǎn)化成了向量空間中的矢量匹配問題,向量間的夾角代表向量的相似度。其相似度計(jì)算如下:sv(q,di)=∑k=1twqkwik∑k=1tw2qk∑k=1tw2ikue001?ue000ue000(2)為了計(jì)算特征詞在文本中的權(quán)重,Salton提出了TF-IDF公式:wik=tfik?IDFk=tfik?log(Nnk+0.5)(3)公式中,tfik表示特征詞tk在文檔di中的詞頻,nk表示文檔庫中包含特征詞tk的文檔總數(shù),N為文檔庫的文檔總數(shù)。TF-IDF公式的依據(jù)是:某一個(gè)特征詞在一篇文獻(xiàn)中頻繁出現(xiàn),則在與其主題相似的文獻(xiàn)中,特征詞的出現(xiàn)次數(shù)也會很多,反之亦然。由此,詞頻TF被選作為特征空間坐標(biāo)系的重要測度,用于體現(xiàn)同類文本的特點(diǎn)。此外,考慮單詞區(qū)別不同類別的能力,發(fā)現(xiàn)單詞出現(xiàn)的的文本頻數(shù)越小,其區(qū)別不同類別的能力就越大,由此引入逆文本頻度IDF的概念,以TF與IDF的乘積作為權(quán)重的測度。4.2網(wǎng)頁內(nèi)容的性質(zhì)由于網(wǎng)頁采用了半結(jié)構(gòu)化的HTML語言,包含有豐富的結(jié)構(gòu)信息,在抽取網(wǎng)頁的主題內(nèi)容時(shí)應(yīng)加以利用。位于<head>、<title>、<meta>以及<ahref=...>等標(biāo)記之內(nèi)的關(guān)鍵詞無疑應(yīng)該加以重視,賦予不同的權(quán)重評測系數(shù)。本文在對大量網(wǎng)頁的實(shí)際操作中發(fā)現(xiàn),在諸多網(wǎng)頁標(biāo)記中最能夠反映網(wǎng)頁內(nèi)容的并不是直觀認(rèn)為的<title>或者<meta>間的文字,而是<ahref=...>與</a>之間的超鏈文字。這主要是因?yàn)樵S多網(wǎng)頁的<title>并非經(jīng)過作者的仔細(xì)推敲,有的是由網(wǎng)頁制作工具自動生成(比如為index1,index2等),有的是作者賦以與主題無關(guān)的title(如“歡迎你的到來”),還有的是為了提升在搜索引擎結(jié)果中的排名,而故意欺騙Spider(這種現(xiàn)象被成為“spiderpersuasion”)。尤其是在<meta>標(biāo)記中,對Spider的欺騙更為常見。所以對于關(guān)鍵詞在網(wǎng)頁中的權(quán)重修改如下:Wij=tfij×log(Ndfj+0.5)×func(tj)(4)其中,func(tj)的取值為:5.1實(shí)驗(yàn)結(jié)果分析本文對于經(jīng)典搜索算法的不足,提出了基于反向鏈接和超鏈文本分析的定題搜索算法,現(xiàn)對其進(jìn)行實(shí)驗(yàn),以檢測算法的性能。我們選用普通搜索引擎最常用的廣度優(yōu)先算法(Breadth-FirstAlgorithm)和定題搜索中經(jīng)典的Shark-Search算法來對比實(shí)驗(yàn)。采用不同搜索算法的Robot依次對給定主題進(jìn)行搜索,下載的網(wǎng)頁根據(jù)網(wǎng)頁相關(guān)度分析算法來計(jì)算與主題的相似度。實(shí)驗(yàn)的分析結(jié)果如圖5所示。結(jié)果表明本文所提出的算法相比其它兩種算法能夠顯著地提高搜索到的相關(guān)網(wǎng)頁數(shù)目,提高了定題搜索的效率。5.2算法的折歸與應(yīng)用從上面的實(shí)驗(yàn)結(jié)果,可以看出,雖然我們的算法效率有所改善,下載的網(wǎng)頁中目標(biāo)網(wǎng)頁數(shù)量仍只有約2.5%左右。還不夠理想,究其原因,為了保證查全率,我們把相關(guān)網(wǎng)頁中獲取的所有超鏈都進(jìn)行下載,而其中自然有大量的無關(guān)鏈接或廣告鏈接,影響了效率。于是實(shí)際運(yùn)行時(shí),對算法進(jìn)行了折衷,對超鏈而不是網(wǎng)頁,來進(jìn)行反向鏈接分析:即對所有指向相關(guān)頁面的超鏈的附近文本分別根據(jù)它們的主題分類,最終的主題集合為{C1,C2,……,Cn},在搜索過程中,對于那些可以分類到{C1,C2,……,Cn}中的超鏈,則下載其頁面。這樣做的好處是可以更快獲得更多的相關(guān)頁面,不利之處在于由于超鏈附近文本文字?jǐn)?shù)量比較少,分類常有不準(zhǔn)確的地方,因此很有可能漏掉一些相關(guān)頁面。對此問題進(jìn)行了搜索測試,實(shí)際運(yùn)行后進(jìn)行比較,完全相同的初始條件,折衷后的算法下載到的目標(biāo)網(wǎng)頁與總數(shù)之比大約為43%,效率提高了近20倍;而與原來相比,大約會漏掉15%左右的相關(guān)頁面,考慮到效率的巨大提高,這樣做應(yīng)是值得的。對于遺漏有效頁面的問題,考慮先快速建成數(shù)據(jù)庫以后,再使用前一種算法進(jìn)行擴(kuò)充搜索。5.3下載速度比較我們采用Win2000的操作系統(tǒng),P41GCPU的計(jì)算機(jī)運(yùn)行NetBat系統(tǒng),進(jìn)行“鋼鐵”領(lǐng)域內(nèi)的主題信息檢索。給定Google上以“鋼鐵”為關(guān)鍵詞查詢所得前20個(gè)頁面以及補(bǔ)充的數(shù)個(gè)知名鋼鐵相關(guān)網(wǎng)站主頁作為種子URL,考慮到系統(tǒng)運(yùn)行大量時(shí)間損耗在等待服務(wù)器響應(yīng)上,決定使用較多的下載器,共25個(gè)并行,以提高效率。系統(tǒng)運(yùn)行了11個(gè)小時(shí)以后,得到表1所示數(shù)據(jù)。單純從性能上來說,這個(gè)下載速度比起Google等知名系統(tǒng)并不是很快,但考慮到這是單機(jī)運(yùn)行,且定題搜索算法較復(fù)雜,需要做比較多相關(guān)方面的運(yùn)算工作,再加上網(wǎng)絡(luò)帶寬的因素,應(yīng)該說這個(gè)速度可以令人滿意了。而且定題搜索最重要的應(yīng)該是準(zhǔn)確地搜索到主題相關(guān)