《一种有效的解图匹配问题的核方法研究 2》由会员分享，可在线阅读，更多相关《一种有效的解图匹配问题的核方法研究 2（4页珍藏版）》请在金锄头文库上搜索。
1、一种有效的解图匹配问题的核方法研究摘要：摘要：随着计算机技术与网络技术的高速发展，大量的数据充斥着我们周围的世界。面对这些复杂的海量数据，如何才能准确无误地对它们进行辨别与分析，这对于人们来说是一个非常具有挑战性的问题。在计算机领域，图是一种非常灵活的数据结构，对图等含有结构化信息数据的进行学习，是模式识别和机器学习领域的一种重要问题。本文主要研究了通过核方法来解决这些识别问题，并且实例化了两种特殊的解决图匹配的核方法。在此基础上，分析了其解决这类问题的算法复杂度。实验结果表明，本文所提出的方法是一种解决图匹配的非常有效技术。关键词：关键词：模式识别；图数据；图匹配；核方法1 引言模式识别伴随
2、着计算机技术和网络技术的快速发展，在许多领域得到了成功应用如数据挖掘、文献分类、财政、多媒体数据库的组织和检索、生物（比如根据人的物理特征，如人脸、指纹等识别人） 、医学（医学图像分析） 。其中图的顶点表示对象的各个组成部分，图的边表示各组成部分之间的关系，以这样的表达方式图就可以很容易地捕捉到物体的关系与结构信息。因此，基于图的描述是一种非常有效的表达方式。而当前模式识别领域中大多数工具却不能直接以图为其处理对象，这严重影响了基于图方法的发展。研究复杂模式分析和分类方法是有必要而且有意义的。其中基于核方法的学习方法是一种比较新的学习方法，它是从统计学习理论中发展出来的，并且有效地克服了传统模
3、式识别方法的局部极小化和不完全统计分析的缺点。现实世界中的数据往往具有数据量多、高维、动态、不完全（缺值） 、不确定（包含噪声）以及稀疏性等特性。对于从事模式识别、信号处理以及数据挖掘的研究者来说，核方法是一个强有力的分析工具。本文主要研究并实例化了一种核方法来模式识别中的图匹配问题，也就是通过在一个图中匹配另一个图中的某个相似的子结构来计算两个图的相似性的过程。2 核方法在近几年的机器学习和数据挖掘领域中，核方法成为一种非线性数据处理的新方法。它避免了神经网络和决策树中典型的局部极小化问题和过拟合问题。因此，它可以看成是经典线性方法的扩展，也可以认为它等效于使用非线性映射将样本变换到希尔伯特
4、特征空间，随后在该空间中实施线性特征抽取的方案。定义 2.1（图核）图 G1 和 G2 间的核函数 K (G1, G2)称为图核。映射 将原始空间中的图映射到高维甚至无穷维向量空间（特征空间）中去，使得K (G1, G2) = 由于映射 的选取，如 (G)的分量可以是两图中某一公共子路径的条数等，核 k :G 1GR 可以看成是两个图 G1 和 G2 间的相似性度量。核方法作为一种非线性方法可以解决这些问题。这将使得原来用于向量表示的标准算法也适合图，它可以把统计模式识别和结构模式识别有机地结合起来。3 图核一般常见的图核可分为三大类：基于路径的核方法如随机游走核、最短路径核；基于有限规模子图
5、的核方法；基于树模式的核方法如树模式图核、快速子树核、Weisfeiler-Lehman 图核等。本节重点深入研究快速子树核和 Weisfeiler-Lehman 图核及其在解决图匹配问题时的算法复杂程度。定义 3.1（快速子树核） ）图 G 和图 G之间快速子树核 vvvvhh ramonvvkGGk)() ,() ,(通过分析比较，两图之间的快速子树核的计算复杂度是，其中包括 n2 个节点对)4(2dhnO的比较和在范围之内，邻居节点的所有匹配次数。重复 h 次，其中 h 是一个多分类因子)4(dO而不是指数。以 k1 为起是点，经过 kh-1到 kh递归地计算子树核。定义 3. 2（We
6、isfeiler-Lehman 图核）图 G 和图 G之间的 WL 图核定义为,.,0),()(|)(),( ) ,()(VvVvhivsfvsfvsvsGGkiiiih WL其中 Si（v）为节点 v 在第 i 次迭代中的多分类标签集，f 是一个映射标签压缩函数，对于所有的，集合和集合是不相交的。S0（v）ji |)(VVvvsfi|)(VVvvsfj是在标签图 v 和非标签图中的初始标签并且。)()(00vsvsf4 实验论证4.1 数据准备实验数据集主要包括 MUTAG， NCI1，NCI109，ENZYMES，D&D。其中 MUTAG 是一个根据是否对革兰氏阴性菌鼠伤寒沙门氏菌有突变作
7、用的含有 188 个突变芳香和杂环硝基化合物。NCI1 和 NCI109 分别代表两组平衡的化学混合物数据集，它们来自于非小细胞肺癌细胞和卵巢癌细胞系。ENZYMES 是一个具有三层结构的蛋白质数据集，它包含从酶蛋白质数据库中获取的 600 个蛋白质酶。这种情况下的主要任务是正确给每个蛋白质添加一个 6 层结构的类。D&D 是一个包含有 1178 个蛋白质结构的数据集。每一个蛋白质可以看作一个图，图中的节点表示氨基酸，两个节点之间的边小于埃则可以用一条边连接。所有节点在数据集中是被标记的，预测的任务则是区分蛋白质结构中的酶与非酶。数据集中节点数、边数和度数的分布表 4.1 所示Data set
8、MUTAGNCI1NCI109ENZYMESD&DMaxi node281111111265748Average node17.9329.8729.6832.63284.32#labels737383824.2 仿真实验图是一种特殊的结构化数据表达形式，许多经典的学习算法不能用于图形数据的分析。因此，本实验主要围绕对图形数据的分析展开寻找适合图形数据后续分析的向量表示方法，以扩大传统学习算法在图形数据中的应用。实验硬件环境是 Intel Core 2 双核 CPU 2.2GH，内存2G。软件环境是美国 The Math Works 公司推出的 Matlab 软件，其中支持向量机 SVM 的实现
9、采用的是 Libsvm 工具箱。实验方法采用十倍交叉进行，其结果如下图所示图 4.2 快速子树核与 Weisfeiler-Lehman 图核的分类精度与运行时间5 结束语本文针对模式识别中的图匹配问题，主要研究了通过核方法来解决现实世界中的模式识别与分类问题。接着对两种图核的实例快速子树和与 Weisfeiler-Lehman 图核进行深入深入研究和分析外，着重探讨了其在解决大规模、复杂、高维数据上所具有的优越性。从实验结果可以看3出，这两种图核解决模式识别问题时具有的高效特点，且 Weisfeiler-Lehman 图核比快速子树具有更优的匹配精度和更少的运行时间。随着经济社会的高速发展，在
10、生物、数据挖掘领域越来越多的图数据（如分子结构、蛋白质交叉网络）变得越来越多。核方法将会受到更多学者们的青睐，希望今后能构造出分类精度更高效果更好的图核来解决其他领域中的分类和识别问题。参考文献: 1 N. Shervashidze, K. Borgwardt. Fast subtree kernels on graphs. In Neural Information Processing Systems, 2009.2 JOHN S T, NELLO C. Kernel methods for pattern analysisM. China machine press，2005.3 DUC
11、HENNE 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 neur
12、al network training. The Annals of Statistics, 1992, 20: 608-613.5 B.Moayer and K.Fu. A tree system approach for fingerprint pattern recognitionJ. Pattern Recognition, 1990,23(8):893-904.6 历小润. 模式识别核方法研究D.20097 Gurney K. Introduction to neural networks. UCL Press, London，1997.8 焦李成. 神经网络系统理论.西安电子科技大学出版社，1996.9 牟少敏. 核方法的研究及其应用.北京交通大学博士论文，2008. 10 郑永涛，刘玉树. 支持向量机解决多类问题研究J计算机工程与应用，2005.23
