数据挖掘十大算法之Apriori算法

Apriori 算法

Apriori 算法是一种最有影响力的挖掘布尔关联规则的频繁项集的 算法,它是由Rakesh Agrawal 和RamakrishnanSkrikant 提出的。它使用一种称作逐层搜索的迭代方法,k- 项集用于探索(k+1)- 项集。首先,找出频繁 1- 项集的集合。该集合记作L1。L1 用于找频繁2- 项集的集合 L2,而L2 用于找L2,如此下去,直到不能找到 k- 项集。每找一个 Lk 需要一次数据库扫描。为提高频繁项集逐层产生的效率,一种称作Apriori 性质的重 要性质 用于压缩搜索空间。其运行定理在于一是频繁项集的所有非空子集都必须也是频繁的,二是非频繁项集的所有父集都是非频繁的。

Apriori算法的向下封闭属性

Apriori算法采用向下封闭属性(Downward Closure Property):如果一个项集满足某个最小支持度要求,那么这个项集的任何非空子集必须都满足这个最小支持度。

问题的引入

购物篮分析:引发性例子
Question:哪组商品顾客可能会在一次购物时同时购买?
关联分析
Solutions:
1:经常同时购买的商品可以摆近一点,以便进一步刺激这些商品一起销售。
2:规划哪些附属商品可以降价销售,以便刺激主体商品的捆绑销售。

关联分析的基本概念

支持度

关联规则A→B的支持度support=P(AB),指的是事件A和事件B同时发生的概率。

置信度

置信度confidence=P(B│A)=P(AB)/P(A) ,指的是发生事件A的基础上发生事件B的概率。比如说在规则Computer → antivirus_software , 其中 support=2%, confidence=60%中,就表示的意思是所有的商品交易中有2%的顾客同时买了电脑和杀毒软件,并且购买电脑的顾客中有60%也购买了杀毒软件。

k项集

如果事件A中包含k个元素,那么称这个事件A为k项集,并且事件A满足最小支持度阈值的事件称为频繁k项集。

由频繁项集产生强关联规则

1、K维数据项集L_K 是频繁项集的必要条件是它所有K-1维子项集也为频繁项集,记为L_(K−1);
2、如果K维数据项集L_K 的任意一个K-1维子集L_(k−1),不是频繁项集,则K维数据项集L_K 本身也不是最大数据项集。
3、L_k 是K维频繁项集,如果所有K-1维频繁项集合L_(k−1) 中包含L_K 的K-1维子项集的个数小于K,则L_k 不可能是K维最大频繁数据项集。
4、同时满足最小支持度阀值和最小置信度阀值的规则称为强规则。

例如:用一个简单的例子说明。表1是顾客购买记录的数据库D,包含6个事务。项集I={网球拍,网球,运动鞋,羽毛球}。考虑关联规则:网球拍→ 网球,事务1,2,3,4,6包含网球拍,事务1,2,6同时包含网球拍和网球,支持度support=3/6=0.5,置信度confident=3/5=0.6。若给定最小支持度 α=0.5,最小置信度 β=0.6,关联规则网球拍 → 网球是有趣的,认为购买网球拍和购买网球之间存在强关联。

Apriori算法的基本思想

Apriori算法过程分为两个步骤:

1、通过迭代,检索出事务数据库中的所有频繁项集,即支持度不低于用户设定的阈值的项集;
2、利用频繁项集构造出满足用户最小信任度的规则

具体做法

首先找出频繁1-项集,记为L1;然后利用L1来产生候选项集C2,对C2中的项进行判定挖掘出L2,即频繁2-项集;不断如此循环下去直到无法发现更多的频繁k-项集为止。每挖掘一层Lk就需要扫描整个数据库一遍。程序伪代码如下:
85323216.jpg

算法利用了一个性质:

Apriori 性质:任一频繁项集的所有非空子集也必须是频繁的。意思就是说,生成一个k-itemset的候选项时,如果这个候选项有子集不在(k-1)-itemset(已经确定是frequent的)中时,那么这个候选项就不用拿去和支持度判断了,直接删除。程序伪代码如下:
59927789.jpg

具体而言:

合并(上图地2~6行):

为找出L_k (所有的频繁k项集的集合),通过将L_(k−1) (所有的频繁k-1项集的集合)与自身连接产生候选k项集的集合。候选集合记作C_k 。设l_1 和l_2 是L_(k−1) 中的成员。记l_i [j]表示l_i 中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序,即对于(k-1)项集l_i,l_i [1]<l_i [2]…<l_i [k−1]。将L_(k−1) 与自身连接,如果(l_1 [1]=l_2 [1])&&( l_1 [2]=l_2 [2])&&……..&& (l_1 [k−2]=l_2 [k−2])&&(l_1 [k−1]<l_2 [k−1]),那认为l_1 和l_2 是可连接。连接l_1 和l_2 产生的结果是{l_1 [1],l_1 [2]],……,l_1 [k−1],l_2 [k−1]}。

