关联规则挖掘与序列模式挖掘

1、关联规则挖掘与序列模式挖掘,从推荐系统(recommender system)说起,频繁项集,关联规则,关联规则挖掘的兴起,1993年，Agrawal提出了关联规则(Association Rule)问题，旨在发现顾客购货篮内商品间令人感兴趣的关系。 “啤酒和尿布” 沃尔玛利用NCR数据挖掘工具意外的发现：跟尿布一起购买最多的商品竟是啤酒！ 今天，关联规则已广泛应用于金融、营销以及生物信息学等领域。,主要内容,关联规则的基本概念 Apriori算法 改进的Apriori算法（AprioriTid、AprioriHybrid） FP-Tree算法 基于多最小支持度的关联规则挖掘（ MSaprio

2、ri 算法） 多层、多维、约束性关联规则挖掘问题 关联规则的评价问题,关联规则挖掘的动机,发现数据内在的关系 哪些商品往往被一起购买啤酒尿布 买了PC机之后，还会购买哪些商品 哪些DNA对新药较为敏感,什么是关联规则,关联规则是寻找给定的数据集中项目之间令人感兴趣的关系,购物栏数据库,例子,Diaper Beer,Milk, Bread Eggs,Coke,Beer, Bread Milk,蕴含并不是因果关系,频繁项集,项集 一个或多个项目的集合。 例如: Milk, Bread, Diaper 包含k 个项目的项集称为k-项集 绝对支持度 () 某一项集出现的次数 比如 (Milk, Bre

3、ad,Diaper) = 2 相对支持度 包含某一项集的事务在全体事务中的比例。比如. s(Milk, Bread, Diaper) = 2/5 频繁项集 支持度不小于给定最小支持度阈值(minsup)的项集,关联规则,关联规则 形如 X Y的蕴涵式, 其中 X 和Y是项集，且XY=。 比如: Milk, Diaper Beer 规则评价参数 支持度 (s) 同时包含X和Y的事务占全部事务的百分比 可信度 (c) 包含项集X的事务中也包含Y的百分比,Example:,关联规则挖掘的一般流程,找出满足最小支持度阈值的所有频繁项集。 由频繁项集产生满足最小可信度阈值的强关联规则。 这两步中，第二步

4、较容易。关联规则挖掘的总体性能由第一步决定。,频繁项集的生成-1,给定d 个项目,可以生成 2d 候选项集,频繁项集的生成-2,频繁项集格中每个项集都作为候选频繁项集 扫描数据库，计算每个候选集的支持度 复杂度 O(NMw) = Expensive since M = 2d !,计算复杂度,假设存在 d 个不同的项目: 项集总数= 2d 规则总数:,d=6, R = 602,频繁项集的生成策略,减少候选项集的个数 (M) 利用各种剪枝方法减少M 减少事务的个数 (N) 随着项集维度的增加，不断减少N的数目 减少比较的次数 (NM) 使用新颖的数据结构存储事务/项集 无需在每个事务中匹配每个项集

5、,主要内容,关联规则的基本概念 Apriori算法 改进的Apriori算法（AprioriTid、AprioriHybrid） FP-Tree算法 基于多最小支持度的关联规则挖掘（ MSapriori 算法） 多层、多维、约束性关联规则挖掘问题 关联规则的评价问题,Apriori性质-1,Agrawal R, Srikant R. Fast algorithms for mining association rules. (VLDB94). Apriori 性质: 频繁项集的所有非空子集都必须也是频繁的。 Apriori 性质成立的原因: 项集的支持度不超过其子集的支持度，即支持度的反单调性

6、。,Apriori性质-2,Pruned supersets,Apriori算法-1,扫描数据库，找出1-频繁项集 连接k-频繁项集生成 (k+1)-候选项集 在数据库中验证候选集是否频繁 当没有候选集或频繁项集生成时结束,Apriori算法-2,Pseudo-code: Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = frequent items; for (k = 1; Lk !=; k+) do begin Ck+1 = candidates generated from Lk; for each

7、transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support end return k Lk;,规则生成-1,给定频繁项集L, 找出所有非空的f L使得f L f 满足最小可信度阈值 如 A,B,C,D 为频繁项集, 候选规则有: ABC D, ABD C, ACD B, BCD A, A BCD,B ACD,C ABD, D ABCAB CD,AC BD, AD BC, B

