Study On Computing Core Algorithm Based On Incomplete Decision Table

In the age of network information explosion, how to get potential, valuable, concise knowledge from a lot of desultorily data has become a problem that people of contemporary are facing with. Rough set theory is a mathematical tool that can process information of incomplete and inaccuracy, Which is widely used in data mining and artificial intelligence. Compared with other mathematical processing tools, the advantages of rough set theory is that it can directly process the mass information and find the hidden knowledge without any prior knowledge or any other additional information.This paper mainly studies the computing core algorithm of incomplete decision table in the rough set theory, Attribute reduction is also one of the important research in rough set theory. Generally the core is the attribute that has divisional role of attribute set in decision table, we can compute the core of decision table first, then compute the minimum attribute reduction by making use of the heuristic information. The main purpose of the attribute reduction is to simplify the knowledge base of knowledge and reduce the size of the knowledge base, then classify the knowledge base with as few attributes as possible, on the base of keeping the classification ability of the knowledge base unchanged.At present, most of the computing core algorithm is based on the complete decision table. But in the practical applications, as the measurement error of the data or the restriction on the knowledge acquisition, most of the information people get is not complete, then the values of some objects in some attributes are unknown. The rough set theory to complete decision table has been developed is no longer suitable for dealing with incomplete decision table, So designing efficient algorithms of attribute reduction and core computing in incomplete decision table is more practical and more suitable for using in the actual work.Granular computing is a new direction of research in the field of artificial intelligence, which is mainly used to dealing with the information of part real and huge amounts and the information of inaccurate and fuzzy. The main idea is to solve problems by computing the granular of different attribute.The paper’s research is the computing core algorithms of incomplete decision table. By studying the basic knowledge of rough set and the common models and corresponding algorithms both in the complete decision table and the incomplete decision table and learning from existing research achievements, the new ideas of computing core of incomplete decision table are put forward as follows:(1) A way to compute binary discernibility matrix based on incomplete decision table is provided, which is based on dividing the objects with different characteristics of the definite value object, but not considering the unknown value of characteristics.(2) By introducing the concept of knowledge granulation, the constructing the granulation binary discernibility matrix based on knowledge granulation was presented. According to the definition of the attribute importance and the definition of core, a computing core algorithm based on the granulation binary discernibility matrix is designed, whose time complexity is max{O(|C‖U‖Upos|),O(K|C‖U|)}, which is better than the time complexity of the same kind of algorithms.(3) The method of dealing with the complete decision table with the thought of discernibility object pair set was proposed on the base of knowledge granulation discernibility matrix. A discernibility object pair set of knowledge granulation of incomplete decision table was defined, Then an algorithm for computing core based on discernibility object pair set of knowledge granulation in incomplete decision table was proposed, whose time complexity is max{O(K|C‖U|),O(|C‖U‖Upos|)},which is better than the time complexity of the same kind of algorithms.(4) The traditional computing core of decision table based on discernibility matrix is computing all the discernibility matrixs directly, which is not only a waste of storage space but also a waste of time. To solve the problem and use the idea of discernibility matrix at the same time, the definition of discernibility matrix and core of incomplete decision table is introduced here. The computing core algorithm based on discernibility object pair set is proposed by introducing the the definition of discernibility object pair set in incomplete decision. The number of discernibility object pair set is far smaller than the elements of discernibility matrix. It greatly reduces the time and space complexity of computing the elements of discernibility matrix.