会员中心 |  会员注册  |  兼职信息发布    浏览手机版!    精选9.9元!    人工翻译    英语IT服务 贫困儿童资助 | 留言板 | 设为首页 | 加入收藏  繁體中文
当前位置:首页 > 机翻技术 > 识别技术 > 正文

FP树:用于编码数据集的有效方式

发布时间: 2023-03-28 09:22:49   作者:etogether.net   来源: 网络   浏览次数:
摘要: FP树,用于编码数据集的有效方式,实现比较困难,在某些数据集上性能会下降。


FP-growth算法


优点:一般要快于Apriori。

缺点:实现比较困难,在某些数据集上性能会下降。

适用数据类型:标称型数据。


FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。FP代表频繁模式(Frequent Pattern)。一棵FP树看上去与计算机科学中的其他树结构类似,但是它通过链接(link)来连接相似元素,被连起来的元素项可以看成一个链表。图1给出了FP树的一个例子。


图1.png

图1 一棵FP树,看上去和一般的树没什么两样,包含着连接相似节点的链接


同搜索树不同的是,一个元素项可以在一棵FP树中出现多次。FP树会存储项集的出现频率,而每个项集会以路径的方式存储在树中。存在相似元素的集合会共享树的一部分。只有当集合之间完全不同时,树才会分叉。树节点上给出集合中的单个元素及其在序列中的出现次数,路径会给出该序列的出现次数。上面这一切听起来可能有点让人迷糊,不过不用担心,稍后就会介绍FP树的构建过程。


相似项之间的链接即节点链接(node link),用于快速发现相似项的位置。为了打消读者的疑惑,下面通过一个简单例子来说明。表1给出了用于生成图1中所示FP树的数据。


表1.png

表1 用于生成图1 中FP树的事务数据样例


在图1中,元素项z出现了5次,集合{r,z}出现了1次。于是可以得出结论:z一定是自己本身或者和其他符号一起出现了4次。我们再看下z的其他可能性。集合{t,s,y,x,z}出现了2次,集合{t,r,y,x,z}出现了1次。元素项z的右边标的是5,表示z出现了5次,其中刚才已经给出了4次出现,所以它一定单独出现过1次。通过观察表1看看刚才的结论是否正确。前面提到{t,r,y,x,z}只出现过1次,在事务数据集中我们看到005号记录上却是{y,r,x,z,q,t,p}。那么,q和p去哪儿了呢?


这里使用支持度定义,该指标对应一个最小阈值,低于最小阈值的元素项被认为是不频繁的。如果将最小支持度设为3,然后应用频繁项分析算法,就会获得出现3次或3次以上的项集。上面在生成图1中的FP树时,使用的最小支持度为3,因此q和p并没有出现在最后的树中。


FP-growth算法的工作流程如下。首先构建FP树,然后利用它来挖掘频繁项集。为构建FP树,需要对原始数据集扫描两遍。第一遍对所有元素项的出现次数进行计数。记住Apriori原理,即如果某元素是不频繁的,那么包含该元素的超集也是不频繁的,所以就不需要考虑这些超集。数据库的第一遍扫描用来统计出现的频率,而第二遍扫描中只考虑那些频繁元素。


FP-growth的一般流程


(1)收集数据:使用任意方法。

(2)准备数据:由于存储的是集合,所以需要离散数据。如果要处理连续数据,需要将它们量化为离散值。

(3)分析数据:使用任意方法。

(4)训练算法:构建一个FP树,并对树进行挖据。

(5)测试算法:没有测试过程。

(6)使用算法:可用于识别经常出现的元素项,从而用于制定决策、推荐元素或进行预测等应用中。


责任编辑:admin


微信公众号

我来说两句
评分: 1分 2分 3分 4分 5分
评论内容:
验证码:
【网友评论仅供其表达个人看法,并不表明本站同意其观点或证实其描述。】
评论列表
已有 0 条评论(查看更多评论)