Research On Efficient Incremental Updating Algorithm For Attribution Reduction And Computing Core Based On Rough Set

Rough Set theory, was proposed by Pawlak in 1982, which is a efficient mathematic tool dealing with vagueness, imprecision and incomplete information. The main advantage of rough set theory in data analysis is that it does not need any preliminary or additional information about data, it can find the hiding and potential knowledge, that is decision rules. In recent years, Rough set theory has led to many interesting applications and extensions. It seems that the rough set approach is fundamentally important in artificial intelligence and cognitive sciences, especially in research areas such as knowledge discovery, machine learning, decision analysis, process control, pattern recognition, data mining and expert systems.In rough set theory, attribute reduction and corresponding core is one of important research. Attribute reduction, based on the classification ability in the knowledge base (decision table), is to delete some irrelevant or unimportant attributes, so that the knowledge in the knowledge base is simplified, but not loss some basic information. If the redundant attributes are removed, the size of the knowledge base is reduced, the cost is saved and the clarity degree of knowledge in the knowledge base is improved. Since in many attribute reduction algorithms of knowledge base, it is first to compute the core of decision table, then on the basis of the core, the attribute reduction is gradually computed. Therefore, to study the efficient algorithms of attribute reduction and the corresponding core has important theoretical significance and application value.At present, most of the existing algorithms are designed based on a static decision table, while the objects in actual decision table are usually dynamic, so the original attribute reduction and corresponding core may no longer be the attribute reduction and the corresponding core of a new decision table. Therefore, the recalculation to the attribute reduction and the corresponding core of new decision table is need. The computing of attribute reduction and core in static decision table will make a lot of useful information effectively unused in the original algorithm for the new decision table updated and changed little, especially for some occasions required for real-time. Therefore, the algorithms about computing attribute reduction and core based on static decision tables often do not apply, studying the efficient dynamically updating algorithm is a widely significant work. In this dissertation, the research trends and theoretical knowledge of rough set are Presented firstly. Then the existing attribute reduction methods, which consists of Pawlak algorithms, algorithms based on discernibility matrix, algorithms based on information entropy. The dissertation is mainly studying and learning from existing research, the new ideas and contributions included in this dissertation are summarized as follows:1) A quick improved algorithm of attribute reduction (Pawlak Reduction) based on positive region is proposed which make use of bitmap and granular computing. In this algorithm, a new heuristic information which can efficiently reduce the numbers of granular computing is proposed. That is to say, some computations which can not change the results of attribute reduction are reduced. The emulate example and the experimental results show that the proposed algorithm is more efficient and more reliable.2) The definition of attribution reduction of simplified binary discernibility matrix is provided. At the same time, it is proved that the above definition of attribution reduction is the same as the definition of attribution reduction based on information entropy. In order to compute simplified binary discernibility matrix, a quick algorithm for simplified decision table is adpoted. On this condition, a quick attribution reduction algorithm based on simplified binary discernibility matrix of Information Entropy is designed, the time complexity and space complexity of the new algorithm are max{ O ( | C || U |), O ( | C |2 | U′|2 )} and max{O ( | C || U′|2 ), O ( | U|)} respectively. At last, an emulate example illustrates the new algorithm is more efficient than the typical algorithms.3) Some drawbacks were analyzed in some existent the computing core algorithms, in order to improve the efficiency of the dynamically updating algorithm of computing the core in decision table, At fist, the concept of simplified decision table is introduced. Then an new incremental updating algorithm for computing core of decision table is designed with simplified binary discernibility matrix. When updating the simplified binary discernibility matrix, the new algorithm is only to update corresponding records on the basis of the old decision table, which doesn't need to compute the binary discernibility matrix of the old decision table. Computing the core of the decision table is conducted when the simplified binary discernibility matrix of the decision table is dynamically updating. For this reason, the efficiency and flexibleness of the new algorithm is remarkably improved. For the binary discernibility matrix is convenient to carry out by computer and its storage is small, the new algorithm remarkably improved the efficiency and flexibleness of updating the core dynamically. The time complexity and space complexity of the new algorithm are O( | C || U′|) and O (| C || U′p os|| U′|) respectively. At last, the emulate experiment and the comparative experiment performance illustrate the efficiency of the new algorithm.4) Since many attribute reduction algorithms in the decision table, it is first to compute the core, and then on the basis of the core, the attribute reduction is gradually computed. Based on the computed incremental updating core of 3) and make use of bitmap operation, a new incremental updating algorithm for computing attribute reduction of decision table is designed with simplified binary discernibility matrix. The time complexity and space complexity of the new algorithm are max{O (| Red|| U′p os|| U′|),O (| Red ? Core|2 | U′p os|| U′|)}and O (| C || U′p os|| U′|) respectively. At last, an emulate example is used to illustrate the efficiency of the new algorithm.