高级人工智能第十二章

1、2022-2-23AA12 关联规则 史忠植1高级人工智能高级人工智能第十二章第十二章 史忠植史忠植 中国科学院计算技术研究所关联规则关联规则 Association Rules Association Rules 2022-2-23AA12 关联规则 史忠植2内容提要内容提要 l引言引言lApriori 算法算法lFrequent-pattern tree 和和FP-growth 算法算法l多维关联规则挖掘多维关联规则挖掘l相关规则相关规则l关联规则改进关联规则改进l总结总结2022-2-23AA12 关联规则 史忠植3关联规则关联规则 l关联规则反映一个事物与其他事物之间的相互依存性和关联

2、性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。关联规则表示了项之间的关系。l示例:cereal, milk fruit“买谷类食品和牛奶的人也会买水果.”商店可以把牛奶和谷类食品作特价品以使人们买更多的水果.2022-2-23AA12 关联规则 史忠植4市场购物篮分析市场购物篮分析l分析事务数据库表l我们是否可假定?lChips = Salsa Lettuce = SpinachPersonBasketAChips, Salsa, Cookies, Crackers, Coke, BeerBLettuce, Spinach, Oranges, Ce

3、lery, Apples, GrapesCChips, Salsa, Frozen Pizza, Frozen CakeDLettuce, Spinach, Milk, Butter2022-2-23AA12 关联规则 史忠植5基本概念l通常, 数据包含:TIDBasket事务 ID项的子集2022-2-23AA12 关联规则 史忠植6 关联规则挖掘l在事务数据库,关系数据库和其它信息库中的项或对象的集合之间,发现频繁模式,关联,相关,或因果关系的结构.l频繁模式: 数据库中出现频繁的模式(项集,序列,等等)2022-2-23AA12 关联规则 史忠植7基本概念l项集项集l事务事务l关联规则关

4、联规则l - 事务数据集 (例如右图例如右图)l事务标识事务标识 TID 每一个事务关联着一个标识每一个事务关联着一个标识,称作称作TID.IT ,.,21miiiI BAIBIABA,DTransaction-idItems bought10A, B, C20A, C30A, D40B, E, F2022-2-23AA12 关联规则 史忠植8关联规则的度量l支持度支持度s slD D中包含中包含A A和和 B B 的事务数与总的事务数的比值的事务数与总的事务数的比值规则规则 A AB B 在数据集在数据集D D中的支持度为中的支持度为s, s, 其中其中s s 表示表示D D中包含中包含A

