薛胜军 郭 强

（武汉理工大学计算机科学与技术学院1） 武汉 430063）

（南京信息工程大学计算机与软件学院2） 南京 210044）

粗糙集理论是一种新型的处理模糊性和不确定性问题的数学工具，经过将近30 a的发展，该理论已广泛应用于故障检测、数据挖掘、模式识别、知识发现等领域．属性约简是粗糙集理论中的一个核心内容，目前有很多研究都是针对属性约简方面的．求解属性约简的算法可以划分为如下几类：（1）基于正区域的求解算法，有时在求解的过程中会结合属性的重要性、互信息等；（2）基于差别矩阵的求解算法；（3）基于智能计算的求解方法，如基于遗传算法和神经网络．随着问题规模的增大，基于差别矩阵求解算法的缺陷会愈加凸显．有时在利用正区域或差别矩阵求解时，常结合属性的重要性［1］、互信息［2］、属性出现的频率［3］等，使得算法更加高效．本文通过实例指出文献［4］中的不足并加以改进，结合了基于等价类压缩的思想和基于核增量求解的思想提出了一种新的求解最小约简的方法，最后通过实例验证算法的有效性．

1 粗糙集的相关概念

设S＝（U，R，V，F）为一信息系统．式中：U＝（X1，X2，…，Xn）为论域（universe）；R 为属性集合；V为属性值集合；F为U×R→V 的映射，它为U中各对象的属性指定惟一值．若R＝C∪D，C∩D＝∅，C称为条件属性集；D称为决策属性集，则该信息系统称为决策表．

定义1 设S＝（U，R，V，F），对于每个属性子集P⊆R，定义属性P的不可区分关系IND（P）＝｛（x，y）∈U2｜∀r∈P，f（x，r）＝f（y，r）｝，如果（x，y）∈IND（P），则称x与y 是P 不可区分的．不可区分关系也可称为等价关系．IND（P）是U 的一个划分，记为U／P，U／P中的……