推荐系统-Part2——传统推荐模型

[TOC]

协同过滤(CF)

基本思想

协同过滤是推荐系统的必看内容，因为该算法是后来推荐算法的基本思想。

基本思想：根据用户之前的喜好以及其他兴趣相近的用户的选择来给用户推荐物品(基于对用户历史行为数据的挖掘发现用户的喜好偏向，并预测用户可能喜好的产品进行推荐)。
一般是仅仅基于用户的行为数据（评价、购买、下载等）, 而不依赖于项的任何附加信息（物品自身特征）或者用户的任何附加信息（年龄，性别等）。
目前应用比较广泛的协同过滤算法是基于邻域的方法，而这种方法主要有下面两种算法：
- 基于用户的协同过滤算法(UserCF): 给用户推荐和他兴趣相似的其他用户喜欢的产品
- 基于物品的协同过滤算法(ItemCF): 给用户推荐和他之前喜欢的物品相似的物品

目标场景

存在一系列数据：行为用户记录，列为用户行为目标(包括点击、点赞、购买哪些商品/视频等一些列行为)。

相似度计算

杰卡德相似度：衡量两个集合的相似度，也就是交并比。

余弦相似度：衡量了两个用户向量(矩阵中的行向量) i 和 j 之间的向量夹角的大小，夹角越小，说明相似度越大，两个用户越相似。

局限性：对于不规范的评分数据敏感。例如：A 用户比较喜欢打高分(以95分为优秀)，而 B 用户比较喜欢打低分(以80分为优秀)。

```python
from sklearn.metrics.pairwise import cosine_similarity

i = [1, 0, 0, 0]
j = [1, 0.5, 0.5, 0]
consine_similarity([a, b])


3. 皮尔逊相关系数：先将两个向量都减去分别的均值，消除偏置的影响，然后再计算向量角度 consine 值。

   - ![image-20210926202642997](推荐系统-Part2/image-20210926202642997.png)

   - ```python
     from scipy.stats import pearsonr
     
     i = [1, 0, 0, 0]
     j = [1, 0.5, 0.5, 0]
     pearsonr(i, j)

其他：欧式距离、曼哈顿距离、马氏距离。
- 欧式距离体现数值上的绝对差异，而余弦距离体现方向上的相对差异。
- 如果要分析两个用户对于不同视频的偏好：以观看比例作为特征时，用户A观看向量(0,1)，用户B观看向量(1,0)，此时二者的余弦距离很大，而欧式距离很小。因此，更关注相对差异，应当用余弦距离。
- 如果要分析用户活跃度：以登录次数和平均观看时长作为特征时，余弦距离会认为(1,10)和(10,100)两个用户距离很近，但显然这两个用户活跃度是有着极大差异的。此时我们关注的是数值绝对差异，应当使用欧式距离。

最终结果预测

利用用户相似度(Wu,s) 和相似用户的评价(Rs,p) 加权平均获得用户的评价预测：
在用户相似度和相似用户的评价加权平均的基础上，将用户的评价都减去此用户的所有评分的均值：

基于用户的协同过滤

对于需要个性化推荐的用户A，可以先找到和用户A有相似兴趣的其他用户，然后把那些用户喜欢的且用户A没有听说过的物品推荐给A。

步骤：

根据已有的用户向量，计算与目标用户的相似度，找到最相似的 n 个用户。
根据这 n 个相似用户对目标行为的分数，加权平均来预测目标用户对目标行为的分数。

缺点：

数据稀疏性：在大型的电子商务中物品繁多，不同用户之间买的物品重叠性低，难以找到偏好相似的用户。UserCF 不适用于那些正反馈获取较困难的应用场景。
算法扩展性：需要维护用户相似度矩阵，该矩阵的存储开销大，且随着用户数量的增加而增加。不适合用户数据量大的情况使用。

基于物品的协同过滤

对于需要推广的物品A，可以先找到和物品A有相似用户群体的其他物品，然后把物品A推荐给相似物品的用户群体。
减缓 UserCF 的数据稀疏性和算法扩展性问题。

步骤：

根据已有的物品向量，计算与目标物品之间的相似度，找到最相似的 n 个物品。
根据物品的相似度和用户的历史行为给用户生成推荐列表（购买了该商品的用户也经常购买的其他商品）

优点：

Item-based 算法的预测结果比 User-based 算法的质量要高一点。
由于 Item-based 算法可以预先计算好物品的相似度，所以在线的预测性能比 User-based 算法高。

缺点：

依然存在数据稀疏性。
用户的增长也会导致物品相似度矩阵维护难度变大。

应用场景区别

	UserCF	ItemCF
