0 引言
隨著網絡上Web頁面的急劇增長,Internet已成為世界上最豐富和最密集的信息來源。然而,這些大量、無序的信息也給信息檢索帶來了很多的問題。目前各種搜索引擎均存在查準率、查全率不高的現象,這種現狀無法適應用戶對高質量的網絡信息服務的需求；同時電子商務以及各種網絡信息服務迅速興起,原有的網絡信息處理與組織技術已不能滿足要求,Web數據挖掘(Web Mining)就是在這樣的環境下應運而生的,并迅速成為數據挖掘、信息檢索領域的研究熱點之一。根據挖掘的對象可將Web數據挖掘分為三類：基于Web內容(Content)的挖掘、Web結構(Structure)挖掘，和基于Web使用記錄(Usage)的挖掘[1]。HITS和 PageRank算法是Web結構挖掘的經典算法，它們的廣泛運用，使得信息檢索的效率有所提高，但同時也顯現出這兩種算法的不足之處。于是，本文將這兩種算法的優點結合起來，得到一種改進算法。
1 Web結構挖掘
Web頁面是互聯網上存儲和發布信息最普遍的載體，是世界上最大的信息倉庫之一。Web上存儲的信息量巨大而且缺乏結構化組織的規整性，人們訪問Web留下的日志也是海量數據。近幾年數據挖掘技術不斷的發展完善，為Web信息的處理和有效使用提供了有效的工具。Web挖掘己經成為數據挖掘技術一個重要的應用領域。
Web結構挖掘是Web挖掘的一個方面，它是挖掘Web潛在的鏈接結構模式，找到隱藏在一個個頁面之后的鏈接結構模型，該模型可用于網頁重新分類，也可以用于尋找相似的網站，并由此獲得有關不同網頁間相似度及關聯度的信息[2]。這有助于用戶找到指向相關主題的權威站點。Web結構挖掘可分為超鏈接挖掘、頁面結構挖掘等。這一領域最常用的是圖論中的網落分析法，典型的算法有HITS和PageRank，人們采用這些算法主要是計算Web頁面之間的關聯程度。這不僅可用于提高網上搜索引擎搜索的準確性（在Google和Clever 等系統中己經有應用），還可以用于挖掘網站之間的通信、相互參引關系。
2 HITS算法
2.1 HITS算法的思想和過程
HITS(Hyperlink-Induced Topic Search)算法是Kleinberg于1999年提出的關于超鏈接的檢索算法。該算法通過對網絡中超鏈接的分析,利用頁面的被引用次數及其鏈接數目來決定不同網頁的權威性。
在HITS 算法模型中，Kleinberg 提出了權威網頁(Authority)和中心網頁(Hub)的概念。權威網頁(Authority)是指那些與給定查詢主題的上下文最為相關并具有權威性的網頁，這也是人們對于寬主題查詢最關心的網頁；而中心網頁(Hub)則是那些本身的內容雖然未必具有權威性，但卻包含了多個指向Authority的超鏈接的網頁。Kleinberg認為頁面的重要性應該建立在用戶查詢條件的基礎上，而且每一個頁面都分別有Authority值和Hub值。如果一個頁面由許多相關主題的頁面所指向，則該頁面具有較高的Authority值；如果一個頁面指向許多相關主題頁面，則該頁面具有較高的Hub值。這種Authority和Hub的相互作用可用于權威網頁的挖掘和高質量Web結構和資源的自動發現,這就是HITS算法的基本思想。權威網頁與中心網頁之間的鏈接關系可以用圖1來表示。
Hub　　　　　　　　　　Authority
圖1 權威網頁與中心網頁的的鏈接關系
基于以上這種鏈接結構描述的概念，HITS算法通過挖掘Web鏈接結構，分析Web間的鏈接關系，找出Web集合中的Authority網頁和Hub 網頁。為每個網頁定義兩個度量值:權威權重(authority weight)和中心權重(Hub weight)，通過這兩個權重來判定該網頁對特定主題的重要性。假設給定一個泛指主題檢索提問σ，首先利用一個基于關鍵字的搜索引擎獲取一個與查詢主題相關的網頁根集合(root set)Ｒσ，通過向根集合中擴充那些指向根集合中網頁的網頁和根集合中網頁所指向的網頁，將根集擴展成一個更大的基礎集合(base set)Ｂσ。
HITS算法的過程如下所述：把一個寬主題查詢提交給一個基于文本的搜索引擎，在搜索引擎返回的結果集中取出前t（200 個）個網頁構成一個根集Ｒσ.。擴展根集合，構造基集Ｂσ（如圖2所示）。獲得根集合Ｒσ后，用Ｒσ中頁面的鄰近頁面（即Ｒσ中頁面鏈接的所有頁面和有鏈接指向Ｒσ中頁面的最多50個頁面）來擴展Ｒσ，形成一個頁面基集Ｂσ。從基集Ｂσ中導出頁面鄰域圖G(Ｂσ)=(V,E)。其中G中的節點表示Ｂσ中的網頁，有向邊表示Ｂσ中的鏈接，這樣就構造出了一個Web鏈接結構子圖。


