1、基于網(wǎng)頁結(jié)構(gòu)挖掘算法研究                         摘  要 Web頁面包含了豐富的、動態(tài)的超鏈信息，挖掘超鏈及其周圍的文檔可以幫助用戶找到感興趣的、權(quán)威的內(nèi)容。主要論述了基于超鏈的Web結(jié)構(gòu)挖掘的方法，并對Web結(jié)構(gòu)挖掘的一般方法HITS算法進(jìn)行改進(jìn)。采用這種改進(jìn)算法，可以從任意頁面集中計(jì)算出具有最大Authori

2、ty權(quán)值和Hub權(quán)值的頁面。從而把一個可信度的、權(quán)威的網(wǎng)站推薦給用戶。      關(guān)鍵詞  網(wǎng)頁結(jié)構(gòu)  超鏈 挖掘 算法  1  數(shù)據(jù)挖掘      Web作為目前Internet的主要信息發(fā)布渠道，包含了豐富的、動態(tài)的超鏈接信息，這為數(shù)據(jù)挖掘提供了豐富的資源。現(xiàn)有的知識發(fā)現(xiàn)(KDD)的方法和技術(shù)已不能滿足人們從Web中獲取知識的需要。許多時(shí)候人們苦于在巨大的網(wǎng)絡(luò)世界中不容易找到自己感興趣的、權(quán)威的內(nèi)容。所以人們迫切需要找到這樣的工具，能夠從WEB上快速地、有效地發(fā)

3、現(xiàn)資源，發(fā)現(xiàn)隱含的規(guī)律性的內(nèi)容，提高在WEB上檢索信息、利用信息的效率。數(shù)據(jù)挖掘便應(yīng)運(yùn)而生。數(shù)據(jù)挖掘通常有內(nèi)容挖掘、使用挖掘和結(jié)構(gòu)挖掘三種類型。本文主要研究結(jié)構(gòu)挖掘。Web結(jié)構(gòu)挖掘是指通過分析不同網(wǎng)頁之間的超鏈結(jié)構(gòu)，發(fā)現(xiàn)許多蘊(yùn)涵在Web內(nèi)容之外的對我們有潛在價(jià)值的模式和知識的過程。2  結(jié)構(gòu)挖掘      WWW沒有數(shù)據(jù)庫那樣嚴(yán)格統(tǒng)一的語義模式，但也不像平面文件那樣完全沒有結(jié)構(gòu)，從信息結(jié)構(gòu)的角度來看，WWW上的資源有三種類型：結(jié)構(gòu)化資源、半結(jié)構(gòu)化資源和無結(jié)構(gòu)化資源，它的語義隱含在語法結(jié)構(gòu)之中。忽略掉Web頁面上的文本和其它內(nèi)容，只考慮

4、頁面間的超鏈，WWW可以被看作是以Web頁面為節(jié)點(diǎn)、頁面之間超鏈為有向邊所構(gòu)成的網(wǎng)狀結(jié)構(gòu)的有向圖，把Web看成是一個巨大的有向圖G =(V,E)，結(jié)點(diǎn)vV代表一個Web頁面，有向邊(p,q)E代表從結(jié)點(diǎn)p指向結(jié)點(diǎn)q的超鏈接。結(jié)構(gòu)挖掘就是要在這樣的網(wǎng)絡(luò)有向圖中進(jìn)行超鏈分析。通過分析超鏈可以獲悉網(wǎng)站的受歡迎程度及與其它網(wǎng)站的關(guān)系，而且，通過網(wǎng)頁之間的鏈接還能夠快速了解一個網(wǎng)站的內(nèi)部結(jié)構(gòu)。WWW是一個超文本文檔信息系統(tǒng)，而超鏈?zhǔn)潜硎拘畔⒌囊粋€重要方式，所以挖掘超鏈的語義結(jié)構(gòu)十分必要和有意義。      在WWW上網(wǎng)頁內(nèi)部的超鏈用HTML、XML表示成