8、C AD, BD AC, CD AB, 若|L| = k, 则存在2k 2个候选关联规则,规则生成-2,可信度一般不满足反单调性 c(ABC D) 可以比 c(AB D)大，也可以比c(AB D)小 定理. 若规则 X Y-X 不满足最小可信度阈值，则规则 X Y-X，X X，也不满足最小可信度阈值。 比如, L = A,B,C,D: c(ABC D) c(AB CD) c(A BCD),规则生成-3：,Apriori算法使用一种逐层方法来产生关联规则，其中每层对应规则后件中的项数。 算法首先提取规则后件只含一个项的所有高置信度规则，然后使用这些规则来产生新的候选规则。 例如使用abcb和ab

9、dc来产生候选规则adbc。,规则生成-4,合并结论中具有共同前缀的规则，生成候选规则 连接(CD=AB,BD=AC)生成候选规则 D = ABC 若AD=BC 的可信度未 超过最小可信度阈值则删去 D=ABC,规则生成-5,Lattice of rules,Low Confidence Rule,小结,Apriori算法是挖掘频繁项集中最具有影响力的算法。算法有两步骤：一是发现所有的频繁项集；二是生成强关联规则。 发现频繁项集是关联规则挖掘中的关键步骤。在Apriori算法中利用“频繁项集的子集是频繁项集，非频繁项集的超集是非频繁项集”这一个性质有效的对频繁项集进行修剪。,小结,算法核心思想

10、：给定一个数据库，第一次扫描数据库，搜索出所有支持度大于等于最小支持度的项集组成频繁1-项集即为L1，由L1连接得到候选1-项集C1；第二次扫描数据库，搜索出C1中所有支持度大于等于最小支持度的项集组成频繁2-项集即为L2 ，由L2连接得到候选2-项集C2；同理第k次扫描数据库，搜索出Ck-1 中所有支持度大于等于最小支持度的项集组成频繁k-项集即为Lk，由Lk连接得到候选k-项集Ck，直到没有新的候选集产生为止。,小结,Apriori算法需扫描数据库的次数等于最大频繁项集的项数。 Apriori算法有两个致命的性能瓶颈： 1.产生的候选集过大(尤其是2-项集)，算法必须耗费大量的时间处理候选

11、项集 2. 多次扫描数据库，需要很大的1/0负载，在时间、空间上都需要付出很大的代价。,频繁模式挖掘的挑战,挑战 多次扫描事务数据库 巨大数量的候选项集 繁重的计算候选项集的支持度工作 改进 Apriori: 大体的思路 减少事务数据库的扫描次数 缩减候选项集的数量 使候选项集的支持度计算更加方便,主要内容,关联规则的基本概念 Apriori算法 改进的Apriori算法（AprioriTid、AprioriHybrid） FP-Tree算法 基于多最小支持度的关联规则挖掘（ MSapriori 算法） 多层、多维、约束性关联规则挖掘问题 关联规则的评价问题,AprioriTid算法,Apri

12、ori vs. AprioriTid-1,缺点：内存要求很大，事务过多的时候资源难以满足。,Apriori vs. AprioriTid-2,最初几遍扫描数据库时，Apriori的性能优于AprioriTid；而从某次扫描数据库开始， AprioriTid 的性能优于Apriori 为什么？,AprioriHybrid算法-1,Agrawal R, Srikant R. Fast algorithms for mining association rules. (VLDB94). 开始使用Apriori算法 当能够调入内存时，开始使用AprioriTid算法,AprioriHybrid算法-2

13、,主要内容,关联规则的基本概念 Apriori算法 改进的Apriori算法（AprioriTid、AprioriHybrid） FP-Tree算法 基于多最小支持度的关联规则挖掘（ MSapriori 算法） 多层、多维、约束性关联规则挖掘问题 关联规则的评价问题,Apriori算法的瓶颈,候选验证的挖掘方式存在以下问题： 多次扫描数据库I/O代价较高 挖掘长的频繁项集将产生大量的候选项集 如挖掘 i1i2i100 扫描数据的次数: 100 候选项集的数量: 能否不产生候选项集？,FP-Growth算法,J. Han, J. Pei, and Y. Yin. Mining frequent

14、patterns without candidate generation. SIGMOD 00. FP-growth算法是深度优先算法中最新最高效的且从本质上不同于Apriori算法的经典算法 将数据库的信息压缩成一个描述频繁项相关信息的频繁模式树 在算法中有两个关键步骤： 一是生成频繁模式树FP-tree； 二是在频繁模式树FP-tree上挖掘频繁项集,2020/7/6,43,利用FP-树进行频繁模式挖掘,思想: 频繁模式增长 递归地增长频繁模式 方法 对每个频繁项,构建它的条件模式基,然后构建它的条件FP-树. 对每个新创建的条件FP-树重复上述过程 直至结果FP-树为空,或者它仅包含一

