关联分析:频繁项集和关联规则
从大规模的数据中发现物品间隐含关系的方法被称为关联分析。关联分析是一种在大规模数据集中寻找有趣关系的任务。
关联规则:
关联规则是形如X→Y的表达式，其中X和Y是不相交的项集，即X∩Y=∅。关联规则的强度可以用它的支持度（support）和置信度（confidence）来度量。支持度确定规则可以用于给定数据集的频繁程度，而置信度确定Y在包含X的交易中出现的频繁程度。
支持度（表示X和Y同时在总数N中发生的概率）:
$$
support(X,Y)=\frac{N(X \cup Y)}{N(all)}
$$
置信度（在发生X的项集中，同时会发生Y的概率，即X和Y同时发生的样本数占仅仅X发生样本数的比例）:
$$
confidence(X \rightarrow Y)=P(Y | X)=\frac{support(X,Y)}{P(X)}
$$
提升度（在发生X的条件下，同时发生Y的概率，与只发生Y的概率之比。提升度反映了关联规则中的X与Y的相关性，提升度>1且越高表明正相关性越高，提升度<1且越低表明负相关性越高，提升度=1表明没有相关性，即相互独立）:
$$
lift(X \rightarrow Y)=\frac{confidence(X \rightarrow Y)}{P(Y)} =\frac{P(Y | X)}{P(Y)}
$$
频繁项集:
项集是指若干个项的集合。频繁项集是指支持度大于等于最小支持度(min_sup)的集合。
举例:
10000个超市订单（10000个事务），其中购买A牛奶（A事务）6000个，购买B牛奶（B事务）7500个，4000个同时包含两者。
那么A牛奶（A事务）和B牛奶（B事务）的支持度为:
$$
support(A,B)=\frac{N(A \cup B)}{N(all)}=\frac{4000}{10000}=0.4
$$
A牛奶（A事务）对B牛奶（B事务）的置信度为包含A的事务中同时包含B的占包含A的事务比例:
$$
confidence(A \rightarrow B)=P(B | A)=\frac{support(A,B)}{P(A)}=\frac{4000}{6000}=0.67
$$
说明在购买A牛奶后，有0.67的用户去购买B牛奶。
伊利牛奶（B事务）B牛奶对A牛奶（A事务）的置信度为包含B的事务中同时包含A的占包含B的事务比例:
$$
confidence(B \rightarrow A)=P(A | B)=\frac{support(A,B)}{P(B)}=\frac{4000}{7500}=0.53
$$
说明在购买A牛奶后，有0.53的用户去购买B牛奶。
这里有一点要注意，就是没有任何条件下时，B事务的出现的比例是0.75，而出现A事务，且同时出现B事务的比例是0.67，也就是说设置了A事务出现这个条件，B事务出现的比例反而降低了。这说明A事务和B事务是排斥的。
我们计算A事务对B事务的提升度:
$$
lift(A \rightarrow B)=\frac{confidence(A \rightarrow B)}{P(B)} =\frac{P(B | A)}{P(B)} =\frac{0.67}{0.75}
$$
显然提升度<1，说明A和B是负相关的。
商品列表中，可能存在单一商品组成的频繁项集，也可能存在两个以及两个以上的商品组成的频繁项集。在计算一个频繁项集的支持度时，通常需要遍历所有的商品列表求得，但当列表数目成千上万时，计算量过大，这种方法显然不适用。这时候我们就要用Apriori算法。
Apriori算法原理
Apriori算法的原理:
如果某个项集是频繁的，那么它的所有子集也是频繁的。同时它的逆否命题也成立:如果一个项集是非频繁集，那么它的所有超集也是非频繁的。
Apriori算法的两个输入参数分别是最小支持度和数据集，该算法首先会生成所有单个物品的项集列表，接着扫描交易记录来查看哪些项集满足最小支持度要求，那些不满足最小支持度的集合会被去掉。然后，对生下来的集合进行组合以生成包含两个元素的项集，接下来，再重新扫描交易记录，去掉不满足最小支持度的项集。该过程重复进行，直到所有项集都被去掉。
举例:
假设一个集合{A,B}是频繁项集，即A、B同时出现在一条记录的次数大于等于最小支持度min_support，则它的子集{A},{B}出现次数必定大于等于min_support，即它的子集都是频繁项集。
假设集合{A}不是频繁项集，即A出现的次数小于min_support，则它的任何超集如{A,B}出现的次数必定小于min_support，因此其超集必定也不是频繁项集。
Apriori算法步骤:
- 先计算1项集的支持度，筛选出频繁1项集；
- 然后排列组合出2项集，计算出2项集的支持度，筛选出频繁2项集；
- 然后通过连接和剪枝计算出3项集，计算出3项集的支持度，筛选出频繁3项集；
- 然后依次类推处理K项集，直到没有频繁集出现。
如何从K-1项集计算出K项集（K>=3，K=2时用组合公式C（2,n）即可）？
连接:对K-1项集中的每个项集中的项排序，只有在前K-1项相同时才将这两项合并，形成候选K项集（因为必须形成K项集，所以只有在前K-1项相同，第K项不相同的情况下才合并。）
剪枝:对于候选K项集，要验证所有项集的所有K-1子集是否频繁（是否在K-1项集中），去掉不满足的项集，就形成了K项集。
FPgrowth算法原理
首先构建FP树。扫描数据集，生成频繁一项集L，并按出现次数由多到少排序。删除支持度低于min_support的项，剩余部分称为项头表（Header Table）；再次扫描数据集，从数据中删除非频繁1项集（删除时是删除每一个样本中的非频繁一项集中的项，不是删除整个样本），并按照项头表的顺序排序；FP树头节点是一个null节点，逐个读取上一步处理后的数据集中每个样本，每读取一个样本检查树种是否已有该条样本项组成的路径，已有则每个节点权值加1，如果从某个项开始没有则从该节点开始多一个分支，分支内的节点权值都新置1。这样我们的树就建好了。
下面我们要进行频繁项的挖掘。从FP树底层的节点开始依次向上，构造每个节点的条件模式基（CPB, Conditional Pattern Base），条件模式基就是我们要挖掘的频繁项的前缀路径。对于项头表中的每一个item（设为k），记录其所有条件模式基中出现的每一个item的频数，去除小于min_support的item，保留项用来构造项头表中的这个item（k）的条件FP树。那么其频繁项就是k,item、item。然后递归地挖掘每个条件FP树，累加后缀频繁项集，直到找到FP-tree为空或者FP-tree只有一条路径（只有一条路径情况下，所有路径上item的组合都是频繁项集）。
举例:
上面的说法比较抽象，我们还是举一个实例来说明。
TID Items bought (ordered) frequent items
100 {f, a, c, d, g, i, m, p} {f, c, a, m, p}
200 {a, b, c, f, l, m, o} {f, c, a, b, m}
300 {b, f, h, j, o, w} {f, b}
400 {b, c, k, s, p} {c, b, p}
500 {a, f, c, e, l, p, m, n} {f, c, a, m, p}
第一遍扫描得到频繁1项集。定义min_support=3，删除小于min_support的项，降序排列，得到项头表（Header Table）。
Header Table
Item frequency head
f 4
c 4
a 3
b 3
m 3
p 3
根据项头表对原数据集中每一个样本删除非频繁项，只保留频繁项。并按项头表中的frequency降序排列。
TID (ordered) frequent items
100 {f, c, a, m, p}
200 {f, c, a, b, m}
300 {f, b}
400 {c, b, p}
500 {f, c, a, m, p}
建立FP树，头节点设为null。逐个读取上一步处理后的数据集中每个样本，每读取一个样本检查树中是否已有该条样本项组成的路径，已有则每个节点权值加1，如果从某个项开始没有则从该节点开始多一个分支，分支内的节点权值都新置1。FP树结果如下。
null
/ \
f:4 c:1
/ \ |
c:3 b:1 b:1
| |
a:3 p:1
/ \
m:2 b:1
| |
p:2 m:1
我们的项头表中还有一列head，这列是指向该频繁项在FP-tree中节点位置的指针。FP-tree中每一个节点还有一个指针，用于指向相同名称的节点。这样就把相同名称的节点全部用链表串起来，方便访问。
建立条件模式基。从项头表中每个item的head开始依次访问FP树中的所有同名节点，FP树中每个节点的条件模式基的频数等于该节点的频数，前缀就是节点上的一系列父节点直到根节点。比如对p有两个条件模式基: fcam:2, cb:1。
item 条件模式基
c f:3
a fc:3
b fca:1, f:1, c:1
m fca:2, fcab:1
p fcam:2, cb:1
有两个条件模式基: fcam:2, cb:1。我们分别记录每个item的出现次数:c:3、f:2、a:2、m:2、b:1。由于min_support=3，因此我们只保留c:3。然后用保留项建立一棵新的FP树，这棵树被称之为p的条件FP树：
null
|
c:3
那么以p结尾的频繁项集有p:3、cp:3。由于c的条件模式基为空，所以不需要构建c的条件FP-tree。
m地条件模式基为: fca:2, fcab:1。我们分别记录每个item出现的次数为:f:3、c:3、a:3、b:1。剔除那些低于支持度阈值的项，建立m的条件FP树:
null
|
f:3
|
c:3
|
a:3
与p不同，m的条件FP树中有3个节点，所以需要多次递归地挖掘频繁项集（f:3，c:3，a:3|m:3）。按照a:3，c:3，f:3的顺序递归调用mine（f:3，c:3|a，m），mine（f:3|c，m），mine（null|f，m）。由于m:3满足支持度阈值要求，所以以m结尾的频繁项集有{m:3}。
null
|
f:3
|
c:3
节点（a,m）的条件FP树有2个节点，需要进一步递归调用mine（f:3|c，a，m）和mine（null|f，a，m）。进一步递归mine（f:3|c，a，m）生成mine（null|f，c，a，m）。因此，以（a，m）结尾的频繁项集有{am:3，fam:3，cam:3，fcam:3}。
null
|
f:3
节点（c,m）的条件FP树只有1个节点，所以只需要递归调用mine(null|f，c，m)。因此，以（c，m）结尾的频繁项集有{cm:3，fcm:3}。同理，以（f，m）结尾的频繁项集有{fm:3}。
在FP树中以b结尾的节点链共有三条，分别是f:4，c:3，a:3，b:1，f:4，b:1和c:1，b:1。由于节点b的条件模式基f:1，c:1，a:1，f:1和c:1都不满足支持度阈值，所以不需要再递归。因此，以b结尾的频繁项集只有{b:3}。
同理可得，以a结尾的频繁项集{fa:3，ca:3，fca:3，a:3}，以c结尾的频繁项集{fc:3，c:4}，以f结尾的频繁项集{f:4}。
