Research On Attribute Reduction Algorithm In Incomplete Decision Table Based On Rough Set Theory

Rough set theory is presented by Z.Pawlak, a professor of Polish mathematician in1980s. As a kind of mathematical tool in data analysis, It could makes quantitative analysis and deals with inaccurate, uncertain, inconsistent information. Rough set theory has been an important tool to data mining due to it doesn’t need to provide any priori information and uses a pair of upper and lower approximate set to describing knowledge. With the development in rough set, this theory has been applied to machine learning, process control, cognitive science and other fields successfully.Attribute reduction and computing core are the basic issue in rough set theory. Attribute reduction is to delete the irrelevant or redundant attributes which is based on keeping the original information in data. This problem is also important to data mining and pattern recognition. To the core, it defined by attribute reduction, and is an essential part of attribute reduction. We can obtain an attribute reduction through add some attribute to the core in an information system.The classical rough set theory is based on indiscernibility relation, and generally uses to process the complete information system with discrete attribute value. Due to the wrong comprehending, omission and restriction on the data acquisition, we also face to some incomplete information systems in our life. Compared to the complexity of reduction algorithm in complete information table, it is worth researching the attribute reduction in incomplete information table. At the same time, it plays a key role in taking this theory into practice.In this thesis, the basic concepts of rough set theory and some attribute reduction algorithms are briefly introduced at first. Through analyzing of attribute reduction in incomplete information table, the new research and contributions on attribute reduction and computing core as follows:(1) Define two kinds of core and give corresponding algorithm of computing core. To attribute reduction based on discernibility matrix in complete decision table, the condition attribute must belong to the core if a single element exists in matrix. Firstly, a new discernibility matrix is given by this mind. And then, the core is defined use this matrix. And it proves that the core is equivalent to the one based on positive region in incomplete information table. At last, the core of E condition entropy is defined too. (2) Attribute reduction based on conditional distribution information quantity. At present, one weakness of some algorithms of attribute reduction which are based on the view of information theory is that the system will reduce its classification capacity when increasing the condition attribute in incomplete information table. So, we bring up a definition of conditional distribution information quantity. This information quantity comes from the distribution that condition attributes determinate tolerance class on the division of decision attribute. Meanwhile, new attribute significance is defined, and a heuristic attribute reduction algorithm is given. At last, experimental result shows that this algorithm is effective for attribute reduction in incomplete decision table.(3) Attribute reduction in incomplete decision table based on ant colony optimization and E conditional entropy. Since finding a minimal subset of reduction is an NP-hard problem and evolution algorithm shows good performance in solving the combinatorial optimization problem, we present an algorithm of attribute reduction by using ant colony optimization. In this algorithm, the core of E conditional entropy is introduced into the initial feasible solution of artificial ant directly. And the heuristic information is attribute significance of E conditional entropy. At the same time, we use the random exchange mechanism between some artificial ants to avoid getting the local optical solution. Finally, some datasets in UCI machine learning repository are used to test this algorithm. The experimental result shows that the algorithm can find the minimal relative reduction, and it is effective.