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

米歇爾?豪斯等編

在基于圖形的結構模式識別中，其思路是將模式轉變?yōu)閳D形，然后在圖形域進行分析和模式識別——通常稱為圖形匹配。目前已經(jīng)提出很多種圖形匹配方法，圖形編輯距離就是其中之一。它是通過將一個圖形變換為另一個圖形所需的變形數(shù)目來定義兩個圖形的相異度的，被認為是最靈活的容錯圖形匹配方法之一。

本書的重點是對于結構性錯誤具有高容錯性的圖形核函數(shù)。其基本思路是將圖形編輯距離的概念移植到核函數(shù)中，從而將編輯基于距離的圖形機器的靈活性與核機在模式識別方面的能力相結合。作者介紹了與編輯距離相關的各種新型的圖形核，包括擴散核、卷積核和隨機游動核。通過對一個半人工畫線數(shù)據(jù)集和四個包括圖片、顯微圖像、指紋、分子等的現(xiàn)實世界的數(shù)據(jù)集進行評估的實驗，作者驗證了一些核函數(shù)與支持向量機相結合可以在分類精度和運行時間兩個方面明顯地優(yōu)于傳統(tǒng)的編輯距離為基礎的近鄰分類。

本書共分為7章。1.導言；2.圖形匹配，介紹了基本的符號和圖形的定義以及圖形匹配的應用；3.圖形編輯距離，給出了精確的及模糊的圖形編輯距離算法，簡單討論了以編輯距離為基礎的近鄰分類方法以及編輯距離在圖形融合方面的應用；4.核機，給出了核函數(shù)，討論了支持向量機、核主要組成分析以及Fisher差異分析；5.圖核，是本書的主要部分，討論了與編輯距離相關的圖核；6.實驗結果，給出了基于第五章理論的實驗結果；7.總結與結論。

本書是《機器感知與人工智能》叢書的第68卷，是在第一作者Michel Neuhaus的博士論文基礎上修改補充而成的。本書的第二作者Horst Bunke是第一作者在瑞士伯爾尼大學的博士生導師，Horst Bunke在德國Erlangen大學獲得碩士和博士學位，1984年加入伯爾尼大學計算機科學系并任教授，1992 ~1996年任系主任，1997~1998年任理學院院長。Horst Bunke長期從事模式識別方面的研究，1998~2000年擔任第一屆國際模式識別協(xié)會（IAPR）副主席，還同時擔任《International Journal of Pattern Recognition and Artificial Intelligence》的責任編輯，《Electronic Letters of Computer Vision and Image Analysis》的主編，《機器感知與人工智能》系列叢書的主編，以及Pattern Recognition的顧問編輯。

本書內(nèi)容新穎，論述詳盡。適合工業(yè)界和學術界從事結構模式識別和機器學習研究的人員及研究生閱讀參考。

張文濤，助理研究員

（中國科學院半導體研究所）

Zhang wentao，Assistant Professor

（Institute of Semiconductors，CAS）