2.4 網頁搜索算法

2.4.1 網頁特征選取

1．主題描述方式

主題蜘蛛需要對搜索目標的主題進行描述，主題描述方式可以分為基于目標網頁特征、基于目標數據模式和基于領域概念等三種。

在基于目標網頁特征的描述方式中，網絡蜘蛛的搜索對象通常是網頁，網頁特征可以是網頁的內容特征，也可以是網頁的鏈接結構特征等。種子樣本獲取方式可以分為如下三種：

（1）預先給定的初始種子樣本。

（2）預先給定的網頁分類目錄以及與分類目錄對應的種子樣本。

（3）通過用戶行為確定的搜索目標樣例，包括用戶瀏覽過程中顯示標注的樣本、通過用戶日志挖掘得到訪問模式及相關樣本。

在基于目標數據模式的描述方式中，網絡蜘蛛的搜索對象是網頁上的數據，其網頁數據要符合一定的數據模式或者能夠映射為目標數據模式。這類數據的典型代表就是電子商務網站的產品信息頁面，具有統一的風格，其中的數據表示具有固定格式，并按照一定目錄層次結構來組織。

在基于領域概念的描述方式中，通過建立目標領域的詞典，從語義角度分析不同特征在某一主題中的重要程度。這種描述方式具有清晰的概念層次以及概念間、屬性間的關系定義，能夠方便地獲得一個詞語的同義詞或上下義詞。

2．特征選取方法

常用的特征選取方法有文檔頻率（Document Frequency, DF）、信息增益（Information Gain, IG）、互信息（Mutual Information, MI）、卡方檢驗（Chi-square/χ2, CHI）等。

1）DF

DF表示在訓練集中包含某個特征項t的文檔數。使用這種方法來衡量特征項重要程度是基于這樣一個假設：DF值較小的特征項對分類結果的影響較小。這種方法優先選取DF值較大的特征項，而DF值較小的特征項將被剔除，即特征項按照DF值排序。DF是最簡單的特征項選取方法，并且該方法的計算復雜度低，能夠勝任大規模的分類任務。

2）IG

IG通過統計某個特征項t在一個文檔中出現或不出現的次數來預測文檔的類別，IG的計算公式如下：

式中，Pr(ci)表示一個文檔屬于類別ci的概率；Pr(t)表示特征項t在一個文檔內出現的概率；表示特征項t不在一個文檔內出現的概率；Pr(ci|t)表示特征項t在屬于類別ci的文檔內出現的概率；表示特征項t不在屬于類別ci的文檔內出現的概率。m是文檔類別數。G(t)值大則被選取的可能性大，即特征項按照G值排序。

3）MI

MI使用如下公式計算某個特征項t和類別c之間的相關性。

式中，A為t和c同時出現的次數；B為t出現而c沒有出現的次數；C為c出現而t沒有出現的次數。N為所有文檔數。如果t和c不相關，則I（t,c）值為0。如果有m個類別，每個t都會有m個值，取它們的平均值，就可以得到特征選取所需的一個線性序列。I平均值大的特征被選取的可能性大。

4）CHI

使用MI衡量特征項的重要程度時，只考慮到了正相關對特征項重要程度的影響。如果特征項t和類別c反相關，則說明含有特征項t的文檔不屬于c的概率要大一些，這對于判斷一個文檔是否不屬于類別c也是具有指導意義的。CHI考慮了反相關性，使用如下公式計算特征項t和類別c的相關性。

式中，A為t和c同時出現的次數；B為t出現而c沒有出現的次數。C為c出現而t沒有出現的次數；D為t和c同時沒有出現的次數。N為訓練集中的文檔數。與MI類似，如果t和c不相關，則χ2(t,c)值為0。與MI相同，如果有m個類別，每個t都會有m個值，取它們的平均，就可以得到特征選取所需的一個線性序列。χ2平均值大的特征被選取的可能性大。

2.4.2 網頁搜索算法

