资源描述：
《关联规则挖掘算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、关联规则挖掘算法FP-growth2021/8/41关联规则的基本概念数据挖掘是指从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的但又是潜在有用的信息和知识的过程．数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联．关联分析的目的是找出数据库中隐藏的关联网。2021/8/42关联规则的基本概念支持度：P(AUB)，即A和B这两个项集在事务集D中同时出现的概率．置信度：P(BIA)，即在出现项集A的事务集D中，项集B也同时出现的概率．2021/8/43关联规则的基本概念bread=>milk[支持度--7％
2、,置信度--65％]P(breadUmilk)=7％P(milkIbread)=65％如果一条关联规则同时满足最小支持度阈值和最小置信度阈值，那么就认为它是有趣的，并称为强关联规则。给定一个事务集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。2021/8/44FP-tree构造算法扫描事务数据库一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序，结果为频繁项表L。创建FP-tree的根结点(null)。对于D中每个事务：选择事务中的频繁项，并按L中的次序排序。设排序后的频繁项表为[p
3、P]，其中p是第一个元素，而
4、P是剩余元素的表．调用insert_tree([p
5、P]，T)。如果T有子女N使得N.item-name=p.item-name，则N的计数增加1；否则创建一个新节点N，将其计数设置为1，连接到他的父节点T，并通过节点链结构将其连接到具有相同item-name的节点．如果P非空，递归的调用insert_tree(P，N)．2021/8/45FP-growth算法ProcedureFP-growth(Tree，a)ifTree包含单个路径pthenfor路径P中每个节点组合(记做β)产生模式β∪a，其支持度support=β中节点的最小支持度;elseforeachai在tree的头部{产生一个
6、模式β=ai∪a，其支持度support=ai.support;构造β的条件模式基，构建β的条件FP-treeTreeβ;ifTreeβ≠Φthen调用FP-growth(Treeβ，β);}2021/8/46事务数据库TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I32021/8/47第一步、构造FP-tree扫描事务数据库得到频繁1-项目集F定义minsup=20%，即最小支持度为2重新排列FI1I2I3I4I567622I2I1I3I4I5766222021/8/48重新调整事务数据库
7、TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I32021/8/49创建根结点和频繁项目表Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNull2021/8/410加入第一个事务(I2,I1,I5)Item-nameNode-headI2I1I3NullI4NullI5NullI2:1I1:1I5:12021/8/411加入第二个事务(I2,I4)Item-nameNode-headI2I1I3NullI4I5NullI2:2I1:1I5:1
8、I4:12021/8/412加入第三个事务(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:3I1:1I5:1I4:1I3:12021/8/413加入第四个事务(I2,I1,I4)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:12021/8/414加入第五个事务(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:1I1:1I3:12021/8/415加入第六个事务(I2,I3)Item-nameNode-headI2I1I3I
9、4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:1I3:12021/8/416加入第七个事务(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:2I3:22021/8/417加入第八个事务(I2,I1,I3,I5)Item-nameNode-headI2I1I3I4I5NullI2:6I1:3I5:
