从频繁项挖掘到并行序列挖掘

发表于

简要介绍常见频繁项挖掘算法：Apriori，FP-Tree，PrefixSpan。

本文主要参考这篇文章：

  1. 刘建平Pinard大佬的cnblogs

本文还参考了下面的文章和论文：

  1. 数与君_公众号同名
  2. PrefixFPM: A Parallel Framework for General-Purpose Frequent Pattern Mining
  3. 频繁项集挖掘算法研究 蓝祺花 厦门大学
  4. Index-BitTableFI_An_improved_algorithm_for_mining_frequent_itemsets

关联规则挖掘在很多领域都有重要的作用，比如经典的啤酒尿布问题，这是最典型的频繁项挖掘问题，频繁模式的挖掘不止限于项集的挖掘，子图匹配算法可以找到化合物结构中相似的部分，子树挖掘算法可以找到XML的相似结构。

近期我的一些工作需要挖掘流量之间的潜在关系，直接用众包的思想进行统计，会导致出现较大偏差，且难以挖掘多个item的序列关系，利用序列挖掘算法则可以很好的解决这一问题。

Apriori算法

Apriori，FP-Tree，PrefixSpan算法部分来自刘建平的博客。

评估标准

支持度（support）：support(A=>B) = P(A∪B)，表示A和B同时出现的概率。

置信度（confidence）：confidence(A=>B)=support(A∪B) / support(A)，表示A和B同时出现的概率占A出现概率的比值。

频繁项集：在项集中频繁出现并满足最小支持度阈值的集合，例如{牛奶，面包}、{手机，手机壳}等。

强关联规则：满足最小支持度和最小置信度的关联规则。

一般来说，要选择一个数据集合中的频繁数据集，则需要自定义评估标准。最常用的评估标准是用自定义的支持度，或者是自定义支持度和置信度的一个组合。

算法思想

Apriori算法采用了迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁二项集，以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。

1042406-20170117161036255-1753157633

可以看到，Apriori首先挖掘1项集，有1项集进行连接产生候选2项集，再迭代挖掘2项集…直到n项集。

Apriori算法流程

1
2
3
4
5
6
7
8
　　　　输入：数据集合D，支持度阈值𝛼
　　　　输出：最大的频繁k项集
　　　　1）扫描整个数据集，得到所有出现过的数据，作为候选频繁1项集。k=1，频繁0项集为空集。
　　　　2）挖掘频繁k项集
　　　　　　a) 扫描数据计算候选频繁k项集的支持度
　　　　　　b) 去除候选频繁k项集中支持度低于阈值的数据集,得到频繁k项集。如果得到的频繁k项集为空，则直接返回频繁k-1项集的集合作为算法结果，算法结束。如果得到的频繁k项集只有一项，则直接返回频繁k项集的集合作为算法结果，算法结束。
　　　　　　c) 基于频繁k项集，连接生成候选频繁k+1项集。
　　　　3） 令k=k+1，转入步骤2。

Apriori的缺点

  1. 由k项集产生k+1项集是靠连接的操作，这样会产生大量候选集，并没有利用数据本身的特点。
  2. 每轮迭代都要扫描数据集，效率较低，所以现在基本不会直接用Apriori算法。

FP-Tree算法

Apriori的多次扫描带来了很大的开销，FP-Tree算法（也称FP-Growth算法）对此做出了改进，无论多少数据，只需要扫描两次数据集。

为了减少I/O次数，FP Tree算法引入了一些数据结构来临时存储数据。这个数据结构包括三部分，如下图所示：

1042406-20170119165628718-395589856

第一部分是一个项头表。里面记录了所有的1项频繁集出现的次数，按照次数降序排列。比如上图中B在所有10组数据中出现了8次，因此排在第一位，这部分好理解。第二部分是FP Tree，它将我们的原始数据集映射到了内存中的一颗FP树，这个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-Tree的建立

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

下面我根据刘建平Pinard的博客制作了一个简单的GIF示意图，来描述FP-Tree的建立过程，假设现在要求支持度为20%：

pexwb-zf287

FP Tree的挖掘

构建好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的条件模式基如下图右所示。

img

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

img

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

img

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

img

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

