推荐系统二章：推荐系统中的召回算法(1)

发表于 2024-11-14 更新于 2024-11-21 分类于搜广推成长日记阅读次数：本文字数： 13k 阅读时长 ≈ 12 分钟

推荐系统第二章：推荐系统系统中的召回算法：基于协同的过滤召回

学习搜广推主要根据FunRec的教程，面向有机器学习、深度学习基础的搜广推学习笔记。

地址：FunRec

本博客系列所有笔记都是对其中的重点内容进行总结。

如有侵权，请联系我删除。

1. 什么是协同过滤

这里借用原博客的讲解做介绍

协同过滤（Collaborative Filtering）推荐算法是最经典、最常用的推荐算法。基本思想是：

根据用户之前的喜好以及其他兴趣相近的用户的选择来给用户推荐物品。

基于对用户历史行为数据的挖掘发现用户的喜好偏向，并预测用户可能喜好的产品进行推荐。
一般是仅仅基于用户的行为数据（评价、购买、下载等）, 而不依赖于项的任何附加信息（物品自身特征）或者用户的任何附加信息（年龄，性别等）。

目前应用比较广泛的协同过滤算法是基于邻域的方法，主要有：

基于用户的协同过滤算法（UserCF）：给用户推荐和他兴趣相似的其他用户喜欢的产品。
基于物品的协同过滤算法（ItemCF）：给用户推荐和他之前喜欢的物品相似的物品。

不管是 UserCF 还是 ItemCF 算法，重点是计算用户之间（或物品之间）的相似度。

2. 相似度

相似度有很多，这里介绍两种最常用的：余弦距离（Cosine similarity）和皮尔逊相关系数（Pearson coefficient）

2.1 余弦距离

余弦距离是机器学习中最常见的相似度之一了，它度量了两个向量的夹角距离，其公式为

其中都是向量。

2.2 皮尔逊相关系数

皮尔逊相关系数本质上就是标准化的余弦距离，公式如下

其中是向量中的元素，表示向量均值。

现在很多Python库都直接封装有这两个相似度了，这里以scipy为例。

from scipy.spatial.distance import cosine
from scipy.stats import pearsonr
import numpy as np

# 计算余弦距离
vec1 = np.array([1, 2, 3])
vec2 = np.array([4, 5, 6])
print(cosine(vec1, vec2))  

# 计算皮尔逊系数
x = np.array([1, 2, 3, 4, 5])
y = np.array([5, 4, 3, 2, 1])
print(pearsonr)

2.3 Jaccard距离

Jaccard距离度量了两个集合的相似度，公式如下

可以看出是一个“交比并”的模式。

其中，分别表示用户交互物品集合。

对于用户该公式反映了两个交互物品交集占两个用户交互物品并集的数量比例。

3. UserCF与ItemCF

UserCF（基于用户过滤） 的核心思想，是通过分析与用户1爱好相似的其他用户2,3,4...，将物品推送到用户1面前。

ItemCF（基于物品过滤） 的核心思想，是通过计算物体1与其他物品2,3,4...之间的相似性，将用户喜欢可能喜欢的物品推送到用户面前。

3.1 UserCF

例如我们有几个用户对5件商品的评分，现在想知道Alice对物品5的评分是多少，记这个表格为用户-物品评分矩阵

	物品1	物品2	物品3	物品4	物品5
Alice	5	3	4	4	?
用户1	3	1	2	3	3
用户2	4	3	4	3	5
用户3	3	3	1	5	4
用户4	1	5	5	2	1

3.1.1 UserCF算法流程

计算除了物品5以外的所有物品中，Alice与其他所有用户的相似度矩阵，记为，选择其中最相似的个用户。
预测Alice对新物品的评分。

预测方法1：直接预测。记为用户对商品的评分，同理，为用户的相似度

预测方法2：考虑到用户评分会有偏置，有的爱打高分有的爱打低分，可以做标准化处理。

其中，是用户对物品的历史均分。

对所有用户做相同的操作，排序后得到最终结果。

3.1.2 UserCF算法实现

我们可以将上面的表格，除去物品5的第五列，剩下的四列视为一个矩阵，其中每一行都是一个向量。

第一步：计算与分别的相似度或皮尔逊系数，组成一个新的矩阵。

直接调用代码

1
2
3

import numpy as np
data = [[5, 3, 4, 4], [3, 1, 2, 3], [4, 3, 4, 3], [3, 3, 1, 5], [1, 5, 5, 2]]
print(np.corrcoef(data))

输出：

