基于位运算的关联规则挖掘算法问题研究

摘要

随着计算机技术的快速发展,各类应用系统中积累的数据不断增长。为了进一步利用数据,从大规模数据中发现某些有规律或有价值的信息,数据挖掘技术应运而生。关联规则挖掘是数据挖掘研究领域的重要问题之一,主要用于发现隐藏在数据之间的潜在联系。由于其应用的广泛性,一直是被广泛关注的研究问题。
　　目前,针对关联规则挖掘算法,国内外学者已经取得了大量的研究成果。然而,传统的关联规则挖掘算法仍然存在一些不足:
　　(1)处理数据速度不高,求解支持度过程较慢;
　　(2)在频繁项集挖掘过程中,会产生较多的候选频繁项集,对于大型稠密数据集,将导致内存严重不足。
　　针对以上问题,本文分别以稀疏数据集和稠密数据集作为研究对象,开展相关研究。本文的主要工作及贡献如下:
　　(1)提出一种基于先验位运算的频繁项集挖掘算法。
　　针对支持度求解过程较慢的问题,本文提出一种基于先验位运算的频繁项集挖掘算法。该算法首先将数据转换为垂直数据格式,并利用二进制方式存储到二维数组;其次,使用k-1频繁项集组合成为k-候选项集;接着,对候选项集进行“剪枝”操作;最后,利用深度优先搜索算法确定所有的频繁项集。实验结果表明,该方法可以有效地简化支持度计算,提高算法效率。
　　(2)提出一种基于差集的频繁项集挖掘算法。
　　针对传统频繁项集挖掘算法会产生较多候选中间项集的问题,本文提出了一种基于差集的频繁项集挖掘算法。该算法首先使用位运算方式计算出所有1-项集的支持度;然后,根据2-项集的diffset形式分成若干群,从而获得较高的内存利用率;最后,从不同的分群里面产生k-项集(k>2),该操作可以有效减少判断项集是否频繁的时间。实验结果表明,该算法有效地减少了频繁候选项集的产生数量,提高了内存的使用效率。
　　本文提出的两个算法,分别从简化支持度计算以及提高内存利用率的角度,有效地改善了传统频繁项集挖掘算法的效率。

目录

封面

声明

目录

中文摘要

英文摘要

第一章 绪论

1.1 研究背景及意义

1.2 频繁项集挖掘面临的问题

1.3 本文工作及创新点

1.4 本文的组织框架

第二章 相关研究工作

2.1数据挖掘综述

2.2 关联规则挖掘

2.3 小结

第三章 基于先验位运算的频繁项集挖掘算法

3.1 相关概念

3.2基于先验位运算的频繁项集挖掘（A-FIMBII）

3.3 算法分析

3.4实验

3.5 小结

第四章 基于差集的频繁项集挖掘算法

4.1相关概念

4.2 基于差集的频繁项集挖掘算法（D-FIMBII）

4.3 算法示例

4.4实验

4.5小结

第五章 总结与展望

5.1 总结

5.2 展望

参考文献

攻读硕士期间发表学术论文及参与项目情况

致谢