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

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

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

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