目录

• 第一章 好的推荐系统
  • 1.什么是好的推荐系统
  • 2.推荐系统实验方法
  • 3.评测指标
• 第二章利用用户行为数据
  • 1.用户行为分析
  • 2.基于邻域的算法
    • 基于用户的协同过滤算法
    • 用户相似度计算的改进
    • 基于物品的协同过滤算法
    • 用户活跃度对物品相似度的影响
    • 物品相似度的归一化
    • UserCF和ItemCF的综合比较
    • 隐语义模型
    • 基于LFM的实际系统的例子
    • LFM和基于领域的方法的比较
  • 3.基于图的模型
    • 用户行为数据的二分图表示
    • 基于图的推荐算法

第一章 好的推荐系统

1.什么是好的推荐系统

好的推荐系统能使用户、物品提供者和提供推荐系统的平台三方达到共赢。

2.推荐系统实验方法

在推荐系统中，主要有3种评测推荐效果的实验方法，即离线实验（offline experiment）、用户调（user study）和在线实验（online experiment）。

• 离线实验
  (1) 通过日志系统获得用户行为数据，并按照一定格式生成一个标准的数据集；
  (2) 将数据集按照一定的规则分成训练集和测试集；
  (3) 在训练集上训练用户兴趣模型，在测试集上进行预测；
  

• 用户调查

• 在线实验
  下图是一个简单的AB测试系统。用户进入网站后，流量分配系统决定用户是否需要被进
  行AB测试，如果需要的话，流量分配系统会给用户打上在测试中属于什么分组的标签。然后用
  户浏览网页，而用户在浏览网页时的行为都会被通过日志系统发回后台的日志数据库。此时，如
  果用户有测试分组的标签，那么该标签也会被发回后台数据库。在后台，实验人员的工作首先是
  配置流量分配系统，决定满足什么条件的用户参加什么样的测试。其次，实验人员需要统计日志
  数据库中的数据，通过评测系统生成不同分组用户的实验报告，并比较和评测实验结果。
  
  一般来说，一个新的推荐算法最终上线，需要完成上面所说的3个实验。
  1)首先，需要通过离线实验证明它在很多离线指标上优于现有的算法。
  2)然后，需要通过用户调查确定它的用户满意度不低于现有的算法。
  3)最后，通过在线的AB测试确定它在我们关心的指标上优于现有的算法。

3.评测指标

1)用户满意度
2)预测准确度

• 评分预测
  
• TopN推荐
  
• 覆盖率
  覆盖率（coverage）描述一个推荐系统对物品长尾的发掘能力。覆盖率有不同的定义方法，最简单的定义为推荐系统能够推荐出来的物品占总物品集合的比例。假设系统的用户集合为U，推荐系统给每个用户推荐一个长度为N的物品列表R(u)
  
  覆盖率是一个内容提供商会关心的指标，上面的定义过于粗略。覆盖率为100%的系统可以有无数的物品流行度分布。为了更细致地描述推荐系统发掘长尾的能力，需要统计推荐列表中不同物品出现次数的分布。如果所有的物品都出现在推荐列表中，且出现的次数差不多，那么推荐系统发掘长尾的能力就很好。
  
• 多样性
  
  
• 新颖度
• 惊喜度
• 信任度
• 实时性
  （1）推荐系统需要实时地更新推荐列表来满足用户新的行为变化。
  （2）推荐系统需要能够将新加入系统的物品推荐给用户。
• 健壮性

#第二章利用用户行为数据
基于用户行为分析的推荐算法是个性化推荐系统的重要算法，学术界一般将这种类型的算法
称为协同过滤算法。

用户行为在个性化推荐系统中一般分两种——显性反馈行为（explicit feedback）和隐性反馈
行为（implicit feedback）。显性反馈行为包括用户明确表示对物品喜好的行为。隐性反馈行为指的是那些不能明确反应用户喜好的行为。最具代表性的隐性反馈行为就是页面浏览行为。

1.用户行为分析

很多关于互联网数据的研究发现，互联网上的很多数据分布都满足一种称为Power Law的分布，这个分布在互联网领域也称长尾分布。

$f(x)=ax^k$

（1）不管是物品的流行度还是用户的活跃度，都近似于长尾分布。
（2）用户越活跃，越倾向于浏览冷门的物品

2.基于邻域的算法

基于用户的协同过滤算法

基于用户的协同过滤算法主要包括两个步骤。
(1) 找到和目标用户兴趣相似的用户集合。

直接对两两用户都利用余弦相似度计算相似度算法时间复杂度较大，用户数很大时非常耗时。
改进1:

