fp-growth算法及演示程序

《fp-growth算法及演示程序》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、FP-Growth算法及演示程序FP-Growth(频繁模式增幻兑法足韩家炜老师在2000年提出的关联分析兑法，它采取如下分治策略：将提供频繁项集的数裾库压缩到一棵频繁模式树(FP-Tree),但仍保贸项集关联信息；该算法和Apriori算法最人的不冋有两点：第一，不产生候选集，第二，只需要两次遍历数据库，大大提高了效率。算法伪代码算法：FP-增长。使用FP-树，通过模式段增长，挖掘频繁模式。输入：事务数据库D;最小支持度阈值w/uw/7。输出：频繁模式的完全集。1.按以下步骤构造FP-树：(a)扫描事务数据库D—次。收集频繁项的集合

2、F和它们的支持度。对F按支持度降序排序，结果为频繁项表L。(b)创建FP-树的根结点，以“null”标记它。对于D中每个事务Trans,执行：选择Trans巾的频繁项，并按L巾的次序排序。设排序后的频繁项表为［p

3、P］，其中，p是第一个元素，而P是剩余元素的表。调川inSert_tree(［p

4、P］，T)。该过程执行情况如卜。如果T科了女N使得N.item-name=p.item-name，贝ijN的计数增加1;否则创建一个新结点N,将M:计数设置为1，链接到它的父结点T,丼且通过结点链结构将其链接到其有相同item-name的结如果

5、P非空，递!地凋用insert_tree(P，N)。2.FP-树的挖掘通过调用FP_growth(FP_tree，null)实现。该过程实现如下：procedureFP_growth(Tree,a)(1)ifTree含单个路挽Pthen(2)for路径P巾结点的每个组合(记作p)(3)产生模式pUa，•其支持度support=P中结点的域小支持度；(4)elseforeachai在Tree的头部｛(5)产生一个模式P=aiUa，其支持度support=ai.support；(6)构造p的条件模式基，然后构造p的条件FP-树TreeP；

6、(7)ifTreeP关0then(8)调用FPgrowth(Treep，p);}点Buildd:.成的头表和FP-TreeBuildTIDIteas

7、TO12,11,15T112,14T212,13T312,11,14T411,13T512,13T611.13T712,11,13,15T812.11,13倒序场繁项头表Ra臘eCountLinkI12712:711611:413613:214214:115215:1StepPrevHext事务数据痒ConditionTreelodeI点Step后生成再点Next会一次加入一个事务项进行

8、生成FP-Tree最后生成完了FP-Tree后/XdjConditionTreeMode进入FP-Tree挖掘模又姑不•.当前义•表中选中项的条件FP-Tree事务数据库TIDIte>sTO12,11,15T112,14T212,13T312,11,14T4II,13T512,13T6II,13T712,11,13,15T812,11,13倒序穽繁项头表la扈cCountLink12712:7II611:413613:214214:115215:1ConditionTreelode15:1StepPrevBuildBeit