资源描述：
《基于图论的频繁模式挖掘》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、计算机研究与发展ISSN100021239/CN1121777/TPJournalofComputerResearchandDevelopment42(2):230～235,2005基于图论的频繁模式挖掘汪卫周皓峰袁晴晴楼宇波施伯乐(复旦大学计算机与信息技术系上海200433)(weiwang1@fudan1edu1cn)MiningFrequentPatternsBasedonGraphTheoryWangWei,ZhouHaofeng,YuanQingqing,LouYubo,andSuiBaile(DepartmentofComputing&InformationTechnology,F
2、udanUniversity,Shanghai200433)AbstractMiningthefrequentpatternfromdatasetisoneofthekeysuccessstoriesofdataminingre2search1Currently,mostoftheeffortsarefocusedontheindependentdatasuchastheitemsinthemarket2ingbasket1However,theobjectsintherealworldoftenhavecloserelationshipwitheachother1Howtogainthefr
3、equentpatternfromtheserelationsistheobjectiveofthispaper1Graphsareusedtomodelthere2lations,andasimpletypeisselectedforanalysis1Combiningthegraph2theoryandalgorithmstogeneratefrequentpatterns,twonewalgorithmsareproposed1Thefirstalgorithm,namedAMGM,isbasedontheAproiriideaandmakesuseofmatrix1Fortheseco
4、ndalgorithm,anewstructureSFP2treeandanalgo2rithm,whichcanminethesesimplegraphsmoreefficiently,havebeenproposed1Theperformanceofthealgorithmsisevaluatedbyexperimentswithsyntheticdatasets1Theempiricalresultsshowthattheybothcandothejobwell,whileSFPperformsbetterthanAMGM1Suchalgorithmsarealsoappliedinmi
5、ningoftheauthoritativepagesandcommunitiesonWeb,whichisusefulforWebmining1Attheendofthepaper,thepotentialimprovementismentioned1KeywordsSFPtree;connectedfrequentgraph;datamining摘要对图数据频繁模式的挖掘是近年的研究热点1选择了惟一标号图进行分析,结合图论和频集生成的算法,提出了基于Aproiri思想、运用矩阵乘法的AMGM算法和基于SFP树的SFP算法1它们可有效地挖掘简单图中连通频繁子图1实验表明,这两个算法是十分有效
6、的,其中SFP算法的性能优于AMGM1该算法还被运用于发现Web上的权威页面和社团,具有良好的效果1关键词SFP树;频繁连通图;数据挖掘中图法分类号TP301如在化学数据中由于原子与原子之间存在化学键,1引言其数据构成一个图1Web网站的结构也是一种图的结构等1如何对图结构数据进行关联规则分析是一经过近10年的发展,关联规则的研究逐渐拓展项很有意义的工作1到Web挖掘、生物信息学、购物篮分析等众多实际本文从标号图的连通频繁子图的分析入手,提应用领域1在这些应用包含大量复杂类型的数据,出对包含结构信息的数据进行初步分析的方法,以收稿日期:2003-07-08;修回日期:2004-10-29基金项
7、目:国家自然科学基金项目(69933010,60303008);国家“八六三”高技术研究发展计划基金项目(2002AA4Z3430)汪卫等:基于图论的频繁模式挖掘231求将原先对单个项的频繁模式生成工作扩展到项对的领域上13基本概念本文在第2节介绍相关工作;在第3节引入标号图等基本概念,在此基础上提出两种算法:基于在详细介绍算法之前,首先给出有关的基本概Aproiri思想、利用矩阵乘法的AMGM算
