基于粒子群算法的聚类及图聚类研究

论文摘要

核方法是解决非线性模式分析问题的一种有效途径,其核心思想是:首先,通过某种非线性映射将原始数据扩展到合适的高维特征空间;然后,在这个新的空间中分析和处理模式。相对于使用通用非线性学习器直接在原始数据上进行学习的方法,核方法具有明显的优势:首先,核方法的非线性映射可以集成问题相关的先验知识。再者,核方法可以更好地保证泛化性能。还有,在核方法中,计算复杂度与高维特征空间的维数无关,减少了计算的复杂度。因此,核方法能够很好地对图数据结构进行学习。图学习的主要内容包括:频繁子图的挖掘、图聚类、图分类等。其中,频繁子图的挖掘可以作为图聚类和图分类的基础。同时,本文对粒子群算法进行了一定的研究,提出了一种自适应种群的离散粒子群算法,并将其和传统的聚类算法相结合,形成了自适应种群的离散粒子群聚类算法。通过对粒子群拓扑结构进行研究与分析,结合Gbest模型和Lbest模型各自的优点。文中在粒子群算法搜索的前期采用Lbest模型,随着搜索的进行逐渐形成一种多簇结构,在簇内实行全连接的拓扑结构,而簇之间采用环形拓扑结构。不仅保证了粒子群算法的全局搜索能力,而且又很好地控制了粒子群算法的局部搜索能力。实验验证了该算法在聚类方面有着很好的效果。另外,本文提取图中重要程度较高的子结构--主干图（BackBone Graph）进行分析。而后,利用随机路径核函数来定义主干图核函数,并对不同阶的主干图给予不同的权重。最后,通过自适应种群的离散粒子群算法来对核相似矩阵进行学习。实验结果表明,文中方法能够很好地对图结构数据进行学习。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景和课题意义
• 1.2 本文的主要工作
• 1.3 本文的组织结构
• 2 粒子群算法原理及分析
• 2.1 粒子群优化算法
• 2.1.1 基本的粒子群算法
• 2.1.2 标准的粒子群算法
• 2.2 粒子群算法分析
• 2.2.1 粒子群算法收敛性
• 2.2.2 粒子轨迹分析
• 2.2.3 粒子群算法复杂度
• 2.3 与其他算法比较
• 2.3.1 粒子群算法与遗传算法
• 2.3.2 粒子群算法与蚂蚁算法比较
• 2.4 粒子群算法的应用
• 3 图数据挖掘
• 3.1 图的基本定义
• 3.1.1 图与带标签的图
• 3.1.2 度、路径、连通图
• 3.2 图数据挖掘的内容
• 3.2.1 频繁子图挖掘
• 3.2.2 图关系学习
• 3.3 图匹配
• 3.3.1 基于图编辑距离的图匹配
• 3.3.2 基于拓扑描述子的图匹配
• 3.3.3 基于核方法的图匹配
• 4 自适应种群的离散粒子群聚类算法
• 4.1 研究背景
• 4.2 自适应种群的离散粒子群聚类算法
• 4.2.1 聚类分析
• 4.2.2 适应值函数和粒子构造
• 4.2.3 自适应种群的离散粒子群聚类算法
• 4.3 实验
• 4.3.1 实验数据
• 4.3.2 实验设置
• 4.3.3 实验结果
• 4.4 结束
• 5 用于图学习的主干图核方法
• 5.1 研究背景
• 5.1.1 图核函数
• 5.1.2 核矩阵学习
• 5.2 主干图核方法
• 5.2.1 相关定义
• 5.2.2 主干图核函数
• 5.3 用于核矩阵学习的离散粒子群算法
• 5.4 实验
• 5.4.1 实验数据
• 5.4.2 实验设置
• 5.4.3 实验结果
• 结论
• 参考文献
• 致谢
• 攻读硕士学位期间发表的论文