几种图匹配的核方法研究

摘要：

数据挖掘算法现面临挑战,这个挑战就是要处理日益增长的复杂对象.对于图数据,随机游走核是有力的容错图匹配方法.由于随机游走核的局部定义,它的适用性取决于潜在图表示的特性.另外通过定义图实例的核函数,数据挖掘算法的整个工具变得可用.迄今为止,已经提出了基于图的游走、子树和循环的图核.一般问题在于,这些核要么运算量大要么受限于他们的表达性.我们试着通过定义基于路径有表达性的图核克服这个问题.由于计算图的所有路径和最长路径是NP-难,我们建议基于最短路径图核.这些核在多项式时间内就可以计算,保持表现力并且仍然是正定的.

关键词：NP-难、图核、核方法、随机游走核、最短路径核、正定

分类号：TP391.4(计算技术、计算机技术)

在线出版日期：2013-06-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：1622-1625