[科普中国]-PFP-tree算法

2004 年，A Javed 等人在文章《Frequent Pattern Mining on Message Passing Multiprocessor Systems》中提出了一种基于模式增长的分布式频繁项集挖掘算法——PFP-tree 算法。PFP-tree 算法运用在消息传递型多核处理器中。首先，各处理器分别处理本地的数据集，计算并得到局部的频繁1-项集；接着，各处理器之间相互交换频1-项集，生成全局的项头表（header table）；然后，各处理器创建局部 FP-tree 并扫描项头表，交换各自的局部条件模式基。最后，在得到全局的条件模式基后，生成条件 FP-tree 并运用 FP-growth 算法在条件 FP-tree上递归挖掘频繁项集。

简介PFP-tree 算法是一种基于 MPI的挖掘算法，其中MPI 的全称是 Message Passing Interface，它是一种消息传递标准，同时也是一项被广泛采用的并行编程技术。基于MPI 的频繁项集挖掘算法都是一些并行算法，它们的特点是各个计算节点并行地挖掘频繁项集，因此算法的效率很高。但是它们也有很多的缺点，比如：没有容错能力、节点之间需要进行大量的通信等等，这些缺点严重影响了算法的性能。PFP-tree 算法是基于消息传递机制并行运行多个FP-growth算法1。

FP-growth 算法FP-growth算法是 Jiawei Han 等人在 2000 年提出的一种基于频繁模式树（Frequent Pattern tree，FP-tree）的频繁项集挖掘算法，它通过递归地方式来构建条件 FP-tree，以及在条件FP-tree 上进行频繁项集挖掘。FP-growth 采用了一种分治策略的思想，它将一个问题递归地转化为若干个子问题。FP-tree 存储了压缩后的事务数据以及关于频繁项集的关键信息，它是一种定义为如下的树结构：

1）它包含了一个根节点，记为 null，一个项前缀子树的集合作为根节点的孩子，以及一个频繁项头表；

2）项前缀子树的每一个节点包含了三个域：item-name、count 和 node-link，其中 item-name 表示这个节点所代表的项，count 表示的是到达该节点的路径的部分所表示的事务数目，而 node-link（虚线）则指向在 FP-tree 中具有相同item-name 的下一个节点，如果没有下一个节点的话则为 null，实线表示的是父亲节点和子节点之间的关系。

3）频繁项头表的每一条记录都包含有两个域：item-name 和 node-link（虚线）的起始位置，node-link 的起始位置记录着 FP-tree 中具有相同项的链接所在的起始地址。

算法的整体思路是这样的：首先，通过数据库的一次扫描，计算并得到支持度大于等于最小支持度阈值ξ的频繁 1-项集，并对频繁 1-项集按照支持度的递减顺序排序放在项头表（header table）中；接着，第二次扫描数据库，构建 FP-tree：

对于数据库中的每一条事务记录 T，根据项头表对 T 中的项按递减顺序排序并删除不在项头表中的项，之后按照构造 FP-tree 的方法将 T 插入 FP-tree 中并更新项头表的节点链接，当数据库扫描完成之后，FP-tree 也同时建立好了；

最后，在FP-tree 上进行频繁项集挖掘：在项头表（header table）中，从项头表的下面往上开始，由长度为 1 的频繁模式（即频繁 1-项集，初始的后缀模式）开始，构造它的条件模式基。这些条件模式基可以看成是一个子事务数据库，它是由 FP-tree中与后缀模式一起出现的前缀路径集所组成。接着，算法开始构造这个初始后缀模式的条件 FP-tree，构造方式与构造 FP-tree 的方式一样，然后递归地在该条件FP-tree 上实现挖掘，这个过程是一个递归挖掘的过程，模式的增长方式是通过将后缀模式与条件 FP-tree 产生的频繁模式连接起来，从而实现模式的增长。

TPFP-tree算法2008 年，J Zhou 等人在文章《Tidset-Based Parallel FP-tree Algorithm for the Frequent Pattern Mining Problem on PC Clusters》中提出了另一种并行挖掘频繁项集的方法—TPFP-tree 算法。TPFP-tree 算法采用事务标识（Transaction identification set，Tidset）来构建TPFP-tree，即通过事务标识 Tidset 来直接选择事务，而不是通过扫描数据库。Tidset 是一个表结构，它记录了所有事务的 ID，而每个事务包含了相关的数据项，所以 Tidset 所占用的内存基本上和计算节点的局部子数据库一样大。也正是因为如此，TPFP-tree 算法约束了目标数据库的大小。

消息传递接口消息传递接口（MPI）是一个跨语言的通讯协议，用于编写并行计算机。支持点对点和广播。或指基于消息传递的一种并行编程规范和编程环境，实现并行执行的进程或线程之间的数据交换和同步。MPI是一个信息传递应用程序接口，包括协议和和语义说明，他们指明其如何在各种实现中发挥其特性。MPI的目标是高性能，大规模性，和可移植性。MPI在仍为高性能计算的主要模型。主要的MPI-1模型不包括共享内存概念，MPI-2只有有限的分布共享内存概念。 但是MPI程序经常在共享内存的机器上运行。在MPI模型周边设计程序比在NUMA架构下设计要好因为MPI鼓励内存本地化。

本词条内容贡献者为:

方正 - 副教授 - 江南大学