基于FP-Tree的关联规则挖掘算法研究

论文摘要

数据挖掘技术是信息科学领域的前沿课题之一,其中的关联规则挖掘技术揭示事务数据库项集之间的关联关系,已广泛应用于市场营销、医学、电信、农业等诸多领域,是数据挖掘的重要研究课题。本文主要研究基于FP-Tree的关联规则挖掘算法。为了更好的分析事务数据库的性质、研究算法的优化方法在不同事务数据库下的挖掘效率,本文提出了关联聚集度的概念并给出了关联聚集度的一种定义和计算方法。然后根据数据库的关联聚集度提出了对经典FP-growth的优化方法。基于FP-Tree的经典FP-growth算法虽然不需要像Apriori算法一样产生大量的候选频繁项集,但是在构造FP-Tree以及基于FP-Tree对事务数据库进行关联规则挖掘等过程中,需要进行大量的遍历和递归操作,严重影响了挖掘的整体效率。针对该问题,本文改进了传统的FP-Tree结构,并提出了基于改进的数据结构DFP-Tree的关联规则挖掘算法DFP-growth。该算法采用了挖掘时间效率优先的数据结构重组织,在节点中加入了后继节点的标识信息以及前驱节点的地址信息,使针对树结构的操作得以简化。同时,针对无法基于内存构建FP-Tree的大型事务数据库,提出了适合挖掘大型数据库的算法LDFP-growth,该算法通过频繁1-项集分解数据库,并分步构建基于子数据库的DFP-Tree,然后分步挖掘子数据库的约束频繁模式,最后合并这个子数据库的关联规则得到原数据库的关联规则。实验表明,在对相对于内存较小的事务数据库进行挖掘时,DFP-growth算法显示了良好的性能,而对于大型的事务数据库,LDFP-growth算法也可以顺利的基于内存进行关联规则挖掘,并且在频繁项集增长到一定规模时显示了比经典FP-growth以及DFP-growth算法更良好的性能。最后,论文总结了三种算法的优缺点,并给出了对数据库进行基于DFP-growth或LDFP-growth算法进行关联规则挖掘时的步骤。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.3 本文的研究内容
• 1.4 论文的结构安排
• 第二章 数据挖掘概述
• 2.1 数据挖掘的定义
• 2.2 数据挖掘的过程
• 2.3 数据挖掘的任务
• 2.4 数据挖掘的对象
• 2.5 数据挖掘的方法
• 2.6 数据挖掘的发展趋势
• 第三章 关联规则挖掘
• 3.1 关联规则的基本概念
• 3.1.1 问题定义
• 3.1.2 关联规则的分类
• 3.2 关联规则挖掘的经典算法
• 3.2.1 Apriori算法
• 3.2.2 基于Apriori的改进算法
• 3.2.3 FP-growth算法
• 第四章 一种新的事务数据库参考参数与FP-Tree结构分析
• 4.1 事务数据库数据项分布性质的判定参数——关联聚集度
• 4.2 关联聚集度的确定
• 4.3 自定义数据结构
• 4.3.1 时间效率优先的数据结构重组织
• 4.3.2 空间存储优先的数据结构重组织
• 4.4 经典FP-Tree的数据结构分析
• 第五章 改进的建树稠密的事务数据库挖掘算法
• 5.1 FP-Tree的前缀性质
• 5.2 时间效率优先的DFP-Tree构造
• 5.3 算法示例
• 5.4 实验设计及结果分析
• 第六章 改进的大型事务数据库关联规则挖掘算法
• 6.1 条件FP-Tree分析及基于条件FP-Tree的结构分解
• 6.2 算法示例
• 6.3 实验实际及结果分析
• 6.4 算法优缺点及关联规则挖掘流程总结
• 第七章 总结及展望
• 7.1 本文工作总结
• 7.2 进一步研究方向
• 致谢
• 参考文献