数据挖掘关联规则

1、1关联规则 Association Rules2内容提要内容提要 n引言引言nApriori Apriori 算法算法nFrequent-pattern tree Frequent-pattern tree 和和FP-growth FP-growth 算法算法n多维关联规则挖掘多维关联规则挖掘n相关规则相关规则n基于约束的关联规则挖掘基于约束的关联规则挖掘n总结总结3 关联规则挖掘关联规则挖掘n在事务数据库,关系数据库和其它信息库中的项或对象的集合之间,发现频繁模式,关联,相关,或因果关系的结构.n频繁模式: 数据库中出现频繁的模式(项集,序列,等等)4基本概念基本概念n项集项集n事务事务n关

2、联规则关联规则n事务数据集事务数据集 ( (例如右图例如右图) )n事务标识事务标识 TIDTID： 每一个事务关联着一个标识每一个事务关联着一个标识IT ,.,21miiiI BAIBIABA,D5基本概念基本概念n支持度支持度s snD D中包含中包含A A和和 B B 的事务数与总的事务数的比的事务数与总的事务数的比值值规则规则 A AB B 在数据集在数据集D D中的支持度为中的支持度为s, s, 其中其中s s 表表示示D D中包含中包含A A B B ( (即同时包含即同时包含A A和和B)B)的事务的百的事务的百分率分率. .|)(DTBADTBAs6基本概念基本概念n支持度支持

3、度s snD D中包含中包含A A和和 B B 的事务数与总的事务数的比的事务数与总的事务数的比值值规则规则 A AB B 在数据集在数据集D D中的支持度为中的支持度为s, s, 其中其中s s 表表示示D D中包含中包含A A B B ( (即同时包含即同时包含A A和和B)B)的事务的百的事务的百分率分率. .|)(DTBADTBAs7基本概念基本概念n可信度可信度 c cnD D中同时包含中同时包含A A和和B B的事务数与只包含的事务数与只包含A A的事务的事务数的比值数的比值|)(TADTTBADTBAc规则规则 A AB B 在数据集在数据集D D中的中的可信可信度为度为c,c,

4、 其中其中c c表示表示D D中包含中包含A A的事务中也包含的事务中也包含B B的百分率的百分率. .即可用条件概率即可用条件概率P(B|A)P(B|A)表示表示. . confidence( confidence(A A B )=P(B|A)B )=P(B|A) 条件概率条件概率 P(B|A) P(B|A) 表示表示A A发生的条件下发生的条件下B B也发生也发生的概率的概率. .8关联规则挖掘关联规则挖掘n两个基本步骤两个基本步骤nStep one:Step one:找出所有的频繁项集找出所有的频繁项集n满足最小支持度满足最小支持度nStep two:Step two:找出所有的强关联规

5、则找出所有的强关联规则n由频繁项集生成关联规则由频繁项集生成关联规则n保留满足最小可信度的规则保留满足最小可信度的规则9Apriori Apriori 性质性质n定理定理(Apriori (Apriori 性质性质): ): 若若A A是一个频繁项集是一个频繁项集, ,则则A A的的每一个子集都是一个频繁项集每一个子集都是一个频繁项集. .n证明证明: :设设n n为事务数为事务数. .假设假设A A是是l l个事务的子集个事务的子集, ,若若 A A A A , , 则则A A 为为l l (l (l l ) l )个事务的子集个事务的子集. .因此因此, , l/n s(l/n s(最小支

6、持度最小支持度), l), l/n s/n s也成立也成立. .10Apriori Apriori 算法算法nAprioriApriori算法是一种经典的生成布尔型关联规则的频算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法繁项集挖掘算法. .算法名字是缘于算法使用了频繁项算法名字是缘于算法使用了频繁项集的性质这一先验知识集的性质这一先验知识. .n思想思想: Apriori : Apriori 使用了一种称作使用了一种称作level-wiselevel-wise搜索的搜索的迭代方法迭代方法, ,其中其中k-k-项集被用作寻找项集被用作寻找(k+1)-(k+1)-项集项集. .首先首先,

7、,找出频繁找出频繁1-1-项集项集, ,以以L1L1表示表示.L1.L1用来寻找用来寻找L2,L2,即即频繁频繁2-2-项集的集合项集的集合.L2.L2用来寻找用来寻找L3,L3,以此类推以此类推, ,直至没直至没有新的频繁有新的频繁k-k-项集被发现项集被发现. .每个每个LkLk都要求对数据库作都要求对数据库作一次完全扫描一次完全扫描.11生成频繁项集生成频繁项集n中心思想中心思想: : 由频繁由频繁(k-1)-(k-1)-项集构建候选项集构建候选k-k-项集项集n方法方法n找到所有的频繁找到所有的频繁1-1-项集项集n扩展频繁扩展频繁(k-1)-(k-1)-项集得到候选项集得到候选k-k

8、-项集项集n剪除不满足最小支持度的候选项集剪除不满足最小支持度的候选项集12Apriori: Apriori: 一种候选项集生成一种候选项集生成- -测试方法测试方法nApriori Apriori 剪枝原理剪枝原理: : 若任一项集是不频繁的若任一项集是不频繁的, ,则其超则其超集不应该被生成集不应该被生成/ /测试测试! !n方法方法: : n由频繁由频繁k-k-项集生成候选项集生成候选(k+1)-(k+1)-项集项集, ,并且并且n在在DBDB中测试候选项集中测试候选项集n性能研究显示了性能研究显示了AprioriApriori算法是有效的和可伸缩算法是有效的和可伸缩(scalablil

9、ity)(scalablility)的的. .13The Apriori The Apriori 算法算法一个示例一个示例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scan14频繁模式挖掘的挑战频繁模式挖掘的挑战n挑战n多次扫描事务数据库n巨大数量的候选项集n繁重的计算候选项集的支持度工作n改进 Apriori: 大体的思路n减少事务数据库的扫描次数n缩减候选项集的数量n使候选项集的支持度计算更加方便15内容提要内容提要 n引言nApriori 算法nFrequent-pattern tree 和FP-growth 算法n多维关联规则挖掘n相关

10、规则n基于约束的关联规则挖掘n总结16频繁模式挖掘的瓶颈n多次扫描数据库是高代价的n长模式的挖掘需要多次扫描数据库以及生成许多的候选项集n找出频繁项集 i1i2i100n扫描次数: 100n候选项集的数量: (1001) + (1002) + + (110000) = 2100-1 = 1.27*1030 !n瓶颈:候选项集-生成-测试n我们能否避免生成候选项集?17不生成候选项集的频繁模式挖掘n利用局部频繁的项由短模式增长为长模式n“abc” 是一个频繁模式n得到所有包含 “abc”的事务: DB|abcn“d” 是 DB|abc 的一个局部频繁的项 abcd 是一个频繁模式18FP Gro

11、wth算法 (Han, Pei, Yin 2000)nApriori算法的一个有问题的方面是其候选项集的生成n指数级增长的来源n另一种方法是使用分而治之的策略(divide and conquer)n思想思想: : 将数据库的信息压缩成一个描述频繁项相关信息的频繁模式树19利用FP-树进行频繁模式挖掘n思想: 频繁模式增长n递归地增长频繁模式借助模式和数据库划分n方法 n对每个频繁项,构建它的条件模式基,然后构建它的条件FP-树.n对每个新创建的条件FP-树重复上述过程n直至结果FP-树为空,或者它仅包含一个单一路径.该路径将生成其所有的子路径的组合,每个组合都是一个频繁模式.20频繁 1-项

12、集n最小支持度为20% (计数为 2) 事务数据库 支持度计数 频繁1-项集21FP-树 构建按支持度降序排列22FP-树 构建 创建根结点null 扫描数据库 事务1: I1, I2, I5 排序: I2, I1, I5 处理事务 以项的顺序增加结点 标注项及其计数(I2,1)(I1,1)(I5,1)1I50I40I31I11I2 维护索引表23FP-树 构建null(I2,2)(I1,1)(I5,1)0I51I40I30I12I2(I4,1)24FP-树 构建null(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(I4,1)(I3,2)(I3,2)(I1,2)(I3,2

13、)(I4,1)(I5,1)25FP-树 构建n扫描事务数据库D一次,得到频繁项的集合F及它们的支持度.将F按支持度降序排列成L,L是频繁项的列表.n创建FP-树的根, 标注其为NULL.对D中的每个事务进行以下操作:n根据 L中的次序对事务中的频繁项进行选择和排序. 设事务中的已排序的频繁项列表为p|P,其中p表示第一个元素,P表示剩余的列表.调用insert_Tree(p|P,T).26挖掘 FP-treen从索引表中的最后一个项开始n找到所有包含该项的路径n沿着结点-链接(node-links)n确定条件模式n路径中符合频度要求的模式n构建 FP-tree Cn添加项至C中所有路径,生成频

14、繁模式n递归地挖掘C (添加项)n从索引表和树中移除项27挖掘 FP-Treenull(I2,7)(I1,4)(I5,1)2I52I46I36I17I2(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)28挖掘 FP-Tree29由事务数据库构建FP-树f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem

15、frequency 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, p扫描DB一次,找到频繁1项 (单一项模式)按支持度降序对频繁项排序为 F-list再次扫描DB,构建FP-treeF

16、-list=f-c-a-b-m-p30划分模式和数据库n频繁模式根据F-list可以被划分为若干子集nF-list=f-c-a-b-m-pn包含 p的模式n包含 m 但包含 p的模式nn包含 c 但不包含 a ,b, m, p的模式n模式 fn完整性 和 非冗余性31从P的条件数据库找出包含P的模式n从 FP-tree的索引表的频繁项开始n沿着每个频繁项p的链接遍历 FP-treen累积项p的所有转换前缀路径来形成的p的条件模式基条件模式基条件模式基项项 条件模式基条件模式基cf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1f:4c:1b:

17、1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p332递归: 挖掘每个条件FP-treef:3c:3a:3m-条件条件 FP-tree“am”的条件模式基: (fc:3)f:3c:3am-条件条件 FP-tree“cm”的条件模式基: (f:3)f:3cm-条件条件 FP-tree“cam”的条件模式基: (f:3)f:3cam-条件条件 FP-tree33一个特例: FP-tree中的单一前缀路径n假定 (条件的) FP-tree T 有一个共享的单一前缀路径 Pn挖掘可以分为两部分n将单一前缀路径约简为

18、一个结点n将两部分的挖掘结果串联a2:n2a3:n3a1:n1b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1r1=34通过 DB 投影(Projection)使FP-growth可伸缩nFP-tree 不能全放入内存?DB 投影n首先将一个数据库划分成一个由若干投影(Projected)数据库组成的集合n然后对每个投影数据库构建和挖掘 FP-treenParallel projection vs. Partition projection 技术nParallel projection is space costly35Par

19、tition-based ProjectionnParallel projection 需要很多磁盘空间nPartition projection 节省磁盘空间Tran. DB fcampfcabmfbcbpfcampp-proj DB fcamcbfcamm-proj DB fcabfcafcab-proj DB fcba-proj DBfcc-proj DBff-proj DB am-proj DB fcfcfccm-proj DB fff36改进途径n使用哈希表存储候选k-项集的支持度计数n移除不包含频繁项集的事务n对数据采样n划分数据n若一个项集是频繁的,则它必定在某个数据分区中是频繁

20、的.37FP-tree 结构的优点n完整性 n保持了频繁项集挖掘的完整信息n没有打断任何事务的长模式n紧密性n减少不相关的信息不频繁的项没有了n项按支持度降序排列: 越频繁出现,越可能被共享n决不会比原数据库更大 (不计结点链接和计数域)n对 Connect-4 数据库, 压缩比率可以超过10038内容提要内容提要 n引言nApriori 算法nFrequent-pattern tree 和FP-growth 算法n多维关联规则挖掘n相关规则n基于约束的关联规则挖掘n总结39挖掘多种规则或规律n多层(Multi-level),量化(quantitative)关联规则, 相关(correlati

21、on)和因果(causality), 比率(ratio)规则, 序列 (sequential) 模式,浮现(emerging)模式, temporal associations, 局部周期(partial periodicity)n分类(classification),聚类(clustering),冰山立方体( iceberg cubes), 等等.40多层关联规则n项常常构成层次n可伸缩的(flexible)支持度设置: 在较低层的项预期有较低的支持度.n事务数据库可以基于维度和层次编码n探寻共享多层挖掘统一支持度Milksupport = 10%2% Milk support = 6%Sk

22、im Milk support = 4%Level 1min_sup = 5%Level 2min_sup = 5%Level 1min_sup = 5%Level 2min_sup = 3%减少的支持度41可伸缩的支持度约束的多层/多维(ML/MD)关联规则n为什么设置可伸缩的支持度?n实际生活中项的出现频率变化巨大n在一个商店购物篮中的钻石,手表,钢笔n统一的支持度未必是一个有趣的模型n一个可伸缩模型n较低层的,较多维的组合以及长模式通常具有较小的支持度n总体规则应该要容易说明和理解n特殊的项和特殊的项的组合可以特别设定(最小支持度)以及拥有更高的优先级42多维关联规则n单维规则:buys

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

24、则:冗余滤除n根据项之间的”先辈” (ancestor)关系,一些规则可能是冗余的. n示例nmilk wheat bread support = 8%, confidence = 70%n2% milk wheat bread support = 2%, confidence = 72%n我们说第1个规则是第2个规则的先辈.n一个规则是冗余的,当其支持度接近基于先辈规则的”预期”(expected)值.44多层关联规则:逐步深化(Progressive Deepening)n一个自上而下的,逐步深化的方法:n 首先挖掘高层的频繁项: milk (15%), bread (10%)n 然后挖掘

25、它们的较低层”较弱” (weaker)频繁项: 2% milk (5%), wheat bread (4%)n多层之间不同的最小支持度阈值导致了不同的算法:n如果在多个层次间采用了相同的最小支持度,若t的任何一个先辈都是非频繁的则扔弃(toss)t.n如果在较低层采用了减少的最小支持度，则只检验那些先辈的支持度是频繁的不可忽略的派生（descendents）即可45多维关联规则挖掘的技术n搜索频繁 k-谓词集(predicate set):n示例: age, occupation, buys是一个 3-谓词集n以age处理的方式,技术可以如下分类1. 利用数量属性的统计离散(static di

26、scretization)方法 利用预先确定的概念层次对数量属性进行统计离散化2. 量化关联规则n基于数据的分布,数量属性被动态地离散化到不同的容器空间(bins)3. 基于距离(Distance-based)的关联规则n这是一个动态离散化的过程,该过程考虑数据点之间的距离46数量属性的统计离散化n挖掘之前利用概念层次离散化n数值被范围(ranges)替代.n关系数据库中,找出所有的频繁k-谓词(predicate)集要求 k 或 k+1次表扫描.n数据立方体(data cube)非常适合数据挖掘.nN-维立方体的 cells 与谓词集( predicate sets)相对应.n通过数据立方体

27、挖掘会非常快速.(income)(age)()(buys)(age, income)(age,buys) (income,buys)(age,income,buys)47量化关联规则age(X,”30-34”) income(X,”24K - 48K”) buys(X,”high resolution TV”)n数值属性动态离散化n这样挖掘的规则的可信度或紧密度最大化n2-维 量化关联规则: Aquan1 Aquan2 Acatn示例48量化关联规则nARCS: Association Rule Clustering System (关联规则聚类系统) 借鉴了图像处理中的思想. 本质上, 这种

28、方法映射一对数量属性到满足给定的分类属性条件的2-维元组格. 然后对栅格搜索找到聚类点,由其生成关联规则. nARCS 步骤: 装箱(Binning)找出频繁谓词集(predicate sets) 聚类关联规则 49量化关联规则n装箱(Binning): 划分 过程被认为是装箱,即称作间隔为箱柜(bins). 三种常用装箱策略是: Equiwidth binning, where the intervalsize of each bin is the same Equidepth: where each bin has approximately the same number of tupl

29、es assigned to it Homogeneity-based binning, where bin size is determined so that the tuples in each bin are uniformly distributed.50量化关联规则n找出频繁谓词集: Once the 2-D array containing the count distribution for each category is set up, this can be scanned in order to find the frequent predicate sets that

30、 also satisfy minimum confidence.n聚类关联规则: age(X,”34-35”) income(X,”31K - 50K”) buys(X,”high resolution TV”)51ARCS (Association Rules Clustering System)ARCS 1. Binning2. Frequent Items Set3. Clustering4. Optimization52nARCS: n成功的应用聚类的概念到分类中. n但仅限于基于2-维规则的分类,如A B Classi 的格式所示n利用装箱(Binning)方法将数据属性值离散化,

31、因此ACRS的准确度与使用的离散化程度强烈相关. 53内容提要内容提要 n引言nApriori 算法nFrequent-pattern tree 和FP-growth 算法n多维关联规则挖掘n相关规则n基于约束的关联规则挖掘n总结54相关规则(Correlation Rules)n“Beyond Market Baskets,” Brin et al.n假设执行关联规则挖掘tea = coffee20% support80% confidencebut 90% of the people buy coffee anyway!55相关规则n一种度量是计算相关性n若两个随机变量 A 和 B 是统计

32、独立的n对tea 和 coffee:1)()()(BPAPBAP89.0)()()(cPtPctP56相关规则n利用 2 统计检验来测试独立性n设n为购物篮的总数n设k为考虑的项的总数n设 r 为一个包含项 (ij, ij)的规则n设O(r) 表示包含规则r的购物篮的数量 (即频率)n对单个项ij,设 Eij = O(ij) (反过来即为 n - Eij)nEr = n * Er1/n * * Erk / n57相关规则n2 统计量定义为nLook up for significance value in a statistical textbooknThere are k-1 degrees of freedomnIf test fails cannot reject independence, otherwise contigency table represents dependence.RrrErErO)(2258示例nBack to tea and coffeenEt = 25, Et=75, Ec=90, Ec=10nEtc=100 * 25/100 * 90 /100=22.5nO(tc) = 20nContrib. to 2 = (20 - 22.5)2 / 22.5 = 0.278nCalculate for the rest to get 2=2.204nN