Study On Attribute Reduction Algorithm Based On Rough Set Theory

Attribute reduction is one of important step in preprocessing of data mining, it improves the efficiency of the data mining algorithm by reducing the dimensions of the information. Rough set theory is a mathematical tool used for dealing with vagueness and uncertainty. Attribute reduction is also one of the basic topics in the rough set theory field.It has been proved by Wong.S. K.M and Ziarko that computing the minimal reduction of decision table is a NP-hard problem. In artificial intelligence, approaching to these problems is heuristic searching. The significance of attribute is used as the heuristic information to reduce searching space. MIBARK is an attribute reduction algorithm based on significance of attribute. Defining the significance of attributes, it requires very big calculating quantity. Because it is necessary to calculate mutual informations between the combinations of different condition attributes and the decision attributes for many times.In order to improve the efficiency of the algorithm, using frequency as the heuristic information of attributes selection, getting frequency of attributes from the filtered discernibility matrix, an improved algorithm based on MIBARK is proposed in this paper.The experiment shows that this algorithm, obtaining the same reduction as MIBARK algorithm, can get frequency information of attributes and discernibility matrix at the same time, and need not calculate mutual informations. So it requires less computational effort, and the speed of computing is improved.In the different systems and environments, the user's actual decision need and interest to the attribute reduction is different, but most of algorithms of attribute reduction doesn't take the user's need into account. In order to satisfy the user's need and interest, another algorithm of approximate reduction about attribute is proposed. Using conditional entropy as the heuristic information, it does not compute the core attribute, attribute reduction starts from the condition attributes directly.All steps of this algorithm are given through an example, the results show that the algorithm needs less computing quantity, and the users can obtain a satisfied attribute reduction by changing the value according to actual decision need.