资源描述：
《一种高效频繁子图挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.18,No.10,October2007,pp.2469−2480http://www.jos.org.cnDOI:10.1360/jos182469Tel/Fax:+86-10-62562563©2007byJournalofSoftware.Allrightsreserved.∗一种高效频繁子图挖掘算法+李先通,李建中,高宏(哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001)
2、AnEfficientFrequentSubgraphMiningAlgorithm+LIXian-Tong,LIJian-Zhong,GAOHong(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001,China)+Correspondingauthor:Phn:+86-451-86415827,E-mail:lijzh@hit.edu.cn,http://db.hit.edu.cnLiXT,LiJZ,GaoH.Aneff
3、icientfrequentsubgraphminingalgorithm.JournalofSoftware,2007,18(10):2469−2480.http://www.jos.org.cn/1000-9825/18/2469.htmAbstract:Withthesuccessfuldevelopmentoffrequentitemsetandfrequentsequencemining,thetechnologyofdataminingisnaturaltoextenditswaytosolvetheproblem
4、ofstructuralpatternmining—Frequentsubgraphmining.Frequentpatternsaremeaningfulinmanyapplicationssuchaschemistry,biology,computernetworks,andWorld-WideWeb.ThispaperproposesanewalgorithmGraphGenforminingfrequentsubgraphs.GraphGenreducestheminingcomplexitythroughtheext
5、ensionoffrequentsubtree.Forthebestalgorithmavailable,the3ncomplexityisO(n·2),nisthenumberoffrequentedgesinagraphdataset.ThecomplexityofGraphGenis⎛2.5⎞nnO⎜2⋅⎟,whichisimprovedO(n⋅logn)timesthanthebestone.Experimentalresultsprovethistheoretical⎜logn⎟⎝⎠analysis.Keywords
6、:frequentpatternmining;subgraphisomorphism;subtreeisomorphism;frequentsubgraph;spanningtree摘要:由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题——频繁子图挖掘.诸如化学、生物学、计算机网络和WWW等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间⎛2.5⎞3nnn复杂性是O(n·2),其中,n是图
7、集中的频繁边数.提出算法的时间复杂性是O⎜2⋅⎟,性能提高了O(n⋅logn)倍.⎜logn⎟⎝⎠实验结果也证实了这一理论分析.关键词:频繁模式挖掘;子图同构;子树同构;频繁子树;生成树中图法分类号:TP311文献标识码:A∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.60473075,60773063(国家自然科学基金);theKeyProgramNationalNaturalScienceFoundationofChinaunderG
8、rantNo.60533110(国家自然科学基金重点项目);theNationalBasicResearchProgramofChinaunderGrantNo.2006CB303000(国家重点基础研究发展计划(973));theProgramforNewCenturyEx