5、樹形結(jié)構(gòu)，文檔表示成URL中的目錄路徑結(jié)構(gòu)，站點(diǎn)之間通過超鏈同其它相關(guān)聯(lián)的站點(diǎn)或頁面相鏈接。相關(guān)主題的站點(diǎn)和頁面之間一般都存在大量的鏈接，通過這種鏈接方式相聚集。但主題相同的所有站點(diǎn)或頁面不一定會圍繞一個中心(Hub) 相聚集，也就是說一個主題會存在多個聚集中心。一個網(wǎng)站如果鏈接了許多權(quán)威網(wǎng)站，那么它就是一個中心網(wǎng)站(Hub)；如果一個網(wǎng)站被許多中心網(wǎng)站鏈接，那么它就是一個權(quán)威網(wǎng)站(Authority)，如圖1、圖2所示。很多網(wǎng)站管理和設(shè)計(jì)人員通常愿意鏈接可信度高的網(wǎng)站。因而一個網(wǎng)站的可信度可以根據(jù)它所鏈接的網(wǎng)站的權(quán)威程度來衡量,同時(shí)它會推薦給用戶許多好的權(quán)威網(wǎng)站，對其它網(wǎng)站的權(quán)威性起到了一定

6、程度的增強(qiáng)作用。    3  Web結(jié)構(gòu)挖掘的算法       利用超鏈進(jìn)行挖掘的兩個典型的算法是：PageRank算法及HITS算法。本文主要介紹HITS算法，并針對HITS算法的不足之處提出一種改進(jìn)的方法。采用這種改進(jìn)算法，可以從任意頁面集中計(jì)算出具有最大Authority權(quán)值和Hub權(quán)值的頁面。3.1 HITS 算法      HITS(Hyperlink Induced Topic Search) 是Web結(jié)構(gòu)挖掘的一個基本算法。此算法建

7、立在下面幾個定義之上：      Hubs頁，指的是一個指向權(quán)威頁的超鏈接集合的Web頁；     Authorities頁，指的是被許多Hubs頁指向的權(quán)威的Web 頁；      以及由這兩個定義所衍生出來的一個Web 頁的Authority權(quán)重(由網(wǎng)頁的out-link 決定) 和 Hub 權(quán)重(由網(wǎng)頁的in-link 決定)。     其算法步驟如下：       &#

8、160; 1) 根據(jù)用戶查詢請求，首先用一個現(xiàn)有的商業(yè)搜索引擎進(jìn)行查詢，取其部分查詢結(jié)果(約200個左右)作為算法的根集，記為 R.    2) 將 R 進(jìn)行擴(kuò)充，對R中每一個結(jié)點(diǎn)，將所有指向該結(jié)點(diǎn)或該結(jié)點(diǎn)所指向的網(wǎng)頁補(bǔ)充進(jìn)來，形成基集，記為 S.    3) 計(jì)算S中每一個網(wǎng)頁的Authority權(quán)重和Hub權(quán)重，這是一個遞歸過程.    先將網(wǎng)頁 p的Authority權(quán)重記為 ap ，Hub 權(quán)重記為hp，為 S中所有網(wǎng)頁賦初值：ap (0)1，hp (0)1；再通過以下迭代公式對 ap 和 hp

9、進(jìn)行反復(fù)修正，直至結(jié)果收斂：                             I操作：     O操作：  這里 qp 的含義是存在一個由 q 指向 p 的超鏈接。    設(shè)   

10、基于HITS算法的系統(tǒng)包括Clever、Google 也基于同樣的原理。這些系統(tǒng)由于納入了 Web鏈接和文本內(nèi)容信息，查詢效果明顯優(yōu)于基于詞類索引引擎產(chǎn)生的結(jié)果，如 AltaVista , 和基于人工的本體論生成的結(jié)果，如Yahoo！。3.2 對HITS算法的改進(jìn)      我們不難發(fā)現(xiàn)，HITS算法完全不考慮頁面文本的內(nèi)容，在實(shí)際應(yīng)用中也出現(xiàn)了一定的問題，如主題漂移等。這主要是由于算法認(rèn)為頁面中的所有超鏈具有同等價(jià)值引起的，根據(jù)算法描述，只要兩個頁面之間存在超鏈，則鄰接矩陣中對應(yīng)的值即為1，這完全忽視了超鏈之間的差異，引起了算法結(jié)果的偏差。&