為了高效地搜集與主題相關的網頁資源，主題蜘蛛應盡可能多地搜集主題相關的網頁，并盡可能少地搜集無關的網頁，以確保搜集網頁的質量。因此，研究人員提出了多種主題定制搜索策略和相關算法，下面介紹幾種比較流行的搜索算法。

1．基于鏈接結構評價的搜索算法

基于鏈接結構評價的搜索策略是利用Web結構信息來指導搜索，并通過分析Web網頁之間相互引用的關系來評價網頁和鏈接的重要性。這種策略的基本思想來自于文獻計量學的引文分析理論，將引文分析理論應用于Web環境時，主要采用基于鏈接結構的評價方法。下面介紹基于這種策略的常用兩種搜索算法。

1）PageRank算法

PageRank算法是由Google公司研究人員提出并應用于搜索引擎中。該算法挖掘出網頁間鏈接關系的價值，其挖掘過程也稱為鏈接分析。簡單地說，如果網頁A鏈接到B，則表示網頁A的編寫者對網頁B的認可。或者說網頁A為網頁B投了一票，網頁B的重要性被網頁A認可。網頁重要性可以從三個方面來評價。

（1）認可度越高的網頁越重要，即反向鏈接越多的網頁越重要。

（2）反向鏈接的源網頁質量越高，被這些高質量網頁鏈接指向的網頁越重要。

（3）鏈接數越少的網頁越重要。

PageRank算法用于計算網頁的重要性，對每個鏈入賦以不同的權值，鏈接提供的網頁越重要，則該鏈入權值就越高，即當前網頁的重要性是由其他網頁的重要性決定的。PageRank算法的計算公式如下：

式中，PRn(A)是網頁A的級別（即PageRank值）,PRn-1(Ti)是網頁Ti的級別，網頁Ti存在指向網頁A的鏈接，C(Ti)是網頁Ti鏈出的鏈接數量，d是阻尼系數，取值在0～1，通過實驗找出的最佳值為0.85。

該算法不以站點排序，網頁的級別由一個個獨立的網頁決定，即由鏈向網頁的級別來決定，但每個鏈入網頁貢獻的值是不同的。如果Ti網頁中鏈出越多，它對當前網頁A的貢獻就越小。網頁A的鏈入網頁越多，其網頁的級別也越高。阻尼系數的使用，減少了其他網頁對當前網頁A的排序貢獻。

該算法可以通過用戶上網行為的隨機沖浪模型來解釋，隨機沖浪模型對用戶上網行為描述如下：

（1）用戶隨機選擇一個網頁作為上網的起始網頁。

（2）看完這個網頁后從該網頁內所含的鏈接中隨機選擇一個網頁繼續瀏覽。

（3）沿著鏈接繼續瀏覽，直到對某個主題感到厭倦而重新隨機選擇另一個網頁瀏覽。如此反復，直到結束。

隨機沖浪模型將用戶點擊鏈接的行為視為一種不關心內容的隨機行為，而用戶單擊網頁內鏈接的概率完全由網頁上鏈接數量的多少來決定，這也是式（2-4）中PRn-1(Ti)/C(Ti)的原因。一個網頁通過隨機沖浪模型到達的概率就是鏈入它的網頁上鏈接被點擊概率之和。阻尼系數d的引入是因為用戶不可能無限地點擊鏈接，常常因勞累而隨機跳入另一個網頁。d可以視為用戶無限地點擊下去的概率，1-d則就是網頁本身所具有的網頁級別。

PageRank算法主要考慮了鏈接的結構特征，而忽略了網頁內容與主題的相關性，容易出現采集偏離主題的“主題漂移”問題。因此，研究人員提出了一些改進的PageRank算法，如在PageRank算法中考慮了用戶從一個網頁直接跳轉到非直接相鄰的但是內容相關的另一個網頁的情況等。

2）HITS算法

PageRank算法對于鏈出的權值貢獻是平均的，也就是不考慮不同鏈接的重要性。而Web鏈接卻具有以下特征：

（1）有些鏈接只起導航或廣告作用，還有些鏈接具有注釋性，只有注釋性的鏈接才用于權威判斷。

