正文

3. 通用推荐模型

3.1. 协同过滤推荐

3.1.1. 基于邻域的模型 UserCF & ItemCF

基于邻域的算法分为两大类，一类是基于用户的协同过滤算法，另一类是基于物品的协同过滤算法。

（1）基于用户的协同过滤算法 UserCF

在一个在线个性化推荐系统中，当一个用户A需要个性化推荐时，可以先找到和A有相似兴趣的其他用户，然后把那些用户喜欢的、而用户A没有关注过的物品推荐给A。这种方法称为基于用户的协同过滤算法（UserCF）。

基于用户的协同过滤算法主要包括两个步骤：

找到和目标用户兴趣相似的用户集合

找到这个集合中的用户喜欢的，且目标用户没有听说过的物品，推荐给目标用户

算法的关键是计算两个用户的兴趣相似度。协同过滤算法主要利用用户兴趣列表的相似度计算用户兴趣的相似度，给定用户 u uu、v vv，令 N ( u ) N(u)N(u) 表示用户 u uu 曾经有过兴趣的物品集合，N ( v ) N(v)N(v) 表示用户 v vv 曾经有过兴趣的物品集合。

计算用户兴趣相似度的方法有3种：

Jaccard公式

余弦相似性

改进的余弦相似性

其中 降低了用户u uu和用户v vv的共同兴趣列表中热门物品对用户相似度的影响

得到了用户之间的兴趣相似度之后，就要将用户兴趣列表转换为“物品-用户”倒排表，即对每个物品建立一个喜欢它的用户的列表，以此来给用户推荐与他兴趣最相似的K KK个用户喜欢的物品。如下的公式度量了UserCF算法中用户u uu对物品i ii的感兴趣程度：

其中S ( u , K ) S(u,K)S(u,K)包含和用户u uu兴趣最接近的K KK个用户，N ( i ) N(i)N(i)是对物品i ii有过行为的用户集合，w u  是用户u uu和用户v vv的兴趣相似度，r v i 代表用户v vv对物品i ii的兴趣。一般情况下，如果使用的是单一行为的隐反馈数据，那所有的r v i = 1

例如用户A AA、B BB、C CC、D DD和物品a aa、b bb、c cc、d dd、e ee有如下用户兴趣列表：

用余弦相似度计算用户兴趣相似度：

通过比较我们可以知道用户A AA与用户D DD的兴趣相似度最高，用户B BB、C CC次之。若我们设K = 1 K=1K=1则意味着从相似度最高的用户D DD的兴趣列表中选取物品推荐给用户A AA；若设K = 2 K=2K=2，则从用户B D BDBD或C D CDCD的兴趣列表中选择；若设K = 3 K=3K=3则从全部用户B C D BCDBCD的兴趣列表中选择物品推荐给用户A AA。

这里我们设K = 3 K=3K=3，此时我们需要计算用户A AA与用户B C D BCDBCD兴趣列表中的物品（即，a aa、b bb、c cc、d dd、e ee）的感兴趣程度。首先建立“物品-用户”倒排表：

从倒排表我们可以轻松地找到不同物品关联的喜欢该物品的用户，这时我们就可以利用用户A AA对其他用户的相似度来衡量用户A对这些物品的感兴趣程度了：

根据计算结果，我们可以知道用户 A AA 对物品 c cc、e ee 的兴趣一致，因此我们可以任意推荐他们其中一个，或者一起推荐给用户 A AA。需要注意的是我们没有计算 p ( A , a ) p(A,a)p(A,a)、p ( A , b ) p(A,b)p(A,b)、p ( A , d ) p(A,d)p(A,d)，这是因为物品 a aa、b bb、d dd 已经在用户 A AA 的兴趣列表中了，所以没必要再推荐。

（2）基于物品的协同过滤算法 ItemCF

基于物品的协同过滤算法用于给用户推荐那些与他们之前喜欢的物品相似的物品。

ItemCF算法主要通过分析用户的行为记录来计算物品之间的相似度。该算法认为，物品A和物品B具有很大的相似度是因为喜欢物品A的用户大都也喜欢物品B。

基于物品的协同过滤算法主要分为两步：

计算物品之间的相似度；

根据物品的相似度和用户的历史行为给用户生成推荐列表。

