数据挖掘算法:关联分析二(FP-tree算法)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据挖掘算法:关联分析二(FP-tree算法),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1308字,纯文字阅读大概需要2分钟。
内容图文
![数据挖掘算法:关联分析二(FP-tree算法)](/upload/InfoBanner/zyjiaocheng/1067/95960561d97f4e9a8e168318d1f6cf0b.jpg)
三.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算法,时间复杂度和空间复杂都有了显著的提高。但是对海量数据集,时空复杂度仍然很高,此时需要用到数据库划分等技术。
原文:https://www.cnblogs.com/yuanninesuns/p/8022337.html
内容总结
以上是互联网集市为您收集整理的数据挖掘算法:关联分析二(FP-tree算法)全部内容,希望文章能够帮你解决数据挖掘算法:关联分析二(FP-tree算法)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。