一种有效的解图匹配问题的核方法研究
摘要：随着计算机技术与网络技术的高速发展，大量的数据充斥着我们周围的世界。面对这些复杂的海量数据，如何才能准确无误地对它们进行辨别与分析，这对于人们来说是一个非常具有挑战性的问题。在计算机领域，图是一种非常灵活的数据结构，对图等含有结构化信息数据的进行学习，是模式识别和机器学习领域的一种重要问题。本文主要研究了通过核方法来解决这些识别问题，并且实例化了两种特殊的解决图匹配的核方法。在此基础上，分析了其解决这类问题的算法复杂度。实验结果表明，本文所提出的方法是一种解决图匹配的非常有效技术。
关键词：模式识别；图数据；图匹配；核方法
1 引言
模式识别伴随着计算机技术和网络技术的快速发展，在许多领域得到了成功应用如数据挖掘、文献分类、财政、多媒体数据库的组织和检索、生物（比如根据人的物理特征，如人脸、指纹等识别人）、医学（医学图像分析）。其中图的顶点表示对象的各个组成部分，图的边表示各组成部分之间的关系，以这样的表达方式图就可以很容易地捕捉到物体的关系与结构信息。因此，基于图的描述是一种非常有效的表达方式。而当前模式识别领域中大多数工具却不能直接以图为其处理对象，这严重影响了基于图方法的发展。研究复杂模式分析和分类方法是有必要而且有意义的。其中基于核方法的学习方法是一种比较新的学习方法，它是从统计学习理论中发展出来的，并且有效地克服了传统模式识别方法的局部极小化和不完全统计分析的缺点。
现实世界中的数据往往具有数据量多、高维、动态、不完全（缺值）、不确定（包含噪声）以及稀疏性等特性。对于从事模式识别、信号处理以及数据挖掘的研究者来说，核方法是一个强有力的分析工具。本文主要研究并实例化了一种核方法来模式识别中的图匹配问题，也就是通过在一个图中匹配另一个图中的某个相似的子结构来计算两个图的相似性的过程。
2 核方法
在近几年的机器学习和数据挖掘领域中，核方法成为一种非线性数据处理的新方法。它避免了神经网络和决策树中典型的局部极小化问题和过拟合问题。因此，它可以看成是经典线性方法的扩展，也可以认为它等效于使用非线性映射将样本变换到希尔伯特特征空间，随后在该空间中实施线性特征抽取的方案。
定义2.1（图核）图G1和G2间的核函数K (G1, G2)称为图核。映射ϕ将原始空间中的图映射到高维甚至无穷维向量空间（特征空间）中去，使得
K (G1, G2) = <ϕ (G1), ϕ (G2)>
由于映射 ϕ 的选取，如 ϕ(G)的分量可以是两图中某一公共子路径的条数等，核k :G × G→R 可以看成是两个图G1和G2间的相似性度量。
核方法作为一种非线性方法可以解决这些问题。这将使得原来用于向量表示的标准算法也适合图，它可以把统计模式识别和结构模式识别有机地结合起来。
3 图核
一般常见的图核可分为三大类：基于路径的核方法如随机游走核、最短路径核；基于有限规模子图的核方法；基于树模式的核方法如树模式图核、快速子树核、Weisfeiler-Lehman 图核等。本节重点深入研究快速子树核和Weisfeiler-Lehman 图核及其在解决图匹配问题时的算法复杂程度。
定义3.1（快速子树核））图G 和图G ’之间快速子树核
∑∑∈∈=v v v v h h ramon v v k G G k '
')()',()',(
通过分析比较，两图之间的快速子树核的计算复杂度是)4(2d h n
O ，其中包括n2个节点对的比较和在)4(d O 范围之内，邻居节点的所有匹配次数。重复h 次，其中h 是一个多分类因子而不是指数。以k1为起是点，经过k h-1到k h 递归地计算子树核。
定义3. 2（Weisfeiler-Lehman 图核）图G 和图G ’之间的WL 图核定义为 }',},,...,0{)),'(())((|))'(),(({)',()(V v V v h i v s f v s f v s v s G G k i i i i h WL ∈∈==
其中Si （v ）为节点v 在第i 次迭代中的多分类标签集，f 是一个映射标签压缩函数，对于所有的j i ≠，集合{}'|))((V V v v s f i ⋃∈和集合{}
'|))((V V v v s f j ⋃∈是不相交的。S 0（v ）是在标签图v 和非标签图中的初始标签并且)())((00v s v s f =。
4 实验论证
4.1数据准备 实验数据集主要包括MUTAG ， NCI1，NCI109，ENZYMES ，D&D 。其中MUTAG 是一个根据是否对革兰氏阴性菌鼠伤寒沙门氏菌有突变作用的含有188个突变芳香和杂环硝基化合物。NCI1和NCI109分别代表两组平衡的化学混合物数据集，它们来自于非小细胞肺癌细胞和卵巢癌细胞系。ENZYMES 是一个具有三层结构的蛋白质数据集，它包含从酶蛋白质数据库中获取的600个蛋白质酶。这种情况下的主要任务是正确给每个蛋白质添加一个6层结
3 构的类。D&D是一个包含有1178个蛋白质结构的数据集。每一个蛋白质可以看作一个图，图中的节点表示氨基酸，两个节点之间的边小于埃则可以用一条边连接。所有节点在数据集中是被标记的，预测的任务则是区分蛋白质结构中的酶与非酶。
数据集中节点数、边数和度数的分布表4.1所示
4.2仿真实验
图是一种特殊的结构化数据表达形式，许多经典的学习算法不能用于图形数据的分析。因此，本实验主要围绕对图形数据的分析展开寻找适合图形数据后续分析的向量表示方法，以扩大传统学习算法在图形数据中的应用。实验硬件环境是Intel Core 2 双核CPU 2.2GH，内存2G。软件环境是美国The Math Works公司推出的Matlab软件，其中支持向量机SVM的实现采用的是Libsvm工具箱。实验方法采用十倍交叉进行，其结果如下图所示
图4.2 快速子树核与Weisfeiler-Lehman图核的分类精度与运行时间
5 结束语
本文针对模式识别中的图匹配问题，主要研究了通过核方法来解决现实世界中的模式识别与分类问题。接着对两种图核的实例快速子树和与Weisfeiler-Lehman图核进行深入深入研
