数据集

基本概念

1. 项集

   购买商品的集合。

2. 频繁项集

   经常出现在一起的商品的集合。

3. 关联规则

   关联规则是形如$X\to Y$$X \rightarrow Y$的表达式，$X$$X$和$Y$$Y$是两个不相交的项集，$X$$X$称为规则前件，$Y$$Y$是规则后件。

评估指标

1. 支持度

   项集$X$$X$（可能是一个商品，也可能是多个商品）出现的概率，公式如下：

   $$\begin{array}{}\text{(1)}& \begin{array}{c}\mathrm{Support}(X)=P(X)=\frac{\mathrm{N}(X)}{\mathrm{N}(AllSamples)}\\ \text{其}\text{中}，\mathrm{N}(X)\text{是}\text{项}\text{集}X\text{在}\text{数}\text{据}\text{集}\text{中}\text{出}\text{现}\text{的}\text{次}\text{数}\\ \mathrm{N}(AllSamples)\text{是}\text{数}\text{据}\text{集}\text{的}\text{总}\text{数}\text{目}\end{array}\end{array}$$

   例如，$X=\{\text{啤}\text{酒}，\text{尿}\text{布}\}$$X = \{啤酒，尿布 \}$

   $\mathrm{Support}(X)=\{\text{啤}\text{酒}，\text{尿}\text{布}\}=\frac{3}{5}=0.6$$\mathrm{Support}(X) = \{啤酒，尿布 \} = \frac{3}{5} = 0.6$

2. 置信度

   在项集$X$$X$出现时，项集$Y$$Y$出现的概率，公式如下：

   $$\begin{array}{}\text{(2)}& \begin{array}{c}\mathrm{Confidence}(X\to Y)=P(Y\mid X)=\frac{\mathrm{N}(XY)}{\mathrm{N}(X)}\\ \text{其}\text{中}，\mathrm{N}(X)\text{是}\text{项}\text{集}X\text{在}\text{数}\text{据}\text{集}\text{中}\text{出}\text{现}\text{的}\text{次}\text{数}\\ \mathrm{N}(Y\mid X)\text{是}\text{在}\text{项}\text{集}X\text{出}\text{现}\text{的}\text{条}\text{件}\text{下}\text{项}\text{集}Y\text{出}\text{现}\text{的}\text{次}\text{数}\end{array}\end{array}$$

   例如，$X=\{\text{尿}\text{布}\}$$X = \{尿布 \}$，$Y=\{\text{啤}\text{酒}\}$$Y = \{啤酒 \}$

   $\mathrm{Confidence}(X\to Y)=P(Y\mid X)=\frac{\mathrm{N}(\{\text{啤}\text{酒},\text{尿}\text{布}\})}{\mathrm{N}(\{\text{尿}\text{布}\})}=\frac{3}{4}$$\large \mathrm{Confidence}(X \rightarrow Y) = P(Y \mid X) = \frac{\mathrm{N}(\{啤酒,尿布\})}{\mathrm{N}(\{尿布\})} = \frac{3}{4}$

3. 提升度

   项集$X$$X$的出现，对项集$Y$$Y$出现的提升程度，公式如下：

   $$\begin{array}{}\text{(3)}& \begin{array}{c}\mathrm{Lift}(X\to Y)=\frac{P(Y\mid X)}{P(Y)}=\frac{P(X,Y)}{P(X)P(Y)}\\ \text{其}\text{中}，P(Y\mid X)\text{指}\text{项}\text{集}X\text{出}\text{现}\text{的}\text{条}\text{件}\text{下}\text{项}\text{集}Y\text{出}\text{现}\text{的}\text{概}\text{率}\\ P(X)\text{指}\text{项}\text{集}X\text{出}\text{现}\text{的}\text{概}\text{率}\\ P(Y)\text{指}\text{项}\text{集}Y\text{出}\text{现}\text{的}\text{概}\text{率}\\ P(X,Y)\text{指}\text{项}\text{集}X\text{和}Y\text{同}\text{时}\text{出}\text{现}\text{的}\text{概}\text{率}\end{array}\end{array}$$

   例如，$X=\{\text{尿}\text{布}\}$$X = \{尿布 \}$，$Y=\{\text{啤}\text{酒}\}$$Y = \{啤酒 \}$

$\mathrm{Lift}(X\to Y)=\frac{P(Y\mid X)}{P(Y)}=\frac{P(\{\text{啤}\text{酒}\})\mid P(\{\text{尿}\text{布}\})}{P(\{\text{啤}\text{酒}\})}=\frac{P(\{\text{啤}\text{酒},\text{尿}\text{布}\})}{P(\{\text{啤}\text{酒}\})P(\{\text{尿}\text{布}\})}=\frac{0.6}{0.6\ast 0.8}=1.25$$\large \mathrm{Lift}(X \rightarrow Y) = \frac{P(Y \mid X)}{P(Y)} = \frac{P(\{啤酒\}) \mid P(\{尿布 \}) }{P(\{啤酒\})} = \frac{P(\{啤酒,尿布 \}) }{P(\{啤酒\}) P(\{尿布\})} = \frac{0.6}{0.6 * 0.8} = 1.25$

Apriori

对于Apriori算法，通常使用支持度作为判断频繁项集的标准，Apriori算法的目标是找到最大的K项频繁集。

Apriori采用迭代的方法寻找最大的K项频繁集。具体如下：

1. 搜索出候选1项集及对应的支持度，剪枝去掉低于支持度阈值的1项集，得到频繁1项集；
2. 对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁2项集；
3. 依次类推，迭代下去，直到无法找到频繁K+1项集为止，对应的频繁K项集的集合即为算法的输出结果。

下图为Apriori算法过程示例：

在该例中，共有4条记录：134、235、1235、25。使用Apriori算法寻找频繁K项集，设最小支持度为0.5。步骤如下：

1. 生成候选频繁1项集，然后计算支持度$C_1$$C_1$，剪枝得到$L_1$$L_1$
2. 基于$L_1$$L_1$进行连接得到原始的$C_2$$C_2$，然后计算$C_2$$C_2$的支持度，剪枝后得到$L_2$$L_2$
3. 基于$L_2$$L_2$得到频繁3项集$C_3$$C_3$，然后计算$C_3$$C_3$的支持度，得到$L_3$$L_3$
4. 由于无法再进行连接得到频繁4项集，最终的结果即为频繁3项集235

参考文档

1. Apriori算法原理总结 - 刘建平Pinard - 博客园 (cnblogs.com)
2. 实战：关联规则挖掘 - 知乎 (zhihu.com)
3. 第一部分 关联规则实战分析 1-关联规则概述哔哩哔哩bilibili