第二章—前深度学习时代—推荐系统的进化之路-(1)协同过滤—基于邻域的方法

为什么还要学习传统推荐系统方法

尽管当今推荐系统、计算广告和其他工业互联网领域中深度学习已经成为了主流方法，但了解传统推荐系统方法依然是必要的，理由有二：

1. 即使深度学习流行的今日，像协同过滤、逻辑回归、因子分解机等方法依然凭借可解释性强、环境要求低、易于快速训练和部署简单等优势，活跃在大量应用场景中。依然有许多领域把LR当作基线不断去迭代。
2. 传统推荐模型是深度学习模型的基础。比如，神经网络的基本单元是神经元，应用广泛的LR是神经元（感知机）的另一种表示形式。而深度学习中也有很多基于因子分解机的方法。另外，协同过滤中的因子分解方法使用的梯度下降训练方法更是沿用至深度学习时代。像基于时序信息的协同过滤方法，深度学习也有所借鉴。方法无新旧，了解本质才能了解每种建模方法背后的深刻认知和原理。

传统推荐模型的演化关系图

传统推荐模型的发展脉络主要由以下部分组成：
（1）协同过滤算法族（紫色部分）
（2）逻辑回归模型族（黄色部分）
（3）因子分解机模型族（绿色部分）
（4）组合模型（橙色部分）

协同过滤算法族

毫无疑问，协同过滤是推荐系统领域影响力最大、应用最广泛的模型。协同过滤在互联网领域大放异彩是2003年Amazon发表的论文《Amazon.com Recommenders Item-to-Item Collaborative Filtering》。

协同过滤方法简介

（以下参考《推荐系统(技术、评估及高效算法)》）
协同过滤方法大致可以分为两类：基于邻域的方法和基于模型的方法。
基于邻域的方法：基于用户的推荐和基于物品的推荐。
基于用户的推荐：目标用户对某一物品的感兴趣程度是利用对物品已经评过分并且和目标用户有相似评分模式的其他用户（近邻）来估计的。
基于物品的推荐：根据某一用户对相似于目标物品的评分来预测该用户对目标物品的评分。
基于模型的方法：使用属性构建用户和物品之间的联系，属性代表在系统中用户和物品的潜在特征。包括贝叶斯聚类、潜在语义分析、潜在狄利克雷分布、最大熵、玻尔兹曼机、支持向量机和奇异值分解等。
另外，还有混合推荐方法，如通过多个预测结果融合成一个综合的预测结果等。
基于邻域方法的优势：

1. 简单性：仅有一个参数（用于选取的近邻数目）需要调整。
2. 合理性：可以提供简洁且直观的解释性理由。“构建这件物品的用户也购买了另一件商品”。
3. 高效性：基于模型的系统需要消耗大量时间在训练阶段。但邻域方法可以离线预先计算近邻，线上存储近邻只需要很小的内存，可以提供近乎实时的推荐结果。
4. 稳定性：当用户、物品、评分增加时受到的影响比较小。比如基于物品的推荐方法，一旦物品相似度计算完成，就可以为所有用户作推荐。当新的物品加入时，只需要计算新物品和系统已有物品的相似度。

协同过滤的形式化定义

$U$U : 用户集合
$I$I : 物品集合
$R$R : 评分集合
$S$S : 评分可选的分数集合（如 $S=(1,2,3)$S=(1,2,3) 或 $S=(like,dislike)$S=(like,dislike)
$r_{ui}$rui​ : 用户$u\in U$u∈U对于特定物品$i \in I$i∈I的评分,且$|r_{ui}|\leq 1$∣rui​∣≤1
$U_i$Ui​ : 集合中已经对物品$i$i进行了评分的用户集合
$I_u$Iu​ : 被用户$u$u所评分的物品集合
$I_u \cap I_v$Iu​∩Iv​ : 同时被用户u和v所评分的物品集合
$U_{ij}$Uij​ : 同时对物品i和物品j进行了评分的用户集合
$L(U_a)$L(Ua​) : 用户$u_a$ua​实际最感兴趣的N项物品
$T(u)$T(u) : 根据训练样本为用户u作出的推荐列表
$w_{uv}$wuv​ : 用户u和v的兴趣相近程度
$N(u)$N(u) : 用户u的k近邻，即k个与用户u相似度最高的用户v的集合
$N_i(u)$Ni​(u) : k个和用户u兴趣相近且对物品i已做评分的用户集合
$N_u(i)$Nu​(i) : 用户u已经评分且和物品i评分相近的物品集合。

