首页 > 编程语言 > 详细

数据挖掘算法:关联分析二(FP-tree算法)

时间:2018-04-23 22:05:58      阅读:188      评论:0      收藏:0      [点我收藏+]

三.FP-tree算法

  下面介绍一种使用了与Apriori完全不同的方法来发现频繁项集的算法FP-tree。FP-tree算法在过程中没有像Apriori一样产生候选集,而是采用了更为紧凑的数据结构组织tree, 再直接从这个结构中提取频繁项集。FP-tree算法的过程为:

首先对事务中的每个项计算支持度,丢弃其中非频繁的项,每个项的支持度进行倒序排序。同时对每一条事务中的项也按照倒序进行排序。

根据每条事务中事务项的新顺序,依此插入到一棵以Null为根节点的树中。同时记录下每个事务项的支持度。这个过程完成之后,我们就得到了棵FP-tree树结构。

对构建完成的FP-tree,从树结构的上方到下方对每个项,将先前的路径转化为条件FP-tree。

根据每棵条件FP-tree,找出所有频繁项集。

这个对FP-tree算法过程的描述比较抽象,我们通过下面这个例子具体地了解一下FP-tree算法是如何找到频繁项集的。

(source: 数据挖掘:概念与技术Jiawei, Han)

首先对实务中的所有项集计算支持度,然后按照倒序排序,如下图中的绿表所示。然后对每条事务中的项也按照这个倒序,重新排列。例如,对T100这个事务,原来是无序的Ⅰ1, Ⅰ2, Ⅰ5, 但因为Ⅰ2的支持度按照倒序排列在Ⅰ1之前,因此重新排序之后的顺序为Ⅰ2,Ⅰ1,Ⅰ5。经过重新排序后的事务的项集如下表中的第三列所示。

重新扫描事务库,按照重新排序的项集的顺序依次插入以NULL为根节点的树中。对事务T100, 依次创建Ⅰ2,Ⅰ1,Ⅰ5三个结点,然后可以形成一条NULL→Ⅰ2→Ⅰ1→Ⅰ5的路径,该路径上所有结点的频度计数记为1。对事务T200,FP-tree中已经存在了结点Ⅰ2,于是形成一条NULL→Ⅰ2→Ⅰ4的路径,同时创建一个Ⅰ4的节点。此事,Ⅰ2结点上的频度计数增加1,记为2,同时结点Ⅰ4的频度计数记为1。按照相同的过程,扫描完库中的所有事务之后可以得到下图的树结构。

对于构建完成的FP-tree,从树的底部开始依次构建每个项的条件FP-tree。首先我们在上图中找到节点Ⅰ5,发现能够达到Ⅰ5的路径有两条{ Ⅰ2,Ⅰ1,Ⅰ5 :1}和{ Ⅰ2,Ⅰ1,Ⅰ3,Ⅰ5 :1}。

基于这两天路径来构造Ⅰ5的条件tree如同下图所示,其中Ⅰ3要被舍去,因为这里Ⅰ3的计数为1不能满足频繁项集的条件。然后用Ⅰ5的前缀{ Ⅰ2,Ⅰ1:2}列举所有与后缀Ⅰ5的组合,最终得到{Ⅰ2,Ⅰ5 },{ Ⅰ2,Ⅰ1 }和{Ⅰ2,Ⅰ1,Ⅰ5 }三个频繁项集。

对所有项执行上述步骤,我们可以得到所有项产生的频繁项集。

https://www.cnblogs.com/zhengxingpeng/p/6679280.html

优缺点评价:

FP-tree算法相对于Apriori算法,时间复杂度和空间复杂都有了显著的提高。但是对海量数据集,时空复杂度仍然很高,此时需要用到数据库划分等技术。

数据挖掘算法:关联分析二(FP-tree算法)

原文:https://www.cnblogs.com/yuanninesuns/p/8022337.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!