基于粗糙集理论的属性约简算法研究

Research for attribute reduction based on rough set theory

属性约简是粗糙集理论研究中的核心内容之一,现已证明寻找最小约简是NP-hard问题。在完备信息系统中,通过引入区分度的概念,以相对区分度为启发式信息,提出一种基于区分度的属性约简启发式算法,并对该算法的时间复杂性进行了分析。

Attribute reduction is one of the key topics of rough set theory. Search for minimum reduction has been proved to be a NP-hard problem. The concept of discernibility degree is introduced in complete information systems. With the discernibility degree as heuristic information, a heuristic algorithm based on discernibility degree for reduction of attributes is presented, and the time complexity of this algorithm is analyzed.