（2）基于商業或競爭因素考慮，很少有Web網頁指向其競爭領域的權威（Authority）網頁。

（3）權威網頁很少具有顯式的描述，比如Google主頁不會明確給出Web搜索引擎之類的描述信息。因此，權值的平均分布不符合鏈接的實際情況。

HITS（Hyperlink-Induced Topic Search）算法定義了另一種網頁，稱為中心（Hub）網頁。Hub網頁是提供指向Authority網頁鏈接集合的網頁，它本身可能并不重要，或者說沒有幾個網頁指向它，但是Hub網頁的確提供了指向某個主題的重要站點鏈接集合，例如一個課程主頁上的推薦參考文獻列表。一般來說，好的Hub網頁指向很多好的Authority網頁，好的Authority網頁是有很多好的Hub網頁指向的網頁。這種Hub與Authority網頁之間的相互加強關系，可用于Authority網頁以及Web結構與資源的自動發現，這就是Hub/Authority方法的基本思想。

HITS算法是基于Hub/Authority方法的搜索算法，算法如下：

（1）將查詢q提交給基于關鍵字匹配的搜索引擎。搜索引擎返回很多的網頁，從中取前n個網頁作為根集，用S表示。S滿足以下條件：S中網頁數量相對較小；S中大多數網頁是與查詢q相關的網頁；S中網頁包含較多的Authority網頁。

（2）通過向S中加入被S引用的網頁和引用S的網頁，將S擴展成一個更大的集合T。

（3）以T中的Hub網頁為頂點集V1，以Authority網頁為頂點集V2,V1中的網頁到V2中的網頁的鏈接為邊集E，形成一個二分有向圖SG=（V1,V2,E）。對V1中的任何一個頂點v，用h(v)表示網頁v的Hub值，對V2中的頂點u，用a(u)表示網頁的Authority值。開始時h(v)=a(u)=1，對u執行I操作修改它的a(u)，對v執行O操作修改它的h(v)，然后規范化a(u)和h(v)。如此重復計算I、O操作，直到a(u)和h(v)收斂。

I操作為：

O操作為：

每次迭代后需要對a(u)和h(v)進行規范化處理：

I操作反映了如果一個網頁有很多好的Hub指向，則權威值會相應地增加，即權威值增加為所有指向它的網頁的現有Hub值之和。O操作反映了如果一個網頁指向很多好的Authority網頁，則Hub值也會相應地增加，即Hub值增加為該網頁鏈接的所有網頁的權威值之和。

PageRank和HITS兩種算法的共同點是利用網頁之間的引用關系來確定鏈接的重要性，其優點是考慮了鏈接的結構特征，但也存在一些缺陷：一是忽略了網頁與主題的相關性，在某些情況下，會出現搜索偏離主題的“主題漂移”問題，二是在搜索過程中需要重復計算PageRank值或Authority與Hub權值，計算復雜度隨訪問網頁和鏈接數量的增長呈指數級增長。

2．基于網頁內容評價的搜索算法

基于網頁內容評價的搜索策略是利用網頁文本內容作為領域知識指導搜索，并根據網頁文本與主題之間相似度的大小來評價鏈接價值的高低。下面介紹基于這種策略的兩種常用搜索算法。

1）Fish Search算法

Fish Search算法也稱為魚群搜索算法，它將在網絡上遍歷搜索的網絡蜘蛛比喻為海里的一個魚群，當魚群找到大量的食物（主題相關網頁）之后，這些魚就變得強壯，并繁殖更多的后代；反之，魚群就變得虛弱，后代也少。當魚群找不到食物（無相關網頁）或者水被污染（帶寬不夠）的時候，魚群就會死亡。該算法的關鍵是根據用戶的種子站點和查詢的關鍵詞或短語，將包含查詢字符串的網頁看作與主題相關，計算該網頁與主題的相似度，動態地維護待爬行URL的優先級隊列url_queue。

