数据仓库与数据挖掘技术第6章4关联规则.ppt

6.3 关联算法 购物篮分析一个引发关联规则挖掘的典型例子 应用：购物分析 市场购物分析结果将帮助商场内商品应如何合理摆放进行规划设计。 其中一种策略就是将常常一起购买的商品摆放在相邻近的位置，以方便顾客同时购买这两件商品；如：如果顾客购买电脑的同时常也会购买一些金融管理类软件，那么将电脑软件摆放在电脑硬件附近显然将有助于促进这两种商品的销售。 而另一种策略则是将电脑软件与电脑硬件分别摆放在商场的两端，这就会促使顾客在购买两种商品时，走更多的路从而达到诱导他们购买更多商品的目的。比如：顾客在决定购买一台昂贵电脑之后，在去购买相应金融管理软件的路上可能会看到安全系统软件，这时他就有可能购买这一类软件。 市场购物分析可以帮助商场主管确定那些物品可以进行捆绑减价销售，如一个购买电脑的顾客很有可能购买一个捆绑减价销售的打印机。 关联规则的概念 超市中客户在购买A的同时，经常会购买B，即A=B（关联规则） 客户在购买A后，隔了一段时间后会购买B（序列分析） “90%的客户在购买面包时也会购买牛奶” “啤酒与尿布” “买外套=买鞋子” …… 关联规则挖掘 关联规则挖掘就是从大量的数据中挖掘出有价值描述数据项之间相互联系的有关知识。 随着收集和存储在数据库中的数据规模越来越大，人们对这些数据中挖掘相应的关联知识越来越有兴趣。 例如：从大量的商业交易记录中发现有价值的关联知识就可帮助进行商品目录的设计、交叉营销或帮助进行其它有关的商业决策。 在数据挖掘的知识模式中，关联规则是比较重要的一种。 关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的方法。 基本概念：关联规则、支持度、置信度（P145） 设I={i1,i2,…,im}是项目集，其中的元素im称为项，D是全体事务的集合，事务T是I上的一个子集，集合T?I，每个事务有唯一的TID标识。设X是一个项集，事务T包含X当且仅当X?T ，关联规则就是形如X=Y的蕴含式，其中X?I，Y?I且X∩Y =Φ，X称为规则的条件，Y称为规则的结果。关联规则设定两项约束：支持度Supp和可信度Conf。 （1）支持度s：support(X=Y)=P(X∪Y) P(X∪Y):X和Y这两个项目集在事务集D中同时出现的概率 （2）置信度c：confidence(X=Y)= P(Y｜X) P(Y｜X) :在出现项目集X的事务集D中，项目集Y也同时出现的概率 （3）关联规则X=Y成立的条件是：①它具有支持度，即事务集D中至少有s%的事务包含X∪Y；②它具有置信度，即事务集D中包含X的事务至少有c%同时也包含Y 强规则：满足最小支持度阈值（minsup）和最小置信度阈值（minconf）的规则（用0%和100%之间的值而不是用0到1之间的值表示） 什么是关联挖掘？ 关联规则挖掘： 在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。 应用： 购物篮分析、交叉销售、产品目录设计、聚集、分类、loss－leader analysis等 举例：规则形式： 应用：进行关联分析 关联的挖掘过程 挖掘关联规则的问题的处理过程分为两步： (1)发现频繁项目集。通过用户给定的最小支持度寻找所有频繁项集，即找出所有支持度不低于用户指定的最小支持度的项目集。事实上这些频繁项目集可能具有包含关系，一般我们只关心那些不被其他频繁项目集所包含的，所谓频繁大项目集的集合，这些频繁大项目集是形成关联规则的基础。 (2)生成关联规则。通过用户给定的最小可信度在每个最大频繁项目集中寻找可信度不小于给定的最小可信度的关联规则。 关联规则的优缺点 优点 可以产生清晰有用的结果； 支持间接数据挖掘； 可以处理变长的数据； 计算的消耗量是可以预见的； 缺点 当问题变大时，计算量增长得厉害； 难以决定正确的数据； 容易忽略离群数据； 简单形式的关联规则算法 几个经典的关联挖掘算法 Apriori算法 抽样算法 DIC算法 Apriori算法是最经典的关联规则挖掘算法，是由R.Agrawal等人于1993年首先提出的，其核心方法是基于频集理论的递推方法。 Apriori算法 算法的基本思想：Apriori算法的中心思想是首先通过对事务数据库进行扫描，找出支持度不小于最小支持度的所有项目，即频繁1-项集。然后循环执行以下三步： 对频繁k-项集中的项进行连接，前提条件是前k-1项必须相同。 进行减枝，利用Apriori性质对连接后的项目集进行筛选，删除那些子集不是频繁集的项目集，得出候选(k+1)-项集。 对数据库进行扫描，计算候选项的支持度，从候选集中删除支持度小于最小支持度的候选项，进而得出频繁(k+1)-项集。依此类推，直到不能找到频繁项集为止，也即频繁k-项集为空