GrC-based Research On Knowledge Reduction Algorithms For Decision Table

With the rapid development of computer and Internet technology, hugeamounts of data and a variety of information resources are produced. People areeager to obtain more knowledge from the abundant data, then it was like theappearance of “big data” and “lack of knowledge”. As a means of knowledgeacquisition, but also can deal with uncertain information, rough set theory hasbeen developing rapidly in recent years. Attribute reduction and rule extractionis the core research contents of rough set theory, and it’s also an importantresearch topic in the field of knowledge discovery. Efficient and fast algorithmsfor knowledge reduction has beening the direction and hot issue for rough setsresearchers to study.Granular computing (GrC) is a new subject developed in recent years, anda lot of research and development has been made in artificial intelligence,machine learning, data mining, pattern recognition and fault diagnosis, and otherfields. People are always eager to analyze and solve problems from severalaspects, and the main idea of granular computing is to analyze problems frommultiple granularity, then solve the problems from the various granularity, andeventually merge the solution of each granularity to be the original problemsolution, this accords with the cognitive law of human. Therefore, GrC hasreceived extensive attention of the interdisciplinary field of research workers, and it has become a new processing method of complex problem and intelligentinformation.This thesis starts from the study of granular computing and rough set theory,mainly focusing on attribute reduction and rule extraction. Specifically, we carryout the relevant work from the following several aspects:(1) First of all, the granulation idea of granular computing is used to thegranulation of decision table, and study on how to depict and representinformation granule (equivalence class). On the basis of knowledge granularity,we define the concept of granular space;(2) The relationship of condition equivalence classes (information granule)and decision equivalence classes was mainly analyzed, and we use granularmatrix to represent condition information granule and decition informationgranule, as well as the relationship between the information granules. Then therelationship between information granules was mapped on the problem ofattribute reduction and rules extraction. Lastly, we defined relevant propertiesand theorems and give the corresponding proof;(3) On the research of attribute reduction, respectively from the study ofconsistent decision table and inconsistent decision table, attribute reductionalgorithms based on granular computing were designed and proposed, theexample verification for the proposed algorithm and the complexity of thealgorithm is analyzed, finally, the attribute reduction algorithm proposed in thispaper with several common attribute reduction algorithms are summarized andcompared, the advantages and disadvantages of this algorithm were analyzed,and we put forward the further research direction;(4) On the study of rules extraction, the combination relationship betweeninformation granules by granular matrix was mainly studied, the relevantproperties and theorems were defined and two heuristic operators were defined.Then, we design rules extraction algorithms related to consistent decision tables and inconsistent decision tables, and example vertification and analysis of theproposed algorithms have been done on them. Lastly, we made UCI datasets testcompared to several similar rules extraction algorithm, the test results show thesuperiority and effectiveness of the algorithm in this paper;(5) Finally, on the basis of the algorithms in this paper, the knowledgereduction system based on granular computing was designed and implementedin MATLAB development environment.