关联规则挖掘

1、沃尔玛，沃尔玛，请把蛋挞与飓风用品摆在请把蛋挞与飓风用品摆在一起一起通过对通过对历史交易记录这个庞大数据库进行历史交易记录这个庞大数据库进行观察，沃尔玛注意到，每当季节性飓风来观察，沃尔玛注意到，每当季节性飓风来临之前，不仅手电筒销量增加，而且美式临之前，不仅手电筒销量增加，而且美式早餐含糖零食蛋挞销量也增加早餐含糖零食蛋挞销量也增加了。了。因此每当季节性飓风来临时因此每当季节性飓风来临时，沃尔玛就会，沃尔玛就会把蛋挞与飓风用品摆放在一起，从而增加把蛋挞与飓风用品摆放在一起，从而增加销量。销量。2案例回顾案例回顾尿不湿和啤酒尿不湿和啤酒超级商业零售连锁巨无霸沃尔玛公司超级商业零售连锁巨无霸沃尔

2、玛公司(Wal Mart)拥有世上最大的数据仓库系统之一。为拥有世上最大的数据仓库系统之一。为了能够准确了解顾客在其门店的购买习惯，沃了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行了购物篮关联规尔玛对其顾客的购物行为进行了购物篮关联规则分析，从而知道顾客经常一起购买的商品有则分析，从而知道顾客经常一起购买的商品有哪些。哪些。跟尿不湿一起购买最多的商品竟是啤酒跟尿不湿一起购买最多的商品竟是啤酒”!这这是数据挖掘技术对历史数据进行分析的结果，是数据挖掘技术对历史数据进行分析的结果，反映的是数据的内在规律。反映的是数据的内在规律。那么这个结果符合现实情况吗那么这个结果符合现实情况

3、吗?是否是一个有是否是一个有用的知识？是否有利用价值？用的知识？是否有利用价值？3尿不湿和啤酒尿不湿和啤酒经过大量实际调查和分析，他们揭示了一个隐藏在经过大量实际调查和分析，他们揭示了一个隐藏在“尿不湿与啤酒尿不湿与啤酒”背后的美国消费者的一种行为模式：背后的美国消费者的一种行为模式：在美国，到超市去买婴儿尿不湿是一些年轻的父亲下班后的日常工在美国，到超市去买婴儿尿不湿是一些年轻的父亲下班后的日常工作，而他们中有作，而他们中有30%40%的人同时也会为自己买一些啤酒。产生的人同时也会为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫不要忘了下班这一现象的原因是：美国的太太们常

4、叮嘱她们的丈夫不要忘了下班后为小孩买尿不湿，而丈夫们在买尿不湿后又随手带回了他们喜欢后为小孩买尿不湿，而丈夫们在买尿不湿后又随手带回了他们喜欢的啤酒。另一种情况是丈夫们在买啤酒时突然记起他们的责任，又的啤酒。另一种情况是丈夫们在买啤酒时突然记起他们的责任，又去买了尿不湿。既然尿不湿与啤酒一起被购买的机会很多，那么沃去买了尿不湿。既然尿不湿与啤酒一起被购买的机会很多，那么沃尔玛就在他们所有的门店里将尿不湿与啤酒并排摆放在一起，结果尔玛就在他们所有的门店里将尿不湿与啤酒并排摆放在一起，结果是得到了尿不湿与啤酒的销售量双双增长。是得到了尿不湿与啤酒的销售量双双增长。按常规思维，尿不湿与啤酒风马牛不相

5、及，若不是借助数据挖掘技按常规思维，尿不湿与啤酒风马牛不相及，若不是借助数据挖掘技术对大量交易数据进行挖掘分析，沃尔玛是不可能发现数据内这一术对大量交易数据进行挖掘分析，沃尔玛是不可能发现数据内这一有价值的规律的。有价值的规律的。4美国一名男子闯入他家附近的一家美国一名男子闯入他家附近的一家美国零售连锁超市美国零售连锁超市Target店铺店铺(美国美国第三大零售商塔吉特第三大零售商塔吉特)进行抗议：进行抗议：“你们竟然给我你们竟然给我17岁的女儿发婴儿尿岁的女儿发婴儿尿片和童车的优惠券。片和童车的优惠券。”店铺经理立刻向来者承认错误，但店铺经理立刻向来者承认错误，但是其实该经理并不知道这一行为

