以互信息為度量的一種規(guī)則可視化

謝霖銓，章恩

江西理工大學(xué)理學(xué)院，江西贛州 341000

以互信息為度量的一種規(guī)則可視化

謝霖銓，章恩

江西理工大學(xué)理學(xué)院，江西贛州 341000

概念格是一種有效的知識(shí)表示和知識(shí)發(fā)現(xiàn)的工具，已被成功應(yīng)用于許多領(lǐng)域，然而在建格上大多是利用最小支持度以及置信度來(lái)進(jìn)行約簡(jiǎn)操作，同時(shí)利用置信度來(lái)進(jìn)行規(guī)則提取。提出以信息論的互信息來(lái)構(gòu)造具有強(qiáng)關(guān)聯(lián)規(guī)則的Hasse圖，并利用互信息進(jìn)行規(guī)則提取。

強(qiáng)關(guān)聯(lián)規(guī)則；概念格；互信息；規(guī)則提??；數(shù)據(jù)挖據(jù)

1 概述

自從W ille R教授[1]首先提出形式概念分析以來(lái)，形式概念分析已被證明是進(jìn)行數(shù)據(jù)分析的有力工具。在應(yīng)用概念格的過(guò)程中，格的構(gòu)造[2]問(wèn)題以及規(guī)則提取一直是研究的熱點(diǎn)。傳統(tǒng)的串行可以分為批處理和漸進(jìn)式構(gòu)造算法。批處理算法的思想是首先生成所有的概念集合，然后再生成概念之間的直接前驅(qū)和后繼關(guān)系或者是每次生成少量的概念，并將這些概念鏈接到節(jié)點(diǎn)集合中。如：Bordat算法[3]。漸進(jìn)式算法的思想是先初始化概念格為空，將當(dāng)前要插入的對(duì)象和現(xiàn)有格中的所有的形式概念作交運(yùn)算，然后采取不同的行動(dòng)，如Godin[4]等。規(guī)則提取有：利用支持度和信任度來(lái)提取強(qiáng)關(guān)聯(lián)規(guī)則[5]、進(jìn)行無(wú)冗余規(guī)則提取[6]、利用內(nèi)涵縮減[7]進(jìn)行規(guī)則提取[8]及文獻(xiàn)[9]等。但卻鮮見(jiàn)構(gòu)成的Hasse圖能直接可視化其內(nèi)部的規(guī)則。

本文給出的建格方法是：首先根據(jù)形式背景利用FP-TREE的第一次掃描數(shù)據(jù)庫(kù)得到項(xiàng)目列表，根據(jù)所得的列表進(jìn)行形式背景的約簡(jiǎn)，求出形式背景的單元概念的秩，再利用對(duì)于概念的內(nèi)涵和外延作并集和交集的運(yùn)算，利用互信息的性質(zhì)進(jìn)行建格約簡(jiǎn)操作，得到所需的具有強(qiáng)關(guān)聯(lián)規(guī)則的概念格Hasse圖，然后利用信息論的互信息M I來(lái)進(jìn)行強(qiáng)關(guān)聯(lián)分析與規(guī)則提取。在所得到的Hasee圖中可發(fā)現(xiàn)其規(guī)則是有可視化性。

2 相關(guān)概念

定義1[10]在關(guān)聯(lián)規(guī)則挖掘中，項(xiàng)集就是項(xiàng)的集合，k項(xiàng)集是包含k項(xiàng)的項(xiàng)集，稱為k項(xiàng)集，給定數(shù)據(jù)庫(kù)D和最小支持度閾值M in，對(duì)于項(xiàng)集(O，A)，如果該項(xiàng)集的支持度Sup≥M in，則稱該項(xiàng)集為頻繁項(xiàng)集。

定義2[11]定義在項(xiàng)目集I和事物數(shù)據(jù)集D上形如I1?I2的關(guān)聯(lián)規(guī)則的可信度是指包含I1和I2的事務(wù)數(shù)與包含I1的事務(wù)數(shù)之比，簡(jiǎn)記為Conf(I1?I2)即Conf(I1?I2)=Sup(I1∪I2)/Sup(I1)。其中，I1，I2?I，I1∩I2=φ。

定義3[12]對(duì)于頻繁項(xiàng)集(O，A)，并且對(duì)于子節(jié)點(diǎn)(O1，A1)。可以得知(O，A)的支持度Sup≥(O1，A1)的支持度Sup。但增加任何一項(xiàng)其支持度Sup＜M in，則稱(O，A)為最大頻繁項(xiàng)集。

