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

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

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

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

P(啤酒与尿布) = P(啤酒) \times P(尿布)

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

P(啤酒与尿布) >> P(啤酒) \times P(尿布)

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

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

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

Apriori

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

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

  • O中寻找频繁1项集M_1.排出O中低于阀值的项.
  • O中寻找频繁2项集M_2.排出O中低于阀值的项.
  • O中寻找频繁3项集M_3.排出O中低于阀值的项.
  • 直至寻找到频繁k项集.

举个例子,给定数据:

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

我们来使用Apriori算法计算它的频繁3项集.根据数据知O = \{1,2,3,4,5\}.

  • 寻找高于阀值的频繁1项集M_1 = \{\{1\},\{2\},\{3\},\{5\}\},于是O =\{1,2,3,5\}
  • 寻找高于阀值的频繁2项集M_2 = \{\{1,3\},\{2,3\},\{2,5\},\{3,5\}\},于是O =\{1,2,3,5\}
  • 寻找高于阀值的频繁3项集M_3 = \{\{1,2,3\}\}

FP-Growth

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

image.png

上图是一个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树。
image.png

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

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

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

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

image.png

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

image.png

image.png

接下来开始挖掘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的条件模式基如下图右所示。
image.png

通过它,我们很容易得到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项集。

image.png

同样的方法可以得到B的条件模式基如下图右边,递归挖掘到B的最大频繁项集为频繁4项集{A:2, C:2, E:2,B:2}。

image.png

继续挖掘G的频繁项集,挖掘到的G的条件模式基如下图右边,递归挖掘到G的最大频繁项集为频繁4项集{A:5, C:5, E:4,G:4}。

image.png
E的条件模式基如下图右边,递归挖掘到E的最大频繁项集为频繁3项集{A:6, C:6, E:6}。
image.png
C的条件模式基如下图右边,递归挖掘到C的最大频繁项集为频繁2项集{A:8, C:8}。
image.png

至于A,由于它的条件模式基为空,因此可以不用去挖掘了。

至此我们得到了所有的频繁项集,如果我们只是要最大的频繁K项集,从上面的分析可以看到,最大的频繁项集为5项集。包括{A:2, C:2, E:2,B:2,F:2}。

通过上面的流程,相信大家对FP Tree的挖掘频繁项集的过程也很熟悉了。


参考:
https://www.cnblogs.com/pinard/p/6307064.html

posted @ 2018-12-18 09:16:38
评论加载中...

发表评论