商务智能原理与基础之关联规则

商务智能原理与方法2021/5/5版权所有，不得翻印第0页目录一．引言二．商务智能过程三．数据仓库四．商务智能应用五．构建商务智能环境六．关联规则七．分类分析八．聚类分析九．概念描述商务智能原理与方法2021/5/5版权所有，不得翻印第1页三．关联规则1.关联规则简介2.关联规则挖掘方法3.关联规则兴趣性4.关联规则知识形式扩展5.简单关联规则6.小结及练习目录商务智能原理与方法2021/5/5版权所有，不得翻印第2页关联（association）规则是当前数据挖掘研究的主要方法之一，它反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到典型的关联规则发现问题是对超市中的货篮数据（MarketBasket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。将顾客同时购买的东西，放在比较远的位置，诱导顾客浏览并购买更多的东西。把经常同时购买的商品放在比较靠近的货架上，便于顾客同时购买。商务智能原理与方法2021/5/5版权所有，不得翻印第3页如果我们把商场内的所有商品设置为一个集合，每个商品就是一个数据项（item）。商场的交易数据库通常包含每个顾客每一次购买的商品记录。关联规则表达的就是商品间联动购买的情况购买羽毛球拍的顾客通常也购买浴巾，这种关联关系可以用：羽毛球拍=浴巾这样的关联规则来表示，这样的规则在数据库中是否有代表性，重要性及有用性，需要多个步骤来评判。规则中的数据出现的是否足够频繁数据之间的联系是否足够紧密数据之间的联系是否符合其他兴趣性的考虑……商务智能原理与方法2021/5/5版权所有，不得翻印第4页关联规则的基本概念(1)设I={i1,i2,…,im}为所有项目的集合，D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识TID。对于任意非空项集A（AI），如果记录T包含A，则称记录T支持项集A。如果项集A中包含k个项目，则称其为k项集。苹果，橘子，香蕉，梨，西瓜标识TID项目子集1苹果2橘子，香蕉3梨，西瓜，香蕉橘子梨，香蕉商务智能原理与方法2021/5/5版权所有，不得翻印第5页关联规则的基本概念(2)商务智能原理与方法2021/5/5版权所有，不得翻印第6页关联规则的基本概念(3)商务智能原理与方法2021/5/5版权所有，不得翻印第7页案例：商场记录顾客购买商品的数据，假设有数据库D，数据集合I={MP3，羽毛球拍，旅游鞋，浴巾，跑步机}购买记录TID购买商品T100旅游鞋，浴巾，MP3T200浴巾，跑步机T300浴巾，羽毛球拍T400旅游鞋，浴巾，跑步机T500旅游鞋，羽毛球拍T600浴巾，羽毛球拍T700旅游鞋，羽毛球拍T800旅游鞋，浴巾，羽毛球拍，MP3T900旅游鞋，浴巾，羽毛球拍商务智能原理与方法2021/5/5版权所有，不得翻印第8页案例计算Dsupp（{羽毛球拍}）=Dsupp（{MP3}）=Dsupp（{旅游鞋，跑步机}）=Dsupp（{羽毛球拍，浴巾}）=假设给定α=20%，则上述哪些是频繁集假设给定α=20%，β=60%，则羽毛球拍=浴巾是否是合格关联规则6/92/91/94/9商务智能原理与方法2021/5/5版权所有，不得翻印第9页案例总结如果指定一对项集X和Y，并且要求验证X=Y在数据集T上是否为一个合格关联规则，那么人们可以直接根据上述定义来计算X=Y的支持度和置信度，并且通过与给定的阈值进行比较来判断。这与很多模型驱动的方法类似，比如给定一个线性回归模型：Y=a+bX+ε，人们可以通过已经知道的数据来判断模型与数据的符合程度。商务智能原理与方法2021/5/5版权所有，不得翻印第10页发现关联规则需要经历两个步骤，每一个步骤都对应规则生成过程中两大问题种的一个频繁项集生成满足最小信任度阈值的规则找出所有频繁项集。这项工作极具挑战性。发现关联规则需要经历两个步骤规则的生成过程存在两个大问题规则数量问题规则质量问题商务智能原理与方法2021/5/5版权所有，不得翻印第11页三．关联规则1.关联规则简介2.关联规则挖掘方法3.关联规则兴趣性4.关联规则知识形式扩展5.简单关联规则6.小结及练习目录商务智能原理与方法2021/5/5版权所有，不得翻印第12页支持度和置信度是评估关联规则的两个基本测度，进一步讨论关联规则在这两个测度上的性质对于关联规则的挖掘和应用很有意义（1）首先由于Dsupp（X=Y）=Dsupp（XY），我们可知道计算规则X=Y的支持度就等于计算项集XY的支持度。此外，由于Dconf（X=Y）=||X∪Y||/||X||=（||X∪Y||/|T|)/(||X||/|T|)=Dsupp（XY）/Dsupp（X），我们知道X=Y的置信度的计算可以通过XY和X的支持度得到。这样一个挖掘思路就是通过扫描数据库，先计算所有项集的支持度，而后通过支持度计算置信度，而不需要对数据库再次扫描。商务智能原理与方法2021/5/5版权所有，不得翻印第13页进一步讨论关联规则（2）商务智能原理与方法2021/5/5版权所有，不得翻印第14页进一步讨论关联规则（3）据此可知，我们计算项集支持度的过程中，可以采用逐层扩展方式，即：先计算1项集，再计算2项集……（m-1）项集。当计算k项集支持度的时候（2≤k≤m-1），只需要考虑哪些其子集是频繁集的k项集，而不必考虑包含非频繁子集的k项集，这样可以优化计算。这里，我们把计算获得项集支持度的过程称为生成（候选）项集的过程，把计算出由频繁子集组成的项集的支持度的过程称为生成候选频繁集的过程。商务智能原理与方法2021/5/5版权所有，不得翻印第15页Apriori方法是基于上述思路的关联规则挖掘的经典方法，它是一种基于逐层搜索的迭代算法，从k项集生成满足规则的k+1项集。Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。Apriori算法将发现关联规则的过程分为两个步骤：通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；利用频繁项集构造出满足用户最小信任度的规则。挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。商务智能原理与方法2021/5/5版权所有，不得翻印第16页Apriori算法：变量说明（Ck：k-候选项集；Lk：k-频繁项集；minsup：最小支持度阈值）kkL商务智能原理与方法2021/5/5版权所有，不得翻印第17页实例（最小支持度50%）DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2商务智能原理与方法2021/5/5版权所有，不得翻印第18页案例：某电子商城的购物记录，经理很希望知道什么样的顾客购买了什么样的手机，购买了某种手机是否还会购买另一种手机（设定α=40%，β=100%）顾客编号数据项女：A男：B青年：C老年：DIphone：ENokia：F11111211113111411151116111711118111911110111商务智能原理与方法2021/5/5版权所有，不得翻印第19页客户手机频繁集1-itemsetssupport2-itemsetssupport3-itemsetssupportA60%AB0ACF40%B40%AC40%C60%AD20%D40%AE30%E70%AF50%F60%BC20%BD20%BE40%BF10%CD0CE30%CF50%DE40%DF10%EF30%商务智能原理与方法2021/5/5版权所有，不得翻印第20页客户手机的关联规则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商务智能原理与方法2021/5/5版权所有，不得翻印第21页Apriori算法的不足多次扫描数据库：Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库所挖掘的规则存在大量冗余：算法一定要等到扫描完整个数据库后才做结合,因为在扫描的过程中,有些候选项集在若干的区段中的支持度已大于等于使用者制定的最小支持度,因此在扫描这些若干个区段后,便可以找出频集,并直接结合产生下一个层级的候选物项集商务智能原理与方法2021/5/5版权所有，不得翻印第22页Apriori方法被认为是一个有效的经典的关联规则挖掘方法。对Apriori方法的进一步优化还可以从下列角度展开。编号算法内容1Apriori-Tid，Apriori-Hybrid，Hash树DHP算法在频繁项集合生成过程中，对冗余项集合进行剪枝2DIC，Eclat，MacEclat，Clique，MaxClique通过减少对数据库的扫描来提高效率3SETM，MONET从关系数据库操作角度出发，开发出基于关系数据库操作的算法4基于分区操作和基于随即的分区算法5基于采样的算法6并行算法和分布算法商务智能原理与方法2021/5/5版权所有，不得翻印第23页三．关联规则1.关联规则简介2.关联规则挖掘方法3.关联规则兴趣性4.关联规则知识形式扩展5.简单关联规则6.小结及练习目录商务智能原理与方法2021/5/5版权所有，不得翻印第24页关联规则的应用越来越广泛，在很多行业都体现出了重要性。但是用户怎么知道从挖掘系统得到的结果就是他们想要的，就是对他们有价值的结果呢？怎样来评价一个规则是否有价值呢？主要从两个层面来评价用户主观层面系统客观层面商务智能原理与方法2021/5/5版权所有，不得翻印第25页（1）系统客观层面：大多数算法都使用支持度-置信度的框架。这样的结构并不能保证产生的关联规则是完全正确的。规则的置信度有一定的欺骗性，它只表示了规则前件和后件的条件概率估计，并没有度量项目之间蕴涵的实际强度购买咖啡和牛奶的统计表（%）mc20525705759010100商务智能原理与方法2021/5/5版权所有，不得翻印第26页案例分析计算Coffee=milk，S=20/100=20%,C=(c∪m)/c=20/25=80%,当我们把可信度和支持度阈值定为低于0.8和0.2时,很显然该规则将会作为目标规则之一被采掘出来.由此我们得出结论,刺激顾客对咖啡的购买欲望将增加奶粉的销售量,或换句话说,将咖啡和奶粉放在一起将提高奶粉的销售量.商务智能原理与方法2021/5/5版权所有，不得翻印第27页案例分析计算商务智能原理与方法2021/5/5版权所有，不得翻印第28页案例分析计算于是我们可以得出结论,在考虑了反面示例的影响之后,问题出现了.并非采掘出的规则可信度或支持度不高,但一条即使可信度和支持度都很高的规则其实际利用价值已经难以肯定了，在此我们提出一个解决的办法,引入第3个阈值——兴趣度.商务智能原理与方法2021/5/5版权所有，不得翻印第29页期望可信度描述了在没有任何条件影响时，项集B在所有事务中出现的概率有多大。如果某天