根據(jù)定義可知：

性質(zhì)1[13-14]最大頻繁項(xiàng)的父節(jié)點(diǎn)一定是頻繁項(xiàng)集。

性質(zhì)2[13、14]最大頻繁項(xiàng)的子節(jié)點(diǎn)一定是非頻繁項(xiàng)集。

推論1當(dāng)某項(xiàng)集節(jié)點(diǎn)是非頻繁項(xiàng)集時(shí)，則包含該節(jié)點(diǎn)內(nèi)涵的所有項(xiàng)集都是非頻繁項(xiàng)集。

定義4[1]在形式概念的分析中，概念的形式化背景定義為一個(gè)三元組(O，A，R)，O代表的是形式對(duì)象Object的集合，A代表的是形式屬性A ttribute的集合，R代表的是對(duì)象O和屬性A之間的二元關(guān)系Relation。即R?O×A。

定義5[11]格L的每一節(jié)點(diǎn)為一序偶，記為＜X，Y＞，其中X是實(shí)例集合稱為概念的外延，Y是X中所有實(shí)例共同具有的屬性集合稱為概念的內(nèi)涵，每一序偶相對(duì)于關(guān)系R是完備的，即

定義6[7]假設(shè)有下面的H1=(O1，A1)，H2=(O2，A2)∈L，L代表格，如果A1?A2或O1?O2，則稱H1是H2的子概念（節(jié)點(diǎn)），H2是H1的父節(jié)點(diǎn)?？尚问交硎緸镠1≤H2。

定義7對(duì)于概念C=(O，A)，稱Q為C的量化（Quantitation）概念，其Q是A外延的基數(shù)。顯然生成的量化概念格和原概念格是同構(gòu)的。

定義8設(shè)(G，M，L)為一形式背景，L(G，M，L)概念格，(A，B)∈L(G，M，L)，則(A，B)或者是存在m∈B，使得r(m)=|A|，且(A，B)=({m}+，{m}++)，或者為(A，B)的兩個(gè)直接父節(jié)點(diǎn)的交。

定義10[15]互信息熵：描述了某個(gè)變量取值對(duì)另一個(gè)變量取值的確定的能力。其值越大2個(gè)變量間的確定能力越強(qiáng)。2個(gè)變量x，y的互信息熵M I(x，y)定義為：

且I(x，y)=H(x)-H(x|y)=H(y)-H(y|x)。

定義11[15]互信息在信息論中是作為一種衡量2個(gè)信號(hào)關(guān)聯(lián)程度的尺度。后來(lái)引申為2個(gè)隨機(jī)變量間的關(guān)聯(lián)程度進(jìn)行統(tǒng)計(jì)描述，可表示成這2個(gè)隨機(jī)變量的概率的函數(shù)。假設(shè)M I(X，Y)為隨機(jī)變量X和Y的互信息，則M i(x，y)=lb p(x，y)p(x)p(y)，其中p(x，y)=和P(y)分別是x和y獨(dú)立出現(xiàn)的概率。P(x，y)是x和y同時(shí)出現(xiàn)的概率，當(dāng)M I(x，y)＞＞0時(shí)，表明x和y的關(guān)聯(lián)程度強(qiáng)。M I(x，y)=0時(shí)，表明x和y的關(guān)聯(lián)程度弱，它們的同時(shí)出現(xiàn)僅屬于偶然。當(dāng)M I(x，y)＜＜0時(shí)，表明x，y互補(bǔ)分布，不存在關(guān)聯(lián)關(guān)系。

例1形式背景如表1所示。

表1 形式背景

則由表1（其中H在分類中表示為C1標(biāo)簽和C2標(biāo)簽，為了對(duì)數(shù)據(jù)的預(yù)處理在進(jìn)行下文的關(guān)聯(lián)規(guī)則中將C1替換為0，C2為1）得到的邊緣概念根據(jù)秩的大小進(jìn)行排序得到：C1=(E，5)，C2=(A，3)，C3=(C，3)，C4=(D，3)，C5=(B，2)，C6=(F，2)，C7=(G，1)。

3 算法描述及實(shí)例驗(yàn)證

