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

1、商务智能原理与方法参考文档,2020年12月20日,机 密,目 录,引言 商务智能过程 数据仓库 商务智能应用 构建商务智能环境 关联规则 分类分析 聚类分析 概念描述,关联规则 关联规则简介 关联规则挖掘方法 关联规则兴趣性 关联规则知识形式扩展 简单关联规则 小结及练习,目 录,关联（association）规则是当前数据挖掘研究的主要方法之一，它反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到,典型的关联规则发现问题是对超市中的货篮数据（Market Basket）进行分析。通过发现顾客放入货篮中的不同

2、商品之间的关系来分析顾客的购买习惯。,将顾客同时购买的东西，放在比较远的位置，诱导顾客浏览并购买更多的东西。,把经常同时购买的商品放在比较靠近的货架上，便于顾客同时购买。,如果我们把商场内的所有商品设置为一个集合，每个商品就是一个数据项（item）。商场的交易数据库通常包含每个顾客每一次购买的商品记录。关联规则表达的就是商品间联动购买的情况,购买羽毛球拍的顾客通常也购买浴巾，这种关联关系可以用：羽毛球拍=浴巾这样的关联规则来表示，这样的规则在数据库中是否有代表性，重要性及有用性，需要多个步骤来评判。,规则中的数据出现的是否足够频繁,数据之间的联系是否足够紧密,数据之间的联系是否符合其他兴趣性的

3、考虑,关联规则的基本概念(1),设I=i1, i2, im为所有项目的集合，D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识TID。对于任意非空项集A（A I ），如果记录T包含A，则称记录T支持项集A。如果项集A中包含k个项目，则称其为k项集。,苹果，橘子，香蕉，梨，西瓜,橘子,梨，香蕉,关联规则的基本概念(2),关联规则的基本概念(3),案例：商场记录顾客购买商品的数据，假设有数据库D，数据集合I=MP3，羽毛球拍，旅游鞋，浴巾，跑步机,案例计算,6/9,2/9,1/9,4/9,案例总结,如果指定一对项集X和Y，并且要求验证X=Y在数据集T上是否为一个合格关联规则

4、，那么人们可以直接根据上述定义来计算X=Y的支持度和置信度，并且通过与给定的阈值进行比较来判断。 这与很多模型驱动的方法类似，比如给定一个线性回归模型：Y=a+bX+ ，人们可以通过已经知道的数据来判断模型与数据的符合程度。,发现关联规则需要经历两个步骤，每一个步骤都对应规则生成过程中两大问题种的一个,频繁项集生成满足最小信任度阈值的规则,找出所有频繁项集。这项工作极具挑战性。,发现关联规则需要经历两个步骤,规则的生成过程存在两个大问题,规则数量问题,规则质量问题,关联规则 关联规则简介 关联规则挖掘方法 关联规则兴趣性 关联规则知识形式扩展 简单关联规则 小结及练习,目 录,支持度和置信度是

5、评估关联规则的两个基本测度，进一步讨论关联规则在这两个测度上的性质对于关联规则的挖掘和应用很有意义（1）,首先由于Dsupp（ X=Y ）=Dsupp（XY），我们可知道计算规则X=Y的支持度就等于计算项集XY的支持度。 此外，由于Dconf（ X=Y ）=|XY| / |X|=（|XY| /|T|)/ (|X|/|T|)= Dsupp（XY）/ Dsupp（X），我们知道X=Y 的置信度的计算可以通过XY和X的支持度得到。 这样一个挖掘思路就是通过扫描数据库，先计算所有项集的支持度，而后通过支持度计算置信度，而不需要对数据库再次扫描。,进一步讨论关联规则（2）,进一步讨论关联规则（3）,据此

6、可知，我们计算项集支持度的过程中，可以采用逐层扩展方式，即：先计算1项集，再计算2项集（m-1）项集。当计算k项集支持度的时候（2km-1），只需要考虑哪些其子集是频繁集的k项集，而不必考虑包含非频繁子集的k项集，这样可以优化计算。 这里，我们把计算获得项集支持度的过程称为生成（候选）项集的过程，把计算出由频繁子集组成的项集的支持度的过程称为生成候选频繁集的过程。,Apriori方法是基于上述思路的关联规则挖掘的经典方法，它是一种基于逐层搜索的迭代算法，从k项集生成满足规则的k+1项集。Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。,Apriori算法将发现关联规则