6、是是其实该经理并不知道这一行为是总公司运行数据挖掘的结果。如图总公司运行数据挖掘的结果。如图所示。一个月后，这位父亲来道歉，所示。一个月后，这位父亲来道歉，因为这时他才知道他的女儿的确怀因为这时他才知道他的女儿的确怀孕了。孕了。Target比这位父亲知道他女儿比这位父亲知道他女儿怀孕的时间足足早了一个月。怀孕的时间足足早了一个月。5美国折扣零售商塔吉特与怀孕预测美国折扣零售商塔吉特与怀孕预测美国折扣零售商塔吉特与怀孕预测美国折扣零售商塔吉特与怀孕预测塔吉特公司塔吉特公司能能在在不被清楚告知的情况下预测出一个女性不被清楚告知的情况下预测出一个女性的怀孕的怀孕情况情况该公司找出了大概该公司找出了大

7、概20多种与怀孕的关联多种与怀孕的关联物，给顾客进行物，给顾客进行“怀孕趋势怀孕趋势”评分评分这些这些数据甚至使得零售商能够比较准确地预测预产期，数据甚至使得零售商能够比较准确地预测预产期，这样就能够在孕期的每个阶段给客户寄送相应的优惠券这样就能够在孕期的每个阶段给客户寄送相应的优惠券Target能够通过分析女性客户购买记录，能够通过分析女性客户购买记录，“猜出猜出”哪些哪些是孕妇。他们从是孕妇。他们从Target的数据仓库中挖掘出的数据仓库中挖掘出25项与怀孕项与怀孕高度相关的商品，制作高度相关的商品，制作“怀孕预测怀孕预测”指数。比如他们发指数。比如他们发现女性会在怀孕四个月左右，大量购买

8、无香味乳液。以现女性会在怀孕四个月左右，大量购买无香味乳液。以此为依据推算出预产期后，就抢先一步将孕妇装、婴儿此为依据推算出预产期后，就抢先一步将孕妇装、婴儿床等折扣券寄给客户来吸引客户购买。床等折扣券寄给客户来吸引客户购买。6大数据分析核心手段、技术数据处理数据挖掘模型预测概念概念数据挖掘数据挖掘(Data Mining) (Data Mining) 是通过分析每个数据，从大量是通过分析每个数据，从大量数据中寻找其规律的技术，主要有数据准备、规律寻找数据中寻找其规律的技术，主要有数据准备、规律寻找和规律表示和规律表示3 3个步骤。个步骤。 数据挖掘的任务数据挖掘的任务有关联分析、聚类分析、分

9、类分析、异有关联分析、聚类分析、分类分析、异常分析、特异群组分析和演变分析等。常分析、特异群组分析和演变分析等。关联分析关联分析是指如果两个或多个事物之间存在一定的关联是指如果两个或多个事物之间存在一定的关联, ,那么其中一个事物就能通过其他事物进行预测那么其中一个事物就能通过其他事物进行预测. .它的目的它的目的是为了挖掘隐藏在数据间的相互关系是为了挖掘隐藏在数据间的相互关系 。典型的关联规则发现问题是对超市中的货典型的关联规则发现问题是对超市中的货篮数据（篮数据（Market Basket）进行分析。通过）进行分析。通过发现顾客放入货篮中的不同商品之间的关发现顾客放入货篮中的不同商品之间的

10、关系来分析顾客的购买习惯。系来分析顾客的购买习惯。数据关联数据关联 经典案例：经典案例：沃尔玛的啤酒和尿布的故事沃尔玛的啤酒和尿布的故事关联规则关联规则购物篮分析购物篮分析“啤酒和尿布啤酒和尿布”的故事是营销届的神话，的故事是营销届的神话，“啤酒啤酒”和和“尿布尿布”两个看上去没有关系的两个看上去没有关系的商品摆放在一起进行销售、并获得了很好的商品摆放在一起进行销售、并获得了很好的销售收益，这种现象就是卖场中商品之间的销售收益，这种现象就是卖场中商品之间的关联性。关联性。 研究研究“啤酒与尿布啤酒与尿布”关联的方法就是购物关联的方法就是购物篮分析，购物篮分析是沃尔玛秘而不宣的独篮分析，购物篮分

11、析是沃尔玛秘而不宣的独门武器，购物篮分析可以帮助我们在门店的门武器，购物篮分析可以帮助我们在门店的销售过程中找到具有销售过程中找到具有关联关系关联关系的商品，并以的商品，并以此获得销售收益的增长！此获得销售收益的增长！ 关联规则挖掘（Association Rule）在数据挖掘的知识模式中，关联规则模式是比较重要的一种。关联规则的概念由Agrawal、Imielinski、Swami 提出，是数据中一种简单但很实用的规则。在数据库的知识发现中，关联规则就是描述这种在一个事务中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过量化的数字描述物品甲的出现对物品乙的出现有多大的影响现实中，这

