基于原型选择的图嵌入方法研究

刘永强

摘要：图嵌入方法为结构化模式识别问题转化为统计模式识别问题搭建了桥梁。而随着训练样本集规模的增加，为避免图嵌入时的“维度灾难”现象，对训练样本集进行原型选择是十分必要的。因此，本文提出一种基于类内和类间相均衡的原型选择方法，该方法通过对训练样本上的每一类的类内和其他类进行均衡化处理，分别选出每个类上依据均衡化程度排列的原型。实验表明，与未进行原型选择策略相比，本方法能较为有效地降低了图嵌入时的空间维度，且具有较高的分类精度。

关键词： 图匹配； 图嵌入； 图编辑距离； 原型选择

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2015）02-0172-04

Abstract：Graph embedding builds a bridge for converting structural pattern recognition problem into the statistical pattern recognition problem.However，with the increase of size of the training set，it is essential to select prototype for training set in order to avoid the “curse of dimensionality” phenomenon when embedding graph into vector space.Therefore，this paper proposes a method of prototype selection based on the balance between inner class and inter class due to a lack of prototype selection method，implemented on a set of training sample.This method carries out a equalization process for each class within a class and other classes on training samples，aims to select prototype arranged by the degree of equalization on each class.Experimental results show that this approach is more effective in reducing the spatial dimension when embedding graph，and also has higher classification accuracy， compared with non-prototype selection strategy.

Key words：graph matching； graph embedding； graph edit distance； prototype selection

图作为一种结构化的信息表示形式，其在生物信息学、交通运输、网络数据分析、汉字识别、图像识别和三维对象识别等诸多领域广泛存在，特别是在过去的数十年里，应用基于图的复杂对象[1]表示得到了飞速发展。目前，只要采用这种对象表示形式，模式识别问题就可以转换为图匹配问题[2]，即一个表示未知对象的输入图与数据库中的图进行比较，以匹配出最为相似的模板图。

近年来，各国研究者提出了大量的基于不同范式的图匹配方法[3]，有图矩阵的谱分解，人工神经网络的训练，持续优化算法和树搜索过程的优化等。然而，这些图匹配算法的缺陷在于拘泥于某一类图或者仅可应用到失真程度很小的数据上。后来Bunke等人提出的图编辑距离算法[4]解决了这些算法的不足，它是一种任意结构和任意标记图的非相似性度量，其受限于KNN分类和K-median聚类。图匹配问题现今已成为各国模式识别研究者关注的热点问题。在这个快速发展的研究领域中，核方法的引入[5]无疑给这个领域添入了新的活力。随之二者结合下的图核技术[6]出现，该技术揭示了图匹配和核机器之间的联系，并将图投射到点积空间上，其缺点在于核函数的选择成为影响最终匹配性能的关键。

而后出现的图嵌入技术[7]，该技术结合了统计学习理论上的向量空间优势，采用大量的非相似性进行图的度量，将图嵌入到一定维数的向量空间上，缺点是原型图的选择对向量空间上的分类的成功尤为重要。因此，需要构造适用于图的聚类算法，从图集中选择和构造有代表特征的原型图，以提高图匹配的精度。本文将以编辑距离度量为基础，结合类内聚合和类间分离的均衡策略构造出一种较为有效改善图嵌入性能的原型选择方法。

1 原型选择策略

原型选择旨在[8]剔除不相关或冗余的训练样本，从而达到减少训练样本个数，提高模型精确度，减少运行时间的目的。此外，选取出真正相关的特征简化了模型，使研究人员易于理解数据产生的过程。传统的各种原型选择策略的最大缺点[9]在于需要用户自定义嵌入的空间维度，需要频繁地在验证集上执行某一原型选择算法，以确定选取的合适原型数量。如，广为熟知的进化包装算法，其在验证集上对原型数量的优化是极为耗时的。因而，亟待出现一种能够自动地推理目标嵌入空间维度的原型选择方法。为达到这个目标，研究者们尝试了各种各样的原型削减方案。与启发式的原型选择策略相比，这类方法以一种算法化的过程定义了选取的原型数量。

本文针对原型选择问题，以编辑距离度量为基础，首先提出一种采用训练样本每一类内聚合和与其他类相远离原型选择方法，然后提出一种改进的基于训练样本类内和类间平衡的原型选择方法，该方法首先通过对训练样本上的每一类的类内和其他类上的进行均衡化处理，以选出依据均衡化程度排列的每个类内原型。

2 图编辑距离

为很好地表征图的结构信息，本文定义如下一种属性图来表述图的特征。

