简介
关于频繁模式挖掘的一个经典例子应该就是"啤酒和尿布"了，虽然看到很多人都说这个是编造的，但是也不妨碍用它来说明频繁模式挖掘到底是干什么的。简单来说，频繁模式就是当出现物品A时也经常出现物品B，比如在分析超市的购物清单时，发现买啤酒的人经常也买尿布。
基本概念
事务：它由一组物品组成，可看作一个订单中的物品集合。
支持度：某几个物品一起出现在事物中的次数或在数据库中所占的比例
置信度：在出现A时出现B的概率，就是P(B|A) = P(A B) / P(A)
Apriori
Apriori类的方法基于的基本思想是频繁k+1项集是由频繁k项集构成，那么就可以通过一遍一遍地扫描数据集来发现频繁模式，首先找到频繁１项集，再扫描数据库由频繁１项集找到频繁２项集，等等。
FP-growth
FP-growth是一种新的方法，它只需要扫描两次数据集。FP-growth包含两部分内容，首先需要构造FP-tree，它高度压缩了数据库中的信息。然后在FP-tree上挖掘出频繁模式。
构造FP-tree
FP-tree的基本思想是通过共享事务的前缀来压缩数据库，树中的每个节点包含４部分信息：物品的标识、节点的计数(表示从根节点到这个节点的路径出现的次数)、指向孩子的链接以及指向父节点的链接。
构造FP-tree只需遍历两次数据库，首先扫描一次数据库，统计出每个物品出现的次数，过滤掉支持度不够的物品，也就是寻找频繁一项集。得到频繁一项集后将它们按出现次数从大到小排序，然后创建一个对应的链表，链表中的每个节点都是一个指向链表的表头，这个链表中的节点是那个对应物品在树种出现的所有结点。然后再一次地扫描数据库，对于其中的每个事务(item1,item2,item3...)，将其按物品出现的次数排序。此时，需从树的根节点开始添加这个排好序的事务，对于事务中的每个物品，如果这个物品出现在树中当前路径之下，则将那个节点的计数+1；否则在当前路径之下添加一个新的节点，设置计数为1，并将这个新的节点加入到节点链表中相应的链表尾部。
比如当数据库如下图所示:
第一次扫描计数结果为：(a:3),(b:3),(c:4),(d:1),(e:1),(f:4),(g:1),(h:1),(i:1),(j:1),(k:1),(l:2),(m:3),(n:1),(o:2),(p:3)。按最小支持度为３过滤并排序后的结果为：
(f:4),(c:4),(a:3),(b:3),(m:3),(p:3)。第二次扫描数据库时，对于事务100，排好序后为(f,c,a,m,p)，此时树只有根节点，只需依次添加新节点即可。而对于事务200，排好序后为(f,c,a,b,m)，此时树中已经存在路径(f,c,a)，那么将这个前缀路径中的节点计数都+1，并在a节点后添加b、m节点即可。构造出的树如下图所示：
图中左侧为物品链表头，虚线表示这个链表的链接，实线表示树中的链接。
在FP-tree中挖掘频繁模式
利用构造好的FP-tree可快速地挖掘出频繁模式，只需从低向上处理节点链表即可。对于链表中的每一个物品，利用父结点求出树中所有这个物品的前缀路径，利用这些路径便可挖掘出所有包含这个物品的频繁项集。比如对于m结点，树中的前缀路径为(f:2,c:2,a:2,m:2)以及(f:1,c:1,a:1,b:1,m:1)，这叫做条件模式基(conditional pattern base)。最终其它物品与m共同出现的次数就为(f:3,c:3,a:3,b:1)，所以所有包含m结点的频繁项集就为{(m),(f,m),(c,m),(a,m),(f,c,m),(f,a,m),(c,a,m),(f,a,c,m)}。这个过程如图所示：
代码实现
参考文献
1: Mining Frequent Patterns without Candidate Generation
网友评论