Research On The Attribute Reduction Algorithm Based On Rough Set In Data Mining

Data Mining has been an urgent need because of increasing size of current databases. Rough Set theory, a new mathematical theory for mining and processing imprecise and uncertain data, has got great improvement under this background. Rough Set theory has also become a main method for KDD due to its unique advantage in knowledge discovery.Attribute reduction is one of the key topics in the Rough Set theory field. First, the model of Rough Set theory of Pawlak is introduced in this paper and its basic concepts such as decision table, discemibility matrix, and reduction. These are basic theories for the latter chapters about attribute reduction algorithms.It has been proved that computing the minimal reduction of decision table is a NP-hard problem. In AI the approach to these problems is heuristic algorithm. The significance of attribute is used as the heuristic information, and the core attribute as the start of the algorithm, thus, the size of searching space can by reduced by adding heuristic information to the algorithm. And then the concept of relative discemibility matrix is introduced and on which a revised reduction algorithm is given. This algorithm converts the logic operation to the algebraic operation, so it can simplify the operation and enhance the efficiency of seeking the reduction in some extent. And then a relative attribute reduction algorithm is mentioned based on information entropy. At last in this paper a new attribute reduction algorithm is given based on the gray relationship degree theory, and by analyzing the CTR, it is concluded that the algorithm can obtain better reduction and even can get the optimal attribute reduction sometimes.