本文基于互信息提出強(qiáng)關(guān)聯(lián)規(guī)則的建格約簡(jiǎn)，以互信息的性質(zhì)可以知道經(jīng)過(guò)約簡(jiǎn)后的Hasse圖的內(nèi)涵是具有強(qiáng)關(guān)聯(lián)關(guān)系，在規(guī)則提取中也表現(xiàn)出很大的優(yōu)勢(shì)。

3.1 算法描述

輸入事務(wù)數(shù)據(jù)集D，最小支持度閾值M in，gram矩陣

輸出與D對(duì)應(yīng)的強(qiáng)關(guān)聯(lián)關(guān)系的概念格Hasse圖

步驟1掃描數(shù)據(jù)庫(kù)D一次，收集1頻繁項(xiàng)集的集合F和它們的支持度計(jì)數(shù)Sup，并對(duì)F按支持度計(jì)數(shù)進(jìn)行降序排序，if Sup≤M in，則刪除該項(xiàng)列表DEL得到頻繁列表L。

步驟2用形式背景來(lái)和刪除的列表DEL進(jìn)行匹配，當(dāng)匹配成功時(shí)形式背景對(duì)于該屬性進(jìn)行刪除操作。得到新的形式背景H。

步驟3對(duì)L進(jìn)行屬性的并集操作得到C，并計(jì)算其屬性之間的互信息值，為了快捷地進(jìn)行計(jì)算，其互信息值可由gram矩陣給出，當(dāng)互信息值M I≤0的時(shí)候或者其支持度Sup＜M in時(shí)，可以對(duì)其內(nèi)涵進(jìn)行約簡(jiǎn)，且此內(nèi)涵的父節(jié)點(diǎn)都可以進(jìn)行刪除操作。

步驟4根據(jù)概念格的分層得到所有的C，直到?jīng)]有互信息的值小于等于0為止。

步驟5根據(jù)所得到各層的屬性集并根據(jù)偏序關(guān)系，生成不帶有1項(xiàng)集概念格的Hasse圖，并進(jìn)行連邊。

3.2 實(shí)例驗(yàn)證

為驗(yàn)證本文算法的有效性，以表1的形式背景分析，設(shè)其最小支持度M in的數(shù)值為2，可由表1知FPTREE[16]1項(xiàng)集列表如表2及FP-TREE[17]的頻繁1項(xiàng)集如表3所示。

表2 1項(xiàng)集列表

表3 頻繁1項(xiàng)集列

所以由刪除的列表的概念格屬性知形式背景可以轉(zhuǎn)化為表4。

表4 形式背景

則由表4得到的單元概念根據(jù)秩的大小進(jìn)行排序得：C1=(E，5)，C2=(A，3)，C3=(C，3)，C4=(D，3)，C5=(B，2)，C6=(F，2)，C7=(H，2)。再根據(jù)步驟3建立Gram概率矩陣如表5。

表5 gram矩陣

表5表達(dá)的含義是該內(nèi)涵出現(xiàn)的概率，通過(guò)建立gram矩陣，可以滿足快捷的算法計(jì)算。然后通過(guò)約簡(jiǎn)之后進(jìn)行內(nèi)涵并集操作直至結(jié)束，根據(jù)分層的層次屬性知生成以互信息為度量的頻繁概念格的Hasse圖如圖1所示。

4 強(qiáng)關(guān)聯(lián)規(guī)則提取

圖1 以互信息為度量的Hasse圖

本文根據(jù)互信息M I來(lái)找到最強(qiáng)的關(guān)聯(lián)關(guān)系以做更準(zhǔn)確的決策，為了更加詳細(xì)準(zhǔn)確地進(jìn)行強(qiáng)關(guān)聯(lián)規(guī)則提取，列出全部的所求得的互信息值如下：M I(A，B)＜0，M I(A，C)＞0，M I(A，D)＜0，M I(A，E)=0，M I(A，F(xiàn))＜0，M I(A，H)＜0，M I(B，C)＜0，M I(B，D)＜0，M I(B，E)=0，M I(B，F(xiàn))＞0，M I(B，H)＞0，M I(C，D)＜0，M I(C，E)=0，M I(C，F(xiàn))＜0，M I(C，H)＞0，M I(D，E)=0，M I(D，F(xiàn))＜0，M I(D，H)=0，M I(E，F(xiàn))=0，M I(E，H)=0，M I(F，H)＞0，M I(AC，H)＞0，M I(AH，C)＞0，M I(CH，A)＞0。根據(jù)互信息性質(zhì)可以直接以葉子節(jié)點(diǎn)本文即(ACH，2)作為強(qiáng)關(guān)聯(lián)規(guī)則進(jìn)行規(guī)則提取，即有A?C，C?H，A?H，AC?H，AH?C，CH?A由此可根據(jù)一個(gè)節(jié)點(diǎn)推導(dǎo)出所有的規(guī)則。

