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

摘要

随着计算机科学与技术的进步，信息技术领域在最近几十年得到了迅猛发展，人们使用信息技术手段在各领域均产生并积累了海量数据，由于数据量以及维度巨大，传统的数据分析方法已经并不奏效，此时，数据挖掘技术应运而生。数据挖掘是从海量的实际应用数据中，挖掘出隐藏的、难以用普通手段发现的，但对现实生活中某些领域的应用具有实际价值的信息的过程。数据挖掘的主要任务之一关联规则的作用在于揭示项集之间的有趣联系，已广泛应用于市场营销、医学、金融、生物等各个领域。FP-growth算法作为关联规则挖掘算法中的一个经典算法，由于不需要产生候选项集，运行效率较Apriori算法有了一定程度上的提高，从而得到了广泛应用。
　　本文针对FP-growth算法产生FP-tree太多、太大，占用内存太多，以及向本地及数据库服务器申请查询重复数据给数据库服务器增加负担的问题，提出了NFP-growth算法。NFP-growth算法通过构造基于支持度二维表的方式存放各项的支持度计数，并且采用基于频繁项集划分的思想，分别得到每个频繁项的数据库子集并从二维表中获取支持度直接构造条件FP-tree，挖掘以该项为结尾的频繁项集。减少了FP-tree的产生数量并将经典FP-growth算法在此过程中遍历每项前缀路径的次数由2次减少为1次。
　　针对FP-growth算法产生频繁项集的过程中会产生大量大于支持度阈值，但人们并不感兴趣的频繁项集的问题，本文在第四章提出的NFP-growth算法的基础上进一步提出了KNFP-growth算法。KNFP-growth算法在NFP-growth算法中融合了关键项抽取KEEP-growth算法的思想，通过划分关键项表和非关键项表，在构造每一项的条件FP-tree后，使用KEEP-growth算法代替FP-growth算法挖掘频繁项集，依靠关键项表的约束，仅输出包含关键项的频繁项集，消除了无意义的频繁项集的挖掘。

目录

封面

声明

中文摘要

英文摘要

目录

1绪论

1.1 研究背景

1.2 研究目的和意义

1.3 研究现状分析

1.4 本文主要工作

1.5 论文组织结构

2数据挖掘概述

2.1数据挖掘的基本概念

2.2数据挖掘的过程

2.3数据挖掘的主要任务

2.4数据挖掘的研究现状

2.5数据挖掘的未来研究方向和热点

2.6本章小结

3关联规则挖掘理论与算法

3.1 关联规则的基本概念

3.2 关联规则的挖掘步骤

3.3 关联规则挖掘分类

3.4 经典算法分析

3.5本章小结

4基于FP-growth算法的NFP-growth算法

4.1NFP-growth算法思想

4.2NFP-growth算法描述

4.3实例分析

4.4算法性能对比

4.5本章小结

5结合KEEP-growth算法的KNFP-growth算法

5.1KNFP-growth算法思想

5.2KNFP-growth算法描述

5.3实例分析

5.4算法性能对比

5.5本章小结

6总结与展望

6.1本文总结

6.2未来展望

参考文献

致谢

个人简历、在学期间发表的学术论文