15、个单一路径.该路径将生成其所有的子路径的组合,每个组合都是一个频繁模式.,FP-Tree(不产生频繁候选集),FP-Tree增长算法的步骤： (1) 建立 FP-tree树 扫描数据库一次，找出频繁1-项集，按递减顺序排序。再一次扫描数据库，建立FP-tree 。 (2) 利用FP-tree挖掘频繁集 对于每一个项，先构造条件模式基，然后构造条件FP-树。 在每一个新创建的条件FP-树上重复此过程。 直到结果FP-树为空，或只包含一条路径 。,COMP537,44,例1,FP-Growth算法步骤,例2,例3,COMP537,59,Step 1: 遍历一次数据库，导出频繁项（1项集）的集合和支

16、持度计数（频率），并且以降序排序。 Step 2: 构造FP-tree Step 3: 根据第二步得到的FP-Tree, 为1项频繁项集中的每一项构造条件FP-Tree. Step 4: 得到频繁模式（频繁项集）.,FP-tree,频繁项集的挖掘（FP树的挖掘）,COMP537,60,问题: 找到所有的满足最小支持度（阈值）的频繁项集（min_Support=3）,COMP537,61,Threshold = 3,4,COMP537,62,Threshold = 3,4,4,COMP537,63,Threshold = 3,4,4,1,3,3,3,3,1,1,1,1,COMP537,64,Th

17、reshold = 3,4,4,1,3,3,3,3,1,1,1,1,a, b, d, e, f, g,a, f, g,b, d, e, f,a, b, d,a, b, e, g,FP-tree,COMP537,65,Step 1: 遍历一次数据库，导出频繁项（1项集）的集合和支持度计数（频率），并且以降序排序，结果集或表记为L。 Step 2: 构造FP-tree Step 3: 根据第二步得到的FP-Tree, 为1项频繁项集中的每一项构造条件FP-Tree. Step 4: 得到频繁模式（频繁项集）.,FP-Tree,FP-Tree构造如下： 首先，创建树的根节点，用“null”标记。 其

18、次，第二次扫描数据库D.每个数据库的项都按照L中的次序处理（即按照递减的支持度技术排序），并对每个事务数据创建一个分支。,COMP537,66,COMP537,67,Threshold = 3,a, b, d, e, f, g,a, f, g,b, d, e, f,a, b, d,a, b, e, g,root,COMP537,68,Threshold = 3,a, b, d, e, f, g,a, f, g,b, d, e, f,a, b, d,a, b, e, g,root,a:1,b:1,d:1,e:1,f:1,g:1,a:2,COMP537,69,Threshold = 3,a, b,

19、 d, e, f, g,a, f, g,b, d, e, f,a, b, d,a, b, e, g,root,a:2,b:1,d:1,e:1,f:1,g:1,f:1,g:1,COMP537,70,Threshold = 3,a, b, d, e, f, g,a, f, g,b, d, e, f,a, b, d,a, b, e, g,root,a:2,b:1,d:1,e:1,f:1,g:1,f:1,g:1,e:1,a:3,b:2,d:2,COMP537,71,Threshold = 3,a, b, d, e, f, g,a, f, g,b, d, e, f,a, b, d,a, b, e, g,

20、root,a:3,b:2,d:2,e:1,f:1,g:1,f:1,g:1,b:1,d:1,e:1,f:1,a:4,b:3,COMP537,72,Threshold = 3,a, b, d, e, f, g,a, f, g,b, d, e, f,a, b, d,a, b, e, g,root,a:4,b:3,d:2,e:1,f:1,g:1,e:1,g:1,f:1,g:1,b:1,d:1,e:1,f:1,FP-tree,COMP537,73,Step 1: 遍历一次数据库，导出频繁项（1项集）的集合和支持度计数（频率），并且以降序排序。 Step 2: 构造FP-tree Step 3: 根据第二

21、步得到的FP-Tree, 为1项频繁项集中的每一项构造条件FP-Tree. Step 4: 得到频繁模式（频繁项集）.,FP-Tree,条件模式基：一个“子数据库”，由FP树中与该后缀模式一起出现的前缀路径集组成。 由长度为1的频繁模式开始，构造他的条件模式基（即从叶子节点开始）。,COMP537,74,COMP537,75,Threshold = 3,a, b, d, e, f, g,a, f, g,b, d, e, f,a, b, d,a, b, e, g,root,a:4,b:3,d:2,e:1,f:1,g:1,e:1,g:1,f:1,g:1,b:1,d:1,e:1,f:1,76,Thr

