相信大家都听说过沃尔玛的"啤酒与尿布"的故事,将啤酒与尿布摆放在相同的区域,销售收入会增长,这可能是最早的几个成功将数据分析应用到商业的案例.这里用的的就是数据的关联性分析.

我们把经常在一起发生的事件集称作频繁项集.例如事件与事件关联性较强,那么他们同时发生的次数一定比较多,所以我们称,为频繁项集.

常用的频繁项集的评估标准有支持度,置信度和提升度三个。对于事件A,B:

支持度就是两个事件同时出现的概率
例如,如果啤酒与尿布没有关系,是随机出现的,会有:

但事实上"啤酒与尿布"出现的概率比"啤酒"的概率与"尿布"的概率乘积大很多:

一般来说，支持度高的数据不一定构成频繁项集，但是支持度太低的数据肯定不构成频繁项集。

置信度的定义事件A对事件B的置信度为.
例如，啤酒对尿布的置信度为40%，支持度为1%。则意味着在购物数据中，总共有1%的用户既买啤酒又尿布;同时买啤酒的用户中有40%的用户买尿布。

提升度体现了A和B之间的关联关系,定义为.
当事件A与B无关,随机发生时,提升度=1,A与B相关时,提升度>1.

Apriori

Apriori是经典的数据关联性分析的算法.对于频繁项集的判断标准可以选择支持度,置信度和提升度之一,或是自定义判断标准.

假设我们使用Apriori算法寻找数据中频繁k项集.首先设置频繁项集的阀值.设特征集为

在中寻找频繁1项集.排出中低于阀值的项.
在中寻找频繁2项集.排出中低于阀值的项.
在中寻找频繁3项集.排出中低于阀值的项.
...
直至寻找到频繁k项集.

举个例子,给定数据:

编号	数据
1	1,3,4
2	2,3,5
3	1,2,3,5
4	2,5

我们来使用Apriori算法计算它的频繁3项集.根据数据知.

寻找高于阀值的频繁1项集,于是
寻找高于阀值的频繁2项集,于是
寻找高于阀值的频繁3项集

FP-Growth

Apriori算法需要多次扫描数据，I/O是很大的瓶颈。为了解决这个问题，FP-Growth算法采用了一种叫做FP Tree的数据结构，无论多少数据，只需要扫描两次数据集，因此提高了算法运行的效率。

上图是一个FP Tree结构.第一部分是一个项头表。里面记录了所有的1项频繁集出现的次数，按照次数降序排列。比如上图中B在所有10组数据中出现了8次，因此排在第一位，这部分好理解。第二部分是FP Tree，它将我们的原始数据集映射到了内存中的一颗FP树。第三部分是节点链表。所有项头表里的1项频繁集都是一个节点链表的头，它依次指向FP树中该1项频繁集出现的位置。这样做主要是方便项头表和FP Tree之间的联系查找和更新，也好理解。

FP树的建立需要首先依赖项头表的建立。首先我们看看怎么建立项头表。

我们第一次扫描数据，得到所有频繁一项集的的计数。然后删除支持度低于阈值的项，将1项频繁集放入项头表，并按照支持度降序排列。接着第二次也是最后一次扫描数据，将读到的原始数据剔除非频繁1项集，并按照支持度降序排列。

上面这段话很抽象，我们用下面这个例子来具体讲解。我们有10条数据，首先第一次扫描数据并对1项集计数，我们发现O，I，L，J，P，M, N都只出现一次，支持度低于20%的阈值，因此他们不会出现在下面的项头表中。剩下的A,C,E,G,B,D,F按照支持度的大小降序排列，组成了我们的项头表。

接着我们第二次扫描数据，对于每条数据剔除非频繁1项集，并按照支持度降序排列。比如数据项ABCEFO，里面O是非频繁1项集，因此被剔除，只剩下了ABCEF。按照支持度的顺序排序，它变成了ACEBF。其他的数据项以此类推。为什么要将原始数据集里的频繁1项数据项进行排序呢？这是为了我们后面的FP树的建立时，可以尽可能的共用祖先节点。

通过两次扫描，项头表已经建立，排序后的数据集也已经得到了，下面我们再看看怎么建立FP树。

有了项头表和排序后的数据集，我们就可以开始FP树的建立了。开始时FP树没有数据，建立FP树时我们一条条的读入排序后的数据集，插入FP树，插入时按照排序后的顺序，插入FP树中，排序靠前的节点是祖先节点，而靠后的是子孙节点。如果有共用的祖先，则对应的公用祖先节点计数加1。插入后，如果有新节点出现，则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后，FP树的建立完成。

似乎也很抽象，我们还是用第二节的例子来描述。

首先，我们插入第一条数据ACEBF，如下图所示。此时FP树没有节点，因此ACEBF是一个独立的路径，所有节点计数为1, 项头表通过节点链表链接上对应的新增节点。

接着我们插入数据ACG，如下图所示。由于ACG和现有的FP树可以有共有的祖先节点序列AC，因此只需要增加一个新节点G，将新节点G的计数记为1。同时A和C的计数加1成为2。当然，对应的G节点的节点链表要更新

同样的办法可以更新后面8条数据，如下8张图。由于原理类似，这里就不多文字讲解了，大家可以自己去尝试插入并进行理解对比。相信如果大家自己可以独立的插入这10条数据，那么FP树建立的过程就没有什么难度了。

接下来开始挖掘FP树里的频繁项集,首先要从项头表的底部项依次向上挖掘。对于项头表对应于FP树的每一项，我们要找到它的条件模式基。所谓条件模式基是以我们要挖掘的节点作为叶子节点所对应的FP子树。得到这个FP子树，我们将子树中每个节点的的计数设置为叶子节点的计数，并删除计数低于支持度的节点。从这个条件模式基，我们就可以递归挖掘得到频繁项集了。

我们看看先从最底下的F节点开始，我们先来寻找F节点的条件模式基，由于F在FP树中只有一个节点，因此候选就只有下图左所示的一条路径，对应{A:8,C:8,E:6,B:2, F:2}。我们接着将所有的祖先节点计数设置为叶子节点的计数，即FP子树变成{A:2,C:2,E:2,B:2, F:2}。一般我们的条件模式基可以不写叶子节点，因此最终的F的条件模式基如下图右所示。

通过它，我们很容易得到F的频繁2项集为{A:2,F:2}, {C:2,F:2}, {E:2,F:2}, {B:2,F:2}。递归合并二项集，得到频繁三项集为{A:2,C:2,F:2}，{A:2,E:2,F:2},...还有一些频繁三项集，就不写了。当然一直递归下去，最大的频繁项集为频繁5项集，为{A:2,C:2,E:2,B:2,F:2}

F挖掘完了，我们开始挖掘D节点。D节点比F节点复杂一些，因为它有两个叶子节点，因此首先得到的FP子树如下图左。我们接着将所有的祖先节点计数设置为叶子节点的计数，即变成{A:2, C:2,E:1 G:1,D:1, D:1}此时E节点和G节点由于在条件模式基里面的支持度低于阈值，被我们删除，最终在去除低支持度节点并不包括叶子节点后D的条件模式基为{A:2, C:2}。通过它，我们很容易得到D的频繁2项集为{A:2,D:2}, {C:2,D:2}。递归合并二项集，得到频繁三项集为{A:2,C:2,D:2}。D对应的最大的频繁项集为频繁3项集。