作者：vivo 互联网服务器团队 -Tang Shutao
现如今举荐无处不在，例如抖音、淘宝、京东 App 均能见到举荐零碎的身影，其背地波及许多的技术。
本文以经典的协同过滤为切入点，重点介绍了被工业界宽泛应用的矩阵合成算法，从实践与实际两个维度介绍了该算法的原理，通俗易懂，心愿可能给大家带来一些启发。
笔者认为要彻底搞懂一篇论文，最好的形式就是入手复现它，复现的过程你会遇到各种各样的纳闷、实践细节。
一、背景
1.1 引言
在信息爆炸的二十一世纪，人们很容易吞没在常识的陆地中，在该场景下 搜索引擎 能够帮忙咱们迅速找到咱们想要查找的内容。
在电商场景，现在的社会物质极大丰富，商品目不暇接，品种繁多。消费者很容易挑花眼，即用户将会面临信息过载的问题。
为了解决该问题，举荐引擎 应运而生。例如咱们关上淘宝 App，JD app，B 站视频 app，每一个场景下都有 举荐 的模块。
那么此时有一个幼儿园小朋友忽然问你，为什么 JD 给你举荐这本《程序员颈椎痊愈指南》？你可能会答复，因为我的职业是程序员。
接着小朋友又问，为什么《Spark 大数据分析》这本书排在第 6 个举荐位，而《Scala 编程》排在第 2 位？这时你可能无法回答这个问题。
为了答复该问题，咱们构想上面的场景：
在 JD 的电商零碎中，存在着用户和商品两种角色，并且咱们假如用户都会对本人购买的商品打一个 0 - 5 之间的分数，分数越高代表越喜爱该商品。
基于此假如，咱们将下面的问题转化为用户对《程序员颈椎痊愈指南》，《Spark 大数据分析》，《Scala 编程》这三本书打分的话，用户会打多少分（用户之前 未购买 过这 3 本书）。因而物品在页面的先后顺序就等价于 预测 用户对这些物品的评分，并且依据这些评分进行排序的问题。
为了便于预测用户对物品的评分问题，咱们将所有三元组(User, Item, Rating)，即用户 User 给本人购买的商品 Item 的评分为 Rating，组织为如下的矩阵模式：
其中，表格蕴含 \(m\)个 用户 和 \(n\)个 物品 ，将表格定义为 评分 矩阵 \({\bf{R}}_{m \times n}\)，其中的元素 \(r_{u,i}\)示意第 \(u\)个用户对第 \(i\)个物品的评分。
例如，在下面的表格中，用户 user- 1 购买了物品 item-1，item-3，item-4，并且别离给出了 4，2，5 的评分。最终，咱们将原问题转化为预测 红色空格 处的数值。
1.2 协同过滤
协同过滤，简略来说是利用与用户趣味相投、领有独特教训之群体的爱好来举荐给用户感兴趣的物品。趣味相投应用数学语言来表白就是类似度 (人与人，物与物)。因而，依据 类似度 的对象，协同过滤能够分为 基于用户 的协同过滤和 基于物品 的协同过滤。
以评分矩阵为例，以 行方向 观测评分矩阵，每一行代表每个用户的向量示意，例如用户 user- 1 的向量为 [4, 0, 2, 5, 0, 0]。以 列方向 观测评分矩阵，每一列示意每个物品的向量示意，例如物品 item- 1 的向量为[4, 3, 0, 0, 5]。
基于向量示意，类似度的计算有多种公式，例如余弦类似度，欧氏间隔，皮尔森。这里咱们以余弦类似度为例，它是咱们中学学过的向量夹角 (中学只波及 2 维和 3 维) 的高维推广，余弦类似度公式很容易了解和应用。给定两个向量 \(\mathbf{A}=\{a\_1, \cdots, a\_n\}\)和 \(\mathbf{B}=\{b\_1, \cdots, b\_n\}\)，其夹角定义如下：
\(\cos(\theta)=\frac{\bf{A}\cdot \bf{B}}{{|\bf{A}}|{|\bf{B}}|}=\frac{a\_1 b\_1 + \cdots + a\_n b\_n}{\sqrt{a\_1^2+\cdots a\_n^2}\sqrt{b\_1^2 + \cdots b\_n^2}}\)
例如，咱们计算 user- 3 和 user- 4 的余弦类似度，二者对应的向量别离为 [0, 2, 0, 3, 0, 4]，[0, 3, 3, 5, 4, 0]
\(\cos(\theta)=\frac{\bf{A}\cdot \bf{B}}{{|\bf{A}}|{|\bf{B}}|}=\frac{a\_1 b\_1 + \cdots + a\_n b\_n}{\sqrt{a\_1^2+\cdots a\_n^2}\sqrt{b\_1^2 + \cdots b\_n^2}}\)
向量夹角的 余弦值 越靠近 1 代表两个物品方向越靠近平行，也就是越类似，反之越靠近 - 1 代表两个物品方向越靠近反向，示意两个物品类似度靠近相同，靠近 0，示意向量靠近垂直 / 正交，两个物品简直无关联。显然，这和人的直觉完全一致。
例如，咱们在视频 App 中常常能看到 ”相干举荐“ 模块，其背地用到的原理之一就是类似度计算，下图展现了一个具体的例子。
咱们用《血族第一部》在向量库 (存储向量的数据库，该零碎可能依据输出向量，用类似度公式在库中进行检索，找出 TopN 的候选向量) 外面进行类似度检索，找到了前 7 部高类似度的影片，值得注意的是第一部是本人自身，类似度为 1.0，其余三部是《血族》的其余 3 部同系列作品。
1.2.1 基于用户的协同过滤 (UserCF)
基于用户的协同过滤分为两步
- 找出用户类似度 TopN 的若干用户。
- 依据 TopN 用户评分的物品，造成候选物品汇合，利用加权均匀预估用户 u 对每个候选物品的评分。
例如，由用户 u 的类似用户 {u1, u3, u5, u9} 可得候选物品为
\(\{i\_1, i\_2, i\_3, i\_4, i\_5, i\_6, i_7\}\)
咱们当初预测用户 u 对物品 i1 的评分，因为物品在两个用户 {u1, u5} 的购买记录里，因而用户 u 对物品 i1 的预测评分为：
\({r}_{u,i\_1} = \frac{\text{sim}{(u,u\_1)}\times {r}_{u\_1,i\_1}+\text{sim}{(u,u\_5)}\times {r}\_{u\_5,i\_1}}{\text{sim}{(u,u\_1)}+\text{sim}{(u,u\_5)}}\)
其中 \(\text{sim}{(u,u_1)}\)示意用户 u 与用户 \(u_1\)的类似度。
在举荐时，依据用户 u 对所有候选物品的预测分进行排序，取 TopM 的候选物品举荐给用户 u 即可。
1.2.2 基于物品的协同过滤 (ItemCF)
基于物品的协同过滤分为两步：
- 在用户 u 购买的物品汇合中，选取与每一个物品 TopN 类似的物品。
- TopN 类似物品造成候选物品汇合，利用 加权均匀 预估用户 u 对每个候选物品的评分。
例如，咱们预测用户 u 对物品 i3 的评分，因为物品 i3 与物品 {i6, i1, i9} 均类似，因而用户 u 对物品 i3 的预测评分为：
\({r}_{u,i\_3} = \frac{\text{sim}{(i\_6,i\_3)}\times {r}\_{u,i\_6}+\text{sim}{(i\_1,i\_3)}\times {r}\_{u,i\_1}+\text{sim}{(i\_9,i\_3)}\times {r}\_{u,i\_9}}{\text{sim}{(i\_6,i\_3)}+\text{sim}{(i\_1,i\_3)}+\text{sim}{(i\_9,i_3)}}\)
其中 \(\text{sim}{(i\_6,i\_3)}\)示意物品 \(i_6\)与物品 \(i_3\)的类似度，其余符号同理。
1.2.3 UserCF 与 ItemCF 的比拟
咱们对 ItemCF 和 UserCF 做如下总结：
UserCF次要用于给用户举荐那些与之有独特兴趣爱好的用户喜爱的物品，其举荐后果着重于反映和用户趣味类似的小群体的热点，更社会化一些，反映了用户所在的小型趣味群体中物品的热门水平。在理论利用中，UserCF 通常被利用于用于新闻举荐。
ItemCF给用户举荐那些和他之前喜爱的物品相似的物品，即 ItemCF 的举荐后果着重于维系用户的历史趣味，举荐更加个性化，反馈用户本人的趣味。在理论利用中，图书、电影平台应用 ItemCF，比方豆瓣、亚马逊、Netflix 等。
除了基于用户和基于物品的协同过滤，还有一类基于模型的协同过滤算法，如上图所示。此外基于用户和基于物品的协同过滤又能够归类为基于邻域 (K-Nearest Neighbor, KNN) 的算法，实质都是在找 ”TopN 街坊 ”，而后利用街坊和类似度进行预测。
二、矩阵合成
经典的协同过滤算法自身存在一些毛病，其中最显著的就是 稠密性 问题。咱们晓得评分矩阵是一个大型 稠密矩阵 ，导致在计算类似度时，两个向量的 点积 等于 0 (以余弦类似度为例)。为了更直观的了解这一点，咱们举例如下：
rom sklearn.metrics.pairwise import cosine_similarity
a = [[ 0, 0, 0, 3, 2, 0, 3.5, 0, 1],
[0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0],
[4.1, 3.8, 4.6, 3.8, 4.4, 3, 4, 0, 3.6]
]
cosine_similarity(a)
# array([[1. , 0. , 0. , 0.66209271],
# [0. , 1. , 0. , 0.34101639],
# [0. , 0. , 1. , 0.41280932],
# [0.66209271, 0.34101639, 0.41280932, 1.]])咱们从评分矩阵中抽取 item1 – item4 的向量，并且利用余弦类似度计算它们之间的类似度。
通过类似度矩阵，咱们能够看到物品 item-1, item-2, item- 3 的之间的类似度均为 0，而且与 item-1, item-2, item-3最类似 的物品都是 item-4，因而在以 ItemCF 为根底的举荐场景中 item- 4 将会被举荐给用户。
然而，物品 item- 4 与物品 item-1, item-2, item- 3 最类似的起因是 item- 4 是一件热门商品，购买的用户多，而物品 item-1, item-2, item- 3 的类似度均为 0 的起因仅仅是它们的 特征向量 十分 稠密，不足类似度计算的间接数据。
综上，咱们能够看到经典的基于用户 / 物品的协同过滤算法有人造的缺点，无奈解决稠密场景。为了解决该问题，矩阵合成被提出。
2.1 显示反馈
咱们将用户对物品的评分行为定义为显示反馈。基于显示反馈的矩阵合成是将评分矩阵 \({\bf{R}}_{m \times n}\)用两个矩阵 \({\bf{X}}_{m \times k}\)和 \({\bf{Y}}_{n \times k}\)的乘积近似示意，其数学示意如下：
\({\bf{R}}_{m \times n} \approx {\bf{X}}_{m \times k}\left({\bf{Y}}_{n \times k}\right)^{\text T}\)
其中，\(k \ll m/n\)示意隐性因子，以用户侧来了解，\(k=2\)示意的就是用户的年龄和性别两个属性。此外有个很好的比喻就是物理学的 三棱镜 ，白光在三棱镜的作用下被合成为 7 种颜色的光，在矩阵合成算法中， 合成 的作用就相似于 ” 三棱镜 ”，如下图所示，因而，矩阵合成也被称为 隐语义模型 。矩阵合成将零碎的自由度从 \(\mathcal{O}(mn)\) 降到了 \(\mathcal{O}((m+n)k)\)，从而实现了降维的目标。
为了求解矩阵 \({\bf{X}}_{m \times k}\)和 \({\bf{Y}}_{n \times k}\)，须要最小化平方误差损失函数，来尽可能地使得两个矩阵的乘积迫近评分矩阵 \({\bf{R}}_{m \times n}\)，即
$$
\min\limits_{{\bf{x}}^*,{\bf{y}}^*} L({\bf{X}},{\bf{Y}})=\min\limits_{{\bf{x}}^*,{\bf{y}}^*}\sum\limits_{r_{u,i} \text{is known}}(r_{u,i}-{\bf{x}}_u^{\text T}{\bf{y}}_i)^2+\lambda \left(\sum\limits_{u}{\bf{x}}_u^{\text T}{\bf{x}}_u+\sum\limits_{i}{\bf{y}}_i^{\text T}{\bf{y}}_i\right)
$$
其中，\(\lambda \left( \sum\limits_{u}{\bf{x}}\_u^{\text T}{\bf{x}}\_u+\sum\limits_{i}{\bf{y}}\_i^{\text T}{\bf{y}}\_i\right)\)为惩办项，\(\lambda\)为惩办系数 / 正则化系数，\(\mathbf{x}_u\)示意第 \(u\)个用户的 \(k\)维特征向量，\(\mathbf{y}_i\)示意第 \(i\)个物品的 \(k\)维特征向量。
\({\bf{x}}\_u = \begin{pmatrix} x\_{u,1} \\ \vdots \\ x_{u,k} \\ \end{pmatrix} \qquad {\bf{y}}\_i = \begin{pmatrix} y\_{i,1} \\ \vdots \\ y_{i,k} \\ \end{pmatrix}\)
整体用户的特征向量形成了用户矩阵 \({\bf{X}}_{m \times k}\)，整体物品的特征向量形成了物品矩阵 \({\bf{Y}}_{n \times k}\)。
\({\bf{x}}\_u = \begin{pmatrix} x\_{u,1} \\ \vdots \\ x_{u,k} \\ \end{pmatrix} \qquad {\bf{y}}\_i = \begin{pmatrix} y\_{i,1} \\ \vdots \\ y_{i,k} \\ \end{pmatrix}\)
咱们训练模型的时候，就只须要训练用户矩阵中的参数和物品矩阵中的 \(n \times k\)个参数。因而，协同过滤就胜利转化成了一个优化问题。
2.2 预测评分
通过模型训练 (即求解模型系数的过程)，咱们失去用户矩阵 \({\bf{X}}_{m \times k}\)和物品矩阵 \({\bf{Y}}_{n \times k}\)，全副用户对全副物品的评分预测能够通过 \({\bf{X}}_{m \times k}\left({\bf{Y}}_{n \times k}\right)^{\text T}\)取得。如下图所示。
失去全副的评分预测后，咱们就能够对每个物品进行择优举荐。须要留神的是，用户矩阵和物品矩阵的乘积，失去的评分 预估值 ，与用户的理论评分不是全等关系，而是 近似相等 的关系。如上图中两个矩阵粉色局部，用户理论评分和预估评分都是近似的，有肯定的误差。
2.3 实践推导
矩阵合成 ALS 的实践推导网上也有不少，然而很多推导 不是那么谨严 ，在操作 向量导数 时有的步骤甚至是谬误的。有的博主对 损失函数 的求和项了解 呈现谬误，例如
\(\sum\limits_{\color{red}{u=1}}^{\color{red} m}\sum\limits_{\color{red}{i=1}}^{\color{red} n}(r_{u,i}-{\bf{x}}\_u^{\text T}{\bf{y}}\_i)^2\)
然而评分矩阵是稠密的，求和并不会贯通整个用户集和物品集。正确的写法应该是
\(\sum\limits_{\color{red}{(u,i) \text{is known}}}(r_{u,i}-{\bf{x}}\_u^{\text T}{\bf{y}}\_i)^2\)
其中，(u,i)is known 示意已知的评分项。
咱们在本节给出具体的、正确的 推导过程，一是当做数学小练习，其次也是对算法有更深层的了解，便于浏览 Spark ALS 的源码。
将 \({(u,i) \text{is known}}\)应用数学语言形容，矩阵合成的损失函数定义如下：
\(L({\bf{X}},{\bf{Y}})=\sum\limits_{\color{red}{(u,i) \in K}}(r_{u,i}-{\bf{x}}\_u^{\text T}{\bf{y}}\_i)^2+\lambda \left(\sum\limits_{u}{\bf{x}}\_u^{\text T}{\bf{x}}\_u+\sum\limits_{i}{\bf{y}}\_i^{\text T}{\bf{y}}\_i\right)\)
其中 \(K\)为评分矩阵中已知的 \((u, i)\)汇合。例如上面的评分矩阵对应的 \(K\)为
\({\bf{R}}_{4 \times 4} = \begin{pmatrix} 0 & r_{1,2} & r_{1,3} & 0 \\ r_{2,1} & 0 & r_{2,3} & 0 \\ 0 & r_{3,2} & 0 & r_{3,4} \\ 0 & r_{4,2} & r_{4,3} & r_{4,4} \end{pmatrix} \\ \Rightarrow \color{red}{K = \{(1,2), (1,3), (2,1), (2,3), (3,2), (3,4), (4,2), (4,3), (4,4)\}}\)
求解上述损失函数存在两种典型的优化办法，别离为
- 交替最小二乘 (Alternating Least Squares, ALS)
- 随机梯度降落 (Stochastic Gradient Descent, SGD)
交替最小二乘，指的是固定其中一个变量，利用 最小 二乘求解另一个变量，以此交替进行，直至收敛或者达到最大迭代次数，这也是“交替”一词的由来。
随机梯度降落，是优化实践中最罕用的一种形式，通过计算梯度，而后更新待求的变量。
在矩阵合成算法中，Spark 最终抉择了 ALS 作为官网的惟一实现，起因是 ALS 很容易实现并行化，工作之间没有依赖。
上面咱们入手推导一下整个计算过程，在机器学习实践中，微分的单位个别在 向量 维度，很少去对向量的重量为偏微分推导。
首先咱们固定物品矩阵 \({\bf{Y}}\)，将物品矩阵 \({\bf{Y}}\)看成 常量 。不失一般性，咱们定义用户 u 评分过的物品汇合为 \(I_u\)，利用损失函数对向量 \(\mathbf{x}_u\) 求偏导，并且令导数等于 0 可得：
$$
\displaystyle \frac{\partial L}{\partial {\bf{x}}_u}=-2\sum\limits_{i \in I_u}(r_{u,i}-{\bf{x}}_u^{\text T}{\bf{y}}_i)\frac{\partial {(\bf{x}}_u^{\text T}{\bf{y}}_i)}{\partial {\bf{x}}_u}+2\lambda \frac{\partial {(\bf{x}}_u^{\text T}{\bf{x}}_u)}{\partial {\bf{x}}_u}=0, \quad u=1, \cdots, m \\
\begin{split}
& \quad \Rightarrow \sum\limits_{i \in I_u}(r_{u,i}-{\bf{x}}_u^{\text T}{\bf{y}}_i){\bf{y}}_i^{\text T}=\lambda {\bf{x}}_u^{\text T} \\
& \quad \Rightarrow \sum\limits_{i \in I_u}r_{u,i}{\bf{y}}_i^{\text T}-\sum\limits_{i \in I_u}{\bf{x}}_u^{\text T}{\bf{y}}_i{\bf{y}}_i^{\text T}=\lambda {\bf{x}}_u^{\text T} \\
& \quad \Rightarrow \sum\limits_{i \in I_u}{\bf{x}}_u^{\text T}{\bf{y}}_i{\bf{y}}_i^{\text T}+\lambda {\bf{x}}_u^{\text T}=\sum\limits_{i \in I_u}r_{u,i}{\bf{y}}_i^{\text T}
\end{split}
$$
因为向量 \(\mathbf{x}_u\)与求和符号 \(\sum\limits_{i \in I_u}\)无关，所有将其移出求和符号，因为 \({\bf{x}}\_u^{\text T}{\bf{y}}\_i{\bf{y}}_i^{\text T}\)是矩阵相乘 (不满足 替换性 )，因而 \(\mathbf{x}_u\) 在右边
$$
\begin{split}
& {\bf{x}}_u^{\text T}\sum\limits_{i \in I_u}{\bf{y}}_i{\bf{y}}_i^{\text T}+\lambda {\bf{x}}_u^{\text T}=\sum\limits_{i \in I_u}r_{u,i}{\bf{y}}_i^{\text T} \\
\end{split}
$$
等式两边取转置，咱们有
$$
\begin{split}
& \quad \Rightarrow \left({\bf{x}}_u^{\text T}\sum\limits_{i \in I_u}{\bf{y}}_i{\bf{y}}_i^{\text T}+\lambda {\bf{x}}_u^{\text T}\right)^{\text T}=\left(\sum\limits_{i \in I_u}r_{u,i}{\bf{y}}_i^{\text T}\right)^{\text T} \\
& \quad \Rightarrow \left(\sum\limits_{i \in I_u}{\bf{y}}_i{\bf{y}}_i^{\text T}\right){\bf{x}}_u+\lambda {\bf{x}}_u=\sum\limits_{i \in I_u}r_{u,i}{\bf{y}}_i \\
& \quad \Rightarrow \left(\sum\limits_{i \in I_u}{\bf{y}}_i{\bf{y}}_i^{\text T}+\lambda {\bf{I}}_k\right){\bf{x}}_u=\sum\limits_{i \in I_u}r_{u,i}{\bf{y}}_i
\end{split}
$$
为了化简 \(\sum\limits_{i \in I\_u}{\bf{y}}\_i{\bf{y}}_i^{\text T}\)与 \(\sum\limits_{i \in I\_u}r\_{u,i}{\bf{y}}_i\)，咱们将 \(I_u\)开展。
假如 \(I\_u=\{i\_{c\_1}, \cdots, i\_{c_N}\}\), 其中 N 示意用户 \(u\)评分过的物品数量，\(i_{c_i}\)示意第 \(c_i\)个物品对应的索引 / 序号，借助于 \(I_u\)，咱们有
$$
\sum\limits_{i \in I_u}{\bf{y}}_i{\bf{y}}_i^{\text T}=
\begin{pmatrix}
{\bf{y}}_{c_1}, \cdots,{\bf{y}}_{c_N}
\end{pmatrix}
\begin{pmatrix}
{\bf{y}}_{c_1}^{\text T} \\ \vdots \\{\bf{y}}_{c_N}^{\text T}
\end{pmatrix}={\bf{Y}}_{I_u}^{\text T}{\bf{Y}}_{I_u}
\\
\sum\limits_{i \in I_u}r_{u,i}{\bf{y}}_i=
\begin{pmatrix}{\bf{y}}_{c_1}, \cdots,{\bf{y}}_{c_N}
\end{pmatrix}
\begin{pmatrix}
r_{u,c_1} \\ \vdots \\ r_{u,c_N}
\end{pmatrix}={\bf{Y}}_{I_u}^{\text T}{\bf{R}}_{u,I_u}^{\text T}
$$
其中，\({\bf{Y}}_{I_u}\) 为以 \(I\_u=\{i\_{c\_1}, \cdots i\_{c_N}\}\)为行号在物品矩阵 \({\bf{Y}}\)中选取的 \(N\)个行向量造成的 子矩阵
\({\bf{R}}_{u,I_u}\)为以 \(I\_u=\{i\_{c\_1}, \cdots i\_{c_N}\}\)为索引，在评分矩阵 \({\bf{R}}\)的第 \(u\)行的行向量中选取的 \(N\)个元素，造成的 子行向量
因而，咱们有
\(\left({\bf{Y}}_{I\_u}^{\text T}{\bf{Y}}\_{I\_u}+\lambda {\bf{I}}\_k\right){\bf{x}}\_u={\bf{Y}}\_{I\_u}^{\text T}{\bf{R}}\_{u,I\_u}^{\text T} \\ \quad \Rightarrow {\bf{x}}\_u=\left({\bf{Y}}_{I\_u}^{\text T}{\bf{Y}}\_{I\_u}+\lambda {\bf{I}}\_k\right)^{-1}{\bf{Y}}_{I\_u}^{\text T}{\bf{R}}\_{u,I_u}^{\text T}\)
网上的博客，许多博主给出相似上面模式的论断不是很谨严，次要是 损失函数 的了解不到位导致的。
\({\bf{x}}\_u=\left({\bf{\color{red} Y}}^{\text T}{\bf{\color{red} Y}}+\lambda {\bf{I}}\_k\right)^{-1}{\bf{\color{red} Y}}^{\text T}{\bf{\color{red} R}}_{u}^{\text T}\)
同理，咱们定义物品 i 被评分的用户汇合为 \(U\_i=\{u\_{d\_1}, \cdots u\_{d_M}\}\)
依据对称性可得
\({\bf{y}}\_i=\left({\bf{X}}\_{U\_i}^{\text T}{\bf{X}}\_{U\_i}+\lambda {\bf{I}}\_k\right)^{-1}{\bf{X}}_{U\_i}^{\text T}{\bf{R}}\_{i,U_i}\)
其中，\({\bf{X}}_{U_i}\)为以 \(U\_i=\{u\_{d\_1}, \cdots, u\_{d_M}\}\)为行号在用户矩阵 \({\bf{X}}\)中选取的 \(M\)个行向量造成的 子矩阵
\({\bf{R}}_{i,U_i}\)为以 \(U\_i=\{u\_{d\_1}, \cdots, u\_{d_M}\}\)为索引，在评分矩阵 \({\bf{R}}\)的第 i 列的列向量中选取的 \(M\)个元素，造成的 子列向量
此外，\(\mathbf{I}_k\)为单位矩阵
如果读者感觉上述的推导还是很形象，咱们也给一个具体实例来领会一下 两头过程
\(\begin{pmatrix} 0 & r_{1,2} & r_{1,3} & 0 \\ r_{2,1} & 0 & r_{2,3} & 0 \\ 0 & r_{3,2} & 0 & r_{1,3} \\ 0 & r_{2,2} & r_{2,3} & r_{2,4} \\ \end{pmatrix} \approx \begin{pmatrix} x_{1,1} & x_{1,2} \\ x_{2,1} & x_{2,2} \\ x_{3,1} & x_{3,2} \\ x_{4,1} & x_{4,2} \end{pmatrix} \begin{pmatrix} y_{1,1} & y_{1,2} \\ y_{2,1} & y_{2,2} \\ y_{3,1} & y_{3,2} \\ y_{4,1} & y_{4,2} \end{pmatrix}^{\text T} \\ \Rightarrow {\bf{R}} \approx {\bf{X}} {\bf{Y}}^{\text T}\)
留神到损失函数是一个标量，这里咱们只开展波及到 \(x_{1,1}, x_{1,2}\)的项，如下所示
\(L=\sum\limits_{\color{red}{(u,i) \text{is known}}}(r_{u,i} – {\bf{x}}\_u^{\text{T}}{\bf{y}}\_i)^2 =(\color{blue}{r_{1,2}} – \color{red}{x_{1,1}}y_{2,1} – \color{red}{x_{1,2}}y_{2,2})^2 + (\color{blue}{r_{1,3}} – \color{red}{x_{1,1}}y_{3,1} – \color{red}{x_{1,2}}y_{3,2})^2 + \cdots\)
让损失函数对 x_{1,1}, x_{1,2}别离求偏导数能够失去
\(\frac{\partial{L}}{\partial{\color{red}{x_{1,1}}}}=2(\color{blue}{r_{1,2}} – \color{red}{x_{1,1}}y_{2,1}-\color{red}{x_{1,2}}y_{2,2})(-y_{2,1}) + 2(\color{blue}{r_{1,3}} – \color{red}{x_{1,1}}y_{3,1}-\color{red}{x_{1,2}}y_{3,2})(-y_{3,1}) = 0 \\ \frac{\partial{L}}{\partial{\color{red}{x_{1,2}}}}=2(\color{blue}{r_{1,2}} – \color{red}{x_{1,1}}y_{2,2}-\color{red}{x_{1,2}}y_{2,2})(-y_{2,2}) + 2(\color{blue}{r_{1,3}} – \color{red}{x_{1,1}}y_{3,1}-\color{red}{x_{1,2}}y_{3,2})(-y_{3,2}) = 0\)
写成矩阵模式可得
\(\begin{pmatrix} y_{2,1} & y_{3,1} \\ x_{2,2} & x_{3,2} \\ \end{pmatrix} \begin{pmatrix} y_{2,1} & y_{2,2} \\ y_{3,1} & y_{3,2} \\ \end{pmatrix} \begin{pmatrix} \color{red}{x_{1,1}} \\ \color{red}{x_{1,2}} \\ \end{pmatrix} = \begin{pmatrix} y_{2,1} & y_{3,1} \\ x_{2,2} & x_{3,2} \\ \end{pmatrix} \begin{pmatrix} \color{blue}{r_{1,2}} \\ \color{blue}{r_{1,3}} \\ \end{pmatrix}\)
利用咱们上述的规定，很容易测验咱们导出的论断。
总结来说，ALS 的整个算法过程只有两步，波及 2 个循环，如下图所示：
算法应用 RMSE（root-mean-square error）评估误差。
\(rsme = \sqrt{\frac{1}{|K|}\sum\limits_{(u,i) \in K}(r_{u,i}-{\bf{x}}\_u^{\text T}{\bf{y}}\_i)^2}\)
当 RMSE 值变动很小时或者达到最大迭代步骤时，满足收敛条件，进行迭代。
“Talk is cheap. Show me the code.”作为小练习，咱们给出上述伪代码的 Python 实现。
import numpy as np
from scipy.linalg import solve as linear_solve
# 评分矩阵 5 x 6
R = np.array([[4, 0, 2, 5, 0, 0], [3, 2, 1, 0, 0, 3], [0, 2, 0, 3, 0, 4], [0, 3, 3,5, 4, 0], [5, 0, 3, 4, 0, 0]])
m = 5 # 用户数
n = 6 # 物品数
k = 3 # 隐向量的维度
_lambda = 0.01 # 正则化系数
# 随机初始化用户矩阵, 物品矩阵
X = np.random.rand(m, k)
Y = np.random.rand(n, k)
# 每个用户打分的物品汇合
X_idx_dict = {1: [1, 3, 4], 2: [1, 2, 3, 6], 3: [2, 4, 6], 4: [2, 3, 4, 5], 5: [1, 3, 4]}
# 每个物品被打分的用户汇合
Y_idx_dict = {1: [1, 2, 5], 2: [2, 3, 4], 3: [1, 2, 4, 5], 4: [1, 3, 4, 5], 5: [4], 6: [2, 3]}# 迭代 10 次
for iter in range(10):
for u in range(1, m+1):
Iu = np.array(X_idx_dict[u])
YIu = Y[Iu-1]
YIuT = YIu.T
RuIu = R[u-1, Iu-1]
xu = linear_solve(YIuT.dot(YIu) + _lambda * np.eye(k), YIuT.dot(RuIu))
X[u-1] = xu
for i in range(1, n+1):
Ui = np.array(Y_idx_dict[i])
XUi = X[Ui-1]
XUiT = XUi.T
RiUi = R.T[i-1, Ui-1]
yi = linear_solve(XUiT.dot(XUi) + _lambda * np.eye(k), XUiT.dot(RiUi))
Y[i-1] = yi最终，咱们打印用户矩阵，物品矩阵，预测 的评分矩阵如下，能够看到预测的评分矩阵十分迫近 原始 评分矩阵。
# X
array([[1.30678487, 2.03300876, 3.70447639],
[4.96150381, 1.03500693, 1.62261161],
[6.37691007, 2.4290095 , 1.03465981],
[0.41680155, 3.31805612, 3.24755801],
[1.26803845, 3.57580564, 2.08450113]])
# Y
array([[0.24891282, 1.07434519, 0.40258993],
[0.12832662, 0.17923216, 0.72376732],
[-0.00149517, 0.77412863, 0.12191856],
[0.12398438, 0.46163336, 1.05188691],
[0.07668894, 0.61050204, 0.59753081],
[0.53437855, 0.20862131, 0.08185176]])
# X.dot(Y.T) 预测评分
array([[4.00081359, 3.2132548 , 2.02350084, 4.9972158 , 3.55491072, 1.42566466],
[3.00018371, 1.99659282, 0.99163666, 2.79974661, 1.98192672, 3.00005934],
[4.61343295, 2.00253692, 1.99697545, 3.00029418, 2.59019481, 3.99911584],
[4.97591903, 2.99866546, 2.96391664, 4.99946603, 3.99816006, 1.18076534],
[4.99647978, 2.31231627, 3.02037696, 4.0005876 , 3.5258348 , 1.59422188]])
# 原始评分矩阵
array([[4, 0, 2, 5, 0, 0],
[3, 2, 1, 0, 0, 3],
[0, 2, 0, 3, 0, 4],
[0, 3, 3, 5, 4, 0],
[5, 0, 3, 4, 0, 0]])三、Spark ALS 利用
Spark 的外部实现并不是咱们下面所列的算法，然而外围原理是齐全一样的，Spark 实现的是上述伪代码的分布式版本，具体算法参考 Large-scale Parallel Collaborative Filtering for the Netflix Prize。其次，查阅 Spark 的官网文档，咱们也留神到，Spark 应用的惩办函数与咱们上文的有轻微的差异。
\(\lambda \left( \sum\limits_{u}{\color{red}{n\_u}\bf{x}}\_u^{\text T}{\bf{x}}\_u+\sum\limits\_{i}{\color{red}{n\_i}\bf{y}}\_i^{\text T}{\bf{y}}_i\right)\)
其中 n\_u, n\_i 别示意用户 u 打分的物品数量和物品 i 被打分的用户数量。即
\(\begin{cases} n\_u = |I\_u| \\ n\_i = |U\_i| \\ \end{cases}\)
本大节通过两个案例来理解 Spark ALS 的具体应用，以及在面对互联网理论工程场景下的利用。
3.1 Demo 案例
以第一节给出的数据为例，将三元组 (User, Item, Rating) 组织为als-demo-data.csv，该 demo 数据集波及 5 个用户和 6 个物品。
userId,itemId,rating
1,1,4
1,3,2
1,4,5
2,1,3
2,2,2
2,3,1
2,6,3
3,2,2
3,4,3
3,6,4
4,2,3
4,3,3
4,4,5
4,5,4
5,1,5
5,3,3
5,4,4应用 Spark 的 ALS 类应用非常简单，只需将三元组 (User, Item, Rating) 数据输出模型进行训练。
import org.apache.spark.sql.SparkSession
import org.apache.spark.ml.recommendation.ALS
val spark = SparkSession.builder().appName("als-demo").master("local[*]").getOrCreate()
val rating = spark.read
.options(Map("inferSchema" -> "true", "delimiter" -> ",", "header" -> "true"))
.csv("./data/als-demo-data.csv")
// 展现前 5 条评分记录
rating.show(5)
val als = new ALS()
.setMaxIter(10) // 迭代次数，用于最小二乘交替迭代的次数
.setRank(3) // 隐向量的维度
.setRegParam(0.01) // 惩办系数
.setUserCol("userId") // user_id
.setItemCol("itemId") // item_id
.setRatingCol("rating") // 评分列
val model = als.fit(rating) // 训练模型
// 打印用户向量和物品向量
model.userFactors.show(truncate = false)
model.itemFactors.show(truncate = false)
// 给所有用户举荐 2 个物品
model.recommendForAllUsers(2).show()上述代码在控制台输入后果如下：
+------+------+------+
|userId|itemId|rating|
+------+------+------+
| 1| 1| 4|
| 1| 3| 2|
| 1| 4| 5|
| 2| 1| 3|
| 2| 2| 2|
+------+------+------+
only showing top 5 rows
+---+------------------------------------+
|id |features |
+---+------------------------------------+
|1 |[-0.17339179, 1.3144133, 0.04453602]|
|2 |[-0.3189066, 1.0291641, 0.12700711] |
|3 |[-0.6425665, 1.2283803, 0.26179287] |
|4 |[0.5160747, 0.81320006, -0.57953185]|
|5 |[0.645193, 0.26639006, 0.68648624] |
+---+------------------------------------+
+---+-----------------------------------+
|id |features |
+---+-----------------------------------+
|1 |[2.609607, 3.2668495, 3.554771] |
|2 |[0.85432494, 2.3137972, -1.1198239]|
|3 |[3.280517, 1.9563107, 0.51483333] |
|4 |[3.7446978, 4.259611, 0.6640027] |
|5 |[1.6036265, 2.5602736, -1.8897828] |
|6 |[-1.2651576, 2.4723763, 0.51556784]|
+---+-----------------------------------+
+------+--------------------------------+
|userId|recommendations |
+------+--------------------------------+
|1 |[[4, 4.9791617], [1, 3.9998217]]| // 对应物品的序号和预测评分
|2 |[[4, 3.273963], [6, 3.0134287]] |
|3 |[[6, 3.9849386], [1, 3.2667015]]|
|4 |[[4, 5.011649], [5, 4.004795]] |
|5 |[[1, 4.994258], [4, 4.0065994]] |
+------+--------------------------------+咱们应用 numpy 来验证 Spark 的后果，并且用 Excel 可视化评分矩阵。
import numpy as np
X = np.array([[-0.17339179, 1.3144133, 0.04453602],
[-0.3189066, 1.0291641, 0.12700711],
[-0.6425665, 1.2283803, 0.26179287],
[0.5160747, 0.81320006, -0.57953185],
[0.645193, 0.26639006, 0.68648624]])
Y = np.array([[2.609607, 3.2668495, 3.554771],
[0.85432494, 2.3137972, -1.1198239],
[3.280517, 1.9563107, 0.51483333],
[3.7446978, 4.259611, 0.6640027],
[1.6036265, 2.5602736, -1.8897828],
[-1.2651576, 2.4723763, 0.51556784]])
R_predict = X.dot(Y.T)
R_predict输入预测的评分矩阵如下：
array([[3.99982136, 2.84328038, 2.02551472, 4.97916153, 3.0030386, 3.49205357],
[2.98138452, 1.96660155, 1.03257371, 3.27396294, 1.88351875, 3.01342882],
[3.26670123, 2.0001004 , 0.42992289, 3.00003605, 1.61982132, 3.98493822],
[1.94325135, 2.97144913, 2.98550149, 5.011649 , 4.00479503, 1.05883274],
[4.99425778, 0.39883335, 2.99113433, 4.00659955, 0.41937014, 0.19627587]])从 Excel 可视化的评分矩阵能够察看到 预测 的评分矩阵十分迫近 原始 的评分矩阵，以 user- 3 为例，Spark 举荐的物品是 item- 6 和 item-1, [[6, 3.9849386], [1, 3.2667015]]，这和 Excel 展现的预测评分矩阵完全一致。
从 Spark 函数 recommendForAllUsers() 给出的后果来看，Spark 外部并没有 去除 用户曾经购买的物品。
3.2 工程利用
在互联网场景，用户数 \(m\)(千万~ 亿 级别) 和物品数 \(n\)(10 万~100 万 级别) 规模很大，App 的埋点数据个别会保留在 HDFS 中，以互联网的长视频场景为例，用户的埋点信息最终聚合为用户行为表 t\_user\_behavior。
行为表蕴含用户的 imei，物品的 content-id，然而没有间接的用户评分，实际中咱们的解决方案是利用用户的其余行为进行加权得出用户对物品的评分。即
rating = w1 * play_time (播放时长) + w2 * finsh\_play\_cnt (实现的播放次数) + w3 * praise_cnt (点赞次数) + w4 * share_cnt (分享次数) + 其余适宜于你业务逻辑的指标
其中, wi为每个指标对应的权重。
如下的代码块演示了工程实际中对大规模用户和商品场景进行举荐的流程。
import org.apache.spark.ml.feature.{IndexToString, StringIndexer}
// 从 hive 加载数据，并利用权重公式计算用户对物品的评分
val rating_df = spark.sql("select imei, content_id, 权重公式计算评分 as rating from t_user_behavior group by imei, content_id")
// 将 imei 和 content_id 转换为序号，Spark ALS 入参要求 userId, itemId 为整数
// 应用 org.apache.spark.ml.feature.StringIndexer
val imeiIndexer = new StringIndexer().setInputCol("imei").setOutputCol("userId").fit(rating_df)
val contentIndexer = new StringIndexer().setInputCol("content_id").setOutputCol("itemId").fit(rating_df)
val ratings = contentIndexer.transform(imeiIndexer.transform(rating_df))
// 其余 code，相似于上述 demo
val model = als.fit(ratings)
// 给每个用户举荐 100 个物品
val _userRecs = model.recommendForAllUsers(100)
// 将 userId, itemId 转换为原来的 imei 和 content_id
val imeiConverter = new IndexToString().setInputCol("userId").setOutputCol("imei").setLabels(imeiIndexer.labels)
val contentConverter = new IndexToString().setInputCol("itemId").setOutputCol("content_id").setLabels(contentIndexer.labels)
val userRecs = imeiConverter.transform(_userRecs)
// 离线保留供线上调用
userRecs.foreachPartition {
// contentConverter 将 itemId 转换为 content_id
// 保留 redis 逻辑
}值得注意的是，上述的工程场景还有一种解决方案，即 隐式反馈 。用户给商品评分很繁多，在理论的场景中，用户未必会给物品打分，然而大量的用户行为，同样可能间接反映用户的爱好，比方用户的购买记录、搜寻关键字，退出购物车，单曲循环播放同一首歌。咱们将这些间接用户行为称之为 隐式反馈 ，以区别于评分对应的 显式反馈。胡一凡等人在论文 Collaborative filtering for implicit feedback datasets 中针对隐式反馈场景提出了 ALS-WR 模型 (ALS with Weighted-λ-Regularization)，并且 Spark 官网也实现了该模型，咱们将在当前的文章中介绍该模型。
四、总结
本文从举荐的场景登程，引出了协同过滤这一经典的举荐算法，并且由此解说了被 Spark 惟一实现和保护的矩阵合成算法，具体推导了显示反馈下矩阵合成的实践原理，并且给出了 Python 版本的单机实现，可能让读者更好的了解矩阵这一算法，最初咱们以 demo 和工程实际两个实例解说了 Spark ALS 的应用，可能让没有接触过举荐算法的同学有个直观的了解，用实践与实际的模式明确矩阵合成这一举荐算法背地的原理。
参考文献：
- 王喆, 深度学习举荐零碎
- Hu, Yifan, Yehuda Koren, and Chris Volinsky. “Collaborative filtering for implicit feedback datasets.” 2008 Eighth IEEE International Conference on Data Mining. IEEE, 2008.
- Zhou, Yunhong, et al. “Large-scale parallel collaborative filtering for the Netflix prize.” International conference on algorithmic applications in management. Springer, Berlin, Heidelberg, 2008.