基于压缩矩阵的关联规则挖掘算法的改进研究

摘要

随着信息技术的发展，数据信息呈现爆炸式的增长。为了从海量数据中获取有用的信息，数据挖掘成为当今数据库研究方面最具活力的领域。关联规则挖掘是数据挖掘领域一个重要的研究方向，这项技术广泛应用于各大领域，有着极其重要的应用价值。随着数据集的大小和复杂性的增长，如何提高关联规则挖掘算法对大规模数据集的挖掘效率成为关联规则挖掘研究的核心问题。经典的关联规则挖掘算法Apriori算法是当前关联规则挖掘算法研究的热点。基于矩阵的Apriori算法相比Apriori算法减少了扫描数据库的次数，提高了计算支持度计数的效率，但仍然存在候选集过多，矩阵占用内存空间过大等问题。本文针对已有的基于矩阵的Apriori算法的不足，提出了一种改进的基于压缩矩阵的Apriori算法----NCMA。
　　 本研究主要内容包括：⑴首先了解关联规则挖掘算法的背景和发展现状，重点探讨了Apriori算法及其改进算法的优缺点，分析了现有基于Apriori的改进算法存在的问题。⑵详细分析了基于矩阵的Apriori算法及其改进算法，发现改进的基于矩阵的Apriori算法仍然存在多次扫描矩阵、为减少候选集数量增加过多额外计算时间、矩阵压缩得不够彻底、挖掘结果的精确度不高、算法设计过于复杂等问题。⑶针对不足之处，提出一种改进的基于压缩矩阵的Apriori算法----NCMA。算法从矩阵存储、项集排序、矩阵压缩、支持度计数的计算、算法结束条件五个方面进行改进，并通过实例分析证明算法的正确性。⑷将NCMA算法和Apriori算法、CM_Apriori_1算法从理论上和实验上进行分析比较，理论和实验结果都证明了NCMA算法能有效地减少扫描矩阵的次数，大大压缩了矩阵规模，减少了候选项集的数目，提高了挖掘频繁项集的效率。该算法在挖掘密集型数据库时比现有的基于矩阵的Apriori算法具有更高的运行效率和可伸缩性。

目录

声明

摘要

第一章 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．2．1 经典的关联规则挖掘算法

1．2．2 基于Apriori的改进算法

1．2．3 分布式关联规则挖掘算法

1．3 论文的研究内容与主要工作

1．3．1 论文研究的目标与内容

1．3．2 论文需解决的关键技术问题

1．4 论文的组织结构

第二章 关联规则挖掘技术

2．1 关联规则相关概念

2．2 关联规则相关算法

2．3 Apriori算法及其改进

2．3．1 Apriori算法原理

2．3．2 Apriori的相关性质

2．3．3 相关改进算法分析

2．4 本章小结

第三章 一种改进的基于压缩矩阵的Apriori算法

3．1 基于矩阵的Apriori算法

3．1．1 相关定义

3．1．2 算法描述

3．1．3 算法的分析

3．2 算法的改进思想

3．2．1 矩阵存储

3．2．2 项集排序

3．2．3 矩阵压缩

3．2．4 支持度计数的计算

3．2．5 算法结束条件

3．3 算法的描述

3．3．1 具体步骤描述

3．3．2 伪代码描述

3．4 算法的实例分析

3．5 本章小结

第四章 算法分析与对比实验

4．1 理论分析

4．1．1 Apriori算法复杂度分析

4．1．2 CM_Apriori_1算法复杂度分析

4．1．3 NCMA算法复杂度分析

4．1．4 算法复杂度比较

4．2 实验对比结果与性能分析

4．2．1 实验准备

4．2．2 不同事务数数据库的对比实验

4．2．3 不同支持度同一数据库的对比实验

4．2．4 不同项目数数据库的对比实验

4．2．5 不同密集度数据库的对比实验

4．2．6 实验结论

4．3 本章小结

第五章 结论与展望

5．1 本文的工作总结

5．2 研究的不足与进一步展望

参考文献

附录

致谢

攻读硕士学位期间发表、完成的学术论文