基于联合意义度量的Top-K图模式挖掘

被引：3

作者：

刘勇

高宏

李建中

机构：

[1] 哈尔滨工业大学计算机科学与技术学院

来源：

计算机学报 | 2010年 / 33卷 / 02期

关键词：

图挖掘; 图数据库; 频繁子图; 代表模式; 联合熵; 信息增益;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

提出了一个新的研究问题:如何挖掘Top-K图模式,联合起来使某个意义度量最大化.利用信息论的概念,给出了两个具体问题的定义MES和MIGS,并证明它们是NP-难.提出了两个高效算法Greedy-TopK和Clus-ter-TopK.Greedy-TopK先产生频繁子图,然后按增量贪心方式选择K个图模式.Cluster-TopK先挖掘频繁子图的一个代表模式集合,然后从代表模式中按增量贪心方式选择K个图模式.当意义度量满足submodular性质时,Greedy-TopK能提供近似比保证.Cluster-TopK没有近似比保证,但比Greedy-TopK更高效.实验结果显示,在结果可用性方面,文中提出的Top-K挖掘优于传统的Top-K挖掘.Cluster-TopK比Greedy-TopK快至少一个数量级.而且,在质量和可用性方面,Cluster-TopK的挖掘结果非常类似于Greedy-TopK的挖掘结果.

引用

页码：215 / 230

页数：16