推荐系统（二）——用户行为数据

推荐系统(1)-概述

为了使推荐结果符合用户口味，我们需要对用户有深入的了解。用户留下的文字和行为可以解释。

2. 基于用户行为数据的最典型应用是各种列表。这些列表是基于简单的用户行为统计数据，个性化的推荐算法是通过深入分析用户行为来带来更好的体验。

3. 用户行为不是随机的，包含了许多模式。例如，通过对用户购物车的分析，电子商务平台发现了 购买A用户购买商品B同时，在用户浏览商品的同时A商品直接展示购买A 用户购买的其他商品最著名的例子是啤酒和尿布的故事。

当当网在用户浏览《数据挖掘导论》时，向用户推荐购买本产品的客户 还买了的书

4. 基于用户行为分析的推荐算法称为协同过滤算法。顾名思义，协同过滤是指用户可以通过不断与网站互动，不断过滤自己不感兴趣的物品，从而越来越满足自己的需求。

5. 网站上用户行为数据最简单的存在形式是日志。网站在运行过程中产生了大量的原始日志 (raw log)，并将其存储在文件系统中。许多互联网业务根据用户行为将各种原始日志汇总成会话日志(session log)，每次会话都表示用户行为和相应的服务。这些日志记录了用户的各种行为。

6. 个性化推荐系统中的用户行为一般分为两种-显性反馈行为(explicit feedback)和隐性反馈 行为(implicit feedback)。显性反馈包括用户明确表达对项目偏好的行为。

提供给用户打分或赞/踩的功能，收集用户喜好

7. 一个有趣的例子：YouTube最早是用5分评分系统 收集显性反馈的，但后来他们的研究人员统计了不同评分的评分数1，结果发现，用户最常用的评分是5分，其次是1分，其他的分数很少有用户打。YouTube用户主要关注视频，所以他们只有在特别不满意或特别满意时才会得分，所以二级评分系统就足够了。但如果它是一个评论网站，用户主要关注评论，那么多级评分系统是必要的。

8. 与显性反馈相对应的是隐性反馈。隐性反馈是指无法明确反映用户偏好的行为。最具代表性的隐性反馈行为是页面浏览行为。

网站显性反馈数据和隐性反馈数据的例子

互联网上有许多用户行为，如浏览网页、购买商品、评论、评分等。很难用一种统一的 来表达所有这些行为。下表给出了一种表达方式，将用户行为表达为六部分，即用户和行为对象、行为类型、上下文、内容和权重。

统一表达用户行为

9. 一般来说，不同的数据集包含不同的行为：

无上下文信息的隐性反馈数据集 每个行为记录仅包括用户ID和物品ID。显性反馈数据集 每个记录包含用户ID、物品ID以及用户对项目的评分。每个记录都包括用户对上下文信息的隐藏反馈数据集 ID、物品ID时间戳用户对物品的行为。上下文信息的显性反馈数据集 ID、物品ID、用户对物品进行评分和评分的时间戳。

10. 用户活动和商品流行的分布

互联网上的许多数据分布都被称为Power Law在互联网领域，这种分布也被称为长尾分布。

横坐标是物品的流行程度K，纵坐标很受欢迎K的物品的总数。

11. 用户活动与商品流行的关系

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

图中曲线呈明显下降趋势，表明用户越活跃，越倾向于浏览不受欢迎的物品。

12. 基于用户行为数据设计的推荐算法通常被称为协同过滤算法。学术界深入研究了协同过滤算法 ，并提出了许多方法，如基于邻域的方法(neighborhood-based)、隐语义模型 (latent factor model)、基于图的随机游走算法(random walk on graph)等等。在这些方法中，最著名、最广泛应用于行业的算法是基于邻域的方法。

13. 推荐算法评价指标：

对用户u推荐N物品(记为R(u))，令用户u在测试集上喜欢的物品 ** 为T(u)，然后通过 过准确率/召回率来评估推荐算法的精度:

   召回率：

精度：

