the 频繁子图挖掘算法综述guide download.pdf
文本预览下载声明
维普资讯
计算机科学 2005Voi.32NQ.10
频繁子图挖掘算法综述*)
王艳辉 吴 斌 王 柏
(北京邮电大学计算机科学与技术学院通信软件工程中心 北京 100876)
摘 要 本文介绍了基于图的频繁子图挖掘算法的研究情况,提 出频繁子图挖掘算法的分类方法,对一些经典的算法
进行了分析和评价,归纳出频繁子图挖掘的一般步骤 以及实现这些步骤的方法,展望 了频繁子图挖掘的未来研究方
向 。
关键词 关联规则,标记图,Canonicalcode,子图同构
SurveyofFrequentSubgraphM ining
W A G『YamHui WU Bin W A G『Bai
(TelecommunicationsSoftwareEngineeringGroup,SchoolofComputerScienceandTechnology,Bei}ingUniversity
ofPostsandTelecommunications,BeJjing100876)
Ah吐瞰 t Thispaperprovidesasurveyofthestudyinfrequentsubgraphmining。bringsforwardaclassifiactionoffre—
quentsubgraphmining ,reviewsandanalysessometypicalalgorithms,concludethegeneralstepsonfmdingfrequent
subgraphsingraphdatabaseandthemethodswhichCna beappliedtOtheocrresponding steps,viewssomefuturedirec—
tionsinfrqeuentsubgraphnlining.
Keywor~ Associationrule,Labeledgraph,CanonicM code,Subgraphisomorphjsm
标记集合L(E(G))={/b(eh)IVeh∈E(G)),则有标记图可以
1 引言
表示为G=(V(G),E(G),L((G)),L(E(G)))。
关联规则算法首先是 由Agrawal等人于1993年提出的, 输入数据库 GD= {G1, ,…,G),其中G一( (Gf),E
是基于客户交易数据库,用来解决项集之间关联问题的,后来 (G;i),L( (G )),L(E(G)))。
诸多研究人员对关联规则的挖掘问题进行了大量研究,除了 频繁子图挖掘 (frequentsuturephMining):假定输入数
应用于非结构型数据 (non-structure)以外,还研究和提出了 据库GD={GfIi一0,1,…,,1),给定一个最小支持度阈值
许多应用于半结构型(semi-structure)数据和结构型(strut— min—sup,规定:如果子图g与G 子图同构,则o(g,Gf)一1,
ture)数据的算法。 否则o(g,G)一0, g,GD)一 (g,Gf),如果 艿(g,GD)≥
图形数据广泛存在于我们的生活中,如化学、生物、国防 mm’ sup,则 g是一个频繁子图。频繁子图挖掘就是要从输
等领域都大量使用到了图形数据,因此,对基于图的频繁子图 入数据库中找出所有频
显示全部