基于原型選擇的圖嵌入方法研究

劉永強(qiáng)

摘要：圖嵌入方法為結(jié)構(gòu)化模式識(shí)別問題轉(zhuǎn)化為統(tǒng)計(jì)模式識(shí)別問題搭建了橋梁。而隨著訓(xùn)練樣本集規(guī)模的增加，為避免圖嵌入時(shí)的“維度災(zāi)難”現(xiàn)象，對(duì)訓(xùn)練樣本集進(jìn)行原型選擇是十分必要的。因此，本文提出一種基于類內(nèi)和類間相均衡的原型選擇方法，該方法通過對(duì)訓(xùn)練樣本上的每一類的類內(nèi)和其他類進(jìn)行均衡化處理，分別選出每個(gè)類上依據(jù)均衡化程度排列的原型。實(shí)驗(yàn)表明，與未進(jìn)行原型選擇策略相比，本方法能較為有效地降低了圖嵌入時(shí)的空間維度，且具有較高的分類精度。

關(guān)鍵詞： 圖匹配； 圖嵌入； 圖編輯距離； 原型選擇

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

圖作為一種結(jié)構(gòu)化的信息表示形式，其在生物信息學(xué)、交通運(yùn)輸、網(wǎng)絡(luò)數(shù)據(jù)分析、漢字識(shí)別、圖像識(shí)別和三維對(duì)象識(shí)別等諸多領(lǐng)域廣泛存在，特別是在過去的數(shù)十年里，應(yīng)用基于圖的復(fù)雜對(duì)象[1]表示得到了飛速發(fā)展。目前，只要采用這種對(duì)象表示形式，模式識(shí)別問題就可以轉(zhuǎn)換為圖匹配問題[2]，即一個(gè)表示未知對(duì)象的輸入圖與數(shù)據(jù)庫(kù)中的圖進(jìn)行比較，以匹配出最為相似的模板圖。

近年來(lái)，各國(guó)研究者提出了大量的基于不同范式的圖匹配方法[3]，有圖矩陣的譜分解，人工神經(jīng)網(wǎng)絡(luò)的訓(xùn)練，持續(xù)優(yōu)化算法和樹搜索過程的優(yōu)化等。然而，這些圖匹配算法的缺陷在于拘泥于某一類圖或者僅可應(yīng)用到失真程度很小的數(shù)據(jù)上。后來(lái)Bunke等人提出的圖編輯距離算法[4]解決了這些算法的不足，它是一種任意結(jié)構(gòu)和任意標(biāo)記圖的非相似性度量，其受限于KNN分類和K-median聚類。圖匹配問題現(xiàn)今已成為各國(guó)模式識(shí)別研究者關(guān)注的熱點(diǎn)問題。在這個(gè)快速發(fā)展的研究領(lǐng)域中，核方法的引入[5]無(wú)疑給這個(gè)領(lǐng)域添入了新的活力。隨之二者結(jié)合下的圖核技術(shù)[6]出現(xiàn)，該技術(shù)揭示了圖匹配和核機(jī)器之間的聯(lián)系，并將圖投射到點(diǎn)積空間上，其缺點(diǎn)在于核函數(shù)的選擇成為影響最終匹配性能的關(guān)鍵。

而后出現(xiàn)的圖嵌入技術(shù)[7]，該技術(shù)結(jié)合了統(tǒng)計(jì)學(xué)習(xí)理論上的向量空間優(yōu)勢(shì)，采用大量的非相似性進(jìn)行圖的度量，將圖嵌入到一定維數(shù)的向量空間上，缺點(diǎn)是原型圖的選擇對(duì)向量空間上的分類的成功尤為重要。因此，需要構(gòu)造適用于圖的聚類算法，從圖集中選擇和構(gòu)造有代表特征的原型圖，以提高圖匹配的精度。本文將以編輯距離度量為基礎(chǔ)，結(jié)合類內(nèi)聚合和類間分離的均衡策略構(gòu)造出一種較為有效改善圖嵌入性能的原型選擇方法。

1 原型選擇策略