推荐系统的问题定义

评分预测和最优N项是推荐系统最重要的两个问题。
评分预测：预测某个用户对他未评价过的物品i的评分。
最优N项：没有评分信息时（比如只有用户购买物品的列表），问题转为向用户推荐感兴趣的列表$L(U_a)$L(Ua​)。
评分预测
当有评分值时，定义为回归或分类问题，目标是用学习函数$f: U * I -> S$f:U∗I−>S来预测用户u对于新物品i的评分$f(u,i)$f(u,i)。
评估方法一般用“准确性”，衡量预测准确性的标准一般有两种：平均绝对误差（MAE）和均方根误差（RMAE）：
$MAE(f) = \frac{1}{R_{test}}\sum_{r_{ui} \in R_{test}}|f(u,i) - r_{ui}|$MAE(f)=Rtest​1​rui​∈Rtest​∑​∣f(u,i)−rui​∣
$RMSE(f) = \sqrt{\frac{1}{R_{test}}\sum_{r_{ui} \in R_{test}}(f(u,i) - r_{ui})^2 }$RMSE(f)=Rtest​1​rui​∈Rtest​∑​(f(u,i)−rui​)2​
最优N项
top-N与评分预测是两个问题。一个评分预测更好的模型，不一定会带来更好的top-N推荐。前者是一个list-wise问题，后者是一个point-wise问题。所以在评估时，两个问题的评价指标也不同。
最优N项的评价方法有准确率和召回率：
$Precision(L) = \frac{1}{|U|}\sum_{u \in U} \frac{L(u) \in T(u)}{L(u)}$Precision(L)=∣U∣1​u∈U∑​L(u)L(u)∈T(u)​
$Recall(L) = \frac{1}{|U|}\sum_{u \in U} \frac{L(u) \in T(u)}{T(u)}$Recall(L)=∣U∣1​u∈U∑​T(u)L(u)∈T(u)​

基于邻域的推荐—示例

（下列评分例子来自于《推荐系统(技术、评估及高效算法)》）

-	The Matrix	Titanic	Die Hard	Forrest Gump	Wall-E
John	5	1		2	2
Lucy	1	5	2	5	5
Eric	2	?	3	5	4
Diane	4	3	5	3

本例中，需要预测用户Eric是否要租用电影《Titanic》。从评分表格中可以看出，Eric和Lucy有类似的电影品味。而另一方面，Diane和他有不同的品味。

基于用户的评分预测

