Research On Algorithm For Attribute Reduction Table Based On Enriching Discernibility Matrix In Incomplete Information Systems

Nowadays, it is a big challenge how to extract the most useful information from vast amounts of data for network architecture and data processing capability.Rough Set becomes anther mathematical tool following the probability theory, fuzzy set and evidence theory to deal with to deal with uncertainty as the new soft computing in data processing after its effective proved in much more science and engineering fields.Rough Set is increasingly attention.Attribute reduction is one of the key problems in Rough Set, which doesn’t affect the ability of information system of classification to eliminate redundant data and to extract the unknown, implied, simple knowledge in the knowledge base. That reveals the potential valuable information with less attribute combination. The combinatorial explosion of attributes is the main reason that makes attribute reduction becomes an NP hard problem. With the arrival of the era of big data and the rapid development of database technology, data of scientific research institutions, government, enterprises and other units in various fields are driving exponential and these data are disoederly and unsystematic and interference. It is a big challenge to deal with vast amounts of data for network architecture and data processing capability. So far solving attribute reduction is still not an efficient and feasible method, so it is still a research hot spot to solve an effective algorithm of attribute reduction in Rough Set theory.In many practical cases, people can not make the complete and accurate judgment because of the limitations of the human mind to the external environment, data acquisition technology is limited,the transmission media failure,and the impact of the time factor. (For example,the diagnostic system of the hospital,for collection of the patient objects, and some of the results of clinical examination of the patient attribute values,it is impossible to get all of the test results).The data is missing or the credibility of the data is reducing in the collection of the data.Incomplete data can cause data distortion and the knowledge rules are not reliable.The only unreliable is that the rules disturb people to make the right decisions.Rough set theory which is based on the unclear relationship of the traditional can only handle the complete information system which all property values are known and identified and can not handle the incomplete information system which data is missing.Therefore,Research all kinds of the extended model of Rough Set Theory and its knowledge acquisition method has more important theoretical and practical significance.The paper researches algorithm of Attribute Reduction in the incomplete information system based on the Rough Set and discernibility matrix. The main research work is as follow:(1) We import the concept of enriching discerinibility matrix, use the thought of Boolean-And and give the algorithm of Boolean-And with enriching discerinibility matrix in incomplete information system. The experimental results show that the method of enriching discerinibility matrix is superiority in algorithm of Attribute Reduction. The UCI experimental proves the value of enriching discerinibility matrix.(2) Discemibility matrix method which is to be easy understood and to be designed is accepted and used by many scholars. However, it is a waste of time and a huge amount of storage for big decision table to compute discernibility matrix. For decreasing the storage of the discernibility matrix and using the idea of discernibility matrix, Scholar give the ideal of the idea of discernibility object pair set, but it doesn’t apply to big decision table. For this purpose, we define a function that can measure the numbers of discernibility object pair Based on the research of discernibility object pair set. The new algorithm time complexity and space complexity were reduced O(K|C||U|)(K=max{|Tc(xi)|, xi∈U})and O(|Q|), New algorithm greatly reduces the speed of the algorithm. The experimental results show that the algorithm is efficient and feasible.(3) Further researching the method of Discernibility Object Pair Set, research shows that the time and space complexity of the algorithm of Discernibility Object Pair Set. So that we define a function, which can measure the numbers of discernibility object pair based on ideal of attribute reduction based on discernibility object pair. And the function is used to design a new heuristic function. At the same time, an efficient algorithm for computing the heuristic function is proposed.Meanwhile, the new heuristic function is used to design an efficient attribute reduction algorithm based on incomplete decision table. The new algorithm’s time complexity and space complexity reduced to O(K|C||U|) (K=max{|Tc(xi)|,xi∈U})and O(｜U｜)。 New algorithm greatly reduces the speed of the algorithm. The experimental results show that the algorithm is efficient and feasible.