近年来，数据挖掘(Data Mining)引起了信息产业界的极大关注，其主要原因是数据海洋的日益增大，我们需要新技术将海量数据转化为有用的信息和知识。分类是数据挖掘的主要任务之一，分类的目的是要建立区分数据对象的模型，以便能够使用模型预测类标记未知的数据对象。主要的分类方法有决策树、贝叶斯分类、支持向量机、神经网络、遗传算法、粗糙集等等。粗糙集(Rough Set)理论是波兰数学家Z.Pawlak于1982年提出的，是一种新的处理含糊性(Vagueness)和不确定性(Uncertainty)问题的数学工具，粗糙集理论的主要优势在于它不需要关于数据的任何预备的或额外的信息。高效的约简算法是粗糙集理论应用于数据挖掘与知识发现领域的基础，但是，已经证明求解所有约简和求解最小约简都是NP-hard问题，因此，寻求快速的约简算法仍是粗糙集理论的主要研究课题之一。本文在对数据挖掘和粗糙集约简算法进行综述之后，提出一组基于属性区分能力指数的信息系统约简算法和一组决策表相对约简算法。本文提出的算法都涉及系统的划分，系统划分的目的是为了用属性a来代替相应区域的区分元素(见图4.1)，从而减小算法搜索的空间。为了能够用属性a来代替相应区域的区分元素，要求划分时要将系统划分成属性对应的若干等价类。根据第四章所解释的算法思想，自然希望选择取值分布较均匀的、具有较多属性值的属性。本文针对信息系统和决策表分别提出区分能力指数的概念，并利用具有最大区分能力指数的属性对系统进行划分。当然，信息增益度量也倾向于取值较多且取值分布均匀的属性，但是信息增益不能很好地反映算法思想。正如定理4.2和定理5.2所指出的，取值分布较均匀的属性具有较大的区分能力；而定理4.3和定理5.3指出，当属性b是属性a的细化时，属性b的区分能力不小于a的区分能力。因此，区分能力指数是较好的系统划分启发信息。第四章首先定义了属性区分能力指数I(a)的概念，并给出I(a)的若干性质。然后提出了基于区分能力指数的信息系统划分与约简的基本算法，算法的主要思想是采用分而治之的策略，利用具有最大属性区分能力指数的属性将信息系统划分为子表，求取子表约简后，利用子表约简求解原系统的约简。本文指出该算法所得结果是信息系统的约简。通过对基本算法的分析，提出了考虑公共项的约简算法、考虑公共项和频繁项的约简算法和带有近似精度阈值的约简算法，并对相应算法的完备性进行了分析。为了进一步简化布尔函数化简的过程，当各个子表区分函数的析取范式具有公共项时，考虑公共项的约简算法只给出一个约简。这虽然会丢掉若干约简，但在分类精度容许<WP=59>的情况下，这种策略会在得到各个子表约简后，立即给出原信息系统的一个约简。类似地，当各个子表区分函数的析取范式具有频繁项时，考虑频繁项的约简算法和带有近似精度阈值的约简算法，也只给出一个约简。当然，带有近似精度阈值的约简算法是对以上算法的完善。第四章还对各个子表布尔函数的不同形式进行了较全面的讨论。第五章针对决策表定义了条件属性的区分能力指数DI(a)的概念，并给出DI(a)的若干性质。为论述方便，本文还提出了拟等价类的概念。然后提出基于区分能力指数的决策表划分与相对约简的基本算法，算法的主要思想与第四章算法思想类似，但需改动三点：(1) 划分决策表为各个拟等价类对应的子表；(2) 区分能力指数定义改为DI(a)；(3) 区分函数fi按照决策表区分函数方式构建。基本算法所得结果是决策表的相对约简。最后，提出了带有近似精度阈值的相对约简算法，并对相应算法的完备性进行了分析。本章还对为何选取区分能力指数作为系统划分的启发信息，进行了讨论。第五章的最后一节给出了若干实验结果，实验结果表明，本文提出的算法有较高的效率。值得进一步研究的问题如下：本文给出的算法不具有完备性，因此，进一步的工作应考虑从理论上讨论算法所得结果的“满意程度”。另外，算法的时间复杂度主要是由于区分函数化简引起的，故区分函数化简的高效算法也是值得进一步研究的问题。