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

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

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

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044（2015）02-0172-04

Abstract：Graphembeddingbuildsabridgeforconvertingstructuralpatternrecognitionproblemintothestatisticalpatternrecognitionproblem.However，withtheincreaseofsizeofthetrainingset，itisessentialtoselectprototypefortrainingsetinordertoavoidthe“curseofdimensionality”phenomenonwhenembeddinggraphintovectorspace.Therefore，thispaperproposesamethodofprototypeselectionbasedonthebalancebetweeninnerclassandinterclassduetoalackofprototypeselectionmethod，implementedonasetoftrainingsample.Thismethodcarriesoutaequalizationprocessforeachclasswithinaclassandotherclassesontrainingsamples，aimstoselectprototypearrangedbythedegreeofequalizationoneachclass.Experimentalresultsshowthatthisapproachismoreeffectiveinreducingthespatialdimensionwhenembeddinggraph，andalsohashigherclassificationaccuracy，comparedwithnon-prototypeselectionstrategy.

Keywords：graphmatching；graphembedding；grapheditdistance；prototypeselection

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

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

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

1原型選擇策略

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

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

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

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

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

3原型選擇過程

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

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

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

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

本文改進方法以最短編輯距離作為訓練圖之間的非相似性度量，首先將經(jīng)均衡化處理后的訓練樣本集的每個類內(nèi)靠近類中心的圖作為第一個原型，然后將經(jīng)調(diào)整均衡化處理后的每個類內(nèi)遠離已選原型的圖作為后續(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]是每個類上選取的原型數(shù)量。

4實驗

實驗使用平臺：微軟公司的VS中的C++語言和臺灣大學的林智仁等人開發(fā)的軟件包LibSVM[16]。

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

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

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

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

5結(jié)論

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

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

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

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

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

參考文獻：

[1]H.Bunke，K.Riesen.Recentadvancesingraph-basedpatternrecognitionwithapplicationsindocumentanalysis[J].PatternRecognition，2011，5（32）：352-369.

[2]H.Bunke，S.Gunter，X.Jiang.Towardsbridgingthegapbetweenstatisticalandstructuralpatternrecognition：twonewconceptsingraphmatching，in：InternationalConferenceonAdvancesinPatternRecognition[J].Springer，2001，33（7）：811-825.

[3]D.Conte，P.Foggia，C.Sansone，M.Vento，ThirtyyearsofgraphmatchinginPatternrecognition[J].InternationalJournalofPatternRecognitionandArtificialIntelligence，2004，18（3）：265-298.

[4]H.Bunke.OnarelationbetweengrapheditdistanceandmaximumcommonSubgraph[J].PatternRecognitionLetters，1997（18）：689-694.

[5]Gartner，T..Asurveyofkernelsforstructureddata[J].SIGKDDExplorations，2003，5：394-406.

[6]GartnerT，F(xiàn)lachP，WrobelS.Ongraphkernels：Hardnessresultsandeffcientalternatives[J].B.ScholkopfandM.Warmuth（eds.），Proc.16thAnnualConf.onLearningTheory，2003（27）：462-478.

[7]K.Riesen，H.Bunke.Graphclassificationbasedonvectorspaceembedding[J].InternationalJournalofPatternRecognitionandArtificialIntelligence，2009（23）：1120-1136.

[8]WendyMyrvold，WilliamKocay.Errorsingraphembeddingalgorithms[J].JournalofComputerandSystemSciences，2011（77）：430-438.

[9]JaumeGibert，ErnestValveny，HorstBunke.Graphembeddinginvectorspacesbynodeattributestatistics[J].PatternRecognition，2012（45）：3072-3083.

[10]MichelNeuhaus，HorstBunke.Editdistance-basedkernelfunctionsforstructuralpatterncla