大规模数据库关联规则挖掘算法研究

论文摘要

数据挖掘是致力于数据分析和理解、揭示数据内部蕴藏知识的技术，它成为未来信息技术应用的重要目标之一。经过十几年的努力，数据挖掘领域产生了许多新概念和方法。特别是最近几年，一些基本概念和方法趋于清晰，它的研究正向着更深入的方向发展。像其它新技术的发展历程一样，数据挖掘技术也必须经过概念提出、概念接受、广泛研究和探索、逐步应用和大量应用等阶段。从目前的现状看，大部分学者认为数据挖掘的研究仍然处于广泛研究和探索阶段，迫切需要在基础理论、应用模式、系统构架以及挖掘算法和挖掘语言等方面进行创新。关联规则挖掘是数据挖掘领域中成果颇丰而且比较活跃的研究分支，留给研究者的是更深入的课题。随着数据库规模的日益增大，关联规则挖掘需要在挖掘效率、可用性、精确性等方面得到提升。因此，需要探索新的挖掘理论和模型；需要对一些传统的算法进行改进；也需要研究新的更有效的算法。鉴于目前数据挖掘技术和关联规则挖掘研究的现状和发展趋势，我们选择了这一课题开展相关工作。本文在分析、归类现有关联规则算法研究成果的基础上对大规模数据库关联规则挖掘算法进行了研究，所设计的新算法在挖掘效率和对大规模数据库挖掘的可用性方面具有潜在的应用前景。主要研究工作体现在以下三个方面：1、针对经典Apriori算法对大型交易事务数据库挖掘关联规则时的瓶颈问题，本文提出了一种新的基于矩阵的关联规则挖掘算法—BOM（Base On Matrix）算法。该算法使用矩阵来表示基础数据，并且通过矩阵的直接运算直接得到频繁k-项集，避免了生成大量的候选项集，提高了对大型交易数据库的处理效率。该算法不同于经典的Apriori算法，对于大型交易事务数据库，具有较Apriori算法更加优越的性能。2、扫描大规模数据库是非常耗时的，针对大多数关联规则并行挖掘算法需要扫描数据库至少两次，严重影响了算法的效率的问题，我们提出了一种新的基于共享存储多处理机模型，更有效的并行算法—SO（Scan Once）算法。SO算法仅扫描数据库一次，并且采用了不同于著名的并行算法CD算法的设计思想，理论分析表明SO算法具有较好的性能。3、现有的大部分关联规则挖掘算法对整个数据库的各个属性的数据样本采用单一的支持度来找出符合的关联规则，导致无法高效地发现有价值的稀有数据。本文在无向项集图的基础上，结合RSAA算法，提出了一种新的关联规则挖掘算法，采用多支持度的方法来发现数据库中有价值的稀有数据。通过将该算法与RSAA算法的分析比较，证明了其在获得有价值的稀有数据的效率以及得到规则的可用性方面具有更好的性能。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 数据挖掘概述
• 1.2 关联规则挖掘概述
• 1.2.1 大规模数据库关联规则挖掘研究的意义
• 1.2.2 大规模数据库关联规则挖掘算法研究现状
• 1.2.3 大规模数据库关联规则挖掘目前面临的主要问题
• 1.3 创新性工作
• 1.4 本文组织
• 第二章 关联规则挖掘
• 2.1 基本概念
• 2.2 关联规则挖掘问题
• 2.3 关联规则的种类
• 第三章 关联规则挖掘算法研究
• 3.1 关联规则挖掘的串行算法
• 3.1.1 Apriori算法
• 3.1.2 Apriori算法的性能瓶颈问题
• 3.1.3 其它具有代表性的串行挖掘算法
• 3.2 关联规则挖掘的并行算法
• 3.2.1 并行计算概论
• 3.2.1.1 并行计算机
• 3.2.1.2 并行算法
• 3.2.1.3 并行计算模型
• 3.2.1.4 并行算法的设计环境
• 3.2.1.5 并行算法的一般设计过程
• 3.2.2 几种用于发现频繁项目集的并行算法
• 3.2.2.1 进行候选集复制的算法
• 3.2.2.2 划分候选集的算法
• 3.2.2.3 混合策略:对于候选集的部分复制
• 3.2.3 并行算法面临的挑战
• 3.3 小结
• 第四章 三种新的关联规则挖掘算法
• 4.1 引言
• 4.2 BOM算法
• 4.2.1 算法设计
• 4.2.2 算法正确性
• 4.2.3 一个例子
• 4.2.4 BOM算法与Apriori算法的比较
• 4.3 SO算法
• 4.3.1 计算模型
• 4.3.2 算法设计
• 4.3.3 算法的正确性
• 4.3.4 一个例子
• 4.3.5 比较SO算法和CD算法
• BUIG算法'>4.4 RS_BUIG算法
• 4.4.1 相关研究
• 4.4.1.1 BUIG算法
• 4.4.1.2 RSAA算法
• BUIG算法'>4.4.2 RS_BUIG算法
• 4.4.2.1 算法内容
• 4.4.2.2 一个例子
• 4.4.3 算法性能比较分析
• 4.5 小结
• 第五章 总结与展望
• 参考文献
• 致谢
• 攻读硕士学位期间发表的论文和参与的项目