22、eshold = 3,root,a:4,b:3,d:2,e:1,f:1,g:1,e:1,g:1,f:1,g:1,b:1,d:1,e:1,f:1,对于项 “g”构造条件FP-Tree, ,(a:1, b:1, d:1, e:1, f:1, g:1),77,Threshold = 3,root,a:4,b:3,d:2,e:1,f:1,g:1,e:1,g:1,f:1,g:1,b:1,d:1,e:1,f:1,对于项 “g”构造条件FP-Tree, ,(a:1, b:1, d:1, e:1, f:1, g:1),(a:1, b:1, e:1, g:1),COMP537,78,Threshold = 3,

23、root,a:4,b:3,d:2,e:1,f:1,g:1,e:1,g:1,f:1,g:1,b:1,d:1,e:1,f:1,Cond. FP-tree on “g”, ,(a:1, b:1, d:1, e:1, f:1, g:1),(a:1, b:1, e:1, g:1),(a:1, f:1, g:1),3,COMP537,79,Threshold = 3,root,a:4,b:3,d:2,e:1,f:1,g:1,e:1,g:1,f:1,g:1,b:1,d:1,e:1,f:1,g-条件/FP-Tree, ,(a:1, b:1, d:1, e:1, f:1, g:1),(a:1, b:1, e:1

24、, g:1),(a:1, f:1, g:1),3,2,1,2,2,3, ,(a:1, b:1,d:1,e:1,f:1),(a:1, b:1,e:1),(a:1, f:1),root,3,g-条件模式基,FP-tree,COMP537,80,Step 1: 遍历一次数据库，导出频繁项（1项集）的集合和支持度计数（频率），并且以降序排序。 Step 2: 构造FP-tree Step 3: 根据第二步得到的FP-Tree, 为1项频繁项集中的每一项构造条件FP-Tree. Step 4: 得到频繁模式（频繁项集）.,COMP537,81,Cond. FP-tree on “a”,root,root

25、,a:3,Cond. FP-tree on “g”,root,Cond. FP-tree on “f”,root,b:3,Cond. FP-tree on “e”,root,b:3,Cond. FP-tree on “d”,root,a:3,Cond. FP-tree on “b”,3,3,3,3,4,4,1. 构造g-条件的FP-Tree前：g (support = 3),2. 构造g-条件的FP-Tree后：a, g (support = 3),1. 构造f-条件的FP-Tree前：f (support = 3),2. 构造f-条件的FP-Tree后：Empty.,1. 构造e-条件的FP

26、-Tree前：e (support = 3),2. 构造e-条件的FP-Tree后：b, e (support = 3),1. 构造d-条件的FP-Treel前：d (support = 3),2. 构造d-条件的FP-Tree后：b, d (support = 3),1. 构造b-条件的FP-Tree前：b (support = 4),2. 构造b-条件的FP-Tree后：a, b (support = 3),1. 构造a-条件的FP-Tree前：a (support = 4),2. 构造a-条件的FP-Tree后：Empty,FP-Tree FP-Growth,FP-Growth算法的效率

27、优于一般的类Apriori 算法，因为FP-Tree算法的整个过程只需要遍历两次事务数据库，并且把大量的数据压缩存储在树中，在时间与空间的开销都优于Apriori算法；缺点是需要使用条件模式基递归地构造FP-Tree不仅占用大量的内存空间，而且一次迭代过程结束后，通常只能得到几个频繁模式，因此算法的效率有待进一步提高。,COMP537,82,主要内容,关联规则的基本概念 Apriori算法 改进的Apriori算法（AprioriTid、AprioriHybrid） FP-Tree算法 基于多最小支持度的关联规则挖掘（ MSapriori 算法） 多层、多维、约束性关联规则挖掘问题 关联规则的

28、评价问题,支持度的分布,大多数数据集中支持度的分布都不平衡,一个零售数据集中支持度的分布,支持度的分布,如何合理设置最小支持度阈值minsup? minsup过高, 可能会丢失稀有的、令人感兴趣的项目 (如，贵重商品或耐用品)。 minsup过低, 则计算开销过大，结果项集过多。 使用单一的最小支持度效果不佳。,多最小支持度模型,每个项目都有一个最小支持度(Minimum Item Supports, MIS) 。 通过为不同的项目提供不同的MIS值，用户可以表达对不同规则的不同支持度的需求。,规则的最小支持度,设MIS(i)代表项目i的MIS. 规则R的最小支持度阈值 minsup 是规则所