5、A B B ( (即同时包含即同时包含A A和和B)B)的事务的百分率的事务的百分率. .|)(DTBADTBAs2022-2-23AA12 关联规则 史忠植9关联规则的度量l可信度可信度 c clD D中同时包含中同时包含A A和和B B的事务数与只包含的事务数与只包含A A的事务数的比值的事务数的比值|)(TADTTBADTBAc规则 AB 在数据集D中的可信度为c, 其中c表示D中包含A的事务中也包含B的百分率.即可用条件概率P(B|A)表示. confidence(A B )=P(B|A) 条件概率条件概率 P(B|A) P(B|A) 表示表示A A发生的条件下发生的条件下B B也发生

6、的概率也发生的概率. .2022-2-23AA12 关联规则 史忠植10关联规则的度量l关联规则根据以下两个标准(包含或排除):l最小支持度 表示规则中的所有项在事务中出现的频度l最小可信度 - 表示规则中左边的项(集)的出现暗示着右边的项(集)出现的频度2022-2-23AA12 关联规则 史忠植11市场购物篮分析I是什么?事务ID B的T是什么?s(Chips=Salsa) 是什么?c(Chips=Salsa)是什么?事务 ID购物篮AChips, Salsa, Cookies, Crackers, Coke, BeerBLettuce, Spinach, Oranges, Celery,

7、 Apples, GrapesCChips, Salsa, Frozen Pizza, Frozen CakeDLettuce, Spinach, Milk, Butter, Chips2022-2-23AA12 关联规则 史忠植12频繁项集l项集 任意项的集合lk-项集 包含k个项的项集l频繁 (或大)项集 满足最小支持度的项集l若I包含m个项,那么可以产生多少个项集?2022-2-23AA12 关联规则 史忠植13强关联规则l给定一个项集,容易生成关联规则.l项集: Chips, Salsa, BeerlBeer, Chips = SalsalBeer, Salsa = ChipslChi

8、ps, Salsa = Beerl强规则是有趣的l强规则通常定义为那些满足最小支持度和最小可信度的规则.2022-2-23AA12 关联规则 史忠植14关联规则挖掘l两个基本步骤l找出所有的频繁项集l满足最小支持度l找出所有的强关联规则l由频繁项集生成关联规则l保留满足最小可信度的规则2022-2-23AA12 关联规则 史忠植15内容提要 l引言lApriori 算法lFrequent-pattern tree 和FP-growth 算法l多维关联规则挖掘l相关规则l关联规则改进l总结2022-2-23AA12 关联规则 史忠植16AprioriApriori算法算法lIBM公司Almade

9、n研究中心的R.Agrawal 等人在1993年提出的AIS和SETM。l在1994年提出Apriori和AprioriTid。Apriori和AprioriTid算法利用前次过程中的数据项目集来生成新的候选数据项目集，减少了中间不必要的数据项目集的生成，提高了效率2022-2-23AA12 关联规则 史忠植17生成频繁项集lNave algorithmn - |D|for each subset s of I do l - 0 for each transaction T in D do if s is a subset of T then l - l + 1 if minimum supp

10、ort = l/n then add s to frequent subsets2022-2-23AA12 关联规则 史忠植18生成频繁项集lnave algorithm的分析lI 的子集: O(2m) l为每一个子集扫描n个事务l测试s为T的子集: O(2mn) l随着项的个数呈指数级增长!l我们能否做的更好?2022-2-23AA12 关联规则 史忠植19Apriori 性质l定理定理(Apriori 性质性质): 若A是一个频繁项集,则A的每一个子集都是一个频繁项集.l证明证明:设n为事务数.假设A是l个事务的子集,若 A A , 则A 为l (l l )个事务的子集.因此, l/n s

11、(最小支持度), l/n s也成立.2022-2-23AA12 关联规则 史忠植20Apriori 算法lApriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法.算法名字是缘于算法使用了频繁项集的性质这一先验知识.l思想: Apriori 使用了一种称作level-wise搜索的迭代方法,其中k-项集被用作寻找(k+1)-项集.首先,找出频繁1-项集,以L1表示.L1用来寻找L2,即频繁2-项集的集合.L2用来寻找L3,以此类推,直至没有新的频繁k-项集被发现.每个Lk都要求对数据库作一次完全扫描.2022-2-23AA12 关联规则 史忠植21生成频繁项集l中心思想: 由频繁(k

12、-1)-项集构建候选k-项集l方法l找到所有的频繁1-项集l扩展频繁(k-1)-项集得到候选k-项集l剪除不满足最小支持度的候选项集2022-2-23AA12 关联规则 史忠植22Apriori: 一种候选项集生成-测试方法lApriori 剪枝原理: 若任一项集是不频繁的,则其超集不应该被生成/测试!l方法: l由频繁k-项集生成候选(k+1)-项集,并且l在DB中测试候选项集l性能研究显示了Apriori算法是有效的和可伸缩(scalablility)的.2022-2-23AA12 关联规则 史忠植23The Apriori 算法算法一个示例一个示例Database TDB1st scan

13、C1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E22022-2-23AA12 关联规则 史忠植24Apriori 算法算法Algorithm: Apriori输

14、入输入: Database, D, of transactions; minimum support threshold,min_sup.输出输出: L, freuqent itemsets in D.过程过程:Ck: Candidate itemset of size kLk : frequent itemset of size kL1 = find_frequent_1_itemsets(D);for (k = 2; Lk+1 !=; k+) do begin Ck = apriori_gen(Lk-1 ,min_sup); for each transaction t in databa

15、se D do/scan D for counts Ct =subset(Ck ,t);/ get the subsets of t that are candidates For each candidate c Ct c.count+; Lk = candidates in Ck with min_support endreturn L=k Lk;2022-2-23AA12 关联规则 史忠植25Apriori 算法算法Procedure apriori_gen(Lk-1: frequent (k-1)-itemsets; min_sup:minimum support threshold

16、)for each itemset l1 Lk-1 for each itemset l2Lk-1 if(l11=l21) (l12=l22) (l1k-1=l2k-1) Then c=join(l1,l2)/join step: generate candidates if has_infrequent_subset(c, Lk-1 ) then delete c;/prune step: remove unfruitful candidate else add c to Ckreturn Ck2022-2-23AA12 关联规则 史忠植26Apriori 算法算法Join is gener

17、ate candidates set of itemsets Ck from 2 itemsets in Lk-1Procedure join(p,q) insert into Ck select p.item1, p.item2,., p.itemk-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1=q.item1, ., p.itemk-2=q.itemk-2, p.itemk-1 = q.itemk-12022-2-23AA12 关联规则 史忠植27Apriori 算法算法 Procedure has_infrequent_subset(c:c

18、andidate k-itemset;Lk-1: frequent (k-1)-itemsets;)/use prior knowledge for each (k-1)-subset s of c if s Lk-1 then return TRUE;return FALSE.2022-2-23AA12 关联规则 史忠植28Apriori 算法算法l如何生成候选项集?l步骤 1: 自连接 Lkl步骤 2: 剪枝l如何计算候选项集的支持度?l候选项庥生成的示例lL3= abc, abd, acd, ace, bcd l自连接: L3*L3l由abcabc 和abdabd 连接得到abcdabc

19、d l由acdacd 和aceace 连接得到acdeacdel剪枝:l因为adeade 不在L L3 3中acdeacde 被剪除lC4=abcd2022-2-23AA12 关联规则 史忠植29如何生成候选项集如何生成候选项集? ?l假定Lk-1中的项以一定顺序排列l步骤 1: 自连接 Lk-1 insert into Ckselect p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1l步骤 2

20、: 剪枝forall itemsets c in Ck doforall (k-1)-subsets s of c doif (s is not in Lk-1) then delete c from Ck2022-2-23AA12 关联规则 史忠植30如何计算候选项集的支持度如何计算候选项集的支持度? ?l为何候选项集的支持度的计算是一个问题?l候选项集的总数可能是巨大的l 一个事务可能包含多个候选项集l方法:l候选项集被存储在一个哈希树l哈希树的叶子结点包含一个项集和计数的列表l内部结点 包含一个哈希表l子集函数: 找出包含在一个事务中的所有候选项集2022-2-23AA12 关联规则 史

21、忠植31频繁模式挖掘的挑战l挑战l多次扫描事务数据库l巨大数量的候选项集l繁重的计算候选项集的支持度工作l改进 Apriori: 大体的思路l减少事务数据库的扫描次数l缩减候选项集的数量l使候选项集的支持度计算更加方便2022-2-23AA12 关联规则 史忠植32AprioriTidAprioriTid算法算法lAprioriTid算法由Apriori算法改进l优点：只和数据库做一次交互，无须频繁访问数据库l将Apirori中的Ck 扩展，内容由c变为TID，c，TID用于唯一标识事务l引入Bk ，使得Bk 对于事务的项目组织集合，而不是被动的等待Ck 来匹配2022-2-23AA12 关联

22、规则 史忠植33AprioriTidAprioriTid算法算法l举例：minsupp = 2l数据库：TID项目1001 3 42002 3 5300 1 2 3 54002 52022-2-23AA12 关联规则 史忠植34AprioriTidAprioriTid算法算法示例示例TID项目集1001 3 42002 3 5300 1 2 3 54002 5项集支持度12233 3532022-2-23AA12 关联规则 史忠植35ApioriTidApioriTid算法示例算法示例TID项目集1001 32002 3 2 5 3 5 300 1 2 1 3 1 5 2 3 2 5 3 54

23、002 5项集支持度1 322 322 5 33 522022-2-23AA12 关联规则 史忠植36ApioriTidApioriTid算法示例算法示例TID项目集100 空2002 3 5300 2 3 5 400 空2022-2-23AA12 关联规则 史忠植37ApioriTidApioriTid算法算法l上面图中分别为Bk 和Lk ，而Ck 和Apriori算法产生的一样，因此没有写出来l可以看到Bk 由Bk-1 得到，无须由数据库取数据l缺点：内存要求很大，事务过多的时候资源难以满足2022-2-23AA12 关联规则 史忠植38内容提要 l引言lApriori 算法lFreque

24、nt-pattern tree 和FP-growth 算法l多维关联规则挖掘l相关规则l关联规则改进l总结2022-2-23AA12 关联规则 史忠植39频繁模式挖掘的瓶颈频繁模式挖掘的瓶颈l多次扫描数据库是高代价的l长模式的挖掘需要多次扫描数据库以及生成许多的候选项集l找出频繁项集 i1i2i100l扫描次数: 100l候选项集的数量: (1001) + (1002) + + (110000) = 2100-1 = 1.27*1030 !l瓶颈:候选项集-生成-测试l我们能否避免生成候选项集?2022-2-23AA12 关联规则 史忠植40不生成候选项集的频繁模式挖掘不生成候选项集的频繁模式

25、挖掘l利用局部频繁的项由短模式增长为长模式l“abc” 是一个频繁模式l得到所有包含 “abc”的事务: DB|abcl“d” 是 DB|abc 的一个局部频繁的项 abcd 是一个频繁模式2022-2-23AA12 关联规则 史忠植41FP Growth算法算法 (Han, Pei, Yin 2000)lApriori算法的一个有问题的方面是其候选项集的生成l指数级增长的来源l另一种方法是使用分而治之的策略(divide and conquer)l思想思想: 将数据库的信息压缩成一个描述频繁项相关信息的频繁模式树2022-2-23AA12 关联规则 史忠植42利用利用FP-FP-树进行频繁模

26、式挖掘树进行频繁模式挖掘l思想: 频繁模式增长l递归地增长频繁模式借助模式和数据库划分l方法 l对每个频繁项,构建它的条件模式基,然后构建它的条件FP-树.l对每个新创建的条件FP-树重复上述过程l直至结果FP-树为空,或者它仅包含一个单一路径.该路径将生成其所有的子路径的组合,每个组合都是一个频繁模式.2022-2-23AA12 关联规则 史忠植43频繁频繁 1-1-项集项集l最小支持度为20% (计数为 2)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3ItemsetSuppo

27、rt countI16I27I36I42I52I61ItemsetSupport countI16I27I36I42I52 事务数据库 支持度计数 频繁1-项集2022-2-23AA12 关联规则 史忠植44FP-FP-树树 构建构建ItemsetSupport countI16I27I36I42I52ItemsetSupport countI27I16I36I42I52按支持度降序排列2022-2-23AA12 关联规则 史忠植45FP-FP-树树 构建构建 创建根结点null 扫描数据库 事务1: I1, I2, I5 排序: I2, I1, I5 处理事务 以项的顺序增加结点 标注项及其

28、计数(I2,1)(I1,1)(I5,1)1I50I40I31I11I2 维护索引表2022-2-23AA12 关联规则 史忠植46FP-FP-树树 构建构建null(I2,2)(I1,1)(I5,1)0I51I40I30I12I2(I4,1)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I32022-2-23AA12 关联规则 史忠植47FP-FP-树树 构建构建null(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(I4,1)TIDItems1I1,I2,I52I

29、2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3(I3,2)(I3,2)(I1,2)(I3,2)(I4,1)(I5,1)2022-2-23AA12 关联规则 史忠植48FP-FP-树树 构建构建l扫描事务数据库D一次,得到频繁项的集合F及它们的支持度.将F按支持度降序排列成L,L是频繁项的列表.l创建FP-树的根, 标注其为NULL.对D中的每个事务进行以下操作:l根据 L中的次序对事务中的频繁项进行选择和排序. 设事务中的已排序的频繁项列表为p|P,其中p表示第一个元素,P表示剩余的列表.调用insert_Tree(p

30、|P,T).2022-2-23AA12 关联规则 史忠植49FP-FP-树树 构建构建lInsert_Tree(p|P,T) If T has a child N such that N.item-name= p.item-name, then increment Ns count by 1; else create a new node N, and let its count be 1, its parent link be linked to T, and its node- link to the nodes with the same item-name via the node-l

31、ink structure. If P is nonempty, call insert_tree(P,N) recursively. 2022-2-23AA12 关联规则 史忠植50挖掘挖掘 FP-treeFP-treel从索引表中的最后一个项开始l找到所有包含该项的路径l沿着结点-链接(node-links)l确定条件模式l路径中符合频度要求的模式l构建 FP-tree Cl添加项至C中所有路径,生成频繁模式l递归地挖掘C (添加项)l从索引表和树中移除项2022-2-23AA12 关联规则 史忠植51挖掘挖掘 FP-TreeFP-Treenull(I2,7)(I1,4)(I5,1)2I5

32、2I46I36I17I2(I4,1)(I3,2)(I3,2)(I4,1)(I5,1)(I1,2)(I3,2) 前缀路径(I2 I1,1)(I2 I1 I3, 1)条件路径(I2 I1, 2) 条件 FP-tree (I2 I1 I5, 2), (I2 I5, 2), (I1 I5, 2)null(I2,2)(I1,2)2022-2-23AA12 关联规则 史忠植52挖掘挖掘 FP-Tree项条件模式基条件FP-tree生成的频繁模式I5(I2 I1:1),(I2 I1 I3:1)I2 I5:2,I1 I5:2,I2 I1 I5:2I4(I2 I1:1),(I2:1)I2 I4:2I3(I2 I

33、1:2,(I2:2),(I1:2),I2 I3:4,I1 I3:2,I2 I1 I3:2I1(I2:4)I2 I1:42022-2-23AA12 关联规则 史忠植53挖掘挖掘 FP-TreeProcedure FP_growth(Tree, )(1)If Tree contains a single path P then (2) for each combination (denote as ) of the nodes in the path P(3) generate pattern with support = minisup of nodes in ;(4)Else for each

34、 ai in the header of Tree (5) generate pattern =ai with support =ai.support;(6) construct , s conditional pattern base and then conditional FP_tree Tree;(7) IF Tree then(8) call FP_growth(Tree, ); 2022-2-23AA12 关联规则 史忠植54由事务数据库构建由事务数据库构建FP-FP-树树f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequ

35、ency head f4c4a3b3m3p3min_support = 3TIDItems bought (ordered) frequent items100f, a, c, d, g, i, m, pf, c, a, m, p200a, b, c, f, l, m, of, c, a, b, m300 b, f, h, j, o, wf, b400 b, c, k, s, pc, b, p500 a, f, c, e, l, p, m, nf, c, a, m, p1. 扫描DB一次,找到频繁1项 (单一项模式)2. 按支持度降序对频繁项排序为 F-list3. 再次扫描DB,构建FP-t

36、reeF-list=f-c-a-b-m-p2022-2-23AA12 关联规则 史忠植55划分模式和数据库划分模式和数据库l频繁模式根据F-list可以被划分为若干子集lF-list=f-c-a-b-m-pl包含 p的模式l包含 m 但包含 p的模式ll包含 c 但不包含 a ,b, m, p的模式l模式 fl完整性 和 非冗余性2022-2-23AA12 关联规则 史忠植56从从P P的条件数据库找出包含的条件数据库找出包含P P的模式的模式l从 FP-tree的索引表的频繁项开始l沿着每个频繁项p的链接遍历 FP-treel累积项p的所有转换前缀路径来形成的p的条件模式基条件模式基条件模式

37、基项项 条件模式基条件模式基cf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p32022-2-23AA12 关联规则 史忠植57递归递归: : 挖掘每个条件挖掘每个条件FP-treeFP-treef:3c:3a:3m-条件条件 FP-tree“am”的条件模式基: (fc:3)f:3c:3am-条件条件 FP-tree“cm”的条件模式基: (f:3)f:3cm-条件条件 FP-tree“c

38、am”的条件模式基: (f:3)f:3cam-条件条件 FP-tree2022-2-23AA12 关联规则 史忠植58一个特例一个特例: FP-tree: FP-tree中的单一前缀路径中的单一前缀路径l假定 (条件的) FP-tree T 有一个共享的单一前缀路径 Pl挖掘可以分为两部分l将单一前缀路径约简为一个结点l将两部分的挖掘结果串联a2:n2a3:n3a1:n1b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1r1=2022-2-23AA12 关联规则 史忠植59通过通过 DB DB 投影投影(Projection)(

39、Projection)使使FP-growthFP-growth可可伸缩伸缩lFP-tree 不能全放入内存?DB 投影l首先将一个数据库划分成一个由若干投影(Projected)数据库组成的集合l然后对每个投影数据库构建和挖掘 FP-treelParallel projection vs. Partition projection 技术lParallel projection is space costly2022-2-23AA12 关联规则 史忠植60Partition-based ProjectionlParallel projection 需要很多磁盘空间lPartition proje

40、ction 节省磁盘空间Tran. DB fcampfcabmfbcbpfcampp-proj DB fcamcbfcamm-proj DB fcabfcafcab-proj DB fcba-proj DBfcc-proj DBff-proj DB am-proj DB fcfcfccm-proj DB fff2022-2-23AA12 关联规则 史忠植61改进途径改进途径l使用哈希表存储候选k-项集的支持度计数l移除不包含频繁项集的事务l对数据采样l划分数据l若一个项集是频繁的,则它必定在某个数据分区中是频繁的.2022-2-23AA12 关联规则 史忠植62FP-tree FP-tree

41、结构的优点结构的优点l完整性 l保持了频繁项集挖掘的完整信息l没有打断任何事务的长模式l紧密性l减少不相关的信息不频繁的项没有了l项按支持度降序排列: 越频繁出现,越可能被共享l决不会比原数据库更大 (不计结点链接和计数域)l对 Connect-4 数据库, 压缩比率可以超过1002022-2-23AA12 关联规则 史忠植63关联规则可视化关联规则可视化: 方格图方格图(Pane Graph)2022-2-23AA12 关联规则 史忠植64关联规则可视化关联规则可视化: : 规则图规则图(Rule Graph)(Rule Graph)2022-2-23AA12 关联规则 史忠植65内容提要

42、l引言lApriori 算法lFrequent-pattern tree 和FP-growth 算法l多维关联规则挖掘l相关规则l关联规则改进l总结2022-2-23AA12 关联规则 史忠植66挖掘多种规则或规律挖掘多种规则或规律l多层(Multi-level),量化(quantitative)关联规则, 相关(correlation)和因果(causality), 比率(ratio)规则, 序列 (sequential) 模式,浮现(emerging)模式, temporal associations, 局部周期(partial periodicity)l分类(classification

43、),聚类(clustering),冰山立方体( iceberg cubes), 等等.2022-2-23AA12 关联规则 史忠植67多层关联规则多层关联规则l项常常构成层次l可伸缩的(flexible)支持度设置: 在较低层的项预期有较低的支持度.l事务数据库可以基于维度和层次编码l探寻共享多层挖掘统一支持度Milksupport = 10%2% Milk support = 6%Skim Milk support = 4%Level 1min_sup = 5%Level 2min_sup = 5%Level 1min_sup = 5%Level 2min_sup = 3%减少的支持度202

44、2-2-23AA12 关联规则 史忠植68可伸缩的支持度约束的多层可伸缩的支持度约束的多层/ /多维多维(ML/MD)(ML/MD)关联规则关联规则l为什么设置可伸缩的支持度?l实际生活中项的出现频率变化巨大l在一个商店购物篮中的钻石,手表,钢笔l统一的支持度未必是一个有趣的模型l一个可伸缩模型l较低层的,较多维的组合以及长模式通常具有较小的支持度l总体规则应该要容易说明和理解l特殊的项和特殊的项的组合可以特别设定(最小支持度)以及拥有更高的优先级2022-2-23AA12 关联规则 史忠植69多维关联规则多维关联规则l单维规则:buys(X, “milk”) buys(X, “bread”)

45、l多维规则: 2 个维度或谓词( predicates)l跨维度(Inter-dimension)关联规则 (无重复谓词)age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)l混合维度(hybrid-dimension)关联规则 (重复谓词)age(X,”19-25”) buys(X, “popcorn”) buys(X, “coke”)l分类(Categorical)属性l有限的几个可能值,值之间不可排序l数量(Quantitative)属性l数值的,值之间有固有的排序2022-2-23AA12 关联规则 史忠植70多层关联规则多层关联规

46、则: :冗余滤除冗余滤除l根据项之间的”先辈” (ancestor)关系,一些规则可能是冗余的. l示例lmilk wheat bread support = 8%, confidence = 70%l2% milk wheat bread support = 2%, confidence = 72%l我们说第1个规则是第2个规则的先辈.l一个规则是冗余的,当其支持度接近基于先辈规则的”预期”(expected)值.2022-2-23AA12 关联规则 史忠植71多层关联规则多层关联规则: :逐步深化逐步深化(Progressive Deepening)(Progressive Deepeni

47、ng)l一个自上而下的,逐步深化的方法:l 首先挖掘高层的频繁项: milk (15%), bread (10%)l 然后挖掘它们的较低层”较弱” (weaker)频繁项: 2% milk (5%), wheat bread (4%)l多层之间不同的最小支持度阈值导致了不同的算法:l如果在多个层次间采用了相同的最小支持度,若t的任何一个先辈都是非频繁的则扔弃(toss)t.l如果在较低层采用了减少的最小支持度，则只检验那些先辈的支持度是频繁的不可忽略的派生（descendents）即可2022-2-23AA12 关联规则 史忠植72多维关联规则挖掘的技术多维关联规则挖掘的技术l搜索频繁 k-谓

48、词集(predicate set):l示例: age, occupation, buys是一个 3-谓词集以age处理的方式,技术可以如下分类1. 利用数量属性的统计离散(static discretization)方法 利用预先确定的概念层次对数量属性进行统计离散化2. 量化关联规则l基于数据的分布,数量属性被动态地离散化到不同的容器空间(bins)3. 基于距离(Distance-based)的关联规则l这是一个动态离散化的过程,该过程考虑数据点之间的距离2022-2-23AA12 关联规则 史忠植73数量属性的统计离散化数量属性的统计离散化l挖掘之前利用概念层次离散化l数值被范围(ran

49、ges)替代.l关系数据库中,找出所有的频繁k-谓词(predicate)集要求 k 或 k+1次表扫描.l数据立方体(data cube)非常适合数据挖掘.lN-维立方体的 cells 与谓词集( predicate sets)相对应.l通过数据立方体挖掘会非常快速.(income)(age)()(buys)(age, income)(age,buys) (income,buys)(age,income,buys)2022-2-23AA12 关联规则 史忠植74量化关联规则量化关联规则age(X,”30-34”) income(X,”24K - 48K”) buys(X,”high reso

50、lution TV”)l数值属性动态离散化l这样挖掘的规则的可信度或紧密度最大化l2-维 量化关联规则: Aquan1 Aquan2 Acatl示例2022-2-23AA12 关联规则 史忠植75Mining Distance-based Association RuleslBinning methods do not capture the semantics of interval datalDistance-based partitioning, more meaningful discretization considering:ldensity/number of points in

51、 an intervall“closeness” of points in an intervalPrice($)Equi-width(width $10)Equi-depth(depth 2)Distance-based70,107,207,72011,2022,5020,222221,3051,5350,535031,405141,505351,602022-2-23AA12 关联规则 史忠植76Interestingness Measure: Correlations (Lift)lplay basketball eat cereal 40%, 66.7% is misleadinglT

52、he overall percentage of students eating cereal is 75% which is higher than 66.7%.lplay basketball not eat cereal 20%, 33.3% is more accurate, although with lower support and confidencelMeasure of dependent/correlated events: liftBasketballNot basketballSum (row)Cereal200017503750Not cereal100025012

53、50Sum(col.)300020005000)()()(,BPAPBAPcorrBA2022-2-23AA12 关联规则 史忠植77内容提要 l引言lApriori 算法lFrequent-pattern tree 和FP-growth 算法l多维关联规则挖掘l相关规则l关联规则改进l总结2022-2-23AA12 关联规则 史忠植78相关规则相关规则(Correlation Rules)(Correlation Rules)l“Beyond Market Baskets,” Brin et al.l假设执行关联规则挖掘ccrowt20525t70575col9010100tea = cof

54、fee20% support80% confidencebut 90% of the people buy coffee anyway!2022-2-23AA12 关联规则 史忠植79相关规则相关规则l一种度量是计算相关性l若两个随机变量 A 和 B 是统计独立的l对tea 和 coffee:1)()()(BPAPBAP89.0)()()(cPtPctP2022-2-23AA12 关联规则 史忠植80相关规则相关规则l利用 2 统计检验来测试独立性l设n为购物篮的总数l设k为考虑的项的总数l设 r 为一个包含项 (ij, ij)的规则l设O(r) 表示包含规则r的购物篮的数量 (即频率)l对单

55、个项ij,设 Eij = O(ij) (反过来即为 n - Eij)lEr = n * Er1/n * * Erk / n2022-2-23AA12 关联规则 史忠植81相关规则相关规则l2 统计量定义为lLook up for significance value in a statistical textbooklThere are k-1 degrees of freedomlIf test fails cannot reject independence, otherwise contigency table represents dependence.RrrErErO)(222022

56、-2-23AA12 关联规则 史忠植82示例示例lBack to tea and coffeelEt = 25, Et=75, Ec=90, Ec=10lEtc=100 * 25/100 * 90 /100=22.5lO(tc) = 20lContrib. to 2 = (20 - 22.5)2 / 22.5 = 0.278lCalculate for the rest to get 2=2.204lNot significant at 95% level (3.84 for k=2)lCannot reject independence assumptionccrowt20525t 7057

57、5col90101002022-2-23AA12 关联规则 史忠植83兴趣度（兴趣度（InterestInterest）lIf 2 test shows significance, then want to find most interesting cell(s) in tablelI(r) = O(r)/ErlLook for values far away from 1lI(tc) = 20/22.5 = 0.89lI(tc) = 5/2.5 = 2lI(tc) = 70/67.5 = 1.04lI(tc) = 5/7.5 = 0.662022-2-23AA12 关联规则 史忠植842

58、统计量的性质l上封闭性(Upward closed)l若一个k-项集是相关的,则其所有的超集也是相关的.l寻找最小的相关的项集l没有子集是相关的l能否将a-priori and 2 统计量有效地结合lNo generate and prune as in support-confidence2022-2-23AA12 关联规则 史忠植85其它度量其它度量(Measures)(Measures)l(A B) P(A,B)P(A)P(B)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3l

59、作用度(Lift)l度量项之间的相关性,但没有检验2022-2-23AA12 关联规则 史忠植86其它度量其它度量(Measures)(Measures)l可信度(Conviction)l度量一个规则的强度A B (AB)c(A B) P(A)P(B)P(A,B)TIDItems1I1,I2,I52I2,I43I2,I3,I64I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I32022-2-23AA12 关联规则 史忠植87内容提要 l引言lApriori 算法lFrequent-pattern tree 和FP-growth 算法l多维关联规则挖掘

60、l相关规则l关联规则改进l总结2022-2-23AA12 关联规则 史忠植88关联规则改进关联规则改进lLin等人提出解决规则挖掘算法中的数据倾斜问题，从而使算法具有较好的均衡性。Park等人提出把哈希表结构用于关联规则挖掘。lAgrawal首先提出事务缩减技术，Han和Park等人也分别在减小数据规模上做了一些工作。 l抽样的方法是由Toivonen提出的。 lBrin等人采用动态项集计数方法求解频繁项集。 lAggarwal提出用图论和格的理论求解频繁项集的方法。Prutax算法就是用格遍历的办法求解频繁项集。 2022-2-23AA12 关联规则 史忠植89关联规则改进关联规则改进l关联