基于尝试优先策略的频繁导出子图挖掘算法

《基于尝试优先策略的频繁导出子图挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、创新性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人签名：，函I受艳本人承担一切相关责任。日期>t阄呵军占日留日关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产

2、权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。(保密的论文在解密后遵守此规定)本学位论文属于保密在年解密后适用本授权书。本人签名：缸f女艳日期>删年弓日7留导师签名：角狄日期z研。多、7jj

3、；{承jl每l鼍ji蓬{f．t7摘要{

4、IIIIIIIII11111IIl{Y1867359随着包括化学情报学、生物信息学、计算机视觉、视频索引、文本检索以及Web分析在内

5、的广泛应用，图作为一种一般数据结构在复杂结构和它们之间相互作用建模中变得越来越重要。为了进一步进行特征化、区分、分类和聚类分析，挖掘频繁子图模式已经成为一项重要的任务。近年来，频繁子图挖掘已经成为数据挖掘中一个活跃和重要的课题。本文对基于图论的经典频繁子图挖掘算法进行了系统的研究和全面的总结，在此基础上提出了基于深度优先策略的频繁导出子图挖掘算法CISM(ConnectedInducedSubgraphMining)。CISM采用基于顶点的扩展策略。首先扫描图集，找到图集中的频繁点，并把非频繁点从图集中删除，降低问题的规模；然后找到图集中的频繁边，

6、将频繁边按支持度降序排列；接下来对每一条频繁边进行深度优先搜索，扩展生成候选导出子图，找到该边的所有候选导出k．子图，紧接着对这些候选导出k-子图进行支持度计数，得到频繁导出k-子图，再由这些频繁导出k-子图找到频繁导出(k+1)．子图，直到不能找到更大规模的频繁子图，即完成对该频繁边的所有扩展；然后将该频繁边从图集中删除，进入另一条频繁边的扩展；该方法能够有效地减少冗余子图的生成，提高挖掘的效率。通过真实的PTE化合物数据测试，CISM算法能够准确、高质量地挖掘图集中的频繁导出子图。关键词：图挖掘频繁导出子图图同构算法AbstractAsagen

7、eraldatastructure，graphshavebecomeincreasinglyimportantinmodelingsophisticatedstructuresandtheirinteractions，、)l，imbroadapplicationsincludingchemicalinformatics，bioinformatics，computervision，videoindexing，textretrieval，andWebanalysis．Miningfrequentsubgraphpatternsforfurthercha

8、racterization,discrimination，classification,andclusteranalysisbecomesanimportanttask．Withtheincreasingdemandontheanalysisoflargeamountofstructureddata,frequentsubgraphmininghasbecomeanactiveandimportantthemeindatamining．Inthispaper,someworksaredoneinthefrequentsubgraphmining．F

9、irstly,someclassicalgraph-basedalgorithmsforminingfrequentsubgraphsaresystematicallystudiedandcomprehensivelysummarized．Secondly,thispaperproposesanewalgorithmnamedCISM(ConnectedInduceSubgraphMining)tofrequentconnectedinducedsubgraphsinagivengraphdatasetGD．Itusesavertex—basedc

10、andidategenerationmethodthatincreasesthesubgraphsizebyonevert