第1章 绪论 1
1.1 图学习的目的 1
1.2 图学习的应用领域 4
1.3 子结构发现的研究现状 6
1.3.1 子结构发现所属的研究领域 6
1.3.2 子结构发现的发展历程 8
1.4 本书内容安排 10
1.5 本章小结 12
参考文献 13
第2章 子结构发现与Subdue系统 17
2.1 图的基本概念 17
2.1.1 图与带标签的图 17
2.1.2 度、路径、连通图 19
2.1.3 图同构、子图同构 19
2.2 图匹配 22
2.2.1 精确图匹配 22
2.2.2 不精确图匹配 24
2.3 子结构发现问题描述 27
2.3.1 子结构及实例 27
2.3.2 MDL与子结构的评价 29
2.3.3 子结构的扩展 30
2.3.4 子结构发现的作用和意义 31
2.4 Subdue系统 32
2.4.1 Subdue系统简介 32
2.4.2 Subdue子结构发现算法的伪码描述 33
2.4.3 图数据的组织与表示 34
2.4.4 图概念学习 40
2.4.5 图聚类 43
2.5 本章小结 47
参考文献 48
第3章 进化算法与EPSD进化子结构发现算法 50
3.1 什么是进化算法 50
3.1.1 最优化问题 51
3.1.2 从进化论和遗传变异理论到进化算法 53
3.1.3 进化算法的特点 55
3.2 进化算法的四种典型范式和一般框架 58
3.2.1 遗传算法 58
3.2.2 进化策略 59
3.2.3 进化规划 59
3.2.4 遗传规划 60
3.2.5 进化算法的一般框架 61
3.3 进化算法的各个组成部分及实例 62
3.3.1 表示和编码 62
3.3.2 评价函数 67
3.3.3 种群和多样性 67
3.3.4 选择 68
3.3.5 交叉和变异 70
3.3.6 种群初始化和算法终止条件 73
3.3.7 进化算法运行示例 74
3.4 EPSD进化子结构发现算法 78
3.4.1 个体的表示 78
3.4.2 适应值评价 78
3.4.3 种群初始化 78
3.4.4 变异 79
3.4.5 选择与精英保留 79
3.4.6 EPSD伪码描述 79
3.4.7 实验结果与分析 79
3.5 本章小结 82
参考文献 83
第4章 混合进化算法与混合进化子结构发现 85
4.1 混合进化算法设计 85
4.1.1 什么是混合进化算法 85
4.1.2 爬山算法、梯度下降法和模拟退火算法简介 86
4.1.3 为什么要混合 92
4.1.4 混合进化算法的分类 94
4.1.5 混合进化算法的理论模型 94
4.1.6 局部搜索算法的使用频率和使用强度 97
4.1.7 混合进化计算的发展现状 97
4.2 基于混合进化计算的子结构发现算法 98
4.2.1 染色体的表示 98
4.2.2 种群的初始化 101
4.2.3 适应值函数、选择和精英保留 101
4.2.4 变异 101
4.2.5 交叉 106
4.2.6 算法的伪码描述 109
4.3 实验结果与分析 111
4.3.1 HEASD与EPSD实验结果对比与分析 111
4.3.2 单标签扩展与Subdue扩展性能对比 112
4.3.3 混合算法的有效性验证 113
4.4 本章小结 115
参考文献 116
第5章 基于带状态回溯个体的混合进化子结构发现 120
5.1 子结构查找的单向性 121
5.2 可回溯的混合进化子结构发现算法 124
5.2.1 回溯法的基本原理和机制 124
5.2.2 HEASDBT基本思想 130
5.2.3 染色体的表示 133
5.2.4 种群的初始化 134
5.2.5 适应值、选择和精英保留 134
5.2.6 变异 134
5.2.7 交叉 136
5.2.8 及时去掉种群中没有潜力的个体和重新初始化 138
5.2.9 算法的伪码描述 140
5.3 实验结果与分析 142
5.3.1 HEASDBT与EPSD实验结果对比与分析 142
5.3.2 回溯的有效性验证 144
5.4 本章小结 145
参考文献 146
第6章 基于个体协同的混合进化子结构发现 147
6.1 子结构查找的瓶颈——实例丢失 148
6.2 带全部实例的混合进化子结构发现算法 151
6.2.1 染色体的表示 151
6.2.2 个体的评价 152
6.2.3 HEASDFI的其他组成部分 152
6.2.4 HEASDFI的实验结果与分析 152
6.3 基于个体协同的混合进化子结构发现算法 158
6.3.1 个体协同算子 158
6.3.2 一种新的多样性保持方案 165
6.3.3 算法的伪码表示 167
6.3.4 HEASDCI的实验结果与分析 167
6.4 本章小结 173
参考文献 174
第7章 应用研究 176
7.1 在信息与计算科学学科建设中的应用 176
7.1.1 问题的背景 176
7.1.2 数据的收集与表示 177
7.1.3 调整子结构评价方法以偏置查找 177
7.1.4 挖掘的结果及分析应用 178
7.2 在区域经济研究中的应用 179
7.2.1 引言 179
7.2.2 数据的收集与预处理 179
7.2.3 条件挖掘 183
7.2.4 挖掘的结果及分析 184
7.3 子结构发现在地震数据分析中的应用 185
7.3.1 地震数据库描述 185
7.3.2 地震数据的图表示 185
7.3.3 子结构发现过程及结果 187
7.3.4 判定地震的活动性 188
7.4 子结构发现在反恐中的应用 190
7.4.1 模拟数据集描述 191
7.4.2 学习有威胁的活动模式 191
7.4.3 学习有威胁组织的结构模式 193
7.4.4 学习有威胁组织的通信模式 195
7.5 本章小结 196
参考文献 196
附录一 实验的软硬件环境 198
附录二 实验图数据集 199