基于混合进化算法的子结构发现研究

论文摘要

关系无处不在。近年来,学习数据中各种关系的结构数据挖掘得到了广泛的关注并成为了数据挖掘与机器学习领域的一个重要分支。结构数据含有更为丰富的信息,更能反映问题的本质,同时也会导致更大、更复杂的假设空间,从而向数据挖掘与机器学习领域提出了新的挑战。本文将在众多的复杂问题求解过程中表现突出的进化算法引入到结构数据挖掘的子结构发现之中,取得了较同类算法更好的实验结果。本文的主要工作包括如下内容:1、依据混合进化算法理论提出了混合进化子结构发现算法HEASD。在HEASD中,给出了基于图的染色体表示和遗传算子,并将爬山算法的思想融于交叉和变异算子的设计之中,实验结果表明了该算法的有效性。同时我们还提出了一种新的子结构扩展方法—单标签扩展,并对其正确性和有效性进行了理论证明和实验验证。2、子图同构问题是图数据挖掘的瓶颈问题,是造成问题复杂的根源所在。其表现之一就是它造成了进化的单向性,从而导致了查找的不完全性。为此我们提出了基于带回溯个体的混合进化子结构发现算法HEASDBT,将回溯机制融入到了进化过程之中,可以对假设空间中的某些关键区域进行密集搜索,实验结果表明了该算法的有效性。3、实例丢失现象是结构数据挖掘中广泛存在的造成解质量降低的一个重要原因。为此我们提出了两个算法HEASDFI和HEASDCI,前者采取“预防”的策略,尽量避免实例的丢失;后者则采取“治疗”的办法,重新找回丢失的实例。实验结果表明了以上两种算法的有效性。在HEASDCI中,我们还提出了一个新的遗传算子—个体协同算子,使多个代表同一子结构的不同个体可以对同一目标进行协同查找,以提高解的质量。由于个体协同算子需要进行频繁的图同构操作,而图同构操作虽然不像子图同构那样已被证明是NP完全问题,但目前还没有多项式级的算法存在,为此本文提出了一个时间复杂度为多项式级的近似图同构算法以提高个体协同算子的执行效率。4、将本文提出的算法应用于学科建设和区域经济研究。前者将各院校信息与计算科学学科的培养目标、课程设置等信息组织成为图数据,然后用本文提出的算法挖掘出典型模式作为新建专业的参考模型;后者将我国35个大中城市2005年的经济发展数据及城市之间的地域相邻关系建模为一个图,并用本文提出的算法挖掘出满足一定约束条件的经济发展模式。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 子结构发现的研究现状
• 1.2.1 子结构发现所属的研究领域
• 1.2.2 子结构发现的发展历程
• 1.3 本文研究背景
• 1.3.1 研究动机
• 1.3.2 项目资助
• 1.4 本文内容安排
• 1.5 本文创新点
• 第二章 子结构发现问题描述与Subdue系统
• 2.1 图的基本概念
• 2.2 子结构发现问题描述
• 2.2.1 子结构及实例
• 2.2.2 MDL与子结构的评价
• 2.2.3 子结构的扩展
• 2.3 Subdue系统
• 2.3.1 Subdue系统简介
• 2.3.2 Subdue算法的伪码描述
• 2.3.3 图数据的组织与表示
• 2.4 本章小结
• 第三章 进化算法与EPSD进化子结构发现算法
• 3.1 进化算法的产生与特点
• 3.1.1 从进化论和遗传变异理论到进化算法
• 3.1.2 进化算法的特点
• 3.2 进化算法的四种典型范式和一般框架
• 3.3 进化算法的各个组成部分及实例
• 3.3.1 表示和编码
• 3.3.2 评价函数
• 3.3.3 种群和多样性
• 3.3.4 选择
• 3.3.5 交叉和变异
• 3.3.6 种群初始化和算法终止条件
• 3.3.7 一个简单的进化算法示例
• 3.4 EPSD进化子结构发现算法
• 3.4.1 个体的表示
• 3.4.2 适应值评价
• 3.4.3 种群初始化
• 3.4.4 变异
• 3.4.5 选择与精英保留
• 3.4.6 EPSD伪码描述
• 3.4.7 实验结果与分析
• 3.5 本章小结
• 第四章 混合进化算法与混合进化子结构发现
• 4.1 混合进化算法设计
• 4.1.1 什么是混合进化算法
• 4.1.2 为什么要混合
• 4.1.3 混合进化算法的分类
• 4.1.4 混合进化算法的理论模型
• 4.1.5 局部搜索算法的使用频率和使用强度
• 4.1.6 混合进化计算的发展现状
• 4.2 基于混合进化计算的子结构发现算法
• 4.2.1 染色体的表示
• 4.2.2 种群的初始化
• 4.2.3 适应值、选择和精英保留
• 4.2.4 变异
• 4.2.5 交叉
• 4.2.6 算法的伪码描述
• 4.3 实验结果与分析
• 4.3.1 HEASD与EPSD实验结果对比与分析
• 4.3.2 单标签扩展与Subdue扩展性能对比
• 4.3.3 混合算法的有效性验证
• 4.4 本章小结
• 第五章 基于带状态回溯个体的混合进化子结构发现
• 5.1 子结构查找的单向性
• 5.2 可回溯的混合进化子结构发现算法
• 5.2.1 基本思想
• 5.2.2 染色体的表示
• 5.2.3 种群的初始化
• 5.2.4 适应值、选择和精英保留
• 5.2.5 变异
• 5.2.6 交叉
• 5.2.7 及时去掉种群中没有潜力的个体和重新初始化
• 5.2.8 算法的伪码描述
• 5.3 实验结果与分析
• 5.3.1 HEASDBT与EPSD实验结果对比与分析
• 5.3.2 回溯的有效性验证
• 5.4 本章小结
• 第六章 基于个体协同的混合进化子结构发现
• 6.1 子结构查找的瓶颈—实例丢失
• 6.2 带全部实例的混合进化子结构发现算法
• 6.2.1 染色体的表示
• 6.2.2 个体的评价
• 6.2.3 HEASDFI的其它组成部分
• 6.2.4 HEASDFI的实验结果与分析
• 6.3 基于个体协同的混合进化子结构发现算法
• 6.3.1 个体协同算子
• 6.3.2 一种新的多样性保持方案
• 6.3.3 算法的伪码表示
• 6.3.4 HEASDCI的实验结果与分析
• 6.4 本章小结
• 第七章 应用研究
• 7.1 在信息与计算科学学科建设中的应用
• 7.1.1 问题的背景
• 7.1.2 数据的收集与表示
• 7.1.3 调整子结构评价方法以偏置查找
• 7.1.4 挖掘的结果及分析应用
• 7.2 在区域经济研究中的应用
• 7.2.1 引言
• 7.2.2 数据的收集与预处理
• 7.2.3 条件挖掘
• 7.2.4 挖掘的结果及分析
• 7.3 本章小结
• 第八章 总结与展望
• 8.1 总结
• 8.2 展望
• 参考文献
• 发表论文和参加科研情况说明
• 附录一 实验的软硬件环境
• 附录二 实验图数据集
• 致谢