剪枝(上图8~11行):

C_k 是L_k 的超集,也就是说,C_k 的成员可能是也可能不是频繁的。通过扫描所有的事务(交易),确定C_k 中每个候选的计数,判断是否小于最小支持度计数,如果不是,则认为该候选是频繁的。为了压缩C_k,可以利用Apriori性质:任一频繁项集的所有非空子集也必须是频繁的,反之,如果某个候选的非空子集不是频繁的,那么该候选肯定不是频繁的,从而可以将其从C_k 中删除。

关联规则的生成

设α为f的任一非空子集,则可生成如下的一条关联规则:(f−α)→α,如果满足置信度=(f.count)/((f−α).count)≥minconf其中f.count(或(f−α).count)是f(或(f−α))的支持计数。

根据这个置信度计算公式可知,对于一个频繁项目集f.count是不变的,而假设该规则是强关联规则,则(f−α_sub)→α_sub 也是强关联规则,其中α_sub 是α的子集,因为(f−α_sub).count肯定小于(f−α).count。即给定一个频繁项目集f,如果一条强关联规则的后件为α,那么以α的非空子集为后件的关联规则都是强关联规则。所以可以先生成所有的1-后件(后件只有一项)强关联规则,然后再生成2-后件强关联规则,依次类推,直至生成所有的强关联规则。程序伪代码如下;
51454749.jpg

数据

编号 数据
1 1,2,3
2 1,2,4
3 1,3,4
4 1,2,3,5
5 1,3,5
6 2,4,5
7 1,2,3,4

例如,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

实例说明一

假设有一个数据库D,其中有4个事务记录,分别表示为:

TID Items
T1 I1,I3,I4
T2 I2,I3,I5
T3 I1,I2,I3,I5
T5 I2,I5

这里预定最小支持度minSupport=2,下面用图例说明算法运行的过程:

1、扫描D,对每个候选项进行支持度计数得到表C1:

项集 支持度计数
{I1} 2
{I2} 3
{I3} 3
{I4} 1
{I5} 3

2、比较候选项支持度计数与最小支持度minSupport,产生1维最大项目集L1:

|项集| 支持度计数|
|{I1}| 2|
|{I2}| 3|
|{I3}| 3|
|{I5}| 3|

3、由L1产生候选项集C2并且扫描D,对每个候选项集进行支持度计数:

项 集 支持度计数
{I1,I2} 1
{I1,I3} 2
{I1,I5} 1
{I2,I3} 2
{I2,I5} 3
{I3,I5} 2

4、比较候选项支持度计数与最小支持度minSupport,产生2维最大项目集L2:

项 集 支持度计数
{I1,I3} 2
{I2,I3} 2
{I2,I5} 3
{I3,I5} 2

5、由L2产生候选项集C3并且比较候选项支持度计数与最小支持度minSupport,产生3维最大项目集L3:

项集 支持度计数
{I2,I3,I5} 2

强关联规则生成:

规则 支持度 置信度
I2,I3→I5 2/4=0.5 2/2=1
I2,I5→I3 2/4=0.5 2/3=0.67
I3,I5→I2 2/4=0.5 2/2=1

实例二

94981965.jpg

分析如下:

1、连接:C_3=L_2 L_2= {{A,C},{B,C},{B,E}{C,E}} {{A,C},{B,C},{B,E}{C,E}} = {{A,B,C},{A,C,E},{B,C,E}}

2、使用Apriori性质剪枝:频繁项集的所有子集必须是频繁的,对候选项C_3,我们可以删除其子集为非频繁的选项:
        {A,B,C}的2项子集是{A,B},{A,C},{B,C},其中{A,B}不是L2的元素,所以删除这个选项;
        {A,C,E}的2项子集是{A,C},{A,E},{C,E},其中{A,E} 不是L2的元素,所以删除这个选项;
        {B,C,E}的2项子集是{B,C},{B,E},{C,E},它的所有2-项子集都是L2的元素,因此保留这个选项。

3、剪枝后得到C_3={{B,C,E}}

Apriori算法的优缺点:

优点:简单、易理解、数据要求低。

缺点:

1、在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素;

2、每次计算项集的支持度时,都对数据库D中的全部记录进行了一遍扫描比较,如果是一个大型的数据库的话,这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法