【作者】 郭春根；

【导师】 刘业政；

【作者基本信息】 合肥工业大学 ， 管理科学与工程， 2007， 硕士

【摘要】 粗糙集理论是继概率论、模糊集理论、证据理论之后的又一个处理含糊性和不确定性的数学工具。属性约简算法是粗糙集理论的核心内容。粗糙集属性约简的研究在知识获取、机器学习、模式识别、决策分析、模型建立等实际应用中有重要的意义；但是，由于属性约简被证明是一个NP-hard问题，因此，研究更为有效的属性约简算法，有效地获取较优的属性约简，降低算法的时间复杂度，寻求快速的约简算法仍是粗糙集理论的主要研究课题之一。本文对基于遗传算法的粗糙集属性约简算法进行了研究。本文首先介绍了粗糙集理论的基本概念和遗传算法的相关知识。对粗糙集理论中基于区分矩阵、属性重要度、属性依赖度的属性约简算法以及启发式遗传约简算法进行了系统综述，并且对各种算法进行了比较分析。在对粗糙集理论和遗传算法的研究基础上，通过分析比较现有的遗传约简算法，吸收算法的优点，并且加以改进，提出了一种基于属性依赖度的遗传约简算法的改进算法。本算法的主要特点在于：一是在适应度函数中引入了决策属性对条件属性的依赖度，使算法在加强局部搜索能力的同时保持了该算法全局寻优的特性，也保证了所求约简既含较少的属性又保证分类质量，能够获得最佳的搜索效果。二是对传统遗传算法中随机产生的二进制初始种群加以改进，用属性核加以限制，以增强遗传算法的局部搜索能力，缩短算法的计算时间，并提高决策表属性约简结果的准确性。三是在遗传算法的遗传算子的基础上，新算法进行了局部优化策略，增加了修正校验算子，采用了基于属性依赖度的重要度修正策略，使得算法在局部空间能够得到一个较优解，保证遗传算法的全局搜索在有效的可行解空间进行。该算法通过数据实验分析，证明是求解知识约简问题的快速有效方法。更多还原

【Abstract】 Rough set theory has been proved to be an excellent mathematical tool dealing with uncertain and vague description of objects after vague theory and evidence theory. Finding the minimal reduction is one of the most important works in the research of rough set theory, as an important part of soft computing, attribute reduction plays applications have played an important role, especially in the areas of knowledge acquisition, machine leaning, pattern recognition, decision analysis and modeling etc. However, it has been proved that finding the minimal reductions is a NP-hard problem. The thesis studies on the rough set attribute reduction algorithm based on genetic algorithm.Firstly, the thesis reviews the theories and methods of rough set and genetic algorithm systematically, and analyzes the algorithms of attribute reduction based on discernibility matrix, attribute significance, dependability and GA.Then, based on the characteristic of rough set theory, genetic algorithm as well as decision table attribute reduction, through analysis of the existing primary algorithm of attribute reduction based on the traditional genetic algorithm, an improved algorithm of rough set attribute reduction based on dependability and genetic algorithm is presented in this thesis. There are three characters of the algorithm. The first one is that define the fitness function in the algorithm by the dependability of attribute, in order to decrease the time and space complexity respectively. The second one is that uses attribute core of decision table as a restriction to improve the binary code initial population which is produced stochastically in the primary genetic algorithm. This improvement can shorten the calculation time of the algorithm and raise the accuracy of the results of the attribute reduction. The third one is that adds a correction operator. In this operator, the algorithm uses attribute significance as heuristic information which can guide the algorithm carrying out in the space of feasible results, and the attributes which can make more important influence are prevented to be lost. Last, an experiment is shown to prove that the improved algorithm is more excellence than some other attribute reduction algorithm based on genetic algorithm, and it is more accurate and efficient to solve the problem of attribute reduction in decision table.更多还原