Research On Matrix Algorithm For Attribute Reduction In Incomplete Decision Table

Rough Set theory is brought up by Z.Pawlak, a professor of Polish scientist in1982. It is a kind of mathematical tool. It is used for processing uncertain, inaccurate and inconsistent information. The difference between Rough Set theory and other theories that process uncertain or inaccurate information as follow:Rough Set theory that do not need to provide any priori information can directly analyze data sets and ratiocinate only need to provide the required data set. The main idea is that using the attribute reduction derived the classification of the problem based on keeping the classification ability of information system, And find the implied, unknown information and knowledge, then reveal valuable potential rule. Attribute reduction is one of the cores of the Rough Set theory. At the same it is also the key step of the knowledge acquisition. At present, this theory has been successfully used in artificial intelligence, knowledge discovery, pattern recognition, intelligent information processing, etc.The classical Rough Set theory consider complete information system as the research object and get the equivalent of each object in the domain through the equivalence relation. Then getting attribute reduction and knowledge acquisition using various reduction models. On the complexity of the algorithm, people have already got more satisfied solution.However, information system contains some missing or default data for some reason in real life. The equivalence relation is inexistence in incomplete information system. So it is limited that using the classical Rough Set theory deals with incomplete information system. Facing this problem, some researchers have extended the equivalence relation to tolerance relation, similarity relation and limited tolerance relation. Then getting attribute reduction in incomplete information system using the mature knowledge of complete information system. Or getting attribute reduction after turning incomplete information system into complete information system using the method of filling the data.This paper has the brief introduction of the basic concepts of Rough Set theory and all kinds of attribute reduction algorithms. According to incomplete decision table, a new binary tolerance matrix under single condition attribute is defined after analyzing attribute reduction based on tolerance matrix in incomplete information system. At the same time, absorption of operation rule between two of them is also defined. The binary tolerance matrix under the whole condition attributes in incomplete decision table can be gained by that rule. The absorption of operation rule is to use on the new binary tolerance matrix under single condition attribute of subset of condition attributes. If the binary tolerance matrix based on the subset of condition attributes is equal to the binary tolerance matrix under the whole condition attributes, the subset of condition attributes make up of an attribute reduction. It is proved that the attribute reduction acquired from this new method is equivalent to it based on positive region in incomplete information system. On that basis, an algorithm for attribute reduction is presented. This algorithm gets positive region first and compares the objects in Upos with the objects in U. Finding out the binary tolerance matrix of each condition attribute, And the binary tolerance matrix under the whole condition attributes can be getting through operation. Take the number of1in matrix as the heuristic information. The time complexity of this algorithm is max (O(|C||U|2),O(|C|2|Upos||U|)).The attribute reduction method based on discernibility matrix is one of the most commonly used methods, because it is simple and easy to understand. Usually the discernibility matrix storage condition attributes except binary discernibility matrix. Object matrix, viewed from objects, is defined in this paper. This object matrix based on the relationship between the decision value of the objects in tolerance class and condition attribute, and what it store is inconsistent object set. The intersection of all attribute reduction is core. So core is important part of Rough Set theory. The core and attribute reduction based on object matrix are defined. The correctness of the core is proved. And it is proved that the attribute reduction acquired from this new method is equivalent to it based on positive region in incomplete information system. Attribute reduction algorithms can start with core. Important attribute besides core were added into reduction set using relevant heuristic information until getting attribute reduction. For the discernibility elements mik of object matrix, the less of the elements in mik, the stronger the classification ability of relevant condition attribute is. If mik=φ, the condition attribute ak can separate object xi from other objects which need to be separated in U. On that basis, tow algorithms for attribute reduction based on object matrix in incomplete decision table are presented. The two algorithms get core when gain object matrix and then gain attribute reduction. The time complexity of this two algorithm is max (O(|C|2|Upos||U|),O(|C||U|2)) and space complexity is O(|C||C|2).