為了能更加詳細(xì)地體現(xiàn)本文規(guī)則提取的準(zhǔn)確性，及進(jìn)行更直觀詳細(xì)細(xì)致的比較，在圖2給出利用傳統(tǒng)方法生成的Hasse圖。

圖2 傳統(tǒng)hasse圖

可以利用文獻(xiàn)[7-8]的規(guī)則提取發(fā)現(xiàn)所得到的規(guī)則與本文相同，但本文的方法更加簡(jiǎn)便，而且更加可視化，只需觀察葉子節(jié)點(diǎn)即可。

由于互信息表明的是相互之間的關(guān)聯(lián)程度的強(qiáng)弱，所以所得到的M I能體現(xiàn)出它們屬性之間規(guī)則的相互作用力度。以AC為例。由于M I(A，C)＞＞0。表明AC之間的關(guān)聯(lián)程度很強(qiáng)。所以可以得到規(guī)則A?C。又以(A，E)為例，由于M I(A，E)=0所以A和E同時(shí)發(fā)生是屬于偶然事件。根據(jù)互信息的公式可以精確地計(jì)算出相互屬性之間的關(guān)聯(lián)程度，相比與傳統(tǒng)的利用置信度得到的關(guān)聯(lián)規(guī)則，互信息計(jì)算出的值更加精確，可以非常準(zhǔn)確地得到關(guān)聯(lián)程度最強(qiáng)的組合。并在分類中可以以最強(qiáng)的關(guān)聯(lián)規(guī)則作為類別標(biāo)簽的分類器和進(jìn)行特征提取。

圖3 生成格節(jié)點(diǎn)數(shù)

圖4 規(guī)則提取所需節(jié)點(diǎn)數(shù)

另外可以從上述的互信息值和Hasse圖發(fā)現(xiàn)內(nèi)涵E是必然事件（概率為1），但是其所有的父節(jié)點(diǎn)的互信息值都是0，由此根據(jù)信息熵的定義可以知道關(guān)于內(nèi)涵E的信息m=-p lb p=-1×0=0。也就是說(shuō)E的信息量為0，也表明和其他的內(nèi)涵的關(guān)聯(lián)關(guān)系是屬于偶然事件。類似于在自然語(yǔ)言處理中，頻繁出現(xiàn)的英文單詞“the”，“and”或中文詞中的“的”，其本身是不攜帶任何含義的。所以在只進(jìn)行關(guān)聯(lián)規(guī)則提取的過(guò)程中是可以直接忽略的，但是因?yàn)槭潜厝皇录?，也?yīng)該非常重視。

5 算法實(shí)現(xiàn)與比較

為進(jìn)一步驗(yàn)證該算法的正確性和有效性，使用UC Irvine Machine Learning Repository的mushroom數(shù)據(jù)集做實(shí)驗(yàn)，其下載地址為：https：//archive.ics.uci.edu/m l/ datasets/M ushroom，由于原始數(shù)據(jù)有缺失，本文將其22個(gè)特征和所屬類別用阿拉伯?dāng)?shù)字取代，再根據(jù)其每一列的特征的平均值所靠近的屬性來(lái)代替缺失值。在M int15系統(tǒng)下用java運(yùn)行進(jìn)行對(duì)比，得到的結(jié)果如表6。

表6 對(duì)比數(shù)據(jù)

其效果對(duì)比圖如圖3、圖4所示。由于所建立的Hasse圖的方法不一致，本文是以規(guī)則可視化為目的，所以生成的Hasse圖在數(shù)量級(jí)的結(jié)構(gòu)不一致。

6 總結(jié)

本文利用互信息的特性來(lái)進(jìn)行規(guī)則提取，可以快捷精確地得到所包含的規(guī)則且可視化。由于本文主要是針對(duì)強(qiáng)關(guān)聯(lián)規(guī)則進(jìn)行分析，故互信息的優(yōu)勢(shì)得到極大體現(xiàn)。所以當(dāng)以互信息為度量生成的Hasse圖可以利用葉子節(jié)點(diǎn)進(jìn)行規(guī)則可視。

