粗糙集模型下的进化属性约简算法研究

论文摘要

现实世界的数据是海量数据,大型数据库含有冗余特征及噪音,不仅导致数据挖掘的代价高,而且导致规则提取的质量低。针对此问题,通过粗糙集工具对海量数据进行知识约简,可有效提高数据挖掘的效率及质量。粗糙集是一种新的处理不精确、不完全与不相容知识的数学理论,无需附加先验条件,即可对知识进行约简。近年来,该理论在机器学习、数据挖掘及模式识别等多个领域得到了广泛的应用。本文列粗糙集理论做了深入的研究,力图在一定程度上解决知识约简中的若干问题。论文工作的主要成果表现在如下几个方面:（1）提出两个核的动态求解算法:垂直分布多决策表的增量式求核算法和基于数据修改的求核算法。核是粗糙集理论的重要研究内容之一,大多数属性约简算法,将求核作为求属性约简的前一步骤。然而,在知识动态变化的情况下,采用静态方法求核代价高。为此,采用动态求核方法,可高效维护核的动态变化。（2）提出新的粒子群优化属性约简算法及改进的蚁群优化属性约简算法,并在上述研究的基础上,又提出结合粒子群和蚁群搜索策略的属性约简算法。采用传统的启发式属性约简算法虽可提高求解效率,但存在解个数过少及求得的解为次最佳解等问题。为此,引入进化算法,可有效解决纯粹粗糙集工具得到的解数目过少及求得的解为次最佳解等问题。本文提出的粗糙集模型下的进化属性约简算法可同时得到多个最小约简,且算法时间复杂度明显降低,为数据挖掘的后续步骤打下了良好的基础。（3）提出基于粒子群及蚁群优化的并行属性约简算法,以此有效缩短算法的执行时间。本文的并行机制采用两种数据抽取策略（随机抽取策略及k-d tree抽取策略）可有效祢补单机串行进化算法求解效率低的缺点。

论文目录

• 摘要
• ABSTRACT
• 第一章 概述
• 1.1 课题研究的意义
• 1.2 粗糙集的国内外研究现状
• 1.2.1 粗糙集的研究背景及趋势
• 1.2.2 核的研究现状
• 1.2.3 属性约简的研究现状
• 1.3 本文的创新之处
• 1.4 论文的主要内容
• 1.5 论文的组织结构
• 第二章 粗糙集基础知识介绍
• 2.1 粗糙集基本概念
• 2.1.1 知识表示系统和等价类
• 2.1.2 基本概念
• 2.1.3 核与约简
• 2.2 粗糙模型之间的比较及相关结果
• 第三章 粗糙集求核算法研究
• 3.1 核的静态求解算法
• 3.2 核的动态求解算法
• 3.2.1 增量式求核算法
• 3.2.2 基于数据修改的求核算法
• 第四章 进化属性约简算法研究
• 4.1 引言
• 4.2 启发式属性约简算法
• 4.3 基于进化算法的属性约简算法
• 4.3.1 基于遗传算法的属性约简算法
• 4.3.2 基于蚁群优化的属性约简算法
• 4.3.3 基于粒子群优化的属性约简算法
• 4.3.4 基于粒子群及蚁群优化的属性约简算法
• 第五章 并行进化属性约简算法研究
• 5.1 引言
• 5.1.1 并行的机制
• 5.1.2 数据抽取的策略
• 5.2 基于粒子群及蚁群优化的并行属性约简算法
• 5.3 实验结果及分析
• 第六章 结语
• 参考文献
• 致谢
• 附录一 读研期间发表论文情况
• 附录二 读研期间获奖情况