Rough Set Attribute Reduction Algorithm Based On Genetic Algorithm

Rough set theory has been proved to be an excellent mathematical tool dealing with uncertain and vague description of objects after vague theory and evidence theory. 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. The thesis studies on the rough set attribute reduction algorithm based on genetic algorithm.Firstly, the thesis reviews the theories and methods of rough set and genetic algorithm systematically, and analyzes the algorithms of attribute reduction based on discernibility matrix, attribute significance, dependability and GA.Then, based on the characteristic of rough set theory, genetic algorithm as well as decision table attribute reduction, through analysis of the existing primary algorithm of attribute reduction based on the traditional genetic algorithm, an improved algorithm of rough set attribute reduction based on dependability and genetic algorithm is presented in this thesis. There are three characters of the algorithm. The first one is that define the fitness function in the algorithm by the dependability of attribute, in order to decrease the time and space complexity respectively. The second one is that uses attribute core of decision table as a restriction to improve the binary code initial population which is produced stochastically in the primary genetic algorithm. This improvement can shorten the calculation time of the algorithm and raise the accuracy of the results of the attribute reduction. The third one is that adds a correction operator. In this operator, the algorithm uses attribute significance as heuristic information which can guide the algorithm carrying out in the space of feasible results, and the attributes which can make more important influence are prevented to be lost. Last, an experiment is shown to prove that the improved algorithm is more excellence than some other attribute reduction algorithm based on genetic algorithm, and it is more accurate and efficient to solve the problem of attribute reduction in decision table.