基于位运算的闭频繁项集挖掘算法的研究

摘要

在信息技术高度发达的今天，现实生活和商业应用中积累了大量历史数据，而且这些数据正呈爆炸式增长。海量的历史数据既蕴含着大量宝贵资源，同时也把我们淹没在数据和信息的汪洋大海里。为了从中找到潜在的、有价值的信息，数据挖掘技术应运而生，并显示出强大的生命力和巨大的发展潜力。频繁模式挖掘在数据挖掘任务中一直充当着重要的角色，频繁模式挖掘是一个相对耗时的过程，而且可能会产生大量的频繁模式项，挖掘频繁闭模式比频繁模式数量上要少，但是却能表达相同的信息。
　　 频繁项集挖掘做为关联规则产生的首要步骤，其挖掘效率的高低直接关系着关联规则产生的总体效率。本文将位处理技术运用到二维闭频繁项集挖掘和三维闭频繁项集挖掘过程中，对数据集和项集按位存储，通过充分利用计算机每次处理32位数据的特性，最大限度的提高每次运算处理数据集的数据量，从而提高闭频繁项集挖掘的效率。
　　 本文在对现有的各种二维频繁项集挖掘算法和三维频繁项集挖掘算法优缺点进行分析比较的基础上，对枚举策略和剪枝策略进行优化，设计出更加高效的基于位运算的二维闭频繁项集挖掘算法BD-Miner和基于位运算的三维闭频繁项集挖掘算法BD-Peeler，使得算法既继承了现有算法的优点，又能更高效的完成挖掘任务。
　　 本文使用VC++6.0实现了算法BD-Miner和BD-Peeler，在多个数据集上做了大量实验，并与现有算法进行了比较，实验结果表明：在相同数据集上完成相同约束条件的闭频繁项集的挖掘任务，二维数据集上BD-Miner算法能提升挖掘效率6-7倍，三维数据集上BD-Peeler算法能提升挖掘效率3倍。

目录

文摘

英文文摘

1 绪论

1.1 研究背景及意义

1.2 研究内容

1.3 论文组织结构

2 数据挖掘概述

2.1 数据挖掘的概念

2.2 数据挖掘的功能

2.3 频繁项集挖掘概述

2.3.1 频繁项集

2.3.2 最大频繁项集

2.3.3 闭频繁项集

2.4 经典频繁项集挖掘方法

2.4.1 Apriori算法

2.4.2 FP-growth算法

2.5 本章小结

3 位运算

3.1 集合与二进制的关系

3.2 集合二进制表示的运算

3.2.1 集合交集

3.2.2 集合并集

3.2.3 集合子集判断

3.2.4 集合第i个域值元素包含判断

3.2.5 集合加入第i个域值元素

3.2.6 集合移除第i个域值元素

3.2.7 集合移除第1个集合元素

3.2.8 集合元素个数

3.3 本章小结

4 基于位运算的二维闭频繁项集挖掘算法

4.1 二维频繁项集挖掘现状

4.2 相关定义

4.3 数据集存储结构

4.4 BD-Miner算法

4.4.1 二元枚举策略

4.4.2 剪枝左结点

4.4.3 封闭性剪枝

4.5 实验结果及分析

4.5.1 算法有效性验证

4.5.2 算法效率

4.6 本章小结

5 基于位运算的三维闭频繁项集挖掘算法

5.1 三维频繁项集挖掘现状

5.2 相关定义

5.3 BD-Peeler算法

5.3.1 二元枚举策略

5.3.2 剪枝左结点

5.3.3 封闭性优化策略

5.4 空间复杂性

5.4.1 数据集存储结构

5.4.2 枚举树结点存储结构

5.5 实验结果及分析

5.5.1 算法有效性验证

5.6 本章小结

6 总结及进一步工作展望

6.1 论文总结

6.2 工作展望

参考文献

个人简历

攻读硕士学位期间的研究成果

致谢