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

最大频繁子图挖掘算法研究

作　者: 柴然
导　师: 郭景峰
学　校: 燕山大学
专　业: 计算机系统结构
关键词: 频繁子图挖掘最大频繁子图挖掘有向无循环图 FSG-MaxGraph算法 Top-Down算法
分类号: TP301.6
类　型: 硕士论文
年　份: 2010年
下　载: 47次
引　用: 0次
阅　读: 论文下载

内容摘要

数据挖掘是通过仔细分析大量数据揭示有意义的关系、趋势和模式的过程,图挖掘是数据挖掘的一个分支,它的研究任务包括频繁子图挖掘和最大频繁子图挖掘。与频繁子图挖掘相比挖掘最大频繁子图并不丢失信息,而且挖掘最大频繁子图得到少量的结果有助于对结果的理解和应用,但是当前的算法中仍然存在子图同构的问题,本文的重点内容如下。首先,当前算法中规范编码计算效率很低,本文基于结点不变的原则提出新的规范编码计算方法,提高规范编码的计算效率。并且提出应用有向无循环图来计算支持度的方法,该方法通过节点之间的关系来判断某图在图集中是否存在超集,进而计算它的支持度。其次,针对判断两个频繁k子图是否可以进行连接时的子图同构问题,提出了FSG-MaxGraph算法。算法提出两个定理,在删除边进行子图同构之前应用定理进行判断,减少子图同构判断的次数。再次,针对当前算法存在的挖掘难度大的问题,提出Top-Down算法,Top-Down算法通过改变挖掘策略来避免计算最大频繁子图的所有子图的支持度,降低挖掘难度。最后,通过实例以及实验对FSG-MaxGraph算法、Top-Down算法挖掘效率和正确性进行验证,同时通过理论与实验相结合判断这两种算法分别在哪种情况下具有相对更高的挖掘效率。

全文目录

摘要  5-6
Abstract  6-10
第1章绪论  10-16
  1.1 研究背景  10-11
  1.2 研究现状  11-12
  1.3 研究意义  12-13
  1.4 研究内容  13-15
  1.5 本文结构  15-16
第2章基础知识概述  16-26
  2.1 引言  16
  2.2 图的基本概念  16-19
  2.3 最大频繁子图挖掘方法分类  19
  2.4 最大频繁子图挖掘算法Apriori-MaxGraph  19-21
    2.4.1 候选子图的产生  19-20
    2.4.2 候选最大频繁子图的产生与更新  20-21
  2.5 基于模式增长的最大频繁子图挖掘算法  21-25
    2.5.1 SPIN 算法  21-23
    2.5.2 MARGIN 算法  23-25
  2.6 本章小结  25-26
第3章自底向上的最大频繁子图挖掘算法  26-44
  3.1 引言  26
  3.2 算法的思想  26-27
  3.3 图的规范编码  27-31
    3.3.1 图的存储结构  27-28
    3.3.2 计算图的规范编码  28-31
  3.4 图的支持度  31-35
    3.4.1 应用DAG 计算支持度  31-34
    3.4.2 算法描述  34-35
  3.5 FSG-MaxGraph 算法  35-41
    3.5.1 定理与证明  36-39
    3.5.2 候选最大频繁子图的产生  39-41
    3.5.3 最大频繁子图的产生  41
  3.6 算法分析  41-43
  3.7 本章小结  43-44
第4章自顶向下的最大频繁子图挖掘算法  44-54
  4.1 引言  44
  4.2 算法的思想  44-45
  4.3 Top-Down 算法  45-52
    4.3.1 相关定理和原则  45-46
    4.3.2 算法描述  46-48
    4.3.3 算法应用示例  48-52
  4.4 算法分析  52-53
  4.5 本章小结  53-54
第5章实验及结果分析  54-64
  5.1 引言  54
  5.2 FSG-MaxGraph 算法的实现与分析  54-58
    5.2.1 实验设置  54
    5.2.2 实际的数据集  54-57
    5.2.3 模拟的数据集  57-58
  5.3 Top-Down 算法的实现与分析  58-62
    5.3.1 实验设置  59
    5.3.2 实际的数据集  59-61
    5.3.3 模拟的数据集  61-62
  5.4 本章小结  62-64
结论  64-66
参考文献  66-71
攻读硕士学位期间承担的科研任务与主要成果  71-72
致谢  72-73
作者简介  73

最大频繁子图挖掘算法研究

内容摘要

全文目录

相似论文