我们给定物品i ii、j jj，设N ( i ) N(i)N(i)为喜欢物品i ii的用户数，N ( j ) N(j)N(j)为喜欢物品j jj的用户数，则物品i ii、j jj的相似度可以表达为：

Jaccard公式

w i j = ∣ N ( i ) ∩ N ( j ) ∣ ∣ N ( i ) ∣ w_{ij}=\frac{|N(i)\cap N(j)|}{|N(i)|}

上述公式可以理解为喜欢物品 i ii 的用户中有多少比例的用户也喜欢物品 j jj

余弦相似性

• 该公式降低了热门物品会和很多物品相似的可能性，可以避免推荐出热门的物品。
• 改进的余弦相似性

其中 对余弦相似性进行了修正，使得活跃用户对物品相似度的贡献大于不活跃的用户。

提一句，如果将ItemCF的相似度矩阵 w ww 按最大值归一化，可以提高推荐的准确率，归一化公式如下：

在ItemCF中，两个物品之所以产生相似度是因为它们共同被很多用户喜欢，即每个用户都可以通过他们的历史兴趣列表给物品“贡献”相似度。也就是说，在得到物品之间的相似度后，我们可以建立一个“用户-物品”倒排表，即对每个用户建立一个包含他喜欢的物品的列表。

然后通过如下公式计算用户u uu对一个物品j jj的兴趣度：

这里N ( u ) N(u)N(u)是用户喜欢的物品的集合，S ( j , K ) S(j,K)S(j,K)是和物品j jj最相似的K KK个物品的集合，w j是物品j jj和i ii的相似度，r u i是用户u uu对物品i的兴趣（如果用户u uu对物品i ii有过行为，即可令r u i = 1 。该公式的含义是，与用户历史上感兴趣的物品越相似的物品，越有可能是用户感兴趣的物品。

ItemCF的推荐过程可以用如下例子来表示：

假设已知用户对两个物品A 1  的兴趣度分别为1.3、0.9，现有5个用户未曾见过的新物品，它们与物品A 1 的相似度可以表示为：

可得，用户对B 1 、B 2 B 3 、B 4 B_4、B 5 的兴趣度分别为

由此我们可知，用户可能对物品B 2 的兴趣度最高，应该向用户推荐物品B 2

（3）UserCF 与 ItemCF 的区别

关于协同过滤算法（CF）的推荐效果，我们从流行度的角度来考虑。在movie-lens-1m数据集上，ICF的推荐效果更加分散，UCF的推荐效果更加集中，也就是ICF的平均流行度会低于UCF。

ICF

下面两个图分别是(左)项目流行度与项目平均排名（Top-K）的关系；(右)项目流行度与其排名前50（Top-K）的概率。

UCF

下面两个图分别是(左)项目流行度与项目平均排名（Top-K）的关系；(右)项目流行度与其排名前50（Top-K）的概率。

3.1.2. 隐语义模型 MF

LFM（Latent Factor Model）隐语义模型的核心思想是通过隐含特征(Latent Factor)联系用户兴趣和物品，它采取基于用户行为统计的自动聚类，让用户和物品的分类自动化。

LFM通过如下公式计算用户u uu对物品i的兴趣：

其中 , p u , k p_{u,k}p

u,k

度量了用户u uu的兴趣和第k kk个隐类的关系，而q i , k q_{i,k}q

i,k

度量了物品i ii和第k kk个隐类之间的关系。

推荐系统的用户行为样本分为正样本（用户喜欢什么物品）和负样本（用户对什么物品不感兴趣）。经过对正负样本的采样，可以得到一个用户—物品集K = { ( u , i ) } K=\{(u,i)\}K={(u,i)}，其中如果( u , i ) (u,i)(u,i)是正样本，则有r u i = 1 ，否则r u i = 0 ，然后，通过随机梯度下降法优化如下的损失函数来找到最合适的参数 p p和 q ：

随机梯度下降法需要首先对参数 p u , k p_{u,k}p u,k和 q i , k q_{i,k}q i,k

 分别求偏导数

然后这两个参数沿着方向导数前进，得到如下递推公式：

其中，α \alphaα指学习速率（Learning Rate），是一个可调参数。

