Sustie

数据分析中的association问题及其算法

问题定义

顾客的交易记录可以用一个$m \times n$的矩阵来表示，如果第$i$个顾客购买了第$j$个商品，矩阵的第$i$行第$j$列就为 1，否则为 0。

接下来定义 3 个新概念：association、support 和 confidence。

一个 association 可以用$X \to Y$来表示，其中$X$和$Y$都是商品的集合，$X \cap Y = \emptyset$。

一个商品集合的 support 是指交易记录中包含这些商品的交易的个数。一个 association 的 support 是指$X \cup Y$的 support。

一个 association 的 confidence 是指$X \cup Y$的 support 除以$X$的 support。

所谓 association 问题就是，给定一个交易记录和两个常数$K_1$和$K_2$，希望找到所有的 association，满足其 support $\ge K_1$且 confidence $\ge K_2$。

算法框架

总的算法可以分成两步：第一步是找到所有满足 support $\ge K_1$的商品集合，第二步是在第一步的基础上再找出满足条件的 association。

这个过程中最困难的是第一步，因为可以证明第一步是 NP-hard 的。

第二步的算法

假设我们已经找到了 support $\ge K_1$的商品集合的集合$S_1$，那么最终结果$S_2$可以表示为：

S_2 = \{ X \to Y \backslash X | X, Y \in S_1 \land X \subsetneq Y \land \\ \text{confidence}(X \to Y \backslash X) \ge K_2 \}

也就是说，枚举$S_1$中的任意两个商品集合$X$和$Y$，如果$X \subsetneq Y$且$X \to Y \backslash X$的 confidence $\ge K_2$，那么就将$X \to Y \backslash X$添加到最终结果的集合中。

第一步的算法：Apriori 算法

假设有$N$个商品，把我们最终要得到的 support $\ge K_1$的商品集合的集合记作$L$（large 的意思）。Apriori 算法的思路是把$L$分拆成$N$个集合$L_1, L_2, \cdots, L_N$，其中$L_i$是$L$中元素个数为$i$的商品集合的集合。Apriori 算法会依次寻找$L_1, L_2, \cdots$，直到$L_N$为止。

要想求出$L_1$是非常容易的，因此接下来只需要解决如何根据$L_i$求出$L_{i+1}$。当然我们可以直接用暴力枚举的方法求$L_{i+1}$，但是这样速度太慢。我们需要考虑如何利用$L_i$更快地求出$L_{i+1}$。

Apriori 算法的核心是利用了以下性质：如果$X \subsetneq Y$，那么$\text{support}(X) > \text{support}(Y)$。根据这个性质，如果$X \in L$，那么其任意子集也必定 $\in L$。

因此，求$L_{i+1}$之前，可以先根据这个必要条件筛选掉一些不可能的商品集合。将筛选后的集合记作$C_{i+1}$（candidate 的意思），则有

C_{i+1} = \{X|\forall a \in X, X\backslash {a} \in L_i \}

上面的公式只是数学描述，实际算法实现可以这么做：首先将$L_i$中的每个商品集合中的商品按照一定顺序排序。然后枚举$X, Y\in L_i$，若$X, Y$只有最后一个商品不同，其他都相同，则检查$X \cup Y$是否满足上述必要条件，若满足则加入$C_{i+1}$中。

求出$C_{i+1}$之后，还要再查询交易记录，看看$C_{i+1}$中哪些是真的满足 support $\ge K_1$的，就可以求出$L_{i+1}$了。

除了上面介绍的 Apriori 算法，还有 FP-Growth 等经典的算法。