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

基于图的数据挖掘算法研究

作　者: 唐德权
导　师: 夏幼明
学　校: 云南师范大学
专　业: 计算机软件与理论
关键词: 数据挖掘 子图同构 规范化编码 嵌入集 频繁子图挖掘
分类号: TP311.13
类　型: 硕士论文
年　份: 2007年
下　载: 93次
引　用: 1次
阅　读: 论文下载
 

内容摘要


与一般的数据比较,图能够表达更加丰富的语义,在科学研究和许多商业领域有着更为广泛的应用,如它可以描述世界万物之间错综复杂的联系,在社会网络分析中,人与人之间、人与物之间的联系是复杂的。通过抽象方法,可以将整个社会变成一个网络拓扑图,其中每个人可以是图中的节点,而人与人之间的联系则可以看作为图中的边。对社会人群的分析,自然就可以转化为对社会网络结构的挖掘。在生物技术领域,在生物学家发现蛋白质基因结构配位实验上频繁子图挖掘可以减轻结构匹配实验的代价。在Web挖掘、空间数据挖掘、药物分子式设计及其功能预测等领域也都有广泛应用。因此,对频繁子图的挖掘算法的研究有着重要的理论意义和应用价值。同时,这种丰富的语义也增加了数据结构的复杂性和挖掘令人感兴趣的图的子结构的难度。因此,需要综合应用图论知识与数据挖掘的各种技术。本文工作主要包括以下几部分:(1)在分析当前频繁子图挖掘定义的基础上结合支持度能反映数据库元素的共性和频繁度揭示了元素的个性特点,给出了基于支持度和频繁度的频繁子图挖掘定义;(2)基于子图同构理论和判断两个图同构的思想:如果两个图同构,那么它们的规范化编码一定相等。提出了一种有效进行图的规范化编码算法,从而避免子图同构NP完全问题带来的困难;(3)基于目前产生许多冗余候选子图的技术,提出了一种新的候选子图产生方法,通过连接和扩展操作产生所有候选子图,并且无冗余候选子图产生,从而可以正确计算候选子图的支持度,也减少了一些无效子图匹配问题;(4)引用嵌入集概念,基于候选子图的规范化邻接矩阵(CAM)在某个图的规范化邻接矩阵(CAM)的嵌入特征有效地计算候出选子图的支持度和频繁度;(5)基于图的规范化理论、候选子图的产生技术和候选子图支持度的计算方法,提出了频繁子图挖掘算法FSubgraphM,它能有效地从图数据库中挖掘频繁导出子图。实验研究表明,FSubgraphM能有效地从数据库carcinogen中挖掘其中的频繁导出子图结构,并根据频繁结构集提取有趣的关联知识,有着重要的理论指导意义和应用价值。本文解决了频繁子图挖掘算法中三个关键问题:(1)提出新的规范编码解决了判断一个图是否与另一个图同构,即子图同构问题;(2)提出新的连接和扩展操作算子有效解决了生成候选子图问题;(3)引入嵌入集概念,巧妙地结合连接和扩展操作计算嵌入集,解决了计算频繁子图问题。

全文目录


基于图的数据挖掘算法研究  3-43
  摘要  5-9
  第一章 引言  9-13
    1.1 研究背景  9-10
    1.2 研究现状  10-12
    1.3 本文的主要工作  12
    1.4 论文组织  12-13
  第二章 基本概念  13-21
    2.1 图的基本概念  13-15
    2.2 支持度和频繁度  15-16
    2.3 频繁子图挖掘  16-20
      2.3.1 频繁子图挖掘的一般过程  16-18
      2.3.2 频繁子图挖掘需要解决的问题  18-20
    2.4 本章小结  20-21
  第三章 频繁子图挖掘  21-37
    3.1 规范化邻接矩阵CAM(CANONICAL ADJACENCY MATRIX)及其理论  21-26
    3.2 CAM TREE  26-27
    3.3 候选集的产生  27-33
      3.3.1 FSubgraphM-Join算子  28-29
      3.3.2 FSubgraphM-Extension算法  29-30
      3.3.3 次优CAM Tree  30-33
    3.4 支持度和频繁度计算  33-35
    3.5 频繁子图挖掘算法FSUBGRAPHM  35-36
    3.6 本章小结  36-37
  第四章 实验与分析  37-41
    4.1 数据预处理  37-38
    4.2 实验数据分析  38-39
    4.3 关联知识提取  39-41
  第五章 总结与展望  41-43