覆盖率: (覆盖率反映了发掘长尾的能力。覆盖率越高，推荐算法越能向用户推荐长尾项目。

例:一个数据库有500个文档，其中50个符合定义。系统检索到75个文档，但实际上只有45个符合定义。在500个文档中，系统可以检索到460个文档。

召回率：Recall = 45/50 = 90%

精度：Precision = 45/75 = 60%

覆盖率：Coverage = 460 / 500 = 92%

14. 基于邻域的方法主要包括两种算法：

基于用户的协同过滤算法 向用户推荐其他用户喜欢的物品，这些物品与他的兴趣相似。基于项目的协同过滤算法 向用户推荐类似于他以前喜欢的项目的项目。

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

当一个用户A当你需要个性化的推荐时，你可以首先找到其他与他有类似兴趣的用户，然后找到用户喜欢的用户A推荐没听说过的物品A。

协同过滤算法主要包括两个步骤：①找到与目标用户兴趣相似的用户 ** 。②找到这个 ** 用户喜欢的，目标用户没听说过的推荐给目标用户。

给定用户u和用户v，令N(u)表示用户u曾经有过正反馈的物品 ** ，令N(v) 为用户v曾经有过正反馈的物品 ** 。

通过Jaccard简单计算公式u和v兴趣相似性：

或计算余弦相似度：

案例：

例如用户行为记录

用户A和用户B的相似度为：

用户A和用户C相似度如下：

用户A和用户D相似度如下：

可见，用户A和用户D相似度最高。使用上述算法可以给用户A推荐A对物品c、e没有行为，所以你可以向用户推荐这两个项目A。

在获得用户之间的兴趣相似性后，UserCF算 ** 向用户推荐最类似他兴趣的产品K 用户喜欢的物品。测量了以下公式UserCF算法中用户u对物品i感兴趣：

   

其中，S(u,K)包含和用户u最接近兴趣的K个用户，N(i)是对物品i有过行为的用户 ** ， 是用户u和用户v 代表用户的兴趣相似性v对物品i的兴趣，因为使用的是单一行为的隐反馈数 据，所以所有的 = 1。

选取K=3，用户A对物品c、e没有行为，所以你可以向用户推荐这两个项目A。根据UserCF算法，用户A对物品c、e兴趣是：

p(A,c) = = 0.7416

p(A,e) = = 0.7416

注意，参数K是UserCF其调整对推荐算法的各种指标都有一定的影响。

以MovieLens可以看出，推荐系统的精度指标(精度和召回率)与参数不符K成线性关系MovieLens数据集中，选择K=80精度和召回率都比较高。因此，选择合适的K对于获得高推荐系统的精度更为重要。人气 K越大则UserCF推荐结果越受欢迎。这是因为K决定了UserCF在向您推荐时，请参考其他与您感兴趣相似的用户的兴趣。K越大，参考 的人越多，结果就越接近全球的热门物品。在三个数据集中，可以看到覆盖率 K越大则UserCF推荐结果的覆盖率越低。由于流行程度的增加，覆盖率的降低，UserCF越来越倾向于推荐热门物品，从而对长尾物品的推荐越来越少，导致覆盖率下降。

16. 用户相似度计算的改进

首先，以图书为例。如果两个用户都购买了新华字典，这并不意味着他们有相似的兴趣，因为绝大多数中国人小时候都购买了新华字典。但是，如果两个用户都购买了数据挖掘导论， 可以认为他们的兴趣相似，因为只有研究数据挖掘的人才会购买这本书。换句话说，两个用户对不受欢迎的物品采取了相同的行为，这表明了他们兴趣的相似性。

因此，John S. Breese在论文1中提出 以下公式（UserCF-IIF），用户兴趣相似性按用户行为计算：

UserCF和UserCF-IIF各种性能对比

UserCF-IIF在各项性能上略优于UserCF。这表明，在计算用户兴趣相似性时，考虑 商品的流行程度确实有助于提高推荐结果的质量。

基于用户协同过滤算法的缺点：① 随着网站用户数量的增加，计算用户兴趣相似性矩阵将变得越来越困难，其计算时间复杂性和空间复杂性的增加与用户数量的增加相似。② 基于用户的协同过滤很难解释推荐结果。

17. 基于物体的协同过滤算法（ItemCF）

基于对象的协同过滤(item-based collaborative filtering)算法是目前业界应用最广泛的算法。无论是亚马逊，还是亚马逊，Netflix、Hulu、YouTube，其推荐算法的基础都是该算法。基于对象的协同过滤算法可以利用用户的历史行为给推荐结果提供推荐解释，Hulu推荐使用个性化视频 ItemCF为每个推荐结果提供推荐解释，用于解释的视频是用户之前观看或收集的视频。

Hulu个性化视频推荐

协同过滤算法主要分为两个步骤：①计算物体之间的相似性。②根据物品的相似性和用户的历史行为，向用户生成推荐列表。

用以下公式定义项目的相似性：

分母|N(i)|是喜欢物品i而分子 N(i) N(j) 同时喜欢物品i和物品j用户数。因此，上述公式可以理解为喜欢的物品i有多少用户也喜欢商品？j。

虽然上面的公式看起来很有道理，但是有一个问题。假如物品j很受欢迎，很多人喜欢，所以 会很大，接近1。因此，该公式将导致任何项目与流行项目非常相似，这显然不是致力于挖掘长尾信息的推荐系统的好特点。

为避免推荐流行物品，可使用以下公式：

该公式惩罚了物品j因此，它减轻了流行物品与许多物品相似的可能性。在协同过滤中，这两个项目之所以相似，是因为它们共同受到许多用户的喜爱，也就是说，每个用户都可以通过他们的历史兴趣列表贡献项目的相似性。

下图最左边是输入用户行为记录，每行代表用户感兴趣的物品 ** 。然后，对于每一件物品 ** ，我们把里面的物体加成两两加一，得到一个矩阵。最后，将这些矩阵加到上面C矩阵。其中C[i][j]记录同时喜欢的物品i 和物品j用户数将C矩阵归一化可以获得物体之间的余弦相似度矩阵W。

   获得物品之间的相似性后，ItemCF用户通过以下公式计算u对一个物品j的兴趣:

这里N(u) 是用户喜欢的物品** ，S(j,K)是和物品j最相似的K个物品的 ** ， 是物品j和i 相似性， 是用户u对物品i对隐反馈数据集的兴趣u对物品i有过行为，就可以下令了=1。)该公式的含义是，与用户历史上感兴趣的物品越相似，在用户推荐列表中排名越高。

