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

基于iceberg概念格的最大频繁项集挖掘研究

作　者: 王富强
导　师: 薛安荣
学　校: 江苏大学
专　业: 计算机应用技术
关键词: icebe唱概念格最大频繁概念最大频繁项集新增最大频繁概念更新最大频繁概念正相关的无冗余关联规则
分类号: TP311.13
类　型: 硕士论文
年　份: 2010年
下　载: 36次
引　用: 0次
阅　读: 论文下载

内容摘要

关联规则挖掘过程中频繁项集(Frequent Itemset,FI)的求解是关联规则挖掘的基础和前提,也是关联规则挖掘中最耗时的一步。降低候选项集的数量是减小开销的最好手段。由于最大频繁项集(Maximal Frequent Itemset, MFI)中已经隐含了所有频繁项集,所以可把发现频繁项集的问题转化为发现最大频繁项集的问题。挖掘最大频繁项集可有效地缩小项集的规模,便于用户迅速发现稠密数据集中的知识。然而,随着数据收集和数据存储技术的快速进步,使得各组织机构积累了海量的数据,造成现有的最大频繁项集挖掘算法挖掘效率低下,主要表现为：多次扫描数据库需要大量I/O开销;候选集规模过大导致无法计算和存储；增量挖掘困难；大量冗余的和用户不感兴趣的规则等等。为了解决上述问题,论文将具有完备特性的iceberg概念格模型引入到最大频繁项集挖掘的研究中。iceberg概念格是在用户指定的支持度阈值的条件下概念格中所有频繁概念构成的半序格结构,每个频繁概念的内涵都是一个频繁闭项集,描述了数据集中对象和属性之间的关系。利用频繁闭项集与最大频繁项集之间的隶属关系和频繁概念之间良好的泛化和特化关系,提出了基于iceberg概念格的最大频繁项集和属性增长的最大频繁项集增量挖掘算法。论文还对基于iceberg概念格的正相关的无冗余关联规则进行研究,解决了从最大频繁项集中挖掘的关联规则会导致支持度信息的损失和存在大量冗余的用户不感兴趣的规则的问题。论文的主要工作如下：(1)提出基于iceberg概念格的最大频繁项集挖掘算法ICMFIA(Iceberg Concept Lattice Maxmal Frequent Itemset Alogithm)。该算法通过一次扫描数据集构建iceberg概念格,利用iceberg概念格中频繁概念之间良好的覆盖关系,能快速计算出最大频繁项集所对应的最大频繁概念,所有最大频繁概念的内涵就是所求的最大频繁项集的集合。理论证明和实验测试结果表明,所提算法与现有算法相比,具有扫描数据集次数少和挖掘效率高的优点。(2)提出基于iceberg概念格的最大频繁项集增量挖掘算法MAI-AI(Maximal Frequent Itemset-Attribute Incremental)。该算法主要针对数据集的属性增加后最大频繁项集挖掘问题。在原始iceberg概念格的基础上构建新的iceberg概念格并计算新增的最大频繁概念和需要更新的最大频繁概念。然后只需挖掘新增的最大频繁项集和最大频繁项集集合中需要更新的最大频繁项集。避免了数据集中属性增加后需要重新挖掘所有的最大频繁项集问题。实验结果表明,算法具有重复工作少和重用率高的优点。(3)提出了在iceberg概念格中挖掘正相关的无冗余关联规则的方法,以解决最大频繁项集挖掘出的关联规则支持度信息的损失和存在大量用户不感兴趣的规则等问题。通过提出无冗余关联规则来缩小挖掘规则的规模,其它有效的关联规则的支持度和置信度都能通过无冗余关联规则计算出来。由于使用支持度一置信度框架计算的强关联规则不一定是有趣的,论文引入提升度来挖掘正相关无冗余关联规则,挖掘用户真正感兴趣的规则。

全文目录

摘要  5-7
ABSTRACT  7-11
第一章绪论  11-19
  1.1 研究背景和意义  11-12
  1.2 国内外研究现状  12-16
    1.2.1 最大频繁项集研究现状  12-14
    1.2.2 iceberg概念格研究现状  14-16
  1.3 主要研究内容  16-17
  1.4 论文的组织结构  17-19
第二章相关技术  19-29
  2.1 关联规则挖掘  19-22
    2.1.1 关联规则概念及定义  19-20
    2.1.2 基于支持度的剪枝策略  20-21
    2.1.3 经典的频繁项集  21-22
  2.2 iceberg概念格相关理论  22-27
    2.2.1 形式概念分析理论  22-25
    2.2.2 iceberg概念格定义  25-27
  2.3 概念格与关联规则挖掘  27-28
  2.4 本章小结  28-29
第三章基于iceberg概念格的最大频繁项集挖掘  29-38
  3.1 问题描述  29-30
  3.2 基于iceberg概念格的最大频繁项集挖掘算法  30-34
    3.2.1 最大频繁概念挖掘  30-32
    3.2.2 ICMFIA算法描述  32-33
    3.2.3 算法的复杂度分析  33-34
  3.3 ICMFIA算法实验与结果分析  34-37
    3.3.1 算法实验设计  34-35
    3.3.2 结果分析  35-37
  3.4 本章小结  37-38
第四章基于iceberg概念格的最大频繁项集增量挖掘  38-49
  4.1 增量挖掘技术  38-40
  4.2 最大频繁项集增量挖掘算法MFI-AI  40-46
    4.2.1 iceberg概念格渐进式构造  40-42
    4.2.2 最大频繁项集的集合更新  42-43
    4.2.3 MFI-AI算法描述  43-44
    4.2.4 MFI-AI算法应用举例  44-46
  4.3 实验结果与分析  46-48
  4.4 本章小结  48-49
第五章 iceberg概念格与正相关无冗余关联规则挖掘  49-61
  5.1 支持度-置信度框架的局限性  49-50
  5.2 基于提升度的关联规则分析  50-51
  5.3 iceberg概念格与无冗余关联规则挖掘  51-58
    5.3.1 无冗余关联规则概念和性质  51-52
    5.3.2 Minimal generators生成  52-54
    5.3.3 无冗余的关联规则挖掘  54-58
  5.4 无冗余关联规则中的正相关规则提取  58-59
  5.5 本章小结  59-61
第六章总结与展望  61-63
  6.1 工作总结  61-62
  6.2 进一步工作  62-63
致谢  63-64
参考文献  64-70
攻读硕士学位期间发表的学术论文  70

基于iceberg概念格的最大频繁项集挖掘研究

内容摘要

全文目录

相似论文