img

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

img

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

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

FP-Tree算法流程

1
2
3
4
5
6
7
8
9
　　　　1）扫描数据，得到所有频繁一项集的的计数。然后删除支持度低于阈值的项，将1项频繁集放入项头表，并按照支持度降序排列。

　　　　2）扫描数据，将读到的原始数据剔除非频繁1项集，并按照支持度降序排列。

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

　　　　4）从项头表的底部项依次向上找到项头表项对应的条件模式基。从条件模式基递归挖掘得到项头表项项的频繁项集（可以参见第4节对F的条件模式基的频繁二项集到频繁5五项集的挖掘）。

　　　　5）如果不限制频繁项集的项数，则返回步骤4所有的频繁项集，否则只返回满足项数要求的频繁项集。

PrefixSpan算法

PrefixSpan算法是序列挖掘算法，序列挖掘要求一条记录中的项集和项集之间有严格的时序关系。

1042406-20170120160812015-470353744

左侧的数据就是频繁项挖掘数据，每一条数据内部没有先后顺序，右侧是序列数据，项有选后顺序，()内的项集数据内部不存在先后顺序。

PrefixSpan全称为Prefix-Projected Pattern Growth，意思是前缀投影的模式挖掘。

在PrefixSpan算法中的前缀prefix通俗意义讲就是序列数据前面部分的子序列。比如对于序列数据B=<a(abc)(ac)d(cf)>，而A=<a(abc)a>,则A是B的前缀。当然B的前缀不止一个，比如<a>, <aa>, <a(ab)> 也都是B的前缀。

看了前缀，我们再来看前缀投影，其实前缀投影这儿就是我们的后缀，有前缀就有后缀嘛。前缀加上后缀就可以构成一个我们的序列。下面给出前缀和后缀的例子。对于某一个前缀，序列里前缀后面剩下的子序列即为我们的后缀。如果前缀最后的项是项集的一部分，则用一个“_”来占位表示。

下面这个例子展示了序列<a(abc)(ac)d(cf)>的一些前缀和后缀，还是比较直观的。要注意的是，如果前缀的末尾不是一个完全的项集，则需要加一个占位符。

在PrefixSpan算法中，相同前缀对应的所有后缀称为前缀对应的投影数据库。

1042406-20170120204305781-1880778940

PrefixSpan算法思想

PrefixSpan算法和Apriori算法类似，也是从长度为1的序列开始，再挖掘达到阈值条件的长度为2的频繁序列，递归，直到挖掘满足阈值的最长序列为止。

与Apriori算法不同的是，PrefixSpan算法不需要通过连接产生大量的候选集，而是通过前缀投影的方式得到候选序列，并且随着递归的继续，前缀投影的长度逐渐减少。具体来看🌰：

1042406-20170120214250703-974535125

设置支持度阈值为50%，长度为1的前缀包括<a>,<b>, <c>, <d>, <e>, <f>, <g>我们需要对这6个前缀分别递归搜索找各个前缀对应的频繁序列。由于g只在序列4出现，支持度计数只有1，因此无法继续挖掘。我们的长度为1的频繁序列为<a>, <b>, <c>, <d>, <e>，<f>。去除所有序列中的g，即第4条记录变成<e(af)cbc>，这一部分与Apriori算法第一步类似。

现在开始挖掘频繁序列，分别从长度为1的频繁项开始。这里我们以 d 为例子来递归挖掘，其他的节点递归挖掘方法和 d 一样。方法如下图，首先我们对ｄ的后缀进行计数，得到{a:1, b:2, c:3, d:0, e:1, f:1，_f:1}。注意 f 和 _f 是不一样的，因为前者是在和前缀d不同的项集，而后者是和前缀d同项集。

由于此时 a,d,e,f,_f 都达不到支持度阈值，因此我们递归得到的前缀为d的2项频繁序列为 <db>和 <dc>。接着我们分别递归db和dc为前缀所对应的投影序列，首先看 db 前缀，此时对应的投影后缀只有 <_c(ae)>，此时 _c,a,e 支持度均达不到阈值，因此无法找到以db为前缀的频繁序列。现在我们来递归另外一个前缀 dc。以 dc 为前缀的投影序列为 <_f>, <(bc)(ae)>, <b>，此时我们进行支持度计数，结果为 {b:2, a:1, c:1, e:1, _f:1}，只有b满足支持度阈值，因此我们得到前缀为 dc 的三项频繁序列为 <dcb>。