示例：

下图是一个基于项目推荐的简单例子。用户喜欢这个例子《C Primer中文版和编程之美。ItemCF将为这两本书找出最相似的三本书，然后根据公式的定义计算用户对每本书的兴趣。ItemCF因为这本书和《C Primer中文版相似，相似度为0.4，而且这本书和《编程之美》差不多，相似性是0.5。考虑到用户是对的《C Primer中文版的兴趣是1.3，对编程之美的兴趣是0.9，那么用户对算法导论的兴趣就是1.3 × 0.4 0.9×0.5 = 0.97。

从这个例子可以看出，ItemCF一个优点是可以提供推荐解释，即用户历史上喜欢的 项目来解释当前的推荐结果。

MovieLens数据集中ItemCF结果精度(精度和召回率) ItemCF推荐结果的精度也不和谐K正相关或负相关，所以选择合适的K获得最高精度是非常重要的。 流行度 和UserCF不同，参数K对ItemCF推荐结果流行度的影响也不是完全正相关的。 随着K的增加，结果流行度会逐渐提高，但当K增加到一定程度，流行度就不会再有明显变化。覆盖率 K增加会降低系统的覆盖率。

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

在协同过滤中两个物品产生相似度是因为它们共同出现在很多用户 的兴趣列表中。换句话说，每个用户的兴趣列表都对物品的相似度产生贡献。

那么，是不是每个用户的贡献都相同呢?

假设有这么一个用户，他是开书店的，并且买了当当网上80%的书准备用来自己卖。那么， 他的购物车里包含当当网80%的书。假设当当网有100万本书，也就是说他买了80万本。从前面 对ItemCF的讨论可以看到，这意味着因为存在这么一个用户，有80万本书两两之间就产生了相似 度，也就是说，内存里即将诞生一个80万乘80万的稠密矩阵。

