Web 信息顆粒關(guān)聯(lián)強度研究

劉平峰，楊 柳，姚夢迪，吳 鐘

(1.武漢理工大學(xué) 經(jīng)濟學(xué)院，湖北 武漢430070;2.武漢理工大學(xué) 電子商務(wù)與智能服務(wù)研究中心，湖北 武漢430070;3.武漢理工大學(xué) 華夏學(xué)院，湖北 武漢430223)

圖1 Web 信息顆粒關(guān)聯(lián)強度計算流程圖

Web 信息容量的“爆炸式”增長及其多樣性為人們獲取所需信息和知識帶來了更多機遇，同時這種存有關(guān)聯(lián)關(guān)系的海量信息也給Web 信息的使用帶來了更大挑戰(zhàn)，如何從中挖掘有效信息成為了學(xué)術(shù)界研究的熱點［1］?，F(xiàn)階段Web 信息挖掘主要集中在文本、圖像、視頻等多媒體信息的Web 內(nèi)容挖掘方面［2］和利用網(wǎng)頁超鏈接進(jìn)行分析的Web 結(jié)構(gòu)挖掘方面［3］。Web 結(jié)構(gòu)挖掘也稱鏈接挖掘，是從Web 網(wǎng)頁及其之間的關(guān)聯(lián)網(wǎng)絡(luò)中挖掘人們感興趣的、隱含的和有用的知識［4］。早期BORGES 等提出了超鏈接概率原理［5］;ELANGO 等應(yīng)用超文本概率法發(fā)現(xiàn)了用戶的遷移模式［6］;WEISS 等通過聚類方法分析Web 上的超鏈接結(jié)構(gòu)信息［7］;楊怡玲等將頁面內(nèi)容鏈接比、頁組組內(nèi)鏈接度引入到聚類挖掘中［8］。但是這些Web 結(jié)構(gòu)挖掘研究還遠(yuǎn)不能滿足符合人類認(rèn)知特征的知識服務(wù)的需求。目前有學(xué)者提出從不同粒度對Web 網(wǎng)頁鏈接結(jié)構(gòu)進(jìn)行分析，葛唯益等認(rèn)為研究主要集中在細(xì)粒度實體間鏈接結(jié)構(gòu)和粗粒度文檔間鏈接結(jié)構(gòu)的分析方面［9］;胡軍等把粒計算理論融合到Web 結(jié)構(gòu)研究中，建立了一種基于粒度的Web 結(jié)構(gòu)新模型［10］。

粒計算的引入提高了處理不確定、不完整和海量Web 信息的能力，但是基于粒計算的Web鏈接研究未對粒度間的關(guān)聯(lián)強度做定量分析。筆者在粒度劃分的基礎(chǔ)上研究Web 信息顆粒之間的關(guān)聯(lián)關(guān)系，其具有關(guān)聯(lián)鏈、關(guān)聯(lián)樹和關(guān)聯(lián)網(wǎng)絡(luò)3種結(jié)構(gòu)形式，關(guān)聯(lián)鏈?zhǔn)荳eb 信息顆粒間的基本關(guān)聯(lián)方式，最終形成關(guān)聯(lián)網(wǎng)絡(luò)。筆者把每個Web 信息顆粒抽象為一個等價節(jié)點，節(jié)點間的關(guān)聯(lián)關(guān)系由構(gòu)成信息顆粒的Web 網(wǎng)頁鏈接決定。Web 信息顆粒關(guān)聯(lián)強度計算流程如圖1 所示，首先從海量Web 網(wǎng)頁中選取樣本數(shù)據(jù)，并對數(shù)據(jù)做預(yù)處理操作獲得顆粒間的直接鏈接數(shù)據(jù)，然后根據(jù)預(yù)先設(shè)定的算法計算顆粒間的關(guān)聯(lián)強度并做標(biāo)準(zhǔn)化處理，最后通過比較分析顆粒間的關(guān)聯(lián)強度獲取綜合信息并做出決策。

1 Web 信息顆粒關(guān)聯(lián)強度模型

