以互信息為度量的一種規則可視化

謝霖銓，章恩

江西理工大學理學院，江西贛州 341000

以互信息為度量的一種規則可視化

謝霖銓，章恩

江西理工大學理學院，江西贛州 341000

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

強關聯規則；概念格；互信息；規則提取；數據挖據

1 概述

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

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

2 相關概念

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

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

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

根據定義可知：

性質1[13-14]最大頻繁項的父節點一定是頻繁項集。

性質2[13、14]最大頻繁項的子節點一定是非頻繁項集。

推論1當某項集節點是非頻繁項集時，則包含該節點內涵的所有項集都是非頻繁項集。

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

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

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

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

定義8設(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)的兩個直接父節點的交。

定義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個信號關聯程度的尺度。后來引申為2個隨機變量間的關聯程度進行統計描述，可表示成這2個隨機變量的概率的函數。假設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獨立出現的概率。P(x，y)是x和y同時出現的概率，當M I(x，y)＞＞0時，表明x和y的關聯程度強。M I(x，y)=0時，表明x和y的關聯程度弱，它們的同時出現僅屬于偶然。當M I(x，y)＜＜0時，表明x，y互補分布，不存在關聯關系。

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

表1 形式背景

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

3 算法描述及實例驗證

本文基于互信息提出強關聯規則的建格約簡，以互信息的性質可以知道經過約簡后的Hasse圖的內涵是具有強關聯關系，在規則提取中也表現出很大的優勢。

3.1 算法描述

輸入事務數據集D，最小支持度閾值M in，gram矩陣

輸出與D對應的強關聯關系的概念格Hasse圖

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

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

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

步驟4根據概念格的分層得到所有的C，直到沒有互信息的值小于等于0為止。

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

3.2 實例驗證

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

表2 1項集列表

表3 頻繁1項集列

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

表4 形式背景

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

表5 gram矩陣

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

4 強關聯規則提取

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

本文根據互信息M I來找到最強的關聯關系以做更準確的決策，為了更加詳細準確地進行強關聯規則提取，列出全部的所求得的互信息值如下：M I(A，B)＜0，M I(A，C)＞0，M I(A，D)＜0，M I(A，E)=0，M I(A，F)＜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)＞0，M I(B，H)＞0，M I(C，D)＜0，M I(C，E)=0，M I(C，F)＜0，M I(C，H)＞0，M I(D，E)=0，M I(D，F)＜0，M I(D，H)=0，M I(E，F)=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。根據互信息性質可以直接以葉子節點本文即(ACH，2)作為強關聯規則進行規則提取，即有A?C，C?H，A?H，AC?H，AH?C，CH?A由此可根據一個節點推導出所有的規則。

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

圖2 傳統hasse圖

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

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

圖3 生成格節點數

圖4 規則提取所需節點數

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

5 算法實現與比較

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

表6 對比數據

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

6 總結

本文利用互信息的特性來進行規則提取，可以快捷精確地得到所包含的規則且可視化。由于本文主要是針對強關聯規則進行分析，故互信息的優勢得到極大體現。所以當以互信息為度量生成的Hasse圖可以利用葉子節點進行規則可視。

[1]胡可云，陸玉昌，石純一.基于概念格的分類和關聯規則的集成挖掘方法[J].軟件學報，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概念格構造算法的改進[J].計算機工程與應用，2010，46（35）：33-35.

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

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

[6]劉霜霜，饒天貴，孫建華.基于改進概念格的無冗余關聯規則提取[J].計算機工程，2010，36（10）：52-55.

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

[8]謝志鵬，劉宗田.概念格與關聯規則發現[J].計算機研究與發展，2000，37（12）：1414-1421.

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

[10]陳湘，吳躍.基于概念格挖掘GIS中的關聯規則[J].計算機應用，2011，31（3）：686-689.

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

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

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

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

[15]劉樂樂，田衛東.基于屬性互信息熵的量化關聯規則挖掘[J].計算機工程，2009，35（14）：38-40.

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

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

國家自然科學基金（No.61364015）。

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

2013-12-02

2014-04-02

1002-8331（2014）17-0146-04

CNKI網絡優先出版：2014-04-21,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0454.htm l