网站 图片延时加载,wordpress主题免费和付费,公路水运建设质量安全监督网站,购物网站策划方案! #x1f935;♂️ 个人主页: AI_magician #x1f4e1;主页地址#xff1a; 作者简介#xff1a;CSDN内容合伙人#xff0c;全栈领域优质创作者。 #x1f468;#x1f4bb;景愿#xff1a;旨在于能和更多的热爱计算机的伙伴一起成长#xff01;#xff01;♂️ 个人主页: AI_magician 主页地址 作者简介CSDN内容合伙人全栈领域优质创作者。 景愿旨在于能和更多的热爱计算机的伙伴一起成长 ♂️声明本人目前大学就读于大二研究兴趣方向人工智能硬件虽然硬件还没开始玩但一直很感兴趣希望大佬带带 【深度学习 | 核心概念】那些深度学习路上必经的核心概念确定不来看看 一 作者 计算机魔术师 版本 1.0 2023.8.27 摘要 本系列旨在普及那些深度学习路上必经的核心概念文章内容都是博主用心学习收集所写欢迎大家三联支持本系列会一直更新核心概念系列会一直更新欢迎大家订阅 该文章收录专栏 [✨— 《深入解析机器学习从原理到应用的全面指南》 —✨] toc
FP-Growth算法
Apriori算法需要多次扫描数据I/O是很大的瓶颈。为了解决这个问题FP-GrowthFrequent Pattern Growth通过构建FP树Frequent Pattern Tree来避免生成候选项集从而减少了搜索空间提高了算法的效率。无论多少数据只需要扫描两次数据集因此提高了算法运行的效率。
FP Tree算法引入了一些数据结构来临时存储数据。这个数据结构包括三部分如下图所示 1. 项头表线性结构里面记录了所有的1项频繁集出现的次数按照次数降序排列。比如上图中B在所有10组数据中出现了8次因此排在第一位。
FP Tree树结构它将我们的原始数据集映射到了内存中的一颗FP树。节点链表所有项头表里的1项频繁集都是一个节点链表的头它依次指向FP树中该1项频繁集出现的位置。这样做主要是方便项头表和FP Tree之间的联系以查找和更新。
算法步骤 构建项头表Header Table遍历数据集统计每个项的支持度删除支持度低于阈值的项最后按照支持度降序排序。构建一个项头表每个项头表项包含项的名称、支持度计数和指向该项在FP树中第一个节点的指针。在实际操作中需要扫描两次数据第一次用于统计项支持度操作第二次扫描用于删除支持度低于阈值中事务的项。其中之所排序是因为在FP树的建立时可以尽可能的共用祖先节点 构建FP树遍历数据集读取每一条事务依次构建FP树。对于每个事务中的项从根节点开始如果该项在当前节点的子节点中存在则增加子节点的支持度计数否则创建一个新的子节点并更新项头表中该项的链表。最后构建得到的树称为FP树。 构建条件模式基对于每个项头表中的项从项头表链表的末尾开始递归遍历该项的链表生成以该项为后缀路径的条件模式基。每个条件模式基包含路径中除了当前项的其他项以及对应的支持度计数。 D的条件模式基如下图。将所有的祖先节点计数设置为叶子节点的计数即变成{A:2, C:2,E:1 G:1,D:1, D:1}此时E节点和G节点由于在条件模式基里面的支持度低于阈值被我们删除最终在去除低支持度节点并不包括叶子节点后D的条件模式基为{A:2, C:2}。 递归挖掘FP树对于每个项头表中的项将它与条件模式基组合形成新的频繁项集。如果条件模式基非空则以条件模式基为输入递归调用FP树构建和挖掘过程。 在上一步得到条件模式基后结合得到 D的频繁2项集为{A:2,D:2}, {C:2,D:2}。递归合并二项集得到频繁三项集为{A:2,C:2,D:2}。D对应的最大的频繁项集为频繁3项集。
FP Tree算法改进了Apriori算法的I/O瓶颈巧妙的利用了树结构参考BIRCH聚类BIRCH聚类也是巧妙的利用了树结构来提高算法运行速度。利用内存数据结构以空间换时间是常用的提高算法运行时间瓶颈的办法。
在实践中FP Tree算法是可以用于生产环境的关联算法而Apriori算法则做为先驱起着关联算法指明灯的作用。除了FP Tree像GSPCBA之类的算法都是Apriori派系的。
经典案例和代码实现
以下是一个使用Python的mlxtend库实现FP-Growth算法的示例代码
from mlxtend.frequent_patterns import fpgrowth
from mlxtend.preprocessing import TransactionEncoder
import pandas as pd# 创建示例数据集
dataset [[Milk, Eggs, Bread],[Milk, Butter],[Cheese, Bread, Butter],[Milk, Eggs, Bread, Butter],[Cheese, Bread, Butter]]# 使用TransactionEncoder将数据集转换为布尔矩阵
te TransactionEncoder()
te_ary te.fit(dataset).transform(dataset)
df pd.DataFrame(te_ary, columnste.columns_)# 使用fpgrowth函数查找频繁项集
frequent_itemsets fpgrowth(df, min_support0.2, use_colnamesTrue)print(frequent_itemsets)这里使用了mlxtend库中的fpgrowth函数来执行FP-Growth算法。首先将事务数据集转换为布尔矩阵表示然后调用fpgrowth函数来寻找指定最小支持度阈值的频繁项集。
另外如果你想使用自己实现的FP-Growth算法可以参考相关的开源实现和算法细节。以下是一些学习资源可以帮助你更深入地了解FP-Growth算法
Han, J., Pei, J., Yin, Y. (2000). Mining frequent patterns without candidate generation. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data (pp. 1-12).Agrawal, R., Imieliński, T., Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD Record, 22(2), 207-216.mlxtend documentation: https://rasbt.github.io/mlxtend/Python implementation of FP-Growth algorithm: https://github.com/evandempsey/fp-growth
参考文章
https://www.cnblogs.com/pinard/p/6307064.html 到这里如果还有什么疑问欢迎私信博主问题哦博主会尽自己能力为你解答疑惑的如果对你有帮助你的赞是对博主最大的支持
