关联分析

人们在购物时，有些东西往往是捆绑购买的，如果我们想要通过客户的购物记录挖掘出捆绑消费的物品并将这些物品摆放在一起，可以显著提升商品的销售量，那么如何挖掘出这样的捆绑关系呢？本章我们学习一种无监督学习方法：关联分析。一般来说购买了某个物品是一个很重要的事情，因此购物记录的属性全都是非对称二元属性。本章最后再补充一下序列的关联分析。

基本概念

基本定义：

• 某一个属性称为 项 Item；

• 一些属性的集合称为 项集 Itemset；

• 关联分析的数据集称为事务集，其中每一行表示一个 事务 transaction；

  Warning

  事务和项集并不是一回事。事务可以看做一条实际的购物记录，表示某个顾客买了哪些东西；而项集一般是人为定义的某些商品的集合，比如我想要挖掘尿布和啤酒的关系，我就定义一个项集其中包含尿布和啤酒两项。

• 对于一个项集 \(X\)，事务集中包含 \(X\) 的个数就叫做 \(X\) 的 支持度 \(\sigma (X)\)，若 \(\sigma (X)\) 超过了某个阈值，则称 \(X\) 为 频繁项集。

强关联规则定义：

• 对于两个不相交的项集 \(X,Y\ (X \cap Y=\empty)\)，用 \(X\to Y\) 表示一个关联规则，其中 \(X\) 记作前件，\(Y\) 记作后件；

• 关联规则 \(X\to Y\) 的支持度 support \(s(X\to Y)=\frac{\sigma(X\cup Y)}{N}=P(X\cup Y)\)；

• 关联规则 \(X\to Y\) 的置信度 confidence \(c(X\to Y)=\frac{\sigma(X\cup Y)}{\sigma(X)} = P(Y\ |\ X)\)；
• 若 \(X \to Y\) 的支持度 \(s\) 和置信度 \(c\) 同时超过了对应的阈值，则称 \(X \to Y\) 是一个 强关联规则。

关联分析的任务：

• 在给定事务集、支持度阈值和置信度阈值的情况下，找到所有的强关联规则。

• 显然可以直接枚举 \(X\to Y\) 的所有关联规则然后进行支持度检测和置信度检测。对于一个含有 d 个项的事务集，可能的关联规则总数为：

  \[ 3^d - 2^{d+1} + 1 \]

• 上式可以通过组合数学得来，就不说了。显然，指数复杂度是不能接受的，并且同时符合支持度阈值和置信度阈值的关联规则很少，很多计算都是无效的。

• 尝试优化。不难发现，对于一个强关联规则 \(X \to Y\)，项集 \(\{X,Y\}\) 一定是一个频繁项集。也就是说我们可以先进行支持度检测找到所有的频繁项集，接着对于每一个频繁项集，将其中的项划分到前后件进行置信度检测。这样就可以更快速的挖掘出所有的强关联规则。（这种优化策略可以通俗的理解为：原本的暴力方法就是 n 层 for loop，现在使用一个 set 来维护 n/2 层 for loop 的计算结果，然后再用 n/2 层 for loop 来计算 set 中的信息）。

下面按照优化的思路，分别介绍支持度检测算法和置信度检测算法。

支持度检测

下面分别介绍三种支持度检测算法来寻找事务集中所有的频繁项集。

Apriori 算法

1）先验知识

一个频繁项集的子集一定也是频繁项集，一个非频繁项集的超集也一定是非频繁项集。

2）算法流程

1. 扫描一遍事务集得到频繁 1 项集；
2. 利用频繁 1 项集产生候选 2 项集；
3. 在第二步产生的候选项集中通过支持度阈值筛选出频繁项集；
4. 重复二、三直到找不到频繁 k 项集，结束循环。

3）算法核心

该算法的核心就在二、三两步。下面分别介绍：

• 对于第二步，需要利用「频繁 \(k\) 项集」产生「候选 \(k+1\) 项集」。可以通过以下两步来加速产生过程，具体的：

  1. 连接步。双重 for loop 寻找匹配的两个 \(k\) 频繁项集并连接产生一个候选 \(k+1\) 项集，这里的匹配指的是这两个 \(k\) 频繁项集「有 \(k-1\) 项是相同的且有 \(1\) 项是不相同的」；

  2. 剪枝步。在连接步得到所有的候选 \(k+1\) 项集后，并不是直接就到第三步的支持度计数了，这里还可以进行剪枝，即过滤掉一部分的候选 \(k+1\) 项集。而剪枝方法就可以用到一开始提到的先验知识「一个非频繁项集的超集也一定是非频繁项集」，即如果当前候选 \(k+1\) 项集中包含了非频繁 \(k\) 项集，那么它就不可能是频繁 \(k+1\) 项集。因此我们可以检查当前候选 \(k+1\) 项集中所有的 \(k\) 项子集是否都存在于频繁 \(k\) 项集中，只要有一个子集不存在，那么当前的候选 \(k+1\) 项集就不可能是频繁的，直接删除即可。（其实都挺显然的，只不过用语言描述起来挺费劲）