關(guān)聯(lián)強度是反映兩個Web 信息顆粒之間依賴或聯(lián)系緊密程度的指標(biāo)，在Web 網(wǎng)絡(luò)中用它們之間的鏈接結(jié)構(gòu)來表征。如果兩個或多個Web信息顆粒之間存在關(guān)聯(lián)，那么一個顆粒的出現(xiàn)就可以依據(jù)其他相關(guān)顆粒進(jìn)行預(yù)測，且它們之間的關(guān)聯(lián)強度越強則對另一個顆粒的預(yù)測作用就越大。筆者認(rèn)為關(guān)聯(lián)強度僅由鏈接結(jié)構(gòu)決定，即僅與Web 信息顆粒之間的鏈接次數(shù)和距離相關(guān)，鏈接次數(shù)越多，鏈接距離越短，則關(guān)聯(lián)強度越大。

文獻(xiàn)［11］提出了基于模糊等價關(guān)系的文本多粒度劃分方法，通過模糊等價關(guān)系λ 截集閾值的控制得到不同細(xì)度的信息顆粒，粗粒度劃分包含細(xì)粒度劃分，形成了具有分層遞階結(jié)構(gòu)的Web信息顆粒樹。但是該方法僅限于分析顆粒間簡單的蘊含關(guān)系，缺乏對同層次不同類別信息顆粒關(guān)聯(lián)問題的考慮，也未能計算信息顆粒間的關(guān)聯(lián)強度。筆者基于上述分類體系，把信息顆粒抽象為一個節(jié)點，用實線表示顆粒之間的蘊含關(guān)系，虛線表示顆粒之間存在的鏈接關(guān)系，構(gòu)建如圖2 所示的Web 信息顆粒關(guān)聯(lián)模型。

圖2 Web 信息顆粒關(guān)聯(lián)模型

2 Web 信息顆粒關(guān)聯(lián)強度算法

2.1 基本原理

Web 網(wǎng)頁之間存在大量鏈接，導(dǎo)致由Web 網(wǎng)頁融合而成的信息顆粒之間存有直接或間接的鏈接關(guān)系。根據(jù)社會網(wǎng)絡(luò)權(quán)威等級思想，從一個網(wǎng)頁指向另一個網(wǎng)頁的鏈接暗含傳遞權(quán)威性給目標(biāo)網(wǎng)頁，網(wǎng)頁接收的入鏈越多，網(wǎng)頁的權(quán)威性就越高。指向其他網(wǎng)頁的網(wǎng)頁本身也具有權(quán)威值，指向更多網(wǎng)頁的網(wǎng)頁具有更大的權(quán)威性，即網(wǎng)頁的出鏈越多，網(wǎng)頁的權(quán)威性越高。

筆者不考慮鏈接的方向性問題，即視鏈入鏈出同等重要。設(shè)信息顆粒節(jié)點M中有m個Web網(wǎng)頁，信息顆粒節(jié)點N中有n個Web 網(wǎng)頁，若M、N中的網(wǎng)頁之間存在相互鏈接，則認(rèn)為信息顆粒M、N之間存在直接的鏈接關(guān)系，鏈接強度用一個鄰接矩陣relMN表示：

式中，aij為信息顆粒M中第i個Web 網(wǎng)頁與信息顆粒N中第j個Web 網(wǎng)頁之間的鏈接數(shù)，取值為0 或1。

若M、N中的網(wǎng)頁分別與其他信息顆粒節(jié)點中的網(wǎng)頁存在鏈接，且構(gòu)成一條完整的鏈接路徑，即節(jié)點M經(jīng)過其他節(jié)點到達(dá)N，則認(rèn)為信息顆粒M、N之間存在間接的鏈接關(guān)系，中間經(jīng)過的信息顆粒節(jié)點稱為M、N的中介。假設(shè)節(jié)點M、N之間有h條路徑經(jīng)過k個中介，則稱信息顆粒節(jié)點M、N之間存在h條k+1 步鏈接路徑，其中k為任意一條路徑上的中介數(shù);h為k+1 步鏈接路徑的條數(shù);k+1 步鏈接強度僅與顆粒間的鏈接數(shù)和鏈接路徑中介數(shù)有關(guān)。

2.2 獲取算法

輸入：從海量Web 網(wǎng)頁中選取樣本數(shù)據(jù)，步驟如下。