矩阵分解算法(Matrix Factorization, MF)就是LFM的一种，现实中我们得到的是残缺的评分矩阵，可以通过分解评分矩阵，学习得到用户和物品的隐向量，也就是上面的用户矩阵p u p_up u 和物品矩阵q i q_iq i

LFM和基于邻域的方法区别大致如下：

3.1.3. 基于图的模型

用户对物品的行为很容易用二分图表示，已知用户行为数据是由一系列二元组组成的，其中每个二元组( u , i ) (u, i)(u,i)表示用户u uu对物品i ii产生过行为，这样的数据可以用二分图G ( V , E ) G(V,E)G(V,E)表示，其中 V = V U ∪ V I V=V_U\cup V_IV=V

U ∪VI由用户顶点集合V U V_UV U和物品顶点集合V I V_IV I

组成。

对于数据集中的每一个二元组( u , i ) (u,i)(u,i)，都有一套对应的边e ( v u , v i)e(v_u,v_i)e(v u ,v i )，其中v u ∈ V U v_u\in V_Uv u ∈V U 是用户u uu对应的顶点，v i ∈ V I v_i\in V_Iv i ∈V I是物品i ii对应的顶点，如下表和图所示：

表示为二分图：

可以看到在上图中，圆形结点为一个分割，矩形结点为另一个分割。

要将个性化推荐算法放到二分图模型上，那么给用户u uu推荐物品的任务就可以转化为度量用户顶点v u  与v u v_没有边直接相连的物品节点在图上的相关性，相关性越高的物品在推荐列表中的权重就越高。

相关性高的一对顶点，一般具有以下特征：

两个顶点之间有很多路径相连；

链接两个顶点之间的路径长度都比较短；

链接两个顶点之间的路径不会经过出度比较大的顶点。

基于上面3个主要因素，研究人员设计了很多计算图中顶点之间相关性的方法，这里讲解基于随机游走的PageRank和PersonalRank算法。

（1）PageRank算法

PageRank是用来衡量特定网页相对于搜索引擎中其他网页的重要性的算法，其计算结果作为Google搜索结果中网页排名的重要指标。

网页之间通过超链接相互连接，互联网上不计其数的网页就构成了一张超大的图。PageRank假设用户从所有网页中随机选择一个网页进行浏览，然后通过超链接在网页直接不断跳转。到达每个网页后，用户有两种选择：到此结束或者继续选择一个链接浏览。

设用户继续浏览的概率为α \alphaα，用户以相等的概率在当前页面的所有超链接中随机选择一个继续浏览。当经过很多次这样的随机游走之后，每个网页被访问用户访问到的概率就会收敛到一个稳定值。

算法迭代关系式如下所示：

其中P R ( v ) PR(v)PR(v)是网页v vv被访问的概率（也就是重要性程度），α \alphaα是用户继续访问网页的概率，N NN是网页总数。i n ( v ) in(v)in(v)表示指向网页v vv的网页集合（入度），o u t ( v ′ ) out(v')out(v  )表示网页v ′ v'v  指向的网页集合（出度）。

将网页替换为其他物品同理。

（2）PersonalRank算法

PersonalRank跟PageRank的区别只在于每一步概率的取值不一样，PersonalRank用r vr_vr v 替换了1 / N 1/N1/N，也就是说PersonalRank走到任意的下一个节点的概率服从均分布。公式表达为：

其中 ，v u v_uv u 是指用户u uu对应的节点

为了PersonalRank的时间复杂度，可以从矩阵论出发重新设计算法。

令M MM为用户物品二分图的转移概率矩阵，即：

那么，迭代公式可以转化为：

用PersonalRank算法对上面的示例中的用户A AA进行推荐，可得如下结果：

用户 A AA 和物品 c cc、e ee 没有边相连，但是用户 A AA 和物品 c cc 有三条长度为 3 33 的路径相连，用户 A AA 和物品 e ee 有两条长度为 3 33 的路径相连。那么，顶点 A AA 与 e ee 之间的相关性就要高于顶点 A AA 与 c cc，因而物品 e ee 在用户 A AA 的推荐列表中应该排在物品 c cc 之前。最终得出的推荐列表为{ c , e } \{c,e\}{c,e}

用户A AA与物品c cc的路径：

用户A AA与物品e ee的路径：