Apriori and FP-tree（Simple Example）

1 关联规则挖掘

在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。

2 应用

购物篮分析、交叉销售、产品目录设计、 loss-leader analysis、聚集、分类等。

3 规则度量

查找所有的规则 $X, Y \to Z$ 具有最小支持度和可信度

支持度, Support 一次交易中包含 ${X 、 Y 、 Z}$ 的可能性

S u p p o r t (X, Y \to Z) = \frac{N (X, Y, Z)}{N}

可信度, Confidence, 包含 ${X 、 Y}$ 的交易中也包含 $Z$ 的条件概率
$C o n f i d e n c e (X, Y \to Z) = \frac{N (X, Y, Z)}{N (X, Y)}$

求解所有 $S \geq S_{m i n}$ 、 $C \geq C_{m i n}$ 的组合

例如：

$S u p p o r t (a \Rightarrow c) = 2 / 4 = 50 %$

$C o n f i d e n c e (a \Rightarrow c) = 2 / 3 = 66.7 %$

a \Rightarrow c (50 %, 66.7 %)

$S u p p o r t (c \Rightarrow a) = 2 / 4 = 50 %$

$C o n f i d e n c e (c \Rightarrow a) = 2 / 2 = 100 %$

c \Rightarrow a (50 %, 100 %)

4 Apriori

4.1 基本思想

频繁项集的任何子集也一定是频繁的
如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。

4.2 算法的核心

用频繁的(k – 1)项集生成候选的频繁 k项集
用数据库扫描和模式匹配计算候选集的支持度

4.3 Simple Example

$S_{m i n} = 50 %$ , $C_{m i n} = 90 %$ , 计算满足所有条件的关联规则
Apriori and FP-tree（Simple Example）

最小频数为： $N u m b e r o f i t e m s \times S_{m i n} = 4 \times 50 % = 2$

C1：扫描数据库，统计 each item 的频数
L1：与最小频数比较，剔除 $S < S_{m i n}$ 的items，结果为一项频繁集
C2： L1中items 两两结合， $C_{n}^{2}$ ，扫描数据库，统计 each 二项组合item 的频数
L2：与最小频数比较，剔除 $S < S_{m i n}$ 的items，结果为二项频繁集
C3：扫描L2每项， $C_{n}^{2}$ ，注意，比每项的第一个元素，一样的就合并，不一样的pass，论文中证明了这种方法的完备性（因为频繁项的子集一定是频繁的），扫描数据库，统计 each 三项组合item 的频数

eg：AC+BC pass， AC+BE pass， AC+CE pass，BC+BE 合并 BCE，BC+CE pass，BE+CE pass，结果为 BCE

L3：与最小频数比较，剔除 $S < S_{m i n}$ 的items，结果为三项频繁集
………………

二项频繁集的强关联关系：

C o n f i d e n c e (A \to C) = 2 / 2 > C_{m i n}

C o n f i d e n c e (C \to A) = 2 / 3 < C_{m i n}

三项频繁集的强关联关系：

C o n f i d e n c e (B, C \to E) = 2 / 2 > C_{m i n}

C o n f i d e n c e (B, E \to C) = 2 / 3 < C_{m i n}

C o n f i d e n c e (C, E \to B) = 2 / 2 > C_{m i n}

C o n f i d e n c e (B \to C, E) = 2 / 3 < C_{m i n}

C o n f i d e n c e (C \to B, E) = 2 / 3 < C_{m i n}

C o n f i d e n c e (E \to B, C) = 2 / 3 < C_{m i n}

结果为：

A \to C

B, C \to E

C, E \to B

4.4 Apriori 的瓶颈

巨大的候选集:
$10^{4}$ 个频繁1-项集要生成 $10^{7}$ 个候选 2-项集，要找尺寸为100的频繁模式，如 {a1, a2, …, a100}, 你必须先产生 $2^{100} \approx 10^{30}$ 个候选集
多次扫描数据库：
如果最长的模式是 $n$ 的话，则需要 $(n + 1)$ 次数据库扫描

5 FP-tree

用Frequent-Pattern tree (FP-tree) 结构压缩数据库,

高度浓缩，同时对频繁集的挖掘又是完备的
避免代价较高的数据库扫描

5.1 基本思想

(分而治之) 用FP-tree地归增长频繁集

5.2 方法

对每个项，生成它的条件模式库, 然后生成条件 FP-tree
对每个新生成的条件FP-tree，重复这个步骤
直到结果FP-tree为空, 或只含维一的一个路径 (此路径的每个子路径对应的相集都是频繁集)

5.3 主要步骤

为FP-tree中的每个节点生成条件模式库
用条件模式库构造对应的条件FP-tree
递归构造条件 FP-trees 同时增长其包含的频繁集，如果条件FP-tree直包含一个路径，则直接生成所包含的频繁集。

5.4 Simple Example

扫描一次数据集，筛选出频繁一项集，根据频繁一项集，重新生成新的数据集（按频繁项递减排序）

根据新的数据集，生成FP-tree，过程如下图，统计频数

根据FP-tree生成条件模式库，条件FP-tree 和频繁项

item	条件模式库	条件FP-tree	频繁项
A	{ (C:1), (BCE:1) }	{ (C:2) }\|A	CA:2
E	{ (BC:2), (B:1) }	{ (B:3,C:2) }\|E	BE:3,CE:2,BCE:2
C	{ (B:2) }	(B:2) }\|C	BC:2

表的生成
以item做为“尾巴（路径重点）”，根据画出的FP-tree，由尾巴往上找路径
eg：以A为尾巴，有CA，BCEA两条路径，路径的条数根据A的元素个数决定，这样就可以生成条件模式库

条件模式库到条件FP-tree，就是通过Support筛选之后加上尾巴的结果
eg：以E为尾巴，有BCE,BCE,BE三条路径，B出现三次，C出现2次，都大于等于S最小值，都是频繁项，所以结果为 { (B:3,C:2) }|E

更多关于算法的细节可以参考
数据挖掘十大算法之Apriori详解