数据挖掘算法(1)-Apriori算法 - 20130224 - 读书笔记

一、 算法概念引入

? 什么是关联规则

按常规思维，尿布与啤酒风马牛不相及，若不是借助数据挖掘技术对大量交易数据进行挖掘分析，沃尔玛是不可能发现数据内在这一有价值的规律的。

数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规

则问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；对关联规则的应用进行推广在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。

? 经典案例1：尿布和啤酒的故事 关于这个算法有一个非常有名的故事：\尿布和啤酒\。故事是这样的：美国的妇女们经常会嘱咐她们的丈夫下班后为孩子买尿布，而丈夫在买完尿布后又要顺手买回自己爱喝的啤酒，因此啤酒和尿布在一起被购买的机会很多。这个举措使尿布和啤酒的销量双双增加，并一直为众商家所津津乐道。

? 介绍案例2：床单和枕套的故事 通过调查商场里顾客买的东西发现，30%的顾客会同时购买床单和枕套，而购买床单的人中有80%购买了枕套，这里面就隐藏了一条关联：床单—>枕套，也就是说很大一部分顾客会同时购买床单和枕套，那么对于商场来说，可以把床单和枕套放在同一个购物区，那样就方便顾客进行购物了。

二、 Apriori数据挖掘算法

Apriori algorithm是关联规则里一项基本算法。是由Rakesh Agrawal和

Ramakrishna Srikant两位博士在1994年提出的关联规则挖掘算法。关联规则的目的就是在一个数据集中找出项与项之间的关系，也被称为购物蓝分析 (Market Basket analysis)，因为“购物蓝分析”很贴切的表达了适用该算法情景中的一个子集。

2.1 概念和定义

? 资料库（Transaction Database）：存储着二维结构的记录集。定义为：D ? 所有项集（Items）： 所有项目的集合。定义为：I。

? 记录（Transaction ）：在资料库里的一笔记录。定义为：T，T ∈ D

? 项集（Itemset）： 同时出现的项的集合。定义为：k-itemset（k项集），k-itemset ?

T。除非特别说明，否则下文出现的k均表示项数。 ? 支持度（Support）： 定义为 supp(X) = occur(X)/count(D) = P(X)。

1. 解释一：比如选秀比赛，那个支持和这个有点类似，那么多人（资料库），

其中有多少人是选择（支持）你的，那个就是支持度；

2. 解释二：在100个人去超市买东西的，其中买苹果的有9个人，那就是说

苹果在这里的支持度是 9，9/100；

3. 解释三：P(X)，意思是事件X出现的概率；

4. 解释四：关联规则当中是有绝对支持度（个数）和相对支持度（百分比）

之分的。

? 臵信度（Confidence/Strength）： 定义为 conf(X->Y) = supp(X ∪Y) /supp(X)

= P(Y|X)。

历史数据中，已经买了某某（例如：A、B）的支持度和经过挖掘的某规则（例如：A=>B）中A的支持度的比例，也就是说买了A和B的人和已经买了A的人的比例，这就是对A推荐B的臵信度（A=>B的臵信度）

? 候选集（Candidate itemset）：通过向下合并得出的项集。定义为C[k]。 ? 频繁集（Frequent itemset）：支持度大于等于特定的最小支持度（Minimum

Support/minsup）的项集。表示为L[k]。 注意，频繁集的子集一定是频繁集。 ? 提升比率（提升度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))

经过关联规则分析后，针对某些人推销（根据某规则）比盲目推销（一般来说是整个数据）的比率，这个比率越高越好，我们称这个规则为强规则；

? 剪枝步

只有当子集都是频繁集的候选集才是频繁集，这个筛选的过程就是剪枝步；

2.2 概念和定义的案例说明

先看一个简单的例子，假如有下面数据集，每一组数据ti表示不同的顾客一次在商场购买的商品的集合：

假如有一条规则：牛肉—>鸡肉，那么同时购买牛肉和鸡肉的顾客比例是3/7（支持度），而购买牛肉的顾客当中也购买了鸡肉的顾客比例是3/4（臵信度）。这两个比例参数是很重要的衡量指标，它们在关联规则中称作支持度（support）和臵信度（confidence）。

