FP-growth算法基于Apriori构建,但采用了高级的数据结构减少扫描次数,大大加快了算法速度。FP-growth算法只需要对数据库进行两次扫描,而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁,因此FP-growth算法的速度要比Apriori算法快。
FP-growth算法发现频繁项集的基本过程如下:
·构建FP树;
·从FP树中挖掘频繁项集。
FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。FP代表频繁模式。一棵FP树看上去与计算机科学中的其他树结构类似,但是它通过链接来连接相似元素,被连起来的元素项可以看成一个链表。图11-5给出了FP树的一个例子。
图11-5 FP树结构举例
与搜索树不同的是,一个元素项可以在一棵FP树种出现多次。FP树辉存储项集的出现频率,而每个项集会以路径的方式存储在数中。存在相似元素的集合会共享树的一部分。只有当集合之间完全不同时,树才会分叉。树节点上给出集合中的单个元素及其在序列中的出现次数,路径会给出该序列的出现次数。相似项之间的链接称为节点链接,用于快速发现相似项的位置。
假设数据库中存在下面六条购物记录:
·r,z,h,j,p
·z,y,x,w,v,u,t,s
·z
·r,x,n,o,s
·y,r,x,z,q,t,p
·y,z,x,e,q,s,t,m
元素项z出现了5次,集合{r,z}出现了1次。于是可以得出结论:z一定是自己本身或者和其他符号一起出现了4次。集合{t,s,y,x,z}出现了2次,集合{t,r,y,x,z}出现了1次,z本身单独出现1次。就像这样,FP树的解读方式是读取某个节点开始到根节点的路径。路径上的元素构成一个频繁项集,开始节点的值表示这个项集的支持度。我们可以快速读出项集{z}的支持度为5、项集{t,s,y,x,z}的支持度为2、项集{r,y,x,z}的支持度为1、项集{r,s,x}的支持度为1。FP树中会多次出现相同的元素项,也是因为同一个元素项会存在于多条路径,构成多个频繁项集。但是频繁项集的共享路径是会合并的,如上图中的{t,s,y,x,z}和{t,r,y,x,z}
和之前一样,我们取一个最小阈值,出现次数低于最小阈值的元素项将被直接忽略。最小支持度设为3,所以q和p没有在FP中出现如图11-6所示。
图11-6 FP树构建过程