Study On Attribute Reduction Algorithm Based On Rough Set

Rough Set theory is a new mathematical tool which can tackle ambiguity and uncertainty developed from the 1980s.It is an important method of intellective information transaction,which based of non-distinguish and knowledge reduction.Finding the minimal reduction is one of the most important works in the research of rough set theory,as an important part of soft computing,attribute reduction plays applications have played an important role,especially in the areas of knowledge acquisition,machine leaning,pattern recognition,decision analysis and modeling etc.However,it has been proved that finding the minimal reductions is a NP-hard problem.So it is the main study area on rough set in researching effective attribute reduction algorithm,acquiring the perfect result of attribute reduction and reducing the time complexity.Firstly,the thesis reviews the theories and methods of rough set systematically, and analyzes the algorithms of attribute reduction based on discernibility matrix, attribute significance,information entropy.The time complexity and space complexity of these algorithms have been analyzed detailedly.The traditional rough sets model didn't combine with the relation database system and all the intensive computational operations are performed in flat files, rather than take advantages of the very efficient set-oriented database operations.In view of that,the researchers proposed a new rough sets model based on database system and redefined the core attributes and reduction based on relation algebra in order to take advantages of the very efficient set-oriented database operations.Based on this,we propose the attribute reduction algorithm based on database.Finally,we compare the proposed algorithm with other attribute reduction algorithm on the runtime of the algorithm and the accuracy of reduction result and draw some conclusion.