(1)數(shù)據(jù)預(yù)處理。對樣本W(wǎng)eb 網(wǎng)頁進(jìn)行多粒度劃分生成Web 信息顆粒，信息顆?？倲?shù)為K。

(2)從生成的Web 信息顆粒集中取兩個信息顆粒，分別記為M和N。

(3)令k=0，表示信息顆粒M與N直接鏈接，采用式(1)計算兩者的直接鏈接強度relMN0。

(4)令k=k+1，若k＞K-2，轉(zhuǎn)步驟(6);否則，轉(zhuǎn)步驟(5)。

(5)計算信息顆粒M和N經(jīng)過k步鏈接路徑的鏈接強度relMNk。設(shè)信息顆粒M與N之間k步路徑有h條(h=∏k t=2(K-t))，其中每條路徑的鏈接強度計算如下：

設(shè)信息顆粒M、N之間的第s條k步鏈接路徑上經(jīng)過O、P、Q等k個中介，則有：

其中：relMO、relOP、relQN分別為顆粒M與顆粒O之間、顆粒O與顆粒P之間、顆粒Q與顆粒N之間的直接鏈接強度;aij為顆粒M中第i個網(wǎng)頁與顆粒N中第j個網(wǎng)頁之間的相互鏈接數(shù)。

信息顆粒M與N之間h條k步路徑的鏈接強度為：

轉(zhuǎn)步驟(4)。

(6)計算k步鏈接強度權(quán)重。隨著鏈接距離變長，鏈接步數(shù)增多，鏈接關(guān)系對顆粒之間關(guān)聯(lián)關(guān)系的控制影響逐漸減弱，鏈接強度權(quán)重與鏈接步數(shù)成反比，那么k步鏈接強度的權(quán)重

(7)計算M與N之間的關(guān)聯(lián)強度。信息顆粒M與N之間的關(guān)聯(lián)強度

(8)重復(fù)步驟(2)～步驟(7)，直到信息顆粒集中所有顆粒兩兩間的關(guān)聯(lián)強度計算完畢。

(9)標(biāo)準(zhǔn)化處理。將信息顆粒M與N之間的關(guān)聯(lián)強度表示為數(shù)值形式所有顆粒的關(guān)聯(lián)強度用一個鄰接矩陣Bij表示，Bij=其中bij表示第i個信息顆粒與第j個信息顆粒之間的關(guān)聯(lián)強度。對關(guān)聯(lián)強度矩陣進(jìn)行標(biāo)準(zhǔn)化處理，使所有取值在［0，1］之間，即

輸出：樣本顆粒間的關(guān)聯(lián)強度。

3 實驗分析

