Dissertation > Excellent graduate degree dissertation topics show

Research on Algorithms for Attribution Reduction and Computing Core Based on Rough Set

Author: ShuWenHao
Tutor: XuZhangYan
School: Guangxi Normal University
Course: Computer Software and Theory
Keywords: Rough Set Attribute Reduction Nuclear The complexity of the algorithm
CLC: TP18
Type: Master's thesis
Year: 2011
Downloads: 101
Quote: 3
Read: Download Dissertation

Abstract

Rough set theory is an analytical mathematical tools of fuzzy, imprecise and uncertain information. Its main feature is that it does not require any a priori knowledge, or any other additional information can direct processing of massive data processing, discover implicit knowledge, decision-making rules. Currently, the rough set theory in data mining, knowledge discovery, intelligent decision-making, process control, artificial intelligence and expert systems, and other fields has been more widely used. Attribute reduction and core finding is one of the important research content of rough set theory and applications. Attribute reduction delete Knowledge Base irrelevant or redundant attributes in the case of the same to maintain the knowledge base in data classification ability, knowledge in the knowledge base that can be simplified, but without losing the basic knowledge in important information. If you can delete the Knowledge redundant attributes, so that can be effectively reduced the size of the knowledge base processing, so as to improve the clarity of the potential of knowledge in the knowledge base. However, due to attribute reduction in the decision-making table, most of the reduction algorithm first nuclear-based heuristic information to solve the attribute reduction, then on the basis of the nuclear. How to design efficient attribute reduction and for counting has important research significance. Currently, many scholars have proposed a variety of attribute reduction algorithm, the overwhelming majority as research subjects in order to complete the decision-making table. However, in practical applications due to the measurement error of the data, of knowledge acquisition restrictions for various reasons, people are often faced with incomplete decision table, that the decision-making table there may be some of the properties of the attribute value is unknown. Today attribute reduction based on incomplete decision table for counting has become one of the research hotspots in rough set theory. But due to incomplete attribute reduction algorithm time complexity of the decision table is relatively high, which makes the algorithm is not conducive to dealing with large-scale data, so how to design a fast algorithm for attribute reduction in incomplete decision table has a wide range of practical significance. This paper briefly elaborate on the knowledge of the basic theory of rough set theory and system overview based on incomplete decision table based on incomplete decision table attributes reduction and core finding common model and its associated algorithms, and learning and drawing on make the following major innovations: 1) on the basis of research results, according simplify the decision-making table object attribute values ??is orderly and nuclear simplified discernibility matrix in the difference between the number of elements in the two nature radix sort of thinking, to design an efficient based on positive region for counting time complexity of O (│ C │ │ U / C) O (│ C | | U |), its spatial complexity is O (| U |). In the algorithm, the difference between elements of the nuclear properties set mapping to a smaller search space, just judgment of a small amount of difference in the simplified discernibility matrix elements can find the core attributes, so the efficiency of the algorithm has been improved. And case study shows the efficiency of the new algorithm. 2) gives a the Skowron simplified differential matrix nuclear definition and analysis proved that definition, and the definition of based on Skowron difference matrix nuclear equal. Solving the Skowron simplify difference matrix, the introduction of a fast algorithm that seek to simplify the decision-making table. Then proposed a new can effectively improve the nature of the calculation of nuclear properties algorithm, designed on the basis of an efficient accounting method, the algorithm based on the of Skowron difference matrix time complexity of O (│ ‖ U │) O (│ C │ 2U / C │), and the experimental results show the efficiency of the new algorithm is superior to the typical two algorithms. 3) in order to minimize the difference matrix storage space, and can at the same time take advantage of the difference matrix design ideas, combined distinguish objects on the design of a new attribute reduction algorithm based on information entropy, the algorithm does not need to calculate The difference matrix, but at the same time take advantage of the idea of ??the difference matrix. The definition given on the basis of simplified decision table in order to reduce the complexity of the algorithm, distinguish objects defined set of attributes reduction theory proved with the definition of equivalence of attribute reduction based on information entropy . Designed based on the distinction between objects based on information entropy sets attribute reduction algorithm, whose time complexity and space complexity, respectively: O (│ C ‖ U │) O (│ C | | U / C | 2) and O (| U / C | 2) O (| U |). 4) incomplete decision table, the the tolerance class nature of the calculation Tolerance TC (x) algorithm time complexity is reduced to O (K │ U ‖ C │), at the same time gives a model based on the positive region the difference between the matrix and the corresponding attribute reduction definitions, the definition of attribute reduction based on positive region definition is equivalent. Then incomplete decision table reduction based on positive region to establish the difference matrix, and because of the difference matrix without Uneg between objects, making the difference in the matrix can be simplified. On this basis, we designed attribute reduction algorithm based on positive region, the time complexity is max {O │ C │ 2 │ Upas ‖ U-│), O (K │ U | | C |). Finally, through specific examples to illustrate the effectiveness of the algorithm. 5) incomplete decision table is given a generalized decision model difference matrix and the corresponding definition of attribute reduction is equivalent to prove that the definition of generalized decision attribute reduction definition. And the difference matrix compression effectively get rid of a lot of useless empty value elements, makes the difference to the matrix retain only useful element of the algorithm, which saves a lot of storage space, and improve the efficiency of the algorithm. Then use the corresponding difference matrix design attribute reduction algorithm based on generalized decision, the time complexity down to O (| C | 2 | U | 2), and finally by specific examples to illustrate the effectiveness of the algorithm.

Related Dissertations

CLC: > Industrial Technology > Automation technology,computer technology > Automated basic theory > Artificial intelligence theory
© 2012 www.DissertationTopic.Net Mobile