数据挖掘算法Apriori算法

1、一、 算法概念引入什么是关联规则按常规思维，尿布与啤酒风马牛不相及，若不是借助数据挖掘技术对大量交易数据进 行挖掘分析，沃尔玛是不可能发现数据内在这一有价值的规律的。数据关联是数据库中存在的一类重要的可被发现的 知识。若两个或多个变量的取值之间存在某种规律性，就 称为关联。关联可分为简单关联、时序关联、因果关联。 关联分析的目的是找出数据库中隐藏的关联网。有时并不 知道数据库中数据的关联函数，即使知道也是不确定的， 因此关联分析生成的规则带有可信度。关联规则挖掘发现 大量数据中项集之间有趣的关联或相关联系。Agrawal等于 1993年首先提出了挖掘顾客交易数据库中项集间的关联规 则问题，以后

2、诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对 原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；对关 联规则的应用进行推广在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。经典案例1：尿布和啤酒的故事关于这个算法有一个非常有名的故事：尿布和啤酒。故事是这样的：美国的妇女们经 常会嘱咐她们的丈夫下班后为孩子买尿布，而丈夫在买完尿布后又要顺手买回自己爱喝的啤 酒，因此啤酒和尿布在一起被购买的机会很多。这个举措使尿布和啤酒的销量双双增加，并 一直为众商家所津津乐道。介绍案例2：床单和枕套的故事通过调查商场里顾客买的东西发现，30%的顾客会同时

3、购买床单和枕套，而购买床单的 人中有80%购买了枕套，这里面就隐藏了一条关联：床单一枕套，也就是说很大一部分顾 客会同时购买床单和枕套，那么对于商场来说，可以把床单和枕套放在同一个购物区，那样 就方便顾客进行购物了。二、Apriori数据挖掘算法Apriori algorithm是关联规则里一项基本算法。是由Rakesh Agrawal和Ramakrishna Srikant两位博士在1994年提出的关联规则挖掘算法。关联规则的目的就是在一个数据集中找出项与项之间的关系，也被称为购物蓝分析(Market Basket analysis)，因为“购物蓝分析”很贴切的表达了适用该算法情景中的一个子

