Research On Evolutionary Algorithm For Attribute Reduction Under Rough Set Model

The real world is full of massive amount of data.which may contain redundant data and noise,not only causing the high cost of data mining,but also causing the low quality of extracting rules.To solve this problem,rough set is introduced as a tool of knowledge reduction,which can remarkably improve the efficiency and quality of data mining.Rough set theory is a new mathematical tool to deal with imprecise,incomplete and inconsistent data,which reduces knowledge without additional prior conditions.In recent years,this theory has been widely used in machine learning,data mining,pattern recognition and other fields.To solve certain problems in knowledge reduction,systemic and deep study on the fields of rough set is performed.The main contributions of this thesis are as follows:(1)Two dynamic algorithms about computing core are proposed:an incremental updating algorithm for computing a global attribute core of vertically partitioned multi-decision table,and an updating algorithm of a core for the case of updating.The core of a decision table is the start point to many existing algorithms of attribute reduction.In the case of dynamic changes of the knowledge,static algorithms are in low efficiency.Thus,it can efficiently maintain the dynamic changes of core by using dynamic methods.(2)A new particle swarm attribute reduction algorithm and an improved ant colony optimization attribute reduction algorithm are proposed.Further,an attribute reduction algorithm combining PSO and ACO is proposed.Traditional heuristic methods of attribute reduction can improve the efficiency,but the result is not the optimal solution or the number of the individuals being too few.After introducing evolutionary algorithms,the problems that the result is not the optimal solution or the number of the results being too few can be effectively solved.By combining the evolutionary algorithm and rough set,the two attribute reduction algorithms,that can get a number of the smallest reduction and reduce the time complexity of the algorithms significantly,are proposed in this thesis.Therefore,these newly developed algorithms can be used as the preprocess of data mining.(3)A parallel attribute reduction algorithm based on the PSO and ACO strategies is proposed for reducing further the running time of the algorithm.In this thesis,two kinds of data extraction strategies utilized in the thesis(random sampling strategy and k-d tree strategy)can effectively overcome the disadvantages of the existing evolutionary algorithms aiming at single site.