Research on Algorithm of Graph-Based Data Mining  43-97
  ABSTRACT  45-49
  1.INTRODUCTION  49-55
    1.1 BACKGROUND  49-51
    1.2 STATE OF THE ART OF FREQUENT SUBGRAPH MINING  51-53
    1.3 OUR CONTRIBUTION  53-54
    1.4 THE ARCHITECTURE OF THIS THESIS  54-55
  2.PRELIMINARIES  55-65
    2.1 GRAPH AND IT'S SUBGRAPHS  55-56
    2.2 SUPPORT AND FREQUENT  56-58
    2.3 FREQUENT SUBGRAPH MINING  58-62
      2.3.1 The general process of frequent subgraph mining  59-60
      2.3.2 The problems have to be solved in the frequent subgraph mining  60-62
    2.4 CONCLUSION OF THIS SECTION  62-65
  3.FREQUENT SUBGRAPH MINING  65-83
    3.1 CAM(CANONICAL ADJACENCY MATRIX) AND THEORY  65-70
    3.2 CAM'S TREE  70-72
    3.3 CANDIDATE SUBGRAPH GENERATE  72-79
      3.3.1 FSubgraphM-Join  73-74
      3.3.2 FSubgraphM-Extension  74-76
      3.3.3 Suboptimal CAM Tree  76-79
    3.4 SUPPORT AND FREQUENCY COUNTING  79-81
    3.5 THE ALGORITHM FSUBGRAPHM OF MINING FREQUENT SUBGRAPH  81-82
    3.6 CONCLUSION OF THIS SECTION  82-83
  4.EXPERIMENTS AND ANALYSIS  83-87
    4.1 PREPROCESSING OF THE PRIMITIVE DATA  83-84
    4.2 ANALYSIS OF THE RESULT  84-85
    4.3 ASSOCIATION RULE EXTRACTION  85-87
  5.CONCLUSIONS AND THE FUTURE WORK  87-89
  REFERENCES  89-97
基于图的数据挖掘算法研究综述  97-143
  摘要  99-103
  1.引言  103-111
    1.1 图的数据挖掘技术的产生背景  104
    1.2 目前图的数据挖掘技术方法的分类  104-106
      1.2.1 基于贪心搜索的方法  104-105
      1.2.2 归约数据库方法  105-106
      1.2.3 归约逻辑编程(ILP)方法  106
      1.2.4 数学图论方法  106
    1.3 图的数据挖掘技术的应用  106-108
      1.3.1 Web浏览中用户兴趣点的挖掘  106-107
      1.3.2 分子模型分析  107
      1.3.3 CAD线路分析  107
      1.3.4 数据的压缩  107
      1.3.5 生物信息学中的研究  107-108
    1.4 图的数据挖掘技术研究历史及现状  108-110
    1.5 目前图的数据挖掘技术中的难点和挑战  110-111
  2.数据挖掘基础  111-119
    2.1 关联规则的基本概念  111-112
    2.2 主要关联规则挖掘算法及其模型  112-118
      2.2.1 Apriori算法:使用候选集寻找频繁项集  112-114
      2.2.2 不产生候选集的算法  114-118
    2.3 主要算法的优缺点分析  118-119
  3.图论基础  119-125
    3.1 子图分类  119-120
    3.2 子图同构  120-121
    3.3 图的不变量  121-122
    3.4 图的规范化编码  122-125
  4.对频繁子图挖掘的各种算法分析比较  125-133
    4.1 频繁子树挖掘  125
    4.2 频繁子图挖掘算法的基本概念  125-126
      4.2.1 问题描述  125-126
      4.2.2 频繁子图挖掘的分类  126
    4.3 频繁子图挖掘算法分析  126-133
      4.3.1 Apriori算法在频繁子图挖掘中的应用  127-128
      4.3.2 FP-grow算法在频繁子图挖掘中的应用  128-129
      4.3.3 基于gSpan算法的频繁闭子图挖掘算法CloseGraph  129-131
      4.3.4 非精确算法  131
      4.3.5 large graph型频繁子图挖掘算法  131
      4.3.6 其他算法  131-133
  5.相关工作  133-141
    5.1 频繁项集挖掘  133-135
      5.1.1 问题定义  133
      5.1.2 候选项目集的枚举  133-135
      5.1.3 候选集的产生  135
      5.1.4 频繁度计数  135
    5.2 序列模式挖掘  135-136
    5.3 时间序列模式挖掘  136-137
    5.4 最大频繁项集和频繁闭合项集模式挖掘  137-138
    5.5 频繁子树挖掘  138-139
    5.6 频繁子图挖掘与频繁项目集挖掘比较  139-141
  6.总结与展望  141-143
