導(dǎo)語：網(wǎng)頁結(jié)構(gòu)挖掘算法研究論文一文來源于網(wǎng)友上傳，不代表本站觀點，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

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

關(guān)鍵詞網(wǎng)頁結(jié)構(gòu)超鏈挖掘算法

1數(shù)據(jù)挖掘

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

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)容，只考慮頁面間的超鏈，WWW可以被看作是以Web頁面為節(jié)點、頁面之間超鏈為有向邊所構(gòu)成的網(wǎng)狀結(jié)構(gòu)的有向圖，把Web看成是一個巨大的有向圖G=(V,E)，結(jié)點v∈V代表一個Web頁面，有向邊(p,q)∈E代表從結(jié)點p指向結(jié)點q的超鏈接。結(jié)構(gòu)挖掘就是要在這樣的網(wǎng)絡(luò)有向圖中進行超鏈分析。通過分析超鏈可以獲悉網(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表示成樹形結(jié)構(gòu)，文檔表示成URL中的目錄路徑結(jié)構(gòu)，站點之間通過超鏈同其它相關(guān)聯(lián)的站點或頁面相鏈接。相關(guā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è)計人員通常愿意鏈接可信度高的網(wǎng)站。因而一個網(wǎng)站的可信度可以根據(jù)它所鏈接的網(wǎng)站的權(quán)威程度來衡量,同時它會推薦給用戶許多好的權(quán)威網(wǎng)站，對其它網(wǎng)站的權(quán)威性起到了一定程度的增強作用。

3Web結(jié)構(gòu)挖掘的算法

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

3.1HITS算法

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

①Hubs頁，指的是一個指向權(quán)威頁的超鏈接集合的Web頁；

②Authorities頁，指的是被許多Hubs頁指向的權(quán)威的Web頁；

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

其算法步驟如下：

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

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

3)計算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進行反復(fù)修正，直至結(jié)果收斂：

I操作：

O操作：

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

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

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

3.2對HITS算法的改進

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

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

基于HITS算法的這些不足之處本文提出了計算超鏈權(quán)值的解決方案。在頁面的文本中，最能夠代表鏈接頁面語義信息的是超鏈文字(本文僅考慮以文本為載體的超鏈，對以圖像、動畫等為載體的超鏈暫時不作考慮)。超鏈文字是超鏈的載體，通?？梢宰鳛殒溄禹撁鎯?nèi)容的標(biāo)題，因而能夠很好地反映鏈接頁面的語義信息。本文通過引入加權(quán)系數(shù)α來控制超鏈周圍文字在超鏈權(quán)值中所占的比例。

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

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

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

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

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

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

參考文獻

[1]劉麗珍等.網(wǎng)絡(luò)結(jié)構(gòu)挖掘的關(guān)鍵分析.計算機應(yīng)用研究,2003(5)116-118

[2]陳定權(quán).Web結(jié)構(gòu)挖掘研究.情報理論與實踐,2003(1)59-61

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

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