从图数据库中挖掘频繁跳跃模式

被引：9

作者：

刘勇

李建中

高宏

机构：

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

来源：

软件学报 | 2010年 / 21卷 / 10期

关键词：

数据挖掘; 图挖掘; 图数据库; 频繁子图; 跳跃模式;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

很多频繁子图挖掘算法已被提出.然而,这些算法产生的频繁子图数量太多而不能被用户有效地利用.为此,提出了一个新的研究问题:挖掘图数据库中的频繁跳跃模式.挖掘频繁跳跃模式既可以大幅度地减少输出模式的数量,又能使有意义的图模式保留在挖掘结果中.此外,跳跃模式还具有抗噪声干扰能力强等优点.然而,由于跳跃模式不具有反单调性质,挖掘它们非常具有挑战性.通过研究跳跃模式自身的特性,提出了两种新的裁剪技术:基于内扩展的裁剪和基于外扩展的裁剪.在此基础上又给出了一种高效的挖掘算法GraphJP(an algorithm for mining jump patterns from graph databases).另外,还严格证明了裁剪技术和算法GraphJP的正确性.实验结果表明,所提出的裁剪技术能够有效地裁剪图模式搜索空间,算法GraphJP是高效、可扩展的.

引用

页码：2477 / 2493

页数：17

共 14 条

[11]

An apriori based algorithm for mining frequent substructures from graph data. Inokuchi A,Washio T,Motoda H. Proceedings of the 2000 Europe Conference on Principle of Data Mining and Knowledge Discovery(PKDD’00) . 2000

[12]

Summarizing graph patterns. Liu Y,Li J,Gao H. Proc.of the IEEE Int’l Conf.on Data Mining . 2008

[13]

Scalable mining of large disk-base graph databases. Wang C,Wang W,Pei J,Zhu Y,Shi B. Proc. 2004 ACM SIGKDD int. conf. knowledge discovery in databases (KDD‘04) . 2004

[14]

gSpan:Graph-based substructure pattern mining. Yan X,Han J. Proceedings of the IEEE International Conference on Data Mining . 2002

← 1 2 →