商务智能原理与基础之关联规则PPT学习教案

1、会计学1商务智能原理与基础之关联规则商务智能原理与基础之关联规则三三关联规则关联规则1.关联规则简介关联规则简介2.关联规则挖掘方法关联规则挖掘方法3.关联规则兴趣性关联规则兴趣性4.关联规则知识形式扩展关联规则知识形式扩展5.简单关联规则简单关联规则6.小结及练习小结及练习第1页/共57页关联（关联（association）规则规则是当前数据挖掘研究的主是当前数据挖掘研究的主典型的关联规则发现问题是对超市中的货篮数据（Market Basket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。将顾客同时购买的东西，放在比较远的位置，诱导顾客浏览并购买更多的东西。把经

2、常同时购买的商品放在比较靠近的货架上，便于顾客同时购买。第2页/共57页如果我们把商场内的所有如果我们把商场内的所有购买羽毛球拍的顾客通常也购买浴巾，这种关联关系可以用：羽毛球拍=浴巾这样的关联规则来表示，这样的规则在数据库中是否有代表性，重要性及有用性，需要多个步骤来评判。规则中的数据出现的是否足够频繁数据之间的联系是否足够紧密数据之间的联系是否符合其他兴趣性的考虑第3页/共57页n设I=i1, i2, im为所有项目的集合，D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识TID。对于任意非空项集A（A I ），如果记录T包含A，则称记录T支持项集A。如果项集A中包

3、含k个项目，则称其为k项集。苹果，橘子，香蕉，梨，西瓜标识标识TID项目子集项目子集1苹果2橘子，香蕉3梨，西瓜，香蕉橘子梨，香蕉第4页/共57页第5页/共57页第6页/共57页购买记录购买记录TID购买商品购买商品T100旅游鞋，浴巾，MP3T200浴巾，跑步机T300浴巾，羽毛球拍T400旅游鞋，浴巾，跑步机T500旅游鞋，羽毛球拍T600浴巾，羽毛球拍T700旅游鞋，羽毛球拍T800旅游鞋，浴巾，羽毛球拍，MP3T900旅游鞋，浴巾，羽毛球拍第7页/共57页Dsupp（羽毛球拍）=Dsupp（MP3）=Dsupp（旅游鞋，跑步机）=Dsupp（羽毛球拍，浴巾）=假设给定=20%，则上述哪

4、些是频繁集假设给定=20%，=60%，则羽毛球拍=浴巾是否是合格关联规则6/92/91/94/9第8页/共57页n如果指定一对项集X和Y，并且要求验证X=Y在数据集T上是否为一个合格关联规则，那么人们可以直接根据上述定义来计算X=Y的支持度和置信度，并且通过与给定的阈值进行比较来判断。n这与很多模型驱动的方法类似，比如给定一个线性回归模型：Y=a+bX+ ，人们可以通过已经知道的数据来判断模型与数据的符合程度。第9页/共57页频繁项集生成满足最小信任度阈值的规则找出所有频繁项集。这项工作极具挑战性。发现关联规则需要经历两个步骤规则的生成过程存在两个大问题规则数量问题规则质量问题第10页/共57

5、页三三关联规则关联规则1.关联规则简介关联规则简介2.关联规则挖掘方法关联规则挖掘方法3.关联规则兴趣性关联规则兴趣性4.关联规则知识形式扩展关联规则知识形式扩展5.简单关联规则简单关联规则6.小结及练习小结及练习第11页/共57页第12页/共57页第13页/共57页第14页/共57页Apriori方法是基于上述思方法是基于上述思第15页/共57页kkL第16页/共57页Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E

6、3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E2第17页/共57页顾客编号顾客编号数据项数据项女：A男：B青年：C老年：DIphone：ENokia：F11111211113111411151116111711118111911110111第18页/共57页1-itemsetssupport2-itemsetssupport3-itemset

7、ssupportA60%AB0ACF40%B40%AC40%C60%AD20%D40%AE30%E70%AF50%F60%BC20%BD20%BE40%BF10%CD0CE30%CF50%DE40%DF10%EF30%第19页/共57页ACAFCFDERulesConfRulesConfRulesConfRulesConfA=C4/6A=F5/6C=F5/6D=E1C=A4/6F=A5/6F=C5/6E=D4/6ACFRulesConfRulesConfRulesConfA=CF4/6C=AF4/6F=AC4/6AC=F1AF=C4/5CF=A4/5第20页/共57页多次扫描数据库：Ck中的项