图编辑距离计算的难点[11]在于编辑代价函数[c（e）]的定义，这是由于对于不同含义两个图而言，一条编辑路径包括结点或边的插入、删除和替换，则需要为这三种不同操作定义不同的代价函数，而实际应用中很难依据已有条件去定义出合适的操作代价函数。一般来说，结点或边的插入和删除定义[c（e）>0]，结点或边的替换定义[c（e）=0]。

本文对于编辑路径的定义，采用向更少的结点或边数目的图中插入或替换结点或边进行，从而仅定义插入或替换操作的代价。而最短编辑距离的计算是十分耗时的，传统的树状搜索算法需要指数级运行时间，本文采用二部图匹配算法[12]计算最短编辑距离，将运行时间降低至多项式时间。最终，两个图的最短编辑距离为结点和边的最短编辑距离值之和。

3 原型选择过程

原型选择对于图嵌入架构至关重要[13]。原型选择是指从训练样本集中选取一个子集，使得构造出来的模型表征能力更好。为获得具有类区分的向量表示，选择的原型图不仅应当在整个训练样本图域上分布均匀，而且能够同时避免选择相似图造成的冗余。

本文采用最短编辑距离对训练集上的每一个类在类内进行聚合，用平均中心作为该小聚类中心，接着对每个类与其他类的距离进行度量，将取得最短距离的两个训练图作为该类与其他类之间的分界，最后取所有接近小聚类中心的训练图、未发生聚合的训练图和取分界的训练图的集合作为原型图集。如算法1所示。

鉴于上述策略选取的原型仅是对训练样本类内和类之间单独考察的结果，未能考量类内选取的原型对类之间的相互影响，为此本文引入一种综合类内和类之间选取原型相均衡的改进方法，该方法采用一种均衡因子对类内将选取的原型图和其他类的图进行考察，使得选取的原型图能在训练图集合上均匀分布。

本方法选取的每个原型均由均衡因子评价，产生的第一个原型靠近于训练样本的每一个类的中心上，后续产生的原型远离已选原型，避免了类内选择相似图造成的冗余，并使得选择的原型有更好的类间的区分性。利用上述策略在每个类上可产生依均衡化处理后排列的若干预选原型，在这每个类上的预选原型中选择一定数量的作为预选原型集。

本文改进方法以最短编辑距离作为训练图之间的非相似性度量，首先将经均衡化处理后的训练样本集的每个类内靠近类中心的图作为第一个原型，然后将经调整均衡化处理后的每个类内远离已选原型的图作为后续原型。假定[Win]是类内的均衡因子，[Wout]是类之间的均衡因子，[Win，Wout∈0，1]，[Win+Wout=1]，[n=1，…，T]，[Pn1：k-1=pn1，…，pnk-1]，[k=2，…，K]，[K]是每个类上选取的原型数量。

4 实验

实验使用平台：微软公司的VS 2010.net中的C++语言和台湾大学的林智仁等人开发的软件包LibSVM[16]。

实验使用数据：采用两个国际开放标准数据集，IAM库中的Fingerprint和Protein。其中，Fingerprint数据集是基于美国国家标准与技术研究院（National Institute of Standards and Technology，简称NIST）特别数据库4，由提取自指纹图像的3300个图构成，包含了拱形、尖拱形、左旋形、右旋形和漩涡形等5个类型的指纹数据，该数据集划分为三类，有大小为150个的训练集和验证集、3000个大小的测试集；Protein数据集构造于蛋白质银行（Protein Data Bank）数据库，其标记对应于源自BRENDA酶数据库，该库包含6个类型的蛋白质数据，即EC1、EC2、EC3、EC4、EC5和EC6，该数据集划分为三类，有大小分别为200个训练集、验证集和测试集将每组实验数据分类三类。

实验内容包括原型选择、参数优化和识别精度的比较三部分。原型选择是在训练图集上选取合适的样本作为图嵌入技术的原型。参数优化是在选好原型后，在训练集上利用网格搜索算法进行SVM的参数寻优，以利用最优参数对模型进行训练。比较识别精度是依据优化的模型，对验证样本进行识别精度统计，并与其他原型选择方法[17] [18] 的分类结果进行对比。实验结果如表1所示。

原型的选择方法包括原型的选择策略和原型数量的选择策略，这些策略不仅会对最终嵌入图的空间维数造成影响，还会影响到最终的模式识别性能。从表2可以看出，在Fingerprint和Protein两个数据集上，采用区分原型选择方法所产生的最终识别精度低于此两个数据集上不进行原型选择下的识别精度；此外，从表2可以看出，相比于不进行原型选择和采取的区分原型选择方法，在经过均衡化处理选择原型后，本方法在Fingerprint和Protein两个数据集上产生的识别精度要优于其他两种方法。

