摘  要  粗糙集理论的主要应用是属性约简和规则提取，但由于应用粗糙集理论提取出的规则未必都是最佳规则，因此，本文提出一种基于互信息的规则约简方法。对确定性规则进行优化，挖掘出最简规则集，最后通过实例分析验证了该方法可行性和有效性。    关键词  粗糙集；信息熵；互信息 

1  引言

    粗糙集理论^[1]是由波兰学者Z. Pawlak于1982年提出的，是一种新的处理模糊和不确定性知识的数学工具。其核心思想是在保持分类能力不变的前提下，通过对知识的化简，导出问题的决策或分类规则。信息论由Shannon于1948年提出，信息熵是信息论的核心内容，信息熵^[2]是事件不肯定性程度的度量，它能够从确切的数值量度出发去描述知识。由于应用粗糙集理论的上、下近似概念提取出的规则未必都是最佳规则，即规则中的属性值未必都是必要的，所以，可以通过应用信息熵知识给出决策表中约简属性的重要性度量，必然能删除不必要的属性及属性值，合并相同规则，得到最简规则集。    本文综合应用了粗糙集理论和信息熵理论的优点，首先，应用粗糙集方法，求出属性约简、提取出确定性规则和可能性规则，然后，从[3]定义的信息熵出发，对决策表中属性的重要性进行了有效地度量，即通过约简中的每个属性的互信息，有效地简化得到的规则知识。因此，本文有机结合了粗糙集与信息熵的优点，提出一种基于信息熵理论的规则约简方法。该方法可以挖掘出满足给定精确度的一组条件属性最少、规则数最少的最简决策规则集，使得挖掘出来的规则更简单、实用。

2  基本概念^[3，4]

    定义1  设K=(U，A，V，f)是一个信息系统，其中U是一个有限的非空集合，称为论域。 A=C∪D是属性的非空有限集合，C为条件属性，D为决策属性，C∩D=Φ，V_a是属性a∈A的值域，f：U×A→V是一个信息函数，它为每个对象赋予一个信息值。通常一个信息系统对应一个信息表，其中行对应论域中的对象，列对应论域中的属性。表内容就是对象的属性值。    定义2  设U为一个有限的非空论域，R为U上的等价关系。等价关系R 把集合U划分为多个互不相交的子集，每一个子集称为一个等价类，用[x]_R表示，[x]_R ={y∈U│xRy}，其中x∈U，x、y称为关于R 的等价关系，论域U上的所有等价类的集合用U/ R来表示。    定义3  对于任意的XU，X的R下近似集和R上近似集定义为：    R(X)=∪{Y∈U/R│YX }， (X)= ∪{Y∈U/R│Y∩X≠}    bnR(X)= (X)- R(X) 称为边界；集合的不确定性是由于边界域的存在，集合的边界域越大，精确性越低，粗糙度越大。    定义4  令R为一族等价关系，r∈R，如果 ind(R)=ind (R-{r})，则称r为R中不必要的；否则r为R中必要的^[2]。P中所有必要关系组成的集合称为P的核，记为core( P) 。核与约简有如下关系：    core ( P) = ∩ red ( P)，其中red ( P) 表示P 的所有约简。    定义5  信息熵：知识X 的信息熵定义为：

    定义6  条件熵：知识属性集合Y (U| IND (Y) ={Y₁，Y₂，…，Y_m}) 相对于知识(属性集合)     U/ind(X)={ X₁，X₂，…，X_n}的条件熵：H(Y | X) 定义为： 

    定义7  互信息：设T = < U，R，V，f > 是一个决策表系统，其中R = C∪D，C 是条件属性集合，D = {d}是决策属性集合，且A C，对于任意属性a∈C P A的重要性定义为：SGF(a，A，D) = H(D| A) - H(D| A∪{a}) 。若A =Φ，则：SGF(a，A，D)=SGF(a，D) = H(D) - H(D| {a})，称为属性a 和决策D的互信息，记为I (a，D)。

3  基于信息熵的规则约简

    在信息表中，由于应用粗糙集理论提取的规则未必都是最简规则，即规则中可能存在某个属性值是不必要的，因此规则约简。由于在决策表中可以通过添加某个属性所引起互信息的变化大小作为该属性重要性的度量，互信息SGF(a，A，D) 值越大，说明在已知A 的条件下，属性a 对于决策D 就越重要。因此，基于论域上的不可分辨关系和信息熵的知识可以对确定性规则约简。    其方法如下：    Step1：利用互信息公式计算约简中各属性的互信息，将结果值按降序排列。    Step2：对约简中每个属性(按互信息降序顺序)依次逐行考察确定性规则集中每条规则，若抽取到的规则与其后的规则产生冲突，则将发生冲突规则的该属性值标记为1，若产生重复记录，则将对应规则中的该属性值标记为3，既不产生冲突也不产生重复的规则的属性值标记为2。    Step3：对规则集中的规则进行逐行考察，首先判断是否能由属性值标记为1的属性做出正确决策，若不能将属性值标记为2的属性添加进来，若仍不能得出正确决策，则按互信息的大小依次把属性值标记为3的属性添加进来，直到做出正确决策为止，并将做出正确决策的对应的当前规则保存到新的规则集中。    Step4：将规则集中能利用step3得出的当前规则做出正确判断的规则删除。    Step5：如此循环直到规则集中规则为空为止，新规则集就是进行规则约简后的最优规则集。

