網頁結構挖掘算法研究論文

導語：網頁結構挖掘算法研究論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

摘要Web頁面包含了豐富的、動態的超鏈信息，挖掘超鏈及其周圍的文檔可以幫助用戶找到感興趣的、權威的內容。主要論述了基于超鏈的Web結構挖掘的方法，并對Web結構挖掘的一般方法HITS算法進行改進。采用這種改進算法，可以從任意頁面集中計算出具有最大Authority權值和Hub權值的頁面。從而把一個可信度的、權威的網站推薦給用戶。

關鍵詞網頁結構超鏈挖掘算法

1數據挖掘

Web作為目前Internet的主要信息渠道，包含了豐富的、動態的超鏈接信息，這為數據挖掘提供了豐富的資源?，F有的知識發現(KDD)的方法和技術已不能滿足人們從Web中獲取知識的需要。許多時候人們苦于在巨大的網絡世界中不容易找到自己感興趣的、權威的內容。所以人們迫切需要找到這樣的工具，能夠從WEB上快速地、有效地發現資源，發現隱含的規律性的內容，提高在WEB上檢索信息、利用信息的效率。數據挖掘便應運而生。數據挖掘通常有內容挖掘、使用挖掘和結構挖掘三種類型。本文主要研究結構挖掘。Web結構挖掘是指通過分析不同網頁之間的超鏈結構，發現許多蘊涵在Web內容之外的對我們有潛在價值的模式和知識的過程。

2結構挖掘

WWW沒有數據庫那樣嚴格統一的語義模式，但也不像平面文件那樣完全沒有結構，從信息結構的角度來看，WWW上的資源有三種類型：結構化資源、半結構化資源和無結構化資源，它的語義隱含在語法結構之中。忽略掉Web頁面上的文本和其它內容，只考慮頁面間的超鏈，WWW可以被看作是以Web頁面為節點、頁面之間超鏈為有向邊所構成的網狀結構的有向圖，把Web看成是一個巨大的有向圖G=(V,E)，結點v∈V代表一個Web頁面，有向邊(p,q)∈E代表從結點p指向結點q的超鏈接。結構挖掘就是要在這樣的網絡有向圖中進行超鏈分析。通過分析超鏈可以獲悉網站的受歡迎程度及與其它網站的關系，而且，通過網頁之間的鏈接還能夠快速了解一個網站的內部結構。WWW是一個超文本文檔信息系統，而超鏈是表示信息的一個重要方式，所以挖掘超鏈的語義結構十分必要和有意義。

在WWW上網頁內部的超鏈用HTML、XML表示成樹形結構，文檔表示成URL中的目錄路徑結構，站點之間通過超鏈同其它相關聯的站點或頁面相鏈接。相關主題的站點和頁面之間一般都存在大量的鏈接，通過這種鏈接方式相聚集。但主題相同的所有站點或頁面不一定會圍繞一個中心(Hub)相聚集，也就是說一個主題會存在多個聚集中心。一個網站如果鏈接了許多權威網站，那么它就是一個中心網站(Hub)；如果一個網站被許多中心網站鏈接，那么它就是一個權威網站(Authority)，如圖1、圖2所示。很多網站管理和設計人員通常愿意鏈接可信度高的網站。因而一個網站的可信度可以根據它所鏈接的網站的權威程度來衡量,同時它會推薦給用戶許多好的權威網站，對其它網站的權威性起到了一定程度的增強作用。

3Web結構挖掘的算法

利用超鏈進行挖掘的兩個典型的算法是：PageRank算法及HITS算法。本文主要介紹HITS算法，并針對HITS算法的不足之處提出一種改進的方法。采用這種改進算法，可以從任意頁面集中計算出具有最大Authority權值和Hub權值的頁面。

3.1HITS算法

HITS(HyperlinkInducedTopicSearch)是Web結構挖掘的一個基本算法。此算法建立在下面幾個定義之上：

①Hubs頁，指的是一個指向權威頁的超鏈接集合的Web頁；

②Authorities頁，指的是被許多Hubs頁指向的權威的Web頁；

③以及由這兩個定義所衍生出來的一個Web頁的Authority權重(由網頁的out-link決定)和Hub權重(由網頁的in-link決定)。

其算法步驟如下：

1)根據用戶查詢請求，首先用一個現有的商業搜索引擎進行查詢，取其部分查詢結果(約200個左右)作為算法的根集，記為Rδ.

2)將Rδ進行擴充，對Rδ中每一個結點，將所有指向該結點或該結點所指向的網頁補充進來，形成基集，記為Sδ.

3)計算Sδ中每一個網頁的Authority權重和Hub權重，這是一個遞歸過程.

先將網頁p的Authority權重記為ap，Hub權重記為hp，為Sδ中所有網頁賦初值：ap(0)←1，hp(0)←1；再通過以下迭代公式對ap和hp進行反復修正，直至結果收斂：

I操作：

O操作：

