学位论文 > 优秀研究生学位论文题录展示

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

作　者: 刘文艳
导　师: 高琳
学　校: 西安电子科技大学
专　业: 计算机应用技术
关键词: 图挖掘频繁导出子图图同构算法
分类号: TP301.6
类　型: 硕士论文
年　份: 2009年
下　载: 52次
引　用: 0次
阅　读: 论文下载

内容摘要

随着包括化学情报学、生物信息学、计算机视觉、视频索引、文本检索以及Wleb分析在内的广泛应用,图作为一种一般数据结构在复杂结构和它们之间相互作用建模中变得越来越重要。为了进一步进行特征化、区分、分类和聚类分析,挖掘频繁子图模式已经成为一项重要的任务。近年来,频繁子图挖掘已经成为数据挖掘中一个活跃和重要的课题。本文对基于图论的经典频繁子图挖掘算法进行了系统的研究和全面的总结,在此基础上提出了基于深度优先策略的频繁导出子图挖掘算法CISM (Connected Induced Subgraph Mining)。CISM采用基于顶点的扩展策略。首先扫描图集,找到图集中的频繁点,并把非频繁点从图集中删除,降低问题的规模；然后找到图集中的频繁边,将频繁边按支持度降序排列；接下来对每一条频繁边进行深度优先搜索,扩展生成候选导出子图,找到该边的所有候选导出k-子图,紧接着对这些候选导出k-子图进行支持度计数,得到频繁导出k-子图,再由这些频繁导出k-子图找到频繁导出(k+1)-子图,直到不能找到更大规模的频繁子图,即完成对该频繁边的所有扩展；然后将该频繁边从图集中删除,进入另一条频繁边的扩展；该方法能够有效地减少冗余子图的生成,提高挖掘的效率。通过真实的PTE化合物数据测试,CISM算法能够准确、高质量地挖掘图集中的频繁导出子图。

全文目录

摘要  3-4
Abstract  4-7
第一章绪论  7-13
  1.1 研究背景  7-8
  1.2 频繁子图挖掘的研究历史和现状  8-10
  1.3 论文研究目的及主要内容  10-13
第二章频繁子图挖掘算法  13-31
  2.1 基本概念和问题描述  13-14
  2.2 关联规则挖掘  14-18
    2.2.1 关联规则定义  14-15
    2.2.2 Apriori算法  15-17
    2.2.3 FP-Growth算法  17-18
  2.3 基于Apriori思想的频繁子图挖掘  18-22
    2.3.1 AcGM算法  18-20
    2.3.2 FSG算法  20-22
    2.3.3 边不相交路径算法  22
  2.4 基于FP-Growth思想的频繁子图挖掘  22-28
    2.4.1 gSpan算法  23-24
    2.4.2 FFSM算法  24-27
    2.4.3 CloseGraph算法  27-28
  2.5 频繁子图挖掘算法的问题及分析  28-30
  2.6 本章小结  30-31
第三章频繁导出子图挖掘算法CISM  31-43
  3.1 问题定义  31
  3.2 CISM算法  31-37
    3.2.1 CISM算法框架  31-34
    3.2.2 候选子图生成  34-35
    3.2.3 候选子图剪枝  35-36
    3.2.4 支持度计数  36-37
  3.3 图的规范化标记  37-41
    3.3.1 一般方法  37-38
    3.3.2 顶点不变式  38-39
    3.3.3 规范化标记  39-41
  3.4 本章小结  41-43
第四章实验结果与分析  43-49
  4.1 实验数据  43-46
  4.2 实验结果与分析  46-49
第五章总结与展望  49-51
致谢  51-53
参考文献  53-57
研究成果  57

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

内容摘要

全文目录

相似论文