4  实例分析

    设论域U={1，2，3，4，5，6，7，8 }，条件属性集合C={ Solar energy，Volcanic activity，Residual CO2}，决策属性D为Temperature，决策信息表如表1所示。决策信息表1^[5]

Fact count	Solar energy	Volcanic activity	Residual CO2	Temperature	Days
1	Medium	High	Low	High	20
2	High	High	High	High	30
3	Medium	Low	High	High	90
4	Low	Low	Low	Low	120
5	High	High	Medium	High	70
6	Medium	Low	High	Low	34
7	High	Low	High	High	10
8	Low	high	Low	Low	20

    1)C的D约简    得到C₀={solar，volcanic}是C的D约简。    2)提取规则：    (1)通过计算决策属性等价类相对于 U/ C₀ 的下近似，得到不确定性规则。    ① (Solar Energy，medium)  (Volcanic Activity，high) → (Temperature，high)  /1；    ②　(Solar Energy，high) (Volcanic Activity，high) → (Temperature，high)   /2，5；    ③　(Solar Energy，high) (Volcanic Activity，low) →(Temperature，high)  /7；    ④　(Solar Energy，low)  (Volcanic Activity，low) →(Temperature，low)  /4；    ⑤　(Solar Energy，low)  (Volcanic Activity，high) →(Temperature，low)  /8。    (2)通过计算决策属性等价类相对于约简U/C₀的边界，得到不确定性规则。    ①　(Solar Energy，medium)  (Volcanic Activity，low) →(Temperature，high)；/3    ②　(Solar Energy，medium)  (Volcanic Activity，low) →(Temperature，low)；/6。    3)计算表1中决策属性Temperature的信息熵    约简属性solar，volcanic的互信息：    H(D)=-1* (130/270 * log₂(130/270)+140/270* log₂(140/270))  =0.999属性Solar Energy的条件熵：    H(D|C1)=-1 * (110/270) * ( 110/110)* log₂(110/110) -1 * (20/270)* 20/20* log₂(20/20) -1*(140/270)*(140/140) * log₂(140/140)  =0属性Volcanic Activity的条件熵：    H(D|C2)=-1 * 140/270 * (120/140 * log₂(120/140)+ 20/140 * log₂(20/140))-1 * 130/270 * (120/130 log₂(120/130)+ 10/130 * log₂(10/130) )=0.345两属性的互信息为：    Gain(Solar Energy )=0.999Gain(Volcanic Activity)=0.654    因为solar 互信息大，相对决策重要，Volcanic小，所以先考虑规则中删除Volcanic属性值，当删除Volcanic，若Solar Energy 为 high时，规则集合中没有产生冲突规则；若Solar Energy 为low也没有产生冲突规则，所以对应的规则简化为：    (Solar Energy，high) →(Temperature，high)；    (Solar Energy，low) →(Temperature，low)；    当删除Volcanic，若Solar Energy为medium，决策属性d值是high和low，产生冲突规则，所以当Solar Energy，medium，Volcanic Activity值不能删除。    由此最终得到的简化规则集：    ①　(Solar Energy，medium)  (Volcanic Activity，high) →(Temperature，high)     ②　(Solar Energy，high) →(Temperature，high)     ③　(Solar Energy，low) →(Temperature，low)    ④　(Solar Energy，medium)  (Volcanic Activity，low) →(Temperature，high)    ⑤　(Solar Energy，medium)  (Volcanic Activity，low) →(Temperature，low)              

5  结论

    本文介绍了粗糙集与信息熵之间的关系，给出了一种基于粗糙集理论和信息论相结合的数据挖掘方法，把信息论应用于决策信息系统简化规则集中，实验表明该算法能够获得令人满意的最简规则集。

[1] Pawlak Z. Rough sets(J). International Journal of Computer and Information Science，1982，11 (5)：341～356 [2] SHANNON CE. The mathematical theory of communication [J ]. The Bell System Technical Journal，1948，27 (3 /4)：373 - 423.[3]　L IANG JY，CH IN KS，DANG CY，et al. A new method for measuring uncertainty and fuzziness in rough set theory [ J ]. International Journal of General Systems，2002，31 (4)：331 - 342.[4]　张文修，吴伟志. 粗糙集理论介绍和研究综述[J ] . 模糊系统与数学，2000，15 (4)：1-12. [5] Pawlak Z. Rough sets and intelligent data analysis (J). International Journal of Computer and Information Science，2002，147：1-12