数据仓库与数据挖掘技术第6章4关联规则.ppt
6.3 关联算法5/20/20231购物篮分析一个引发关联规则挖掘的典型例子5/20/20232应用：购物分析l市场购物分析结果将帮助商场内商品应如何合理摆放进行规划设计。l 其中一种策略就是将常常一起购买的商品摆放在相邻近的位置，以方便顾客同时购买这两件商品；如：如果顾客购买电脑的同时常也会购买一些金融管理类软件，那么将电脑软件摆放在电脑硬件附近显然将有助于促进这两种商品的销售。l而另一种策略则是将电脑软件与电脑硬件分别摆放在商场的两端，这就会促使顾客在购买两种商品时，走更多的路从而达到诱导他们购买更多商品的目的。比如：顾客在决定购买一台昂贵电脑之后，在去购买相应金融管理软件的路上可能会看到安全系统软件，这时他就有可能购买这一类软件。l市场购物分析可以帮助商场主管确定那些物品可以进行捆绑减价销售，如一个购买电脑的顾客很有可能购买一个捆绑减价销售的打印机。5/20/20233关联规则的概念l超市中客户在购买A的同时，经常会购买B，即A=B（关联规则）l客户在购买A后，隔了一段时间后会购买B（序列分析）l“90%的客户在购买面包时也会购买牛奶”l“啤酒与尿布”l“买外套=买鞋子”l 5/20/20234关联规则挖掘l关联规则挖掘关联规则挖掘就是从大量的数据中挖掘出有价值描述数就是从大量的数据中挖掘出有价值描述数据项之间相互联系的有关知识。据项之间相互联系的有关知识。l随着收集和存储在数据库中的数据规模越来越大，人们对这些数据中挖掘相应的关联知识越来越有兴趣。l例如：从大量的商业交易记录中发现有价值的关联知识就可帮助进行商品目录的设计、交叉营销或帮助进行其它有关的商业决策。l在数据挖掘的知识模式中，关联规则是比较重要的一种。l关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的方法。5/20/20235基本概念：关联规则、支持度、置信度（P145）l设I=i1,i2,im是项目集，其中的元素im称为项，D是全体事务的集合，事务T是I上的一个子集，集合TI，每个事务有唯一的TID标识。设X是一个项集，事务T包含X当且仅当XT，关联规则就是形如X=Y的蕴含式，其中XI，YI且XY=，X称为规则的条件，Y称为规则的结果。关联规则设定两项约束：支持度Supp和可信度Conf。（1）支持度s：support(X=Y)=P(XY)P(XY):X和Y这两个项目集在事务集D中同时出现的概率（2）置信度c：confidence(X=Y)=P(YX)P(YX):在出现项目集X的事务集D中，项目集Y也同时出现的概率（3）关联规则X=Y成立的条件是：它具有支持度，即事务集D中至少有s%的事务包含XY；它具有置信度，即事务集D中包含X的事务至少有c%同时也包含Y l强规则：满足最小支持度阈值（minsup）和最小置信度阈值（minconf）的规则（用0%和100%之间的值而不是用0到1之间的值表示）5/20/20236什么是关联挖掘？l关联规则挖掘：l在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。l应用：l购物篮分析、交叉销售、产品目录设计、聚集、分类、lossleader analysis等l举例：规则形式：5/20/20237应用：进行关联分析5/20/20238关联的挖掘过程l 挖掘关联规则的问题的处理过程分为两步：(1)发现频繁项目集。通过用户给定的最小支持度寻找所有频繁项集，即找出所有支持度不低于用户指定的最小支持度的项目集。事实上这些频繁项目集可能具有包含关系，一般我们只关心那些不被其他频繁项目集所包含的，所谓频繁大项目集的集合，这些频繁大项目集是形成关联规则的基础。(2)生成关联规则。通过用户给定的最小可信度在每个最大频繁项目集中寻找可信度不小于给定的最小可信度的关联规则。所有支持度大于最小支持度的项集称为频繁项集（频集）5/20/20239关联规则的优缺点l优点l可以产生清晰有用的结果；l支持间接数据挖掘；l可以处理变长的数据；l计算的消耗量是可以预见的；l缺点l当问题变大时，计算量增长得厉害；l难以决定正确的数据；l容易忽略离群数据；5/20/202310简单形式的关联规则算法l几个经典的关联挖掘算法lApriori算法l抽样算法lDIC算法lApriori算法是最经典的关联规则挖掘算法，是由R.Agrawal等人于1993年首先提出的，其核心方法是基于频集理论的递推方法。5/20/202311Apriori算法l算法的基本思想：Apriori算法的中心思想是首先通过对事务数据库进行扫描，找出支持度不小于最小支持度的所有项目，即频繁1-项集。然后循环执行以下三步：(1)对频繁k-项集中的项进行连接，前提条件是前k-1项必须相同。(2)进行减枝，利用Apriori性质对连接后的项目集进行筛选，删除那些子集不是频繁集的项目集，得出候选(k+1)-项集。(3)对数据库进行扫描，计算候选项的支持度，从候选集中删除支持度小于最小支持度的候选项，进而得出频繁(k+1)-项集。依此类推，直到不能找到频繁项集为止，也即频繁k-项集为空。5/20/202312Apriori核心算法表示输入：事务数据库D，最小支持度阈值minsup。输出：D中的频繁项集L。(1)在第一次扫描中，对D中每一个数据项计算其支持度，确定出满足最小支持度的1频繁项集集合L1。(2)利用已经生成的Lk-1自身连接，得到候选k项集的集合Ck。(3)然后扫描数据库，计算这些候选集的支持度。(4)对候选k项集Ck进行剪枝。扫描Ck，计算这些候选项集的支持度，删除支持度低于用户给定最小支持度阈值minsup的项目集，最后，生成所有长度为k的频繁项集Lk。(5)重复(2)(4)，直到Lk为空。(6)对L1到Lk取并集，即为最终的频繁集L。5/20/202313Apriori算法例子【例1】假设数据库中有9个事务，即D=9，Apriori假定事务中的项按字典次序存放。利用Apriori算法寻找D中的频繁项集。事务集合D首先扫描首先扫描D D，对，对每个候选项计数每个候选项计数得到候选得到候选1 1项集项集的集合的集合C1C1项 集支持度计数i16i27i35i42i52候选1项集的集合C15/20/202314项 集支持度计数i16i27i35i42i52候选1项集的集合C1将支持度计数结果与将支持度计数结果与最小支持度进行比较，最小支持度进行比较，保留满足最小支持度保留满足最小支持度的项，得到频繁的项，得到频繁1 1项项的集合的集合L1L1。项 集支持度计数i16i27i35i42i52频繁1项集的集合L1设最小支持度阈值为设最小支持度阈值为20（即在（即在9行中，行中，至少出现两次）至少出现两次）5/20/202315事务集合D继续扫描继续扫描D D，产，产生候选生候选2 2项集的项集的集合集合C2C2，并对每，并对每个候选项计数个候选项计数候选2项集的集合C2 5/20/202316将支持度计数结将支持度计数结果与最小支持度果与最小支持度进行比较，保留进行比较，保留满足最小支持度满足最小支持度的项，得到频繁的项，得到频繁2 2项的集合项的集合L2L2候选2项集的集合C2 频繁2项的集合L25/20/202317事务集合D继续扫描继续扫描D D，产，产生候选生候选3 3项集的项集的集合集合C3C3，并连续，并连续剪枝，得到频繁剪枝，得到频繁3 3项的集合项的集合L3L3项 集支持度计数i1，i2，i52i1，i2，i41i1，i2，i310候选3项集的集合C3频繁3项的集合L3C4=，因此算法由于无法发现新的项集而结束对L1到L3取并集，即为最终的频繁集L5/20/202318从频繁项集产生关联规则 当从数据库D的事务中找出频繁项集后，很容易产生强关联规则（强关联规则满足最小支持度和最小置信度）。对于置信度，可以用下式来计算，其中条件概率用项集支持度计数表示。根据该式，关联规则可以产生如下：support_count(XY)是包含项集XY的事务数support_count(X)是包含项集X的事务数(1)对于每个频繁项集l，产生l的所有非空子集；(2)对于l的每个非空子集，如果 则输出规则 其中，minconf是最小置信度阈值。5/20/202319【例】基于例1的事务数据库，假定数据包含频繁项集，设最小置信度阈值为70%。试根据以上关联规则原理，产生强规则。25/20/202320提高Apriori的有效性l 划分l 散列hashl 抽样l 减少交易的个数l 动态的项目集计数l 层次结构l 序列模式l 依据日历的购物篮分析5/20/202321一个超市的销售系统记录了客户购物的情况。记录号购物清单1啤酒，尿布，婴儿爽身粉，面包，雨伞2尿布，婴儿爽身粉3啤酒，尿布，牛奶4尿布，啤酒，洗衣粉5啤酒，牛奶，可乐(coke)练习：“啤酒与尿布”的关联分析某超市5个客户的购物清单设最小支持度阈值40(即在5行中,至少出现两次)，最小置信度阈值为705/20/202322