圖2 從根集擴展到基集
從理論上看，獲得某一主題權威網頁的最簡單的方法是計算基集中每一個網頁的“入度”（即指向該網頁的所有超鏈接數目）。但是，僅通過計算入度的方法來提取權威網頁實際上會有很多問題。比如，像sohu、Yahoo、新浪等門戶網站的網頁，往往會被大量網站的網頁所鏈接，這類網站建立這種鏈接關系往往只是起到友情鏈接的作用，而門戶網站的網頁很可能與查詢主題是不相關的。實際上，權威網頁和中心網頁之間存在著的一種相互加強(mutual reinforcement, MR)的關系，即一個好的中心網頁應該指向很多好的權威網頁，而一個好的權威網頁則應該被很多好的中心網頁所指向。正是基于這種思想，HITS 算法對Web鏈接結構子圖G(Ｂσ)=(V,E)中的每一個節點P∈V 賦予兩個度量值:權威權重(Authority weight) a(p)和中心權重(Hub weight) h(p)。前者用于度量一個網頁的權威性(即其中包含主題內容的程度)，而后者用于度量一個網頁的中心性(即從它可以導航到權威網頁的潛力)。任一節點p的權威權重和中心權重可分別用以下兩種操作計算(如圖3所示):
I操作：a(p) = ∑q:(q,p)∈E h(q) O操作：h(p) = ∑q:(p,q)∈E a(q)