我们继续递归以<dcb>为前缀的频繁序列。由于前缀<dcb>对应的投影序列<(_c)ae>支持度全部不达标，因此不能产生4项频繁序列。至此以d为前缀的频繁序列挖掘结束，产生的频繁序列为<d><db><dc><dcb>。

同样的方法可以得到其他以<a>, <b>, <c>, <e>, <f>为前缀的频繁序列。

1042406-20170120222303515-615199517

PrefixSpan算法流程

1
2
3
4
5
6
7
8
9
　　　　输入：序列数据集S和支持度阈值𝛼
　　　　输出：所有满足支持度要求的频繁序列集
　　　　1）找出所有长度为1的前缀和对应的投影数据库
　　　　2）对长度为1的前缀进行计数，将支持度低于阈值𝛼的前缀对应的项从数据集S删除，同时得到所有的频繁1项序列，i=1.
　　　　3）对于每个长度为i满足支持度要求的前缀进行递归挖掘：
　　　　　　a) 找出前缀所对应的投影数据库。如果投影数据库为空，则递归返回。
　　　　　　b) 统计对应投影数据库中各项的支持度计数。如果所有项的支持度计数都低于阈值𝛼，则递归返回。
　　　　　　c) 将满足支持度计数的各个单项和当前的前缀进行合并，得到若干新的前缀。
　　　　　　d) 令i=i+1，前缀为合并单项后的各个前缀，分别递归执行第3步。

PrefixSpan运行时最大的消耗在递归的构造投影数据库。如果序列数据集较大，项数种类较多时，算法运行速度会有明显下降。因此有一些PrefixSpan的改进版算法都是在优化构造投影数据库这一块。比如使用伪投影计数。

当然使用大数据平台的分布式计算能力也是加快PrefixSpan运行速度一个好办法。比如Spark的MLlib就内置了PrefixSpan算法。

对频繁项挖掘的改进

频繁项挖掘和序列挖掘的优化方式有很多种，不同的算法都可以采用不同的方式进一步优化，我对此了解不深，这里简单介绍两种较为普遍的方式。

并行加速

随着大数据计算框架的流行，一些研究希望借助大数据平台的分布式计算能力来加速关联规则的挖掘。

分布式计算

使用map reduce可以让1项集并行执行得到2项集，再由2项集并行得到3项集合，由于map reduce对于海量数据和分布式计算支持很好，能有效利用不同机器进行计算。

image-20210716150636152

但是Map reduce会在map和reduce阶段将数据放到磁盘上，并且迭代计算需要启动多个map reduce计算，对于2项集需要在1项集的MR任务基础之上继续启动MR，这两点导致的额外开销反而使并行带来的加速计算并不明显。

Goole08年利用分布式机器并行执行FP-Growth算法，并且证明PFP算法可以实现几乎线性的加速。现在spark上FP-Growth算法的实现就是参照了这篇论文。

对于数据量不是特别大的情况，其实可以完全可以单机并发执行，利用多核CPU进行加速。严达等人在20年提出针对序列模式挖掘，相似子图挖掘，相似子树挖掘通用的并行算法，不依赖大数据系统，这里介绍他们对于序列模式挖掘的分布式尝试，其实思想很简单，就是将把子树的判断交给不同的Thread去做：

图片 1

伪代码如下：

image-20210716161226697

PrefixFPM的代码实现在这里。

减少存储

FP-Growth建立tree对内存的占用不小，并且对于稀疏数据集建树和遍历会耗费大量时间，一些工作设计了新的数据结构来存储存储项集或构件tree，但这部分工作我没有找到具体的实现，这里就不展开啦～

一些工作希望通过减少存储空间来优化，Index-BitTableFI算法采用索引数组和位图存储来减少Apriori的冗余，提升了Apriori类算法的性能。我个人感觉这种方式优点类似布隆过滤器，也就是哈希索引+位图。

图片 2