第5章数据挖掘-1案例.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 即，Lk-1的元素l1和l2是可连接的，若： （ l1[1] = l2[1] ∧ l1 [2] = l2 [2] ∧ … ∧ l1[k-2] = l2[k-2] ∧ l1[k-1] l2[k-1] ） 而条件（l1[k-1] l2[k-1]）可确保不产生 重复的项集。 31 (2)剪枝步 Ck是Lk的超集，即它的成员不一定 都是频繁项集，但所有的频繁k-项集都 包含在Ck中。 扫描数据库，确定Ck中每个候选项 集的计数，从而确定Lk。然而， Ck可能 很大，这样所涉及的计算量就很大。 32 为了压缩Ck，可利用Apriori性质： 任何非频繁的(k-1)-项集都不可能是频繁 k-项集的子集。因此，若一个候选k-项 集的(k-1)-项子集不在Lk-1中，则该候选 也不可能是频繁的，从而可以从Ck中删除。 33 34 TID 项ID的列表 【例3 】一个Apriori的具体例子，该例基于右图某商店的事务DB。DB中有9个事务，Apriori假定事务中的项按字典次序存放。 T100 T200 T300 T400 T500 T600 T700 T800 T900 I1，I2，I5 I2，I4 I2，I3 I1，I2，I4 I1，I3 I2，I3 I1，I3 I1，I2，I3，I5 I1，I2，I3 （1）在算法的第一次迭代，每个项都是 候选1-项集的集合C1的成员。算法简单 地扫描所有的事务，对每个项的出现次 数计数。 C1 项集 支持度计数 扫描D,对每 个候选计数 {I1} {I2} {I3} {I4} {I5} 6 7 6 2 2 35 （2）设最小支持计数为2，可以确定频繁 1-项集的集合L1 。它由具有最小支持 度的候选1-项集组成。 L1 项集 支持度计数 比较候选支持度计数 与最小支持度计数 {I1} {I2} {I3} {I4} {I5} 6 7 6 2 2 36 （3）为发现频繁2-项集的集合L2 ，算法 使用 L1 L1 产生候选2-项集集合C2 。 由L1产生候选C2 C2 项集 {I1，I2} {I1，I3} {I1，I4} {I1，I5} {I2，I3} {I2，I4} {I2，I5} {I3，I4} {I3，I5} {I4，I5} 37 4 2 （4）扫描D中事务，计算C2中每个候选项 集的支持计数。 C2 项集 {I1，I2} {I1，I3} {I1，I4} {I1，I5} 支持度计数 4 4 1 2 扫描D,对每 个候选计数 {I2，I3} {I2，I4} {I2，I5} {I3，I4} {I3，I5} 2 0 1 {I4，I5} 0 38 4 2 （5）确定频繁2-项集的集合L2 ，它由具 有最小支持度的C2中的候选2-项集组成。 L2 项集 {I1，I2} 支持度计数 4 比较候选支持度计数 与最小支持度计数 {I1，I3} {I1，I5} {I2，I3} {I2，I4} {I2，I5} 4 2 2 39 （6）候选3-项集的集合C3 的产生如下： ① 连接： C3 = L2 ∞ L2 = {{I1,I2}，{I1,I3}， {I1,I5}，{I2,I3}，{I2,I4}，{I2,I5}} ∞ {{I1,I2}， {I1,I3}，{I1,I5}，{I2,I3}，{I2,I4}，I2,I5}} = {{I1,I2,I3}，{I1,I2,I5}，{I1,I3,I5}，{I2,I3,I4}， {I2,I3,I5}，{I2,I4,I5}} 40 ② 利用Apriori性质剪枝：频繁项集的所 有子集必须是频繁的。存在候选项集， 判断其子集是否频繁。 {I1,I2,I3}的2-项子集是{I1,I2}，{I1,I3}和{I2,I3}, 它们都是L2的元素。因此保留{I1,I2,I3}在C3中。 {I1,I2,I5}的2-项子集是{I1,I2}，{I1,I5}和{I2,I5}, 它们都是L2的元素。因此保留{I1,I2,I5}在C3中。 {I1,I3,I5}的2-项子集是{I1,I3}，{I1,I5}和{I3,I5}, {I3,I5}不是L2的元素，因而不是频繁的，由C3中 删除{I1,I3,I5}。 41 42 {I2,I3,I4}的2-项子集是{I2,I3}，{I2,I4}和{I3,I4}, 其中{I3,I4}不是L2的元素，因而不是频繁的