謝霖銓，章恩

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

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

謝霖銓，章恩

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

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

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

1 概述

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

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

2 相關(guān)概念

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

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

定義3[12]對于頻繁項集(O，A)，并且對于子節(jié)點(O1，A1)?？梢缘弥?O，A)的支持度Sup≥(O1，A1)的支持度Sup。但增加任何一項其支持度Sup＜M in，則稱(O，A)為最大頻繁項集。

根據(jù)定義可知：

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

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

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

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

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

定義6[7]假設(shè)有下面的H1=(O1，A1)，H2=(O2，A2)∈L，L代表格，如果A1?A2或O1?O2，則稱H1是H2的子概念（節(jié)點），H2是H1的父節(jié)點。可形式化表示為H1≤H2。

定義7對于概念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)的兩個直接父節(jié)點的交。

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

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

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

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

表1 形式背景

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

3 算法描述及實例驗證

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

3.1 算法描述

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

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

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

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

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

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

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

3.2 實例驗證

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

表2 1項集列表

表3 頻繁1項集列

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

表4 形式背景

則由表4得到的單元概念根據(jù)秩的大小進行排序得：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表達的含義是該內(nèi)涵出現(xiàn)的概率，通過建立gram矩陣，可以滿足快捷的算法計算。然后通過約簡之后進行內(nèi)涵并集操作直至結(jié)束，根據(jù)分層的層次屬性知生成以互信息為度量的頻繁概念格的Hasse圖如圖1所示。

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

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

本文根據(jù)互信息M I來找到最強的關(guān)聯(lián)關(guān)系以做更準確的決策，為了更加詳細準確地進行強關(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é)點本文即(ACH，2)作為強關(guān)聯(lián)規(guī)則進行規(guī)則提取，即有A?C，C?H，A?H，AC?H，AH?C，CH?A由此可根據(jù)一個節(jié)點推導(dǎo)出所有的規(guī)則。

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

圖2 傳統(tǒng)hasse圖

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

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

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

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

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

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

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

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

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

6 總結(jié)

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

[1]胡可云，陸玉昌，石純一.基于概念格的分類和關(guān)聯(lián)規(guī)則的集成挖掘方法[J].軟件學(xué)報，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].計算機工程與應(yīng)用，2010，46（35）：33-35.

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

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

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

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

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

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

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

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

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

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

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

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

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

[17]馬麗生，姚光順，楊傳健.基于改進FP-tree的最大頻繁項集挖掘算法[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

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

謝霖銓（1962—），博士，教授，主要研究方向：序代數(shù)、數(shù)據(jù)挖掘、粗糙集理論及應(yīng)用；章恩（1990—），碩士，主要研究方向：概念格、機器學(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