7、的过程分为两个步骤： 通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集； 利用频繁项集构造出满足用户最小信任度的规则。 挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。,Apriori算法：变量说明（Ck：k-候选项集；Lk：k-频繁项集；minsup：最小支持度阈值）,实例（最小支持度50%）,Database TDB,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3,3rd scan,案例：某电子商城的购物记录，经理很希望知道什么样的顾客购买了什么样的手机，购买了某种手机是否还会购买另一种手机（设定=40%，=100%

8、）,客户手机频繁集,客户手机的关联规则,Apriori算法的不足,多次扫描数据库：Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库,所挖掘的规则存在大量冗余：算法一定要等到扫描完整个数据库后才做结合,因为在扫描的过程中,有些候选项集在若干的区段中的支持度已大于等于使用者制定的最小支持度,因此在扫描这些若干个区段后,便可以找出频集,并直接结合产生下一个层级的候选物项集,Apriori方法被认为是一个有效的经典的关联规则挖掘方法。对Apr

9、iori方法的进一步优化还可以从下列角度展开。,关联规则 关联规则简介 关联规则挖掘方法 关联规则兴趣性 关联规则知识形式扩展 简单关联规则 小结及练习,目 录,关联规则的应用越来越广泛，在很多行业都体现出了重要性。但是用户怎么知道从挖掘系统得到的结果就是他们想要的，就是对他们有价值的结果呢？怎样来评价一个规则是否有价值呢？主要从两个层面来评价,用户主观层面,系统客观层面,（1）系统客观层面：大多数算法都使用支持度-置信度的框架。这样的结构并不能保证产生的关联规则是完全正确的。规则的置信度有一定的欺骗性，它只表示了规则前件和后件的条件概率估计，并没有度量项目之间蕴涵的实际强度,案例分析计算,C

10、offee=milk，S=20/100=20%,C=(cm)/c=20/25=80%,当我们把可信度和支持度阈值定为低于0. 8 和0. 2 时,很显然该规则将会作为目标规则之一被采掘出来. 由此我们得出结论, 刺激顾客对咖啡的购买欲望将增加奶粉的销售量, 或换句话说, 将咖啡和奶粉放在一起将提高奶粉的销售量.,案例分析计算,案例分析计算,于是我们可以得出结论, 在考虑了反面示例的影响之后, 问题出现了. 并非采掘出的规则可信度或支持度不高, 但一条即使可信度和支持度都很高的规则其实际利用价值已经难以肯定了， 在此我们提出一个解决的办法, 引入第3 个阈值兴趣度.,期望可信度描述了在没有任何条

11、件影响时，项集B在所有事务中出现的概率有多大。如果某天共有1000个顾客到商场购买商品，其中有200个顾客购买了冰箱，则上述的关联规则的期望可信度就是20%。,第3 个阈值-作用度(提升度、兴趣度)：Lift,是置信度与期望可信度的比值。作用度描述项集A的出现对项集B的出现有多大的影响,作用度的计算及结果解释,在上例中，如果购买微波炉的顾客70%也购买冰箱，则作用度就是 70%/20%=3.5 当Lift1时，规则的前项与后项正相关，有兴趣 当Lift=1时，规则的前项与后项无相关，无兴趣 当Lift1时，规则的前项与后项负相关，无兴趣,用P(A)表示事务中出现项集A的概率， 以上四个参数可用

12、如下公式表示,第4 个阈值影响度:Influence ,关联规则X=Y影响度表示规则前项X和后项Y的的相关程度,influence影响度是将T检验的思想引入到关联规则中而成的,显著性差异(significance level)，是一个统计学名词。它是统计学上对数据差异性的评价。当数据之间具有了显著性差异，就说明参与比对的数据不是来自于同一总体（Population），而是来自于具有差异的两个不同总体。我们说A、B两数据在0.05水平上具备显著性差异，这是说两组数据具备显著性差异的可能性为95%。,第4 个阈值影响度:Influence,支持度、置信度、作用度以及影响度都是兴趣性测度的内容。兴趣

13、性测度的应用旨在帮助提升关联规则的品质，并也可以应用到算法优化的过程中帮助提升计算效率,兴趣性在发现关联规则知识中起到的作用,减少冗余规则，精简关联规则集合,避免前提和结论相关的频繁规则,避免对背景知识的重复，突出新的规则,凸显有价值的例外规则,筛选出用户所关心的规则，屏蔽用户所不关心的规则,提高关联规则挖掘的效率,1,2,3,4,5,6,（2）用户主观层面：系统客观层面只是挖掘潜在有趣的关联规则，真正有趣的关联规则要由用户来决定，只有用户可以决定规则的有效性、可行性，因此在挖掘数据时，引入约束,1,指定任务相关的数据集,1,2,3,2,指定所用的维或概念分层的层,3,指定要挖掘的关联规则的形

