Clementine关联分析曹慧荣20110426

第9章探索内部结构：Clementine的关联分析信息与计算科学专业2010本科

曹慧荣第9章探索内部结构：Clementine的关联分析Apriori算法GRI算法序列关联算法

主要方法有：9.1Apriori算法引例Apriori算法Apriori算法的典型应用

内容安排：Step1:寻找频繁项集;Step2:给出强关联规则。9.1Apriori算法ID牛奶鸡蛋面包110121013111401150001：寻找频繁项集——受欢迎的商品或商品组合。

2：寻找频繁（强）关联规则——高频的购物模式如买牛奶的必然买面包。

项集支持度{牛奶}0.6{鸡蛋}0.4{面包}0.8{牛奶，鸡蛋}0.2{牛奶，面包}0.6{鸡蛋，面包}0.4{牛奶，鸡蛋，面包}0.2引例：某超市销售数据项：商品；项集：商品的集合。9.1Apriori算法ID牛奶鸡蛋面包11012101311140115000例：某超市销售数据Apriori算法完成：1.寻找频繁项集；受欢迎的商品。2.寻找频繁（强）的关联规则。高频的购物模式。当数据量大时，必须引入有效算法9.1Apriori算法K-项集：包含K个项的集合。频繁项集：所有支持度大于等于最小支持度的项集。频繁项集的寻找：如果有m种商品，则只要计算所有非空项集的支持度，大于等于最小支持度的即为频繁项集。

一、寻找频繁项集9.1Apriori算法

如前所述，m种商品的非空项集有2m-1个，计算量爆炸性增长。频繁项集的性质：

性质1：频繁项集的子集必为频繁项集；性质2：非频繁项集的超集必为非频繁项集。先找频繁项集；然后再找频繁规则例题1：设有项集T={a,b,c,d,e}所示的简单交易数据库，设minS=50%，求所有的频繁项集。解：

step1:潜在的频繁1-项集C1为

{a}，{b}，{c}，{d}，{e}由最小支持度可以得到频繁1-项集L1{a}，{b}，{c}，{e}

交易号商品1a,c,d2b,c,e3a,b,c,e4b,e9.1Apriori算法一、寻找频繁项集step2:在频繁L1基础上求L2

L1支持度{a}0.5{b}0.75{c}0.75{e}0.75连接L1*L1得到潜在C2C2支持度{a,b}0.25{a,c}0.5{a,e}0.25{b,c}0.5{b,e}0.75{c,e}0.5交易号商品1a,c,d2b,c,e3a,b,c,e4b,estep3:在频繁L2基础上求L3

交易号商品1a,c,d2b,c,e3a,b,c,e4b,eL2支持度{a,c}0.5{b,c}0.5{b,e}0.75{c,e}0.5连接L2*L2得到{a,b,c},{a,c,e},{b,c,e}剪枝，从而得到潜在的C3{b,c,e}因此所有的频繁项集为：{a},{b},{c},{e},{a,c},{b,c},{b,e},{c,e},{b,c,e}潜在1-项集C1频繁1-项集L1连接潜在2-项集C1频繁2-项集L2连接剪枝潜在3-项集C3频繁3-项集L3.。。。Apriori算法寻找频繁项集的步骤——受欢迎的商品或商品组合。二、寻找强关联规则关联规则：形式上为

(规则支持度，规则置信度)支持度(Support)：同时购买A和B的客户人数占总客户数的百分比称为规则的支持度。

置信度(Confidence)：同时购买A和B的客户人数占购买A的客户人数的百分比称为规则的置信度。

由于在实际应用中，概率P一般是无法事先给出的，所以常以频率代替。前项后项二、寻找强关联规则例题2：计算下面规则的支持度与置信度。ID牛奶奶酪鸡蛋面包1100121101311114000150100（1）{面包}{牛奶}（2）{牛奶}{面包}（3）{鸡蛋}{奶酪}二、寻找强关联规则ID牛奶奶酪鸡蛋面包1100121101311114000150100{面包}{牛奶}(60%,75%){牛奶}{面包}(60%,100%){鸡蛋}{奶酪}(20%,100%)(规则支持度，规则置信度)思考：（1）规则支持度小，规则置信度大，说明什么现象？

如1000个人中只有一个人购买了烤炉，又购买了碳，所以

{烤炉}{碳}(0.1%,100%)

（应用机会少）（2）规则支持度大，规则置信度小，说明什么现象？二、寻找强关联规则

AB(规则支持度，规则置信度)一个好的规则应该有比较高的支持度和置信度．如果满足最小支持度阈值和最小置信度阈值，则称这个规则为强规则。我们的目的就是找出强关联规则。由频繁项集可以产生潜在的强关联规则

二、寻找强关联规则交易号商品1a,c,d2b,c,e3a,b,c,e4b,estep2.

由频繁项集产生关联规则如表：潜在强关联规则置信度是否为强关联规则{a}{c}1Yes{c}{a}0.67No{b}{c}0.67No{c}{b}0.67No{b}{e}1Yes{e}{b}1Yes例题3：同例题1的数据。设minS=50%，minC=80%，利用Apriori算法求所有的强关联规则。解：step1.所有的频繁项集为：{a},{b},{c},{e},{a,c},{b,c},{b,e},{c,e},{b,c,e}三、Apriori算法的步骤Apriori算法是一种寻找强关联规则的算法

Apriori算法具体步骤:

第一步：产生频繁项集第二步：构造关联规则。

给该超市的建议:

请将商品b和e的捆绑销售或就近安排货架!

四、Apriori算法的典型应用潜在强关联规则置信度是否为强关联规则{a}{c}1Yes{c}{a}0.67No{b}{c}0.67No{c}{b}0.67No{b}{e}1Yes{e}{b}1Yes成功案例：神奇的购物篮分析《啤酒与尿布:神奇的购物篮分析》的故事是营销届的神话，“啤酒”和“尿布”两个看上去没有关系的商品摆放在一起进行销售、并获得了很好的销售收益，这种现象就是卖场中商品之间的关联性，研究“啤酒与尿布”关联的方法就是购物篮分析，购物篮分析是沃尔玛秘而不宣的独门武器，购物篮分析可以帮助我们在门店的销售过程中找到具有关联关系的商品，并以此获得销售收益的增长！Apriori算法是一种寻找强关联规则的算法

Apriori算法具体步骤:

第一步：产生频繁项集第二步：构造关联规则。附：关联规则的相关分析强关联规则不一定有正确的指导意义！例：在10000个交易中，6000个顾客交易包含计算机游戏，7500个顾客交易包含影碟机，4000个交易包含计算机游戏和影碟机。规则其实是误导，因为购买影碟机的可能性是75%，比66%还大。事实是：计算机游戏和影碟机是负相关的。

关联规则实用性的测度指标

规则AB提升度L=

L:<1，负相关

=1，A和B是独立的

>1，正相关，每一个出现蕴涵另一个出现p({游戏})=0.6，p({影碟机})=0.75，p({游戏,影碟机})=0.4L=0.4/0.6*0.75=0.89<1负相关，规则无意义！附：关联规则的相关分析小结：基本概念：