FP-tree定义

(1)频繁模式树(Frequent Pattern tree)简称为FP-tree，是满足下列条件的一个树结构：它由一个根节点(值为null)、项前缀子树(作为子女)和一个频繁项头表组成。

(2)项前缀子树中的每个结点包括三个域：item_name、count和node_link，其中：

item_name记录结点表示的项的标识；count记录到达该结点的子路径的事务数；

node_link用于连接树中相同标识的下一个结点，如果不存在相同标识下一个结点，则值为“null”。

(3)频繁项头表的表项包括一个频繁项标识域：item_name和一个指向树中具有该项标识的第一个频繁项结点的头指针：head of node_link。

对于包含在FP-tree中某个结点上的项α，将会有一个从根结点到达α的路径，该路径中不包含α所在结点的部分路径称为α的前缀子路径(prefix subpath)，α称为该路径的后缀。在一个FP-tree中，有可能有多个包含α的结点存在，它们从频繁项头表中的α项出发，通过项头表中的head of node_link和项前缀子树中的node_link连接在一起。FP-tree中每个包含α的结点可以形成α的一个不同的前缀子路径，所有的这些路径组成α的条件模式基(conditional pattern base)。用α的条件模式基所构建的FP-tree称为α的条件模式树(conditional 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的高度压缩。

FP-tree的相关的性质定理

基于FP-tree挖掘频繁闭项集,需要了解FP-tree如下性质和定理:

性质2.1(结点链性质)对于任何频繁项ia，从FP-tree的头表对应ia项的头指针(headof node_link)开始，通过遍历ia的结点链(node_link)可以挖掘出所有包含ia的频繁模式。

性质2.2(前缀路径性质)为了计算以ia为后缀的频繁模式，仅仅需要在FP-tree中计算ia结点的前缀路径，并且前缀路径中每个结点的频繁计数等于ia结点的频繁计数。

定理2.3(分段增长)设α为事务数据库D中的一个项集，B是α的条件模式基，而β是B中的一个项集，那么在D中α∪β的支持度等于B中β的支持度。

推论2.1(模式增长)设项α为事务数据D中的一个项集，B是α的条件模式基，13而β是B中的一个项集，那么α∪β为频繁项集的充分必要条件是β也为频繁项集。