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

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

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

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

Web作為目前Internet的主要信息渠道，包含了豐富的、動(dòng)態(tài)的超鏈接信息，這為數(shù)據(jù)挖掘提供了豐富的資源。現(xiàn)有的知識(shí)發(fā)現(xiàn)(KDD)的方法和技術(shù)已不能滿足人們從Web中獲取知識(shí)的需要。許多時(shí)候人們苦于在巨大的網(wǎng)絡(luò)世界中不容易找到自己感興趣的、權(quán)威的內(nèi)容。所以人們迫切需要找到這樣的工具，能夠從WEB上快速地、有效地發(fā)現(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)挖掘是指通過(guò)分析不同網(wǎng)頁(yè)之間的超鏈結(jié)構(gòu)，發(fā)現(xiàn)許多蘊(yùn)涵在Web內(nèi)容之外的對(duì)我們有潛在價(jià)值的模式和知識(shí)的過(guò)程。

2結(jié)構(gòu)挖掘

WWW沒有數(shù)據(jù)庫(kù)那樣嚴(yán)格統(tǒng)一的語(yǔ)義模式，但也不像平面文件那樣完全沒有結(jié)構(gòu)，從信息結(jié)構(gòu)的角度來(lái)看，WWW上的資源有三種類型：結(jié)構(gòu)化資源、半結(jié)構(gòu)化資源和無(wú)結(jié)構(gòu)化資源，它的語(yǔ)義隱含在語(yǔ)法結(jié)構(gòu)之中。忽略掉Web頁(yè)面上的文本和其它內(nèi)容，只考慮頁(yè)面間的超鏈，WWW可以被看作是以Web頁(yè)面為節(jié)點(diǎn)、頁(yè)面之間超鏈為有向邊所構(gòu)成的網(wǎng)狀結(jié)構(gòu)的有向圖，把Web看成是一個(gè)巨大的有向圖G=(V,E)，結(jié)點(diǎn)v∈V代表一個(gè)Web頁(yè)面，有向邊(p,q)∈E代表從結(jié)點(diǎn)p指向結(jié)點(diǎn)q的超鏈接。結(jié)構(gòu)挖掘就是要在這樣的網(wǎng)絡(luò)有向圖中進(jìn)行超鏈分析。通過(guò)分析超鏈可以獲悉網(wǎng)站的受歡迎程度及與其它網(wǎng)站的關(guān)系，而且，通過(guò)網(wǎng)頁(yè)之間的鏈接還能夠快速了解一個(gè)網(wǎng)站的內(nèi)部結(jié)構(gòu)。WWW是一個(gè)超文本文檔信息系統(tǒng)，而超鏈?zhǔn)潜硎拘畔⒌囊粋€(gè)重要方式，所以挖掘超鏈的語(yǔ)義結(jié)構(gòu)十分必要和有意義。

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

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

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

3.1HITS算法

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

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

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

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

其算法步驟如下：

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

2)將Rδ進(jìn)行擴(kuò)充，對(duì)Rδ中每一個(gè)結(jié)點(diǎn)，將所有指向該結(jié)點(diǎn)或該結(jié)點(diǎn)所指向的網(wǎng)頁(yè)補(bǔ)充進(jìn)來(lái)，形成基集，記為Sδ.

3)計(jì)算Sδ中每一個(gè)網(wǎng)頁(yè)的Authority權(quán)重和Hub權(quán)重，這是一個(gè)遞歸過(guò)程.

先將網(wǎng)頁(yè)p的Authority權(quán)重記為ap，Hub權(quán)重記為hp，為Sδ中所有網(wǎng)頁(yè)賦初值：ap(0)←1，hp(0)←1；再通過(guò)以下迭代公式對(duì)ap和hp進(jìn)行反復(fù)修正，直至結(jié)果收斂：

I操作：

O操作：

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

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

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

3.2對(duì)HITS算法的改進(jìn)

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

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

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

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

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

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

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

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

本文在分析網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上，介紹了結(jié)構(gòu)挖掘中HITS算法模型，并針對(duì)其弱點(diǎn)提出了改進(jìn)方案。對(duì)于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-118

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

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

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