• 对于第三步，需要利用支持度阈值从「候选 \(k+1\) 项集」中筛选出「频繁 \(k+1\) 项集」。有两种方法可以加速支持度计数的过程，具体的：

  • 基于事务树。可以在一开始利用完整的事务集维护一个「项集计数字典列表」，例如 List[ Dict[str, int] ]。后续在对候选 k+1 项集进行支持度计数时，只需要取出 List[k+1] 这个字典（其中维护了事务集中所有 \(k+1\) 项集的支持度计数的数值，这里假设项集可以用一个 str 来唯一表示），然后接近 \(O(1)\) 的累加字典中的数值即可。这种方法适用于事务集不变以及一个项集可以用一个可哈希的 key 来表示的情况；
  • 基于哈希树。这与事务树是逆过程，事务树是先维护事务，然后遍历候选项集进行支持度计数；而哈希树的思路是，基于每一轮产生的候选项集维护一棵树，然后遍历事务集进行支持度计数。感觉这种方法不如上一种方法来的巧妙。

4）时间复杂度分析

支持度阈值越小、事务集的项数越多、事务集的事务数越多、事务集中的事务平均宽度越大，Aprioir 算法的时间复杂度就越高。

5）频繁项集的紧凑表示

需要注意的是，由于计算置信度时需要使用之前计算过的支持度信息，当频繁项集很多时，这会造成很大的存储消耗，为了减少这种存储消耗，我们需要减少频繁项集的数量，为此引入「极大频繁项集」和「闭频繁项集」来压缩频繁项集的数量从而在保留重要信息的前提下减少存储消耗。具体的：

• 极大频繁项集。是指这样的频繁项集，它的所有的直接超集都不是频繁项集。给出了判断项集频繁性的最简表示但损失了频繁项集的支持度计数信息；
• 闭频繁项集。是指这样的频繁项集，它的所有的直接超集都不具有和它相同的支持度计数。保留了频繁项集的所有信息但需要更多的存储资源。

FP-growth 算法

频繁模式增长 (Frequent-Pattern growth, FP-growth) 算法

主要分为两步，一步是构造 FP 树，一步就是根据 FP 树寻找频繁项集。举例说明：假设最小支持度阈值为 22.2%（2/9）。

一）构造 FP 树

首先扫描一遍事务集，去除不符合最小支持度阈值的项 F，并将频繁项按照频率降序排序，同时对每一个事务中的项按照频繁项的顺序重新排序，如下图所示：

接着再扫描一遍事务集构造出最终的 FP 树，如下图所示：

2）寻找频繁项集

构造完 FP 树后，如何基于该树寻找频繁项集呢？分为三步：

1. 基于 FP 树构造每一个频繁项的条件模式基 (conditional pattern base)。简而言之就是 以频繁项为叶子结点的子树；
2. 基于条件模式基构造条件 FP 树 (conditional FP tree)。简而言之就是 条件模式基去掉叶子结点的子树；
3. 基于条件 FP 树寻找频繁项集。寻找方法就是 对前后缀模式进行排列组合，最终项的数量需要取最小值。

当然，第一步中的排序规则并不是一定要按照频率降序排序的，不同的排序方式会导致不同的建树结果同时对于后续寻找频繁项集也是不确定的，这导致了 FP-growth 算法的不稳定性。

例题

假设现在的最小支持度阈值为 40%，按照下面的事务集，使用 FP-growth 算法寻找出所有的频繁项集：

TID	项集
1	{a,b,d,e}
2	{b,c,d}
3	{a,b,d,e}
4	{a,c,d,e}
5	{b,c,d,e}

1）构建 FP 树

首先扫描一遍事务集得到所有频繁项并对事务集中的项进行排序，然后基于重排的事务集构建 FP 树：

2）寻找频繁项集

以 c 为频繁项：

以 a 为频繁项：

以 e 作为频繁项：

以 b 作为频繁项：

以 d 作为频繁项：

Eclat 算法

等价类变换（Equivalence CLAss Transformation，Eclat）算法

这里再补充一个 Apriori 算法的变种，叫做 Eclat 算法。其算法逻辑是将项集编号和项集进行「反拉链」存储：

后续在统计频繁项集时只需要取 TID集 的交集即可：

置信度检测

有了所有的频繁项集，接下来就是在每一个频繁项集中挖掘强关联规则。具体的，假设当前的一个频繁项集为 \(F\)，且 \(|F|=k\)，那么就可以枚举 \(2^k-2\) 次所有的前后件组合进行置信度检测。由于前面在计算支持度时，频繁项集中所有的项都算过支持度了，就可以提前保存好供当前置信度检测时使用，因此置信度检测时除了 \(O(2^k)\) 的枚举开销之外，其余时间开销可以看做 \(O(1)\)。

