基于归纳的值约简算法的研究与实现

在粗糙集理论的基础上，本文研究了归纳值约简过程。归纳值约简算法采用求解知识表达系统决策表的

属性约简和值约简是粗糙集理论研究中的两个重要内容，属性约简是在保持与原有的数据库决策能力相同的情况下，选择问题最小属性子集，剔除数据中的没有利用价值成分的过程。在现实世界的问题中，由于噪音、误导和不相关属性的存在，使得属性约仅是在一定程度上去除了决策表中的冗余属性， 但并没有完全去掉决策表中的不必要的信息。为此，还需要对决策表进行更深层次的处理，即对决策表进行值约简。值约简是去掉多余的属性值，用最少的条件属性值来区分每一个决策类，在不改变决策能力的基础上得到更加简化的规则集。值约简的研究方法有很多，比如一般的值约简算法、启发式值约简算法、基于决策矩阵的值约简算法、归纳值约简算法和Skowron 算法等。本文主要研究基于归纳的值约简算法，并对算法的执行效果进行了实验验证，以及与启发式值约简算法进行了比较。

2. 粗糙集基本概念 粗糙集理论是一种对不确定性数据进行分析的理论，它的主要思想就是在保持信息系统分类能力不变的条件下，通过知识约简剔除数据中冗余的信息，从而得到问题的正确决策或数据分类。

2.1. 信息表和决策表 (), , , SU V A f=为一个信息表[1]，其中U 为论域，是一非空有限对象集，即{}12, , , nUx xx=；{}12, , , nAa aa=是非空有限的属性集合；Va 是属性a 的值域，即VVa= ∪， :a Uf UAV∈×→成为信息函数， 使得对每一aA∈， xU∈， 有(), f x aVa∈。

在粗糙集理论中， 信息表可简化(), SU A=或(), , SU A V=。

在信息表S 中， 如果属性集A 由条件属性集C 和决策属性集D 组成， 并且满足CDA=∪， CD = ∅∩， 则称S 为决策表，记为(), SU CD=∪。在决策表S 中，若存在两行信息，其全部条件属性值相同，而决策属性值不相同，则称S 为不相容决策表，否则为相容决策表。这里仅考虑相容决策表。

2.2. 知识和不可分辨关系 定义1：(知识和知识库)给定论域U 和其对应的一个等价关系R， 在等价关系R 下对论域U 的划分， 称为知识，记为U/R。U 上的一簇划分称为关于U 的一个知识库。

设R 是U 上的一个等价关系，U/R 表示R 的所有等价类(或者U 上的分类)构成的集合，[x]R 表示包含元素xU∈的R 等价类。一个知识库就是一个关系系统(), KU R=，其中R 是论域U 上的一簇等价关系。

若PR⊆， 且P ≠∅， 则∩P(P 中所有等价关系的交集)也是一个等价关系， 称为P 上的不可分辨关系，