性能	适合用户较少的场合，否则维护用户相似度矩阵代价较大	适合物品数远小于用户数的场合。如果物品太多，则维护物品相似度矩阵代价大
领域	时效性较强、具备强社交性、用户个性化弱的场合（热点新闻、发觉潜在喜好）	兴趣变化较为稳定、物品更新慢、用户个性化强烈的领域（推荐艺术品，音乐，电影）
实时性	用户的新行为不一定对推荐结果造成立即变化	用户的新行为一定会导致推荐结果的实时变化
推荐理由	很难提供令用户信服的推荐结识	利用用户的历史行为为用户推荐解释，具有信服力

存在问题分析

无法利用更多的信息。完全没有利用到物品或者用户的自身属性，仅利用用户与物品的交互信息就可以实现推荐，是一个可解释性强，直观、但也存在问题的模型。
较差的稀疏向量处理能力，泛化能力弱。热门物品具有很强的头部效应，容易跟大量物品产生相似，而尾部物品由于特征向量稀疏，导致很少被推荐。

矩阵分解(MF)

基本思路

矩阵分解算法通过引入了隐向量的概念，加强了模型处理稀疏矩阵的能力，也为后续深度学习推荐系统算法中 Embedding 的使用打下了基础。
也就是加入隐含层，抽象化用户和物品之间的特征。这个特征信息需要去挖掘。
针对问题：1. 协同过滤处理稀疏向量能力差；2. 维护相似矩阵难度大

隐语义模型

核心思想：通过隐含特征（latent factor）联系用户兴趣和物品（item），基于用户的行为找出潜在的主题和分类，然后对 item 进行自动聚类，划分到不同类别/主题（用户的兴趣）。
矩阵分解算法将 m×n 维的共享矩阵 R分解成 m×k 维的用户矩阵 U 和 k×n 维的物品矩阵 V 相乘的形式。其中 m 是用户数量，n 是物品数量，k是隐向量维度（隐含特征个数），只不过这里的隐含特征变得不可解释了。k 的大小决定了隐向量表达能力的强弱，k 越大，表达信息就越强。
抽象的特征使得用户和物品向量更加稠密，解决了处理稀疏向量能力差的问题。
维护相似矩阵由用户相似矩阵的 m×m 和物品矩阵的 n×n 降低到了 (m+n)×k，解决了维护相似矩阵难度大的问题。
预测评分公式：

MF的几种方式

特征值分解(EVD)：1. 要求矩阵是方阵，是不符合实际场景的。
奇异值分解(SVD)：1. 要求矩阵稠密，而实际场景非常稀疏。2. 一旦补全会导致空间复杂度非常高，且补得不一定正确。3. 计算复杂度非常高，基本无法使用。

Basic SVD(LFM、Funk-SVD)

把矩阵分解问题转换成最优化问题，通过梯度下降进行优化。
预测函数：
损失函数：
优化目标：
求梯度：
梯度更新：

RSVD

在 Basic SVD 的基础上，在目标函数中加入正则化参数（加入惩罚项），对于目标函数来说，Q矩阵和V矩阵中的所有值都是变量，这些变量在不知道哪个变量会带来过拟合的情况下，对所有变量都进行惩罚：
梯度的更新公式就变成了：

进一步优化：

Netfix Prize中提出了另一种LFM，在原来的基础上加了偏置项，来消除用户和物品打分的偏差，预测公式：
这个预测公式加入了3项偏置μ,bu,bi：
- μ：训练集中所有记录的评分的全局平均数。在不同网站平台中，因为网站定位和销售物品不同，网站的整体评分分布也会显示差异。比如有的网站中用户就喜欢打高分，有的网站中用户就喜欢打低分。而全局平均数可以表示网站本身对用户评分的影响。
- bu：用户偏差系数，可以使用定值(用户 u 给出的所有评分的均值)，也可以当做训练参数。这一项表示了用户的评分习惯中和物品没有关系的那种因素。比如有些用户比较苛刻，对什么东西要求很高，那么他评分就会偏低；而有些用户比较宽容，对什么东西都觉得不错，那么评分就偏高。
- bi：物品偏差系数，可以使用定值(物品 i 收到的所有评分的均值)，也可以当做训练参数。这一项表示了物品接受的评分中和用户没有关系的因素。比如有些物品本身质量就很高，因此获得的评分相对比较高，有的物品本身质量很差，因此获得的评分相对较低。

SVD++

之前都是从用户和用户之间的相似度、其他用户对物品的评分进行预测推荐，而缺少考虑用户本身的历史行为对评分预测的影响。
即，之前只考虑分解当前的共现矩阵，注意：此时并没有考虑该用户评分的历史物品。
经过一系列的演化，最终预测公式为：
其中，1/√|N(u)| 是为了保证方差一致性。

优点&局限性

优点：

泛化能力强，一定程度上解决了数据稀疏的问题，通过为用户和物品的隐语义标签抽象化了特征。
空间复杂度低。UserCF(m×m)、ItemCF(n×n) -> 用户隐向量(m×k) + 物品隐向量(n×k)
更好的扩展性和灵活性。可以和其他特征组合拼接，与深度学习网络无缝结合。

局限性：

与协同过滤一样，无法利用用户特征、物品特征、上下文特征。
缺乏用户历史行为时，无法推荐。

逻辑回归(LR)

基本思想

基础知识：逻辑回归、极大似然估计。
- 逻辑回归做为神经网络中的最基础单一神经元
- 逻辑回归假设数据服从伯努利分布，通过极大化似然函数的方法，运用梯度下降来求解参数，来达到将数据二分类的目的。
针对问题：协同过滤无法有效利用用户、物品、上下文等多种不同的特征。
改进方向：将推荐问题转化成了一个二分类问题。

优点

LR模型形式简单，可解释性好，从特征的权重可以看到不同的特征对最后结果的影响。
训练时便于并行化，在预测时只需要对特征进行线性加权，性能好，适合处理海量id类特征。用id类特征有一个很重要的好处，就是防止信息损失（相对于范化的 CTR 特征），对于头部资源会有更细致的描述。
资源占用小，尤其是内存。在实际的工程应用中只需要存储权重比较大的特征及特征对应的权重。
方便输出结果调整。逻辑回归可以很方便的得到最后的分类结果，因为输出的是每个样本的概率分数，我们可以很容易的对这些概率分数进行cutoff，也就是划分阈值。
工程化需要。在深度学习技术之前，逻辑回归凭借易于并行化、模型简单、训练开销小等特点，占领工程领域的主流。因为即使工程团队发现了复杂模型会提升效果，但一般如果没有把握击败逻辑回归的话仍然不敢尝试或者升级。

局限性

表达能力不强，无法进行特征交叉、特征筛选等一系列高级操作，因此可能造成信息的损失。
准确率并不是很高。因为这毕竟是一个线性模型加了个 sigmoid，形式非常的简单，很难去拟合数据的真实分布。
处理非线性数据较麻烦。逻辑回归在不引入其他方法的情况下，只能处理线性可分的数据，如果想处理非线性，首先对连续特征的处理需要先进行离散化，而人工分桶的方式会引入多种问题。
LR 需要进行人工特征组合，这就需要开发者有非常丰富的领域经验，才能不走弯路。这样的模型迁移起来比较困难，换一个领域又需要重新进行大量的特征工程。

自动特征交叉

基本思想

该算法属于对逻辑回归(LR)算法应用在推荐系统上的一个改进，在LR模型的基础上加上了特征交叉项，该思想不仅在传统的推荐算法中继续使用过，在深度学习推荐算法中也对其进行了改进与应用。
针对问题：逻辑回归只对单一特征做简单加权，不具备特征交叉生成组合特征的能力，因此表达能力受到了限制。
如：“化妆品”类商品与“女”性，“球类运动配件”的商品与“男”性，“电影票”的商品与“电影”品类偏好……

POLY2——特征交叉的开始

