挖掘频繁模式.ppt

关联规则挖掘 基本概念和路线图 频繁模式：频繁地出现在数据集中的模式称作频繁模式。如项集、子序列、子结构都是模式。 频繁项集挖掘导致发现大型事务或关系数据集中项之间有趣的关联或相关。即频繁项集的挖掘是关联规则的挖掘。 1.购物篮分析： “尿布与啤酒”——典型关联分析案例 在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%～40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。 购物篮分析 如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示（0001001100）；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示 关联规则的两个兴趣度度量 支持度 置信度 关联规则：基本概念 给定： 项的集合：I={I1,I2,...,In} 任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得 每个事务由事务标识符TID标识； A,B为两个项集，事务T包含A当且仅当 则关联规则是如下蕴涵式： 其中 并且 ，规则 在事务集D中成立，并且具有支持度s和置信度c 规则度量：支持度和置信度 各种项集 项集：项的集合。 k－项集：包含k个项的集合 {牛奶，面包，黄油}是个3－项集 项集的频率是指包含项集的事务数 如果项集的频率大于最小支持度阈值，则称该项集为频繁项集 频繁k项集的集合通常记作Lk 关联规则挖掘包含两个过程： 找出所有频繁项集 大部分的计算都集中在这一步 由频繁项集产生强关联规则 即满足最小支持度和最小置信度的规则 如果不存在真超项集Y使得Y与X在S中有相同的支持度计数，则称 项集X在数据集S中是闭的。 如果X在S中是闭的和频繁的，则称项集X是数据集S中的闭频繁项 集。 如果X是频繁的，并且不存在超项集Y使得X Y并且Y在S中是频繁的，则称X是S中的极大频繁项集（或极大项集）。 举例： 关联规则挖掘——路线图 关联规则有多种分类：关联规则挖掘.ppt 根据规则中所处理的值类型 布尔关联规则 量化关联规则 根据规则中设计的数据维 单维关联规则 多维关联规则 根据规则集所涉及的抽象层 单层关联规则 多层关联规则 根据关联挖掘的各种扩充 挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的） 挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c`，使得每个包含c的事务也包含c`） 频繁项集挖掘方法 最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。 对于规则A ? C，其支持度 =50% 置信度 Apriori算法 Apriori算法利用频繁项集性质的先验知识（prioriknowledge），通过逐层有哪些信誉好的足球投注网站的迭代方法，即将k-1项集用于探察k项集，来穷尽数据集中的所有频繁项集。 先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。 Apriori性质：频繁项集的所有非空子集也必须是频繁的。（ 模式不可能比A更频繁的出现） Apriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。 Apriori算法——示例 由频繁项集产生关联规则 同时满足最小支持度和最小置信度的才是强关联规则,从 频繁项集产生的规则都满足支持度要求，而其置信度则 可由以下公式计算： 每个关联规则可由如下过程产生： 对于每个频繁项集l，产生l的所有非空子集； 对于l的每个非空子集s，如果 则输出规则“ ”(P155)例.doc 挖掘闭频繁项集 剪枝策略 1.项合并 如果包含频繁项集X的每个事务都包含项集Y,但不包含Y的任何 真超集，则X∪Y形成一个闭频繁项集，并且不必再有哪些信誉好的足球投注网站包含X 但不包含Y的任何项集。 例： 2.子项集剪枝 如果频繁项集X是一个已经发现的闭频繁项集Y的真子集，并且 support_count(X)=support_count(Y),则X和X在集合枚举树中的所有后代都不可能是闭频繁项集。可以剪枝。 例： 3.项跳过 在深度优先挖掘闭项集时，每一层都有一个与头表和投影数据库相关联的前缀项集X。如果一个局部频繁项p在不同层的