面向網(wǎng)絡(luò)的語義Web社區(qū)提取算法

陳麗萍

（巢湖學(xué)院計(jì)算機(jī)系，安徽巢湖238000）

面向網(wǎng)絡(luò)的語義Web社區(qū)提取算法

陳麗萍

（巢湖學(xué)院計(jì)算機(jī)系，安徽巢湖238000）

Web社區(qū)是Web組織中非常重要的信息，將其用于信息搜索策略中可從本質(zhì)上改善信息檢索的結(jié)果，為用戶提供潛在、及時(shí)、準(zhǔn)確的信息；如何發(fā)現(xiàn)這些高精度的社區(qū)，進(jìn)而快速?gòu)木W(wǎng)上找到更多關(guān)于某一主題的網(wǎng)頁是Web數(shù)據(jù)資源挖掘領(lǐng)域的熱點(diǎn).本文提出了一種多尺度語義Web社區(qū)提取算法，該算法很好的將語義信息融入到傳統(tǒng)的社區(qū)模型中.實(shí)驗(yàn)表明，該算法提取的社區(qū)精度高，且漏檢率較低，社區(qū)結(jié)構(gòu)與其所對(duì)應(yīng)的語義產(chǎn)生了較好的映射關(guān)系.它為信息檢索的社區(qū)化奠定了重要的理論基礎(chǔ).

Web社區(qū)；語義；超鏈接分析；Web拓?fù)浣Y(jié)構(gòu)

1 引言

如何在急劇膨脹的海量級(jí)、碎片化的Web信息資源中抽取出潛在的、有價(jià)值的，及時(shí)的信息，進(jìn)而充分高效地利用Web這個(gè)龐大的信息知識(shí)庫(kù)，是當(dāng)今信息檢索領(lǐng)域重要又極具挑戰(zhàn)性的研究課題[1].

盡管Web數(shù)據(jù)存在無組織、海量的特點(diǎn)，但是Web仍存在一些規(guī)律.從微觀上看，Web由根據(jù)“主題”聚集在一起的多個(gè)社區(qū)組成[2]，體現(xiàn)在Web圖上就是鏈接比較稠密的一些子圖[3].Web社區(qū)[4]是指具有相同興趣、愛好或者關(guān)注相同話題的一組用戶所建立起來的一組網(wǎng)頁/站點(diǎn)，這些頁面通過鏈接的方式相互引用.這些社區(qū)提供了特定主題下的相關(guān)資源.因此通過識(shí)別社區(qū)可為用戶提供有價(jià)值、可靠、及時(shí)的信息.

基于Web頁面鏈接的主題爬行技術(shù)在Web社區(qū)分析與提取領(lǐng)域有較大的影響.但基于此技術(shù)的算法往往提取的社區(qū)與真正的Web內(nèi)容聚團(tuán)結(jié)構(gòu)有偏差.已有很多研究者試圖將頁面內(nèi)容屬性與鏈接結(jié)合起來，對(duì)此類算法進(jìn)行改進(jìn)[5,6].但是效果還是比較有限.本文將Web頁面語義信息很好的融入到微觀拓?fù)浣Y(jié)構(gòu)中，提出一種有效的多尺度語義社區(qū)挖掘算法，提取的社區(qū)中拓?fù)浣Y(jié)構(gòu)和內(nèi)容聚團(tuán)性之間有很好的映射關(guān)系.

2 社區(qū)挖掘算法HITS

