推荐系统学习 - (1)基本算法

最近想了解下推荐系统，阅读了《推荐系统实践》（项亮），本文简单介绍推荐系统常用算法的原理，大部分内容来自项亮大牛的书籍。

1. 推荐系统简介

1.1 推荐系统是什么？

随着信息技术的发展，互联网上的信息量快速增长。为了在众多信息中找到想要的内容，常用的方式有——

• 分类目录，如雅虎、hao123，将网站分门别类，但只能覆盖热门网站
• 搜索引擎，如谷歌、百度

与分类目录和搜索引擎相同，推荐系统也是一种针对信息过载的解决方案，通过分析用户的行为、兴趣等数据，主动给用户推荐满足其兴趣和需求的信息，区别在于——

• 对用户来说，用户不需要主动提供明确的需求，推荐系统会根据其历史行为等数据建模，主动推荐信息
• 对信息来说，推荐系统可以更好地挖掘长尾信息，而不仅仅是热门信息

推荐系统已经在很多互联网产品中使用，常见的使用场景有——

• 电子商务，如淘宝的【猜你喜欢】和【类似商品推荐】
• 视频网站，如爱奇艺的【猜你在追】和【精彩推荐】，短视频、小说、漫画等内容产品也类似
• 音乐应用，如豆瓣FM、QQ音乐的【个性电台】，根据收听历史推荐歌曲
• 社交网络，如QQ的【好友推荐】，或利用社交网络推荐信息给用户
• 基于位置的服务，如美团推荐附近的美食
• 个性化广告，根据用户的兴趣，给不同用户投放不同的广告

1.2 推荐系统的类型

推荐系统根据优化目标的不同，常被分为两种类型——

• 评分预测问题，即给定物品，预测用户对其的打分情况，如Netflix的电影推荐。在评分预测问题中，损失函数是均方根误差RMSE，最终推荐给用户的物品是用户对其打分最高（最喜欢）的物品
• TopN问题，是指使用打分函数对物品进行排序，给出N个用户最可能选择的物品列表

由于早期推荐系统研究是基于电影评分数据的评分预测问题，因此绝大多数推荐系统研究都是基于用户评分数据的评分预测。而在实际应用中，TopN问题更加常用，原因在于——

• 评分预测问题依赖用户对物品的评分这类显性数据，而大多数场景下我们只有用户浏览行为等隐性数据
• 推荐系统的目的是找到用户感兴趣的电影，预测用户是否会观看电影比预测用户观看电影后的评分更重要，可能存在电影用户看过后会打出高分，但用户看的可能性非常小

本文介绍的推荐系统算法是用于求解TopN问题的。

2. 推荐系统常用算法

实现推荐系统的算法有很多，但大致可分为三类，下面会依次介绍其基本原理。

在介绍的过程中，使用的数据为用户的隐性数据，如浏览行为。

2.1 协同过滤算法

协同过滤算法（也称为基于邻域的算法）分为两大类，分别是基于用户的协同过滤（UserCF）和基于物品的协同过滤（ItemCF），是推荐系统中最经典的算法。

2.1.1 UserCF基础算法

UserCF的思想是根据用户行为数据，找到与目标用户有相似兴趣的其他用户，给用户推荐其他用户喜欢的物品。

其算法流程分为两步：

1. 找到与目标用户兴趣相似的K个用户集合，计算用户相似度可以使用余弦相似度，如下：

$w_{uv}=\frac{|N(u)\cap N(v)|}{\sqrt{|N(u)||N(v)|}}\\其中，N(u)表示用户u产生过行为的物品集合$wuv​=∣N(u)∣∣N(v)∣​∣N(u)∩N(v)∣​其中，N(u)表示用户u产生过行为的物品集合

2. 在最相似的K个用户中找到他们喜欢且目标用户没有产生过行为的物品，用以下公式计算用户 $u$u 对物品 $i$i 的感兴趣程度，排序后推荐前N个物品给目标用户：

