首页 » 机器学习实战 » 机器学习实战全文在线阅读

《机器学习实战》12.1 FP树:用于编码数据集的有效方式

关灯直达底部

FP-growth算法

优点:一般要快于Apriori缺点:实现比较困难,在某些数据集上性能会下降适用数据类型:标称型数据

FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。FP代表频繁模式(Frequent Pattern)。一棵FP树看上去与计算机科学中的其他树结构类似,但是它通过链接(link)来连接相似元素,被连起来的元素项可以看成一个链表。图12-1给出了FP树的一个例子。

图12-1 一棵FP树,看上去和一般的树没什么两样,包含着连接相似节点的链接

同搜索树不同的是,一个元素项可以在一棵FP树中出现多次。FP树会存储项集的出现频率,而每个项集会以路径的方式存储在树中。存在相似元素的集合会共享树的一部分。只有当集合之间完全不同时,树才会分叉。 树节点上给出集合中的单个元素及其在序列中的出现次数,路径会给出该序列的出现次数。上面这一切听起来可能有点让人迷糊,不过不用担心,稍后就会介绍FP树的构建过程。

相似项之间的链接即节点链接(node link),用于快速发现相似项的位置。为了打消读者的疑惑,下面通过一个简单例子来说明。表12-1给出了用于生成图12-1中所示FP树的数据。

表12-1 用于生成图12-1中FP树的事务数据样例

事务ID事务中的元素项001r, z, h, j, p002z, y, x, w, v, u, t, s003z004r, x, n, o, s005y, r, x, z, q, t, p006y, z, x, e, q, s, t, m

在图12-1中,元素项z出现了5次,集合{r,z}出现了1次。于是可以得出结论:z一定是自己本身或者和其他符号一起出现了4次。我们再看下z的其他可能性。集合{t,s,y,x,z}出现了2次,集合{t,r,y,x,z}出现了1次。元素项z的右边标的是5,表示z出现了5次,其中刚才已经给出了4次出现,所以它一定单独出现过1次。通过观察表12-1看看刚才的结论是否正确。前面提到{t,r,y,x,z}只出现过1次,在事务数据集中我们看到005号记录上却是{y,r,x,z,q,t,p}。那么,q和p去哪儿了呢?

这里使用第11章给出的支持度定义,该指标对应一个最小阈值,低于最小阈值的元素项被认为是不频繁的。如果将最小支持度设为3,然后应用频繁项分析算法,就会获得出现3次或3次以上的项集。上面在生成图12-1中的FP树时,使用的最小支持度为3,因此q和p并没有出现在最后的树中。

FP-growth算法的工作流程如下。首先构建FP树,然后利用它来挖掘频繁项集。为构建FP树,需要对原始数据集扫描两遍。第一遍对所有元素项的出现次数进行计数。记住第11章中给出的Apriori原理,即如果某元素是不频繁的,那么包含该元素的超集也是不频繁的,所以就不需要考虑这些超集。数据库的第一遍扫描用来统计出现的频率,而第二遍扫描中只考虑那些频繁元素。

FP-growth的一般流程

  1. 收集数据:使用任意方法。
  2. 准备数据:由于存储的是集合,所以需要离散数据。如果要处理连续数据,需要将它们量化为离散值。
  3. 分析数据:使用任意方法。
  4. 训练算法:构建一个FP树,并对树进行挖据。
  5. 测试算法:没有测试过程。
  6. 使用算法:可用于识别经常出现的元素项,从而用于制定决策、推荐元素或进行预测等应用中。