A Survey on Graph-Based Data Mining  143-205
  ABSTRACT  145-149
  1.INTRODUCTION  149-159
    1.1 BACKGROUND OF DATA MINING BASE ON GRAPH  150
    1.2 APPROACHES OF GRAPH MINING  150-154
      1.2.1 Greedy search based Approach  151-152
      1.2.2 Inductive Database Based Approach  152-153
      1.2.3 Inductive logic programming(ILP) based approach  153
      1.2.4 Mathematical Graph Theory Based Approach  153-154
    1.3 APPLICATIONS OF DATA MINING BASED ON GRAPH  154-155
      1.3.1 Web mining  154
      1.3.2 Molecule model mining  154-155
      1.3.3 CAD circuit analyze  155
      1.3.4 Data compress  155
      1.3.5 bioinformatics mining  155
    1.4 THE HISTORY AND STATE OF DATA MINING BASE ON GRAPH  155-157
    1.5 THE DIFFICULT AND CHANLLENGE OF DATA MINING TECHNOLOGY BASE ON GRAPH  157-159
  2.PRELIMINARIES OF DATA MINING  159-169
    2.1 CONCEPT OF ASSOCIATION RULES  159-160
    2.2 MAINLY ALGORITHM AND MODEL OF ASSOCIATION RULES  160-166
      2.2.1 Apriori:A Candidate Generation-and-Test Approach  160-163
      2.2.2 FP_Tree:A no Generated Candidate Approach  163-166
    2.3 ANALYZE MERITE AND INSUFFICIENCY OF MAINLY ALGORITHM  166-169
  3.GRAPH CONCEPTS  169-175
    3.1 SUBGRAPH CATEGORIES  169-170
    3.2 SUBGRAPH ISOMORPHISM  170-172
    3.3 GRAPH INVARIANTS  172
    3.4 CANONICAL LABELLING  172-175
  4.ANALYZE ALGORITHMS FOR MINING FREQUENT SUBGRAPHS  175-185
    4.1 FREQUENT SUBTREE MINING ALGORITHM  175-176
    4.2 THE BASIC CONCEPT OF FREQUENT SUBGRAPH MINING ALGORITHM  176-177
      4.2.1 The problem describe  176
      4.2.2 The classification of frequent subgraph mining  176-177
    4.3 TO ANALYZE ALGORITHM OF MINING FREQUENT SUBGRAPH  177-185
      4.3.1 Apriori algorithm application in the mining frequent subgraph  177-179
      4.3.2 FP-grow algorithm application in the mining frequent subgraph  179-181
      4.3.3 Frequent Closed Subgraph Mining Algorithm Base on the gSpan  181-182
      4.3.4 Non-precise algorithm  182-183
      4.3.5 The mibning frequent subgraph in the large graph  183
      4.3.6 The Other Algorithm  183-185
  5.OTHER RELATED WORK  185-195
    5.1.MINING FREQUENT ITEMSETS  185-188
      5.1.1 The problem definition  185-186
      5.1.2 Candidate enumeration  186-187
      5.1.3 Candidate generation  187
      5.1.4 Frequency counting  187-188
    5.2.MINING SEQUENCE PATTERNS  188-189
    5.3.MINING TIME SEQUENCE PATTERNS  189-190
    5.4.MINING MAXIMAL FREQUENT ITEMSET AND FREQUENT CLOSED ITEMSET  190-191
    5.5.MINING FREQUENT SUBTREE  191-193
    5.6.COMPARE MINING FREQUENT SUBGRAPH TO FREQUENT ITEMSET  193-195
  6.CONCLUSION AND FUTURE DIRECTIONS  195-197
  REFERENCES  197-205
致谢  205

相似论文

  1. 频繁图结构并行挖掘算法的研究与实现,TP311.13
  2. 基于数据挖掘技术的保健品营销研究,F426.72
  3. 高忠英学术思想与经验总结及运用补肺汤加减治疗呼吸系统常见病用药规律研究,R249.2
  4. 张炳厚学术思想与临床经验总结及应用地龟汤类方治疗慢性肾脏病的经验研究,R249.2
  5. Bicluster数据分析软件设计与实现,TP311.52
  6. 基于变异粒子群的聚类算法研究,TP18
  7. 融合粒子群和蛙跳算法的模糊C-均值聚类算法研究,TP18
  8. 基于遗传算法和粗糙集的聚类算法研究,TP18
  9. 基于数据挖掘的税务稽查选案研究,F812.42
  10. 面向社区教育的个性化学习系统的研究与实现,TP391.6
  11. 基于关联规则挖掘的入侵检测系统的研究与实现,TP393.08
  12. 数据仓库技术在银行客户管理系统中的研究和实现,TP315
  13. 基于Moodle的高职网络教学系统设计与实现,TP311.52
  14. 教学质量评估数据挖掘系统设计与开发,TP311.13
  15. 关联规则算法在高职院校贫困生认定工作中的应用,G717
  16. 基于数据挖掘技术在城市供水的分析与决策,F299.24;F224
  17. 数据挖掘技术在电视用户满意度分析中的应用研究,TP311.13
  18. Web使用挖掘与网页个性化服务推荐研究,TP311.13
  19. 数据挖掘在学校管理和学生培养中的应用,TP311.13
  20. 高校毕业生就业状况监测系统研究,G647.38
  21. 基于数据仓库的药品监管辅助决策支持系统的设计与实现,TP311.13

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com