考慮Web 文檔間廣泛的鏈接關(guān)系，筆者選取中文維基百科(http：//zh. wikipedia. org)作為數(shù)據(jù)源，從其海量的Web 網(wǎng)頁中選取“人工智能”類下的83 個Web 頁面作為樣本數(shù)據(jù)。對樣本W(wǎng)eb網(wǎng)頁按照維基百科數(shù)據(jù)中的分類方式進(jìn)行多粒度劃分，生成Web 信息顆粒樹，如圖3 所示。

現(xiàn)計算第3 層Web 信息顆粒之間的關(guān)聯(lián)度，由于每個顆粒包含不同數(shù)量的頁面。統(tǒng)計每個顆粒下頁面之間相互鏈接的情況，形成鄰接矩陣。

由實驗結(jié)果可知，存在鏈接的信息顆粒為機器人(A)、人型機器人學(xué)(B)、賽博格(C)、自然語言處理(E)、計算語言學(xué)(F)這5 個顆粒。節(jié)點A、C之間存在1 條1 步鏈接路徑即為直接鏈接，其鏈接強度步鏈接強度的權(quán)重ω1= 1;1 條2 步鏈接路徑的鏈接強度步鏈接強度的權(quán)重ω2=1/2;根據(jù)步驟(7)得出信息顆粒A與C之間的關(guān)聯(lián)強度將信息顆粒A、C之間的關(guān)聯(lián)強度表示成數(shù)值形式為5/2;同理，信息顆粒A、B之間的關(guān)聯(lián)強度表示成數(shù)值形式為1;信息顆粒B、C之間的關(guān)聯(lián)強度表示成數(shù)值形式為1。節(jié)點E、F之間僅存在直接鏈接，其關(guān)聯(lián)強度為7。對顆粒間的關(guān)聯(lián)強度進(jìn)行歸一化計算，所有Web 信息顆粒的關(guān)聯(lián)強度用一個鄰接矩陣表示：

圖3 Web 信息顆粒實例模型

實驗顯示，自然語言學(xué)和計算語言學(xué)兩個信息顆粒之間關(guān)聯(lián)強度較大，關(guān)系密切，有必要將兩者結(jié)合起來研究，為綜合決策提供數(shù)據(jù)支持。這表明通過計算Web 信息顆粒間的關(guān)聯(lián)強度，能夠識別顆粒間的相關(guān)關(guān)系，更加準(zhǔn)確、全面地揭示主題信息。

4 結(jié)論

從不同的Web 信息顆粒得到的信息是不同的，信息的片面性會給信息使用者的決策帶來負(fù)面影響。通過Web 信息顆粒中網(wǎng)頁的鏈接結(jié)構(gòu)計算顆粒間的關(guān)聯(lián)強度，能夠更加全面地反映顆粒間的關(guān)聯(lián)關(guān)系，從而更加準(zhǔn)確地揭示主題相關(guān)的綜合信息。筆者經(jīng)過數(shù)據(jù)選樣和預(yù)處理生成多層次Web 信息顆粒，計算顆粒間的關(guān)聯(lián)強度，分析比較得到綜合決策信息。有效地解決了單一信息帶來的決策偏差問題。但是該算法只是考慮了顆粒間的鏈接關(guān)系，忽略了顆粒本身的文本內(nèi)容，可能會出現(xiàn)一定程度的主題偏離現(xiàn)象。

［1］ 張琰，王強，安萍. 基于Web 文本挖掘相關(guān)技術(shù)的研究［J］.科協(xié)論壇，2012(9)：83 -84.

［2］ 董慧，唐敏. 數(shù)據(jù)挖掘及其在網(wǎng)絡(luò)信息檢索中的應(yīng)用［J］.情報雜志，2010，29(B06)：153 -156.

［3］ 龐英智. Web 數(shù)據(jù)挖掘技術(shù)在電子商務(wù)中的應(yīng)用［J］.情報科學(xué)，2011，29(2)：235 -240.

［4］ 吉根林，趙斌.面向大數(shù)據(jù)的時空數(shù)據(jù)挖掘綜述［J］.南京師大學(xué)報(自然科學(xué)版)，2014，37(1)：1-7.

［5］ BORGES J，LEVENE M. An average linear time algorithm for web usage mining［J］.International Journal of Information Technology ＆ Decision Making，2004，3(2)：307 -319.

［6］ ELANGO A，BOLLEN J，NELSON M L.Dynamic linking of smart digital objects based on user navigation patterns［DB/OL］. ［2015 - 01 - 26］. arxiv preprintcs/0401029.

［7］ WEISS R，VELEZ B，SHELDON M A.HyPursuit：a hierarchical network search engine that exploits content- link hypertext clustering［C］//Proceedings of the Seventh ACM Conference on Hypertext.［S.l.］：ACM，1996：180 -193.

［8］ 楊怡玲，管旭東，尤晉元.基于頁面內(nèi)容和站點結(jié)構(gòu)的頁面聚類挖掘算法［J］. 軟件學(xué)報，2002，23(3)：467 -469.

［9］ 葛唯益，程龔，瞿裕忠.語義Web 鏈接結(jié)構(gòu)分析之綜述［J］.計算機科學(xué)，2010，37(3)：17 -21.

［10］ 胡軍，陳傳明. 一種基于粒度的Web 結(jié)構(gòu)模型［C］//Proceedings of 2010 International Conference on Circuit and Signal Processing ＆ 2010 Second IITA International Joint Conference on Artificial Intelligence.上海：［s.n.］，2010：100 -103.

［11］ 劉平峰，余文艷，游懷杰.基于模糊等價關(guān)系的文本多粒度劃分方法［J］.情報學(xué)報，2012，31(6)：589-594.