Research On Graph Matching Algorithm Based On Edit Distance And Graph Embedding

In the field of pattern recognition,graph is increasingly paid widespread attention,which is a representation of structured information.The method of graph embedding builds a bridge for converting structural pattern recognition problem into the statistical pattern recognition problem using similarity measurement of vector space that combines the advantages of vector space based on the statistical learning theory.Edit distance of graphs is a non-similarity measure of an arbitrary structure and arbitrary lables between two graphs, however, the computation of graph edit distance based on the traditional tree search algorithm need exponential algorithm complexity. With the increasing of size of the training set,it is leading to an significant increasing in dimension embedding graph into a feature vector, a "curse of dimensionality" is occurred, and the feature vector contains a lot of redundancy and noise. Therefore, it is one of the hot and difficult problems of the current graph matching research area that designing an speedy algorithm for computing graph edit distance and prototype selection methods for reducing the dimension of graph embedding under the premise of ensuring the accuracy of pattern recognition.In this paper, the main research work is as follows for expanding the above two issues:(1) Designed a method of prototype selection,which is based on an edit distance metric and constructed a better distinguish prototype graph set between various types, finally experiments confirmed the effectiveness of the method, through studying and comparing the existing graph embedding method based on prototype selection.(2) Designed an improved prototype selection method using a process of equalization for each class within the class and other classes of training samples, experiments show that the method selected a prototype set for classification of apparent effect, as prototype selected by above strategy failed to investigate the interaction between the chosen prototype within a class and inter class.(3) Designed a cost function between graphs by using attribute calculation after using a fast edit distance computation algorithm,as the efficiency of the algorithm increases exponentially with the size of graph by analyzing edit distance calculation using traditional tree searching algorithm.The results of experimental studies show that this design of prototype selection method and edit distance calculation algorithm can effectively reduce the dimension of feature vector and improve the accuracy of pattern recognition based on graph embedding.