[[ 1.          0.85280287  0.70710678  0.         -0.79211803]
 [ 0.85280287  1.          0.30151134  0.42640143 -0.88662069]
 [ 0.70710678  0.30151134  1.         -0.70710678 -0.14002801]
 [ 0.          0.42640143 -0.70710678  1.         -0.59408853]
 [-0.79211803 -0.88662069 -0.14002801 -0.59408853  1.        ]]

可以看出这个矩阵是对称的，与Alice最相似的用户是用户1和用户2。

第三步：计算Alice对物品5的得分。直接套公式

$物品物品$

可得知Alice对物品5打分为4.87分

第四步：对得分排序，很显然将物品5填入表格后并排序后，应该将物品1和物品5推荐给Alice。

代码实践：

import numpy as np

data = np.array(
    [
        [5, 3, 4, 4, -1],  # Alice, 物品5为未知量-1
        [3, 1, 2, 3, 3],  # user 1
        [4, 3, 4, 3, 5],  # user 2
        [3, 3, 1, 5, 4],  # user 3
        [1, 5, 5, 2, 1],
    ]
)  # user 4

sim_mat = np.corrcoef(data[:-1, :-1])


# argsort是从小到大，这里需要取反，从大到小
similar_user = np.argsort(-sim_mat[0]) 

# 最大的一定是1，也就是自己，从第二大开始取
num = 2
similar_user = similar_user[1:num+1]

# 获取相似用户的评分
similar_user_data = np.array([data[i, :] for i in similar_user])

# 获取相似用户的相似度
similar_user_sim = np.array([sim_mat[0, i] for i in similar_user])

# 计算相似用户均值
similar_user_means = [np.mean(similar_user_data[i, :]) for i in range(len(similar_user_data))]


alice_mean = np.mean(data[0,:-1])

#计算公式
score = alice_mean + sum([similar_user_sim[i]*(similar_user_data[i, -1]-similar_user_means[i]) for i in range(len(similar_user))])/sum(similar_user_sim)

print(score)

3.1.3 UserCF优缺点

UserCF存在两个问题：

数据稀疏
- 大型推荐系统中物品很多，用户买的占比很低，导致不同用户之间买的重叠性较低，很难找到偏好相似的用户
- UserCF不适用于正返回获取困难的应用场景（如酒店预订、大件商品购买等低频应用）
算法扩展性
- UserCF需要维护用户相似度矩阵，并找出TopK用户，矩阵存储开销庞大，随用户量呈现增长。因此不适用于用户数据量大的情况使用

3.2 ItemCF

3.2.1 ItemCF算法流程

ItemCF算法流程与UserCF类似，还是以UserCF中的表格为例，想要知道Alice对物品5打多少分

	物品1	物品2	物品3	物品4	物品5
Alice	5	3	4	4	?
用户1	3	1	2	3	3
用户2	4	3	4	3	5
用户3	3	3	1	5	4
用户4	1	5	5	2	1

通过除了Alice以外的其他用户，计算物品5与其他物品之间的相似性。
找到与物品5相似的个物品。
根据Alice对这个物品打分计算物品5的打分。预测公式跟UserCF极其相似，只不过是符号代表的含义不同，如下式所示，代表用户对物品打分，代表物品之间的相似度。

这里就可以明显看出，ItemCF是以物品为导向的，计算的都是物品相似度，而UserCF都是以用户为导向，计算用户之间的相似度。实际上，ItemCF是对原用户-物品评分矩阵的转置进行一遍UserCF的过程。

代码实践

import numpy as np

data = np.array(
    [
        [5, 3, 4, 4, -1],  # Alice, 物品5为未知量-1
        [3, 1, 2, 3, 3],  # user 1
        [4, 3, 4, 3, 5],  # user 2
        [3, 3, 1, 5, 4],  # user 3
        [1, 5, 5, 2, 1],  # user 4
    ]
)

data_transpose = data.T
sim_mat = np.corrcoef(data[1:, :].T)


# argsort是从小到大，这里需要取反，从大到小
similar_item = np.argsort(-sim_mat[-1]) 
print(similar_item)
# 最大的一定是1，也就是自己，从第二大开始取
num = 2
similar_item = similar_item[1:num+1]
print(similar_item)
# 获取相似物品的评分
similar_item_data = np.array([data_transpose[i, :] for i in similar_item])
print(similar_item_data)
# 获取相似物品的相似度
similar_item_sim = np.array([sim_mat[-1, i] for i in similar_item])
print(similar_item_sim)
# 计算相似物品均值
similar_item_means = [np.mean(similar_item_data[i, :]) for i in range(len(similar_item_data))]
print(similar_item_means)


