|
用于计算图形编辑距离的二分图匹配
Bipartite Graph Matching for Computing the Edit Distance of Graphs |
|
| |
| 课程网址: |
http://videolectures.net/gbr07_riesen_bgm/
|
| 主讲教师: |
Kaspar Riesen
|
| 开课单位: |
瑞士伯尔尼大学
|
| 开课时间: |
2007-07-03
|
| 课程语种: |
英语
|
| 中文简介: |
在结构模式识别领域，图形构成了一种非常常见且有效的表示模式的方式。与字符串表示形成对比，图表允许我们描述所考虑的模式中的关系信息。图形表示的主要缺点之一是标准图形相似性度量的计算在所涉及的节点的数量中是指数的。因此，这种计算仅对于相当小的图是可行的。最灵活的容错图相似性度量之一基于图编辑距离。在本文中，我们提出了一种通过Munkres算法（有时称为匈牙利算法）基于二分图匹配有效地编辑编辑距离的方法。我们提出的算法在多项式时间内运行，但仅提供次优的编辑距离结果。其次优性的原因是在找到最佳节点分配的过程中不考虑隐含的边缘操作。在半人工和真实数据的实验中，我们证明了我们提出的方法相对于传统的基于树搜索的图编辑距离计算算法的加速。我们还表明，分类准确性几乎不受影响。
|
| 课程简介: |
In the field of structural pattern recognition graphs constitute a very common and powerful way of representing patterns. In contrast to string representations, graphs allow us to describe relational information in the patterns under consideration. One of the main drawbacks of graph representations is that the computation of standard graph similarity measures is exponential in the number of involved nodes. Hence, such computations are feasible for rather small graphs only. One of the most flexible error-tolerant graph similarity measures is based on graph edit distance. In this paper we propose an approach for the efficient compuation of edit distance based on bipartite graph matching by means of Munkres’ algorithm, sometimes referred to as the Hungarian algorithm. Our proposed algorithm runs in polynomial time, but provides only suboptimal edit distance results. The reason for its suboptimality is that implied edge operations are not considered during the process of finding the optimal node assignment. In experiments on semi-artificial and real data we demonstrate the speedup of our proposed method over a traditional tree search based algorithm for graph edit distance computation. Also we show that classification accuracy remains nearly unaffected.
|
| 关 键 词: |
结构模式; 图形; 字符串
|
| 课程来源: |
视频讲座网
|
| 最后编审: |
2019-04-15：cwx
|
| 阅读次数: |
133
|
|
图 书 馆