當獲取一個網頁后，提取該網頁所有的URL，這些URL所對應的網頁稱為孩子網頁。如果獲取的網頁與主題相關，將孩子網頁的深度設置成一個預先定義的值，否則將孩子網頁的深度設置成一個小于父親網頁深度的值。當這個深度為零時，這個方向的搜索就停止。

按照下列啟發策略，將深度大于0的孩子網頁的URL加入到url_queue的頂部：

（1）相關網頁的前α×width個孩子加入到url_queue的頂部，其中α是預設的大于1的常量。

（2）無關的網頁的前width個孩子URL加入到url_queue隊列中緊靠著相關網頁的孩子節點后面。

（3）剩下的孩子URL加入到url_queue的尾部，它們只有在時間允許的情況下才有可能被搜索。

上述的三種情況可以用一個變量potential_score來等價描述。在情況（1）下，變量設置為1；在情況（2）下，變量設置為0.5；在情況（3）下，變量設置為0。待爬行URL隊列按照該變量值來排序，算法偽代碼如算法2-1所示。

該算法是一種基于客戶端的搜索算法，其優點是模式簡單、動態搜索。但也存在一些缺點，例如只使用簡單的字符串匹配來分配potential_score的值，并且只有1、0.5、0三個值，分配的值不能完全代表與主題的相似度；在url_queue中，優先級值之間的差別太小，當很多的URL具有相同的優先級，并且在搜索時間受到限制時，可能將后面更重要的網頁忽略了；使用width參數來調節刪除網頁后面的URL個數也不盡合理，有可能導致丟掉很重要的資源。

2）Shark Search算法

Shark Search算法是對Fish Search算法的一種改進，主要改進了網頁與查詢信息相似度計算方法和potential_score值計算方法，具體改進如下：

（1）在網頁與查詢信息的相似度計算中引入了向量空間模型，對相似度值進行細化，使其取值在0～1，而Fish Search算法的相似度計算為簡單的兩值判斷，不夠細致和精確。

（2）在網頁與查詢信息的相似度計算中考慮了鏈接附近的文字（如錨文本及其上下文）所包含的提示信息，使相似度計算更加準確。

由于在孩子節點的potential_score計算中綜合考慮了上述兩個因素，因此提高了相似度計算的準確性。

基于網頁內容評價的搜索策略是根據語義相似度的大小來決定鏈接的訪問順序，其優點是計算量比較小。然而，由于Web網頁不同于傳統的文本，它是一種半結構化的文檔，其中包含了許多結構信息，Web網頁不是單獨存在的，網頁中的鏈接在一定程度上反映了網頁之間存在著某些關系。采用這種搜索策略的網絡蜘蛛忽略了這些信息，因此在鏈接預測和利用方面存在一些缺陷，容易造成網頁的誤選。

2.4.3 鏈接分級搜索

由于網絡論壇、博客等互動式網站是網絡輿論的主要來源，網民通過在這類網站上發布帖子來表達自己的意見和觀點，容易形成網絡輿情。因此這類網站成為網絡輿情監測和信息采集的主要對象。由于這類網站有別于一般的靜態網絡，將傳統的搜索策略直接用于網絡論壇、博客網站信息采集時往往達不到令人滿意的效果，需要根據這類網站的特點，采取有針對性的搜索策略。

1．網絡論壇、博客網站特點

通過分析各種網絡論壇、博客網站自身的結構特點以及鏈接結構，可以總結出網絡論壇、博客網站具有如下特點：

（1）鏈接種類眾多。除了一般用戶所關心的文章或帖子對應的鏈接之外，論壇、博客中還存在著大量的功能性鏈接和噪聲鏈接。所謂功能性鏈接是指為了完成某一功能或操作而設置的鏈接，例如“登錄”、“評論”等；而噪聲鏈接是指廣告鏈接之類與用戶所關心的文章完全無關的鏈接。

（2）文章中鏈接所處層次不固定。有些文章鏈接可能置于某一目錄式板塊的索引頁，甚至網絡論壇、博客網站的首頁之上；而另一些文章則置于某一特定的分檔之中，如博客網站中博主自己的文章檔案鏈接之下，有效鏈接所處層次不固定這一現象在博客網站中尤其突出。

