基于編輯距離圖嵌入的圖匹配算法研究.pdf

1、圖作為一種結(jié)構(gòu)化的信息表示形式，在模式識別領(lǐng)域中日益得到廣泛重視。圖嵌入方法結(jié)合統(tǒng)計(jì)學(xué)習(xí)理論中向量空間的優(yōu)勢，將圖嵌入至一定維數(shù)的向量空間，通過向量空間的相似性度量方法搭建了從結(jié)構(gòu)模式識別問題到統(tǒng)計(jì)模式識別問題的橋梁。圖的編輯距離是一種任意結(jié)構(gòu)和任意標(biāo)記圖之間的非相似性度量，而傳統(tǒng)的樹搜索算法計(jì)算圖編輯距離需要指數(shù)級的算法復(fù)雜度。隨著訓(xùn)練樣本集規(guī)模的增加，直接導(dǎo)致圖嵌入時的特征向量的維數(shù)大幅上升，產(chǎn)生“維度災(zāi)難”，且特征向量中包含了大量

2、冗余和噪聲，因此，在確保模式識別的精度前提下，快速的編輯距離計(jì)算算法和降低圖嵌入維度的原型選擇方法設(shè)計(jì)，是當(dāng)前圖匹配研究領(lǐng)域的研究熱點(diǎn)與難點(diǎn)問題之一。
　　本文針對上述兩方面的問題進(jìn)行展開，主要研究工作如下：
　　(1)通過研究與比較現(xiàn)有的基于原型選擇的圖嵌入方法，設(shè)計(jì)出一種以編輯距離度量為基礎(chǔ)，采用訓(xùn)練樣本每一類內(nèi)聚合和與其他類相遠(yuǎn)離的策略，構(gòu)造出較好區(qū)分各類的原型圖，并通過實(shí)驗(yàn)證實(shí)了該方法的效能。
　　(2)針對上

3、述策略選取的原型未能考察類內(nèi)選取的原型對類之間的相互影響，設(shè)計(jì)出一種改進(jìn)的采用訓(xùn)練樣本每一類的類內(nèi)和其他類的進(jìn)行均衡化處理的原型選擇方法，實(shí)驗(yàn)表明，該方法選出了對分類效果明顯的原型集。
　　(3)通過分析傳統(tǒng)的樹搜索編輯距離算法，它的效率隨著圖的規(guī)模呈指數(shù)級增加，采用了一種快速的編輯距離計(jì)算算法，設(shè)計(jì)出一種利用圖之間的屬性計(jì)算定義代價(jià)函數(shù)。
　　實(shí)驗(yàn)結(jié)果表明，本文設(shè)計(jì)的原型選擇方法和編輯距離算法可以有效地降低特征向量的維度，