关联规则挖掘算法

关联规则挖掘算法FP-growth2024/5/41关联规则的基本概念数据挖掘是指从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的但又是潜在有用的信息和知识的过程数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联关联分析的目的是找出数据库中隐藏的关联网。2024/5/42关联规则的基本概念支持度：P(AUB)，即A和B这两个项集在事务集D中同时出现的概率置信度：P(B I A)，即在出现项集A的事务集D中，项集B也同时出现的概率2024/5/43关联规则的基本概念bread=milk支持度-7,置信度-65P(breadUmilk)=7P(milkIbread)=65如果一条关联规则同时满足最小支持度阈值和最小置信度阈值，那么就认为它是有趣的，并称为强关联规则。给定一个事务集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。2024/5/44FP-tree构造算法扫描事务数据库一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序，结果为频繁项表L。创建FP-tree的根结点(null)。对于D中每个事务：选择事务中的频繁项，并按L中的次序排序。设排序后的频繁项表为p|P，其中p是第一个元素，而P是剩余元素的表调用insert_tree(p|P，T)。如果T有子女N使得N.item-name=p.item-name，则N的计数增加1；否则创建一个新节点N，将其计数设置为1，连接到他的父节点T，并通过节点链结构将其连接到具有相同item-name的节点如果P非空，递归的调用insert_tree(P，N)2024/5/45FP-growth算法1.Procedure FP-growth(Tree，a)2.if Tree包含单个路径 p then3.for路径P中每个节点组合(记做)4.产生模式a，其支持度support=中节点的最小 支持度;5.else for each ai在tree的头部6.产生一个模式=aia，其支持度support=ai.support;7.构造的条件模式基，构建的条件FP-tree Tree;8.if Tree then9.调用FP-growth(Tree，);10.2024/5/46事务数据库TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I32024/5/47第一步、构造FP-tree扫描事务数据库得到频繁1-项目集F定义minsup=20%，即最小支持度为2重新排列FI1I2I3I4I567622I2I1I3I4I5766222024/5/48重新调整事务数据库TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I32024/5/49创建根结点和频繁项目表Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNull2024/5/410加入第一个事务(I2,I1,I5)Item-nameNode-headI2I1I3NullI4NullI5NullI2:1I1:1I5:12024/5/411加入第二个事务(I2,I4)Item-nameNode-headI2I1I3NullI4I5NullI2:2I1:1I5:1I4:12024/5/412加入第三个事务(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:3I1:1I5:1I4:1I3:12024/5/413加入第四个事务(I2,I1,I4)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:12024/5/414加入第五个事务(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:1I1:1I3:12024/5/415加入第六个事务(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:1I3:12024/5/416加入第七个事务(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:2I3:22024/5/417加入第八个事务(I2,I1,I3,I5)Item-nameNode-headI2I1I3I4I5NullI2:6I1:3I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:12024/5/418加入第九个事务(I2,I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:7I1:4I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:22024/5/419第二步、FP-growth首先考虑I5，得到条件模式基、构造条件FP-tree得到I5频繁项集：I2,I5:2,I1,I5:2,I2,I1,I5:2Item-nameNode-headI2I1NullI2:2I1:2I3:12024/5/420第二步、FP-growth接着考虑I4，得到条件模式基、构造条件FP-tree得到I4频繁项集：I2,I4:2Item-nameNode-headI2NullI2:2I1:12024/5/421第二步、FP-growth然后考虑I3，得到条件模式基、构造条件FP-tree由于此树不是单一路径，因此需要递归挖掘I3Item-nameNode-headI2I1NullI2:4I1:2I1:22024/5/422第二步、FP-growth递归考虑I3，此时得到I1条件模式基,即I1I3的条件模式基为构造条件FP-tree得到I3的频繁项目集I2,I3:4,I1,I3:4,I2,I1,I3:2Item-nameNode-headI2NullI2:22024/5/423第二步、FP-growth最后考虑I1，得到条件模式基构造条件FP-tree得到I1的频繁项目集I2,I1:4Item-nameNode-headI2NullI2:42024/5/424Thank you!2024/5/425