原型選擇旨在[8]剔除不相關(guān)或冗余的訓(xùn)練樣本，從而達(dá)到減少訓(xùn)練樣本個(gè)數(shù)，提高模型精確度，減少運(yùn)行時(shí)間的目的。此外，選取出真正相關(guān)的特征簡(jiǎn)化了模型，使研究人員易于理解數(shù)據(jù)產(chǎn)生的過程。傳統(tǒng)的各種原型選擇策略的最大缺點(diǎn)[9]在于需要用戶自定義嵌入的空間維度，需要頻繁地在驗(yàn)證集上執(zhí)行某一原型選擇算法，以確定選取的合適原型數(shù)量。如，廣為熟知的進(jìn)化包裝算法，其在驗(yàn)證集上對(duì)原型數(shù)量的優(yōu)化是極為耗時(shí)的。因而，亟待出現(xiàn)一種能夠自動(dòng)地推理目標(biāo)嵌入空間維度的原型選擇方法。為達(dá)到這個(gè)目標(biāo)，研究者們嘗試了各種各樣的原型削減方案。與啟發(fā)式的原型選擇策略相比，這類方法以一種算法化的過程定義了選取的原型數(shù)量。

本文針對(duì)原型選擇問題，以編輯距離度量為基礎(chǔ)，首先提出一種采用訓(xùn)練樣本每一類內(nèi)聚合和與其他類相遠(yuǎn)離原型選擇方法，然后提出一種改進(jìn)的基于訓(xùn)練樣本類內(nèi)和類間平衡的原型選擇方法，該方法首先通過對(duì)訓(xùn)練樣本上的每一類的類內(nèi)和其他類上的進(jìn)行均衡化處理，以選出依據(jù)均衡化程度排列的每個(gè)類內(nèi)原型。

2 圖編輯距離

為很好地表征圖的結(jié)構(gòu)信息，本文定義如下一種屬性圖來(lái)表述圖的特征。

圖編輯距離計(jì)算的難點(diǎn)[11]在于編輯代價(jià)函數(shù)[c（e）]的定義，這是由于對(duì)于不同含義兩個(gè)圖而言，一條編輯路徑包括結(jié)點(diǎn)或邊的插入、刪除和替換，則需要為這三種不同操作定義不同的代價(jià)函數(shù)，而實(shí)際應(yīng)用中很難依據(jù)已有條件去定義出合適的操作代價(jià)函數(shù)。一般來(lái)說，結(jié)點(diǎn)或邊的插入和刪除定義[c（e）>0]，結(jié)點(diǎn)或邊的替換定義[c（e）=0]。

本文對(duì)于編輯路徑的定義，采用向更少的結(jié)點(diǎn)或邊數(shù)目的圖中插入或替換結(jié)點(diǎn)或邊進(jìn)行，從而僅定義插入或替換操作的代價(jià)。而最短編輯距離的計(jì)算是十分耗時(shí)的，傳統(tǒng)的樹狀搜索算法需要指數(shù)級(jí)運(yùn)行時(shí)間，本文采用二部圖匹配算法[12]計(jì)算最短編輯距離，將運(yùn)行時(shí)間降低至多項(xiàng)式時(shí)間。最終，兩個(gè)圖的最短編輯距離為結(jié)點(diǎn)和邊的最短編輯距離值之和。

3 原型選擇過程

原型選擇對(duì)于圖嵌入架構(gòu)至關(guān)重要[13]。原型選擇是指從訓(xùn)練樣本集中選取一個(gè)子集，使得構(gòu)造出來(lái)的模型表征能力更好。為獲得具有類區(qū)分的向量表示，選擇的原型圖不僅應(yīng)當(dāng)在整個(gè)訓(xùn)練樣本圖域上分布均勻，而且能夠同時(shí)避免選擇相似圖造成的冗余。

本文采用最短編輯距離對(duì)訓(xùn)練集上的每一個(gè)類在類內(nèi)進(jìn)行聚合，用平均中心作為該小聚類中心，接著對(duì)每個(gè)類與其他類的距離進(jìn)行度量，將取得最短距離的兩個(gè)訓(xùn)練圖作為該類與其他類之間的分界，最后取所有接近小聚類中心的訓(xùn)練圖、未發(fā)生聚合的訓(xùn)練圖和取分界的訓(xùn)練圖的集合作為原型圖集。如算法1所示。