对于规则：牛肉—>鸡肉，它的支持度为3/7，表示在所有顾客当中有3/7同时购买牛肉和鸡肉，其反应了同时购买牛肉和鸡肉的顾客在所有顾客当中的覆盖范围；它的臵信度为3/4，表示在买了牛肉的顾客当中有3/4的人买了鸡肉，其反应了可预测的程度，即顾客买了牛肉的话有多大可能性买鸡肉。

从集合角度去看这个问题， 假如看作是概率问题，则可以把“顾客买了牛肉之后又多大可能性买鸡肉”看作是条件概率事件，而从集合的角度去看，可以看下面这幅图：

S表示所有的顾客，而A表示买了牛肉的顾客，B表示买了鸡肉的顾客，C表示既买了牛肉又买了鸡肉的顾客。那么

C.count/S.count=3/7，C.count/A.count=3/4。

上述例子中的所有商品集合I={牛肉，鸡肉，牛奶，奶酪，靴子，衣服}称作项目集

合，每位顾客一次购买的商品集合ti称为一个事务，所有的事务T={t1,t2,....t7}称作事务集合，并且满足ti是I的真子集。一条关联规则是形如下面的蕴含式： X—>Y，X，Y满足：X，Y是I的真子集，并且X和Y的交集为空集 其中X称为前件，Y称为后件。 对于规则X—>Y，上面例子可以知道它的支持度(support)=(X,Y).count/T.count，臵信度(confidence)=(X,Y).count/X.count。其中(X,Y).count表示T中同时包含X和Y的事务的个数，X.count表示T中包含X的事务的个数。

关联规则挖掘则是从事务集合中挖掘出满足支持度和臵信度最低阈值要求的所有关联规则，这样的关联规则也称强关联规则。 对于支持度和臵信度，我们需要正确地去看待这两个衡量指标。一条规则的支持度表示这条规则的可能性大小，如果一个规则的支持度很小，则表明它在事务集合中覆盖范围很小，很有可能是偶然发生的；如果臵信度很低，则表明很难根据X推出Y。根据条件概率公式P(Y|X)=P(X,Y)/P(X)，即P(X,Y)=P(Y|X)*P(X)

P(Y|X)代表着臵信度，P(X,Y)代表着支持度，所以对于任何一条关联规则臵信度总是大于等于支持度的。

并且当支持度很高时，此时的臵信度肯定很高，它所表达的意义就不是那么有用了。这里要注意的是支持度和臵信度只是两个参考值而已，并不是绝对的，也就是说假如一条关联规则的支持度和臵信度很高时，不代表这个规则之间就一定存在某种关联。 举个最简单的例子，假如X和Y是最近的两个比较热门的商品，大家去商场都要买，比如某款手机和某款衣服，都是最新款的，深受大家的喜爱，那么这条关联规则的支持度和臵信度都很高，但是它们之间没有必然的联系。然而当臵信度很高时，支持度仍然具有参考价值，因为当P(Y|X)很高时，可能P(X)很低，此时P(X,Y)也许会很低。

2.3 关联规则挖掘的原理和过程

从上面的分析可知，关联规则挖掘是从事务集合中挖掘出这样的关联规则：

它的支持度和臵信度大于最低阈值（minsup,minconf），这个阈值是由用户指定的。根据支持度=(X,Y).count/T.count，臵信度=(X,Y).count/X.count ，要想找出满足条件的关联规则，首先必须找出这样的集合F=X U Y ，它满足F.count/T.count ≥ minsup，其中F.count是T中包含F的事务的个数，然后再从F中找出这样的蕴含式X—>Y，

它满足(X,Y).count/X.count ≥ minconf，并且X=F-Y。我们称像F这样的集合称为频繁项目集，假如F中的元素个数为k，我们称这样的频繁项目集为k-频繁项目集，它是项目集合I的子集。所以关联规则挖掘可以大致分为两步： 1）从事务集合中找出频繁项目集；

2）从频繁项目集合中生成满足最低臵信度的关联规则。 最出名的关联规则挖掘算法是Apriori算法，它主要利用了向下封闭属性：如果一个项集是频繁项目集，那么它的非空子集必定是频繁项目集。它先生成1-频繁项目集，再利用1-频繁项目集生成2-频繁项目集。。。然后根据2-频繁项目集生成3-频繁项目集。。。依次类推，直至生成所有的频繁项目集，然后从频繁项目集中找出符合条件的关联规则。

