《推荐系统实践》读书笔记

第一章，好的推荐系统

评价推荐系统好坏的指标

1. 用户的满意度
2. 准确率和召回率
3. 覆盖率。覆盖率描述的是一个模型能够挖掘长尾数据的能力，一般定义为推荐商品的种类比上所有商品的类别，还可以用信息熵和基尼指数来定义。若覆盖率较低，则出现了马太效应，也就是说一个物品越流行，越容易被推荐，越被推荐，它的流行度就越高。
4. 多样性。多样性描述了推荐列表中物品两两之间的不相似性。推荐给用户u的商品列表R(u)的多样性定义为：
   $$\text{Diversity} = 1-\frac{\sum_{i,j \in R(u),i\neq j}s(i,j)}{\frac{1}{2}|R(u)|(|R(u) | - 1)},$$推荐系统的整体多样性定义为多有用户推荐列表多样性的平均。
5. 新颖性和惊喜性
6. 信任性
7. 实时性
8. 鲁棒性。一些商家可能为了推广自己的商品，利用推荐系统的漏洞，使得推荐系统推荐自家商品的概率变大，推荐系统应该能识别出这种行为。

第二章，利用用户行为数据

用户行为数据简介

用户的行为数据有显性反馈行为（主动打分）和隐性反馈行为（浏览商品留下的痕迹）

用户行为分析

用户活跃度和物品流行度的分布

研究发现，互联网中的数据，很多都呈现长尾数据分布，具体来说就是，热门商品的数量在所有商品数量中是少数的，活跃用户在所有用户中是少数的。
长尾数据分布:
$$f(x) = \alpha x^k,$$
两边同时取对数，画在坐标轴上接近线性。

用户活跃度和物品流行度的关系

一般新用户倾向于浏览热门的物品，因为他们对网站还不熟悉，只能点击首页的热门物品，而老用户会逐渐开始浏览冷门的物品。

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

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

1. 找到和目标用户兴趣相似的用户集合。
2. 找到这个集合中的用户喜欢的，且目标用户没有用过的物品推荐给目标用户。

N(u)和N(v)分别表示用户u和v有过正反馈的物品集合，用户兴趣相似度的计算：

1. Jaccard公式：$$w_{uv} = \frac{|N(u) \cap N(v) |}{|N(u) \cup N(v) |}$$
2. 余弦相似度：$$w_{uv} = \frac{|N(u) \cap N(v) |}{\sqrt{|N(u)| | N(v) |}}$$

此算法需要维护一个用户相似度矩阵W，为计算用户之间的相似度，首先需要建立物品—用户的倒排表，然后扫描每个物品中的用户，若两用户u，v同时出现在一个物品中，则两用户相似矩阵$W[u][v]+=1,W[v][u]+=1.$

得到用户之间的兴趣相似度后，UserCF算法会给用户推荐和他兴趣最相似的K个用户喜欢的物品。如下的公式度量了UserCF算法中用户u对物品i的感兴趣程度：
$$p(u,i) = \sum_{v\in S(u,K) \cap N(i)} w_{u,v}r_{vi}.$$
其中， S(u, K)包含和用户u兴趣最接近的K个用户，N(i)是对物品i有过行为的用户集合， $w_{uv}$是用户u和用户v的兴趣相似度，rvi代表用户v对物品i的兴趣，因为使用的是单一行为的隐反馈数据，所以所有的rvi=1。

实验结果分析

• 准确率和召回率：推荐系统的准确率和召回率并不和K成正比，K是选择多少相似用户
• 流行度： K越大UserCF推荐结果越热门
• 覆盖率： K越大，覆盖率越低

用户相似度计算的改进