基于邻域用户推荐方法的核心是利用和用户u兴趣相近且对物品i做了评分的用户。即用k近邻来做评分的预测。可以利用近邻对物品i的平均评分策略来获得预测评分，公式如下：
$\hat{r}_{ui}=\frac{1}{|N_i(u)|}\sum_{v \in N_i(u)}r_{vi}$r^ui​=∣Ni​(u)∣1​v∈Ni​(u)∑​rvi​
但这个公式没有考虑用户u和每个近邻用户对物品评分相近程度的问题（即用户相似度），所以更通用的解决方式是根据与用户u的兴趣相近程度进行加权，同时做标准化。公式如下：
$\hat{r}_{ui}=\frac{\sum_{v \in N_i(u)}w_{uv} r_{vi}}{\sum_{v \in N_i(u)}|w_{uv}|}$r^ui​=∑v∈Ni​(u)​∣wuv​∣∑v∈Ni​(u)​wuv​rvi​​
分母用绝对值表示是因为负值会让预测评分超过允许范围。
同样也可以用$w_{uv}^{\alpha}$wuvα​代替$w_{uv}$wuv​，其中$\alpha$α是放大因子。当$\alpha>1$α>1时，与用户u最接近的用户评分就越重要。
回到例子中：
假设预测Eric对《Titanic》的评分时，用Lucy和Dinae这两个用户，并且相似度分别为0.75和0.15，则预测评分为：
$\hat{r} = \frac{0.75\times 5+0.15\times 3}{0.75+0.15} \approx 4.67$r^=0.75+0.150.75×5+0.15×3​≈4.67
需要注意：这种方法没有考虑每个用户会使用不同的评分尺度来衡量他们对于相同喜欢程度的物品。解决这个问题可以将近邻评分进行标准化转换,后面会继续讨论这个问题。
####基于物品的推荐
基于物品的推荐方法是通过用户评分相近的物品来进行预测。定义$N_u(i)$Nu​(i)为用户u已经评分且和物品i评分相近的物品集合。则用户u对物品i的预测评分可以通过用户对评分相近物品的评分进行加权平均运算：
$\hat{r}_{ui}=\frac{\sum_{j\in N_u(i)}w_{ij}r_{uj}}{\sum_{j\in N_u(i)}|w_{ij}|}$r^ui​=∑j∈Nu​(i)​∣wij​∣∑j∈Nu​(i)​wij​ruj​​
回到例子中：
假设预测Eric对《Titanic》的评分时，《Titanic》与《Forrest Gump》和《Wall-E》》的相似度权重分别为0.85和0.75，而Eric对这两部电影评分分别是5和4，所以预测评分为：
$\hat{r}=\frac{0.85\times 5 +0.75\times 4}{0.85+0.75}\approx 4.53$r^=0.85+0.750.85×5+0.75×4​≈4.53
另外，不同用户有自己独立的评分尺度，所以也需要对评分标准化（后续讨论这个问题）。

基于物品、用户的推荐方法比较

1. 准确性：推荐系统准确度很大程度依赖于系统中用户数和物品数之间的比例。用户数量远大于物品数量的商业系统中，基于物品的推荐方法更加准确。用户数量小于物品数量的系统中（论文推荐系统），采用基于用户的推荐方法会更有益。
2. 效率：推荐系统的内存和计算效率也依赖于用户和物品的比例。用户远大于物品数量时，基于物品的推荐方法在计算相似度权重方面需要的内存和时间都小于基于用户的方法，反之亦然。当然，对于在线推荐的阶段，复杂度只依赖于有效物品数和近邻数的最大值，这对于基于用户或物品的推荐方法是相同的。
3. 稳定性：用户或物品的改变频率和数量变化。如果系统的有效物品列表对用户来说相对稳定，则选择基于物品的推荐方法跟适用。因为物品相似度依然能将物品推荐给新用户。对于物品列表经常改变的系统（文章推荐系统），基于用户的推荐方法更稳定。
4. 合理性：基于物品的推荐方法更易于证明推荐的合理性。预测中用到的近邻物品列表和相似度权重都可以解释给用户。基于用户的方法比较难做到这一点，因为用户并不认识起到近邻作用的其他用户。
5. 惊喜度：基于物品的推荐方法往往较难给用户带来惊喜度，基本只能产生稳妥或有把握的推荐结果。而基于用户的方法则不然，有可能发觉具有惊喜度的推荐结果。
   惊喜度vs新颖性
   惊喜度：帮助用户找到感兴趣但本不可能发现的物品。
   可以通过一个例子来分辨它与新颖性的差别：推荐给用户一部他喜欢的导演执导的电影，如果用户不知道这部电影，则这是一个新颖性的推荐。但不是一个惊喜度的推荐，因为用户很可能会自己发现这部电影。
   ##基于邻域方法的三因素
   除了选择基于用户还是物品的推荐方法以外，在上述的论述中其实还有一直没有谈论的三个重要的因素：
   1.评分标准化
   2.相似度权重的计算
   3.近邻的选择

评分标准化

用户对物品打分时，每个用户都有自己的评价标准，为了消除这种评价标准的差异，可以对用户的评分进行一些标准化的处理。其中，均值中心化和Z-score是两种通用的标准化机制。

均值中心化

