数据挖掘fp-growth算法实验报告

《数据挖掘fp-growth算法实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、FP-Growth算法实验报告一、算法介绍数据挖掘是从数据库中提取隐含的、未知的和潜在的有用信息的过程,是数据库及相关领域研究中的一个极其重要而又具有广阔应用前景的新领域.目前,对数据挖掘的研究主要集中在分类、聚类、关联规则挖掘、序列模式发现、异常和趋势发现等方面,其中关联规则挖掘在商业等领域中的成功应用使它成为数据挖掘中最重要、最活跃和最成熟的研究方向.现有的大多数算法均是以Apriori先验算法为基础的,产生关联规则时需要生成大量的候选项目集.为了避免生成候选项目集,Han等提出了基于FP树频繁增长模式（F

2、requent-PatternGrowth，FP-Growth）算法。FP树的构造过程可描述为:首先创建树的根结点,用“null”标记.扫描交易数据集DB,每个事务中的项目按照支持度递减排序,并对每个事务创建一个分枝.一般地,当为一个事务考虑增加分枝时,沿共同前缀上的每个结点的计数值增加1,为跟随在前缀之后的项目创建结点并链接.为方便树的遍历,创建一个频繁项目列表,使得每个项目通过一个结点头指针指向它在树中的位置.FP树挖掘过程可描述为:由长度为1的频繁项目开始,构造它的条件项目基和条件FP树,并递归地在该树上

3、进行挖掘.项目增长通过后缀项目与条件FP树产生的频繁项目连接实现.FP-Growth算法将发现大频繁项目集的问题转换成递归地发现一些小频繁项目,然后连接后缀.它使用最不频繁的项目后缀,提供了好的选择性。算法：FP-Growth。使用FP树，通过模式增长挖掘频繁模式。输入：nD：事物数据库nmin_sup：最小支持度阈值输出：频繁模式的完全集。方法：1.按一下步骤构造FP树：7（a）扫描数据库D一次。手机频繁项的集合F和它们的支持度计数。对F按支持度计数降序排序，结果为频繁项列表L。（b）创建FP树的根节点，以“

4、null”标记它。对于D中每个事物Trans，执行：选择Trans中的频繁项，并按L中的次序排序。设Trans排序后的频繁项列表为[p

5、P]，其中p是第一个元素，而P是剩下的元素列表。调用insert_tree([p

6、P],T)。该过程执行情况如下。如果T有子女N使得N.item-name=p.item-name，则N的计数增加1；否则，创建一个新节点N，将其计数设置为1，链接到它的父节点T，并且通过节点链结构将其链接到具有相同item-name的结点。如果P非空，则递归地调用insert_tree(P,N)。

7、1.FP树的挖掘通过调用FP-growth（FP_tree,null）实现。该过程实现如下。ProcedureFP_growth(Tree,α)（1）ifTree包含单个路径Pthen（2）for路径P中结点的每个组合（记作β）（3）产生模式β∪α，其中支持度计数support_count等于β中结点的最小支持度计数；（4）elseforTree的表头中的每一个αi{（5）产生一个模式β=α∪αi,其中支持度计数support_count=αi.support_count;（6）构造β的调减模式基然后构造β的条

8、件FP树Treeβ；（7）ifTreeβ≠∅then（8）调用FP_growth(Treeβ,β)；}二、算法实现及实验结果本实验有两个测试集合：小数据集A：50条事物集，10个不同的项大数据集合B：5670事物集，100个不同项1.对数据集合A进行min_sup=8%计数产生的频繁项集结果如下：77表1.频繁一项集项集支持度计数支持度1I33570%2I9612%3I6510%4I1)1734%5I41428%6I71122%7I23468%8I81122%9I51632%表2.频繁二项集项集支持度计数支持度

9、1I2I6510%2I3I948%3I2I948%4I1I748%5I2I7714%6I3I7816%7I2I8612%8I3I8816%79I2I41122%10I2I51122%11I3I51326%12I3I11020%13I2I11122%14I3I22142%表3.频繁三项集项集支持度计数支持度1I2I5I7510%2I3I5I7612%3I3I2I7510%4I3I2I8510%5I2I5I8510%6I3I5I8612%7I2I1I4510%8I3I1I5510%9I2I1I5612%10I3I2

10、I5816%11I3I2I148%表4.频繁四项集项集支持度计数支持度1I3I2I5I7510%72I3I2I5I8510%3I3I2I1I548%2．对数据集B进行不同支持度实验时间消耗结果如下：图1.数据集B消耗时间三、算法的优缺点分析1.FP-Growth算法的优点：(1)一个大数据库能够被有效地压缩成比原数据库小很多的高密度结构，避免了重复扫描数据库的开销7(2)该算法基于FP