关联规则学习是一种在大型数据库中发现变量之间的有趣关系的方法。它的目的是利用一些有趣的量度来识别数据库中发现的强规则。关联规则被广泛应用于购物篮分析、网络用法挖掘、入侵检测、连续生产及生物信息学。
关联规则（英语：Association Rule）是数据挖掘中的一种发现变量之间有趣关系的手段和方法，它主要的用途是发现数据之间的关联性和强规则。简单来讲，当某类别数据或某个模式在数据集中出行的频率增大时，自然大家都会认为其肯能会更为常见或重要。那么，如果发现两个或多个类别数据同时出现，自然就可以认为其相互之间存在联系或规则。
关联规则最典型的例子就是用于购物篮分析。一些商家发现当顾客购买商品 A 的时候，很容易同时购买商品 B，于是就可以因此调整商品的摆放位置或变换定价策略。这里有一个关于 啤酒和尿布 的故事：大意是一家大型超市的销售团队发现，每周五下午购买尿布的年轻美国男性也有购买啤酒的倾向，于是每周五都会将一个尿布货架放置在啤酒货架旁边，结果是二者的销量都有所上升。
基础 #
频繁项集 #
\(I=\{i_1, i_2, ..., i_m\}\)那么，我们称其中的 i1,i2,…,im 为集合的项 Item，而 I 自然被称之为项 Item 的集合。
此时，若集合 S 满足 \(S=\{i|i∈I\}\) 则 S 被称之为 I 的项集 Itemset。其中，包含 K 个项的项集称为 K-项集。
而频繁项集则表明一个项集出现很「频繁」。从直观的角度理解，你应该会认为对频繁项集的挖掘是有意义的，就例如上面的「啤酒和尿布」，因为它们出现的频率很高，最终我们就可以通过调整销售规则来获益。 但是，如何去衡量频繁项集中的「频繁」呢？达到怎样的程度才能被称之为「频繁」呢？而关联规则的强度可以用它的支持度（support）和置信度（confidence）度量。
支持度 #
支持度 support 用来衡量事件发生的频率。 \( support(X \to Y) \) 则表示项集 \( \{X,Y\} \) 在总项集 I 里出现的频率，记作：
\(support(X \to Y) = P(X∪Y) = \frac{num(XUY)}{num(I)}\)如果项集的支持度超过预先设定的最小支持阈值，则认为该项集可能是有用的，也就被称之为「频繁项集」。
置信度 #
置信度 confidence 用来表示在 X 出现情况下，出现 Y 的可能性，其公式为：
\(confidence(X \to Y) = P(Y|X)= \frac{support(X → Y)}{support(X)}\)有了支持度和置信度之后，频繁项集就可以被扩展为关联规则了。也就是说如果我们有一条规则如下：
啤酒尿布
\(support(啤酒→尿布) = 10\%\)啤酒尿布
\(support(啤酒→尿布) = 60\%\)即表示，在超市的销售记录中。有 10% 的顾客的购物车中出现了啤酒和尿布的组合。同时，购买啤酒的顾客有 60% 的几率会购买尿布。关联规则的左侧是确定项，称作先导。右侧是结果项，称作后继。
Apriori 算法 #
我们通常使用「格结构」来枚举数据集可能存在的项集。如下方格结构图所示，牛奶，咖啡，啤酒组成的数据集可能产生的项集如下：
由牛奶，咖啡，啤酒组成的数据集中，可能产生 7 个候选项集（包含单个项组成的项集）。推广到一般情况，则包含 n 个项的数据集，可能产生 2**n - 1 个候选项集。
Apriori 算法最先于 1994 年在论文 Fast algorithms for mining association rules in large databases 中首次出现，它也是关联规则挖掘中最常用的方法。
Apriori 先验原理说起来非常简单，它主要是告诉我们 2 条定理，即：
- 定理 1：如果一个项集是频繁项集，那么其所有的子集也一定是频繁项集。
- 定理 2：如果一个项集是非频繁项集，那么其所有的超集也一定是非频繁项集。
用 Apriori 算法产生频繁项集算法过程如下：
-
算法一次扫描整个数据集，计算每个项的支持度，并得到频繁 1 项集的集合 \( F_1 \)
-
算法使用频繁 \( k - 1 \) 项集产生候选 \( k \) 项集，可以使用 \( F_{k-1} \times F_{k-1} \) 或 \( F_{k-1} \times F_{1} \) 方法。
-
算法再次扫描数据集对候选项集完成支持度计数，并使用子集函数确定在 \( C_k \) 中的全部候选 \( k \) 项集。
-
计算候选项集的支持度，并删去支持度小于预先设定阈值的候选项集。
-
当没有频繁项集产生，即 \( F_k = \emptyset \) 时，算法结束。
可以参考 Apriori 实例理解