数据挖掘算法-Apriori Algorithm(关联规则)

jopen 6年前

 

数据挖掘算法-Apriori Algorithm(关联规则)

Apriori algorithm是关联规则里一项基本算法。是由Rakesh Agrawal和Ramakrishnan Srikant两位博士在1994年提出的关联规则挖掘算法。关联规则的目的就是在一个数据集中找出项与项之间的关系,也被称为购物蓝分析 (Market Basket analysis),因为“购物蓝分析”很贴切的表达了适用该算法情景中的一个子集。关于这个算法有一个非常有名的故事:"尿布和啤酒"。故事是这样的: 美国的妇女们经常会嘱咐她们的丈夫下班后为孩子买尿布,而丈夫在买完尿布后又要顺 手买回自己爱喝的啤酒,因此啤酒和尿布在一起被购买的机会很多。这个举措使尿布和啤酒的销量双双增加,并一直为众商家所津津乐道。

一.一些概念和定义

1.定义1 项目与项集

设I={i1,i2,…,im}是m个不同项目的集合,每个ik(k=1,2,……,m)称为一个项目(Item)。项目的集合 I 称为项目集合(Itemset),简称为项集。其元素个数称为项集的长度,长度为k的项集称为k-项集(k-Itemset)。

2.定义2 交易

每笔交易T(Transaction)是项集I上的一个子集,即T 数据挖掘算法-Apriori Algorithm(关联规则) I,但通常T 数据挖掘算法-Apriori Algorithm(关联规则) I。

对应每一个交易有一个唯一的标识——交易号,记作TID

交易的全体构成了交易数据库D,或称交易记录集D,简称交易集D。

交易集D中包含交易的个数记为|D|。

3.定义3 项集的支持度

对于项集X,X 数据挖掘算法-Apriori Algorithm(关联规则) I,设定count(X 数据挖掘算法-Apriori Algorithm(关联规则) T)为交易集D中包含X的交易的数量

数据挖掘算法-Apriori Algorithm(关联规则)

项集X的支持度support(X)就是项集X出现的概率,从而描述了X的重要性。

4.定义4 项集的最小支持度与频繁集

发现关联规则要求项集必须满足的最小支持阈值,称为项集的最小支持度(Minimum Support),记为supmin。

支持度大于或等于supmin的项集称为频繁项集,简称频繁集,反之则称为非频繁集。

通常k-项集如果满足supmin,称为k-频繁集,记作Lk 。

5.定义5 关联规则

关联规则(Association Rule)可以表示为一个蕴含式:

数据挖掘算法-Apriori Algorithm(关联规则)

其中: 数据挖掘算法-Apriori Algorithm(关联规则)

例如:R:牛奶→面包

6.定义6 关联规则的支持度

数据挖掘算法-Apriori Algorithm(关联规则)

规则R的的支持度(Support)是交易集中同时包含X和Y的交易数与所有交易数之比。

数据挖掘算法-Apriori Algorithm(关联规则)

例如:在5条记录中,既有橙汁又有可乐的记录有2条。则此条规则的支持度为 2/5=0.4,即Support(A-〉B)=P(AB)。

数据挖掘算法-Apriori Algorithm(关联规则)

7.定义7 关联规则的置信度

数据挖掘算法-Apriori Algorithm(关联规则)

规则R的置信度(Confidence)是指包含X和Y的交易数与包含X的交易数之比

数据挖掘算法-Apriori Algorithm(关联规则)

例如:计算“如果Orange则Coke”的置信度。由于在含有“橙汁”的4条交易中,仅有2条交易含有“可乐”。其置信度为0.5。

8.定义8 关联规则的最小支持度和最小置信度

关联规则的最小支持度也就是衡量频繁集的最小支持度(Minimum Support),记为supmin,它用于衡量规则需要满足的最低重要性。关联规则的最小置信度(Minimum Confidence)记为confmin,它表示关联规则需要满足的最低可靠性。

9.定义9 强关联规则

数据挖掘算法-Apriori Algorithm(关联规则) ,称关联规则X=》Y为强关联规则,否则称关联规则X=》Y为弱关联规则。

在挖掘关联规则时,产生的关联规则要经过supmin和confmin的衡量,筛选出来的强关联规则才能用于指导商家的决策。

10.候选集(Candidate itemset):通过向下合并得出的项集。定义为C[k]。 11.频繁集(Frequent itemset):支持度大于等于特定的最小支持度(Minimum Support/minsup)的项集。表示为L[k]。注意,频繁集的子集一定是频繁集。 12.提升比率(提升度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)) 经过关联规则分析后,针对某些人推销(根据某规则)比盲目推销(一般来说是整个数据)的比率,这个比率越高越好,我们称这个规则为强规则;

13.剪枝步:只有当子集都是频繁集的候选集才是频繁集,这个筛选的过程就是剪枝步。

二. Apriori Algorithm(关联规则)动态演示 点击下载ppt观看

三.Apriori Algorithm(关联规则)算法描述

Apriori 算法采用的方法为:首先产生频繁 1-项集 L1,然后用 L1经过自连接、剪枝生成 L2,频繁 2-项集 L2又用来生成 L3,以此类推,逐层迭代,直到无法产生新的频繁项集为止。然后根据给定的最小可信度,利用生成的频繁项集产生关联规则。

数据挖掘算法-Apriori Algorithm(关联规则)

1.产生频繁项集 该过程可以通过以下步骤实现:

1)  第一阶段,所有单独的项都是候选项集 C1。任何支持度值比给定的最小支持度值小的项都将从候选项集 C1中剔除,形成频繁 1-项集 L1。

2)  两个 L1通过自连接形成具有 2 个项的候选项集 C2。通过再次扫描数据库决定这些候选项的支持度。保留比预先给定的最小支持度大的候选项,形成频繁 2-项集L2。

3)  下一步形成含有 3 个项的候选项集 C3,重复上述步骤,直到找到所有的频繁项集为止。

Apriori 算法的伪码描述如下所示:

输入:数据集 D,min_sup输出:D 中的频繁项集 L

数据挖掘算法-Apriori Algorithm(关联规则)

2.产生关联规则

从事务数据库 D 中挖掘出频繁所有的频繁项集后,就可以比较容易的获得相应的关联规则,即满足可信度min_conf 的频繁项集产生强关联规则。由于规则是由频繁项集产生,所以每个规则自动满足 min_sup。

在用频繁项 X 生成关联的伪码如下:

输入:Yk,Lk,min_conf输出:形如 X=》Y 的关联规则

数据挖掘算法-Apriori Algorithm(关联规则)

-------------------------------------------------------------------------------------------------------------------------------------