Research On Technologies For Improvement And Implementation Of Attribute Reduct Algorithm CARRDG

Information acquisition, especially for large scale of data, has become a challenging and meaningful subject. One of the relative key technologies is to eliminate redundant information in the data. Fortunately, attribute reduct provides an effective way to reach the target while keeping the inherent classification capability of the data unchanged. In this way, high dimensional data may become low dimensional data so that the difficulty and complexity of information processing are reduced.This dissertation can be viewed as an exhibition of fruits about the implementing and verifying technologies for the attribute reduct algorithm CARRDG, whose theoretical study has been developed. The main contribution of this dissertation is not only to implement the algorithm CARRDG, but also to verify its correctness and effectiveness by using six typical data for machine learning.Furthermore, in addition to the existed three heuristic deep-first searching principle(Member Executive Principle MEP, Friend Persuade Principle FPP, Stranger Enter Principle SEP) based on reduct discernibility graph, a new heuristic searching principle——Blocking Layer Block Principle (BLBP)——has been proposed to improve the efficiency of the algorithm CARRDG. Since the reasonable data structures have been developed, BLBP cannot increase the complexity of implementing the algorithm. In contrast, the experimental results by using UCI data show that BLBP exceeds MEP and FPP in trimming efficiency for some large information systems.In this dissertation, the reduct algorithm CARRDG with its improvement is introduced. Then the idea, technology and process of implementing the improved reduct algorithm CARRDG are interpreted in detail with a clue concerning on the total globe design, the design and implementation of main data structures, the creation and implementation of reduct discernibility graph, the computing and display of core attributes as well as the implementation of heuristic deep-first searching principles. Finally, the experimental results are presented and analyzed.It should also be noted that the program developed in this dissertation is so general and practical that for most real large information systems with proper forms, it can rapidly compute their total attribute reducts.In essential, the problem solved by the algorithm CARRDG is an arithmetic one that converting disjunction normal form into conjunction normal form, and vice versa. In this sense, the program developed in this dissertation for implementing the algorithm CARRDG have wide variety of application field since it can solve this kind of arithmetic problems.