14、式,注：由于每个用户的知识水平和知识背景不同，即使对于同一数据集，用户给定的约束也会不尽相同，而且对挖掘到的同样的一条关联规则，感兴趣的程度也会不同。因此，主观层面上的度量方法有很大的随机性，它只适合某一特定的领域或特定的背景下，不具有普遍性。,关联规则 关联规则简介 关联规则挖掘方法 关联规则兴趣性 关联规则知识形式扩展 简单关联规则 小结及练习,目 录,广义关联规则,数量关联规则,在实际应用中，人们经常会遇到需要扩展或丰富布尔关联规则语义情形,广义关联规则：包含高层数据间关系的关联规则成为广义关联规则。对于一些实际应用问题，人们发现在数据之间可能存在一定的关系，比如超市中的商品目录和类别划

15、分所构成的反应超类和子类的隶属关系（层次关系）,获得并利用层次结构信息对于决策分析是有意义的,1、高层数据关联反映了有意义的知识内涵，比如“羽毛球拍”属于“运动器械类”，“MP3”属于“电子产品类”，“运动器械=电子产品”对管理决策有用,2、一些在底层数据间不显著的关联模式，可能在高层数据间显著。比如“羽毛球拍=MP3”和“起跑器=数字摄像机”不一定足够频繁，但是他们的超类层面（运动器械=电子产品）可能是频繁的。,扩展关联规则知识表达的形式和语义不仅能够描述层次结构中最低层数据项之间的关联，而且还能够描述层次中高数据类之间的关联。,一个直接用Apriori方法挖掘广义关联规则的做法是转换数据。

16、基本思路是将此次结构的所有高层数据（超类）也作为数据项放入数据库中。例题详解如下：,某数码店销售笔记本电脑、打印机和数码相机三种产品： 笔记本电脑：DELL D6，Sony S3，Sony T7 打印机：HP1010，HP4300，Canon LBP5200 数码相机：Canon EOS-7D， Canon Ixus700，Sony DSC-V3,数码店销售记录,笔记本电脑,打印机,数码相机,数码产品的层次结构,如果设定的最小支持度为30%，最小置信度为100%，则合格的关联规则有：,在广义关联规则的挖掘中，可以引入一些性质或兴趣性测度来进行剪枝和过滤低质量的规则,超类和其所属子类之间的关联没

17、有意义：MP3=电子产品 另外子类/超类之间的关系也会造成一定的冗余： 比如：“DELL笔记本电脑=打印机”和“笔记本电脑=打印机”。我们知道笔记本电脑中有60%是DELL笔记本电脑，所以上述两个规则并没带来什么特别不同于“平均期望”的信息（即Dsupp（笔记本电脑=打印机）X0.6=0.3），规则“DELL笔记本电脑=打印机”可以剔除。,数量关联规则：在实际中，碰到的数据通常是类别数据或数值数据，如商品的数量、家庭的收入和客户的年龄等，这些数据属性分别成为多值属性和连续属性。基于多值和连续属性的关联规则称为数量关联规则,我们考虑的超市问题，我们以往只考虑“是否购买”的问题，而没有考虑“购买多

18、少”的问题。基于Apriori算法挖掘数量关联规则的一个方法是进行数据转换。采用离散化的方法划分连续属性的值域。将每一个离散化得到的区间属性（如年龄30,50）作为一个新属性，并且将原数据值在此区间上的匹配结构形成一个相应的布尔真值。比如，如果原纪录t年龄为45，我们划定的年龄属性30,50为布尔值1，那么t的布尔值就为1；如果原记录年龄t为25，则其布尔值为0. 通常一个数量关联规则知识形式的例子为：水果15KG=饮料212L,显然，数据划分的结构对数据挖掘的结果又很大的影响，因此，设计和选择合适的离散化方法是人们研究和应用的课题。,关联规则 关联规则简介 关联规则挖掘方法 关联规则兴趣性 关联规则知识形式扩展 简单关联规则 小结及练习,目 录,简单关联规则：即规则后项为单个数据项的关联规则,合格关联规则：满足给定支持度阈值和置信度阈值的关联规则叫做合格关联规则。 把已知数据集挖掘出来的所有合格关联规则的集合记为：=X=Y|Dsupp(X=Y)，Dc