$p(u,i)=\sum_{v\in S(u,K)\cap N(i)}w_{uv}r_{vi}\\ 其中,S(u,K)是用户u最相似的K个用户集合,N(i)为对i有过行为的用户集合,\\ r_{vi}为用户v对物品i的评分,由于数据为隐性数据而不是评分数据，r_{vi}设为常数1$p(u,i)=v∈S(u,K)∩N(i)∑​wuv​rvi​其中,S(u,K)是用户u最相似的K个用户集合,N(i)为对i有过行为的用户集合,rvi​为用户v对物品i的评分,由于数据为隐性数据而不是评分数据，rvi​设为常数1

这样，就可以得到目标用户最感兴趣的TopN物品列表。

2.1.2 ItemCF基础算法

ItemCF的思想是根据用户行为数据，计算物品间的相似度，基于用户以往的喜好记录，推荐给用户相似的物品。

其算法流程分为两步：

1. 计算物品之间的相似度，可使用余弦相似度，如下：

$w_{ij}=\frac{|N(i)\cap N(j)|}{\sqrt{|N(i)||N(j)|}}\\其中，N(i)表示对物品i产生过行为的用户集合$wij​=∣N(i)∣∣N(j)∣​∣N(i)∩N(j)∣​其中，N(i)表示对物品i产生过行为的用户集合

2. 用如下共识计算目标用户 $u$u 对物品 $j$j 的感兴趣程度，排序后推荐前N个物品给目标用户。从公式可以看到，与用户喜欢过的物品越相似，计算的值越高

$p_{uj}=\sum_{i \in N(u)\cap S(j,K)}w_{ij}r_{ui}$puj​=i∈N(u)∩S(j,K)∑​wij​rui​

这样，就可以得到目标用户最感兴趣的TopN物品列表。

2.1.3 相似度修正

上述介绍的算法是比较简单和原始的版本，使用的数据也只有用户的行为数据。

实际场景中，用户的画像信息、物品的属性、时间空间信息都会加入考虑，算法也会相应地改进以适应实际需求。

以上述介绍的用户相似度计算方式为例，在实际场景中，我们认为热门物品对相似度的贡献比冷门物品小，也就是两个人对冷门物品都产生过行为更能说明兴趣相似，因此用户相似度可以如下对热门物品做惩罚：
$w_{uv}=\frac{\sum_{i\in N(u)\cap N(v)} log\frac{1}{1+|N(i)|}}{\sqrt{|N(u)||N(v)|}}\\其中，N(u)表示用户u产生过行为的物品集合,N(i)表示对物品i产生过行为的用户集合$wuv​=∣N(u)∣∣N(v)∣​∑i∈N(u)∩N(v)​log1+∣N(i)∣1​​其中，N(u)表示用户u产生过行为的物品集合,N(i)表示对物品i产生过行为的用户集合
类似地，在物品相似度中认为活跃用户的贡献小于非活跃用户，因此物品相似度可以如下对活跃用户做惩罚：
$w_{ij}=\frac{\sum_{u \in N(i)\cap N(j)}log \frac{1}{1+|N(u)|}}{\sqrt{|N(i)||N(j)|}}\\其中，N(u)表示用户u产生过行为的物品集合,N(i)表示对物品i产生过行为的用户集合$wij​=∣N(i)∣∣N(j)∣​∑u∈N(i)∩N(j)​log1+∣N(u)∣1​​其中，N(u)表示用户u产生过行为的物品集合,N(i)表示对物品i产生过行为的用户集合

2.1.4 UserCF与ItemCF对比

从上述UserCF与ItemCF的原理看，UserCF的推荐结果反映了与目标用户兴趣相似的小群体的热点，ItemCF的推荐结果是维护目标用户的历史兴趣，从不同角度对比如下：

UserCF常在新闻网站中使用，因为新闻数量很多，时效性很强，且从冷启动角度看，新的新闻出现后可快速用于推荐；