4、集。概念和定义1 ti&m s etS Lip .1rm卜Ir|目Y) = supp(X UY) /supp(X) =P(Y|X)。历史数据中，已经买了某某(例如：A、B)的支持度和经过挖掘的某规则(例如： A=B)中A的支持度的比例，也就是说买了入和日的人和已经买了入的人的比例，这就 是对A推荐B的置信度(A=B的置信度)候选集(Candidate itemset):通过向下合并得出的项集。定义为Ck。频繁集(Frequent itemset):支持度大于等于特定的最小支持度(Minimum Support/minsup)的项集。表示为 Lk。注意，频繁集的子集一定是频繁集。提升比率(提升度

5、 Lift): lift(X - Y) = lift(Y - X) = conf(X - Y)/supp(Y) = conf(Y - X)/supp(X) = P(X and Y)/(P(X)P(Y)经过关联规则分析后，针对某些人推销(根据某规则)比盲目推销(一般来说是整个数 据)的比率，这个比率越高越好，我们称这个规则为强规则；剪枝步只有当子集都是频繁集的候选集才是频繁集，这个筛选的过程就是剪枝步；概念和定义的案例说明先看一个简单的例子，假如有下面数据集，每一组数据ti表示不同的顾客一次在商场 购买的商品的集合：tit.4牛肉、鸡肉牛奶牛肉、蛆酪2奶酪、靴子彖牛肉、鸦肉、奶酪牛肉、器肉衣服奶

6、酷I牛奶尸鸡肉、衣服、牛蛆鸡肉、牛奶、衣服J假如有一条规则：牛肉一鸡肉，那么同时购买牛肉和鸡肉的顾客比例是3/7 (支持度)， 而购买牛肉的顾客当中也购买了鸡肉的顾客比例是3/4 (置信度)。这两个比例参数是很重 要的衡量指标，它们在关联规则中称作支持度(support)和置信度(confidence) o对于规则：牛肉一鸡肉，它的支持度为3/7,表示在所有顾客当中有3/7同时购买牛 肉和鸡肉，其反应了同时购买牛肉和鸡肉的顾客在所有顾客当中的覆盖范围；它的置信度为 3/4,表示在买了牛肉的顾客当中有3/4的人买了鸡肉，其反应了可预测的程度，即顾客 买了牛肉的话有多大可能性买鸡肉。从集合角度去看

7、这个问题，假如看作是概率问题，则可以把“顾客买了牛肉之后又多 大可能性买鸡肉”看作是条件概率事件，而从集合的角度去看，可以看下面这幅图：S表示所有的顾客，而A表示买了牛肉的 顾客，B表示买了鸡肉的顾客，C表示既买了 牛肉又买了鸡肉的顾客。那么C. /S,=3/7, C. /A,=3/4。count countcount count上述例子中的所有商品集合I=牛肉， 鸡肉，牛奶，奶酪，靴子，衣服称作项目集合，每位顾客一次购买的商品集合ti称为一个事务，所有的事务T=t1,t2,.t7称作事务 集合，并且满足ti是I的真子集。一条关联规则是形如下面的蕴含式：XY，X，Y满足：X，Y是I的真子集，并

8、且X和Y的交集为空集其中X称为前件，Y称为后件。对于规则XY，上面例子可以知道它的支持度(support)=(X,Y).count/T.count，置 信度(confidence)=(X,Y).count/X.count。其中(X,Y).count 表示T 中同时包含X 和 Y 的 事务的个数，X.count表示T中包含X的事务的个数。关联规则挖掘则是从事务集合中挖掘出满足支持度和置信度最低阈值要求的所有关联 规则，这样的关联规则也称强关联规则。对于支持度和置信度，我们需要正确地去看待这两个衡量指标。一条规则的支持度表示 这条规则的可能性大小，如果一个规则的支持度很小，则表明它在事务集合中覆盖

9、范围很小， 很有可能是偶然发生的；如果置信度很低，则表明很难根据乂推出丫。根据条件概率公式 P(Y|X)=P(X,Y)/P(X)，即 P(X,Y)=P(Y|X)*P(X)P(Y|X)代表着置信度，P(X,Y)代表着支持度，所以对于任何一条关联规则置信度总是 大于等于支持度的。并且当支持度很高时，此时的置信度肯定很高它所表达的意义就不是那么有用了这 里要注意的是支持度和置信度只是两个参考值而已，不是绝对的，也就是说假如一条关联 规则的支持度和置信度很高时，不代表这个规则之间就一定存在某种关联。举个最简单的例子，假如X和Y是最近的两个比较热门的商品，大家去商场都要买， 比如某款手机和某款衣服，都是

10、最新款的，深受大家的喜爱，那么这条关联规则的支持度和 置信度都很高，但是它们之间没有必然的联系。然而当置信度很高时，支持度仍然具有参考 价值，因为当P(Y|X)很高时，可能P(X)很低，此时P(X,Y)也许会很低。关联规则挖掘的原理和过程从上面的分析可知，关联规则挖掘是从事务集合中挖掘出这样的关联规则：它的支持度和置信度大于最低阈值(minsup,minconf)，这个阈值是由用户指定 的。根据支持度=(X,Y)./T.，置信度=(X,Y)./X.，要想找出满足条件的count countcount count关联规则，首先必须找出这样的集合F=X U Y，它满足F.匚t minsup， 其中

11、F.count是T中包含F的事务的个数，然后再从F中找出这样的蕴含式XY， 它满足(X,Y). t/X. t minconf,并且X=F-Y。我们称像F这样的集合称为频繁 项目集，假疝0岸中的芫素个数为k，我们称这样的频繁项目集为k-频繁项目集，它是 项目集合I的子集。所以关联规则挖掘可以大致分为两步：从事务集合中找出频繁项目集；从频繁项目集合中生成满足最低置信度的关联规则。最出名的关联规则挖掘算法是Apriori算法，它主要利用了向下封闭属性：如果一 个项集是频繁项目集，那么它的非空子集必定是频繁项目集。它先生成1-频繁项目集， 再利用1-频繁项目集生成2-频繁项目集。然后根据2-频繁项目集

12、生成3-频繁项目 集。依次类推，直至生成所有的频繁项目集，然后从频繁项目集中找出符合条件的 关联规则。下面来讨论一下频繁项目集的生成过程，它的原理是根据蚪频繁项目集生成(k+1) -频繁项目集。因此首先要做的是找出1-频繁项目集，这个很容易得到，只要循环扫描 一次事务集合统计出项目集合中每个元素的支持度，然后根据设定的支持度阈值进行筛 选，即可得到1-频繁项目集。下面证明一下为何可以通过k-频繁项目集生成(k+1)- 频繁项目集：假设某个项目集S=s，s .，s是频繁项目集，那么它的(n-1)非空子集s， TOC o 1-5 h z 12n1s，.s ，s，s，.s s .s，s，.s 必定都

13、是频繁项目集，通过观察，任何 2n-112n-2， n 23n一个含有n个元素的集合A=a，a，.a，它的(n-1)非空子集必行包含两项a，12n1a，.a ，a 和a，a，.a ，a ，对比这两个子集可以发现，它们的前。-2)2n-2n-112n-2 n项是相同的，它们的并集就是集合A。对于2-频繁项目集，它的所有1非空子集也必 定是频繁项目集，那么根据上面的性质，对于2-频繁项目集中的任一个，在1-频繁项 目集中必定存在2个集合的并集与它相同。因此在所有的1-频繁项目集中找出只有最 后一项不同的集合，将其合并，即可得到所有的包含2个元素的项目集，得到的这些包 含2个元素的项目集不一定都是频