item5_mean = np.mean(data_transpose[-1,1:])

# 计算公式
score = item5_mean + sum([similar_item_sim[i]*(similar_item_data[i, 0]-similar_item_means[i]) for i in range(len(similar_item))])/sum(similar_item_sim)



print(score)

思考题：什么时候用UserCF？什么时候用ItemCF？为什么？

UserCF适用于用户少、物品多、时效性强的场合，因为UserCF计算的是用户相关性，具备更强的社交特性，例如新闻推荐场景。
- 因为新闻本身兴趣点分散，相比用户对不同新闻的兴趣偏好，新闻的及时性，热点性往往更加重要，所以正好适用于发现热点，跟踪热点的趋势。
- 另外还具有推荐新信息的能力，更有可能发现惊喜, 因为看的是人与人的相似性, 推出来的结果可能更有惊喜，可以发现用户潜在但自己尚未察觉的兴趣爱好。
ItemCF适用于物品少、用户多，用户兴趣固定持久，物品更新速度不太快的场合。例如艺术品、音乐、电影等

4. 协同过滤算法权重改进

基础权重公式

该公式表示同时的被购买数量占被购买的比例。

缺点：若物品为热门物品，那么它与任何物品相似度都很高

对热门物品进行惩罚

公式如下

要对热门物品进行惩罚的思路很简单，直接在分母再除以一个被购买数量的指数倍，的指数和为1。

对活跃用户惩罚

除了对物品惩罚，还可以对活跃用户数量这一项惩罚

对于活跃度高的用户，在计算相似度时，他们的权重应该小于非活跃用户

5. 协同过滤算法存在的问题

协同过滤算法存在的问题之一就是泛化能力弱。

具体而言，就是热门物品有很强的头部效应，跟大量物品的相似度都很高，而尾部物品由于向量稀疏，导致很少被推荐。

例如

属于热门物品，跟相似，因此系统更加有可能将推荐给用过物品的用户，但之间的内部关联性却没有办法根据这个矩阵推荐。

为了解决这个问题，同时增加模型的泛化能力。2006年，矩阵分解技术(Matrix Factorization, MF)被提出：

该方法在协同过滤共现矩阵的基础上，使用更稠密的隐向量表示用户和物品，挖掘用户和物品的隐含兴趣和隐含特征。
在一定程度上弥补协同过滤模型处理稀疏矩阵能力不足的问题。

*6. Swing与Suprise

Swing和Surpise本质上属于两种相似度，这里作简要介绍，基本是照搬原文。

之前方法局限性

基于 Cosine, Jaccard, 皮尔逊相关性等相似度计算的协同过滤算法，在计算邻居关联强度的时候只关注于 Item-based (常用，因为item相比于用户变化的慢，且新Item特征比较容易获得)，Item-based CF 只关注于 Item-User-Item 的路径，把所有的User-Item交互都平等得看待，从而忽视了 User-Item 交互中的大量噪声，推荐精度存在局限性。
对互补性产品的建模不足，可能会导致用户购买过手机之后还继续推荐手机，但用户短时间内不会再继续购买手机，因此产生无效曝光。

贡献

提出了高效建立产品索引图的技术。

主要包括：

Swing 算法利用 user-item 二部图的子结构捕获产品间的替代关系。
Surprise 算法利用商品分类信息和用户共同购买图上的聚类技术来建模产品之间的组合关系。

6.1 Swing

Swing 通过利用 User-Item-User 路径中所包含的信息，考虑 User-Item 二部图中的鲁棒内部子结构计算相似性。

什么是内部子结构？以经典的啤酒尿布故事为例，张三同时购买了啤酒和尿布，这可能是一种巧合。但两个甚至多个顾客都同时购买了啤酒尿布，这就证明啤酒和尿布具有相关关系。这样共同购买啤酒和尿布的用户越多，啤酒和尿布的相关度就会越高。

图中的红色四边形就是一种Swing子结构，这种子结构可以作为给王五推荐尿布的依据。

通俗解释：若用户和用户之间除了购买过外，还购买过商品，则认为两件商品是具有某种程度上的相似的。也就是说，商品与商品之间的相似关系，是通过用户关系来传递的。为了衡量物品和的相似性，比较同时购买了物品和的用户和用户，如果这两个用户共同购买的物品越少，即这两个用户原始兴趣不相似，但仍同时购买了两个相同的物品和，则物品和的相似性越高。
计算公式

其中是点击过商品i的用户集合，是用户u点击过的商品集合，是平滑系数。

是用户权重参数，来降低活跃用户的影响。