圖3 I操作與0操作
鏈接結構子圖中n個節點的Authority與Hub值分別構成兩個n（列）向量a ∈ Rn 和h ∈ Rn 。為了打破兩種權重計算時的循環關系，需要一個迭代過程來計算向量a和h ：
首先，a和h初始化為向量z = (1,1……,1)T ∈ Rn ；
然后對向量a和h進行反復迭代計算，即交替地在h上運用I操作來計算a。在a上運用O操作來計算h，每次迭代后對a和h進行單位化，使它們成為Rn上的單位向量；
最后，分別將G中c（典型的，設c=5—10）個具有最大a和h值的節點作為權威頁面和中心頁面輸出。這樣即得到了某一查詢的權威網頁和中心網頁。
2.2 HITS的優點與不足
作為基于結構分析的典型算法，HITS 算法有很多優點：
第一， 算法的迭代速度很快，往往迭代五次以后a( p) 和h( p) 排名最高的網頁就趨于穩定。
第二，從算法的整個流程來看，只有在算法的初始階段生成根集合時使用了用戶提供的關鍵詞，其后基集的產生和迭代過程完全根據超鏈接組成的有向圖操作，與關鍵詞無關。這一算法特性使算法能有力地檢索到不包含關鍵詞但與主題高度相關的網頁，使主題不受關鍵詞語種的約束。
第三， 實驗證明算法最后得到的結果受初始的根集合影響不大，具有良好的算法穩定性。
HITS 算法引發了主題精選的研究熱潮，但進一步的研究表明HITS算法存在一些不足：容易發生主題偏移；容易產生不合理結果；易受無關鏈接和無關頁面的影響等。
3 PageRank算法
PageRank算法由Stanford大學的Brin和Page提出的[3] ,是Web超鏈接結構分析中最早、最成功的算法之一。搜索引擎Google就是利用該算法和鏈接文本標記、詞頻統計等因素相結合的方法對檢索出的大量結果進行相關度排序,將等級值高的網頁盡量排在前面。
PageRank算法的基本思想是：一個頁面被多次引用，則這個頁面很可能是重要的；一個頁面盡管沒有被多次引用，但被一個重要頁面引用，則這個頁面很可能也是很重要的。算法的過程如下:將Web對應成有向圖,Ni是頁面i指向的所有頁面的集合, Bi是指向頁面i的所有頁面的集合，則頁面i的等級PageRank值PR(i)可以通過以下兩步計算得出:
（1）以概率(1-d)隨機取Web上任一頁面i；
（2）以概率d隨機取指向當前頁面i的頁面j。則PageRank算法的具體迭代公式為:
PR(i) = (1-d) + d Σj∈Bi ( PR(j)/|Nj|)
其中,參數d是取值0到1之間的衰減因子,d通常被設置為0.85。
PageRank算法的實現過程為:將網頁的URL對應成唯一的整數,把每一個超鏈接用其整數ID存放到索引數據庫中,經過預處理之后,設每個網頁的初始PR值為1 ,通過以上的遞歸算法計算每一個網頁的PageRank值,反復進行迭代,直至結果收斂。顯然,PageRank值越大,該頁面權威性越高。該算法與用戶查詢條件無關,只是給出每一頁面的等級PageRank值,作為搜索引擎結果排序的一個參考,等級越高的頁面排序越靠前。
4 HITS算法與PageRank算法的比較分析
顯而易見,兩者均是基于鏈接分析的搜索引擎排序算法,并且在算法中二者均利用了特征向量作為理論基礎和收斂性依據。但兩種算法的不同點也非常明顯,下面就主要談談其不同點:
（1）從算法思想上看,雖然均同為鏈接分析算法,但二者之間還是有一定的區別。HITS的原理如前所述,其authority值只是相對于某個檢索主題的權重,因此HITS算法也常被稱為query - dependent算法。而PageRank算法獨立于檢索主題,因此也常被稱為query - independent 算法。PageRank算法利用網絡自身的超鏈接結構給所有的網頁確定一個重要性的等級數，根據因特網自身的性質等,它不僅考慮了網頁引用數量,還特別考慮了網頁本身的重要性[4]。簡單地說,重要網頁所指向的鏈接將大大增加被指向網頁的重要性。
（2）從權重的傳播模型來看,HITS是首先通過基于文本的搜索引擎來獲得最初的處理數據,網頁重要性的傳播是通過Hub頁向Authority頁傳遞,而且Kleinberg認為,Hub與Authority之間是相互增強的關系；而PageRank基于隨機沖浪(randomsurfer)模型,可以認為它將網頁的重要性從一個authority頁傳遞給另一個authority頁。
（3）從具體應用來看，PgaeRank算法應用于搜索引擎服務端，可以直接用于標題查詢并獲得較好的結果，若要用于全文本查詢，需要與其他相似度判定標準(向量模型等)進行復合，以針對具體查詢形成最終排名，搜索機器人(Crawler)可以將PgaeRank做為搜索優先次序的標準。HTIS算法一般用于全文本搜索引擎的客戶端，對于寬主題的搜索相當有效，可以用于自動編撰萬維網分類目錄，通過找到指向某網頁的Hub網頁并以此為root集可以查找該網頁的相關網頁，也可用于元搜索引擎的網頁排序。
（4）從處理的數據量及用戶端等待時間來分析。表面上看,HITS算法對需排序的網頁數量較小,所計算的網頁數量一般為1000至5000個,但由于需要從基于內容分析的搜索引擎中提取根集并擴充基本集,這個過程需要耗費相當的時間,而PageRank算法表面上看,處理的數據數量上遠遠超過了HITS算法。據Google介紹,目前已收錄的中文網頁已達33億以上,但由于其計算量在用戶查詢時已由服務器端獨立完成,不需要用戶端等待,基于該原因,從用戶端等待時間看,PageRank算法應該比HITS要短。
5 基于PageRank和HITS的改進算法
基于上述分析,本文得出一種基于PageRank和HITS的改進算法,可以較好地解決上述不足。
5.1 算法描述
第一步，構照算法的基本集,這一步和HITS中方法類似。根據用戶查詢請求,首先用一個現有的商業搜索引擎進行查詢,取其部分查詢結果(約500個左右)作為算法的根集,記為Rδ。然后將Rδ進行擴充,對Rδ中每一個節點,將所有指向該節點或該節點所指向的網頁補充進來,形成基本集,記為Qδ。
第二步，求Qδ中頁面的PageRank值,作為搜索引擎結果排序的一個參考。設W為Qδ中頁面的集合,N=|W|,Ri是頁面i指向的所有頁面的集合,Bi是指向頁面i的所有頁面的集合。對每個出度為0或者出度頁面都不在Qδ中的頁面s,設RS={Qδ中所有頁面的集合} ,則所有其他結點的Bi={Bi∪s} ,這樣可以將結點s所具有的PageRank值均勻地傳遞給其他所有頁面i。由此頁面i的等級PageRank值PR(i)可以通過以下兩步計算得出:
(1)以概率(1-d)隨機取基集Qδ中任一頁面i;
(2)以概率d隨機取指向當前頁面i的頁面j ,如果j∈Qδ不成立,則重新選擇頁面j。計算PageRank值算法的具體迭代公式為:
PR(i) = (1-d) + d Σj∈Bi (PR(j)/|Rj|)
其中,參數d是取值范圍在0 到1之間的衰減因子,通常被置為0.85。
5.2 算法分析
PageRank是對WWW的整體分析,是獨立于用戶查詢的,可以對用戶要求產生快速的響應。而HITS算法是對WWW的局部分析,依賴于用戶查詢的,實時性差。改進算法通過HITS算法得到與用戶查詢請求相關的Web頁面集(即基本集) ,進而求得每一頁面的PR(i)值作為搜索引擎結果排序的參考。由于改進算法采用HITS構造結果的基本集,因此它彌補了PageRank算法中頁面內容無關性的缺點。與HITS算法不同的是,改進算法采用了PageRank的排序機制,通過計算基本集的PageRank值作為排序參考,在一定程度上消弱了HITS算法中的“主題漂移”的缺點。盡管算法中搜索排序網頁比PageRank要少的多,但是由于需要在客戶端處理一些數據,所以響應時間沒有明顯提高。
6 結束語
近年來,隨著WWW的飛速發展及信息量的指數級增長,Web挖掘逐漸成為數據挖掘、人工智能和信息檢索領域的一個研究熱點。
Web挖掘作為數據挖掘的一個新的主題,是一個新興的研究領域,至今還未形成成熟的理論和技術�；�于鏈接分析的網頁排序算法,目前的研究都也還很不成熟,無論是HITS算法,還是PgaeRank算法,已有眾多的國內外學者在算法的改進方面做出了努力,并且提出了一些其它的算法。





參考文獻：
[1] J iawei Han, Micheline Kamber. DataMining: Concep ts and Techniques[M ]. Morgan Kaufmann Publishers, Inc, 2001.
[2]楊炳儒,李巖,陳新中等.Web結構挖掘[J].計算機工程,29(20),2003.
[3]王艷華,張紀.Web結構挖掘及其算法[J].計算機工程,2005 ,31(增刊):125 - 127.
[4]戚華春,黃德才,鄭月峰.具有時間反饋的PageRank 改進算法[J].浙江工業大學學報,2005,33(3):272-275.



作者簡介:
熊鳳,女,25歲,貴州省福泉市人,現就讀于貴州大學計算機科學與信息學院,攻讀計算機應用技術專業碩士研究生學位,研究方向為數據庫技術。