Research On Algorithms For Attribution Reduction And Computing Core Based On Rough Set

Rough Set theory is a valid mathematic tool to deal with vague, imprecision and uncertain information. The main feature of rough set theory is that it does not need any priority or additional information, it can process the mass datas directly, find the implicit knowledge, which is also called decision rules. Rough set theory has widely applied in many fields successfully at present, such as theses research areas:data mining, knowledge discovery, intelligent decision-making, process control, artificial intelligence and expert systems.Attribute reduction and computing core is one of the most important researches in rough set theory and its application. Attribute reduction is to delete some irrelevant or redundant attributes, which is based on the same classification ability in the decision table and keep the basic important information unchanged. If the redundant attributes are removed in the decision table, the scale of the information decision table is reduced, so that the clarity degree of knowledge in the knowledge base is improved. Since in many attribute reduction algorithms of decision table, the core of decision table is computed at first, on the basis of the core, the attribute reduction is calculated by making use of the heuristic information. So that how to design the efficient algorithms of attribute reduction and computing core is very significant.At present, most of the attribute reduction algorithms are designed based on complete decision table, while due to the measurement error of the data in actual application and the restriction on the knowledge acquisition, people always face the incomplete decision table, that is to say, some attributes are unknown in incomplete decision table. Nowadays the attribute reduction and computing core in incomplete decision table are becoming one of the important researches. On the other hand, the time complexity of attribute reduction is relatively high in incomplete decision table, which is not convenient to tackle with large-scale data set. Therefore, how to design the quick algorithms of attribute reduction and computing core is a widely important work.In this dissertation, the basic knowledge of rough set are expounded briefly at first. Then the common models and corresponding algorithms are summarized theoretically based on both the complete decision table and the incomplete decision table. On studying and learning from existing research achievements, the new ideas and contributions are involved in this dissertation as follows:1) Making use of the following two properties:the objects with condition attribute value of the simplified decision table are order and the core is that the number of the elements in discernibility matrix is one. On these conditions, an efficient algorithm based on positive region for computing core is designed by integrating the idea of radix sorting, whose time complexity and space complexity are O(│C‖U│)+O(│C│2│U/C│) and O(│U│) respectively. In the new algorithm, the discernibility elements including the core may be mapped into a mall quantity of research space, so the core can be found through searching a small quantity of discerniblity elements of the simplified discernibility matrix, thus the efficiency of the new algorithm is improved, the emulate example show that the proposed algorithm is more efficient.2) The core definition of the Skowron simplified discernibility matrix is presented. Furthermore, it is proved that the mentioned core definition is the same as the core definition based on Skowron discernibility matrix. To calculate the Skowron simplified discernibility matrix, an efficient algorithm of simplified decision table is provided and a new property for computing core is provided, on this condition, an efficient algorithm for computing core based on Skowron simplified discernibility matrix is designed, whoes time complexity of the new algorithm is O(│C‖U│)+O(│C│2│U/C│). Finally, an example is employed to show that the new algorithm is more efficient than the two other classical algorithms.3) In order to reduce storage space of the discernibility matrix as possible as one can, while making use of the idea of the discernibility matrix, the method of object pair set is provided, then a new algorithm of attribution reduction based on information entropy is designed. In this algorithm, the idea of the discernibility matrix is used but not computing the discernibility matrix. To reduce the time complexity of the algorithm, on this condition of the simplified decision table, the definition of attribution reduction of object pair set is presented. What's more, it is proved that the above definition of attribution reduction is the same as the definition attribution reduction based on information entropy. On this condition, an efficient attribution reduction algorithm based on discernibility object pair set of information entropy, whose time complexity and space complexity of the proposed algorithm are O(│C‖U│)+O(│C‖U/C│2) and O(│U/C│2)+O(│U│) respectively.4) In incomplete decision table, according to relative theorems and the symmetry of the tolerance relation, the time complexity of the algorithm for computing tolerance relation is cut down to O(K│U‖C│), the definition of discernibility matrix and its corresponding attribution reduction are provided. At the same time, it is proved that the definition is equivalent to the definition of attribution reduction based on the positive region. The attribution reduction based on the positive region is established on the discernibility matrix, and the discernibility matrix is simplified for not comparing the objects between Uneg. On this condition, a quick algorithm for computing attribution reduction based on positive region is designed, whose time complexity is max{O(│C│2│Upos‖U│), O(K│U‖C│)}. Finally, an example is used to show the efficiency of the new algorithm.5) In incomplete decision table, the definition of discernibility matrix and its corresponding attribution reduction are presented. Furthermore, it is proved that the mentioned definition of attribution reduction is equal to the definition of generalized attribution reduction, it is also compressed the discernibility matrix, deleting a great deal of unuseful elements, so that the space is reduced and the efficiency is improved. Then a new efficient attribution reduction algorithm of incomplete decision table based on the compressed discernibility matrix is designed, the time complexity of the new algorithm is O(│C│2│U│2). Finally, an example is used to show the efficiency of the proposed algorithm.