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

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

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

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

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

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

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

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

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

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

2.1 基本原理

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

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

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

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

2.2 獲取算法

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

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

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

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

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

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

設信息顆粒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步路徑的鏈接強度為：

轉步驟(4)。

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

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

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

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

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

3 實驗分析

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

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

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

圖3 Web 信息顆粒實例模型

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

4 結論

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

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

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

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

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

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

［10］ 胡軍，陳傳明. 一種基于粒度的Web 結構模型［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］ 劉平峰，余文艷，游懷杰.基于模糊等價關系的文本多粒度劃分方法［J］.情報學報，2012，31(6)：589-594.