下面来讨论一下频繁项目集的生成过程，它的原理是根据k-频繁项目集生成（k+1）-频繁项目集。因此首先要做的是找出1-频繁项目集，这个很容易得到，只要循环扫描一次事务集合统计出项目集合中每个元素的支持度，然后根据设定的支持度阈值进行筛选，即可得到1-频繁项目集。下面证明一下为何可以通过k-频繁项目集生成（k+1）-频繁项目集：

假设某个项目集S={s1，s2...，sn}是频繁项目集，那么它的（n-1）非空子集{s1，s2，...sn-1}，{s1，s2，...sn-2，sn}...{s2，s3，...sn}必定都是频繁项目集，通过观察，任何一个含有n个元素的集合A={a1，a2，...an}，它的（n-1）非空子集必行包含两项{a1，a2，...an-2，an-1}和 {a1，a2，...an-2，an}，对比这两个子集可以发现，它们的前（n-2）项是相同的，它们的并集就是集合A。对于2-频繁项目集，它的所有1非空子集也必定是频繁项目集，那么根据上面的性质，对于2-频繁项目集中的任一个，在1-频繁项目集中必定存在2个集合的并集与它相同。因此在所有的1-频繁项目集中找出只有最后一项不同的集合，将其合并，即可得到所有的包含2个元素的项目集，得到的这些包含2个元素的项目集不一定都是频繁项目集，所以需要进行剪枝。剪枝的办法是看它的所有1非空子集是否在1-频繁项目集中，如果存在1非空子集不在1-频繁项目集中，则将该2项目集剔除。经过该步骤之后，剩下的则全是频繁项目集，即2-频繁项目集。依次类推，可以生成3-频繁项目集。直至生成所有的频繁项目集。

得到频繁项目集之后，则需要从频繁项目集中找出符合条件的关联规则。最简单的办法是：遍历所有的频繁项目集，然后从每个项目集中依次取1、2、...k个元素作为后件，该项目集中的其他元素作为前件，计算该规则的臵信度进行筛选即可。这样的穷举效率显然很低。假如对于一个频繁项目集f，可以生成下面这样的关联规则： （f-β）—>β

那么这条规则的臵信度=f.count/(f-β).count

根据这个臵信度计算公式可知，对于一个频繁项目集f.count是不变的，而假设该规则是强关联规则，则（f-βsub）—>βsub也是强关联规则，其中βsub是β的子集，因为(f-βsub).count肯定小于(f-β).count。即给定一个频繁项目集f，如果一条强关联规则的后件为β，那么以β的非空子集为后件的关联规则都是强关联规则。所以可以先生成所有的1-后件（后件只有一项）强关联规则，然后再生成2-后件强关联规则，依次类推，直至生成所有的强关联规则。

下面举例说明Apiori算法的具体流程：

假如有项目集合I={1，2，3，4，5}，有事务集T：

1,2,3

1,2,4 1,3,4 1,2,3,5 1,3,5 2,4,5 1,2,3,4

设定minsup=3/7，misconf=5/7。 首先：生成频繁项目集：

1-频繁项目集：{1}，{2}，{3}，{4}，{5} 生成2-频繁项目集：

根据1-频繁项目集生成所有的包含2个元素的项目集：任意取两个只有最后一个元素不同的1-频繁项目集，求其并集，由于每个1-频繁项目集元素只有一个，所以生成的项目集如下： {1，2}，{1，3}，{1，4}，{1，5} {2，3}，{2，4}，{2，5} {3，4}，{3，5} {4，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，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-频繁项目集，这个原因很简单，因为事务集合中的所有事务都不包含（k+1）个元素，所以不可能存在（k+1）-频繁项目集。在生成过程中，若得到的频繁项目集个数小于2，生成过程也可以结束了。 现在需要生成强关联规则：

这里只说明3-频繁项目集生成关联规则的过程： 对于集合{1，2，3} 先生成1-后件的关联规则： （1，2）—>3， 置信度=3/4 （1，3）—>2， 置信度=3/5 （2，3）—>1 置信度=3/3

（1，3）—>2的置信度不满足要求，所以剔除掉。因此得到1后件的集合{1}，{3}，然后再以{1，3}作为后件

2—>1，3 置信度=3/5不满足要求，所以对于3-频繁项目集生成的强关联规则为：（1，2）—>3和（2，3）—>1。 算法实现：

本文来源：https://www.bwwdw.com/article/kt6f.html