6.2 Surprise

首先在行为相关性中引入连续时间衰减因子，然后引入基于交互数据的聚类方法解决数据稀疏的问题，旨在帮助用户找到互补商品。互补相关性主要从三个层面考虑，类别层面，商品层面和聚类层面。

类别层面首先通过商品和类别的映射关系，我们可以得到 user-category 矩阵。随后使用简单的相关性度量可以计算出类别的相关性。

即，为在购买过之后购买类的数量，为购买j类的数量。

由于类别直接的种类差异，每个类别的相关类数量存在差异，因此采用最大相对落点来作为划分阈值。

例如图(a)中T恤的相关类选择前八个，图(b)中手机的相关类选择前三个。

商品层面商品层面的相关性挖掘主要有两个关键设计：

商品的购买顺序是需要被考虑的，例如在用户购买手机后推荐充电宝是合理的，但在用户购买充电宝后推荐手机是不合理的。
两个商品购买的时间间隔也是需要被考虑的，时间间隔越短越能证明两个商品的互补关系。

最终商品层面的互补相关性被定义为：

其中属于的相关类，且的购买时间晚于。

聚类层面

如何聚类？传统的聚类算法（基于密度和 k-means ）在数十亿产品规模下的淘宝场景中不可行，所以作者采用了标签传播算法。
在哪里标签传播？ Item-item 图，其中又 Swing 计算的排名靠前 item 为邻居，边的权重就是 Swing 分数。
表现如何？快速而有效，15分钟即可对数十亿个项目进行聚类。最终聚类层面的相关度计算同上面商品层面的计算公式

线性组合： ,其中是作者设置的权重超参数。 Surprise算法通过利用类别信息和标签传播技术解决了用户共同购买图上的稀疏性问题。

7. 矩阵分解

由于协同过滤算法处理稀疏矩阵效果不好，为了增强其泛化能力，从协同过滤中衍生出矩阵分解模型（Matrix Factorization, MF），或者叫隐语义模型。隐语义模型有两个作用

在协同过滤共现矩阵的基础上，使用更稠密的隐向量表示用户和物品。
通过挖掘用户和物品的隐含兴趣和隐含特征，在一定程度上弥补协同过滤模型处理稀疏矩阵能力不足的问题。

7.1 隐语义模型

隐语义模型实际上类似于Embedding，具体到推荐系统来说，就是就用户行为找出潜在的主题和分类，然后对物品进行自动聚类。

用一个音乐评分的例子来说明，用户和音乐存在两个特征矩阵

潜在特征-用户矩阵

潜在特征-音乐矩阵

通过对的逐行做点积就可以得到每个用户对每首音乐的打分。最终得到一个打分矩阵，就可以计算出向用户推荐哪一首歌了。

用公式表达这个过程就是

其中，向量表示用户的隐向量，向量表示物品的隐向量。用户向量和物品向量的内积可以表示为用户对物品的预测评分。
和是模型的参数，度量的是用户的兴趣和第个隐类的关系，度量了第个隐类和物品之间的关系。

但实际过程中矩阵很难获取，一般能够获取到的只有一个稀疏的打分矩阵，因为用户很可能不会对每一项物品都评分。 因此需要将矩阵分解为矩阵，再反过来计算未知的用户对物品的评分，相当于对上述过程做逆向拆解。

7.2 矩阵分解

矩阵分解有很多中，特征值分解、SVD等等。特征值分解只能用于方阵，SVD要求原矩阵是稠密的，因此都不适合直接运用。

因此提出了可学习的矩阵分解，分为FunkSVD和BiasSVD，BiasSVD是FunkSVD的改进版本，这里合在一起阐述。

7.2.1 FunkSVD与BiasSVD

可学习的矩阵分解概念很简单，就是用ML的方式去学习分解出来的矩阵，让的点积尽可能跟原矩阵相同。

FunkSVD算法步骤

随机初始化矩阵

随机初始化矩阵

注意: 不能全0或1初始化。全0初始化会导致无法更新权重，因为怎么乘出来都是0，全1会导致激活函数的导数趋近于0，产生梯度消失

计算与的MSE，作为损失函数

其中为用户对物品的真实评分，是中的元素。分别是矩阵的第行。为预测项，可以简记为

然后根据经典反向传播优化这个损失函数就可以了。另外还可以加入正则项来防止过拟合。这里选用L2正则，L2正则假设模型参数符合0均值正态分布，让模型输出更稳定。具体L1，L2正则的区别与作用请参见L1正则项L2正则项

BiasSVD就是在FunkSVD的基础上，再加入了3个可学习的偏置项