12、样的例子很多。l例如超级市场利用前端收款机收集存储了大量的售货数据，这些数据是一条条的购买事务记录，每条记录存储了l事务处理时间，l顾客购买的物品、l物品的数量及金额等。l 这些数据中常常隐含形式如下的关联规则：在购买铁锤的顾客当中，有70 的人同时购买了铁钉。l 这些关联规则很有价值，商场管理人员可以根据这些关联规则更好地规划商场，如把铁锤和铁钉这样的商品摆放在一起，能够促进销售。关联规则分析拓展1）商业销售商业销售上，如何通过交叉销售得到更大的收入？2）保险方面保险方面，如何分析索赔要求发现潜在的欺诈行为？3）银行方面银行方面，如何分析顾客消费行业，以便有针对性地向其推荐感兴趣的服务？4）

13、哪些制造零件和设备设置与故障事件故障事件关联？5）哪些病人和药物药物属性与结果关联？6）哪些商品商品是已经购买商品A的人最有可能购买的？l如何从交易记录数据库或关系数据库的大量数如何从交易记录数据库或关系数据库的大量数据中挖掘出关联规则知识据中挖掘出关联规则知识？l什么样的关联规则才是最有意义的什么样的关联规则才是最有意义的？l如何才能帮助挖掘过程尽快发现有价值的关联如何才能帮助挖掘过程尽快发现有价值的关联知识知识？问题问题关联规则基本概念项目（item）：其中的B C M T 都称作item。项集（itemset）:item的集合，例如B C、C M T等，每个顾客购买的都是一个项集。其中，

14、项集中item的个数称为项集的长度，含有k个item的项集成为K-itemset.交易（transaction）：定义I为所有商品的集合，在这个例子中I=B C M T。每个非空的I子集都成为一个交易。所有交易构成交易数据库D。交易ID（TID）购买商品（Items）B：bread C:cream M:milk T:teaT01 B C M TT02 B C MT03 C MT04 M TT05 B C MT06 B TT07 B M TT08 B TT09 B C M TT10 B M T关联规则关联规则设I=i1,i2,im是项（Item）的集合。记D为事务（Transaction）的集合

