关联规则学习（Association rule learning）是一种在大型数据库中发现变量之间的有趣性关系的方法。它的目的是利用一些有趣性的量度来识别数据库中发现的强规则。基于强规则的概念，Rakesh Agrawal等人引入了关联规则以发现由超市的POS系统记录的大批交易数据中产品之间的规律性。。

关联规则学习作为数据挖掘的重要研究方向之一，关联规则学习挖掘的目的是从事务数据集中分析数据项之间潜在的关联关系，揭示其中蕴含的对于用户有价值的模式。一般认为，关联规则挖掘主要由两个步骤组成：(1)从事务数据集中挖掘所有支持度不小于最小支持度阈值的频繁项集；(2)从上一步结果中生成满足最小置信度阈值要求的关联规则。其中，由于具有指数级别的时间复杂度，频繁项集挖掘所消耗的时间往往超过用户可以接受的程度。例如，从销售数据中发现的规则 {洋葱, 土豆}→{汉堡} 会表明如果顾客一起买洋葱和土豆，他们也有可能买汉堡的肉。此类信息可以作为做出促销定价或产品植入等营销活动决定的根据。除了上面购物篮分析中的例子以外， 关联规则如今还被用在许多应用领域中，包括网络用法挖掘、入侵检测、连续生产及生物信息学中。与序列挖掘相比，关联规则学习通常不考虑在事务中、或事务间的项目的顺序。

基于规则中处理的变量类别

关联规则分为布尔型和多值属性型。布尔型关联规则处理的是离散、种类化的数据，它研究项是否在事务中出现; 多值属性关联规则又可分为数量属性和分类属性，它显示了量化的项或属性之间的关系。在挖掘多值属性关联规则时，通常将连续属性运用离散( 等深度桶、部分 K 度完全法) 、统计学方法划分为有限个区间，每个区间对应一个属性，分类属性的每个类别对应一个属性，再对转换后的属性运用布尔型关联规则算法进行挖掘。

基于规则中数据的抽象层次

关联规则分为单层和多层。实际应用中，数据项之间有价值的关联规则常出现较高的概念层中，因此，挖掘多层次关联规则比单层关联规则能得到更深入的知识。根据规则中对应项目的粒度层次，多层关联规则可以划分为同层和层间关联规则。多层关联规则挖掘的两种设置支持度的策略为统一的最小支持度和不同层次设置不同的最小支持度。前者相对而言容易生成规则，但未考虑到各个层次的精度，容易造成信息丢失和信息冗余问题，后者增加了挖掘的灵活性。

基于规则中数据的维数

关联规则分为单维和多维。单维关联规则处理的对象只是一维的; 多维关联规则处理的则是两个或两个以上的变量。根据同一维在规则中是否重复出现，多维关联规则又可分为维内关联规则和混合关联规则1。

先验算法

在计算机科学以及数据挖掘领域中， 先验算法（Apriori Algorithm）是关联规则学习的经典算法之一。先验算法的设计目的是为了处理包含交易信息内容的数据库（例如,顾客购买的商品清单，或者网页常访清单。）而其他的算法则是设计用来寻找无交易信息（如Winepi算法和Minepi算法）或无时间标记（如DNA测序）的数据之间的联系规则。在关联式规则中,一般对于给定的项目集合（例如，零售交易集合，每个集合都列出的单个商品的购买信息），算法通常尝试在项目集合中找出至少有C个相同的子集。先验算法采用自底向上的处理方法，即频繁子集每次只扩展一个对象（该步骤被称为候选集产生），并且候选集由数据进行检验。当不再产生匹配条件的扩展对象时，算法终止。

先验算法采用广度优先搜索算法进行搜索并采用树结构来对候选项目集进行高效计数。它通过长度为 k-1的候选项目集来产生长度为 k的候选项目集，然后从中删除包含不常见子模式的候选项。根据向下封闭性引理,该候选项目集包含所有长度为k的频繁项目集。之后，就可以通过扫描交易数据库来决定候选项目集中的频繁项目集。

虽然先验算法具有显著的历史地位，但是其中的一些低效与权衡弊端也进而引致了许多其他的算法的产生。候选集产生过程生成了大量的子集（先验算法在每次对数据库进行扫描之前总是尝试加载尽可能多的候选集）。

FP-Growth算法

FP-Growth算法采用分而治之的思想，递归地将事务数据集划分为多个更小的条件事务数据集来挖掘频繁项集。同时，采用FP-Tree来表示事务数据集，FP-Tree是一种前缀树的变形，具有较高的压缩性能。FP-Growth算法在执行过程中只需要两次遍历事务数据集，并且不产生候选项集，从而在性能上比Apriori算法快了一个数量级。FP增长算法的运行性能依赖于数据集的压缩因子。如果生成的条件FP树非常茂盛，则算法的性能显著下降，因为算法必须产生大量的子问题，并且需要合并每个子问题返回的结果。在FP-Growth算法挖掘频繁项集的过程中，每一次递归都需要两次遍历FP-Tree。第一次是通过遍历FP-Tree生成条件事务数据集，第二次是根据条件事务数据集建立条件FP-Tree。尽管采用FP-Tree来表示事务数据集具有较高的压缩性能，但是，当FP-Tree所包含的节点数量较多时，遍历FP-Tree所需的时间明显增加。采用FP-Array技术后，每一次递归可以只需要一次遍历，进一步提高了FP-Growth算法的性能。

基于图的关联规则挖掘

图挖掘是指将关联分析用于基于图的数据，在图的集合中发现一组公共子结构，即频繁子图挖掘。根据挖掘的搜索路径频繁子图挖掘算法分为BFS广度优先搜索( broad first search)和DFS 深度优先搜索( depth first search) 两类。基于广度优先搜索算法包括 AGM、FSG。AGM算法基于 Apriori 思想以频繁顶点作为初始集，采用递归方法逐步增加节点来挖掘所有频繁子图。FSG 在 AGM 算法基础上作出了改进，以扩展边代替增加顶点生成候选子图模式，优化了候选子图剪枝策略，提高了计算支持度的速度。针对基于 Apriori 思想的算法产生大量候选子图的缺点，出现了基于 FP-growth 的频繁子图挖掘算法Span、FFSM、close Graph。Yan 等人首次提出了基于深度优先搜索算法Span，算法中对最小 DFS 编码作标记并对其进行最右路扩展，避免复制图的产生以减少冗余。

本词条内容贡献者为: