基于关联规则的推荐算法

1.1算法简介

基于关联规则的推荐是根据历史数据统计不同规则出现的关系，形如：X->Y，表示X事件发生后，Y事件会有一定概率发生，这个概率是通过历史数据统计而来。关联规则的目的在于在一个数据集中找出项之间的关系，也称之为购物篮分析 (market basket analysis)。例如，购买鞋的顾客，有10%的可能也会买袜子，60%的买面包的顾客，也会买牛奶。这其中最有名的例子就是'尿布和啤酒'的故事了。

对于一个规则X->Y，有两个指标对该规则进行衡量。一个是支持度，表示在所有样本数据中，同时包含X和Y样本的占比。另一个是置信度，表示在所有包含X的样本中，包含Y的样本占比。

在关联推荐算法中，最主要的是如何找到最大频繁项，业界主要的做法有两种，分别为Apriori算法和FP树。

关联规则的一般步骤
找到频繁集；
在频繁集中通过可信度筛选获得关联规则。

Apriori算法是生成频繁集的一种算法。Apriori原理有个重要假设，如果某个项集是频繁的，那么它的所有子集势必也是频繁的。如果一个项集是非频繁项集，那么它所对应的超集就全都是非频繁项集。

传统的Apriori算法的计算量很大，当商品数据量大时基本上效率很低，所以后来有FP-Tree算法优化了该算法。

在电商平台中，常用的关联规则应用是单品推荐单品，即一般只需要知道频繁2项集即可。而且商品并不是全部平等销售的，组合、搭售、买赠、企业采购等订单都会影响频繁集的生成，若仅用支持度衡量物品之间的关联性，很容易导致出现假性关联。

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

但在互联网海量的用户特征中，使用这些算法挖掘频繁集计算复杂度非常高，下面我们介绍一种在业务当中简单实用的关联规则算法。

1.2业务实践

同样是以购物篮子为例，业务场景是：根据用户历史购物记录，给用户推荐商品。下面我们介绍如何构建简单的关联规则推荐算法。

Step1：数据准备

首先收集用户展示购买记录，并且关联用户在展示时刻的特征数据。设总样本数量为n条，数据格式如下：

表1：初始数据

其中用户特征可以是用户历史购买的商品ID，也可以是用户属性特征，例如：年龄、性别、居住地等等。

Step2：特征交叉

在上表中，对于同一个样本所有特征两两交叉，生成长度为2的特征规则，合并原来的长度为1的特征规则，得到关联规则数据输入表如下：

表2：rule输入数据

上述表中只用长度为1（原始特征）和2（原始特征两两交叉）的规则作为后面rule的候选集，不做长度为3的规则主要的考虑点是降低规则空间复杂度。

Step3：生成关联规则

首先把上表的特征展开，使得一个特征一条记录，如下表：

表3：展开数据

如何来度量一个规则是否够好？有两个量，置信度(Confidence)和支持度(Support)。假设有如下表的购买记录。

将上表整理一下，得到如下的一个2维表

上表中横栏和纵栏的数字表示同时购买这两种商品的交易条数。如购买有Orange的交易数为4，而同时购买Orange和Coke的交易数为2。

置信度表示了这条规则有多大程度上值得可信。设条件的项的集合为A,结果的集合为B。置信度计算在A中，同时也含有B的概率。即Confidence(A==>B)=P(B|A)。例 如计算'如果Orange则Coke'的置信度。由于在含有Orange的4条交易中，仅有2条交易含有Coke.其置信度为0.5。

支持度计算在所有的交易集中，既有A又有B的概率。例如在5条记录中，既有Orange又有Coke的记录有2条。则此条规则的支持度为2/5=0.4。现在这条规则可表述为，如果一个顾客购买了Orange,则有50%的可能购买Coke。而这样的情况（即买了Orange会再买Coke）会有40%的可能发生。

计算每个规则的支持度，置信度，提升度。首先作变量声明：

f->i 表示具备特征f的用户购买商品i的事件
sf,i 表示规则f->i的支持度
cf,i 表示规则f->i的置信度

sf,i 计算方法为：统计表3中同时满足特征=f，商品=i，用户是否购买=0的记录条数记为notbuyersf,i

规则选择，规则可以通过以下条件进行过滤。

条件1：大于等于某个值，参考值取20-100。
条件2：对所有规则的支持度做降序，取75位数为参考值，sf,i大于等于这个值。
条件3：对所有规则的置信度做降序，取75位数为参考值，cf,i大于等于这个值。

Step4：给用户推荐商品

给定一个用户u和一个商品i，通过上述方法生成用户u的特征集合记为F. 我们用该用户特征集合下，所有对i有效特征的均值衡量用户u对该物品的购买可能性p(u,i)：

通过上述公式对全库商品求top 10得分的商品推荐给用户。在实际计算当中，并非会进行全库计算，而是采用特征索引技术进行减少大量冗余计算。

1.3实例代码

https://github.com/asaini/Apriori

参考来源
[1] https://mp.weixin.qq.com/s/9F_BRgnhAxP-nALtBdIZpg
[2] https://www.cnblogs.com/junyuhuang/p/5572364.html
[3] https://baijiahao.baidu.com/s?id=1578453192439039733&wfr=spider&for=pc
[4] https://github.com/asaini/Apriori
[5] https://blog.csdn.net/wsp_1138886114/article/details/80921905