文档详情

the 频繁子图挖掘算法综述guide download.pdf

发布:2015-09-24约2.51万字共5页下载文档
文本预览下载声明
维普资讯 计算机科学 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是一个频繁子图。频繁子图挖掘就是要从输 等领域都大量使用到了图形数据,因此,对基于图的频繁子图 入数据库中找出所有频
显示全部
相似文档