15、（事务数据库），事务T是项的集合，并且T I。设A是I中一个项集，如果A T，那么称事务T包含A。定义1：关联规则是形如AB的蕴涵式，这里A I，B I，并且A B= 。度量规则的指标支持度（）可信度（）作用度/兴趣度（）支持度定义2：规则的支持度。支持度描述了A 和B 这两个物品集在所有的事务中同时出现的概率有多大。规则AB在数据库D中具有支持度S，即概率P(AB)，即： 其中|D|表示事务数据库D的个数，表示A、B两个项集同时发生的事务个数。|D|AB| P(AB)B) (A SCustomerbuys diaperCustomerbuys bothCustomerbuys beer可信度

16、定义3：规则的可信度可信度就是指在出现了物品集A 的事务T 中，物品集B 也同时出现的概率规则AB具有可信度C，表示C是条件概率P(B|A)，即： 其中 表示数据库中包含项集A的事务个数。 |A|AB|)|()BA(ABPC|A|小结可信度是对关联规则的准确度准确度的衡量，支持度是对关联规则重要性重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性。显然支持度越大，关联规则越重要。有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小，因此也不重要。 理解：关联分析中的三个重要的概念理解：关联分析中的三个重要的概念 举例：举例：1000010000个人购买了产品，其中

17、购买个人购买了产品，其中购买A A产品的人是产品的人是10001000个，购个，购买买B B产品的人是产品的人是20002000个，个，ABAB同时购买的人是同时购买的人是800800个。个。支持度支持度指的是关联的产品（假定指的是关联的产品（假定A A产品和产品和B B产品关联）同时购产品关联）同时购买的人数占总人数的比例，即买的人数占总人数的比例，即800/10000=8%800/10000=8%，有，有8%8%的用户的用户同时购买了同时购买了A A和和B B两个产品；两个产品； 可信度可信度指的是在购买了一个产品之后购买另外一个产品的可能指的是在购买了一个产品之后购买另外一个产品的可能性

18、，如购买了性，如购买了A A产品之后购买产品之后购买B B产品的可信度产品的可信度=800/1000=80% =800/1000=80% 支持度支持度可信度可信度作用度（兴趣度）讨论两种事务的比较关系 AB作用度是两种可能性的比较，描述物品集A 的出现对物品集B 的出现有多大的影响。定义定义4：兴趣度：兴趣度： 公式反映了项集公式反映了项集A与项集与项集B的相关程度。的相关程度。若若 即即 表示表示项集项集A出现和项集出现和项集B是相互独立的。是相互独立的。若若 表示表示A出现和出现和B出现是负相关的。出现是负相关的。若若 表示表示A出现和出现和B出现是正相关的。意味着出现是正相关的。意味着A

19、的出现的出现蕴含蕴含B的出现。的出现。()()( ) ( )P ABI ABP A P B () 1I AB )()()(BPAPABPI(A) 1B一条规则的兴趣度越大于1说明我们对这条规则越感兴趣（即其实际利用价值越大）；一条规则的兴趣度越小于1说明我们对这条规则的反面规则越感兴趣（即其反面规则的实际利用价值越大）；兴趣度I不小于0。 例设交易集D，经过对D的分析，得到表格:买咖啡买咖啡不买咖啡不买咖啡合计合计买牛奶买牛奶20525不买牛奶不买牛奶70575合计合计9010100所有可能的关联规则 Rules SCI1 买牛奶买咖啡0.20.80.89 2买咖啡买牛奶 0.20.220.8

20、9 3买牛奶不买咖啡0.050.224不买咖啡买牛奶0.050.525不买牛奶买咖啡0.70.931.0376买咖啡不买牛奶0.70.781.0377不买牛奶不买咖啡0.050.0670.678不买咖啡不买牛奶0.050.20.87讨论讨论I1I2I3I6共共4条规则：条规则：由于由于I1,I21,规则才有价值。规则才有价值。兴趣度也称为作用度（兴趣度也称为作用度（Lift）,表示关联规表示关联规则则AB的的“提升提升”。如果作用度（兴趣度）。如果作用度（兴趣度）不大于不大于1，则此关联规则就没有意义了。，则此关联规则就没有意义了。 小结作用度描述了物品集A 对物品集B 的影响力的大小。作用度

21、越大，说明物品集B 受物品集A 的影响越大。一般情况，有用的关联规则的作用度都应该大于1，说明A 的出现对B 的出现有促进作用，也说明了它们之间某种程度的相关性，如果作用度不大于1，则此关联规则也就没有意义了。关联规则挖掘在关联规则的三个属性中，支持度和可信度能够比较直接形容关联规则的性质事实上，人们一般只对满足一定的支持度和可信度的关联规则感兴趣。因此，为了发现有意义的关联规则，需要由用户给定两个阈值： 最小支持度（min_sup）和最小可信度（min_conf）频繁项集如果项集满足最小支持度，则它称之为频繁项集（Frequent Itemset）。 强规则定义定义5：强关联规则。同时满足最

22、小支持度（min_sup）和最小可信度（min_conf）的规则称之为强关联规则，即成立时，规则称之为强关联强关联规则规则，否则称为弱关联弱关联规则规则。数据挖掘主要就是对强规则的挖掘数据挖掘主要就是对强规则的挖掘。min_confB) (A min_supB) (A CS且3. 关联规则挖掘过程关联规则挖掘过程关联规则的挖掘一般分为两个过程：（1）找出所有的频繁项集）找出所有的频繁项集：找出支持度大于最小支持度的项集，即频繁项集。（2）由频繁项集）由频繁项集产生（强）关联产生（强）关联规则规则：根据定义，这些规则必须满足最小支持度和最小可信度。35Step one: 频繁项集项集项集 - 任

23、意项的集合任意项的集合k-项集项集 - 包含包含k个项的项集个项的项集频繁项集频繁项集 - 满足最小支持度的项集满足最小支持度的项集若若I包含包含m个项个项,那么可以产生多少个项集那么可以产生多少个项集?36Step two:强关联规则给定一个项集给定一个项集,容易生成关联规则容易生成关联规则.项集项集: Chips, Salsa, Beer Beer, Chips = Salsa Beer, Salsa = Chips Chips, Salsa = Beer强强规则规则强规则通常定义为那些满足最小支持度和最小可信强规则通常定义为那些满足最小支持度和最小可信度的规则度的规则.保留满足最小可信度

24、的规则保留满足最小可信度的规则4 Apriori算法基本思想算法基本思想Apriori是挖掘关联规则的一个重要方法。算法分为两个子问题：1、找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频繁集（Frequent Itemset）。2、使用第1步找到的频繁集产生规则。 Apriori 使用一种称作逐层搜索的迭代方法，使用一种称作逐层搜索的迭代方法，“K-项集项集”用于探索用于探索“K+1-项集项集”。首先，找出频繁首先，找出频繁“1-项集项集”的集合。该集的集合。该集合记作合记作L1。L1用于找频繁用于找频繁“2-项集项集”的集的集合合L2，而，而L2用于找用于找L3，如此下

25、去，直到不能找到如此下去，直到不能找到“K-项集项集”。找。找每个每个LK需要一次数据库扫描。需要一次数据库扫描。Apriori 算法中候选项集算法中候选项集 与频繁项集的产生实例与频繁项集的产生实例事务ID事务的项目集T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C1) 在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法扫描所有的事务，对每个项的出现次数计数。见图中第1列。2) 假定最小事务支持计数为2（即min-sup=2/9=22%），可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。见图中第2列。3) 为发现频繁2-项集的集合L2，算法使用L1*L1来产生候选集C2。见图中第3列。4) 扫描D中事务，计算C2中每个候选项集的支持度计数，如图中的