另外可以看到，这个用户虽然活跃，但是买这些书并非都是出于自身的兴趣，而且这些书覆 盖了当当网图书的很多领域，所以这个用户对于他所购买书的两两相似度的贡献应该远远小于一 个只买了十几本自己喜欢的书的文学青年。

为了解决这个问题，John S. Breese一个称为IUF(Inverse User Frequence)，即用户活跃度对数的倒数的参数，他认为活跃用户对物品相似度的贡献应该小于不活跃的用户，他提出应该增加IUF 参数来修正物品相似度的计算公式（ItemCF-IUF）:

上面的公式只是对活跃用户做了一种软性的惩罚，但对于很多过于活跃的用户，比如上面那位买了当当网80%图书的用户，为了避免相似度矩阵过于稠密，我们在实际计算中一般直 接忽略他的兴趣列表，而不将其纳入到相似度计算的数据集中。

19. 物品相似度的归一化

如果将ItemCF的相似度矩阵按最大值归一化，可以提高推荐的准确率。

如果已经得到了物品相似度矩阵w，那么可以用如下公式得到归一化之后的相似度矩阵w':

归一化的好处不仅仅在于增加推荐的准确度，它还可以提高推荐的覆盖率和多样性。 一般来说，物品总是属于很多不同的类，每一类中的物品联系比较紧密。举一个例子，假设在一个电影网站中，有两种电影——纪录片和动画片。那么，ItemCF算出来的相似度一般是纪录片和 纪录片的相似度或者动画片和动画片的相似度大于纪录片和动画片的相似度。但是纪录片之间的 相似度和动画片之间的相似度却不一定相同。假设物品分为两类——A和B，A类物品之间的相似 度为0.5，B类物品之间的相似度为0.6，而A类物品和B类物品之间的相似度是0.2。在这种情况下， 如果一个用户喜欢了5个A类物品和5个B类物品，用ItemCF给他进行推荐，推荐的就都是B类物品， 因为B类物品之间的相似度大。但如果归一化之后，A类物品之间的相似度变成了1，B类物品之 间的相似度也是1，那么这种情况下，用户如果喜欢5个A类物品和5个B类物品，那么他的推荐列表中A类物品和B类物品的数目也应该是大致相等的。从这个例子可以看出，相似度的归一化可以提高推荐的多样性。

ItemCF算法和ItemCF-Norm算法的离线实验性能。

20. UserCF和ItemCF的综合比较

UserCF是推荐系统领域较为古老的算法，1992年就已经在电子邮件的个性化推荐系统 Tapestry中得到了应用，1994年被GroupLens1用来实现新闻的个性化推荐，后来被著名的文章分 享网站Digg用来给用户推荐个性化的网络文章。ItemCF则是相对比较新的算法，在著名的电子商 务网站亚马逊和DVD租赁网站Netflix中得到了广泛应用。

那么，为什么Digg使用UserCF，而亚马逊网使用ItemCF呢?

首先回顾一下UserCF算法和ItemCF算法的推荐原理。UserCF给用户推荐那些和他有共同兴 趣爱好的用户喜欢的物品，而ItemCF给用户推荐那些和他之前喜欢的物品类似的物品。从这个算法的原理可以看到，UserCF的推荐结果着重于反映和用户兴趣相似的小群体的热点，而ItemCF 的推荐结果着重于维系用户的历史兴趣。换句话说，UserCF的推荐更社会化，反映了用户所在的小型兴趣群体中物品的热门程度，而ItemCF的推荐更加个性化，反映了用户自己的兴趣传承。

