Apriori算法

在电商行业里，有一个著名的公式：销售额=UV*转化率*客单价。而提高客单价的一个有效手段就是关联销售或者叫交叉销售（cross-selling）。常见的产品形态就是组合产品、套餐搭配、配件中心等。而不同的商品如何搭配组合才能激发用户最大的购买欲望就是一个关键的问题。今天，就介绍下关联规则的Apriori算法。

一、简介

Apriori算法是最常用的关联规则挖掘算法。由RakeshAgrawal和Ramakrishnan Srikant两位博士在1994年提出。关联规则算法的目的就是在一个数据集中找出项与项之间的关系。在零售领域中，超市通过分析顾客的一张张订单来指导商品的交叉销售，所以也被称为购物蓝分析 (Basket analysis)。关于关联销售最有名的例子就是啤酒与尿布（真实性无证实）。讲的是沃尔玛员工通过订单发现货架相隔很远的啤酒和尿布经常出现在一个订单里，他们走访了顾客，发现妻子总是在上班前叮嘱丈夫记得下班后买尿布回来，结果丈夫在买尿布的同时会顺带买一些啤酒。于是，沃尔玛的员工便把啤酒和尿布放在相邻的位置，结果商品销量大增。

Apriori算法的原理就是说如果某个项是频繁的，那么它的所有子集也是频繁的。也就是说，如果一个项是非频繁的，那么它的所有超集也是非频繁的。

Apriori算法的基本原理是用支持度表示关联规则的强度，把具有关联规则的商品看做一个集合。从最小的集合开始，筛选出支持度大于某个值的集合，然后合并集合，再循环，直到找不集合为止。

二、名词定义

关联规则（association rules）：形如"如果…那么…(If…Then…)",前者为条件，后者为结果。一般表示为A→B。衡量一个规则是否好，可以用支持度和置信度衡量。

支持度（support）：某事件发生的概率。A的支持度就是A被购买的概率：Support(A)=P(A)=num(A)/num(I)。A→B的支持度就是A和B同时购买的概率：Support(A→B)= P(A∩B) =num(A∩B)/num(I)；

置信度（confidence）：在A条件下，A和B共同购买的概率。Confidence(A→B)=P(B|A)=P(A∩B)/P(A)。

提升度（lift）：相对于不用规则，使用规则可以提高多少。Lift(A→B)=Confidence(A→B)/Support(B)=P(B|A)/P(B)。

K项集（K-itemset）:同时购买的商品数量为K的，K项集合。

频繁K项集（frequent itemset）：满足最小支持度阈值的K项集合。

候选K项集（candidate itemset）：通过连接形成的K项集合。

三、原理

步骤：

1.先计算1项集的支持度，筛选出频繁1项集。

2.然后排列组合出2项集，计算出2项集的支持度，筛选出频繁2项集。

3.然后通过连接和剪枝计算出3项集，计算出3项集的支持度，筛选出频繁3项集。

4.然后依次类推处理K项集，直到没有频繁集出现（具体例子参考首图）。

关键：如何从K-1项集计算出K项集（K>=3，K=2时用组合公式C(2,n)即可）

连接：对K-1项集中的每个项集中的项排序，只有在前K-1项相同时才将这两项合并，形成候选K项集（因为必须形成K项集，所以只有在前K-1项相同，第K项不相同的情况下才合并。）

剪枝：对于候选K项集，要验证所有项集的所有K-1子集是否频繁（是否在K-1项集中），去掉不满足的项集，就形成了K项集。

四、局限

传统的Apriori算法的计算量很大，当商品数据量大时更显著，基本是不可计算的，不过后来有人用FP-Tree算法简化了计算量。

电商常用的关联规则应用是单品推荐单品，所以一般只需要知道频繁2项集即可。K>=3的项集并没有被挖掘价值。

商品并不是全部平等销售的，仅使用支持度衡量，容易导致出现假性关联。组合、搭售、买赠、企业采购等订单都会影响。

五、改进

支持度表示在历史中A和B同时购买的概率，置信度表示A推荐B的可信程度。由此可以认为支持度*置信度表示A推荐B而A和B同时购买的概率。这样相比于单纯使用支持度更全面，同时避免了支持度中等或置信度中等的关联规则被淘汰。

因为提升度表示提升单品购买概率的程度，所以可以使用提升度作为最终推荐依据，避免组合、搭售、买赠关系的假性关联。

六、缺点

当数据量很大的时候，运行效率比较低

文章来源：http://www.woshipm.com/pmd/265193.html