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

基于分布式的频繁闭合模式挖掘算法研究

作　者: 张敏
导　师: 杨君锐
学　校: 西安科技大学
专　业: 计算机应用技术
关键词: 数据挖掘关联规则分布式算法频繁闭合模式
分类号: TP311.13
类　型: 硕士论文
年　份: 2011年
下　载: 25次
引　用: 0次
阅　读: 论文下载

内容摘要

关联规则挖掘是数据挖掘研究中的热点问题之一,其目的是发现数据库中数据项之间存在的潜在联系。关联规则挖掘的重点任务是频繁模式挖掘。然而,由于频繁模式挖掘的复杂性,业界提出了频繁闭合模式挖掘问题。频繁闭合模式可以唯一地确定所有频繁模式完全集以及它们的准确支持度,且其规模远远小于频繁模式。在单处理机上的频繁闭合模式挖掘算法研究方面,人们已经取得了许多成果。但随着分布式环境的日益普遍,使得传统串行算法的挖掘技术已无法解决分布式下的挖掘问题,因此,研究高性能的分布式频繁闭合模式挖掘算法显得尤为重要。本文在对典型关联规则挖掘算法进行较深入研究的基础上,将分布式思想引入关联规则挖掘中,提出了两种分布式频繁闭合模式挖掘算法,主要内容有以下两部分:第一部分提出了一种基于分布式的频繁闭合模式挖掘算法-PFCI_Miner。算法采用任务分布的主从方式,其中主处理器通过发送文中提出的前缀路径表(PrePthx)将挖掘任务合理划分,而从处理器借助提出的存储树(Trac-tree)挖掘局部频繁闭合模式,最后由主处理器挖掘出全局频繁闭合模式集。另外,采用星形的拓扑结构,使数据通信只存在于主处理器与从处理器之间,而各从处理器之间无数据通信且不需要同步。实验结果表明,PFCI_Miner算法具有较好的效率。第二部分针对数据流及分布式算法的特点,提出了一种数据流下的分布式频繁闭合模式挖掘算法DSFC_Miner。该算法采用分段思想,挖掘每个数据流分段的临界频繁闭合模式,并创建相应的局部FCI_DS树保存临界频繁闭合模式。最后通过合并局部FCI_DS树,在允许误差范围内挖掘得到当前数据流中的频繁闭合模式集。实验结果表明该算法是可行的。

全文目录

摘要  2-3
ABSTRACT  3-7
1 绪论  7-12
  1.1 本文的研究背景和意义  7-8
  1.2 关联规则研究现状  8-10
  1.3 本文研究内容  10-11
  1.4 本文组织结构  11-12
2 关联规则挖掘技术  12-23
  2.1 关联规则概述  12-13
    2.1.1 关联规则问题描述  12-13
    2.1.2 关联规则挖掘步骤  13
  2.2 频繁模式挖掘算法  13-19
    2.2.1 Apriori 算法  13-16
    2.2.2 FP-growth 算法  16-17
    2.2.3 其它频繁模式挖掘算法  17-19
  2.3 频繁闭合模式挖掘算法  19-22
    2.3.1 A-Close 算法  19
    2.3.2 Closet 和 Closet+算法  19-20
    2.3.3 其它频繁闭合模式挖掘算法  20-22
  2.4 本章小结  22-23
3 分布式关联规则挖掘技术  23-30
  3.1 问题描述  23-25
    3.1.1 分布式系统  23-24
    3.1.2 分布式关联规则挖掘  24-25
    3.1.3 消息传递接口MPI  25
  3.2 基于分布式的频繁模式挖掘算法  25-28
    3.2.1 基于Apriori 的分布式算法  26-27
    3.2.2 其它分布式的频繁模式挖掘算法  27-28
  3.3 基于分布式的频繁闭合模式挖掘研究现状  28-29
  3.4 本章小结  29-30
4 基于分布式的频繁闭合模式挖掘算法PFCI_Miner  30-45
  4.1 BFP-tree 和Trac-tree  30-33
    4.1.1 BFP-tree  30-32
    4.1.2 Trac-tree  32-33
  4.2 PFCI_Miner 算法  33-37
    4.2.1 算法基本思想和挖掘过程  33-34
    4.2.2 PFCI_Miner 算法描述  34-36
    4.2.3 算法示例  36-37
  4.3 算法测试与性能分析  37-44
    4.3.1 测试环境  38
    4.3.2 算法对比测试与分析  38-42
    4.3.3 算法通信次数测试与分析  42-43
    4.3.4 可扩展性测试  43-44
  4.4 小结  44-45
5 数据流下的分布式频繁闭合模式挖掘算法DSFC_Miner  45-54
  5.1 数据流挖掘技术概述  45-46
    5.1.1 数据流的相关概念  45-46
    5.1.2 分布式数据流挖掘研究现状  46
  5.2 DSFC_Miner 算法  46-50
    5.2.1 FCI_DS 树  47-48
    5.2.2 DSFC_Mine 算法基本思想  48-49
    5.2.3 DSFC_Mine 算法挖掘过程  49-50
  5.3 算法测试与性能测试  50-53
    5.3.1 测试环境  50
    5.3.2 算法对比测试与分析  50-51
    5.3.3 算法性能测试与分析  51-53
  5.4 本章小结  53-54
6 结论  54-56
  6.1 总结  54
  6.2 展望  54-56
致谢  56-57
参考文献  57-62
附录  62

基于分布式的频繁闭合模式挖掘算法研究

内容摘要

全文目录

相似论文