在新闻网站中，用户的兴趣不是特别细化，绝大多数用户都喜欢看热门的新闻。即使是个性 化，也是比较粗粒度的，比如有些用户喜欢体育新闻，有些喜欢社会新闻，而特别细粒度的个性化一般是不存在的。比方说，很少有用户只看某个话题的新闻，主要是因为这个话题不可能保证每天都有新的消息，而这个用户却是每天都要看新闻的。因此，个性化新闻推荐更加强调抓住新闻热点，热门程度和时效性是个性化新闻推荐的重点，而个性化相对于这两点略显次要。因此，UserCF可以给用户推荐和他有相似爱好的一群其他用户今天都在看的新闻，这样在抓住热点和时效性的同时，保证了一定程度的个性化。这是Digg在新闻推荐中使用UserCF的最重要原因。

UserCF适合用于新闻推荐的另一个原因是从技术角度考量的。因为作为一种物品，新闻的更 新非常快，每时每刻都有新内容出现，而ItemCF需要维护一张物品相关度的表，如果物品更新很 快，那么这张表也需要很快更新，这在技术上很难实现。绝大多数物品相关度表都只能做到一天 一次更新，这在新闻领域是不可以接受的。而UserCF只需要用户相似性表，虽然UserCF对于新 用户也需要更新相似度表，但在新闻网站中，物品的更新速度远远快于新用户的加入速度，而且 对于新用户，完全可以给他推荐最热门的新闻，因此UserCF显然是利大于弊。

但是，在图书、电子商务和电影网站，比如亚马逊、豆瓣、Netflix中，ItemCF则能极大地发 挥优势。首先，在这些网站中，用户的兴趣是比较固定和持久的。一个技术人员可能都是在购买技术方面的书，而且他们对书的热门程度并不是那么敏感，事实上越是资深的技术人员，他们看的书就越可能不热门。此外，这些系统中的用户大都不太需要流行度来辅助他们判断一个物品的好坏，而是可以通过自己熟悉领域的知识自己判断物品的质量。因此，这些网站中个性化推荐的任务是帮助用户发现和他研究领域相关的物品。因此，ItemCF算法成为了这些网站的首选算法。此外，这些网站的物品更新速度不会特别快，一天一次更新物品相似度矩阵对它们来说不会造成太大的损失，是可以接受的。

同时，从技术上考虑，UserCF需要维护一个用户相似度的矩阵，而ItemCF需要维护一个物品 相似度矩阵。从存储的角度说，如果用户很多，那么维护用户兴趣相似度矩阵需要很大的空间， 同理，如果物品很多，那么维护物品相似度矩阵代价较大。

在早期的研究中，大部分研究人员都是让少量的用户对大量的物品进行评价，然后研究用 户兴趣的模式。那么，对于他们来说，因为用户很少，计算用户兴趣相似度是最快也是最简单 的方法。但在实际的互联网中，用户数目往往非常庞大，而在图书、电子商务网站中，物品的 数目则是比较少的。此外，物品的相似度相对于用户的兴趣一般比较稳定，因此使用ItemCF是 比较好的选择。当然，新闻网站是个例外，在那儿，物品的相似度变化很快，物品数目庞大， 相反用户兴趣则相对固定(都是喜欢看热门的)，所以新闻网站的个性化推荐使用UserCF算法的 更多。

UserCF和ItemCF优缺点的对比

21. 隐语义模型 LFM（latent factor model）

隐语义模型是最近几年推荐系统领域最为热门的研究话题，它的核心思想是通过隐含特征 (latent factor)联系用户兴趣和物品。

两个用户在豆瓣的读书列表

上图展示了两个用户在豆瓣的读书列表。从他们的阅读列表可以看出，用户A的兴趣涉及侦探小说、科普图书以及一些计算机技术书， 而用户B的兴趣比较集中在数学和机器学习方面。

那么如何给A和B推荐图书呢?

对于UserCF，首先需要找到和他们看了同样书的其他用户(兴趣相似的用户)，然后给他们推荐那些用户喜欢的其他书。 对于ItemCF，需要给他们推荐和他们已经看的书相似的书，比如作者B看了很多关于数据挖掘的书，可以给他推荐机器学习或者模式识别方面的书。

还有一种方法，可以对书和物品的兴趣进行分类。对于某个用户，首先得到他的兴趣分类，然后从分类中挑选他可能喜欢的物品。 基于兴趣分类的方法大概需要解决3个问题：

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