POLY2是二阶多项式模型，对所有特征进行两两交叉、暴力组合。
针对问题：在逻辑回归里面，如果想得到组合特征，往往需要人工在特征工程的时候手动的组合特征，然后再进行筛选，低效且玄学。
数学形式：
优点：
1. 保留了逻辑回归的优点：充分利用用户特征、物品特征、上下文特征。
2. 一定程度上解决了特征组合的问题。
存在问题：
1. 推荐系统中的数据稀疏性是实际问题中不可避免的挑战(类别型数据经过独热），经过特征较差之后特征向量更加稀疏，使得大部分特征交叉的权重缺乏有效训练，无法收敛。
2. 训练复杂度由 O(n) 上升到 O(n^2^)

FM——隐向量特征交叉

因子分解机(Factorization Machine, FM)
针对问题：1. 在面对稀疏数据向量时，PLOY2特征交叉项无法收敛。2. PLOY2 计算复杂度过高。
数学模型：
优点：
1. 极大降低了训练开销 O(n^2^) -> O(kn)
2. 引入隐向量，更好地解决数据稀疏性的问题
3. FM 模型是利用两个特征的 Embedding 做内积得到二阶特征交叉的权重。可以将训练好的 FM 特征离线训练保存，以便其他拓展。

FFM——引入特征域

域感知因子分解机(Field-aware Factorization Machine, FFM)
先对特征根据性质的不同进行了一个分类，不同的分类就是不同的域，域内特征一般都是同一个 categorical 特征经过 One-Hot 编码生成的数值特征。

对于连续特征，一个特征就对应一个域；或者可以对连续特征离散化，一个分箱成为一个特征，总的分箱是一个域。
改进方向：针对不同的交叉域要学习不同的隐向量特征
优点：引入了更多有价值的信息，表达能力更强。
缺点：
1. 参数量：FM: k×n -> FFM: f×k×n
2. 时间复杂度：FM: O(kn) -> FFM: O(kn^2^)
3. 局限在二阶特征交叉
工业改进：
1. 模型上：双线性FFM(新浪微博张俊林团队)，减少参数量的一种优化思路，共享W矩阵。
2. 业务上：对特征域再进行抽象，减少域的数量。比如说，对 100 个域进行再分类，分为上下文特征、用户特征、item特征、交互特征和匹配特征五大类，实际应用时只考虑这 5 个域即可。

GBDT+LR

基本思想

该模型仍然是对LR模型的改进，使用树模型做特征交叉，相比于 FM 的二阶特征交叉，树模型可以对特征进行深度的特征交叉，充分利用了特征之间的相关性。
针对问题：
1. LR 模型无法进行特征交叉、特征筛选等一些列操作。
2. FM、FFM只能做二姐特征交叉，如果继续提高特征交叉的维度，会不可避免地出现组合爆炸和计算复杂度过高的问题。

GBDT

GBDT 全称梯度提升决策树，在传统机器学习算法里面是对真实分布拟合的最好的几种算法之一。
- GBDT 每轮的训练是在上一轮的训练的残差基础之上进行训练的。
- GBDT 无论用于分类还是回归一直都是使用的 CART 回归树。
优点：可以自动进行多维度特征的发掘与有效组合。
局限性：
1. 对于海量的 id 类特征，GBDT 由于树的深度和棵树限制（防止过拟合），不能有效的存储
2. 另外海量特征在也会存在性能瓶颈，当 GBDT 的 one hot 特征大于 10 万维时，就必须做分布式的训练才能保证不爆内存。
所以 GBDT 通常配合少量的反馈 CTR 特征来表达，这样虽然具有一定的范化能力，但是同时会有信息损失，对于头部资源不能有效的表达。

GBDT+LR

GBDT和LR的优缺点可以进行互补
训练：GBDT 建树的过程相当于自动进行的特征组合和离散化，从根结点到叶子节点的这条路径就可以看成是不同特征进行的特征组合。用叶子节点可以唯一地表示这条路径，并作为一个离散特征传入 LR 进行二次训练。（GBDT 和 LR 是分两步进行训练的，所以不存在 LR 梯度回传至 GBDT）
预测：会先走 GBDT 的每棵树，得到某个叶子节点对应的一个离散特征(即一组特征组合)，然后把该特征以 one-hot 形式传入 LR 进行线性加权预测。
优点：
1. 大大推进了特征工程模型化这一重要趋势。意味着特征工程可以完全交由一个模型独立完成，模型的输入可以是原始的特征向量，不必在特征工程上投入过多的人工筛选和模型设计的精力。
2. 在一定程度上解决了高阶特征交叉的问题。
缺点：容易过拟合。

LS-PLM(MLR)

针对问题：LR 表达能力差
解决思路：
- 通过聚类，构造带权 LR。
- 在逻辑回归的基础上，采用分而治之的思路：先对样本进行聚类，在对样本分片中应用逻辑回归进行 CTR 预估。
- 目的：让 CTR 预估模型对不同的用户群体、不同的应用场景更有针对性。
预测函数：
优点：
1. 端到端的非线性学习能力
2. 稀疏性强，部署更加轻量级
提升模型性能的 trick：
1. 结构化先验增量训练（用户特征进行训练，广告特征进行分类）
2. 线性偏置
3. 模型级联

推荐系统-Part2——传统推荐模型

协同过滤(CF)

基本思想

目标场景

相似度计算

最终结果预测

基于用户的协同过滤

基于物品的协同过滤

应用场景区别

存在问题分析

矩阵分解(MF)

基本思路

隐语义模型

MF的几种方式

Basic SVD(LFM、Funk-SVD)

RSVD

SVD++

优点&局限性

逻辑回归(LR)

基本思想

推荐过程

优点

局限性

自动特征交叉

基本思想

POLY2——特征交叉的开始

FM——隐向量特征交叉

FFM——引入特征域

GBDT+LR

基本思想

GBDT

GBDT+LR

LS-PLM(MLR)