鑒于上述策略選取的原型僅是對(duì)訓(xùn)練樣本類內(nèi)和類之間單獨(dú)考察的結(jié)果，未能考量類內(nèi)選取的原型對(duì)類之間的相互影響，為此本文引入一種綜合類內(nèi)和類之間選取原型相均衡的改進(jìn)方法，該方法采用一種均衡因子對(duì)類內(nèi)將選取的原型圖和其他類的圖進(jìn)行考察，使得選取的原型圖能在訓(xùn)練圖集合上均勻分布。

本方法選取的每個(gè)原型均由均衡因子評(píng)價(jià)，產(chǎn)生的第一個(gè)原型靠近于訓(xùn)練樣本的每一個(gè)類的中心上，后續(xù)產(chǎn)生的原型遠(yuǎn)離已選原型，避免了類內(nèi)選擇相似圖造成的冗余，并使得選擇的原型有更好的類間的區(qū)分性。利用上述策略在每個(gè)類上可產(chǎn)生依均衡化處理后排列的若干預(yù)選原型，在這每個(gè)類上的預(yù)選原型中選擇一定數(shù)量的作為預(yù)選原型集。

本文改進(jìn)方法以最短編輯距離作為訓(xùn)練圖之間的非相似性度量，首先將經(jīng)均衡化處理后的訓(xùn)練樣本集的每個(gè)類內(nèi)靠近類中心的圖作為第一個(gè)原型，然后將經(jīng)調(diào)整均衡化處理后的每個(gè)類內(nèi)遠(yuǎn)離已選原型的圖作為后續(xù)原型。假定[Win]是類內(nèi)的均衡因子，[Wout]是類之間的均衡因子，[Win，Wout∈0，1]，[Win+Wout=1]，[n=1，…，T]，[Pn1：k-1=pn1，…，pnk-1]，[k=2，…，K]，[K]是每個(gè)類上選取的原型數(shù)量。

4 實(shí)驗(yàn)

實(shí)驗(yàn)使用平臺(tái)：微軟公司的VS 2010.net中的C++語(yǔ)言和臺(tái)灣大學(xué)的林智仁等人開發(fā)的軟件包LibSVM[16]。

實(shí)驗(yàn)使用數(shù)據(jù)：采用兩個(gè)國(guó)際開放標(biāo)準(zhǔn)數(shù)據(jù)集，IAM庫(kù)中的Fingerprint和Protein。其中，F(xiàn)ingerprint數(shù)據(jù)集是基于美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院（National Institute of Standards and Technology，簡(jiǎn)稱NIST）特別數(shù)據(jù)庫(kù)4，由提取自指紋圖像的3300個(gè)圖構(gòu)成，包含了拱形、尖拱形、左旋形、右旋形和漩渦形等5個(gè)類型的指紋數(shù)據(jù)，該數(shù)據(jù)集劃分為三類，有大小為150個(gè)的訓(xùn)練集和驗(yàn)證集、3000個(gè)大小的測(cè)試集；Protein數(shù)據(jù)集構(gòu)造于蛋白質(zhì)銀行（Protein Data Bank）數(shù)據(jù)庫(kù)，其標(biāo)記對(duì)應(yīng)于源自BRENDA酶數(shù)據(jù)庫(kù)，該庫(kù)包含6個(gè)類型的蛋白質(zhì)數(shù)據(jù)，即EC1、EC2、EC3、EC4、EC5和EC6，該數(shù)據(jù)集劃分為三類，有大小分別為200個(gè)訓(xùn)練集、驗(yàn)證集和測(cè)試集將每組實(shí)驗(yàn)數(shù)據(jù)分類三類。

