数据挖掘第3章 关联规则挖掘.ppt

数据挖掘与模式识别Data Mining and Pattern Recognition ;三、关联规则挖掘 Association Rules Mining;OUTLINE;OUTLINE;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;购物篮关联分析实例图;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;什么是频繁模式分析?;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;例题1 对下表所示的交易数据库记录，请给出项集和其中的事务。;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;例题2 针对例题1中的交易数据库记录，;例题3;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;关联规则的基本概念与基础理论;典型算法 AIS 算法（R. Agrawal等提出） Apriori算法（及变种AprioriTid和AprioriHybrid)） SETM 算法（M. Houtsma等提出） DHP 算法（J. Park等提出） PARTITION 算法（A.Savasere等提出） Sampling 算法（H.Toivonen提出） FP-growth 算法（Jiawei Han提出）;Apriori算法原理;Apriori算法原理;Apriori算法原理;Apriori算法的主要步骤;Apriori算法原理;Apriori算法原理;发现频繁项集;发现频繁项集;发现频繁项集;(2) FOR k=1, 2, 3, …. (3) 连接：将Lk进行自身连接生成一个候选频繁k+1项集的集合Ck+1，其连接方法如下：对任意p，q?Lk，若按字典序有 p={p1, p2,…, pk-1, pk }，q={p1, p2,…, pk-1, qk}且满足pkqk，则把p, q连接成k+1项集，即将p?q={p1, p2,…, pk-1, pk, qk}作为候选(k+1)-项集Ck+1中的元素。 (4) 剪枝：删除Ck+1中明显的非频繁(k+1)-项集，即当Ck+1中一个候选(k+1)-项集的某个k-项子集不是Lk中的元素时，则将它从Ck+1中删除。 (5) 计算支持数：通过扫描事务数据库T，计算Ck+1中各个元素的支持数。 (6) 求Lk+1：剔除Ck+1中低于最小支持数MinSptN的元素，即得到所有频繁(k+1)-项集构成的集合Lk+1。 (7) 若Lk+1=????则转第(9)步 (8) END FOR (9) 令L= L1? L2?L3?… ?Lk ，并输出L。;发现频繁项集;产生关联规则;产生关联规则;产生关联规则;产生关联规则;产生关联规则;The Apriori Algorithm—An Example;Apriori算法实例分析;Apriori算法实例分析;解： 1、找出所有的频繁项目集 因支持度min_sup=0.4，事务数据库有5条记录，即最小支持数MinSptN=2。 (1) 求L1：扫描事务数据库，可得候选频繁1-项集及其支持数计算结果。;(2) 第一轮循环：对L1执行算法的(3)至(6)步。 (3) 连接：由L1自身连接生成候选频繁2-项集的集合C2，其结果由下表左侧第1列给出，且已按字典序排序。 {a}与{b}, {c}, {d} , {e}分别连接生成{a,b}, {a,c}, {a,d}和{a,e}。 {b}与 {c}, {d}, {e}分别连接生成{b,c}, {b,d}, {b,d}。 ……;(4) 剪枝：由于I中所有1-项集都是频繁的，因此C2无 需进行剪枝过程。 (5)计算支持数：扫描数据库，计算其支持数。 (6) 求L2：删除支持数小于2的候选2-项集，最终得到所有的频繁2-项集。 (7) L2??;(2)第二轮循环：对L2执行算法的(3)至(6)步获得L3。 SptN({d,e})=1, {b, d, e}、 {c, d, e}被剪枝;(2) 第三轮循环：对L3执行算法的(3)至(6)步获得L4。 (2) 第四轮循环：由于L4仅有一个频繁4-项集，故已不能生成候选频繁5-项集C5，因此(7)L5=?，转算法(9)步。 (9) 输出 L= L1? L2? L3? L4 = {{a}, {b}, {c}, {d}, {e}} ?{{a, b}, {a, c}, {a, d},