商务智能原理与方法（第3版）-课件 Lecture3-Association Rule

数据挖掘——关联分析关联分析关联规则（AR，AssociationRule）商务智能领域中最基本的一种关联知识形式反映一种特定的数据之间的联系购物篮分析应用交叉销售分析金融证券联动网络连接分析产品购买推荐客户关系维护啤酒vs尿布啤酒与尿布一起出售，为什么？啤酒消费者大多为男性->爱看电视体育节目->不愿被精彩的比赛打断->减少上厕所次数->所以。。。关联规则很容易理解，但它不是万能的几类关联规则

——可操作的规则沃尔玛商场中购买芭比娃娃的客户有60%的可能性也购买三种类型的糖果中的一种芭比喜欢吃巧克力棒？妈妈为孩子选购生日礼物很累，需要补充能量？妈妈带着孩子买芭比，孩子喜欢巧克力棒？可操作的规则模式被发现后，可推到出一些见解和操作几类关联规则

——平凡的规则购买维修协议的客户很可能会购买大型设备为什么会单独购买维修协议呢？经常同时购买购买油漆的客户也购买刷子汉堡包和面包几乎100%正确，复制以前营销活动的成功平凡规则几类关联规则

——费解的规则当一个新的五金店开张时，马桶清洁剂是销售最好的产品之一新开张的五金店通常位于新的居住区附近->新家的主人需要囤积马桶清洁剂费解的规则不能给出营销的建议几类关联规则当运用关联规则进行购物篮分析时许多结果是平凡的或费解的平凡的规则再现了营销中的常识费解的规则不能提供可操作的建议非常少量的结果是可操作的规则啤酒vs尿布但是值得挖掘将啤酒与尿布放在一起将啤酒与尿布放在很远的地方羽毛球拍vs浴巾，休闲服装，护肤用品等关联规则简介商场所有商品作为一个集合每个商品是一个数据项（item）商场交易数据库记录每个顾客每一次购买的商品记录关联规则表达商品间联动购买的情况羽毛球拍->浴巾关联规则评判一条规则在数据库中是否具有代表性支持度一条规则的重要性置信度一条规则的有用性兴趣度关联规则的支持度m个不同数据项组成的一个集合I={I1,I2,…Im}对于一个非空的项集(itemset)X，X属于I有多少消费者同时购买X和Y每个事务记录t是I的一个非空子集，具有唯一的标TID(TransactionID)，所有事物集合T={t1,t2,…tn}如果记录t包含X，则称记录t支持X所有支持X的记录构成集合TX，则项集X的支持度为关联规则的支持度频繁项集XXY如果||X||=k，则称X为k-项集关联规则的支持度若X的支持度大于给定的最小支持度阈值

X与Y不相交关联规则左侧的项集叫做前项(antecedent)关联规则右侧的项集叫做后项(consequent)Dsupp(X

Y)=Dsupp(X∪Y)0≤Dsupp(X

Y)≤1关联规则置信度购买X的消费者中有多少购买Y关联规则X

Y的置信度度量一条规则的重要性0≤Dconf(X

Y)≤1合格的关联规则如果Dsupp(X

Y)≥

，且Dconf(X

Y)≥

则称关联规则X

Y是关于

,

合格的合格的关联规则给定最小支持度

和最小置信度

,

[0,1]一个合格关联规则X

Y的含义为关于X和Y的事件同时发生的频率足够高（≥

）在事件X发生的情况下，事件Y与之同时发生的频率足够高（≥

）关联规则示例数据项集合={MP3，羽毛球拍，旅游鞋，浴巾，跑步机}。判断“羽毛球拍

浴巾”是否为合格的关联规则某商场记录了大量客户购买商品的数据。假设已采集到购买交易数据集T。T中包含9条记录，分别记载了9次购买事件中所购买的商品名称。给定

＝20%,

=60%关联规则示例购买记录TID购

买

商

品T100旅游鞋，浴巾，MP3T200浴巾，跑步机T300浴巾，羽毛球拍T400旅游鞋，浴巾，跑步机T500旅游鞋，羽毛球拍T600浴巾，羽毛球拍T700旅游鞋，羽毛球拍T800旅游鞋，浴巾，羽毛球拍，MP3T900旅游鞋，浴巾，羽毛球拍关联规则挖掘的意义指定一对项集X和Y，验证X