:该参数反映的是推荐模型整体的平均评分，一般使用所有样本评分的均值。
:用户偏差系数。可以使用用户给出的所有评分的均值，也可以当做训练参数。这一项表示了用户的评分习惯中和物品没有关系的那种因素。比如有些用户比较苛刻，对什么东西要求很高，那么他评分就会偏低，而有些用户比较宽容，对什么东西都觉得不错，那么评分就偏高。
:物品偏差系数。可以使用物品收到的所有评分的均值，也可以当做训练参数。这一项表示了物品接受的评分中和用户没有关系的因素。比如有些物品本身质量就很高，因此获得的评分相对比较高，有的物品本身质量很差，因此获得的评分相对较低。

那么整体的损失函数为（加上L2正则项）

7.3 代码实战

还使用Alice的例子，直接借用原文代码，注释很清晰

	物品1	物品2	物品3	物品4	物品5
Alice	5	3	4	4	?
用户1	3	1	2	3	3
用户2	4	3	4	3	5
用户3	3	3	1	5	4
用户4	1	5	5	2	1

import random
import math


class BiasSVD():
    def __init__(self, rating_data, F=5, alpha=0.1, lmbda=0.1, max_iter=100):
        self.F = F          # 这个表示隐向量的维度
        self.P = dict()     # 用户矩阵P  大小是[users_num, F]
        self.Q = dict()     # 物品矩阵Q  大小是[item_nums, F]
        self.bu = dict()    # 用户偏置系数
        self.bi = dict()    # 物品偏置系数
        self.mu = 0         # 全局偏置系数
        self.alpha = alpha  # 学习率
        self.lmbda = lmbda  # 正则项系数
        self.max_iter = max_iter        # 最大迭代次数
        self.rating_data = rating_data  # 评分矩阵

        for user, items in self.rating_data.items():
            # 初始化矩阵P和Q, 随机数需要和1/sqrt(F)成正比
            self.P[user] = [random.random() / math.sqrt(self.F) for x in range(0, F)]
            self.bu[user] = 0
            for item, rating in items.items():
                if item not in self.Q:
                    self.Q[item] = [random.random() / math.sqrt(self.F) for x in range(0, F)]
                    self.bi[item] = 0

    # 采用随机梯度下降的方式训练模型参数
    def train(self):
        cnt, mu_sum = 0, 0
        for user, items in self.rating_data.items():
            for item, rui in items.items():
                mu_sum, cnt = mu_sum + rui, cnt + 1
        self.mu = mu_sum / cnt

        for step in range(self.max_iter):
            # 遍历所有的用户及历史交互物品
            for user, items in self.rating_data.items():
                # 遍历历史交互物品
                for item, rui in items.items():
                    rhat_ui = self.predict(user, item)  # 评分预测
                    e_ui = rui - rhat_ui                  # 评分预测偏差

                    # 参数更新
                    self.bu[user] += self.alpha * (e_ui - self.lmbda * self.bu[user])
                    self.bi[item] += self.alpha * (e_ui - self.lmbda * self.bi[item])
                    for k in range(0, self.F):
                        self.P[user][k] += self.alpha * (e_ui * self.Q[item][k] - self.lmbda * self.P[user][k])
                        self.Q[item][k] += self.alpha * (e_ui * self.P[user][k] - self.lmbda * self.Q[item][k])
            # 逐步降低学习率
            self.alpha *= 0.1


    # 评分预测
    def predict(self, user, item):
        return sum(self.P[user][f] * self.Q[item][f] for f in range(0, self.F)) + self.bu[user] + self.bi[
            item] + self.mu


# 通过字典初始化训练样本，分别表示不同用户（1-5）对不同物品（A-E)的真实评分
def loadData():
    rating_data={1: {'A': 5, 'B': 3, 'C': 4, 'D': 4},
           2: {'A': 3, 'B': 1, 'C': 2, 'D': 3, 'E': 3},
           3: {'A': 4, 'B': 3, 'C': 4, 'D': 3, 'E': 5},
           4: {'A': 3, 'B': 3, 'C': 1, 'D': 5, 'E': 4},
           5: {'A': 1, 'B': 5, 'C': 5, 'D': 2, 'E': 1}
          }
    return rating_data

# 加载数据
rating_data = loadData()
# 建立模型
basicsvd = BiasSVD(rating_data, F=10)
# 参数训练
basicsvd.train()
# 预测用户1对物品E的评分
for item in ['E']:
    print(item, basicsvd.predict(1, item))

# 预测结果：E 3.685084274454321