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

维普资讯 计算机科学 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是一个频繁子图。频繁子图挖掘就是要从输 等领域都大量使用到了图形数据，因此，对基于图的频繁子图 入数据库中找出所有频