本文运用的图编辑距离计算算法，其时间复杂度为[On3]，区分原型选择算法2的时间复杂度为[OnCi×Cj]，均衡原型选择算法2的时间复杂度为[OnCi]，而采用SVM对实验数据的训练或测试的时间复杂度为[O（n3）]。据此，本文提出的改进方法的大部分时间消耗在原型选择上，即若类的样本数目越多，越耗时。

5 结论

由于在图嵌入方法中，若不进行适当的原型选择，随着训练样本规模不断地增加，最终导致嵌入图的向量空间中存在大量的冗余和噪声，这对后期的模式识别精度的分析与研究造成了干扰。据此，本文提出训练样本集类内和类间区分和均衡的原型选择方法，其具有如下特点：

（1）两种原型选择方法均以编辑距离作为图间的非相似性度量，选用最短编辑距离作为图间的非相似值。

（2）提出考虑训练样本类内和类间区分的原型选择方法，其以编辑距离度量为基础，采用训练样本每一类内聚合和与其他类相远离的策略，构造出较好区分各类的原型图。

（3）提出改进的考察类内和类间均衡的原型选择方法，其采用选取训练样本每一类的类中心图作为第一个原型，继而采用平衡因子选取满足类内和类间均衡性的图作为后续原型。

本文方法没有破坏图域上的结构信息，从训练图集中选择出了有代表特征的原型图，实际上，本文方法在时间执行效率上未做出优化，在接下来本文将探索进一步改进原型选择算法，并引入并行程序设计，以改善本文方法的分类效率。

参考文献：

[1] H.Bunke，K.Riesen.Recent advances in graph-based pattern recognition with applications in document analysis[J].Pattern Recognition，2011，5（32）：352-369.

[2] H.Bunke，S.Gunter，X.Jiang.Towards bridging the gap between statistical and structural pattern recognition：two new concepts in graph matching，in：International Conference on Advances in Pattern Recognition[J].Springer，2001，33（7）：811-825.

[3] D.Conte，P.Foggia，C.Sansone，M.Vento，Thirty years of graph matching in Pattern recognition[J].International Journal of Pattern Recognition and Artificial Intelligence，2004，18（3）：265-298.

[4] H.Bunke.On a relation between graph edit distance and maximum common Subgraph[J].Pattern Recognition Letters，1997（18）：689-694.

[5] Gartner，T..A survey of kernels for structured data[J].SIGKDD Explorations，2003，5：394-406.

[6] Gartner T，Flach P，Wrobel S.On graph kernels： Hardness results and effcient alternatives[J].B. Scholkopf and M. Warmuth （eds.），Proc.16th Annual Conf.on Learning Theory，2003（27）：462-478.

[7] K.Riesen，H.Bunke.Graph classification based on vector space embedding[J].International Journal of Pattern Recognition and Artificial Intelligence，2009（23）：1120-1136.

[8] Wendy Myrvold，William Kocay.Errors in graph embedding algorithms[J].Journal of Computer and System Sciences，2011（77）：430-438.

[9] Jaume Gibert，Ernest Valveny，Horst Bunke. Graph embedding in vector spaces by node attribute statistics[J]. Pattern Recognition，2012（45）：3072-3083.

[10] Michel Neuhaus，Horst Bunke. Edit distance-based kernel functions for structural pattern classification[J].Pattern Recognition，2006（39）：1852-1863.

[11] Michel Neuhaus，Horst Bunke. Automatic learning of cost functions for graph edit distance[J].Information Sciences，2007（177）：239-247.

[12] Kaspar Riesen，Horst Bunke.Approximate graph edit distance computation by means of bipartite graph matching[J].Image and Vision Computing，2009（27）：950-959.

[13] Ehsan Zare Borzeshi，Massimo Piccardi，Kaspar Riesen，Horst Bunke.Discriminative prototype selection methods for graph embedding[J].Pattern Recognition，2013（46）：1648-1657.

[14] 郭亚维，刘晓霞.文本分类中信息增益特征选择方法的研究[J].计算机工程与应用，2012（27）.

[15] 业宁，王迪，窦立君.信息熵与支持向量的关系[J].广西师范大学学报：自然科学版，2006（4）.

[16]C.Chang，C.Lin. LIBSVM ： A Library for Support Vector Machines. http：//www.csie.ntu.edu.tw/?cjlin/libsvm.