實(shí)驗(yàn)內(nèi)容包括原型選擇、參數(shù)優(yōu)化和識(shí)別精度的比較三部分。原型選擇是在訓(xùn)練圖集上選取合適的樣本作為圖嵌入技術(shù)的原型。參數(shù)優(yōu)化是在選好原型后，在訓(xùn)練集上利用網(wǎng)格搜索算法進(jìn)行SVM的參數(shù)尋優(yōu)，以利用最優(yōu)參數(shù)對(duì)模型進(jìn)行訓(xùn)練。比較識(shí)別精度是依據(jù)優(yōu)化的模型，對(duì)驗(yàn)證樣本進(jìn)行識(shí)別精度統(tǒng)計(jì)，并與其他原型選擇方法[17] [18] 的分類結(jié)果進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果如表1所示。

原型的選擇方法包括原型的選擇策略和原型數(shù)量的選擇策略，這些策略不僅會(huì)對(duì)最終嵌入圖的空間維數(shù)造成影響，還會(huì)影響到最終的模式識(shí)別性能。從表2可以看出，在Fingerprint和Protein兩個(gè)數(shù)據(jù)集上，采用區(qū)分原型選擇方法所產(chǎn)生的最終識(shí)別精度低于此兩個(gè)數(shù)據(jù)集上不進(jìn)行原型選擇下的識(shí)別精度；此外，從表2可以看出，相比于不進(jìn)行原型選擇和采取的區(qū)分原型選擇方法，在經(jīng)過均衡化處理選擇原型后，本方法在Fingerprint和Protein兩個(gè)數(shù)據(jù)集上產(chǎn)生的識(shí)別精度要優(yōu)于其他兩種方法。

本文運(yùn)用的圖編輯距離計(jì)算算法，其時(shí)間復(fù)雜度為[On3]，區(qū)分原型選擇算法2的時(shí)間復(fù)雜度為[OnCi×Cj]，均衡原型選擇算法2的時(shí)間復(fù)雜度為[OnCi]，而采用SVM對(duì)實(shí)驗(yàn)數(shù)據(jù)的訓(xùn)練或測(cè)試的時(shí)間復(fù)雜度為[O（n3）]。據(jù)此，本文提出的改進(jìn)方法的大部分時(shí)間消耗在原型選擇上，即若類的樣本數(shù)目越多，越耗時(shí)。

5 結(jié)論

由于在圖嵌入方法中，若不進(jìn)行適當(dāng)?shù)脑瓦x擇，隨著訓(xùn)練樣本規(guī)模不斷地增加，最終導(dǎo)致嵌入圖的向量空間中存在大量的冗余和噪聲，這對(duì)后期的模式識(shí)別精度的分析與研究造成了干擾。據(jù)此，本文提出訓(xùn)練樣本集類內(nèi)和類間區(qū)分和均衡的原型選擇方法，其具有如下特點(diǎn)：

（1）兩種原型選擇方法均以編輯距離作為圖間的非相似性度量，選用最短編輯距離作為圖間的非相似值。

（2）提出考慮訓(xùn)練樣本類內(nèi)和類間區(qū)分的原型選擇方法，其以編輯距離度量為基礎(chǔ)，采用訓(xùn)練樣本每一類內(nèi)聚合和與其他類相遠(yuǎn)離的策略，構(gòu)造出較好區(qū)分各類的原型圖。

（3）提出改進(jìn)的考察類內(nèi)和類間均衡的原型選擇方法，其采用選取訓(xùn)練樣本每一類的類中心圖作為第一個(gè)原型，繼而采用平衡因子選取滿足類內(nèi)和類間均衡性的圖作為后續(xù)原型。

本文方法沒有破壞圖域上的結(jié)構(gòu)信息，從訓(xùn)練圖集中選擇出了有代表特征的原型圖，實(shí)際上，本文方法在時(shí)間執(zhí)行效率上未做出優(yōu)化，在接下來(lái)本文將探索進(jìn)一步改進(jìn)原型選擇算法，并引入并行程序設(shè)計(jì)，以改善本文方法的分類效率。

參考文獻(xiàn)：

[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，F(xiàn)lach 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].計(jì)算機(jī)工程與應(yīng)用，2012（27）.

[15] 業(yè)寧，王迪，竇立君.信息熵與支持向量的關(guān)系[J].廣西師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2006（4）.

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