对于第一个问题的简单解决方案是找编辑给物品分类。以图书为例，每本书出版时，编辑都 会给书一个分类。为了给图书分类，出版界普遍遵循中国图书分类法1。但是，即使有很系统的分类体系，编辑给出的分类仍然具有以下缺点：

编辑的意见不能代表各种用户的意见。比如，对于《具体数学》应该属于什么分类，有 人认为应该属于数学，有些人认为应该属于计算机。编辑很难控制分类的粒度。我们知道分类是有不同粒度的，《数据挖掘导论》在粗粒度的 分类中可能属于计算机技术，但在细粒度的分类中可能属于数据挖掘。对于不同的用户， 我们可能需要不同的粒度。比如对于一位初学者，我们粗粒度地给他做推荐就可以了， 而对于一名资深研究人员，我们就需要深入到他的很细分的领域给他做个性化推荐。编辑很难给一个物品多个分类。有的书不仅属于一个类，而是可能属于很多的类。 编辑很难给出多维度的分类。我们知道，分类是可以有很多维度的，比如按照作者分类、 按照译者分类、按照出版社分类。编辑很难决定一个物品在某一个分类中的权重。比如编辑可以很容易地决定《数据挖掘导论》属于数据挖掘类图书，但这本书在这类书中的定位是什么样的，编辑就很难给出一个准确的数字来表示。

为了解决上面的问题，研究人员提出:为什么我们不从数据出发，自动地找到那些类，然后进行个性化推荐？于是，隐含语义分析技术(latent variable ** ysis)出现了。隐含语义分析技术 因为采取基于用户行为统计的自动聚类，较好地解决了上面提出的5个问题：

编辑的意见不能代表各种用户的意见，但隐含语义分析技术的分类来自对用户行为的统 计，代表了用户对物品分类的看法。编辑很难控制分类的粒度，但隐含语义分析技术允许我们指定最终有多少个分类，这个数字越大，分类的粒度就会越细，反正分类粒度就越粗。编辑很难给一个物品多个分类，但隐含语义分析技术会计算出物品属于每个类的权重， 因此每个物品都不是硬性地被分到某一个类中。 编辑很难给出多维度的分类，但隐含语义分析技术给出的每个分类都不是同一个维度的，它是基于用户的共同兴趣计算出来的，如果用户的共同兴趣是某一个维度，那么LFM给出的类也是相同的维度。编辑很难决定一个物品在某一个分类中的权重，但隐含语义分析技术可以通过统计用户行为决定物品在每个类中的权重，如果喜欢某个类的用户都会喜欢某个物品，那么这个物品在这个类中的权重就可能比较高。

隐含语义分析技术从诞生到今天产生了很多著名的模型和方法，其中和该技术相关且耳熟能 详的名词有pLSA、LDA、隐含类别模型(latent class model)、隐含主题模型(latent topic model)、 矩阵分解( ** trix factorization)。

以LFM为例介绍隐含语义分析技术在推荐系统中的应用，LFM的公式如下：

这个公式中 和 是模型的参数，其中 度量了用户u的兴趣和第k个隐类的关系，而 度量了第k个隐类和物品i之间的关系。

要计算这两个参数，需要一个训练集，对于每个用户u，训练集里都包含了用户u喜欢的物品和不感兴趣的物品，通过学习这个数据集，就可以获得上面的模型参数。

推荐系统的用户行为分为显性反馈和隐性反馈。LFM在显性反馈数据(也就是评分数据)上解决评分预测问题并达到了很好的精度。在没有负样本的情况下，需要对用户没有过行为的物品进行采集，对负样本采样时应该遵循以下原则：

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

由于LFM相对而言较为复杂，在这里就省略了书中的具体算法介绍，有兴趣可以读一读《推荐系统实战》

22. LFM和基于领域的方法对比

LFM是一种基于机器学习的方法，具有比较好的理论基础。这个方法和基于邻域的方法(比 如UserCF、ItemCF)相比，各有优缺点。

