文档介绍：山西财经大学
硕士学位论文
基于粒子群算法的聚类及图聚类研究
姓名:沈亮
申请学位级别:硕士
专业:计算机应用技术
指导教师:常新功
2011-02-13
摘要
核方法是解决非线性模式分析问题的一种有效途径,其核心思想是:首先,
通过某种非线性映射将原始数据扩展到合适的高维特征空间;然后,在这个新
的空间中分析和处理模式。相对于使用通用非线性学习器直接在原始数据上进
行学习的方法,核方法具有明显的优势:首先,核方法的非线性映射可以集成
问题相关的先验知识。再者,核方法可以更好地保证泛化性能。还有,在核方
法中,计算复杂度与高维特征空间的维数无关,减少了计算的复杂度。因此,
核方法能够很好地对图数据结构进行学习。图学习的主要内容包括:频繁子图
的挖掘、图聚类、图分类等。其中,频繁子图的挖掘可以作为图聚类和图分类
的基础。
同时,本文对粒子群算法进行了一定的研究,提出了一种自适应种群的离
散粒子群算法,并将其和传统的聚类算法相结合,形成了自适应种群的离散粒
子群聚类算法。通过对粒子群拓扑结构进行研究与分析,结合 Gbest 模型和 Lbest
模型各自的优点。文中在粒子群算法搜索的前期采用 Lbest 模型,随着搜索的
进行逐渐形成一种多簇结构,在簇内实行全连接的拓扑结构,而簇之间采用环
形拓扑结构。不仅保证了粒子群算法的全局搜索能力,而且又很好地控制了粒
子群算法的局部搜索能力。实验验证了该算法在聚类方面有着很好的效果。
另外,本文提取图中重要程度较高的子结构--主干图(BackBone Graph)进行
分析。而后,利用随机路径核函数来定义主干图核函数,并对不同阶的主干图
给予不同的权重。最后,通过自适应种群的离散粒子群算法来对核相似矩阵进
3-
行学习。实验结果表明,文中方法能够很好地对图结构数据进行学习。
关键字:自适应粒子群算法主干图核图数据挖掘
4-
Abstract
Kernel method is an effective way to solve nonlinear mode analysis problem, its core ideas are:
first, expanding the original data to the appropriate high-dimensional feature space through some
nonlinear mapping; Then, analizing and processing mode in this new space. Compaired with using
generic nonlinear directly on the original data ,nuclear method has obvious advantages : firstly,
nonlinear mapping of kernel method can integration problems which related to the prior knowledge.
Moreover, kernel method can better ensure generalization capability. Also, as putational
complexity and high-dimensional feature space dimension is irrelevant in the kernel method, it
reduces plexity. Therefore, kernel method can be well study the figure data
structure. The Figure learning mainly includes: frequent sub-graph mining, graph relationship
learning, etc. Among them, the frequent sub -graph mining can be as graph clustering and figure
classification foundation.
Meanwhile, this paper proposes a particle swarm algorithm that could adapt population based
on a lot bined with the traditional clustering algorithms, it forms discre