关联分析算法FP-Growth学习笔记

Apriori算法的学习中,我们了解到Apriori算法需要不断生成候选项目队列和不断得扫描整个数据库进行比对,I/O是很大的瓶颈。为了解决这个问题,FP-Growth利用了巧妙的数据结构,无论多少数据,只需要扫描两次数据集,大大降低了Aproir挖掘算法的代价。FP-Growth算法主要包含有两个步骤:

  • 建立一个精简的数据结构:FP-tree(frequent-pattern tree, 频繁模式树)
  • 从FP-tree中提取频繁项集

FP-Growth算法原理

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

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

我们以下面的数据为例进行详细了解:

上面的流程讲的有些迷糊,我们用一个数据举例:定义“TID”为订单ID,“Items bought”为一次订单内购买的商品:

TID Items bought
100 {f, a, c, d, g, i, m, p}
200 {a, b, c, f, l, m, o}
300 {b, f, h, j, o}
400 {b, c, k, s, p}
500 {a, f, c, e, l, p, m, n}

建立项头表

在构建FP-Tree之前,首先要建立一张项头表。扫描原始数据,并对每个商品进行计数。在这里可以设置阈值,比如保留最少要出现三次的商品。筛选后剩下a,b,c,f,m,p这六个商品,将这些商品按数量降序排列,生成项头表。

Item Count
f 4
c 4
a 3
b 3
m 3
p 3

 

筛选排序原始数据

接下来开始第二次扫描原属数据,对于每条数据,剔除非项头表上的商品,并按照支持度降序排列。比如订单100,购买商品为{f, a, c, d, g, i, m, p},剔除数据后为{f, a, c, m, p},排序后为{f, c, a, m, p}。其他的原始数据以此类推进行处理,得到排序后的数据集。

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} {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}

构建FP-Tree

有了项头表和筛选排序后的原始数据集,接下来就可以构建FP-Tree了。建立FP-Tree需要我们一条条的读取筛选排序后的原始数据,并按照顺序依次插入到树中。如果有公共的祖先节点,则在对应的祖先节点加1。同时,新节点出现时,需要将其链接到项表头对应的节点链表。直到所有数据都插入树中,则构建完成。

接下来还是用上面的数据举个例子。首先插入TID 100,此时FP-Tree没有其他节点,因此{f, c, a, m, p}是一个独立的路径,所有节点计数为1, 项头表通过节点链表链接上对应的新增节点。

接着插入TID 200,{f, c, a, b, m},其中f、c、a三个节点公用,计数变为2,到b节点产生新的分支,m为b的子节点,两个节点计数为1。当然,对应的b、m两个节点的链表也要更新。

依次处理剩下的三条数据,构建完成FP-Tree

挖掘频繁项集

准备好了FP-Tree,接下来就可以开始挖掘频繁项集。遍历项头表依次挖掘,找到每项的条件模式基。条件模式基是以要挖掘的节点作为叶子节点所对应的子树。得到这个子树,将子树中每个节点的的计数设置为叶子节点的计数,并删除计数低于约定值的节点。从这个条件模式基,我们就可以递归挖掘得到频繁项集了。假设需要的最小节点计数为2,开始挖掘p节点,如下图所示:

删除图中节点计数小于2的红色{c:1}、{b:1}、{p:1}节点,得到{p:2}节点的条件模式基为{f:2, c:2, a:2, m:2}。通过它,可以递归得到频繁二项集{f:2, p:2}、{c:2, p:2}、{a:2, p:2}、{m:2, p:2},频繁三项集{f:2, c:2, p:2}、{f:2, a:2, p:2}等等,最后得到最大的频繁项集为频繁五项集,为{f:2, c:2, a:2, m:2, p:2}。如果最小节点计数为1,则可在挖掘完上面的子树后,根据项表头对应的节点链表找到红色的节点{p:1},继续挖掘频繁项集。至此,p节点挖掘完毕,可以继续挖掘其他节点。挖掘完所有节点,也就得到了所有的频繁项集。至于最后f节点,由于它的条件模式基为空,因此可以不用去挖掘。

FP-Growth的Python实现

其他参考:

微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

时间序列趋势判断

判断时间序列数据是上升还是下降是我们常见的问题。比如某个股票在过去一年整体趋势是上升还是下降。我们可以通过画图

聚类算法之Affinity Propagation(AP)

Affinity Propagation算法简介 AP(Affinity Propagation)通常被翻译为

机器学习算法之朴素贝叶斯

贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。而朴素贝叶斯分类是贝叶斯分类

发表评论

电子邮件地址不会被公开。 必填项已用*标注