一种基于规则的属性约简算法

An Attribute Reduction Algorithm Based on Rules

Reduction of attributes is one of important topics in the research on rough set theory. Wong S K M and Ziarko W have proved that finding the minimal attribute reduction of decision table is a NP-hard problem. Algorithm A (the improved algorithm to Jelonek) choices optimal candidate attribute by using approximation quality of single attribute,it improves efficiency of attribute reduction,but yet exists the main drawback that the single atribute having maximum approxiamtion quality is probably optimal candidate attribute. Therefore,in this paper, we introduce the concept of compatible decision rule,and propose an attribute reduction algorithm based on rules (ARABR). Algorithm ARABR provides a new method that measures the relevance between extending attribute and the set of present attributes, the method assures that the optimal attribute is extended, and obviously reduces the search space. Theory analysis shows that algorithm ARABR is of lower computational complexity than Jelonek's algorithm,and overcomes effectively the main drawback of algorithm A.

Reduction of attributes is one of important topics in the research on rough set theory. Wong S K M and Ziarko W have proved that finding the minimal attribute reduction of decision table is a NP-hard problem. Algorithm A (the improved algorithm to Jelonek) choices optimal candidate attribute by using approximation quality of single attribute, it improves efficiency of attribute reduction,but yet exists the main drawback that the single atribute having maximum approxiamtion quality is probably optimal candidate attribute. Thereforr, in this paper, we introduce the concept of compatible decision rule,and propose an attribute reduction algorithm based on rules (ARABR). Algorithm ARABR provides a new method that measures the relevance between extending attribute and the set of present attributes, the method assures that the optimal attribute is extended,and obviously reduces the search space. Theory analysis shows that algorithm ARABR is of lower computational complexity than Jelonek's algorithm,and overcomes effectively the main drawback of algorithm A.