基于星形图频繁挖掘的研究

《基于星形图频繁挖掘的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要频繁项目挖掘算法已经用于解决各种有趣的问题。数据挖掘技术越来越多地应用到非传统领域，但也存在挖掘项目的方法不能应用于那些不适合限制条件要求的领域。在这些数据集的模拟对象中，一个方法是利用图来模拟数据库对象。在这一模型中，挖掘频繁结构的问题变成挖掘在完全的图集中频繁出现的子图的问题。本文提出一种称为S-FSG的算法，挖掘出在大型图数据库中频繁出现的所有连通星形子图。该算法采用且拓展FSG[2tl的方法来挖掘频繁星形子图。S-FSG的主要特征如下：(1)用图来表示，极小化了存储和计算；(2)通过一次增加一条边来增大

2、频繁子图，并有效地生成候选图：(3)使用规范标号图及图同构的简单算法，对较小的图很有效；(4)对候选生成元和计算进行最优化，给出对大型图数据库进行度量。在大量的模拟图中，我们根据实验评估S．FSG。对于具有实体和关系的适度地大的不同类型的问题，S-FSG能获得好的性能以及线性地度量数据库的大小。实验结果显示我们的算法与输入记录的次数成线性关系，而且能够在图的集合中合理地迅速地挖掘出频繁星形子图。关键词：数据挖掘；频繁项目；星形图AbstractThealgorithmsoffrequentitemsetdiscov

3、eryhavebeenusedtosolveVariousinterestingproblems．Althoughdataminingtechniquesagebeingincreasinglyappliedtonon-traditionaldomains，existingapproachesforfindingfrequentitemsetscannotbeusedastheycannotmeettherequirementofthesedomains．Awayofmodelingtheobjectsinthes

4、edatasets．ist0u∞agraphtomodelthedatabaseobje圮-ts．Withinthatmodel．theproblemoffindingfrequentpatternshasbecomethatofdiscoveringsubgraphathatoccurfrequentlyovertheentiresetofgraphs．Inthispaperwepresentanewalgorithm,namedS-FSGforfmdingallconnectedanddirectedstars

5、ubgraphsthatappearfrequentlyinalargegraphdatabase．Ouralgorithmfindsfrequentdire咖edstarsubgraphsusingthesamelevel—by—levelexpansionadoptedinFSC，m．Thekeyfeaturesors—FSGarethefollowings：(1)ItUSeSadirectedgraphicrepresentationwhichminimizesbothstorageandcomputatio

6、n；(2)Itincreasesthesizeoffrequentsubgraphsbyaddingoneedgeatatime，allowingtogeneratethecandidatesefficiently；(3)nrisessimplealgorithmsofcanonicallabelingandgraphisomorphismwhichworkefficientlyforsmallgraphs；(4)Rincorporatesvariousoptimizationsforcandidategenera

7、tionandcountingwhichallowit幻scaletolargegraphdatabases．WehaveexperimentallyevaluatedS-FSGonalargenumberofgraphs．Forproblemsinwhichamoderatelylargenumberofdifferenttypesofentitiesandrelationsexist,S-FSGisabletoachievegoodperformanceandtoscalelinearlywiththedata

8、basesize．Theempiricalresultsshowthatouralgorithmscaleslinearly、析tIlthenumberofinputtransactionsanditisabletodiscoverfrequemsubgraphsfromasetofgraphtransactionsreasonablyfast．Keywor