基于差别函数的决策表属性约简算法研究

李飏

摘要：属性约简是粗糙集的核心内容，该文分析了基于差别函数的决策表属性约简存在的优缺点，在他人提出的改进的基于差别函数的决策表属性约简算法的基础上，进一步对约简结果处理，通过对其平均信息熵的大小衡量，选择具有巨大信息量的约简作为最后的单一约简。

关键词：属性约简；粗糙集；差别函数；平均信息熵

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2014）22-5348-02

1 概述

粗糙集理论是一种关于数据分析和推理的理论，它不需要任何预备的或额外的有关数据信息，能够有效地分析和处理不完备、不一致、不精确的数据。属性约简是指在保持知识分类能力不变的条件下，删除其中不必要的、不重要的或不相关的属性。

2 基于差别函数的决策表属性约简算法

2.1属性约简的概念

对于决策表而言，属性约简的定义为：设子集[R?C]，若[R]为[C]的[D]约简，当且仅当[R]满足[POSR（D）=POSC（D）]而且不存在[R′?R]使得[POSR′（D）=POSC（D）]，记[R∈REDC（D）]，其中[REDC（D）]表示[C]的全体[D]约简组成的集合。由此可见，决策表的属性约简是保证正域不变的最小属性集合。[C]的[D]核[COREC（D）=?REDC（D）]，或[C]的[D]核为[C]中全体必要属性的集合。

2.2 基于差别函数的属性约简

2.3 优缺点分析

基于差别函数的决策表属性约简算法可以得到该决策表所有可能的属性约简结果，实际上是将对属性组合情况的搜索演变为逻辑公式的化简，从而简化问题。但是，由于求差别矩阵需要将每个对象与其他的所有对象比较，当决策表的论域对象很多时，该算法的逻辑转换运算代价很大，计算过程麻烦，复杂度逐渐增大，求取约简所需的时间也越来越多。

此外，该方法一般只适用于完备相容的决策表，即在决策表不相容的情况下可能导致错误的计算结果。

2.4属性约简算法的改进

利用任何一个相对约简一定包含相对核这一特性来简化和降低计算代价。于是提出了改进的基于差别函数的决策表属性约简算法。首先将相对[D]核中的条件属性从差别矩阵中取出，同时将差别矩阵中包含相对[D]核属性的元素置为0（[?]和[-]同样置为0），从而得到一个新矩阵，称为决策表的分明矩阵。对分明矩阵计算得到析取范式逻辑表达式，最有将所有核属性重新加到析取范式中的每个合取项，得到决策表的所有属性约简。

3 基于差别函数的属性约简进一步改进

不管是基于差别函数的决策表属性约简算法还是改进的基于差别函数的决策表属性约简算法，最后的结果都是求得所有约简。这对信息系统的理论分析和实际计算都是有用处的，但是在实际应用时只需要一种约简，而且该约简具有的信息量要求最大。

具体思路为：基于分明矩阵得到析取范式，然后计算各合取项的平均信息熵，选择平均信息熵最小的与核属性组成最终的约简结果。

4 结论

属性约简是粗糙集的重要内容，属性约简也是各方面研究的基础环节，具有重要意义，该文首先介绍了基于差别函数的属性约简以及他人的改进算法，在此基础上，提出了进一步对约简结果处理的方法。

参考文献：

[1] Pawlak Z. Rough sets： Theoretical Aspects of Reasoning about Data， Kluwer Academic Publishers， Boston， 1991.

[2] 苗夺谦， 李道国. 粗糙集理论、算法与应用[J]. 北京：清华大学出版社， 2008.

[3] 苗夺谦， 胡桂荣. 知识约简的一种启发式算法[J]. 计算机研究与发展， 1999，36（6）：681-684.