FP-Tree的表示方法是什么？

FP-tree是对输入数据的简洁描述。它是通过一次读取一个事务的数据集，并将每个事务映射到FP-tree中的一个路径来构建的。多个事务可能有许多共同的项，它们的路径可能会重叠。

路径重叠越多，使用FP-tree架构实现的压缩就越多。如果FP-tree的大小足以放入主内存，这将使我们能够直接从内存中的架构中提取频繁项集，而不是对保存在磁盘上的数据进行重复的遍历。

树中的每个节点包含一个项目的标签以及一个计数器，该计数器显示映射到给定路径的多个事务。最初，FP-tree只包含由空符号定义的根节点。

FP-tree的构建过程如下：

首先扫描数据集以确定每个项目的支持度计数。不频繁的项目将被丢弃，而频繁项目的支持度计数将被保留。

算法对数据进行第二次遍历以构建FP-tree。在查看第一个事务{a, b}后，将创建标记为a和b的节点。将形成一条从null→a→b的路径来表示该事务。路径上的每个节点的频率计数为1。

在查看第二个事务{b, c, d}后，将为项目b、c和d创建一组新的节点。然后形成一条路径null→b→c→d来表示该事务。

此路径上的每个节点的频率计数也为1。尽管前两个事务有一个频繁项b，但它们的路径是不相交的，因为这些事务不共享频繁的前缀。

第三个事务{a, c, d, e}与第一个事务共享一个频繁前缀项（即a）。因此，第三个事务的路径null→a→c→d→e与第一个事务的路径null→a→b重叠。由于它们的路径重叠，节点a的频率计数增加到2，而新创建的节点c、d和e的频率计数仍然为1。

这个过程将持续到每个事务都被映射到FP-tree中的一个路径为止。FP-tree的大小小于未压缩数据的大小，因为市场篮子数据中的多个事务共享许多共同的项。

更新于：2022年2月11日

745 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告