《《数据仓库与数据挖掘》课件 4 关联规则挖掘理论和算法》由会员分享，可在线阅读，更多相关《《数据仓库与数据挖掘》课件 4 关联规则挖掘理论和算法（69页珍藏版）》请在金锄头文库上搜索。
1、n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题nApriori的改进算法n对项目集格空间理论的发展n基于项目序列集操作的关联规则挖掘算法n改善关联规则挖掘质量问题n约束数据挖掘问题n关联规则挖掘中的一些更深入的问题n数量关联规则挖掘方法第4章 关联规则挖掘理论和算法内容提要 关联规则挖掘是数据挖掘研究的基 础n关联规则挖掘（Association Rule Mining）是数据挖掘中研究较早而且至今仍活跃的研究方法之一。n最早是由Agrawal等人提出的（1993）。最初提出的动机是针对购物篮分析（Basket Analysis）问题提出的，其目的是为
2、了发现交易数据库（Transaction Database）中不同商品之间的联系规则。n关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理论、算法设计、算法的性能以及应用推广、并行关联规则挖掘以及数量关联规则挖掘等。n关联规则挖掘是数据挖掘的其他研究分支的基础。 事务数据库 n设I= i1，i2，im 是一个项目集合，事务数 据库D= t1，t2，tn 是由一系列具有唯一标识 TID的事务组成，每个事务ti（i=1，2，n）都对 应I上的一个子集。n一个事务数据库可以用来刻画：n购物记录： I是全部物品集合， D是购物 清单，每个元组ti是一次购买物品的集合（它当然 是I的一个子集）。n其它应
3、用问题支持度与频繁项目集 n定义（项目集的支持度）. 给定一个全局项目集I 和事务数据库D，一个项目集I1I在D上的支持度（ Support）是包含I1的事务在D中所占的百分比：support（ I1 ）=| t D | I1 t| / | D|。n定义（频繁项目集）.给定全局项目集I和事务数 据库D ，D中所有满足用户指定的最小支持度（ Minsupport）的项目集，即大于或等于minsupport的 I的非空子集，称为频繁项目集（频集：Frequent Itemsets）。在频繁项目集中挑选出所有不被其他元 素包含的频繁项目集称为最大频繁项目集（最大频集 ： Maximum Freque
4、nt Itemsets）。可信度与关联规则n定义（关联规则与可信度）.给定一个全局项目 集I和事务数据库D，一个定义在I和D上的关联规则形 如I1I2，并且它的可信度或信任度或置信度（ Confidence）是指包含I1和I2的事务数与包含I1的事务 数之比，即： Confidence（I1I2）= P（ I1 | I2 ） Confidence（I1I2）= support（I1I2）/ support（I1 ），其中I1，I2I，I1I2=。 定义（强关联规则）. D在I上满足最小支持度和 最小信任度（Minconfidence）的关联规则称为强关 联规则（Strong Associati
5、on Rule）。关联规则挖掘基本过程n关联规则挖掘问题可以划分成两个子问题：n1. 发现频繁项目集:通过用户给定 Minsupport ，寻找所有频繁项目集或者最大频繁 项目集。n2生成关联规则:通过用户给定 Minconfidence ，在频繁项目集中，寻找关联规则 。n第1个子问题是近年来关联规则挖掘算法研究的 重点。n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题nApriori的改进算法n对项目集格空间理论的发展n基于项目序列集操作的关联规则挖掘算法n改善关联规则挖掘质量问题n约束数据挖掘问题n关联规则挖掘中的一些更深入的问题n数量关联规则挖掘
6、方法第5章 关联规则挖掘理论和算法内容提要 项目集格空间理论 定理1（ Appriori 属性1）. 如果项目集X 是频繁项目集 ，那么它的所有非空子集都是频繁项目集。 证明 设X是一个项目集，事务数据库T 中支持X 的元组数为s。对 X的任一非空子集为Y，设T中支持Y的元组数为s1。 根据项目集支持数的定义，很容易知道支持X 的元组一定支持Y， 所以s1 s，即support（Y） support（X）。 按假设：项目集X 是频繁项目集，即support(X) minsupport， 所以support（Y） support（X） minsupport，因此Y是频繁 项目集。n定理2（ Ap
7、priori 属性2）.如果项目集X 是非频繁项目 集，那么它的所有超集都是非频繁项目集。证明 （略）经典的发现频繁项目集算法n1994年，Agrawal 等人提出了著名的Apriori 算 法。n算法1 Apriori（发现频繁项目集）（1） L1 = large 1-itemsets; /所有1-项目频集 （2） FOR （k=2; Lk-1; k+） DO BEGIN （3） Ck=apriori-gen（Lk-1）; / Ck是k-候选集 （4） FOR all transactions tD DO BEGIN （5） Ct=subset（Ck，t）; / Ct是所有t包含的候选集元素
8、 （6） FOR all candidates c Ct DO （7） c.count+; （8） END （9） Lk=cCk |c.countminsup_count （10） END （11） L= Lk; apriori-gen过程n算法apriori中调用了apriori-gen（Lk-1），是为了 通过（k-1）-频集产生K-侯选集。nhas_infrequent_subset（c， Lk-1） ，判断c是否加入到k-侯选集中。（1） FOR all itemset p Lk-1 DO （2） FOR all itemset qLk-1 DO （3） IF p.item1=q.it
9、em1， ， p.itemk-2=q.itemk-2， p.itemk-1 1） THEN /generate rules with subsets of xm-1 as antecedents （7） genrules（lk， xm-1）; （8） END （9）END； Rule-generate算法例子nMinconfidence=80%序号lkxm-1confidencesupport规则（是否是强规则）123523100%50%235（是）2235267%50%235（否）3235367%50%325（否）42352567%50%253（否）5235567%50%523（否） 623
10、535100%50%352（是）n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题nApriori的改进算法n对项目集格空间理论的发展n基于项目序列集操作的关联规则挖掘算法n改善关联规则挖掘质量问题n约束数据挖掘问题n关联规则挖掘中的一些更深入的问题n数量关联规则挖掘方法第5章 关联规则挖掘理论和算法内容提要 Apriori算法的性能瓶颈 nApriori作为经典的频繁项目集生成算法，在数据挖掘 中具有里程碑的作用。nApriori算法有两个致命的性能瓶颈: 1多次扫描事务数据库，需要很大的I/O负 载对每次k循环，侯选集Ck中的每个元素都必须通过扫 描数
11、据库一次来验证其是否加入Lk。假如有一个频繁大项目集包 含10个项的话，那么就至少需要扫描事务数据库10遍。 2可能产生庞大的侯选集由Lk-1产生k-侯选集Ck是指数增长的，例如104个1-频繁 项目集就有可能产生接近107个元素的2-侯选集。如此大的侯选集 对时间和主存空间都是一种挑战。n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题nApriori的改进算法n对项目集格空间理论的发展n基于项目序列集操作的关联规则挖掘算法n改善关联规则挖掘质量问题n约束数据挖掘问题n关联规则挖掘中的一些更深入的问题n数量关联规则挖掘方法第5章 关联规则挖掘理论和算法内
12、容提要 提高Apriori算法效率的技术n一些算法虽然仍然遵循Apriori 属性，但是由于引入了相 关技术，在一定程度上改善了Apriori算法适应性和效率。n主要的改进方法有：n基于数据分割（Partition）的方法：基本原理是“在 一个划分中的支持度小于最小支持度的k-项集不可能是全 局频繁的”。n基于散列（Hash）的方法：基本原理是“在一个 hash桶内支持度小于最小支持度的k-项集不可能是全局频 繁的”。n基于采样的方法：基本原理是“通过采样技术，评 估被采样的子集中，并依次来估计k-项集的全局频度”。n其他：如，动态删除没有用的事务：“不包含任何Lk的事务对未来的扫描结果不会产
13、生影响，因而可以删除”。基于数据分割的方法n定理3-5 设数据集D被分割成分块D1， D2， ， Dn ，全局最小支持数为minsup_count。如果一个数据分块Di 的局部最小支持数minsup_counti （i=1，2，n），按 着如下方法生成：minsup_counti= minsup_count *|Di| /|D| 则所有的局部频繁项目集涵盖全局频繁项目集。n作用：n1合理利用主存空间：数据分割将大数据集 分成小的块，为块内数据一次性导入主存提供机会。n2支持并行挖掘算法：每个分块的局部频繁 项目集是独立生成的，因此提供了开发并行数据挖掘 算法的良好机制。基于散列的方法n1995
14、，Park等发现寻找频繁项目集的主要计算 是在生成2-频繁项目集上。因此，Park等利用了这个 性质引入杂凑技术来改进产生2-频繁项目集的方法。n 例子：桶地址 =（10x+y）mod 7； minsupport_count=3 TID Items 1 I1，I2，I5 2 I2，I4 3 I2，I3 4 I1，I2，I4 5 I1，I3 6 I2，I3 7 I1，I3 8 I1，I2，I3，I5 9 I1，I2，I3桶地址 0 1 2 3 4 5 6 桶计数 2 2 4 2 2 4 4 桶内 I1，I4 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3I3，I5 I1，
15、I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3I2，I3 I1，I2 I1，I3I2，I3 I1，I2 I1，I3L2=I2，I3 ， I1，I2 ， I1，I3 n基本概念与解决方法 n经典的频繁项目集生成算法分析 nApriori算法的性能瓶颈问题nApriori的改进算法n对项目集格空间理论的发展n基于项目序列集操作的关联规则挖掘算法n改善关联规则挖掘质量问题n约束数据挖掘问题n关联规则挖掘中的一些更深入的问题n数量关联规则挖掘方法第5章 关联规则挖掘理论和算法内容提要 探索新的理论n随着数据库容量的增大，重复访问 数据库（外存）将导致性能低下。因此 ，探索新的理论和算法来减少数据库的
