基于FP-Tree的频繁项集挖掘算法研究

论文摘要

数据挖掘在最近几年里已被广泛的研究和应用，而频繁项集挖掘则是诸如关联规则挖掘、序列模式挖掘等数据挖掘问题中的关键步骤，因此对它的研究具有重要的理论和实际价值。本文的主要工作是对频繁项集挖掘领域内的经典算法FP-Growth进行改进。针对该算法存在的缺陷：挖掘过程中需要递归生成大量的条件FP-Tree来保存投影信息，过度消耗了存储空间。首先分析了造成这种缺陷的原因：原算法对项的处理顺序与投影方向重合，即“向前处理，向前投影”，若直接用原FP-Tree来保存投影信息，则会覆盖掉将来要用到的信息，造成信息的丢失，因此需要条件FP-Tree来保存投影信息。然后给出了相应的改进策略：调整原算法对项的处理顺序或投影方向，使原FP-Tree能够直接存储投影信息，这样算法的所有工作便可完全基于原FP-Tree，从而不再需要任何条件FP-Tree。以此为基础，提出了一种基于FP-Tree的改进算法：NCTree-Growth，并详细讨论了它的两种不同的实现方案：“向后处理，向前投影”和“向前处理，向后投影”，给出了它们的算法伪代码描述和相互间的比较。最后通过对NCTree-Growth算法的进一步优化，使其能够充分利用前面的计算结果，从而减少了投影次数，提高了算法效率。实验表明，NCTree-Growth的内存开销小于FP-Growth，性能也得到了提升。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.3 本文主要工作及章节安排
• 第二章 数据挖掘概述
• 2.1 数据挖掘的概念及其产生背景
• 2.2 数据挖掘的功能
• 2.3 数据挖掘的过程
• 2.4 典型的数据挖掘系统
• 2.5 数据挖掘的常用方法
• 2.6 数据挖掘的发展趋势
• 2.7 本章小结
• 第三章 频繁项集挖掘及其经典算法介绍
• 3.1 问题描述
• 3.1.1 现实背景
• 3.1.2 形式化定义
• 3.1.3 举例说明
• 3.2 Apriori算法介绍
• 3.2.1 算法基本思想
• 3.2.2 Apriori性质
• 3.2.3 算法基本步骤
• 3.2.4 算法详解
• 3.3 FP-Growth 算法介绍
• 3.3.1 算法基本思想
• 3.3.2 算法详解
• 3.4 本章小结
• 第四章 改进的频繁项集挖掘算法
• 4.1 改进动机
• 4.1.1 FP-Growth算法存在的缺陷
• 4.1.2 缺陷的原因分析
• 4.2 改进思路
• 4.2.1 方案 1：向后处理，向前投影
• 4.2.2 方案 2：向前处理，向后投影
• 4.3 具体实现
• 4.3.1 方案 1 详解
• 4.3.2 方案 2 详解
• 4.3.3 两种方案的对比
• 4.4 进一步优化
• 4.4.1 核心思想
• 4.4.2 实例说明
• 4.4.3 实现方法
• 4.5 实验及结果分析
• 4.5.1 实验环境及测试数据
• 4.5.2 时间复杂度分析
• 4.5.3 空间复杂度分析
• 4.6 本章小结
• 第五章 总结与展望
• 5.1 本文工作总结
• 5.2 进一步研究方向
• 致谢
• 参考文献