劉平峰，楊 柳，姚夢(mèng)迪，吳 鐘

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

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

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

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

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

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

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

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

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

2.1 基本原理

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

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

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

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

2.2 獲取算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

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

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

圖3 Web 信息顆粒實(shí)例模型

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

4 結(jié)論

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

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

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

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

［4］ 吉根林，趙斌.面向大數(shù)據(jù)的時(shí)空數(shù)據(jù)挖掘綜述［J］.南京師大學(xué)報(bào)(自然科學(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］ 楊怡玲，管旭東，尤晉元.基于頁(yè)面內(nèi)容和站點(diǎn)結(jié)構(gòu)的頁(yè)面聚類(lèi)挖掘算法［J］. 軟件學(xué)報(bào)，2002，23(3)：467 -469.

［9］ 葛唯益，程龔，瞿裕忠.語(yǔ)義Web 鏈接結(jié)構(gòu)分析之綜述［J］.計(jì)算機(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］ 劉平峰，余文艷，游懷杰.基于模糊等價(jià)關(guān)系的文本多粒度劃分方法［J］.情報(bào)學(xué)報(bào)，2012，31(6)：589-594.