软件工程
软计算方法软计算方法
    从海量数据中获取信息是具有挑战和现实意义的课题，其中的关键技术之一在于如何消除数据中的冗余信息。属性约简为解决该问题提供了有效途径，其目的是在保持已有数据信息分类能力不变的前提下，消除冗余属性，使高维数据降为低维数据，从而降低信息处理的难度与复杂性。因此，属性约简在数据挖掘、机器学习、知识发现、决策支持等领域具有重要意义。本文是在对属性约简算法CARRDG的理论研究基础上，对属性约简算法CARRDG的实现与验证技术进行进一步研究。本文不仅完全实现了属性约简算法CARRDG，而且用六种典型的UCI机器学习数据验证了算法CARRDG的正确性与高效性。本文针对属性约简算法CARRDG在实现技术层面上的可改进之处，在原有的三种约简分辨图深度优先搜索原则（成员独占原则、友人劝阻原则、陌生人吸纳原则）的基础上，增加了新的深度优先搜索原则──阻挡层阻挡原则。由于采用了恰当的数据结构与实现技术，阻挡层阻挡原则不会增加算法实现的复杂性，也几乎不会增加程序的运行时间。相反，实验结果表明，阻挡层阻挡原则对于某些大型信息系统的约简分辨图的剪枝效率甚至超过了成员独占原则与友人劝阻原则。本文首先介绍了属性约简算法CARRDG及其改进方法，然后以总体设计、主要数据结构设计与实现、约简分辨图的创建与实现、核属性集的计算与显示、启发式深度优先搜索原则的实现为主线，详细阐述了改进型属性约简算法CARRDG实现的思想、技术与过程，最后介绍了实验结果分析。本文所实现的属性约简算法CARRDG的程序具有通用性与实用性。对于大多数现实中的信息系统，只要符合基本格式要求，程序都能快速地计算出其所有属性约简。属性约简算法CARRDG本质上解决的是数学领域中析取范式与合取范式的相互转换问题。因此，本文实现属性约简算法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 principles(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.