基本背景
关联分析的目的可以看做是要找到经常出现的产品组。形式化地说，给定\(p\)个不同的物品，编号为\(\{1,\ldots , p\}\)，以及一些这些物品子集\(X_n \subset \{1,\ldots, p\}\)构成的集合，假设\(X_n\)是顾客\(n=1,\ldots, N\)购买的物品，关联分析的目的是找到经常同时出现的物品，例如，如果\(\mathcal{K} \subset \{1,\ldots,p\}\)是经常同时出现的物品，则应有 \[ P(\mathcal{K}) = \frac{\#\{n{\rm\ such\ that\ }\mathcal{K} \subseteq X_n\}}{N} \] 很大。而关联规则意味着购买\(A\)增加了用户购买\(B\)的概率
可以将每个顾客篮子里的物品编号，然后顾客篮子里的物品就可以用一个0-1数组来表示。例如，若面包编号为1，牛奶编号为2，尿布编号为3，则若顾客1买了面包和牛奶，ta的篮子可以表示为[1,1,0]；若顾客2买了面包和尿布，ta的篮子可以表示为[1,0,1]
一个直观的想法是，可以使用穷举法找出所有出现概率超过某个阈值的物品组合。但是，当顾客数量\(N\)和商品数量\(p\)都很大时，搜索空间呈指数级增长：\(\mathcal{K} \subseteq \{1,\ldots, p\}\)一共有\(2^p\)个子集，即便把子集中元素数控制在至多\(k\)个，那么也有\(p \choose k\)个组合。当\(p=10^4\)，\(k=5\)时，\({p \choose k} \approx 10^{18}\)
在探讨有效的计算方法之前，需要先看三个术语。令\(\mathcal{K} \subset \{1,\ldots,p\}\), \(A, B\subset \mathcal{K}\)且有$A B = , A B = $，我们对三个经验概率值非常有兴趣：
- 支持度 (support): \(P(\mathcal{K}）= P(A, B)\)，即我们要看哪些组合经常出现
- 信任度 (confidence): \(P(B|A) = P(\mathcal{K})/P(A)\)，即篮子中\(A\)已出现时出现\(B\)的概率。通过该值定义规则\(A \Rightarrow B\)
- 规则\(A \Rightarrow B\)的提升度 (lift): \(L(A, B) = \frac{P(A,B)}{P(A)P(B)} = P(B|A)/P(B)\)，即当我们看到篮子里有\(A\)时篮子里有\(B\)的信任度提升了多少
例如，令\(\mathcal{K}\)为花生酱、果酱和面包组成的集合，\(A\)包含花生酱和果酱，\(B\)只包含面包，则
- 支持度0.03意味着这三样物品在3%的篮子中同时出现
- 信任度0.82意味着如果一个人的篮子里已经有了花生酱和果酱，那么82%的情况下还会ta还会买面包
- 提升度1.95意味着如果一个人买了花生酱和果酱，则购买面包的概率是原来的1.95倍
频繁性依赖与Apriori算法
算法
Apriori算法的目标是快速找到所有出现概率大于预定阈值\(t\)的子集\(\mathcal{K} \subset \{1,\ldots,p\}\)。其算法的基础是频繁性依赖，即
- 如果集合\(\mathcal{K}\)出现的次数不够频繁，那么\(\mathcal{K}' = \mathcal{K} \cup A\ (A \subset \{1,\ldots, p\})\)也不够频繁。即\(P(\mathcal{K}) < t \rightarrow P(\mathcal{K}') < t\)。其数学解释为\(P(\mathcal{K}') = P(\mathcal{K}, A) = P(A|\mathcal{K})P(\mathcal{K}) \le P(\mathcal{K}) < t\)
- 反之，如果有\(P(\mathcal{K}) > t\)且\(A \subset \mathcal{K}\)，则\(P(A) > P(\mathcal{K}) > t\)
Apriori算法 设定阈值\(N\cdot t\)，其中\(0 < t < 1\) 1. \(|\mathcal{K}|= 1\)：遍历所有物品，保留那些在\(\ge N \cdot t\)个篮子里出现物品 2. \(|\mathcal{K}|= 2\)：遍历所有在上一步中保留的物品构成的物品对，保留那些在\(\ge N \cdot t\)个篮子里出现的物品对 \(\vdots\) 3. \(|\mathcal{K}|= k\)：遍历所有出现在\(\ge N \cdot t\)个篮子里出现的，长度为\(k-1\)的物品集，逐个加入在第一步留下的物品，保留所有在\(\ge N \cdot t\)个篮子里出现的集合
寻找关联规则
找到所有满足\(P(\mathcal{K})>t\)的\(\mathcal{K}\)以后，需要去挖掘关联规则，即将\(\mathcal{K}\)分割成两个不相交集合\(A\)和\(B\)以后，找到所有\(P(A|B)>t_2\)的\(A\)和\(B\)。由于\(P(A|B) = P(\mathcal{K})/P(B)\)，且若\(P(\mathcal{K})>t\)和\(A\)和\(B\)是\(\mathcal{K}\)的划分，就有\(P(A)>t\)及\(P(B)>t\)，而后两者在找所有\(P(\mathcal{K})\)时已被计算过，因此不用再重复计算\(P(A|B)\)
