计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2014年
19期
118-122
,共5页
李智杰%李昌华%姚鹏%刘欣
李智傑%李昌華%姚鵬%劉訢
리지걸%리창화%요붕%류흔
图模式识别%非精确图匹配%空间句法%最短路径%图核
圖模式識彆%非精確圖匹配%空間句法%最短路徑%圖覈
도모식식별%비정학도필배%공간구법%최단로경%도핵
graph-based pattern recognition%inexact graph matching%space syntax%shortest path%graph kernel
针对图模式识别领域中现有图核方法对反映图本身拓扑结构的节点特征挖掘不够充分的问题,提出了基于空间句法和最短路径的图核。借鉴建筑学与城市规划学科中的空间句法理论构造分布于图节点上的拓扑特征的量化描述,基于此提出了可表示、计算,正定、适用范围较广的空间句法核和基于最短路径的空间句法核,进而借助支持向量机实现了非精确图匹配。不同于其他图核方法,该方法对图的拓扑特征表达能力强,通用性较好。实验结果表明,所设计的图核在分类精度方面相较于最短路径核有较显著的改善。
針對圖模式識彆領域中現有圖覈方法對反映圖本身拓撲結構的節點特徵挖掘不夠充分的問題,提齣瞭基于空間句法和最短路徑的圖覈。藉鑒建築學與城市規劃學科中的空間句法理論構造分佈于圖節點上的拓撲特徵的量化描述,基于此提齣瞭可錶示、計算,正定、適用範圍較廣的空間句法覈和基于最短路徑的空間句法覈,進而藉助支持嚮量機實現瞭非精確圖匹配。不同于其他圖覈方法,該方法對圖的拓撲特徵錶達能力彊,通用性較好。實驗結果錶明,所設計的圖覈在分類精度方麵相較于最短路徑覈有較顯著的改善。
침대도모식식별영역중현유도핵방법대반영도본신탁복결구적절점특정알굴불구충분적문제,제출료기우공간구법화최단로경적도핵。차감건축학여성시규화학과중적공간구법이론구조분포우도절점상적탁복특정적양화묘술,기우차제출료가표시、계산,정정、괄용범위교엄적공간구법핵화기우최단로경적공간구법핵,진이차조지지향량궤실현료비정학도필배。불동우기타도핵방법,해방법대도적탁복특정표체능력강,통용성교호。실험결과표명,소설계적도핵재분류정도방면상교우최단로경핵유교현저적개선。
In the field of graph-based pattern recognition, the existing graph kernels can’t mine the node features that reflect graph’s topology sufficiently. To solve this problem, the present study proposes new graph kernels based on space syntax and shortest path. This paper takes advantage of the space syntax theory in architecture and urban planning to make up quantitative description of the graph’s topological features and proposes the space syntax kernel and the space syntax kernel based on shortest path. These graph kernels are expressible, positive definite, computable and applicable to most graphs, and then are used to implement the inexact graph matching using SVM. Differ from other graph kernel methods, the pro-posed method can render the graph’s topology adequately and has a favorable universality. Experimental results show that such graph kernels can achieve superior results in classification compared to shortest path kernel.