8、集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库所挖掘的规则存在大量冗余：算法一定要等到扫描完整个数据库后才做结合,因为在扫描的过程中,有些候选项集在若干的区段中的支持度已大于等于使用者制定的最小支持度,因此在扫描这些若干个区段后,便可以找出频集,并直接结合产生下一个层级的候选物项集第21页/共57页编号编号算法算法内容内容1Apriori-Tid，Apriori-Hybrid，Hash树DHP算法在频繁项集合生成过程中，对冗余项集合进行剪枝2

9、DIC，Eclat，MacEclat，Clique，MaxClique通过减少对数据库的扫描来提高效率3SETM，MONET从关系数据库操作角度出发，开发出基于关系数据库操作的算法4基于分区操作和基于随即的分区算法5基于采样的算法6并行算法和分布算法第22页/共57页三三关联规则关联规则1.关联规则简介关联规则简介2.关联规则挖掘方法关联规则挖掘方法3.关联规则兴趣性关联规则兴趣性4.关联规则知识形式扩展关联规则知识形式扩展5.简单关联规则简单关联规则6.小结及练习小结及练习第23页/共57页关联规则的应用越来越广关联规则的应用越来越广泛，在很多行业都体现出泛，在很多行业都体现出用户主观层面用

10、户主观层面系统客观层面系统客观层面第24页/共57页（1）系统客观层面：大多）系统客观层面：大多数算法都使用支持度数算法都使用支持度-置信置信购买咖啡和牛奶的统计表（购买咖啡和牛奶的统计表（%）mc20525705759010100第25页/共57页第26页/共57页第27页/共57页第28页/共57页第29页/共57页第30页/共57页第31页/共57页名称名称描述描述公式公式支持度SA和B同时出现概率P(AB）置信度C在A出现的前提下，B出现的概率P(B/A)B出现的概率P(B)作用度L置信度与期望可信度比值P(B/A)/P(B)第32页/共57页第第4 个阈值个阈值影响影响显著性差异(s

11、ignificance level)，是一个统计学名词。它是统计学上对数据差异性的评价。当数据之间具有了显著性差异，就说明参与比对的数据不是来自于同一总体（Population），而是来自于具有差异的两个不同总体。我们说A、B两数据在0.05水平上具备显著性差异，这是说两组数据具备显著性差异的可能性为95%。第33页/共57页第34页/共57页支持度、置信度、作用度支持度、置信度、作用度兴趣性在发现关联兴趣性在发现关联规则知识中起到的规则知识中起到的作用作用减少冗余规则，精减少冗余规则，精简关联规则集合简关联规则集合避免前提和结论相避免前提和结论相关的频繁规则关的频繁规则避免对背景知识的避免对

12、背景知识的重复，突出新的规重复，突出新的规则则凸显有价值的例外凸显有价值的例外规则规则筛选出用户所关心筛选出用户所关心的规则，屏蔽用户的规则，屏蔽用户所不关心的规则所不关心的规则提高关联规则挖掘提高关联规则挖掘的效率的效率123456第35页/共57页（2）用户主观层面：系）用户主观层面：系数数据据约约束束维维/层约层约束束规则约规则约束束1指定任务相关的数据集1232指定所用的维或概念分层的层3指定要挖掘的关联规则的形式注：由于每个用户的知识水平和知识背景不同，即使对于同一数据集，用户给定的约束也会不尽相同，而且对挖掘到的同样的一条关联规则，感兴趣的程度也会不同。因此，主观层面上的度量方法有

13、很大的随机性，它只适合某一特定的领域或特定的背景下，不具有普遍性。第36页/共57页三三关联规则关联规则1.关联规则简介关联规则简介2.关联规则挖掘方法关联规则挖掘方法3.关联规则兴趣性关联规则兴趣性4.关联规则知识形式扩展关联规则知识形式扩展5.简单关联规则简单关联规则6.小结及练习小结及练习第37页/共57页广义关联规则数量关联规则在实际应用中，人们经常会遇到需在实际应用中，人们经常会遇到需要扩展或丰富布尔关联规则语义情要扩展或丰富布尔关联规则语义情形形第38页/共57页广义关联规则：包含高层广义关联规则：包含高层数据间关系的关联规则成数据间关系的关联规则成获得并利用层次结构信息对于决策分

14、析是有意义的1、高层数据关联反映了有意义的知识内涵，比如“羽毛球拍”属于“运动器械类”，“MP3”属于“电子产品类”，“运动器械=电子产品”对管理决策有用2、一些在底层数据间不显著的关联模式，可能在高层数据间显著。比如“羽毛球拍=MP3”和“起跑器=数字摄像机”不一定足够频繁，但是他们的超类层面（运动器械=电子产品）可能是频繁的。扩展关联规则知识表达的形式和语义不仅能够描述层次结构中最低层数据项之间的关联，而且还能够描述层次中高数据类之间的关联。第39页/共57页一个直接用一个直接用Apriori方法挖方法挖某数码店销售笔记本电脑、打印机和数码相机三种产品：某数码店销售笔记本电脑、打印机和数码

15、相机三种产品：笔记本电脑：笔记本电脑：DELL D6DELL D6，Sony S3Sony S3，Sony T7Sony T7打印机：打印机：HP1010HP1010，HP4300HP4300，Canon LBP5200Canon LBP5200数码相机：数码相机：Canon EOS-7DCanon EOS-7D， Canon Ixus700Canon Ixus700，Sony DSC-V3Sony DSC-V3第40页/共57页TID顾客顾客产品产品1张三DELL D6，HP 10102李四DELL D6，Canon LBP5200，Sony DSC-V33张三Sony S3，Canon L

16、BP52004王五DELL D6，HP43005李四Sony T7，Canon LBP52006王五Canon LBP52007李四HP1010，HP4300，Canon EOS-7D8李四Canon Ixus7009张三Canon EOS-7D，Sony DSC-V310王五Canon Ixus700笔记本电脑打印机数码相机第41页/共57页笔记本电脑DELL笔记本电脑SONY笔记本电脑DELL D6Sony S3Sony T7打印机Canon打印机HP打印机Canon LBP5200HP 4300HP 1010数码相机Sony数码相机Canon数码相机Sony DSC-V3Canon EO

17、S-7DCanon Ixus700第42页/共57页1-itemsets支持度支持度2-itemsets支持度支持度DELL D60.3DELL D6 ，打印机0.3Canon LBP52000.4Canon LBP5200，笔记本电脑0.3DELLDELL笔记本电脑笔记本电脑0.3DELLDELL笔记本电脑笔记本电脑，打印机0.3笔记本电脑0.5笔记本电脑，CanonCanon打印机打印机0.3CanonCanon打印机打印机0.4笔记本电脑，打印机0.5HPHP打印机打印机0.3打印机0.7CanonCanon数码相机数码相机0.4数码相机0.5规则规则支持度支持度置信度置信度DELL D

18、6=打印机0.31DELLDELL笔记本电脑笔记本电脑=打印机0.31笔记本电脑=打印机0.51第43页/共57页第44页/共57页数量关联规则：在实际中，数量关联规则：在实际中，碰到的数据通常是类别数碰到的数据通常是类别数显然，数据划分的结构对数据挖掘的结果又很大的影响，因此，设计和选择合适的离散化方法是人们研究和应用的课题。第45页/共57页三三关联规则关联规则1.关联规则简介关联规则简介2.关联规则挖掘方法关联规则挖掘方法3.关联规则兴趣性关联规则兴趣性4.关联规则知识形式扩展关联规则知识形式扩展5.简单关联规则简单关联规则6.小结及练习小结及练习第46页/共57页第47页/共57页第48页/共57页第49页/共57页第50页/共57页TID数据项数据项1A D2B E3A B D E4B D E5B C D E6A B E7A B C D E第51页/共57页规则规则代码代码关联规则关联规则DsuppDconf1A=B3/775%2A=D3/775%3A=E3/775%4B=D4/766.7%5D=B4/780%6B=E6/7100%7E=B6/7100%8D=E4/780%9E=D4/766.7%10AB=E3/7100%规则规则代码代码关联规则关联规则DsuppDconf11AE=B3/7100%12BD=E4/7100%13BE=D4/766.7%