在社區(qū)提取技術(shù)中，以HITS為代表的鏈接分析技術(shù)影響相當(dāng)廣泛.HITS算法中引入了權(quán)威網(wǎng)頁和中心網(wǎng)頁的概念.中心頁面與權(quán)威頁面形成一個(gè)互相加強(qiáng)的鏈接關(guān)系圖：好的中心頁面指向許多好的權(quán)威頁面，而好的權(quán)威頁面被許多好的中心頁面所指向.HITS算法具體可描述為：①通過文本分析，經(jīng)過關(guān)鍵詞匹配得到與主題相關(guān)的一定數(shù)量r的頁面構(gòu)成根集合(root)R；②然后向根集合中擴(kuò)充那些所有指向R的頁面和所有R指向的頁面，得到頁面基礎(chǔ)集(base)B；③為基礎(chǔ)集B中每個(gè)頁面p賦予一個(gè)非負(fù)的Authority權(quán)重ap和非負(fù)的Hub權(quán)重hp，這樣基礎(chǔ)集B中所有頁面的Athority權(quán)威值可表示為權(quán)威向量a=(a1,a2,…,an)，Hub中心值可表示為中心向量h=(h1,h2,…,hn).④將所有的Authority和Hub的初始值均設(shè)為1，操作In(a)使向量a=ATh,而操作Out(h)使向量h=Aa.反復(fù)迭代上述兩個(gè)操作,每次迭代后對(duì)向量a和h范化.求得每個(gè)頁面的ap和hp，直到ap和hp恒定為止.最終得到一組具有最大Authority值和最大Hub值的頁面.

HITS算法在執(zhí)行迭代計(jì)算時(shí)，完全基于鏈接結(jié)構(gòu)的，對(duì)每條邊賦予相同的權(quán)值，忽略了網(wǎng)頁所具有的語義信息.這樣使得單純以鏈接分析所得Web社區(qū)可能會(huì)產(chǎn)生語義歧義或者錯(cuò)誤.

3 多尺度語義Web社區(qū)提取算法

3.1 基本思想

Web中建立鏈接目的多種多樣，這些鏈接代表不同組織和個(gè)人的判斷，因此在社區(qū)提取過程中，完全基于鏈接結(jié)構(gòu)、不加區(qū)分的對(duì)待、平均的分配權(quán)值不符合鏈接的實(shí)際情況，將會(huì)造成提取的社區(qū)內(nèi)容有偏差.事實(shí)上，重要度高的Hub頁是指向許多具有較高Anthority值的頁面；反過來，重要度高的Authority頁是由許多具有較高的Hub值所指向的頁面.因此認(rèn)為，連接重要度高的頁面的鏈接質(zhì)量更高.另外，Web頁面間語義主題相似度越高，說明網(wǎng)頁間相關(guān)度越高，則它們之間的鏈接質(zhì)量也更高.因此，本文基于HITS算法，結(jié)合鏈接質(zhì)量和頁面語義主題相似度提出了多尺度的語義社區(qū)提取算法.

3.2 鏈接質(zhì)量計(jì)算

根據(jù)其鏈接的網(wǎng)頁i,j的重要度計(jì)算link(i,j)的質(zhì)量.文獻(xiàn)[7]提出網(wǎng)頁的權(quán)重（重要度）計(jì)算公式如下：

這里，Piin和Piout分別為依據(jù)頁面i的入鏈信息和出鏈信息確定的頁面權(quán)重；Njin和Njout分別為頁面j的鏈入數(shù)量和鏈出數(shù)量；B(i)為頁面i的鏈入頁面集合；F(i)為頁面i的鏈出頁面集合；Pjout和Pjin分別為頁面j作為鏈出頁面的權(quán)重和作為鏈入頁面的權(quán)重，其初值均設(shè)為1.對(duì)所有的頁面按公式(1)，(2)反復(fù)迭代計(jì)算，直到所有的Piout和Piin恒定為止.

通過公式(1)、(2)得到的網(wǎng)頁重要度，Web中頁面的鏈接質(zhì)量計(jì)算根據(jù)其連接的方向，可分為兩類情況：

⑴若web鏈接如圖1所示，同是作為鏈入頁面的B1，B2和B3.通過式(1)，(2)計(jì)算，PB1in大于PB2in和PB3in，則說明頁面B1的重要度更高.由此可得，link(A1,B1)=PB1in質(zhì)量高于link(A1,B2)=PB2in和link(A1,B3)=PB3in；

圖1 web鏈接圖(1)