思想：与平均分比较，决定一个评分为正或为负。
对于基于用户的推荐方法：
假设$r_{ui}$rui​为用户对物品i的原始评分，可通过减去他评价的物品集$I_u$Iu​的平均评分$\overline {r}_u$ru​来转为均值中心化评分：
$h(r_{ui})=r_{ui} - \overline {r}_u$h(rui​)=rui​−ru​
于是，可以用下式预测用户评分$r_{ui}$rui​:
$\hat{r}_{ui} = \overline{r}_u + \frac{\sum_{v\in N_i(u)}w_{uv}(r_{vi} - \overline{r}_v)}{\sum_{v\in N_i(u)}|w_{uv}|}$r^ui​=ru​+∑v∈Ni​(u)​∣wuv​∣∑v∈Ni​(u)​wuv​(rvi​−rv​)​
对于基于物品的推荐方法：
$r_{ui}$rui​为用户对物品i的原始评分，可通过减去用户集合$U_i$Ui​对物品i的平均评分$\overline {r}_i$ri​来得到基于物品推荐方法的均值中心化评分。
$h(r_{ui})=r_{ui} - \overline {r}_i$h(rui​)=rui​−ri​
于是，可以用下式预测用户评分$r_{ui}$rui​:
$\hat{r}_{ui} = \overline{r}_i + \frac{\sum_{j\in N_u(i)}w_{ij}(r_{uj} - \overline{r}_j)}{\sum_{j\in N_u(i)}|w_{ij}|}$r^ui​=ri​+∑j∈Nu​(i)​∣wij​∣∑j∈Nu​(i)​wij​(ruj​−rj​)​
均值中心化有一个有趣的性质：用户对物品喜好倾向可以直接观察标准化后的评分值的正负情况。同时评分可以表示用户对该物品的喜好或厌恶的程度。

Z-score标准化

考虑一种情况：用户A和B的平均评分都是3，而用户A评分在1到5之间均匀选择，用户B则基本都是3。如果此时用户B给某一个物品评分5分，这会比用户A给物品评5分更加意外且更有意义，因为这反映了用户B更加喜爱这个物品。
均值中心化移除了针对平均评分的不同感受而导致的偏差，但Z-score标准化还考虑到了个人评分范围不同带来的差异性。
基于用户的推荐方法：
标准化评分等于用户均值中心化评分除以用户评分标准差：
$h(r_{ui})=\frac{r_{ui}-\overline{r}_u}{\sigma_u}$h(rui​)=σu​rui​−ru​​
于是，基于用户的推荐方法预测评分$r_{ui}$rui​可以通过下式计算：
$\hat{r}_{ui} = \overline{r}_u + \frac{\sum_{v\in N_i(u)}w_{uv}(r_{vi} - \overline{r}_v)/\sigma_v}{\sum_{v\in N_i(u)}|w_{uv}|}$r^ui​=ru​+∑v∈Ni​(u)​∣wuv​∣∑v∈Ni​(u)​wuv​(rvi​−rv​)/σv​​
基于物品的推荐方法：
标准化评分等于物品均值中心化评分除以物品评分标准差：
$h(r_{ui})=\frac{r_{ui} - \overline {r}_i}{\sigma_i}$h(rui​)=σi​rui​−ri​​
于是，可以用下式预测用户评分$r_{ui}$rui​:
$\hat{r}_{ui} = \overline{r}_i + \frac{\sum_{j\in N_u(i)}w_{ij}(r_{uj} - \overline{r}_j)/\sigma_j}{\sum_{j\in N_u(i)}|w_{ij}|}$r^ui​=ri​+∑j∈Nu​(i)​∣wij​∣∑j∈Nu​(i)​wij​(ruj​−rj​)/σj​​

评分标准化的选择

如果评分较少时，标准化可能会产生不可预测结果。例如一个用户只是给予一个评分或者几个相同的评分，则标准差就是0，导致了一个不可定义的预测值。
当离散评分范围很大或者是连续值评分时，Z-score方法由于考虑了评分的方差所以更有优势，且比均值中心化更加敏感。

相似度权重的计算

相似度在基于邻域的推荐方法中扮演着双重角色：

1. 选择可信的近邻用于预测评分；
2. 给予不同近邻在预测中的权重。
   它直接影响准确性和性能。

基于关联的相似度