Y是否为合格关联规则计算支持度和置信度（数据驱动）线性回归模型Y＝a+bX+

（模型驱动）挖掘的意义哪些数据项之间存在着关联人们事先不知道或无法事先假设用户需要找出所有可能的合格关联关联规则挖掘的复杂度大数据（海量数据）数据项（或数据属性）的数目m（即|I|）数据集中记录的数目n（即|T|）n可能数百万或更大扫描数据库这些数据一般都储存在外存设备上关联规则的数目巨大课堂练习数据库中存储的数据项的数目m计算所有项集的数目2m计算关联规则的总数目O(3m)课堂练习关联规则总数目为T上述两式相加关联规则挖掘方法给定事务数据集合T，最小支持度

和最小置信度

找出所有满足合格关联规则？关联规则挖掘方法计算思路Dsupp(X

Y)=Dsupp(XY)计算规则X

Y的支持度就等于计算项集XY的支持度Dconf(X

Y)=||TXY||/||TX||=(||TXY||/||T||)/(||TX||/||T||)=Dsupp(XY)/Dsupp(X)X

Y置信度可以基于项集XY和X的支持度进一步计算得到先计算所有项集的支持度，扫描数据集利用项集的支持度信息直接计算置信度不必扫描数据集下闭合性质所有项集的个数是2m

1（除去空集）计算一个项集的支持度至少需要遍历扫描一次数据库下闭合性质Dsupp(X)≥Dsupp(XY)≥

如果一个集合是频繁集，则其子集也是频繁集如果一个集合是频繁集，则其子集也是频繁集

>Dsupp(X)≥Dsupp(XY)挖掘思路计算项集支持度可以采用逐层扩展方式生成候选项集先计算1-项集，然后计算2-项集，…，m-项集当计算k-项集支持度的时候（2≤k≤m），只需考虑那些其子集是频繁集的k-项集，而不必考虑包含任何非频繁子集的k-项集。这可省去大量的项集支持度计算操作计算获得项集支持度的过程生成候选频繁集计算由频繁子集组成的项集的过程Apriori方法Agrawal等人在1993年提出首先找出频繁1-项集，记为L1；利用频繁1-项集L1生成频繁2-项集

；不断如此循环下去，直到无法找到更多的频繁k-项集为止。每生成一层Lk都需要扫描一遍数据库。Apriori方法主要包含连接和剪枝两个处理步骤连接步骤：为了找出Lk，可以将Lk-1中的两个项集连接起来以获得一个Ck的候选集合。剪枝步骤：Ck是Lk的超集，所有的频繁k-项集必定都在Ck中，但Ck中有些项集不一定是频繁的。可以将Ck中的不频繁k-项集剪枝去掉。Apriori方法在生成了所有的频繁集之后，可生成规则。对于每个频繁集V，产生V的所有非空子集；对于V的每个非空子集W，如果||TV||/||TW||≥

，则输出规则W

(V－W)。Apriori方法示例某电子商城记录了顾客购买手机的信息数据值，设定

＝40%，

=100%。找出所有满足最小支持度和置信度的关联规则顾客号码数

据

项女男青年老年SamsungiPhone11111211113111411151116111711118111911110111Apriori方法示例找出k项频繁候选集顾客号码数

据

项女男青年老年SamsungiPhone11111211113111411151116111711118111911110111Apriori方法示例找出关联规则ACAFCFDERulesConf.RulesConf.RulesConf.RulesConf.A

C4/6A

F5/6C

F5/6D

E100%C

A4/6F

A5/6F

C5/6E

D4/6ACFBERulesConf.RulesConf.RulesConf.RulesConf.A

CF4/6C

AF4/6F

AC4/6B

E100%AC

F100%AF

C4/5CF

A4/5E

B4/7D

E，老年人买三星B

E，男性买三星

AC

F，青年女性买苹果关联规则的兴趣性规则爆炸问题(RuleExploration)如果得到了规则“置信度为86%的规则A

B”，那么“置信度为80%的规则AC