ItemCF则在电商、视频网站中使用，在这些网站中物品不容易过时，用户的兴趣也更持久。

2.2 隐语义模型

LFM（Latent Factor Model），隐语义模型是推荐系统中很热门的研究话题。

隐语义模型最开始是在NLP领域中使用，用于找到文本的隐含语义，相关的主题模型有LSA、pLSA、LDA等，在这篇回答中解释得很清楚，建议看一下：既然 LDA 是一种比 PLSA 更高级的模型，为啥百度还在用 PLSA？

在NLP的主题模型中，通过在单词与文档之间引入 【主题】 这一隐含变量，来挖掘文本的语义，比如在上面回答中举到的例子：

文本1：“马云、马化腾和李彦宏”

文本2：“阿里巴巴、腾讯和百度掌门人”

如果通过单词来计算两个文本的距离，可能会得出两个文本完全不相关的结论。

但若把两个文本的 【主题】 抽离出来，会得到“企业家”、“互联网”、“BAT”等等这些主题，这样就发现两句话主题上是完全相同的，由此可知这两句话具有很高的相似性。

将LFM应用到推荐系统中，则是在用户和物品之间引入【类别】这一隐含变量——对于某个用户，首先得到他的兴趣分类，再从属于该分类的物品中挑选他可能喜欢的物品。

2.2.1 算法原理

假设用户的兴趣分类（或物品的分类）有 $F$F 种，用如下公式表示用户对物品的感兴趣程度——
$Preference(u,i)=r_{ui}=p_uq_i=\sum_{k=1}^{F}p_{u,k}q_{k,i}$Preference(u,i)=rui​=pu​qi​=k=1∑F​pu,k​qk,i​
其中 $r_{ui}$rui​ 表示用户是否对物品 $i$i 产生行为，$p_u$pu​ 是用户-分类矩阵 $P$P 的第 $u$u 行，表示用户 $u$u 与各个兴趣分类的关系，$q_i$qi​ 是分类-物品矩阵 $Q$Q 的第 $i$i 列，表示物品 $i$i 与各个兴趣分类的关系。

因此，只要求解出两个矩阵 $P$P 和 $Q$Q，根据感兴趣程度的排序就可以推荐TopN列表给目标用户。

求解过程如下：

1. 由于我们的数据是隐性数据，即只有用户对哪些物品产生过行为，对应的 $r_{ui} = 1$rui​=1，为了求解矩阵，需要先按如下原则采集负样本，对应的 $r_{ui}=0$rui​=0——

• 对每个用户，保证正负样本数平衡
• 对每个用户采集负样本时，要选取热门但用户没有行为的物品

2. 得到正负样本后，则需要最小化以下损失函数，其中后两项为防止过拟合的正则化项

$C=\sum(r_{ui}-\hat r_{ui})^2+\lambda||p_u||^2+\lambda||q_i||^2=\sum(r_{ui}-\sum_{k=1}^{F}p_{u,k}q_{k,i})^2+\lambda||p_u||^2+\lambda||q_i||^2$C=∑(rui​−r^ui​)2+λ∣∣pu​∣∣2+λ∣∣qi​∣∣2=∑(rui​−k=1∑F​pu,k​qk,i​)2+λ∣∣pu​∣∣2+λ∣∣qi​∣∣2

3. 对参数求偏导，有

$\frac{\partial C}{\partial p_{u,k}}=-2q_{k,i}+2\lambda p_{u,k}\\ \frac{\partial C}{\partial q_{k,i}}=-2p_{u,k}+2\lambda q_{k,i}$∂pu,k​∂C​=−2qk,i​+2λpu,k​∂qk,i​∂C​=−2pu,k​+2λqk,i​

4. 使用梯度下降法，迭代求解参数值，递推公式如下，其中 $\alpha$α 是学习速率

