搭建图形编辑距离与核机之间的桥梁

Michel Neuhaus University of Bern,

Switzerland

Horst Bunke University of Bern,

Switzerland

Bridging the Gap Between

Graph Edit Distance and

Kernel Machines

2007, 232pp.

Hardcover

ISBN 9789812708175

米歇尔•豪斯等编

在基于图形的结构模式识别中，其思路是将模式转变为图形，然后在图形域进行分析和模式识别——通常称为图形匹配。目前已经提出很多种图形匹配方法，图形编辑距离就是其中之一。它是通过将一个图形变换为另一个图形所需的变形数目来定义两个图形的相异度的，被认为是最灵活的容错图形匹配方法之一。

本书的重点是对于结构性错误具有高容错性的图形核函数。其基本思路是将图形编辑距离的概念移植到核函数中，从而将编辑基于距离的图形机器的灵活性与核机在模式识别方面的能力相结合。作者介绍了与编辑距离相关的各种新型的图形核，包括扩散核、卷积核和随机游动核。通过对一个半人工画线数据集和四个包括图片、显微图像、指纹、分子等的现实世界的数据集进行评估的实验，作者验证了一些核函数与支持向量机相结合可以在分类精度和运行时间两个方面明显地优于传统的编辑距离为基础的近邻分类。

本书共分为7章。1.导言；2.图形匹配，介绍了基本的符号和图形的定义以及图形匹配的应用；3.图形编辑距离，给出了精确的及模糊的图形编辑距离算法，简单讨论了以编辑距离为基础的近邻分类方法以及编辑距离在图形融合方面的应用；4.核机，给出了核函数，讨论了支持向量机、核主要组成分析以及Fisher差异分析；5.图核，是本书的主要部分，讨论了与编辑距离相关的图核；6.实验结果，给出了基于第五章理论的实验结果；7.总结与结论。

本书是《机器感知与人工智能》丛书的第68卷，是在第一作者Michel Neuhaus的博士论文基础上修改补充而成的。本书的第二作者Horst Bunke是第一作者在瑞士伯尔尼大学的博士生导师，Horst Bunke在德国Erlangen大学获得硕士和博士学位，1984年加入伯尔尼大学计算机科学系并任教授，1992 ~1996年任系主任，1997~1998年任理学院院长。Horst Bunke长期从事模式识别方面的研究，1998~2000年担任第一届国际模式识别协会（IAPR）副主席，还同时担任《International Journal of Pattern Recognition and Artificial Intelligence》的责任编辑，《Electronic Letters of Computer Vision and Image Analysis》的主编，《机器感知与人工智能》系列丛书的主编，以及Pattern Recognition的顾问编辑。

本书内容新颖，论述详尽。适合工业界和学术界从事结构模式识别和机器学习研究的人员及研究生阅读参考。

张文涛，助理研究员

（中国科学院半导体研究所）

Zhang wentao，Assistant Professor

（Institute of Semiconductors，CAS）