搭建圖形編輯距離與核機(jī)之間的橋梁

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

米歇爾?豪斯等編

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

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

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

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

本書(shū)內(nèi)容新穎，論述詳盡。適合工業(yè)界和學(xué)術(shù)界從事結(jié)構(gòu)模式識(shí)別和機(jī)器學(xué)習(xí)研究的人員及研究生閱讀參考。

張文濤，助理研究員

（中國(guó)科學(xué)院半導(dǎo)體研究所）

Zhang wentao，Assistant Professor

（Institute of Semiconductors，CAS）