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