The Research On Reduction Algorithm Of Rough Sets Theory

Rough Sets Theory, presented by Pawlak in 1982, is an tool to handle information,it can effectively deal with imprecise, inconsistent, incomplete information, etc.The research on rough set theory has become a hot spot, the theory is widely applied in instrusion detection,data mining,knowledge discovery and so on.Attribute reduction is an important part of Rough Sets Theory,the purpose of attribute reduction is to delete the redundant attributes under the condition of maintaining the classification,get a concise decision table to provide convenience for the later calculation.There are many algorithms on attribute reduction,but this paper mainly introduces the algorithms based on discernibility matrix.Firstly,this paper introduces several typical reduction algorithms,gives the definitions of the algorithms,analyzes the solving processes of the algorithms,points out the advantages and disadvantages of them,gives relevant solutions for the faults,gives examples at last.Secondly,a new model of attribute reduction is introduced,this model is equivalent to the traditional model.Some related definitions of this model and attribute reduction algorithm based on this model are presented in this paper,and an example is given to demonstrate the attribute reduction process of the algorithm.Thirdly, an algorithm based on discernibility matrix is introduced,it calculates the minimum reduction by U/{c} partirion,this paper points out the algorithm's disadvantages:there are repeated computation and the algorithm maybe get wrong results.After the disadvantages of the algorithm is analyzed,an improved algorithm is presented,firstly,the algorithm compresses the data of decision table,delete the redundant data,this reduces the time complexity and the space complexity,then a minimum attribute reduction based on core of attributes are used to compute the minimum reduction.Finally, the improved algorithm is analyzed,only if there are many redundant datas in the decision table,the improved algorithm can work effectively,the algorithm needs further improvement, such as combining with intelligent computation.