资源描述：
《浅析一种基于前缀节点的频繁子图挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、浅析一种基于前缀节点的频繁子图挖掘算法摘要:基于频繁子树挖掘算法中的前缀节点思想,将模式图分为图核—分支—连接向量三个部分,提出了CBE算法。对在分支上扩展得到的候选模式图,CBE算法能够在常数时间内完成规范化判定。通过实验证明CBE算法的子图挖掘效率有显著提高。 关键词:数据挖掘;频繁子图;同构类;规范化形式;前缀节点 Frequentsubgraphsminingalgorithmbasedonprefixnode LIHai-bo,WANGYuan-zhen (ResearchInstitu
2、teofDatabase&Multimedia,SchoolofComputerScience&Technology,HuazhongUniversityofScience&Technology,Wuhan30074,China) Abstract:Basedontheprefixnodemethodinfrequenttreeminingalgorithms,adoptingcore-braches-connectingvectorpartitionongraphs,thispaperprovidedanewa
3、lgorithmCBE.TheCBEalgorithmcouldaccomplishcanonicaldeterminingin浅析一种基于前缀节点的频繁子图挖掘算法摘要:基于频繁子树挖掘算法中的前缀节点思想,将模式图分为图核—分支—连接向量三个部分,提出了CBE算法。对在分支上扩展得到的候选模式图,CBE算法能够在常数时间内完成规范化判定。通过实验证明CBE算法的子图挖掘效率有显著提高。 关键词:数据挖掘;频繁子图;同构类;规范化形式;前缀节点 Frequentsubgraphsminingalgori
4、thmbasedonprefixnode LIHai-bo,WANGYuan-zhen (ResearchInstituteofDatabase&Multimedia,SchoolofComputerScience&Technology,HuazhongUniversityofScience&Technology,Wuhan30074,China) Abstract:Basedontheprefixnodemethodinfrequenttreeminingalgorithms,adoptingcore-
5、braches-connectingvectorpartitionongraphs,thispaperprovidedanewalgorithmCBE.TheCBEalgorithmcouldaccomplishcanonicaldetermininginconstanttimeoncandidatepatterngraphsexpandedfrombranches.PerformancetestingprovesthattheefficiencyofsubgraphsminingisimprovedbyCBEal
6、gorithm. Keywords:datamining;frequentsubgraph;isomorphismclass;canonicalform;prefixnode 在化学信息学、生物信息学、网络结构分析等领域,频繁子图挖掘算法是一个热点研究问题。与其他的频繁模式挖掘算法类似,一般的频繁子图挖掘算法都分为候选模式生成和模式频繁判定两步[1]。在频繁子图的挖掘过程中,会生成大量的候选模式图。对每一个新产生的候选模式图,在进行频繁判定之前,都要首先判断它与前面产生的模式图是否同构。而图的同构判定是一个复杂
7、度介于P与NP之间的问题[2~5]。受此限制,目前出现的子图挖掘算法的效率还不是很高,特别是与频繁子树挖掘算法相比。频繁子树的挖掘也会生成大量的候选模式树,但基于一种称为前缀节点的方法,可以在常数时间内解决候选模式树的同构判定问题。 本文针对这种情况,基于频繁子树挖掘算法中的前缀节点思想,提出了一种在部分候选模式图上能够在常数时间内完成同构判定的方法,并以此方法为核心给出了一种新的高效频繁子图挖掘算法——图核—分支扩展算法(CBE)。 1基于次前缀节点的频繁子树挖掘算法 频繁子树挖掘算法分为候选模式子树生成和
8、子树频繁判定两步。候选模式子树可以通过在一棵频繁子树的任一个节点上扩展任一条边得到,但这种扩展会产生大量同构的模式子树。一种朴素的筛选方法是检查新生成的模式子树是否与先前生成的某棵模式子树同构。若存在同构的模式子树,则当前扩展是无效的;否则当前扩展生成一棵新的有效的模式子树。因此,候选子树的生成,本质是要遍历所有的子树同构类。对每一类同构的子树,只需生成一棵