当然，我们在进行前后件组合的搜索时，可以利用先验知识进行剪枝。具体的，假设当前的频繁项集 \(F\) 被划分为了 \(X \to F-X\) 的关联规则：

• 若关联规则 \(X \to F-X\) 不满足置信度检测，则 \(X' \to F-X\) 也一定不满足置信度检测。其中 \(X'\) 为 \(X\) 的子集；
• 若关联规则 \(X \to F-X\) 满足置信度检测，则 \(X \to (F-X)'\) 也一定满足置信度检测，其中 \((F-X)'\) 为 \(F-X\) 的子集。

上面两个先验知识利用置信度检测的式子就可以一目了然的推出来。

更强的强关联规则定义

仅仅使用支持度和置信度仍然有可能挖掘出没那么有意义的关联规则，例如对于一个在支持度置信度框架下挖掘出的强关联规则，有可能是因为其中的前件或者后件的单独销量很高而误判了。为了解决这个问题，基于「支持度、置信度和相关性」三个准则的强关联规则的定义被提了出来。也就是说，还需要满足相关性的阈值标准才能被称为强关联规则。

1）提升度

\[ \text{lift}(X, Y)=\frac{P(X\cup Y)}{P(X)P(Y)} \]

对于两个项集 \(X\) 和 \(Y\)：

• 如果 \(\frac{P(X\bigcup Y) }{P(X)P(Y)} >1\) 则说明 \(X\) 和 \(Y\) 是正相关的，这也是我们进行关联分析所感兴趣的；
• 如果 \(\frac{P(X\bigcup Y) }{P(X)P(Y)} = 1\) 则说明 \(X\) 和 \(Y\) 是相互独立的，没有研究意义；
• 如果 \(\frac{P(X\bigcup Y) }{P(X)P(Y)} < 1\) 则说明 \(X\) 和 \(Y\) 是负相关的，其中一项的出现会抑制另一项的出现，也没有研究意义。

2）杠杆度

\[ \text{leverage}(X, Y)= P(X\cup Y)-P(X)P(Y) \]

这是提升度的另一种表现，三种关系很显然，就不说了。

3）全置信度

\[ \text{all\_conf}(X, Y) = \min\{P(X|Y), P(Y|X)\} \]

4）最大置信度

\[ \text{max\_conf}(X, Y) = \max\{P(X|Y), P(Y|X)\} \]

5）Kulc 度量

\[ \text{Kluc}(X, Y) = \frac{1}{2}(P(X|Y) + P(Y|X)) \]

6）余弦度量

\[ \text{Cosine}(X, Y) = \sqrt{P(X|Y)P(Y|X)} \]

注：上述 6 种相关性度量标准中第一种以 1 为界，第二种以 0 为界，后四种以 0.5 为界。并且都是越大越相关。

零不变性。即度量数值不随零事务的变化而变化，所谓零事务就是不包含任何项的事务。说白了，就是度量的规则不受那些无关事务的影响，上述 6 种度量规则中后四种都具有零不变性。根本原因是表达式中的量纲没有发生改变。

不平衡比。从零不变性可以看出后四种是更为合理的相关性度量准则，因此我们将目光聚焦在后四个度量标准上，可以看出无非就是对 \(P(X|Y)\) 和 \(P(Y|X)\) 进行运算。定义不平衡比：

\[ \text{IR}(X, Y)=\frac{|\sigma(X)-\sigma(Y)|}{\sigma(X)+\sigma(Y)-\sigma(X\cap Y)} \]

也就是 \(X\) 发生概率与 \(Y\) 发生概率之差比上 \(X\) 或 \(Y\) 发生的概率。IR 越大表示数据集越不平衡。实验的结论是：当数据不平衡时，可以综合使用 Kluc 度量和 IR 度量。

关联分析在序列数据上的应用

当数据的类型不是非对称的二元属性，而是一个序列数据时，如何挖掘其中的强关联序列呢？本节我们补充学习子序列的包含关系、频繁序列（序列模式）的表示形式以及「k-序列」的定义。

子序列的包含关系如下图所示：

频繁序列（序列模式）的定义为满足最小支持度技术的序列，如下图所示：

k-序列即包含 \(k\) 个项的序列，序列中的元素可以重复，例如对于一个只有两个项的 2-序列，可以有以下的所有序列可能：

\[ \begin{aligned} &<\{i_1, i_2\}>\\ &<\{i_1\}, \{i_2\}>\\ &<\{i_1\}, \{i_1\}>\\ &<\{i_2\}, \{i_2\}>\\ \end{aligned} \]