（3）鏈接冗余現象顯著。鏈接冗余是指同一網頁與多個鏈接相對應的現象。這一現象普遍存在于網絡論壇、博客網站之中，例如一篇文章中可能引用了一個鏈接，但是另外一篇文章中可能也引用同一鏈接，但鏈接的URL在形式上很可能是完全不同的。

如果網絡蜘蛛沒有針對網絡論壇、博客網站自身的結構特點采用相應的搜索策略，則有可能導致如下方面的問題：一是大量的無效鏈接被采集；二是由于有效鏈接往往位于不同的深度層次，影響到采集覆蓋率；三是大量的鏈接冗余現象有可能導致網絡蜘蛛陷入采集陷阱之中。

2．鏈接分級模型

對于網絡論壇、博客網站中各種形式的鏈接，可以將它們抽象成如下的鏈接類型。

（1）文章鏈接：網絡論壇、博客網站中有效帖子等形式的文章所對應的鏈接，每一篇文章都有其唯一的鏈接，該類鏈接稱為文章鏈接。

（2）博主鏈接：博客網站一般包含許多注冊博主，每一博主有其唯一的鏈接，該類鏈接稱為博主鏈接。

（3）板塊鏈接：論壇網站一般可以劃分出若干板塊，如新聞板塊、人文板塊、體育板塊等，每一板塊有其唯一的鏈接，該類鏈接稱為板塊鏈接。

（4）目錄鏈接：由于博主鏈接與板塊鏈接比較相似，并且它們都有一個顯著特征，即它們所對應的網頁中都包含了若干文章鏈接，因此可以把兩者抽象為目錄鏈接，即目錄鏈接=博主鏈接∪板塊鏈接。

（5）其他鏈接：將一些功能性鏈接、噪聲鏈接等與采集主題無關的一類鏈接稱為其他鏈接。

上述鏈接類型基本覆蓋了網絡論壇、博客網站中所有形式的鏈接。一般情況下，目錄鏈接中往往包含若干文章鏈接，這些文章鏈接則是網絡蜘蛛所需要采集的重點鏈接，而其他鏈接則是網絡蜘蛛所應規避的鏈接。

在此基礎之上，可以把網絡論壇、博客網站中的鏈接歸納劃分為三種級別：目錄鏈接、文章鏈接、其他鏈接。這三種級別的鏈接基本覆蓋了網絡論壇、博客網站中所有的鏈接形式，如圖2-9所示。

從圖2-9可以看出，網絡蜘蛛所關心的文章鏈接往往包含在一個目錄鏈接之下。因此，可以將上述構成抽象成為網絡論壇、博客網站的鏈接分級模型，即網絡論壇、博客網站中包含的大量文章鏈接都抽象歸納于一個目錄鏈接之下，如圖2-10所示。

3．“目錄鏈接-文章鏈接”搜索策略

根據鏈接分級模型，網絡蜘蛛首先搜索目錄鏈接，去除其他鏈接的干擾后，再采集目錄鏈接下的文章鏈接，有助于提高網絡蜘蛛的搜索效率。這種搜索方式稱為“目錄鏈接-文章鏈接”搜索策略。

“目錄鏈接-文章鏈接”搜索策略具有如下優點：

（1）該策略可以使網絡蜘蛛的注意力集中在目錄鏈接與文章鏈接上，從而能夠規避無效鏈接的干擾。

（2）該策略不同于廣度優先策略或深度優先策略，在邏輯上規定了兩級深度，并限制了各個文章鏈接之間的干擾，在搜索過程中能夠避免搜索陷阱現象的發生。

（3）該策略更加符合人的思維方式，可以融入人工智能方法，提高網絡蜘蛛智能化水平，進一步提高搜索效率。

因此，網絡蜘蛛在采集網絡論壇、博客網站信息時，比較適合采用鏈接分級模型進行搜索，能夠有效地提高搜索效率。