FP-tree的FP-tree构造算法

FP-tree的FP-tree构造算法

输入：事务数据库D和最小支持度阈值minσ。
输出：D所对应的FP-tree。
方法：FP-tree是按以下步骤构造的：
(1)扫描事务库D，获得D中所包含的全部频繁项集1F，及它们各自的支持度。对1F中的频繁项按其支持度降序排序得到L。
(2)创建FP-tree的根结点T，以“null”标记。再次扫描事务库。对于D中每个事务，将其中的频繁项选出并按L中的次序排序。设排序后的频繁项表为[p|P]，其中p是第一个频繁项，而P是剩余的频繁项。调用insert_tree([p|P],T)。insert_tree([p|P],T)过程执行情况如下：如果T有子女N使N .item_name=p.item_name，则N的计数增加1；否则创建一个新结点N，将其计数设置为1，链接到它的父结点T，并且通过node_link将其链接到具有相同item_name的结点。如果P非空，递归地调用insert_tree(P，N)。FP-tree是一个高度压缩的结构，它存储了用于挖掘频繁项集的全部信息。FP-tree所占用的内存空间与树的深度和宽度成比例，树的深度一般是单个事务中所含项目数量的最大值；树的宽度是平均每层所含项目的数量。由于在事务处理中通常会存在着大量的共享频繁项，所以树的大小通常比原数据库小很多。频繁项集中的项以支持度降序排列，支持度越高的项与FP-tree的根距离越近，因此有更多的机会共享结点，这进一步保证了FP-tree的高度压缩。