一种基于互信息的规则约简方法(1)
2014-12-10 01:46
导读：计算机应用论文论文，一种基于互信息的规则约简方法(1)在线阅读，教你怎么写，格式什么样，科教论文网提供各种参考范例：摘 要 粗糙集理论的主要应用是属性约简和规则提取，但由于应用粗糙集理论提
摘 要 粗糙集理论的主要应用是属性约简和规则提取，但由于应用粗糙集理论提取出的规则未必都是最佳规则，因此，本文提出一种基于互信息的规则约简方法。对确定性规则进行优化，挖掘出最简规则集，最后通过实例分析验证了该方法可行性和有效性。 关键词 粗糙集；信息熵；互信息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=Φ，Va是属性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 对于任意的X
U，X的R下近似集和R上近似集定义为：
R(X)=∪{Y∈U/R│Y
X }，
(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) ={
Y1，
Y2，…，
Ym}) 相对于知识(属性集合) U/ind(X)={
X1，
X2，…，
Xn}的条件熵：H(Y | X) 定义为：
定义7 互信息：设T =
