关联规则反映一个事物与其它事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物发生就能够预测与它相关联的其它事物的发生。比如经典的购物篮事务(market basket transaction)，通过顾客放入购物篮中商品之间的同现关系(co-occurrence)来分析顾客的购买习惯，实现商品的交叉销售和推荐。

从上面的数据中我们可以提取如下的规则：

$$\{ \text{尿布} \} \rightarrow \{ \text{啤酒} \}$$

这表明尿布和啤酒的销售关系存在很强的联系，因为许多购买尿布的顾客也购买了啤酒，零售商可以利用这类规则，帮助他们发现新的商机。

那我们如何提取出这样的关联规则呢？

---

基本概念

• 项集，支持度计数，频繁项集

---

• 关联规则，支持度，置信度

---

举个简单例子，熟悉下公式。

考虑关联规则： $\{Milk,Diaper\} \Rightarrow Beer$，

$$\begin{align*} s & = \frac{\sigma(Milk,Diaper,Beer)}{|T|} = \frac{2}{5} = 0.4\\ c & = \frac{\sigma(Milk,Diaper,Beer)}{\sigma(Milk,Diaper)} = \frac{2}{3} = 0.67 \end{align*}$$

这里面还有一个小 trick， 下面的关联规则都源自于同一个项集 $\{ \text{啤酒，尿布，牛奶} \}$，它们都有相同的支持度。当我们的项集 $\{ \text{啤酒，尿布，牛奶}\}$ 为非频繁，我们可以立即剪掉这6条候选规则，而不必计算其置信度。

---

关联规则挖掘

大多数关联规则挖掘算法都可以分为两个主要步骤：

• 频繁项集产生：其目标是发现满足最小支持度阈值的所有项集(frequent itemset).
• 规则提取：从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称为强规则(strong rule).

一般来说，一个包含 $k$ 个项的数据集可能产生 $2^k-1$个频繁项集（不包括空集），提取的可能规则总数为 $R = 3^k-2^{k+1}+1$，太庞大了。

---

最直接的思路，

---

Apriori算法

Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。

性质1：频繁项集的子集必为频繁项集。
性质2：非频繁项集的超集一定是非频繁的。

Apriori算法运用性质1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁 k 项集的集合 $C_k$ 是指由有可能成为频繁 k 项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。

---

算法流程，

---

---

---