The Algorithms For Attribution Reduction Based On Simplified Discernibility Matrix

In recent years, with the fast development of database technology, various databases to be used in various areas of business, government, etc. Network Information presented trends explosion, the ability to analysis and handle large amounts of data is very limited for people. How to obtain useful information from these massive data become the focus of attention. Rough set theory as a way to deal with uncertain, incomplete, imprecise information mathematical tool, and it has obvious advantages in the quantitative analysis to deal with uncertain and incomplete data, So it is widely applied to the field of artificial intelligence and data mining. The advantage of rough set theory is completely dependent on the data itself when it analyzes the data, and it does not require any additional outside information. So it avoid the influence of human subjective factors and ensure the objectivity of the results of the data analysis.The reality of the data has the following characteristics:(1)The data is very large. Due to the development of science and technology, variety of terminal equipment make it easy to the collection of data needed people, but also caused a rapid growth of the database.(2)Due to limitations of human reason or the data itself, the research data may be incomplete.(3) In real life, the data is constantly generated every time. In this case, the effective treatment is also needed.This paper studies the problem of attribute reduction based on the decision table system in the theory of rough set. The main objective of attribute reduction is to simplify Knowledge. Under the guarantee of knowledge classification ability remains unchanged, retaining as little property.Most of the current work of attribute reduction are for the decision complete system. But in real life due to the limitations of human reason or Decision system itself, the information accessed is mostly incomplete. Those methods for incomplete decision system is no longer applicable, therefore research incomplete decision system is better to meet the needs of real life. This paper researches the existing knowledge of attribute reduction. According to the characteristics of the data given above, made several innovations as follows:(1)As the object of study incomplete decision table, with the study of the notion of conflict region, the definition of attribute reduction based on conflict region in incomplete decision table is provided. A new attribution reduction algorithm which is in incomplete decision table is designed, whose time complexity is O(|K||C|2|U|)(|K|=max{|Tc(x1)|,x1∈U}).(2)The attribute reduction algorithm based on discernibility matrix has the nature of intuitive and easy to be understand. Due to it often produces a large number of repetitive elements and useless elements in discernibility matrix; it will waste a lot of memory and reduce the efficiency of the algorithm. In real life, this kind of data is often inevitable. In this paper, in order to delete the number of repetitive elements and reduce the number of useless elements, we construct a binary tree to store differential attribute set, and design a new algorithm which based on discernibility matrix attribute reduction ideas, and get the attribute reduction.(3)In order to overcome the problem of large space storage occupied by discernibility matrix, this paper introduces a binary storage structure. At this time algorithm only for static decision table, and in real life, the data is increasing. This paper proposed incremental attribute reduction algorithm based on binary tree. The algorithm can quickly update binary tree, and the use of the original attribute reduction for incremental update of attribute reduction. This has obvious efficiency than conventional algorithms.