关联规则挖掘算法研究

论文摘要

数据挖掘技术是近年来数据库和人工智能等领域研究的热点课题，它引起了科学界和产业界的广泛关注。关联规则挖掘主要用于发现数据集中项之间的相关联系，是数据挖掘最先研究的问题之一，也是数据挖掘的一个主要研究方向。关联规则可以广泛地应用于各个领域，既可以检验行业内长期形成的知识模式，也能够发现隐藏的新规律。有效地发现、理解和运用关联规则，是完成数据挖掘任务的一个重要手段。本文首先对数据挖掘技术进行了较为简单的概括性介绍。然后在介绍关联规则挖掘基本算法—Apriori算法的基础上，对其性能进行了分析，并较详细归纳和分析了已有的一些典型的关联规则挖掘算法。接着介绍了基于关联图的关联规则挖掘算法，对算法性能进行了分析，指出了其存在的缺陷，并提出了两种改进的关联规则高效挖掘算法—基于完全子图的改进算法和基于有序树的改进算法。针对目前已有的关联规则挖掘算法在项目支持度阈值方面的缺陷，提出了项目支持度阈值的设定方法；并在已有的最小约束下的多支持度阈值关联规则挖掘算法的基础上提出了基于树的改进算法；在已有的最大约束下多支持度阈值关联规则挖掘算法的基础上提出了基于完全子图的改进算法。最后针对已有的关联规则挖掘算法在处理批量购买时存在的缺陷，提出了批量关联规则挖掘算法的构想。在基于完全子图的改进算法中，通过利用完全子图与频繁项集的对应关系，以完全子图结点的度作为判断标准，避免了一些不必比较项目之间的比较；同时通过对关联图的结点进行编号，完全避免了相同项目集的重复比较。从而使得在寻找k-项频繁集（k≥3）的过程中，时间复杂度远小于原算法的1／（k-1）。因此，该改进算法减小了存储空间，加快了挖掘速度，提高了算法的效率。在基于有序树的改进算法中，在对项目进行编号的基础上，得到有序的频繁2-项集，根据有序频繁2-项集构造有序频繁树。由于在树的各结点对是有序的，从而完全避免了相同项目集的重复比较。通过实例的分析得到：基于有序树的改进算法的挖掘效率加快了挖掘速度，提高了算法的效率。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 数据挖掘简介
• 1.2 关联规则挖掘简介
• 1.3 关联规则挖掘算法的研究现状
• 1.4 关联规则挖掘研究中存在的问题
• 1.5 本课题的研究内容及研究意义
• 1.5.1 研究内容
• 1.5.2 研究意义
• 第二章 数据挖掘技术
• 2.1 数据挖掘的定义与特点
• 2.2 数据挖掘的支撑技术
• 2.3 数据挖掘的分类
• 2.4 数据挖掘的主要功能
• 第三章 关联规则概述
• 3.1 关联规则的基本概念
• 3.1.1 基本概念
• 3.1.2 关联规则的分类
• 3.2 关联规则挖掘的基本算法—Apriori
• 3.2.1 算法的基本思想
• 3.2.2 Apriori核心算法
• 3.2.3 Apriori性能分析
• 3.2.4 Apriori的改进算法
• 3.3 关联规则挖掘的扩充
• 3.3.1 基于约束的关联规则
• 3.3.2 时态约束关联规则
• 3.3.3 变支持度关联规则
• 3.3.4 多层关联规则挖掘
• 3.3.5 多维关联规则挖掘
• 第四章 基于图论的关联规则算法研究
• 4.1 概念和定理
• 4.2 基于完全子图的关联规则挖掘算法
• 4.2.1 算法思想和步骤
• 4.2.2 算法性能分析
• 4.3 基于完全子图的关联规则挖掘改进算法
• 4.3.1 算法的基本思想
• 4.3.2 算法的具体方法
• 4.4 基于树的改进算法
• 4.4.1 基本概念
• 4.4.2 算法的基本思想
• 4.4.3 构造树的具体方法
• 4.5 实例说明
• 4.5.1 用原算法来寻找频繁项集
• 4.5.2 用基于完全子图的改进算法来寻找频繁项集
• 4.5.3 用基于树的改进算法来寻找频繁项集
• 4.5.4 原算法与改进算法的比较
• 第五章 基于图论的多支持度阈值下的关联规则挖掘算法
• 5.1 项目支持度阈值的设定
• 5.2 最小约束下的多支持度阈值关联规则挖掘
• 5.2.1 MSApriori算法
• 5.2.2 基于树的改进算法
• 5.3 最大限制条件下的关联规则挖掘
• 5.3.1 原算法
• 5.3.2 基于完全子图的改进算法
• 5.3.3 实例说明
• 第六章 批量购买情况下的关联规则挖掘算法
• 6.1 基本概念
• 6.2 算法思想
• 6.3 具体方法
• 结束语
• 致谢
• 参考文献
• 硕士研究生学习期间的研究成果