上面用余弦计算用户相似度，这个公式有点粗糙，因为对于热门商品，很多人都可能购买，但并不能说明他们相似，相反，对于冷门物品如果他们都购买了，这个更能说明他们兴趣的相似性。因此，使用下式来计算用户兴趣相似度：
$$w_{uv} = \frac{\sum_{i\in N(u)\cap N(v)} \frac{1}{\log(1+| N(i) |)}}{\sqrt{|N(u)| | N(v) |}},$$ $\frac{1}{\log(1+| N(i) |}$惩罚了用户u和用户v共同兴趣列表中热门物品对他们相似度的影响。

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

基于用户的协同过滤算法在一些网站中得到了应用，但该算法有一些缺点。首先，随着网站的用户数目越来越大，计算用户兴趣相似度矩阵将越来越困难，其运算时间复杂度和空间复杂度的增长和用户数的增长近似于平方关系。其次，基于用户的协同过滤很难对推荐结果作出解释。

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

1. 计算物品之间的相似度。
2. 根据物品的相似度和用户的历史购买物品给用户生成推荐列表。

物品相似性度量公式：$$w_{ij} = \frac{|N(i) \cap N(j) |}{\sqrt{|N(i)| | N(j) |}},$$
$|N(i)|$是喜欢物品$i$的用户数。这里面蕴涵着一个假设，就是每个用户的兴趣都局限在某几个方面，因此如果两个物品属于一个用户的兴趣列表，那么这两个物品可能就属于有限的几个领域，而如果两个物品属于很多用户的兴趣列表，那么它们就可能属于同一个领域，因而有很大的相似度。

和UserCF算法类似，ItemCF算法需要维护一个物品相似性矩阵，用ItemCF算法计算物品相似度时也可以首先建立用户—物品倒排表（即对每个用户建立一个包含他喜欢的物品的列表），然后对于每个用户，将他物品列表中的物品两两在共现矩阵C中加1。

在得到物品之间的相似度后，ItemCF通过如下公式计算用户u对一个物品j的兴趣：
$$p_{uj} = \sum_{i\in N(u)\cap S(j,K)} w_{ji}r_{ui},$$
N(u)是用户喜欢的物品的集合， S(j,K)是和物品j最相似的K个物品的集合， wji是物品j和i的相似度， rui是用户u对物品i的兴趣。

物品相似度计算的改进

$$w_{ij} = \frac{\sum_{u\in N(i)\cap N(j)} \frac{1}{\log(1+| N(u) |)}}{\sqrt{|N(i)| | N(j) |}},$$

物品相似度归一化

Karypis在研究中发现如果将ItemCF的相似度矩阵按最大值归一化，可以提高推荐的准确率。假设物品相似度矩阵为$W$，那么可以用如下公式得到归一化之后的相似度矩阵$W’$：$$w_{ij}’ = \frac{w_{ij}}{\max_{j}w_{ij}},.$$
一般来说，热门的类其类内物品相似度一般比较大。如果不进行归一化，就会推荐比较热门的类里面的物品，而这些物品也是比较热门的。因此，推荐的覆盖率就比较低。

UserCF 和 ItemCF 的比较

1. UserCF给用户推荐那些和他有共同兴趣爱好的用户喜欢的物品，而ItemCF给用户推荐那些和他之前喜欢的物品类似的物品。从这个算法的原理可以看到，UserCF的推荐结果着重于反映和用户兴趣相似的小群体的热点，而ItemCF的推荐结果着重于维系用户的历史兴趣。换句话说，UserCF的推荐更社会化，反映了用户所在的小型兴趣群体中物品的热门程度，而ItemCF的推荐更加个性化，反映了用户自己的兴趣。
2. UserCF适合用于新闻推荐
3. ItemCF适用于图书、电子商务和电影网站

隐语义模型

隐语义模型的核心思想是通过隐含特征(latent factor)联系用户兴趣和物品。我们可以从另一个角度考虑如何给用户推荐商品，对于某个用户，首先得到他的兴趣分类，然后从分类中挑选他可能喜欢的物品。这个基于兴趣分类的方法需要解决3个问题：

1. 如何给物品进行分类？
2. 如何确定用户对哪些类的物品感兴趣，以及感兴趣的程度？
3. 对于一个给定的类，选择哪些属于这个类的物品推荐给用户，以及如何确定这些物品在一个类中的权重？

隐含语义分析技术采取基于用户行为统计的自动聚类，较好地解决了上面提出的几个问题。LFM通过如下公式计算用户u对物品i的兴趣：
$$\text{Preference(u,i)} = r_{ui} = p_u^Tq_i = \sum_{k=1}^K p_{uk}q_{ik},$$
$p_{uk} $度量了用户u的兴趣和第k个隐类的关系，$q_{ik}$度量了第k个隐类和物品i之间的关系。

负样本采样

原则：

1. 对每个用户，要保证正负样本的平衡（数目相似）。
2. 对每个用户采样负样本时，要选取那些很热门，而用户却没有行为的物品。一般认为，很热门而用户却没有行为更加代表用户对这个物品不感兴趣。因为对于冷门的物品，用户可能是压根没在网站中发现这个物品，所以谈不上是否感兴趣。

目标函数

$$\min_{p_u,q_i} \sum_{(u,i)\in K} \left(r_{ui} - \sum_{k=1}^K p_{uk}q_{ik}\right)^2 + \lambda (|p_u|^2+| q_i |^2),$$
其中，$K$为经过采样后得到的用户-物品集，第一项为拟合项，第二项为正则项。

LFM和基于邻域的方法的比较

UserCF和ItemCF都是基于邻域的方法，可从以下方面比较与LFM的异同。

1. 理论基础： LFM具有较好的理论基础，是一种机器学习方法，而基于邻域的方法是一种统计方法。
2. 离线计算的空间复杂度：基于领域的方法需要维护一张用户相关表或者物品相关表，需要较大的存储空间。
3. 离线计算的时间复杂度：差不多。
4. 在线实时推荐：一旦用户有了新的喜欢物品，ItemCF可以通过查询与此物品相关的其他商品推荐给用户，而LFM则需要计算用户对所有物品的兴趣权重，然后排名，返回权重最大的N个物品，在物品数很多时，这一过程的时间
   复杂度非常高。
5. 解释性： ItemCF有很好的解释性，LFM则没有。

第三章，推荐系统冷启动问题

冷启动问题简介

主要分为3类：

1. 用户冷启动
2. 物品冷启动
3. 系统冷启动

一般有如下解决方案：

1. 提供非个性化推荐，比如推荐排行榜
2. 利用用户注册时提供的年龄、性别等信息
3. 利用用户的社交网络账号
4. 要求用户注册时对一些物品进行反馈，收集用户对这些物品的兴趣
5. 物品冷启动,对新加入的物品可利用物品的内容信息，可能需要用到文本分析的技术
6. 系统冷启动，可引入专家知识

利用用户注册信息

基于用户注册信息的推荐算法其核心问题是计算每种特征的用户喜欢的物品。也就是说，对于每种特征$f$，计算具有这种特征的用户对各个物品的喜好程度$p(f, i)$。 $p(f,i)$ 可以简单地定义为物品$i$在具有f的特征的用户中的热门程度：
$$p(f,i) = | N(i) \cap U(f)|,$$其中$N(i)$是喜欢物品$i$的用户集合，$U(f)$是具有特征$f$的用户集合。在这种定义下，往往热门的物品会在各种特征的用户中都具有比较高的权重。因此，我们可以将 p(f,i)定义为喜欢物品$i$的用户中具有特征f的比例：
$$p(f,i) = \frac{| N(i) \cap U(f)|}{| N(i) | + \alpha},$$
参数$\alpha$的目的是解决数据稀疏问题。

选择合适的物品启动用户的兴趣

解决用户冷启动问题的另一个方法是在新用户第一次访问推荐系统时，不立即给用户展示推荐结果，而是给用户提供一些物品，让用户反馈他们对这些物品的兴趣，然后根据用户反馈给提供个性化推荐。

需要选择启动用户兴趣的物品应具有以下特征：

1. 比较热门的商品
2. 具有代表性和区分性
3. 启动物品集合需要有多样性

一般可以使用决策树算法构建一个这样的选择启动物品集合的系统。给定一群用户，用这群用户对物品评分的方差度量这群用户兴趣的一致程度。如果方差很大，说明这一群用户的兴趣不太一致，反之则说明这群用户的兴趣比较一致。通过如下方式度量一个物品的区分度$D(i):$
$$D(i) = \delta_{u \in N^+(i)} + \delta_{u \in N^-(i)}+\delta_{u \in \bar{N}(i)},$$三项分别还是喜欢、不喜欢、不知道商品i的用户对其他物品评分的方差。决策树算法首先会从所有用户中找到具有最高区分度的物品i，然后将用户分成3类。然后在每类用户中再找到最具区分度的物品，然后将每一类用户又各自分为3类，也就是将总用户分成9类，然后这样继续下去，最终可以通过对一系列物品的看法将用户进行分类。而在冷启动时，我们从根节点开始询问用户对该节点物品的看法，然后根据用户的选择将用户放到不同的分枝，直到进入最后的叶子节点，此时我们就已经对用户的兴趣有了比较清楚的了解，从而可以开始对用户进行比较准确地个性化推荐。

利用物品的内容信息

对于物品的冷启动呢问题，一般是利用物品的文本信息，计算物品的词向量，然后根据词向量计算物品的相似性，将其加入相似性矩阵。

发挥专家的作用

针对系统冷启动问题，一般使用专家进行样本标注。

第四章，利用用户标签数据

标签应用一般分为两种：一种是让作者或者专家给物品打标签；另一种是让普通用户给物品打标签，也就是UGC,书中用到的是UGC。当一个用户对一个物品打上一个标签，这个标签一方面描述了用户的兴趣，另一方面则表示了物品的语义，从而将用户和物品联系了起来。

标签系统中的推荐问题

两个：

1. 利用用户的标签为其推荐物品
2. 用户给物品打标签时，如何给用户推荐标签

用户为什么打标签

两个维度：社会维度，便于其他人找到信息；功能维度，方便自己将来查找。

用户打标签的分布

标签的流行度：用户在物品上打这个标签的次数。

标签的流行度分布也呈现非常典型的长尾分布。

用户打标签的类型

• 表明物品是什么
• 表明物品的种类
• 表明谁拥有物品
• 表达用户的观点
• 用户相关的标签
• 用户的任务

基于标签的推荐系统

$(u,i,b)$表示用户u给物品i打上标签b。

一个简单的基于标签的推荐算法：

1. 统计每个用户最常用的标签。
2. 对于每个标签，统计被打过这个标签次数最多的物品。
3. 对于一个用户，首先找到他常用的标签，然后找到具有这些标签的最热门物品推荐给这个用户。
   那么用户u对物品i的兴趣公式为：
   $$p(u,i) = \sum_b n_{u,b}n_{b,i}$$

算法的改进

上述的公式倾向于给热门标签对应的热门物品很大的权重，因此会造成推荐热门的物品给用户，从而降低推荐结果的新颖性。并且，给热门标签过大的权重，从而不能反应用户个性化的兴趣。书中借鉴了TF-IDF的思想，将公式改进为
$$p(u,i) = \sum_b \frac{n_{u,b}}{\log(1+n_b^{u})}n_{b,i},$$
$n_b^{u}$为标签b被多少不同的用户使用过。同时，也可以对热门物品进行惩罚：
$$p(u,i) = \sum_b \frac{n_{u,b}}{\log(1+n_b^{u})}\frac{n_{b,i}}{\log(1+n_i^u)}$$

数据稀疏性

对于新用户或者新物品$B(u)\cap B(i)$中的标签会很少，为了提高推荐的准确率，我们可能要对标签集合做扩展，比如若用户曾经用过“推荐系统”这个标签，我们可以将这个标签的相似标签也加入到用户标签集合中，比如“个性化”、“协同过滤”等标签。标签扩展的本质是对每个标签找到和它相似的标签，也就是计算标签之间的相似度。

标签清理

不是所有的标签都能反应用户的兴趣，要将这一部分标签清理掉。

给用户推荐标签

1. 给用户u推荐物品i上最热门的标签
2. 给用户u推荐他自己经常使用的标签
3. 融合前两种方法，该方法通过一个系数将上面的推荐结果线性加权，然后生成最终的推荐结果。

第五章，利用上下文信息

时间上下文信息

时间效应简介

1. 用户兴趣随时间是变化的
2. 物品有生命周期
3. 季节效应

时间上下文相关的ItemCF算法

ItemCF由两部分构成：计算物品间的相似性，利用用户历史行为和物品相似性给用户推荐商品，加入时间上下文信息后，可以对这两部分做出改进。
加入时间信息后的物品相似性度量：
$$\text{sim}(i,j) = \frac{\sum_{u \in N(j) \cap N(i)}f\left( | t_{ui} - t_{uj}|\right)}{\sqrt{|N(i)| |N(j)|}}$$
其中f为衰减函数：
$$f\left( | t_{ui} - t_{uj}|\right) = \frac{1}{1+\alpha |t_{ui} - t_{uj}|},$$$\alpha$是时间衰减参数，它的取值在不同系统中不同。相应的，用户u对物品i的兴趣为
$$p(u,i) = \sum_{j \in N(u)\cap S(i,K)} \frac{\text{sim}(i,j)}{1+\beta |t_0 - t_{uj}|}$$

时间上下文的UserCF算法

与时间上下文的ITemCF算法类似，UserCF算法需要改进的也有两方面：用户相似性度量的计算改进和用户对物品兴趣计算的改进。
用户相似性度量：
$$w_{uv}\frac{\sum_{i \in N(u) \cap N(v)}\frac{1}{1+\alpha |t_{ui} - t_{vi}|}}{\sqrt{|N(u)| |N(v)|}},$$
上面公式的分子对于用户u和用户v共同喜欢的物品i增加了一个时间衰减因子。用户u和用户v对物品i产生行为的时间越远，那么这两个用户的兴趣相似度就会越小。
用户对物品的兴趣：
$$p(u,i) = \sum_{v \in S(u,K)} w_{uv}r_{vi}$$
或者
$$p(u,i) = \sum_{v \in S(u,K)} w_{uv}r_{vi} \frac{1}{1+\alpha (t_0 - t_{vi})}$$