摘要：随着计算机技术与网络技术的高速发展，大量的数据充斥着我们周围的世界。面对这些复杂的海量数据，如何才能准确无误地对它们进行辨别与分析，这对于人们来说是一个非常具有挑战性的问题。在计算机领域，图是一种非常灵活的数据结构，对图等含有结构化信息数据的进行学习，是模式识别和机器学习领域的一种重要问题。该文主要研究了通过核方法来解决这些识别问题，并且实例化了两种特殊的解决图匹配的核方法。在此基础上，分析了其解决这类问题的算法复杂度。实验结果表明，该文所提出的方法是一种解决图匹配的非常有效技术。 关键词：模式识别；图数据；图匹配；核方法 中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）20-4802-02 The Research of Graph Matching Based on Kernel Method LI Yin-hu （Department of Information and Control Engineering Institute， Xi’an University of Architecture and Technology， Xi’an， 710055， China） Abstract： With the development of computer technology and network technology，our word is full of large number of data. It is a challenge thing that how to recognize and analyse these data. In the field of computer， graph is a flexible data structure and Learning graph that structured data is becoming an important problem. This article focuses on kernel method to settle down the pattern recognition problem and put forward an efficient kernel method to solve pattern recognition problem. Experimental results demonstrate the effectiveness and feasibility of the proposed algorithm. Key words： pattern recognition； graph data； graph matching； kernel method 模式识别伴随着计算机技术和网络技术的快速发展，在许多领域得到了成功应用如数据挖掘、文献分类、财政、多媒体数据库的组织和检索、生物（比如根据人的物理特征，如人脸、指纹等识别人）、医学（医学图像分析）。其中图的顶点表示对象的各个组成部分，图的边表示各组成部分之间的关系，以这样的表达方式图就可以很容易地捕捉到物体的关系与结构信息。因此，基于图的描述是一种非常有效的表达方式。而当前模式识别领域中大多数工具却不能直接以图为其处理对象，这严重影响了基于图方法的发展。研究复杂模式分析和分类方法是有必要而且有意义的。其中基于核方法的学习方法是一种比较新的学习方法，它是从统计学习理论中发展出来的，并且有效地克服了传统模式识别方法的局部极小化和不完全统计分析的缺点。 现实世界中的数据往往具有数据量多、高维、动态、不完全（缺值）、不确定（包含噪声）以及稀疏性等特性。对于从事模式识别、信号处理以及数据挖掘的研究者来说，核方法是一个强有力的分析工具。该文主要研究并实例化了一种核方法来模式识别中的图匹配问题，也就是通过在一个图中匹配另一个图中的某个相似的子结构来计算两个图的相似性的过程。 1 核方法 在近几年的机器学习和数据挖掘领域中，核方法成为一种非线性数据处理的新方法。它避免了神经网络和决策树中典型的局部极小化问题和过拟合问题。因此，它可以看成是经典线性方法的扩展，也可以认为它等效于使用非线性映射将样本变换到希尔伯特特征空间，随后在该空间中实施线性特征抽取的方案。 定义1（图核）图G1和G2间的核函数K （G1， G2）称为图核。映射?将原始空间中的图映射到高维甚至无穷维向量空间（特征空间）中去，使得 K （G1， G2） = 由于映射?的选取，如 ? （G）的分量可以是两图中某一公共子路径的条数等，核k：G×G→R可以看成是两个图G1和G2间的相似性度量。 核方法作为一种非线性方法可以解决这些问题。这将使得原来用于向量表示的标准算法也适合图，它可以把统计模式识别和结构模式识别有机地结合起来。 2 图核 一般常见的图核可分为三大类：基于路径的核方法如随机游走核、最短路径核；基于有限规模子图的核方法；基于树模式的核方法如树模式图核、快速子树核、Weisfeiler-Lehman图核等。本节重点深入研究快速子树核和Weisfeiler-Lehman图核及其在解决图匹配问题时的算法复杂程度。 定义2 （快速子树核）图G和图G’之间快速子树核 通过分析比较，两图之间的快速子树核的计算复杂度是[O（n2h4d）]，其中包括n2个节点对的比较和在[O（4d）]范围之内，邻居节点的所有匹配次数。重复h次，其中h是一个多分类因子而不是指数。以k1为起是点，经过kh-1到kh递归地计算子树核。 定义3（Weisfeiler-Lehman图核）图G和图G’之间的WL图核定义为： 其中Si（v）为节点v在第i次迭代中的多分类标签集，f是一个映射标签压缩函数，对于所有的[i≠j]，集合[f（si（v））|v∈V?V']和集合[f（sj（v））|v∈V?V']是不相交的。S0（v）是在标签图v和非标签图中的初始标签并且[f（s0（v））=s0（v）]。 3 实验论证 3.1 数据准备 实验数据集主要包括MUTAG， NCI1，NCI109，ENZYMES，D&D。其中MUTAG是一个根据是否对革兰氏阴性菌鼠伤寒沙门氏菌有突变作用的含有188个突变芳香和杂环硝基化合物。NCI1和NCI109分别代表两组平衡的化学混合物数据集，它们来自于非小细胞肺癌细胞和卵巢癌细胞系。ENZYMES 是一个具有三层结构的蛋白质数据集，它包含从酶蛋白质数据库中获取的600个蛋白质酶。这种情况下的主要任务是正确给每个蛋白质添加一个6层结构的类。D&D是一个包含有1178个蛋白质结构的数据集。每一个蛋白质可以看做一个图，图中的节点表示氨基酸，两个节点之间的边小于埃则可以用一条边连接。所有节点在数据集中是被标记的，预测的任务则是区分蛋白质结构中的酶与非酶。 数据集中节点数、边数和度数的分布表1所示。 3.2 仿真实验 图是一种特殊的结构化数据表达形式，许多经典的学习算法不能用于图形数据的分析。因此，本实验主要围绕对图形数据的分析展开寻找适合图形数据后续分析的向量表示方法，以扩大传统学习算法在图形数据中的应用。实验硬件环境是Intel Core 2 双核CPU 2.2GH，内存2G。软件环境是美国The Math Works公司推出的Matlab软件，其中支持向量机SVM的实现采用的是Libsvm工具箱。实验方法采用十倍交叉进行，其结果如图1所示。 4 结束语 本文针对模式识别中的图匹配问题，主要研究了通过核方法来解决现实世界中的模式识别与分类问题。接着对两种图核的实例快速子树和与Weisfeiler-Lehman图核进行深入深入研究和分析外，着重探讨了其在解决大规模、复杂、高维数据上所具有的优越性。从实验结果可以看出，这两种图核解决模式识别问题时具有的高效特点，且Weisfeiler-Lehman图核比快速子树具有更优的匹配精度和更少的运行时间。随着经济社会的高速发展，在生物、数据挖掘领域越来越多的图数据（如分子结构、蛋白质交叉网络）变得越来越多。核方法将会受到更多学者们的青睐，希望今后能构造出分类精度更高效果更好的图核来解决其他领域中的分类和识别问题。 参考文献： [1] Shervashidze N， Borgwardt K. Fast subtree kernels on graphs. In Neural Information Processing Systems， 2009. [2] John S T， Nello C. Kernel methods for pattern analysis[M]. China machine press，2005. [3] Duchenne O， Bach F， Kweon I， Ponce J. A tensor-based algorithm for high-order graph matching [C].International Conference on Computer Vision and Pattern Recognition， 2006. [4] Jones L.K. A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training. The Annals of Statistics，1992（20）： 608-613.
摘要：随着计算机技术与网络技术的高速发展，大量的数据充斥着我们周围的世界。面对这些复杂的海量数据，如何才能准确无误地对它们进行辨别与分析，这对于人们来说是一个非常具有挑战性的问题。在计算机领域，图是一种非常灵活的数据结构，对图等含有结构化信息数据的进行学习，是模式识别和机器学习领域的一种重要问题。该文主要研究了通过核方法来解决这些识别问题，并且实例化了两种特殊的解决图匹配的核方法。在此基础上，分析了其解决这类问题的算法复杂度。实验结果表明，该文所提出的方法是一种解决图匹配的非常有效技术。 关键词：模式识别；图数据；图匹配；核方法 中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）20-4802-02 The Research of Graph Matching Based on Kernel Method LI Yin-hu （Department of Information and Control Engineering Institute， Xi’an University of Architecture and Technology， Xi’an， 710055， China） Abstract： With the development of computer technology and network technology，our word is full of large number of data. It is a challenge thing that how to recognize and analyse these data. In the field of computer， graph is a flexible data structure and Learning graph that structured data is becoming an important problem. This article focuses on kernel method to settle down the pattern recognition problem and put forward an efficient kernel method to solve pattern recognition problem. Experimental results demonstrate the effectiveness and feasibility of the proposed algorithm. Key words： pattern recognition； graph data； graph matching； kernel method 模式识别伴随着计算机技术和网络技术的快速发展，在许多领域得到了成功应用如数据挖掘、文献分类、财政、多媒体数据库的组织和检索、生物（比如根据人的物理特征，如人脸、指纹等识别人）、医学（医学图像分析）。其中图的顶点表示对象的各个组成部分，图的边表示各组成部分之间的关系，以这样的表达方式图就可以很容易地捕捉到物体的关系与结构信息。因此，基于图的描述是一种非常有效的表达方式。而当前模式识别领域中大多数工具却不能直接以图为其处理对象，这严重影响了基于图方法的发展。研究复杂模式分析和分类方法是有必要而且有意义的。其中基于核方法的学习方法是一种比较新的学习方法，它是从统计学习理论中发展出来的，并且有效地克服了传统模式识别方法的局部极小化和不完全统计分析的缺点。 现实世界中的数据往往具有数据量多、高维、动态、不完全（缺值）、不确定（包含噪声）以及稀疏性等特性。对于从事模式识别、信号处理以及数据挖掘的研究者来说，核方法是一个强有力的分析工具。该文主要研究并实例化了一种核方法来模式识别中的图匹配问题，也就是通过在一个图中匹配另一个图中的某个相似的子结构来计算两个图的相似性的过程。 1 核方法 在近几年的机器学习和数据挖掘领域中，核方法成为一种非线性数据处理的新方法。它避免了神经网络和决策树中典型的局部极小化问题和过拟合问题。因此，它可以看成是经典线性方法的扩展，也可以认为它等效于使用非线性映射将样本变换到希尔伯特特征空间，随后在该空间中实施线性特征抽取的方案。 定义1（图核）图G1和G2间的核函数K （G1， G2）称为图核。映射?将原始空间中的图映射到高维甚至无穷维向量空间（特征空间）中去，使得 K （G1， G2） = 由于映射?的选取，如 ? （G）的分量可以是两图中某一公共子路径的条数等，核k：G×G→R可以看成是两个图G1和G2间的相似性度量。 核方法作为一种非线性方法可以解决这些问题。这将使得原来用于向量表示的标准算法也适合图，它可以把统计模式识别和结构模式识别有机地结合起来。 2 图核 一般常见的图核可分为三大类：基于路径的核方法如随机游走核、最短路径核；基于有限规模子图的核方法；基于树模式的核方法如树模式图核、快速子树核、Weisfeiler-Lehman图核等。本节重点深入研究快速子树核和Weisfeiler-Lehman图核及其在解决图匹配问题时的算法复杂程度。 定义2 （快速子树核）图G和图G’之间快速子树核 通过分析比较，两图之间的快速子树核的计算复杂度是[O（n2h4d）]，其中包括n2个节点对的比较和在[O（4d）]范围之内，邻居节点的所有匹配次数。重复h次，其中h是一个多分类因子而不是指数。以k1为起是点，经过kh-1到kh递归地计算子树核。 定义3（Weisfeiler-Lehman图核）图G和图G’之间的WL图核定义为： 其中Si（v）为节点v在第i次迭代中的多分类标签集，f是一个映射标签压缩函数，对于所有的[i≠j]，集合[f（si（v））|v∈V?V']和集合[f（sj（v））|v∈V?V']是不相交的。S0（v）是在标签图v和非标签图中的初始标签并且[f（s0（v））=s0（v）]。 3 实验论证 3.1 数据准备 实验数据集主要包括MUTAG， NCI1，NCI109，ENZYMES，D&D。其中MUTAG是一个根据是否对革兰氏阴性菌鼠伤寒沙门氏菌有突变作用的含有188个突变芳香和杂环硝基化合物。NCI1和NCI109分别代表两组平衡的化学混合物数据集，它们来自于非小细胞肺癌细胞和卵巢癌细胞系。ENZYMES 是一个具有三层结构的蛋白质数据集，它包含从酶蛋白质数据库中获取的600个蛋白质酶。这种情况下的主要任务是正确给每个蛋白质添加一个6层结构的类。D&D是一个包含有1178个蛋白质结构的数据集。每一个蛋白质可以看做一个图，图中的节点表示氨基酸，两个节点之间的边小于埃则可以用一条边连接。所有节点在数据集中是被标记的，预测的任务则是区分蛋白质结构中的酶与非酶。 数据集中节点数、边数和度数的分布表1所示。 3.2 仿真实验 图是一种特殊的结构化数据表达形式，许多经典的学习算法不能用于图形数据的分析。因此，本实验主要围绕对图形数据的分析展开寻找适合图形数据后续分析的向量表示方法，以扩大传统学习算法在图形数据中的应用。实验硬件环境是Intel Core 2 双核CPU 2.2GH，内存2G。软件环境是美国The Math Works公司推出的Matlab软件，其中支持向量机SVM的实现采用的是Libsvm工具箱。实验方法采用十倍交叉进行，其结果如图1所示。 4 结束语 本文针对模式识别中的图匹配问题，主要研究了通过核方法来解决现实世界中的模式识别与分类问题。接着对两种图核的实例快速子树和与Weisfeiler-Lehman图核进行深入深入研究和分析外，着重探讨了其在解决大规模、复杂、高维数据上所具有的优越性。从实验结果可以看出，这两种图核解决模式识别问题时具有的高效特点，且Weisfeiler-Lehman图核比快速子树具有更优的匹配精度和更少的运行时间。随着经济社会的高速发展，在生物、数据挖掘领域越来越多的图数据（如分子结构、蛋白质交叉网络）变得越来越多。核方法将会受到更多学者们的青睐，希望今后能构造出分类精度更高效果更好的图核来解决其他领域中的分类和识别问题。 参考文献： [1] Shervashidze N， Borgwardt K. Fast subtree kernels on graphs. In Neural Information Processing Systems， 2009. [2] John S T， Nello C. Kernel methods for pattern analysis[M]. China machine press，2005. [3] Duchenne O， Bach F， Kweon I， Ponce J. A tensor-based algorithm for high-order graph matching [C].International Conference on Computer Vision and Pattern Recognition， 2006. [4] Jones L.K. A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training. The Annals of Statistics，1992（20）： 608-613.