[1]胡可云，陸玉昌，石純一.基于概念格的分類和關(guān)聯(lián)規(guī)則的集成挖掘方法[J].軟件學(xué)報(bào)，2000，11（11）：1478-1484.

[2]Nourine L，Raynaud O.A fast algorithm for building lattices[J].Information Processing Letters，1999，7（1）：199-204.

[3]陳慶燕.Bordat概念格構(gòu)造算法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（35）：33-35.

[4]謝志朋，劉宗田.概念格的快速漸進(jìn)式構(gòu)造算法[J].計(jì)算機(jī)學(xué)報(bào)，2002，25（2）：490-496.

[5]謝福鼎，王照飛.基于概念格的關(guān)聯(lián)規(guī)則挖掘[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（33）：170-172.

[6]劉霜霜，饒?zhí)熨F，孫建華.基于改進(jìn)概念格的無(wú)冗余關(guān)聯(lián)規(guī)則提取[J].計(jì)算機(jī)工程，2010，36（10）：52-55.

[7]智東杰，智慧來(lái)，劉宗田.概念格的內(nèi)涵縮減研究[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（1）：42-44.

[8]謝志鵬，劉宗田.概念格與關(guān)聯(lián)規(guī)則發(fā)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展，2000，37（12）：1414-1421.

[9]楊霽琳.一種基于概念格的規(guī)則提取方法及其應(yīng)用[J].計(jì)算機(jī)科學(xué)，2012，39（11A）：204-206.

[10]陳湘，吳躍.基于概念格挖掘GIS中的關(guān)聯(lián)規(guī)則[J].計(jì)算機(jī)應(yīng)用，2011，31（3）：686-689.

[11]王慧，王京.FP-Tree上頻繁概念格的無(wú)冗余關(guān)聯(lián)規(guī)則提取[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（15）：12-15.

[12]余遠(yuǎn)，錢旭，鐘鋒，等.基于最大概念的概念格增量構(gòu)造算法[J].計(jì)算機(jī)工程，2009，35（21）：62-64.

[13]宋余慶，朱玉全，孫志揮，等.基于FP-Tree的最大頻繁項(xiàng)目集挖掘及更新算法[J].軟件學(xué)報(bào)，2003，14（9）：1586-1592.

[14]姜晗，賈泂，徐峰.基于頻繁項(xiàng)集挖掘最大頻繁項(xiàng)集和頻繁閉項(xiàng)集[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（28）：146-148.

[15]劉樂(lè)樂(lè)，田衛(wèi)東.基于屬性互信息熵的量化關(guān)聯(lián)規(guī)則挖掘[J].計(jì)算機(jī)工程，2009，35（14）：38-40.

[16]楊云，羅艷霞.FP-Grown算法的改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2012，31（7）：1506-1509.

[17]馬麗生，姚光順，楊傳健.基于改進(jìn)FP-tree的最大頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)應(yīng)用，2012，32（2）：326-329.

XIE Linquan,ZHANG En

School of Science,Jiangxi University of Science and Technology,Ganzhou,Jiangxi 341000,China

The concept lattice is an effective tool for know ledge discovering and know ledge processing,which has been successfully applied in many fields.How ever,lattice constructions with reduction operation are mostly based on minimum support and degree of confidence.A t the same time,the degree of confidence is used to extract rules.This paper proposes the Hasse diagram with strong association which is constructed by the mutual information of information theory, and extracts rules by mutual information.

strong association rules;concept lattice;mutual information;rule extraction;data mining

XIE Linquan,ZHANG En.Ru les visualization based on Metric of mutual in form ation.Computer Engineering and Applications,2014,50（17）：146-149.

A

TP391

10.3778/j.issn.1002-8331.1311-0454

國(guó)家自然科學(xué)基金（No.61364015）。

謝霖銓（1962—），博士，教授，主要研究方向：序代數(shù)、數(shù)據(jù)挖掘、粗糙集理論及應(yīng)用；章恩（1990—），碩士，主要研究方向：概念格、機(jī)器學(xué)習(xí)。E-mail：lq_xie@163.com

2013-12-02

2014-04-02

1002-8331（2014）17-0146-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-04-21,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0454.htm l