14、繁项目集，所以需要进行剪枝。剪枝的办法是看它的 所有1非空子集是否在1-频繁项目集中，如果存在1非空子集不在1-频繁项目集中， 则将该2项目集剔除。经过该步骤之后，剩下的则全是频繁项目集，即2-频繁项目集。 依次类推，可以生成3-频繁项目集。直至生成所有的频繁项目集。得到频繁项目集之后，则需要从频繁项目集中找出符合条件的关联规则。最简单的 办法是：遍历所有的频繁项目集，然后从每个项目集中依次取1、2、.k个元素作为 后件，该项目集中的其他元素作为前件，计算该规则的置信度进行筛选即可。这样的穷 举效率显然很低。假如对于一个频繁项目集f，可以生成下面这样的关联规则： (f-6)一6那么这条规则的置

15、信度=土t/(f-6). t根据这个置信度计算公式可知，对于一个频繁项目集f_nt是不变的，而假设该规 则是强关联规则，则(f-6 b)一6 b也是强关联规则，其中莅b是6的子集，因为(f-6 b). t肯定小于(f-6).即给定一个频繁项目集f，如果一藁强关联规则的后件为6,那么H以&的非空子集为后洋的关联规则都是强关联规则。所以可以先生成所有的1-后件 (后件只有一项)强关联规则，然后再生成2-后件强关联规则，依次类推，直至生成 所有的强关联规则。下面举例说明Apiori算法的具体流程：假如有项目集合1=1，2, 3, 4, 5，有事务集T：1,2,31,2,41,3,41,2,3,51,

16、3,52,4,51,2,3,4命定 minsup=3/7 , misconf=5/7。首先：生成频繁项目集：1-频繁项目集：1，3，4，5生成2-频繁项目集：根据1-频繁项目集生成所有的包含2个元素的项目集：任意取两个只有最后一个元素不同 的1-频繁项目集，求其并集，由于每个1-频繁项目集元素只有一个，所以生成的项目集如下：1，2，1，3，1，4，1，52,3，2,4，2, 53,4，3, 54,5计算它们的支持度，发现只有1，2，1，3，1，4，2,3，2,4，2,5的支持度 满足要求，因此求得2-频繁项目集：1，2，1，3，1，4，2,3，2,4生成3-频繁项目集：因为1，2，1，3，1，

17、4除了最后一个元素以外都相同，所以求1，2，1，3的并集 得到1，2,3，1，2和1，4的并集得到1，2,4，1，3和1，4的并集得到1，3,4。 但是由于1，3，4的子集3，4不在2-频繁项目集中，所以需要把1，3，4剔除掉。然后再来 计算1，2，3和1，2，4的支持度，发现1，2，3的支持度为3/7，1，2,4的支持度为 2/7，所以需要把1，2，4剔除。同理可以对2，3，2,4求并集得到2，3,4，但是2， 3,4的支持度不满足要求，所以需要剔除掉。因此得到3-频繁项目集：1，2,3。到此频繁项目集生成过程结束。注意生成频繁项目集的时候，频繁项目集中的元素个数最大 值为事务集中事务中含有的最大元素个数，即若事务集中事务包含的最大元素个数为k，那么最 多能生成k-频繁项目集，这个原因很简单，因为事务集合中的所有事务都不