| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 基于联合意义度量的Top-K图模式挖掘 |
| 作者 | 刘勇 高宏 李建中 |
| 作者单位 | (哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001) |
| 发表年份 | 2010 |
| 发表月份 | 2期(215—230) |
| 文章摘要 | 摘要 提出了一个新的研究问题:如何挖掘Top-K图模式，联合起来使某个意义度量最大化.利用信息论的概念，给出了两个具体问题的定义MES和MIGS，并证明它们是NP-难.提出了两个高效算法Greedy-TopK和Cluster-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的挖掘结果. 关键词 图挖掘；图数据库；频繁子图；代表模式；联合熵；信息增益 中图法分类号 TP311 DOI号: 10.3724/SP.J.1016.2010.00215 |