数据挖掘 FP-Growth算法实验报告

FP-Growth算法实验报告

一、算法介绍

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

FP 树的构造过程可描述为: 首先创建树的根结点, 用“null”标记. 扫描交易数据集DB ,每个事务中的项目按照支持度递减排序,并对每个事务创建一个分枝. 一般地,当为一个事务考虑增加分枝时,沿共同前缀上的每个结点的计数值增加1 ,为跟随在前缀之后的项目创建结点并链接. 为方便树的遍历,创建一个频繁项目列表,使得每个项目通过一个结点头指针指向它在树中的位置. FP 树挖掘过程可描述为:由长度为1 的频繁项目开始,构造它的条件项目基和条件FP树,并递归地在该树上进行挖掘. 项目增长通过后缀项目与条件FP 树产生的频繁项目连接实现. FP-Growth 算法将发现大频繁项目集的问题转换成递归地发现一些小频繁项目,然后连接后缀.它使用最不频繁的项目后缀,提供了好的选择性。 算法:FP-Growth。使用FP树,通过模式增长挖掘频繁模式。 输入:

D:事物数据库

min_sup:最小支持度阈值

输出:频繁模式的完全集。 方法:

1. 按一下步骤构造FP树:

(a)扫描数据库D一次。手机频繁项的集合F和它们的支持度计数。对F按支持度计数降

序排序,结果为频繁项列表L。

(b)创建FP树的根节点,以“null”标记它。对于D中每个事物Trans,执行:

选择Trans中的频繁项,并按L中的次序排序。设Trans排序后的频繁项列表为[p|P],其中p是第一个元素,而P是剩下的元素列表。调用insert_tree([p|P],T)。该过程执行情况如下。如果T有子女N使得N.item-name=p.item-name,则N的计数增加1;否则,创建一个新节点N,将其计数设置为1,链接到它的父节点T,并且通过节点链结构将其链接到具有相同item-name的结点。如果P非空,则递归地调用insert_tree(P,N)。 2. FP树的挖掘通过调用FP-growth(FP_tree,null)实现。该过程实现如下。

Procedure FP_growth(Tree,α) (1)if Tree包含单个路径P then

(2)for 路径P中结点的每个组合(记作β)

Word文档免费下载Word文档免费下载:数据挖掘 FP-Growth算法实验报告 (共5页,当前第1页)

你可能喜欢

  • 关联规则挖掘
  • 企业私有云
  • 私有云建设
  • 企业年金方案
  • 信用评分
  • 数据挖掘案例
  • LTE培训
  • 数据挖掘应用案例

数据挖掘 FP Growth算法实验报告相关文档

最新文档

返回顶部