什么是 fptree 算法

FP—tree由标记为“null”的一个根节点(root)、作为根节点之子节点的项前缀子树(item prefix subtrees)的集合、和—个频繁项头表(frequent item header table)所组成。
项前缀子树中的每个节点包含3个域：item_name,count和node_link。item _name记录了该节点所代表的项的名字。count记录了所在路径代表的事务中达到此节点的事务个数。 node_link指向下一个具有同样的item_name域的节点，如果没有这样一个节点，则其值被置为null。
频繁项头表包含两个域：Item_name和head of node_link. head of node_link指向FP—tree中具有相同Item_name的第一个节点。
根据FP_tree 的定义，我们得到FP_tree的构造方法
2 FP—tree的生成
FP—tree是通过两次扫描事务集建立的.
(1)扫描事务集D，获得D中所包含的全部频繁项集合F，及它们各自的支持度。对F中的频繁项按其支持度降序排序,结果记为L；
(2)创建FP—tree的根节点T，以“null”标(3) 记；然后对D中的每个事务Trans进行如下操作：根据L中的顺序，选出并排序Trans的频繁项．设排序后的频繁项表为[x|P]，其中x是第一个频繁项。而P是剩余的频繁项:调用insert—tree([x|P]，T)：insert—tree([x|P]，T)过程执行情况如下：如果T有子女N并使得N.item_name=x.item_name，则N的计数增加1；否则创建一个新节点N，将其计数设置为1，链接到它的父节点T、、并且通过节点链结构将其链接到具有相同item_name的节点；如果P非空，递归地调用INSERT—tree(P，N)。在事务集再次扫描完毕时，一个完全的FP—tree就建成了。
3 频繁模式的挖掘
FP—tree被建立后，频繁模式是采用下面的FP—growth方法对FP—tree进行挖掘得到的. Procedure FP_growth(Tree，α)／／tree为α的条件