一种新的启发式知识约简算法

Novel Heuristic Algorithm for Knowledge Reduction

知识约简是Rough Set理论研究的重要内容.通过分辨矩阵定义了简化分辨函数,然后针对此分辨函数构造了两种操作以及定义了覆盖、最小覆盖等概念,并基于这种操作、概念和相关原理将决策系统的约简问题转化为寻求简化分辨函数最小覆盖的问题;面向最小属性约简定义了基于简化分辨函数的属性重要度,并以此为启发信息,结合已导出的有关最小覆盖的定理构造了一种新的知识约简算法——算法SDFAR.文中,在理论上详细证明了提出算法的完备性并给出了算法的复杂性分析,说明其高效性,对寻找最小约简是相对有效的,这在最后的实验中也得到了验证.

Knowledge reduction is one of the most important problems in rough set theory. In this paper, simple discernibility function is defined by discernibility matrice, and then two kinds of operations and relevant concepts such as minimal coverage are defined, with which the problem of finding reduction for DS is turned into another problem of finding minimal coverage of simple discernibility function; significance of attributes in decision table is defined for minimal reduction based on simple discernibility function, which is used as heuristic information to design a novel knowledge reduction algorithm with relevant theory of minimal coverage. The presented algorithm, named as SDFAR, is proved to be complete. This paper also gives the algorithm＇s complexity analysis and experimental analysis, proving its completeness. The proposed algorithm is relatively effective for finding minimal reduct.