$p_{u,k}=p_{u,k}+\alpha(q_{k,i}-\lambda p_{u,k})\\ q_{k,i}=q_{k,i}+\alpha(p_{u,k}-\lambda q_{k,i})$pu,k​=pu,k​+α(qk,i​−λpu,k​)qk,i​=qk,i​+α(pu,k​−λqk,i​)

2.2.2 LFM与协同过滤对比

• 离线计算的空间复杂度：UserCF需要计算用户相似度表，空间复杂度为$O(M^2)$O(M2)，ItemCF需要计算物品相似度表，空间复杂度为 $O(N^2)$O(N2)。而LFM存储两个矩阵，假设有 $F$F 个隐类，则空间复杂度为 $O(F*(M+N))$O(F∗(M+N))，在用户数或物品数很高的情况下，LFM所需空间小得多
• 离线计算的时间复杂度：两种算法时间复杂度没有大的差别
• 在线实时推荐：UserCF和ItemCF将相似度表缓存在内存中，可以在线进行实时推荐，如用户喜欢新的物品后，ItemCF可以实时推荐类似的物品给该用户；而LFM需要计算用户对所有物品的感兴趣程度，复杂度太高，无法实时推荐
• 推荐结果解释：ItemCF支持很好的推荐解释，LFM这类神经网络可解释性则比较差

2.3 基于图的模型

用户行为可以用二分图表示，如下图所示，很多图的算法也可以应用到推荐系统上，此处介绍基于随机游走的PersonalRank算法。

PersonalRank算法跟用于网页排序的PageRank算法原理基本相同，其思路是，假设给用户 $u$u 做推荐，可以从对应图上的 $v_u$vu​ 节点出发进行随机游走，最终每个节点被访问的概率（Rank值）会收敛，排序即可得到用户的推荐列表。

随机游走的规则为：

1. 初始状态下，$v_u$vu​ 节点的Rank值为1，其余节点为0，每次游走，节点上的Rank值也会传递到下一个节点

2. 在每个节点上，有 $\alpha$α 的概率继续随机游走，即以相等的概率游走到该节点指向的任意节点上

   • 因此，传递到下一节点的Rank值期望为 $\frac{Rank(v)}{|out(v)|}$∣out(v)∣Rank(v)​，$out(v)$out(v) 为节点 $v$v 指向的顶点集
   • 因此，每个节点可以得到的Rank值期望为 $\alpha \sum_{v' \in in(v)} \frac{Rank(v')}{|out(v')|}$α∑v′∈in(v)​∣out(v′)∣Rank(v′)​，$in(v)$in(v) 为指向节点 $v$v 的顶点集

3. 在每个节点上，剩余有 $1-\alpha$1−α 的概率回到 $v_u$vu​ 起点

   • 因此，起点 $v_u$vu​ 还可以得到额外的Rank值 $\sum_v (1-\alpha) Rank(v)=1-\alpha$∑v​(1−α)Rank(v)=1−α

因此用迭代公式表达上述随机游走的过程如下：
$Rank(v)=\left\{ \begin{aligned} \alpha & \sum_{v' \in in(v)} \frac{Rank(v')}{|out(v')|}&(v \ne v_u) \\ ( & 1-\alpha) + \alpha \sum_{v' \in in(v)} \frac{Rank(v')}{|out(v')|} &(v=v_u) \end{aligned} \right.$Rank(v)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​α(​v′∈in(v)∑​∣out(v′)∣Rank(v′)​1−α)+αv′∈in(v)∑​∣out(v′)∣Rank(v′)​​(v​=vu​)(v=vu​)​
基于图的推荐算法(PersonalRank)，这篇博客中有详细的代码实现和注释，可以参考一下。

上述算法需要在全图进行迭代，时间复杂度很高，可以通过转化为矩阵运算求解，此处不再说明。

Reference

1. 《推荐系统实践》，项亮
2. 既然 LDA 是一种比 PLSA 更高级的模型，为啥百度还在用 PLSA？
3. 基于图的推荐算法(PersonalRank)