Research On Algorithm For Rule Acquisition Based On Enriching Discernibility Matrix In Incomplete Information Systems

With the development of science and technology,the popularity of the network,a large amount of information is preserved,people want to search the useful information on their own is becoming more difficult.Rough set theory is a relatively new soft computing method,and it is a mathematical tool after the probability theory,fuzzy set theory and the evidence theory to deal with uncertainty,and its effectiveness has been comfirmed by successfully applied in many fields of science and engineering,and it is also one of the hotspots of artificial intelligence theory and applications in the current international,so more and more people pay attention to it.Rough set theory at first main research object of a complete information system,whereas the data in real life could be missing type or the default type,the traditional rough set theory can no longer be used to handle this type of information system.How to solve this problem has become the research hotspot of some domestic and foreign scholars and experts,they began to use two types of thoughts to solve the problem,one is to be extended the equivalence relations theory of the complete information system to the incomplete information system,therefore the similar relations and tolerance relations extended model were produced;the other is through the data filling method,the vacancy valued of a incomplete information system will make to a complete information system in some way,and then process the data.Rule acquisition is an important research of rough set theory,which includes attribute reduction and attribute value reduction.The purpose of attribute reduction is to try to simplify the original data,and does not change the relationship between the data to the buried rules of the original data.And the result of the attribute reduction is carried out in order to better attribute value reduction,achieves the purpose of the rules acquisition.Thus,to study various extension model of rough set theory and knowledge acquisition method in a incomplete information system has important theoretical and practical significance.This paper is studying and researching the attribute reduction and rule acquisition in rough set theory based on the previous studies,it mainly carries on the following three aspects:(1) Discernibility matrix method used by many scholars because of its simple and convenient. However,for the vast amounts of data of the decision-making table in the face of the reality, the difference matrix using conventional methods to obtain the rule not only time- consuming, but will take up a lot of storage space, so that the efficiency of the algorithm is not high. Some scholars use the method of pairwise comparisons between elements to construct concentrated difference matrix algorithm,and the time complexity of the algorithm is O( |C? U|4), Because of the time complexity is too high, it is not suitable the processing of big data. There are many other scholars who put the difference element to be stored in a compressed FP tree, while it is reducing the storage space, but did not get rid of those unwanted elements, For this reason, we have designed an improved algorithm, introduced the idea of a binary tree, using the circulating method of a short difference set to establish binary tree and a long difference set successively to seek cycle,then on this basis.introduced the extended binary difference matrix,and directly extracted the rules, which is making the new algorithm time complexity reduced to max{O(|C?U|2),O(|C|2|Upos? U|)}. Experimental results show that the rule acquisition method of the concentrate difference matrix is efficient and feasible.(2) For the large decision table,the calculation of the discernibility matrix not only time-consuming and also a waste of space,resulting of these attribute reduction are not good enough. In order to minimize the discernibility matrix storage space.but also use the ideological of discernibility matrix,proposed the idea of discernibility object pair set,and knowledge granularity as a heuristic information,introduced the method of count by steps which is used to compute the tolerance class,and combined with the conflict region,the time complexity and space complexity reduced to max{O(|C?U|),O(| C?U/a|2}(a ? C) and max{O(|U|), O(| U/ a|2}(a ? C). Finally, Experiments show that the algorithm is a viable and efficient attribute reduction algorithm.(3) Due to the calculation of the discernibility matrix not only time-consuming and also a waste of space,resulting of these attribute reduction are not good enough. In order to reduce the complexity of attribute reduction algorithm,defined a heuristic function on the basis of boolean conflict matrix,which can measure the number of conflicts of the condition attribute in the decision table and given a fast algorithm of the heuristic function on the same time. Then,design an effective attribute reduction algorithm of the incomplete table based on the boolean conflict matrix with the heuristic function, the time complexity of the algorithm is reduced to O(K| C? U|) (K= max{|Tp(xi)? xi?U}). Finally, the experiment illustrates the effectiveness of the new algorithm.