11、#160;     通過引入頁面文本的語義信息可以解決這個問題，已有不少研究者對算法進(jìn)行改進(jìn)，在一定程度上改善了這些偏差。在Clever系統(tǒng)中使用HITS算法，通過在超鏈的周圍文字中匹配查詢關(guān)鍵字并計(jì)算詞頻的方法來計(jì)算超鏈的權(quán)值，用計(jì)算出的權(quán)值來代替鄰接矩陣中相應(yīng)的值，從而達(dá)到引入語義信息的目的，取得了一定的效果。然而，網(wǎng)絡(luò)上的頁面形式十分復(fù)雜，很多時(shí)候超鏈周圍文字無法代表鏈接頁面的內(nèi)容，甚至與鏈接頁面的內(nèi)容大相徑庭。      基于HITS算法的這些不足之處本文提出了計(jì)算超鏈權(quán)值的解決方案。在頁面的文本

12、中，最能夠代表鏈接頁面語義信息的是超鏈文字(本文僅考慮以文本為載體的超鏈，對以圖像、動畫等為載體的超鏈暫時(shí)不作考慮)。超鏈文字是超鏈的載體，通常可以作為鏈接頁面內(nèi)容的標(biāo)題，因而能夠很好地反映鏈接頁面的語義信息。本文通過引入加權(quán)系數(shù)來控制超鏈周圍文字在超鏈權(quán)值中所占的比例。在計(jì)算超鏈權(quán)值時(shí)，需要將文本中的語義信息進(jìn)行量化，這樣才能夠使語義信息這一概念具有可計(jì)算性。本文使用查詢關(guān)鍵字在超鏈文字中出現(xiàn)的次數(shù)，即詞頻信息進(jìn)行語義信息的量化。為了方便描述，定義從頁面p指向頁面q關(guān)于查詢關(guān)鍵字k的超鏈權(quán)值為w(p, q, k)，這個數(shù)值隨著查詢關(guān)鍵字在超鏈文字和周圍文字中出現(xiàn)數(shù)量的增多而增大；定義t(k)

13、 st(k)為查詢關(guān)鍵字在周圍文字中出現(xiàn)的次數(shù)，系數(shù)用于控制周圍文字的語義信息在超鏈權(quán)值中的比例，可用式(1)來計(jì)算權(quán)值w的值：w(p, q, k)=1+ t (k) +*st (k)                 (1)      其中，系數(shù)的值可以根據(jù)不同頁面集進(jìn)行調(diào)整。根據(jù)式(1)計(jì)算出的w值是大于1的，在迭代過程中得到的向量會不斷增大。然而，本文所關(guān)心的只是它們之間的相對大小，

14、而不是權(quán)值的絕對數(shù)值，因此，為了把結(jié)果向量的數(shù)值控制在一定范圍內(nèi)，可以在每次迭代后進(jìn)行標(biāo)準(zhǔn)化。所有超鏈的權(quán)值計(jì)算完成后，就可以根據(jù)公式xATyATAx(ATA)x，yAxAATy(AAT)y    (2)      進(jìn)行迭代得到authority權(quán)值向量x和hub權(quán)值向量y。其中鄰接矩陣A中每一項(xiàng)的值是這樣定義的，如果存在超鏈從頁面p指向頁面q，則A中對應(yīng)項(xiàng)的值為w(p, q, k)，否則對應(yīng)項(xiàng)的值為0。經(jīng)過n次迭代后，輸出x向量中值最大的一組頁面作為authority頁面，y向量中值最大的一組頁面作為hub頁面，

15、其中結(jié)果的數(shù)量可以根據(jù)具體的應(yīng)用要求定制。迭代次數(shù)n的選擇來自于矩陣特征向量的理論，經(jīng)過足夠數(shù)量的迭代，結(jié)果向量最終將收斂于矩陣 ATA 的特征向量。采用這種算法，可以從任意頁面集中計(jì)算出具有最大authority權(quán)值和hub權(quán)值的頁面。       本文在分析網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上，介紹了結(jié)構(gòu)挖掘中HITS算法模型，并針對其弱點(diǎn)提出了改進(jìn)方案。對于HITS算法而言，還有其它的方式可以進(jìn)一步改進(jìn)它的精度。在今后的工作中，可以考慮根據(jù)這些思想進(jìn)一步改進(jìn)算法。參考文獻(xiàn)1 劉麗珍等. 網(wǎng)絡(luò)結(jié)構(gòu)挖掘的關(guān)鍵分析 .計(jì)算機(jī)應(yīng)用研究,2003(5) 116-1182 陳定權(quán). Web結(jié)構(gòu)挖掘研究. 情報(bào)理論與實(shí)踐 ,2003(1) 59-613 Bharat K, Henzinger M R. Improved Algorithms for Topic Distillation in a Hyperlinked Environment. In Proceedings of th