资源描述：
《2015.8.25FPGrowth算法及源码介绍.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1.1FPGrowth算法1.1.1基本概念关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响，分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。关联规则的相关术语如下：（1）项与项集这是一个集合的概念，在一篮子商品中的一件消费品即为一项（Item），则若干项的集合为项集，如{啤酒，尿布}构成一个二元项集。（2）关联规则一般记为的形式，X为先决条件，Y为相应的关联结果，用于表示数据内隐含的关联性。如：表示购买了尿布的消费者往往
2、也会购买啤酒。关联性强度如何，由三个概念——支持度、置信度、提升度来控制和评价。例：有10000个消费者购买了商品，其中购买尿布1000个，购买啤酒2000个，购买面包500个，同时购买尿布和面包800个，同时购买尿布和面包100个。（3）支持度（Support）支持度是指在所有项集中{X,Y}出现的可能性，即项集中同时含有X和Y的概率。该指标作为建立强关联规则的第一个门槛，衡量了所考察关联规则在“量”上的多少。通过设定最小阈值（minsup），剔除“出镜率”较低的无意义规则，保留出现较为频繁的项集所隐含的规则。设定最小阈值为5%，由于{尿布，啤酒}的支
3、持度为800/10000=8%，满足基本输了要求，成为频繁项集，保留规则；而{尿布，面包}的支持度为100/10000=1%，被剔除。（4）置信度（Confidence）置信度表示在先决条件X发生的条件下，关联结果Y发生的概率。这是生成强关联规则的第二个门槛，衡量了所考察的关联规则在“质”上的可靠性。相似的，我们需要对置信度设定最小阈值（mincon）来实现进一步筛选。具体的，当设定置信度的最小阈值为70%时，置信度为800/1000=80%，而的置信度为800/2000=40%，被剔除。（5）提升度（lift）提升度表示在含有X的条件下同时含有Y的可能
4、性与没有X这个条件下项集中含有Y的可能性之比：公式为confidence(artichok=>cracker)/support(cracker)=80%/50%=1.6。该指标与置信度同样衡量规则的可靠性，可以看作是置信度的一种互补指标。1.1.2FP-Growth算法FP-Growth(频繁模式增长)算法是韩家炜老师在2000年提出的关联分析算法，它采取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树（FP-Tree），但仍保留项集关联信息；该算法和Apriori算法最大的不同有两点：第一，不产生候选集；第二，只需要两次遍历数据库，大大提高了效
5、率。（1）按以下步骤构造FP-树(a)扫描事务数据库D一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序，结果为频繁项表L。(b)创建FP-树的根结点，以“null”标记它。对于D中每个事务Trans，执行：选择Trans中的频繁项，并按L中的次序排序。设排序后的频繁项表为[p
6、P]，其中，p是第一个元素，而P是剩余元素的表。调用insert_tree([p
7、P],T)。该过程执行情况如下。如果T有子女N使得N.item-name=p.item-name，则N的计数增加1；否则创建一个新结点N将其计数设置为1，链接到它的父结点T，并且通过结点链
8、结构将其链接到具有相同item-name的结点。如果P非空，递归地调用insert_tree(P,N)。（2）FP-树的挖掘通过调用FP_growth(FP_tree,null)实现。该过程实现如下：FP_growth(Tree,α)(1)ifTree含单个路径Pthen(2)for路径P中结点的每个组合（记作β）(3)产生模式β∪α，其支持度support=β中结点的最小支持度；(4)elseforeachai在Tree的头部(按照支持度由低到高顺序进行扫描){(5)产生一个模式β=ai∪α，其支持度support=ai.support；(6)构造β的
9、条件模式基，然后构造β的条件FP-树Treeβ；(7)ifTreeβ≠∅then(8)调用FP_growth(Treeβ,β)；}end1.1.3FP-Growth算法演示—构造FP-树（1）事务数据库建立原始事务数据库如下：TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3扫描事务数据库得到频繁1-项目集F。I1I2I3I4I567622定义minsup=20%，即最小支持度为2，重新排列F。I2I1I3I4I576622重新调整事务数据库。TidI
10、tems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I3