B”就可以认为是不感兴趣的关联规则兴趣性是一类测度用于判断关联规则具有意义、引人关注的程度支持度和置信度就是两个基本的兴趣性测度关联规则的兴趣性Lift确信度Conviction提升度、兴趣度Leverage杠杆率关联规则的提升度当提升度小于1，规则的效果比直接猜测更差体现了Y总体上的频率和在条件X下的频率之间的差异当提升度大于1，规则的效果好于仅基于数据中项目的频率来猜测规则右侧是否出现关联规则的杠杆度杠杆度越大，前项与后项之间的关系越紧密与提升度类似，反映关联规则前项与后项之间的关系如果杠杆度等于0，前项与后项之间独立关联规则的确信度确信度越小，前项与后项之间关联度越小在兴趣度Lift中，对后项取反，整体求倒数确信度越大，前项与后项之间越关联特殊形式关联规则时序关联规则广义关联规则数量关联规则简单关联规则广义关联规则“运动器材”是“羽毛球拍”的超类数据项之间可能存在更为复杂的关系，如数据项层次结构（taxonomy）“羽毛球拍”属于“运动器材”利用层次结构信息对决策分析是有意义的高层数据项关联也反映了有意义的知识内涵“运动器材

电子产品”一些在低层数据项间不显著的关联模式可能在高层数据间显著广义关联规则利用Apriori方法挖掘如何挖掘广义广联规则？将层次结构的所有高层数据（超类）项也作为数据项放到数据库中广义关联规则某数码店销售笔记本电脑、打印机和数码相机三种产品，经营型号如下。笔记本电脑：DellD610,SonyS38,SonyT27打印机：HP1010,HP4300,CanonLBP5200数码相机：CanonEOS-20D,CanonIXUS700,SonyDSC-V3最小支持度30%，最小置信度100%广义关联规则TID顾

客产

品1张三DellD610,HP10102李四DellD610,CanonLBP5200,SonyDSC-V33张三SonyS38,CanonLBP52004王五DellD610,HP43005李四SonyT27,CanonLBP5200,6王五CanonLBP52007李四HP1010,HP4300,CanonEOS-20D8李四CanonIXUS7009张三CanonEOS-20D,SonyDSC-V310王五CanonIXUS7001-项频繁集支

持

度2-项频繁集支

持

度DellD6100.3DellD610，打印机0.3CanonLBP52000.4CanonLBP5200，笔记本电脑0.3Dell笔记本电脑0.3Dell笔记本电脑，打印机0.3笔记本电脑0.5笔记本电脑，Canon打印机0.3Canon打印机0.4笔记本电脑，打印机0.5HP打印机0.3打印机0.7Canon数码相机0.4数码相机0.5规

则支

持

度置

信

度DellD610打印机0.31Dell笔记本电脑

打印机0.31笔记本电脑

打印机0.51广义关联规则规则中存在冗余超类和其所属子类之间的关联就没有意义MP3

电子产品子类/超类关系也可能造成一些规则是冗余的“Dell笔记本电脑

打印机”“笔记本电脑

打印机”数量关联规则数据项数值数据，如商品的数量、家庭的收入、客户的年龄等称做多值属性和连续属性数量关联规则水果[1～5kg]

饮料[2～12L]传统的关联规则广义关联规则关心“是否购买”没有涉及“购买多少”布尔关联规则数量关联规则基于Apriori方法挖掘数量关联规则将每一个离散化得到的区间属性（如年龄[30,50]）作为一个新属性进行数据转换。采用离散化的方法划分连续属性的值域。将原数据值在此区间上的匹配结果形成一个相应的布尔真值。例如，如果原记录t的年龄值是45，则在属性“年龄[30,50]”上的布尔值为1。进行关联规则挖掘，并得到形如XY的数量关联规则，其中项集X和Y包含区间属性。简单关联规则形如X

Ij（X

I，Ij

I）的简单关联规则具有一些重要的性质和用途，值得予以关注分类和一些诸如“P

?”的决策分析需求等许多应用只需要简单规则而不必生成所有的规则打印机

打印纸打印机与打印纸

文件夹仅挖掘形如X

Ij的关联规则简单关联规则如果有X

Y和XYZ的支持度和置信度，是否需要XYZ？只要给定X

Y及XY

Z的支持度和置信度X

Y及XY

Z也满足最小支持度和置信度X

YZ是冗余的如果有X

YZ满足最小支持度和置信度简单关联规则TID数

据

项#1AD#2BE#3ABDE#4BDE#5BCDE#6ABE#7ABCDE规

则

代

码关

联

规

则DsuppDconf#1A

B3/775%#2A

D3/775%#3A

E3/775%#4B

D4/766.7%#