菜头哥教程--关联规则挖掘(Apriori算法).docVIP

关联规则挖掘 数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 1、什么是关联规则挖掘 关联规则挖掘，也称为购物篮分析(market basket analysis)，研究属性间的相关性。所有的关联规则用形如if—then的形式来提供，从数据仓库的数据中挖掘得到，并且与逻辑的if—then规则不同，关联规则本质上是概率规则。 如果一个事务中含有X，则该事务中很可能含有Y。具体形式为{X}→{Y}，即通常可以描述为:当一个事务中顾客购买了一样东西{钢笔}(这里X=“钢笔”)则很可能他同时还购买了{墨水}(这里Y= 墨水)，这就是关联规则。 市场分析员要从大量的数据中发现顾客放入其购物篮中的不同商品之间的关系。如果顾客买牛奶，他也购买面包的可能性有多大？ 什么商品组或集合顾客多半会在一次购物时同时购买？例如，买牛奶的顾客有80%也同时买面包，或买铁锤的顾客中有70%的人同时也买铁钉，这就是从购物篮数据中提取的关联规则。分析结果可以帮助经理设计不同的商店布局。一种策略是：经常一块购买的商品可以放近一些，以便进一步刺激这些商品一起销售，例如，如果顾客购买计算机又倾向于同时购买财务软件，那么将硬件摆放离软件陈列近一点，可能有助于增加两者的销售。另一种策略是：将硬件和软件放在商店的两端，可能诱发购买这些商品的顾客一路挑选其他商品。 2、理论分析 关联规则是描述数据库中数据项之间存在的潜在关系的规则,形式为“A1∧A2∧...∧Am--B1∧B2∧...∧Bn”,其中Ai(i=1,2,......,m),Bj(j=1,2,......,n)是数据库中的数据项.数据项之间的关联规则即根据一个事务中某些项的出现,可推导出另一些项在同一事务中也出现. 挖掘关联规则的问题描述如下: 设: I={i1,i2......,im}是所有项目的集合. D是所有事务的集合(即数据库), 每个事务T是一些项目的集合, T包含在I中, 每个事务可以用唯一的标识符TID来标识. 设X为某些项目的集合,如果X包含在T中, 则称事务T包含X, 关联规则则表示为如下形式 (X包含在T)--(Y包含在T)的蕴涵式, 这里X包含在I中, Y包含在I中, 并且X∧Y=Φ. 其意义在于一个事务中某些项的出现,可推导出另一些项在同一事务中也出现 (为简单化,将(X包含在T)--(Y包含在T)表示为X--Y, 这里,‘--’称为‘关联’操作, X称为关联规则的先决条件, Y称为关联规则的结果). 事务集D中的规则X--Y是由支持度s(support)和置信度c(confidence)约束,置信度表示规则的强度, 支持度表示在规则中出现的频度。 数据项集X的支持度s(X)是D中包含X的事务数量与D的总事务数量之比, 但为下文便于叙述, 数据项集X的支持度是用数据库D中包含X的数量来表示; 规则X--Y的支持度s定义为: 在D中包含X∪Y的事务所占比例为s%, 表示同时包含X和Y的事务数量与D的总事务量之比; 规则X--Y的置信度c定义为: 在D中,c%的事务包含X的同时也包含Y, 表示D中包含X的事务中有多大可能性包含Y. 最小支持度阈值minsupport表示数据项集在统计意义上的最低主要性. 最小置信度阈值mincontinence表示规则的最低可靠性. 如果数据项集X满足X.support=minsupport, 则X是大数据项集. 一般由用户给定最小置信度阈值和最小支持度阈值.置信度和支持度大于相应阈值的规则称为强关联规则, 反之称为弱关联规则. 发现关联规则的任务就是从数据库中发现那些置信度、支持度大小等于给定值的强壮规则. 基于上述概念，我们可以很容易得到一些基本结论: (1) K维数据项集XK是频繁项集的必要条件是它所有K-1维子项集也为频繁项集，记为XK-1　 (2)如果K维数据项集XK的任意一个K-1维子集XK-1，不是频繁项集，则K维数据项集XK本身也不是最大数据项集。 (3) XK是K维频繁项集，如果所有K-1维频繁项集集合XK-1中包含XK的K-1维子项集的个数小于K，则XK不可能是K维最大频繁数据项集。 证明: 很明显，数据项集XK-1:的K-1维子项集的个数为K-1。如果高频繁数据项集XK-1，中包含XK的K-1.维子项集的个数小于k，则存在XK的K-1维子项集不是频繁数据项集，由结论(2)知K维数据项集本身也不是高频繁数据项集。 支持度： 每个关联规则都用支持度和置信度来表达规则的不确定性。在关联规则中，前件和后件都是不相交的项的集合。支持度是包含规则前件和后件中所有项的事务的个数。有时，也用这些事务占数据库中全部记录的百分比来