两个向量的相似度经常通过计算两个向量的余弦距离来获得。在基于物品的推荐方法中，这种方法也可以用来计算用户的相似度，将用户u表示为一个向量$x_u\in R^{|I|}$xu​∈R∣I∣，其中|x_{ui}=r{ui}|为用户u对物品i的评分，0表示没有评分。则用户u和v的相似度为：
$CV(u,v) = cos(x_u,x_v)=\frac{\sum_{i\in I_{uv}}r_{ui}r_{vi}}{\sqrt{\sum_{i\in I_u}r_{ui}^2 \sum_{i\in I_v}r_{vj}^2}}$CV(u,v)=cos(xu​,xv​)=∑i∈Iu​​rui2​∑i∈Iv​​rvj2​​∑i∈Iuv​​rui​rvi​​
其中$I_{uv}$Iuv​表示同时被用户u和v评分的物品。这种方法存在一个问题：它没考虑到用户u和v的评分均值以及方差间的差异。
常用的可去除均值和方差差异影响的方法是皮尔逊相关系数
$PC(u,v)=\frac{\sum_{i\in I_{uv}}(r_{ui}-\overline{r}_u)(r_{vi}-\overline{r}_v)}{\sqrt{\sum_{i\in I{uv}}(r_{ui}-\overline{r}_u)^2 \sum_{i\in I_{uv}}(r_{vi} - \overline{r}_v)^2}}$PC(u,v)=∑i∈Iuv​(rui​−ru​)2∑i∈Iuv​​(rvi​−rv​)2​∑i∈Iuv​​(rui​−ru​)(rvi​−rv​)​
这种方法也同样可以拓展到计算物品i和j的相似度。

其他相似度计算方法

均方差（Mean Squared Difference, MSD）：使用用户u和v对相同物品评分差的平方总和均值的倒数表示两个人的相似度。
$MSD(u,v)=\frac{|I_{uv}|}{\sum_{i\in I_{uv}}(r_{ui}-r_{vi})^2}$MSD(u,v)=∑i∈Iuv​​(rui​−rvi​)2∣Iuv​∣​
斯皮尔曼等级关联(Spearman Rank Correlation, SRC)：综合考虑评分的排名。
$k_{ui}$kui​ : 物品i在用户u所评分物品中的排位
用户u和v的相似度通过下式计算。
$SRC(u,v)=\frac{\sum_{i\in I_{uv}}(k_{ui}-\overline{k}_u)(k_{vi}-\overline{k}_v)}{\sqrt{\sum_{i\in I_{uv}}(k_{ui}-\overline{k}_u)^2\sum_{i\in I_{uv}}(k_{vi}-\overline{k}_v)^2}}$SRC(u,v)=∑i∈Iuv​​(kui​−ku​)2∑i∈Iuv​​(kvi​−kv​)2​∑i∈Iuv​​(kui​−ku​)(kvi​−kv​)​
其中$\overline{k}_u$ku​是用户所评价物品的平均排名。

邻域的选择

邻域数量和选择邻域的规则对推荐质量会产生重要影响。选择邻域的方法可以分为两步：

1. 全局过滤保持最有可能的近邻
2. 预测时选择最合适的近邻

过滤预选近邻数

大型的推荐系统中，由于内存限制不太可能存储所有用户和物品的非零相似度。当然即使没有限制也是极大浪费，因为只有一小部分有重要影响的值对预测才是有效的。预选近邻数是一项基本步骤，可以减少存储相似度权重的数量，并且可以限制预测的近邻数目，使得基于邻域的推荐方法可行。有下列三种方法可选：

1. top-N过滤：列表中选择N个近邻和对应的相似度权重需要保留。N的选择需要谨慎，太大会让预测速度变慢并且需要大量内存来存储。太小会让覆盖度太低，使得一些物品永远无法被推荐。
2. 阈值过滤：保留所有相似度权重大于给定阈值$w_{min}$wmin​的近邻。虽然更加灵活，但选择阈值也比较困难。
3. 负值过滤：过滤负的权重值。通常负评分关联性比正关联可靠性要差，因为两个用户正相关说明他们属于同一个团体，但负相关无法显示团体之间的差异程度。
   当然这三种过滤方法并不是互斥的，可以根据需要结合在一起。