Abstract: Attribute reduction is one of the key problems in the research field of rough set theory,which can eliminate unnecessary attributes of the information table.However,the number of possible subsets is always very large when the number of attributes N is large,because there are 2N subsets for N attributes.Hence exhaustively examining all subsets of attributes for finding the minimal reduction is a NP-hard problem.Many heuristic algorithms are proposed to solve this difficulty.But most of them have not considered two problems at the same time which are the completeness and the data noise.An efficient algorithm named REDA that can process data noises was proposed in this paper.Firstly,the feature that the significance of attribute is related to the property of its refinement was analyzed.Then the relative refinement capacity was employed as the heuristic information.The completeness and the correctness of REDA were proved from the theoretic analysis.The examples show the minimal attribute reduction can be found by REDA in some cases with a higher probability than that gained by other approaches.Finally,the experiment indicates REDA is an efficient and complete attribute reduction algorithm,which can reduce the temporal and spatial complexity for the next work.

Key words: Rough set,Attribute reduction,Heuristic,Complete,Relative refinement capacity