⑵若web鏈接如圖2所示，同是作為鏈出頁面的A1，A2和A3.通過式(1)，(2)計(jì)算，PA1out大于PA2out和PA3out，則說明頁面A1重要度更高，由此可得，link(A1,B3)=PA1out質(zhì)量高于link(A2,B3)=PA2out和link(A3,B3)=PA3out.

圖2 web鏈接圖(2)

3.3 語義相似度計(jì)算

本文認(rèn)為采用單一的關(guān)鍵詞匹配方式來評(píng)估頁面的相似度勢(shì)必會(huì)影響查準(zhǔn)率與查全率.因?yàn)殛P(guān)鍵詞會(huì)出現(xiàn)一詞多義、一義多詞以及同一事物多種表述的情形.概念并不是孤立存在的，一個(gè)概念總是與其他概念之間存在著各種各樣的關(guān)系，如上下位關(guān)系、同義關(guān)系、反義關(guān)系等.例如“notebook”在語義上和“l(fā)aptop”這個(gè)單詞具有相關(guān)性，機(jī)械匹配的話就只能檢索到有關(guān)“notebook”或“l(fā)aptop”的信息.WordNet，它作為語言學(xué)本體庫(kù)，同時(shí)又是一部語義詞典，在自然語言處理研究方面應(yīng)用非常廣泛.

本文將利用wordnet來衡量?jī)蓚€(gè)詞語的語義相似度.如下圖所示：

圖3 wordnet下義詞分類圖

在圖4中，car與automobile的距離為1，car與truck的距離為3，car與knife的距離為12.則兩個(gè)詞語語義相似度計(jì)算公式可以定義為：

這里，distance代表從s,t的路徑長(zhǎng)度（用節(jié)點(diǎn)個(gè)數(shù)記錄）.

設(shè)查詢向量Q=(w1q,w2q,…，wtq)∈Rt,網(wǎng)頁向量Vj=(w1j,w2j,…wij)∈Rt，則查詢和網(wǎng)頁語義相似度由式(4)求解所得.

3.4 算法實(shí)現(xiàn)

下面給出基于HITS算法的多尺度語義社區(qū)提取算法迭代過程如下：

Step1、Step2、Step3同HITS算法，即通過搜索引擎得到某一查詢的結(jié)果集合作為根集合R，對(duì)R集合進(jìn)行擴(kuò)展生成基礎(chǔ)集合B，并將各網(wǎng)頁的中心值和權(quán)威值初始化為1；

Step4：應(yīng)用公式(1)(2)計(jì)算link(i,j)的質(zhì)量，qin=Piout，qout=Pjin；

Step5：應(yīng)用公式(4)計(jì)算集合B中的頁面語義主題相似度sj=SIM(Q,Vj)；

Step6：對(duì)B中所有頁面，按下式迭代計(jì)算直到收斂：

4 實(shí)驗(yàn)及性能分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證算法的結(jié)果和有效性，本文選用3個(gè)經(jīng)典主題abortion,movies,computer作為本實(shí)驗(yàn)的查詢主題，首先，對(duì)于3個(gè)主題，都通過Google搜索引擎獲得排名最靠前的30個(gè)頁面作為root集的頁面.

接著把root集進(jìn)一步擴(kuò)展為base集，通過分析html文檔獲取root集中所有頁面指向的頁面；以及所有指向root集中頁面的頁面（反向鏈接頁面）且這些網(wǎng)頁數(shù)量限至在50個(gè)頁面，本實(shí)驗(yàn)使用Yahoo!SiteExplorer（link:網(wǎng)址）獲得反向鏈接頁面.這樣分別得到對(duì)應(yīng)主題的1323,1506和1627個(gè)頁面作為實(shí)驗(yàn)數(shù)據(jù)集.采用這個(gè)數(shù)據(jù)集對(duì)單純以鏈接結(jié)構(gòu)提取社區(qū)的HITS算法和多尺度語義社區(qū)提取算法進(jìn)行實(shí)驗(yàn).為了比較算法的結(jié)果，這里分別引入相關(guān)度和漏檢度的概念，式(5)給出了相關(guān)度計(jì)算：

