一种有效的解图匹配问题的核方法研究 2

一种有效的解图匹配问题的核方法研究

摘要：随着计算机技术与网络技术的高速发展，大量的数据充斥着我们周围的世界。面对这些复杂的海量数据，如何才能准确无误地对它们进行辨别与分析，这对于人们来说是一个非常具有挑战性的问题。在计算机领域，图是一种非常灵活的数据结构，对图等含有结构化信息数据的进行学习，是模式识别和机器学习领域的一种重要问题。本文主要研究了通过核方法来解决这些识别问题，并且实例化了两种特殊的解决图匹配的核方法。在此基础上，分析了其解决这类问题的算法复杂度。实验结果表明，本文所提出的方法是一种解决图匹配的非常有效技术。 关键词：模式识别；图数据；图匹配；核方法

1 引言

模式识别伴随着计算机技术和网络技术的快速发展，在许多领域得到了成功应用如数据挖掘、文献分类、财政、多媒体数据库的组织和检索、生物（比如根据人的物理特征，如人脸、指纹等识别人）、医学（医学图像分析）。其中图的顶点表示对象的各个组成部分，图的边表示各组成部分之间的关系，以这样的表达方式图就可以很容易地捕捉到物体的关系与结构信息。因此，基于图的描述是一种非常有效的表达方式。而当前模式识别领域中大多数工具却不能直接以图为其处理对象，这严重影响了基于图方法的发展。研究复杂模式分析和分类方法是有必要而且有意义的。其中基于核方法的学习方法是一种比较新的学习方法，它是从统计学习理论中发展出来的，并且有效地克服了传统模式识别方法的局部极小化和不完全统计分析的缺点。

现实世界中的数据往往具有数据量多、高维、动态、不完全（缺值）、不确定（包含噪声）以及稀疏性等特性。对于从事模式识别、信号处理以及数据挖掘的研究者来说，核方法是一个强有力的分析工具。本文主要研究并实例化了一种核方法来模式识别中的图匹配问题，也就是通过在一个图中匹配另一个图中的某个相似的子结构来计算两个图的相似性的过程。 2 核方法

在近几年的机器学习和数据挖掘领域中，核方法成为一种非线性数据处理的新方法。它避免了神经网络和决策树中典型的局部极小化问题和过拟合问题。因此，它可以看成是经典线性方法的扩展，也可以认为它等效于使用非线性映射将样本变换到希尔伯特特征空间，随后在该空间中实施线性特征抽取的方案。

定义2.1（图核）图G1和G2间的核函数K (G1, G2)称为图核。映射 将原始空间中的图映射到高维甚至无穷维向量空间（特征空间）中去，使得

K (G1, G2) = < (G1), (G2)>