理论基础 LFM具有比较好的理论基础，它是一种学习方法，通过优化一个设定的指标建立最优的模型。基于邻域的方法更多的是一种基于统计的方法，并没有学习过程。 离线计算的空间复杂度 基于邻域的方法需要维护一张离线的相关表。在离线计算相关表的过程中，如果用户/物品数很多，将会占据很大的内存。 而LFM在建模过程中，可以很好地节省离线计算的内存。离线计算的时间复杂度 在一般情况下，LFM的时间复杂度要稍微高于UserCF和ItemCF，这主要是因为该算法需要多次迭代。但总体上，这两种算法在时间复杂度上没有质的差别。在线实时推荐 UserCF和ItemCF在线服务算法需要将相关表缓存在内存中，然后可以在线进行实时的预测。以ItemCF算法为例，一旦用户喜欢了新的物品，就可以通过查询内存中的相关表将和该物品相似的其他物品推荐给用户。因此，一旦用户有了新的行为， 而且该行为被实时地记录到后台的数据库系统中，他的推荐列表就会发生变化。而从LFM的预测公式可以看到，LFM在给用户生成推荐列表时，需要计算用户对所有物品的兴趣权重，然后排名，返回权重最大的N个物品。那么，在物品数很多时，这一过程的时间复杂度非常高。 LFM不能进行在线实时推荐，也就是说，当用户有了新的行为后，他的推荐列表不会发生变化。

23. 基于图的模型

用户行为很容易用二分图表示，因此很多图的算法都可以用到推荐系统中。

本章讨论的用户行为 数据是由一系列二元组组成的，其中每个二元组(u, i)表示用户u对物品i产生过行为。这种数据集 很容易用一个二分图表示。

用户物品二分图模型：说明用户A对物品a、b、d产生过行为

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

度量图中两个顶点之间相关性的方法很多，但一般来说图中顶点的相关性主要取决于下面3个因素:

两个顶点之间的路径数两个顶点之间路径的长度两个顶点之间的路径经过的顶点

相关性高的一对顶点一般具有如下特征:

两个顶点之间有很多路径相连连接两个顶点之间的路径长度都比较短连接两个顶点之间的路径不会经过出度比较大的顶点

举一个简单的例子，如下图所示，用户A和物品c、e没有边相连，但是用户A和物品c有两 条长度为3的路径相连，用户A和物品e有两条长度为3的路径相连。那么，顶点A与e之间的相关 性要高于顶点A与c，因而物品e在用户A的推荐列表中应该排在物品c之前，因为顶点A与e之间有 两条路径——(A, b, C, e)和(A, d, D, e)。其中，(A, b, C, e)路径经过的顶点的出度为(3, 2, 2, 2)，而(A, d, D, e)路径经过的顶点的出度为(3, 2, 3, 2)。因此，(A, d, D, e)经过了一个出度 比较大的顶点D，所以(A, d, D, e)对顶点A与e之间相关性的贡献要小于(A, b, C, e)。

基于图的推荐算法示例

基于上面3个主要因素，研究人员设计了很多计算图中顶点之间相关性的方法，如 PersonalRank算法。

PersonalRank算法介绍：假设要给用户u进行个性化推荐，可以从用户u对应的节点 开始在用户物品二分图上进行随机游走。游走到任何一个节点时，首先按照概率α决定是继续游走，还是停止这次游走并从vu节点开始重新游走。如果决定继续游走，那么就从当前节点指向的节点中按照均匀分布随机选择一个节点作为游走下次经过的节点。这样，经过很多次随机游走后，每个物品节点被访问到的概率会收敛到一个数。最终的推荐列表中物品的权重就是物品节点的访问概率。（具体的算法和代码属于工程范畴，不具体一一介绍，有兴趣可以去看《推荐系统实践》）

以上图为例，用PersonalRank算法给用户A进行推荐。

上图给出了不同迭代次数后每个顶点的访问概率。从图中可以看到，每个顶点的访问概率在9次迭代之后就基本上收敛了。在这个例子中，用户A没有对物品b、d有过行为。在最后的迭代结果中，d的访问概率大于b，因此给A的推荐列表就是{d, b}。