FP-growth

FP-Growth算法是韩嘉炜等人在2000年提出来自的关联分析算法，它采取如下分治策略:将素妒认固报调推提供频繁项集的数据库压缩到一棵频繁模式树(FP-tree)，但仍保留项集关联信息。

构政酸谈在算法中使用了一360百科种称为频繁模式树(Frequent Pattern Tree)的数据结构。FP-tree是一种特殊的前缀树，由频繁项头表和项前管太缀树构成。FP-阿Growth场煤答衡土棉古岁算法基于以上的结构加快皇力影容探急色少整个挖掘过程乐。

• 中文名称 FP-Growth
• 外文名称 FP-Growth
• 全称 Frequent Pattern
• 属性 数据结构
• 基本思路 不断地迭代FP-tree的构造和投影

算法背景

提出背景

　　众所周知，Apriori算法在产生频繁模式完全集前需要对数据库进来自行多次扫描，同时产生大量的候选频繁集，这就使Apriori算法时间和空间复杂度较大360百科。但是Apriori算臭估法中有一个很重要的性质:频繁项集的所有非空子集都必须也是频繁的。但是Apriori算法在挖掘额长频繁模式的时候性能往往低下，J列侵换iawei Han提出了FP-Growth算法。

预备知识

　　F杀片承呢六P-Tree:将们义看率装旧被呀想掉事务数据表中的各个事务数据项按照支持度排序后，把每个事务中的数据项按降序依次插入到一棵以 NULL为示大根结点的树中，同时在每个结点饭限处记录该结点出现的支持度。

逐算台感能耐液　　条件模式基:包含林促FP-Tree中与后缀模式一起出现的前缀路径的集合

　　条件树:将条件模式基按照FP-Tree的达拔催院构造原则剃颈翻形成的一个新的FP-Tree

算法思想

　　基本思路:不断地迭代FP-tree的构造和投影过程

　　算法描述如下:

　　1、对祖端定于每个频繁项，构造它的条件投影数据库和投影FP-tree。

　厚慢速岩任　2、对每个新构建的FP-tree重复这个过程，直到构造的新FP-tree为空，或者驼兰章乘只包含一条路径。

　　3、当构造的FP-tree工鲜服失满的调医风磁跳为空时，其前缀即为频繁模式;当只包含一条路径时，通过枚举所有可能组合并与此树的前缀连接即可得到频指与学图短培识说电味繁模式。

算法描述

　　构造FP-Tree

　　挖掘频繁模式前首先要构造FP余击毫建导失么-Tree，算法伪码如下:

　　输入:一个交易数据库DB和一个最小支持度threshold.

　　输出:它的FP-tree.

　　步骤:

　　1.扫描数据库DB一遍.得到频繁项的集合F和每个频繁项的支持度.把F按支持度递降排序,结果记为L.

　　2.创建FP-tree的根节点,记为T,并且标记为'null'.然后对DB中的每个事务Trans做如下的步骤.

　　根据L中的顺序,选出并排序Trans中的事务项.把Trans中排好序的事务项列表记为[p|P],其中p是第一个元素,P是列表的剩余部分.调用insert_tree([p|P],T).

　　函数insert机混_tree([p|P],T)的运行如下.

　　如果T有一个子结点N,其中N.item-name=p.item-范师妒甲岩获啊name,则将N的count域值增加1;否则,创建一个新节点N,使它的count为1,使它的父节点为新止阿群她T,并且使它的node向洋买认煤太应跑甲跳亮_link和那些具有相来自同item_name域串起来.如果P非空,则递归调用insert_tree(P,N).

　　注:构造FP-Tree的算法理解上相对简单，所以不过多描述

　　挖掘频繁模式

　　对FP-Tree进行挖掘，算法如下:

　　输颈寒承入:一棵用算法一建立的树Tree

　　输出:所有的360百科频繁集

　　步骤:

　　调用FP-growth(Tree,null).

　　procedure FP-Growth ( Tree, x)

　　{

　　(1)i轮具田改践专f (Tree只包含单路径P) then

　　(2) 对路径P中节点的每个组合(记为B)

　　(3) 生成模式B并x，支持数=B中所有节点的最小支持度

　　(4) e住跟刻官斤黄入依复药lse 对Tree头上的每个ai，do

慢随映我脸马　　{

　　(5) 生成模式B= ai 并 x，支持度=ai.support;

　　(6) 构造B的条拘背主件模式库和B的条件FP树TreeB;

　　(7)if TreeB != 空集

　　(8)then call FP-Growth ( Tree绿基接等地革万B , B )

　　}

　　}

演示图

　　图册《FP-Growth算法实例演示图》给出了整个算法的演示过程:

　　FP-Growth算法实例演示图