关联分析：fp-growth算法

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

1、关联分析：FP-Growth算法关联分析乂称关联挖掘，就是在交易数据、关系数据或其他信息载体屮，查找存在于项冃集合或对象集合Z间的频繁模式、关联、相关性或因果结构。关联分析的一个典型例子是购物篮分析。通过发现顾客放入购物篮中不同淌品之间的联系，分析顾客的购买习惯。比如，67%的顾客在购买尿布的同时也会购买啤酒。通过了解哪些商品频繁地被顾客同时购买"可以帮助零售商制定营销策略。关联分析也可以应用于其他领域，如生物信息学、医疗诊断、网页挖掘和科学数据分析等。1.问题定义TED面包牛奶尿布呻济乐1110000210111030111014111100S

2、111001图1购物篮数据的二元表示图1表示顾客的购物篮数据，其中每一行是每位顾客的购物记录，对应一个事务，而每一列对应一个项。令l=｛ii,i2,...,id｝是购物篮数据中所有项的集合,而丁=｛切t2,...,tz｝是所有事务的集合。每个事务£包含的项集都是I的子集。在关联分析中，包含0个或多个项的集合被称为项集(itemset)。所谓的关联规则是指形如X-Y的麦达式，其中X和Y是不相交的项集。在关联分析中，有两个重要的概念支持度(support)和置信度(confidence)o支持度确定规则可以用于给定数据集的频繁程度，而置信度确定Y在包

3、含X的事务中岀现的频繁程度。支持度(s)和置信度(c)这两种度量的形式定义如下：or(X5)c(X5)公式1其屮，N是事务的总数。关联规则的支持度很低，说明该规则只是偶然出现，没有多大意义。另一方面，置信度可以度量通过关联规则进行推理的可靠性。因此，大多数关联分析算法采用的策略是：(1)频繁项集产生：其冃标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。(2)规则的产牛：其冃标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则。2.构建FP-treeFP-growth算法通过构建FP-tree来压缩事务数据库中的信息，

4、从而更加有效地产生频繁项集。FP・tree其实是一棵前缀树，按支持度降序排列，支持度越高的频繁项离根节点越近，从而使得更多的频繁项可以共亨前缀。TIDItemsBought(Ordeied)FYequeiitItems100/,qc,(1、g、t,m,pc,a,m,p200a,6,c,/,Z,m,o/,c,a,6,m3006,/,h,jyof、b1006,c,k、s,p50()a,c,e,/,p,m,nC,a,m,p图2事务型数据库图2表示用于购物篮分析的事务型数据库。其中，a,b,…，p分别表示客户购买的物品。首先，对该事务型数据库进行一次扫描

5、，计算每一行记录屮各种物品的支持度，然后按照支持度降序排列，仅保留频繁项集，剔除那些低于支持度阈值的项，这里支持度阈值取3,从而得到＜(f：4),(c:4),(a:3),(b:3),(m:3,(p:3)＞(由于支持度计算公式中的N是不变的,所以仅需要比较公式中的分子)。图2中的第3列展示了排序后的结果。FP-tree的根节点为null,不表示任何项。接下来，对事务型数据库进行第二次扫描，从而开始构建FP-tree：第一条记录vf,c,a,m,p＞对应于FP-tree中的第一条分支＜(f:1),(c:1),(a:1),(m:1),(p:1)＞：Nu

6、llP:1图3第一条记录由于第二条记录vf,c,a,b,与第一条记录有相同的前缀vf,c,a＞,因此vf,c,a＞的支持度分別加一，同时在(a:2)节点下添加节点(b:1),(m:1)o所以，FP-tree中的第二条分支是＜(f:2),(c:2),(a:2),(h:1),Nullf:?图4第二条记录第三条记录vf,b＞与前两条记录相比，只有一个共同前缀vf＞,因此，只需要在(f:3)下添加节点vb：1A:Null■P:1■图5第三条记录第四条记录vc,b,p＞与之前所有记录都没有共同前缀，因此在根节点下添加节点(c:1),图6第四条记录类似地，将

7、第五条记录vf,c,a,m,p＞作为FP-tree的一个分支，更新相关节点的支持度：Null图7第五条记录为了便于对整棵树进行遍历，建立一张项的头表(anitemheadertable)。这张表的第一列是按照降序排列的频繁项。第二列是指向该频繁项在FP-tree中节点位置的指针。FP-tree屮每一个节点还有一个指针，用于指向相同名称的节点：图8FP-tree综上，FP-tree的节点可以定义为：2classTreeNode{345678private:Stringname;//节点名称intcount;//支持度计数TreeNode^paren

8、t;//父节点Vectorchildren;//子节点TreeNode*nextllomonym;//指向同名节点