基于混合进化的子结构发现

出版时间：2009-1  出版社：国防工业出版社  作者：常新功  页数：204  
Tag标签：无  

内容概要

本书介绍了使用进化算法进行图学习的一些概念、思想、方法和技术。全书共分7章，其中前3章为基础篇，介绍了图学习的基本概念、基本思想、发生发展历程、应用领域和典型的图学习算法Subdue系统，另外还介绍了进化算法的基本理论、基本思想、典型范式、一般框架、各个组成要素、典型实例和一个基于进化规划的子结构发现算法EPSD。第4章～第6章为算法设计篇，分别介绍了基于混合进化、基于回溯机制、基于带全部实例的个体表示和基于个体协同的四种混合进化子结构发现算法。第7章为应用篇，介绍了子结构发现算法在学科建设、区域经济研究、地震数据分析和反恐数据分析中的四个典型应用。附录中还给出了本书用到的多个图数据集。    本书可供所有从事机器学习和数据挖掘的专业技术人员阅读和使用，也可供管理科学和系统工程专业的读者学习参考。

书籍目录

第1章  绪论  1.1  图学习的目的  1.2  图学习的应用领域  1.3  子结构发现的研究现状    1.3.1  子结构发现所属的研究领域    1.3.2  子结构发现的发展历程  1.4  本书内容安排  1.5  本章小结  参考文献第2章  子结构发现与Subdue系统  2.1  图的基本概念    2.1.1  图与带标签的图    2.1.2  度、路径、连通图    2.1.3  图同构、子图同构  2.2  图匹配    2.2.1  精确图匹配    2.2.2  不精确图匹配  2.3  子结构发现问题描述    2.3.1  子结构及实例    2.3.2  MDL与子结构的评价    2.3.3  子结构的扩展    2.3.4  子结构发现的作用和意义  2.4  Subdue系统    2.4.1  Subdue系统简介    2.4.2  Subdue子结构发现算法的伪码描述    2.4.3  图数据的组织与表示    2.4.4  图概念学习    2.4.5  图聚类  2.5  本章小结  参考文献第3章  进化算法与EPSD进化子结构发现算法  3.1  什么是进化算法    3.1.1  最优化问题    3.1.2  从进化论和遗传变异理论到进化算法    3.1.3  进化算法的特点  3.2  进化算法的四种典型范式和一般框架    3.2.1  遗传算法    3.2.2  进化策略    3.2.3  进化规划    3.2.4  遗传规划    3.2.5  进化算法的一般框架  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章  混合进化算法与混合进化子结构发现  4.1  混合进化算法设计    4.1.1  什么是混合进化算法    4.1.2  爬山算法、梯度下降法和模拟退火算法简介    4.1.3  为什么要混合    4.1.4  混合进化算法的分类    4.1.5  混合进化算法的理论模型    4.1.6  局部搜索算法的使用频率和使用强度    4.1.7  混合进化计算的发展现状  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章  基于带状态回溯个体的混合进化子结构发现  5.1  子结构查找的单向性  5.2  可回溯的混合进化子结构发现算法    5.2.1  回溯法的基本原理和机制    5.2.2  HEASDBT基本思想    5.2.3  染色体的表示    5.2.4  种群的初始化    5.2.5  适应值、选择和精英保留    5.2.6  变异    5.2.7  交叉    5.2.8  及时去掉种群中没有潜力的个体和重新初始化    5.2.9  算法的伪码描述  5.3  实验结果与分析    5.3.1  HEASDBT与EPSD实验结果对比与分析    5.3.2  回溯的有效性验证  5.4  本章小结  参考文献第6章  基于个体协同的混合进化子结构发现  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章  应用研究  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  子结构发现在地震数据分析中的应用    7.3.1  地震数据库描述    7.3.2  地震数据的图表示    7.3.3  子结构发现过程及结果    7.3.4  判定地震的活动性  7.4  子结构发现在反恐中的应用    7.4.1  模拟数据集描述    7.4.2  学习有威胁的活动模式    7.4.3  学习有威胁组织的结构模式    7.4.4  学习有威胁组织的通信模式  7.5  本章小结  参考文献附录一  实验的软硬件环境附录二  实验图数据集

章节摘录

　　第1章 绪论　　本书关注两方面的内容：图学习和进化算法。图是建模复杂结构和复杂交互的利器，然而由于图表示的灵活性，从图数据中进行学习或数据挖掘是困难的：一方面图学习的假设空间（子图结构集合）非常巨大，另一方面在图数据中学习时常常要面对图同构、子图同构等目前还没有多项式时间算法的问题。为此将擅长解决复杂问题的进化算法引入图学习，以期发现更优的解。本章l·I节介绍图学习的重要性和复杂性；1.2节简要介绍图学习的典型应用领域；l.3节详细阐述本书的研究目标、图学习中的核心任务——子结构发现的研究现状；1.4节为全书的内容安排；l.5节对本章进行小结。　　1.1　图学习的目的　　科学技术的飞速发展使当今社会呈现出信息化、网络化和全球化的特点，随之而来的海量数据对人类现有的数据处理能力提出了新的挑战，“数据爆炸”、“数据的丰富，知识的匮乏’’正是对这一现象的真实写照。然而更为复杂的是，除了海量性之外，数据本身往往还呈现出结构化的特点，即数据内部或数据之间存在着形形色色、错综复杂、常常较数据本身更能反映问题实质的联系，这又进一步加大了数据的自动处理和分析的难度，同时也使得许多数据挖掘结果不能尽如人意。“数据的丰富和复杂，高质量知识的匮乏”呼唤更为强有力的数据挖掘工具。近年来，从结构数据中进行挖掘和学习引起了众多研究者的关注，并逐渐成为数据挖掘和机器学习领域的一个主流分支。在第五届图挖掘和图学习国际研讨会（MLG，07）的主页上这样写到：“数据挖掘和机器学习正在经历一场结构化革命。数十年来人们一直关注独立同分布数据，然而现在许多研究者开始或正在研究建立在更为复杂的数据表示形式上的问题……”