思路：我们可以首先计算出 $\mid N(u) \bigcap N(v)\mid \not=0$ 的用户对(u,v)，然后再对这种情况除以分母$\sqrt{\mid N(u) \bigcap N(v) \mid}$。
具体实现：
为此，可以首先建立物品到用户的倒排表，对于每个物品都保存对该物品产生过行为的用户
列表。令稀疏矩阵$C[u][v]=\mid N(u)\bigcap N(v)\mid$。那么，假设用户u和用户v同时属于倒排表中K个物品对应的用户列表，就有$C[u][v]=K$。从而，可以扫描倒排表中每个物品对应的用户列表，将用户列
表中的两两用户对应的$C[u][v]$加1，最终就可以得到所有用户之间不为0的$C[u][v]$。
倒排表的生成（物品:a,b,c,d 用户:A,B,C,D）

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

用户相似度计算的改进

基于物品的协同过滤算法

需求：随着网站的用户数目越来越大，计算用户兴趣相似度矩阵将越来越困难，其运算时间复杂度和空
间复杂度的增长和用户数的增长近似于平方关系。
基于物品的协同过滤算法主要分为两步。
(1) 计算物品之间的相似度。

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

用户活跃度对物品相似度的影响

物品相似度的归一化

将ItemCF的相似度矩阵按最大值归一化，好处不仅仅在于增加推荐的准确度，它还可以提高推荐的覆盖率和多样性。

UserCF和ItemCF的综合比较

• 哈利波特问题
  

隐语义模型

UserCF：首先需要找到和他们看了同样书的其他用户（兴趣相似的用户），然后给他
们推荐那些用户喜欢的其他书。
ItemCF：需要给他们推荐和他们已经看的书相似的书，比如作者B看了很多关于数据
挖掘的书，可以给他推荐机器学习或者模式识别方面的书。
新的算法思路：可以对书和物品的兴趣进行分类。对于某个用户，首先得到他的兴趣分类，
然后从分类中挑选他可能喜欢的物品。隐含语义分析技术，因为采取基于用户行为统计的自动聚类，较好的满足了新的算法思路所带来的问题。

如何解决隐性反馈数据集上应用LFM解决TopN推荐的没有负样本这个问题：
1.对于一个用户，从他没有过行为的物品中均匀采样出一些物品作为负样本。

1. 对于一个用户，从他没有过行为的物品中采样出一些物品作为负样本，但采样时，保证
   每个用户的正负样本数目相当。
   3.对于一个用户，从他没有过行为的物品中采样出一些物品作为负样本，但采样时，偏重
   采样不热门的物品。
   通过2011年的KDD Cup的Yahoo! Music推荐系统比赛的采样方案
   1.对每个用户，要保证正负样本的平衡（数目相似）。
   2.对每个用户采样负样本时，要选取那些很热门，而用户却没有行为的物品。

基于LFM的实际系统的例子

遇到的困难：经典的LFM模型每次训练时都需要扫描所有的用户行为记录，这样才能计算出用户隐类向量$(p_u)$和物品隐类向量$(q_i)$。LFM的每次训练都很耗时，一般在实际应用中只能每天训练一次，并且计算出所有用户的推荐结果。从而LFM模型不能因为用户行为的变化实时地调整推荐结果来满足用户最近的行为。在新闻推荐中，冷启动问题非常明显。每天都会有大量新的新闻。这些新闻会在很短的时间内获得很多人的关注，但也会在很短的时间内失去用户的关注。因此，它们的生命周期很短，而推荐算法需要在它们短暂的生命周期内就将其推荐给对它们感兴趣的用户。
解决方法：

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

1)理论基础：LFM具有比较好的理论基础，它是一种学习方法，通过优化一个设定的指标建立最优的模型。基于邻域的方法更多的是一种基于统计的方法，并没有学习过程。
2)离线计算的空间复杂度：基于邻域的方法需要维护一张离线的相关表。在离线计算相关表的过程中，如果用户/物品数很多，将会占据很大的内存。LFM只需占用很少的内存。
3)离线计算的时间复杂度：总体上来说两者没有太大差别。
4)在线实时推荐：UserCF和ItemCF在线服务算法需要将相关表缓存在内存中，然后可以在线进行实时的预测。LFM在给用户生成推荐列表时，需要计算用户对所有物品的兴趣权重，然后排名，返回权重最大的N个物品。那么，在物品数很多时，这一过程的时间复杂度非常高，LFM不太适合用于物品数非常庞大的系统，也不能实时计算。
5)推荐解释：ItemCF算法支持很好的推荐解释，它可以利用用户的历史行为解释推荐结果。但LFM无法提供这样的解释。

基于图的模型

1.用户行为数据的二分图表示

基于图的模型（graph-based model）是推荐系统中的重要内容。用户行为数据是由一系列二元组组成的，其中每个二元组(u, i)表示用户u对物品i产生过行为。这种数据集很容易用一个二分图表示。(用户节点A,B,C和物品节点a、b、c,d)

2.基于图的推荐算法

基于上一步，下面的任务就是在二分图上给用户进行个性化推荐。那么给用户u推荐物品的任务就可以转化为度量用户顶点$v_u$和与$v_u$没有边直接相连的物品节点在图上的相关性，相关性越高的物品在推荐列表中的权重就越高。