式(6)給出了漏檢度計(jì)算：

4.2 實(shí)驗(yàn)結(jié)果分析

將實(shí)驗(yàn)中單純以鏈接結(jié)構(gòu)分析的HITS算法提取的社區(qū)中前50個(gè)頁面和多尺度語義社區(qū)提取算法提取的社區(qū)前50個(gè)頁面分別與主題進(jìn)行比較，頁面主題相關(guān)度比對(duì)如圖4所示.

圖4 網(wǎng)頁相關(guān)度比對(duì)

將實(shí)驗(yàn)中單純以鏈接結(jié)構(gòu)分析的HITS算法提取的社區(qū)頁面和多尺度語義社區(qū)提取算法提取的社區(qū)頁面統(tǒng)計(jì)分析，漏檢度比對(duì)如圖5所示.

圖5 網(wǎng)頁漏檢度比對(duì)

由此可見，多尺度語義社區(qū)提取算法提高了返回結(jié)果的精確度，使得頁面的主題相關(guān)度提高了18%-49%，且降低了頁面漏檢度，能夠從語義層次處理檢索主題.表明此算法提取的社區(qū)結(jié)構(gòu)與其所對(duì)應(yīng)的語義產(chǎn)生了較好的映射關(guān)系.

5 結(jié)語

單純使用鏈接分析抽取的社區(qū)結(jié)構(gòu)會(huì)造成社區(qū)的語義產(chǎn)生歧義.主要原因在于完全基于鏈接結(jié)構(gòu)的方法對(duì)每條邊賦予相同的權(quán)值，忽略了網(wǎng)頁所具有的語義信息.本文提出的多尺度語義社區(qū)提取算法.很好的將語義信息融入到傳統(tǒng)鏈接結(jié)構(gòu)中.實(shí)驗(yàn)表明，此算法提取的社區(qū)結(jié)構(gòu)與其所對(duì)應(yīng)的語義產(chǎn)生了較好的映射關(guān)系，對(duì)于檢索的社區(qū)化研究有著重要的理論和實(shí)際應(yīng)用價(jià)值.

〔1〕JPrasanna Kumar,PGovindarajulu．Duplicate and Near DuplicateDocumentsDetection:AReview[J]．European Journal of Scientific Research，2009：514-527．

〔2〕Andrei Broder，RaviKumar，etal．Graph Structure in the Web:ExperimentsandModela[C]．Proc．ofthe9th WWW Conference．Amaterdam，2000：309-320．

〔3〕Brian Davison．Topical Locality in the Web[C]．Proceeding of the 23rd’Annual International Conference on Research and Development in Information Retrieval(SIGIR 2000)，Athens,Greece，2000：272-279．

〔4〕RaviKumar，abhakarRaghavan，SridharRajagopalan，Andrew Tomkins．Trawling the Web for emerging cyber-communities[C].Proceedingsofthe8thACMWWWInternationalConference．Toronto：ACMPress，1999：1481-1493．

〔5〕Krishna Bharat,Monika R.Henzinger.Improved Algorithms for Topic Distillation in a Hyperlinked Environment[C].In Proceedings of the ACM-SIGIR,1998.

〔6〕S.Chakrabarti,B.Dom,P.Raghavan,S.Rajagopalan, D.Gibson,J.Kleinberg.Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text[C].In Proceedings of the 7th International World Wide Web Conference,1998.

〔7〕Jun Lai,Ben Soh,Chai Fei.A Web Page Ranking Method by Analyzing Hyperlink Structure and K-elements[J].M.Gavrilova et al.(Eds.):Computer Science and Its Application 2006,LNCS 3983.Spring-Verlag Berlin Heidelberg(2006):179-186.

TP39

A

1673-260X（2013）03-0015-03

巢湖學(xué)院自然科學(xué)研究項(xiàng)目（XLY-201014）；安徽省教育廳基金(KJ2010B125）