29、包含项目的最小MIS。 规则 R: a1, a2, , ak ak+1, , ar 满足最小支持度阈值，若其实际的支持度 min(MIS(a1), MIS(a2), , MIS(ar).,多最小支持度举例,MIS(Milk)=5%, MIS(Coke) = 3%,MIS(Broccoli)=0.1%, MIS(Salmon)=0.5% MIS(Milk, Broccoli) = min (MIS(Milk), MIS(Broccoli) = 0.1% 支持度不再满足反单调性 假设: Support(Milk, Coke) = 1.5% 且Support(Milk, Coke, Broccoli

30、) = 0.5% Milk,Coke 不频繁，但 Milk,Coke,Broccoli 频繁,MSapriori算法,按支持度升序排列项目 e.g.: MIS(1) = 10% MIS(2) = 20% MIS(3) = 5% MIS(4) = 6% 顺序: 3, 4, 1, 2 对Apriori进行修改: L1 : 1-频繁项集（支持度 minMIS(i)） F1 : i | sup(i) MIS(i) C2 : 2-候选项集从F1，而不是L1中连接得到,举例,假设数据集包含100条事务，第一次扫描数据库得到如下项目的支持度: 3.count = 6, 4.count = 3, 1.coun

31、t = 9, 2.count = 25. 则L1= 3, 1, 2, and F1 = 3, 2 由于4.count /n MIS(3) (= 5%)，故L1 中不包含4。 由于1.count /n MIS(1) (= 10%)，故F1中不包含1。,MIS(1) = 10% MIS(2) = 20% MIS(3) = 5% MIS(4) = 6%,多最小支持度Apriori性质,多最小支持度Apriori性质,主要内容,关联规则的基本概念 Apriori算法 改进的Apriori算法（AprioriTid、AprioriHybrid） FP-Tree算法 基于多最小支持度的关联规则挖掘（ MS

32、apriori 算法） 多层、多维、约束性关联规则挖掘问题 关联规则的评价问题,2020/7/6,101,挖掘多种规则或规律,多层(Multi-level)关联规则 多维(Multi-dimension)关联规则 量化(quantitative)关联规则分类 基于约束的挖掘,多层关联规则,项通常形成分层结构 低层的项通常有低支持度. 基于维数和层级可对事务数据库编码 利用共享的多级挖掘,渐进的多层挖掘方法,自顶向下, 渐进加深的方法，在每层挖掘所有的频繁项集: 首先挖掘高层频繁项: milk (15%), bread (10%) 然后挖掘低层的 “较弱” 频繁项集: 2% milk (5%),

33、 wheat bread (4%) 跨层时不同的 min_support门限，算法不同 : 一致支持度 若项的祖先非频繁，则丢掉该项，类似Apriori的优化策略 递减支持度 只检查那些祖先为频繁的或不可忽略的项,多维关联规则概念,单维规则: buys(X, “milk”) buys(X, “bread”) 多维关联规则: 2 维 or 谓词 维间关联规则 (无重复谓词) age(X,”19-25”) occupation(X,“student”) buys(X, “coke”) 混合维关联规则 (重复谓词) age(X,”19-25”) buys(X, “popcorn”) buys(X,

34、“coke”) 分类属性: 有限个可能值, 值间无序数据立方体方法 量化属性: 数值, 值间隐含顺序离散化, 聚类和梯度法,量化关联规则挖掘的技巧,根据量化值的处理方式进行分类，如age,salary 基于预定义的概念分层进行静态离散化(数据立方体方法) 基于数据分布的动态离散化 (量化规则, e.g., Agrawal /大 1-序列 for (k=2;Lk-1;k+) 利用频繁序列Lk生成候选k-序列Ck; for (对于序列数据库S中每个序列s) if (Ck的每个候选序列c包含在s中) c.sup_count+; /c的支持度计数增1 Lk= c | cCk and c.sup_cou

35、ntmin_sup; /由Ck中计数大于min_sup的候选序列组成频繁k-序列集合Lk L=kLk;,L1=，。,上述算法中利用频繁序列Lk-1生成候选k-序列Ck的过程说明如下：,（1）连接,对于Lk-1中任意两个序列s1和s2，如果s1与s2的前k-2项相同，即s1=，s2=，则合并序列s1和s2，得到候选k-序列和。即：,insert into Ck select p.itemset1, p.itemset2, p.itemsetk-1,q.itemsetk-1 from Lk-1 p,Lk-1 q where p.itemset1=q.itemset1 and p.itemset2=q.itemset2 and an