這里q←p的含義是存在一個由q指向p的超鏈接。

設且，a(t)、h(t)迭代的初始向量為[1,…,1]T,則a3、h3分別收斂為矩陣XTX、XXT主特征向量。因此，頁面i的Authority權重為ai3，Hub權重為hi3。具有較大的a3和h3的頁面就是Authorities頁和Hubs頁。

基于HITS算法的系統包括Clever、Google也基于同樣的原理。這些系統由于納入了Web鏈接和文本內容信息，查詢效果明顯優于基于詞類索引引擎產生的結果，如AltaVista,和基于人工的本體論生成的結果，如Yahoo！。

3.2對HITS算法的改進

我們不難發現，HITS算法完全不考慮頁面文本的內容，在實際應用中也出現了一定的問題，如主題漂移等。這主要是由于算法認為頁面中的所有超鏈具有同等價值引起的，根據算法描述，只要兩個頁面之間存在超鏈，則鄰接矩陣中對應的值即為1，這完全忽視了超鏈之間的差異，引起了算法結果的偏差。

通過引入頁面文本的語義信息可以解決這個問題，已有不少研究者對算法進行改進，在一定程度上改善了這些偏差。在Clever系統中使用HITS算法，通過在超鏈的周圍文字中匹配查詢關鍵字并計算詞頻的方法來計算超鏈的權值，用計算出的權值來代替鄰接矩陣中相應的值，從而達到引入語義信息的目的，取得了一定的效果。然而，網絡上的頁面形式十分復雜，很多時候超鏈周圍文字無法代表鏈接頁面的內容，甚至與鏈接頁面的內容大相徑庭。

基于HITS算法的這些不足之處本文提出了計算超鏈權值的解決方案。在頁面的文本中，最能夠代表鏈接頁面語義信息的是超鏈文字(本文僅考慮以文本為載體的超鏈，對以圖像、動畫等為載體的超鏈暫時不作考慮)。超鏈文字是超鏈的載體，通常可以作為鏈接頁面內容的標題，因而能夠很好地反映鏈接頁面的語義信息。本文通過引入加權系數α來控制超鏈周圍文字在超鏈權值中所占的比例。

在計算超鏈權值時，需要將文本中的語義信息進行量化，這樣才能夠使語義信息這一概念具有可計算性。本文使用查詢關鍵字在超鏈文字中出現的次數，即詞頻信息進行語義信息的量化。為了方便描述，定義從頁面p指向頁面q關于查詢關鍵字k的超鏈權值為w(p,q,k)，這個數值隨著查詢關鍵字在超鏈文字和周圍文字中出現數量的增多而增大；定義t(k)st(k)為查詢關鍵字在周圍文字中出現的次數，系數α用于控制周圍文字的語義信息在超鏈權值中的比例，可用式(1)來計算權值w的值：

w(p,q,k)=1+t(k)+α*st(k)(1)

其中，系數α的值可以根據不同頁面集進行調整。根據式(1)計算出的w值是大于1的，在迭代過程中得到的向量會不斷增大。然而，本文所關心的只是它們之間的相對大小，而不是權值的絕對數值，因此，為了把結果向量的數值控制在一定范圍內，可以在每次迭代后進行標準化。所有超鏈的權值計算完成后，就可以根據公式

x←ATy←ATAx←(ATA)x，y←Ax←AATy←(AAT)y(2)

進行迭代得到authority權值向量x和hub權值向量y。其中鄰接矩陣A中每一項的值是這樣定義的，如果存在超鏈從頁面p指向頁面q，則A中對應項的值為w(p,q,k)，否則對應項的值為0。經過n次迭代后，輸出x向量中值最大的一組頁面作為authority頁面，y向量中值最大的一組頁面作為hub頁面，其中結果的數量可以根據具體的應用要求定制。迭代次數n的選擇來自于矩陣特征向量的理論，經過足夠數量的迭代，結果向量最終將收斂于矩陣ATA的特征向量。采用這種算法，可以從任意頁面集中計算出具有最大authority權值和hub權值的頁面。

本文在分析網絡結構的基礎上，介紹了結構挖掘中HITS算法模型，并針對其弱點提出了改進方案。對于HITS算法而言，還有其它的方式可以進一步改進它的精度。在今后的工作中，可以考慮根據這些思想進一步改進算法。

參考文獻

[1]劉麗珍等.網絡結構挖掘的關鍵分析.計算機應用研究,2003(5)116-118

[2]陳定權.Web結構挖掘研究.情報理論與實踐,2003(1)59-61

[3]BharatK,HenzingerMR.ImprovedAlgorithmsforTopicDistillationinaHyperlinkedEnvironment.InProceedingsoftheACM-SIGIR,1998

[4]ChakrabartiS,DomB,GibsonD,etal.AutomaticResourceListCompilationbyAnalyzingHyperlinkStructureandAssociatedText.InProc.ofthe7thInt.WWWConference,1998-05