推荐系统实践读书笔记-05利用上下文信息

本章之前提到的推荐系统算法主要集中研究了如何联系用户兴趣和物品，将最符合用户兴趣的物品推荐给用户，但这些算法都忽略了一点，就是用户所处的上下文（context）。这些上下文包括用户访问推荐系统的时间、地点、心情等，对于提高推荐系统的推荐系统是非常重要的。比如，一个卖衣服的推荐系统在冬天和夏天应该给用户推荐不同种类的服装。推荐系统不能因为用户在夏天喜欢过某件T恤，就在冬天也给该用户推荐类似的T恤。再举个例子，当用户在中关村打开一个美食推荐系统时，如果这个推荐系统推荐的餐馆都是中关村附近的，显然推荐结果更加能够令用户满意。上下文影响用户兴趣的例子还有很多，比如用户上班时和下班后的兴趣会有区别，用户在平时和周末的兴趣会有区别，用户和父母在一起与和同学在一起时的兴趣有区别，甚至用户在上厕所时阅读的文章和在办公桌旁阅读的文章也是不同的。因此，准确了解用户的上下文信息，并将该信息应用于推荐算法是设计好的推荐系统的关键步骤。

关于上下文推荐的研究，可以参考Alexander Tuzhilin① 教授的一篇综述“Context Aware Recommender Systems”。Alexander Tuzhilin教授最近几年和他的学生们对上下文相关的推荐算法进行了深入研究。他们在论文中提到了一个上下文推荐系统的例子——Sourcetone音乐推荐系统（如图5-1所示）。该系统会让用户选择自己现在的心情，然后它根据用户选择的心情给用户推荐音乐。这里，心情是一种重要的上下文，用户在不同的心情下会选择不同的音乐。当然，当用户在某个时间点刚刚使用推荐系统时，系统很难猜出用户当时是什么心情。因此Sourcetone采取了让用户主动告诉系统他现在心情的方式，然后系统根据用户当前的心情并综合考虑其历史兴趣推荐符合他要求的合适歌曲。

和心情类似的上下文还有很多，以看视频为例。用户是在上班时间看还是在下班后看，用户是在家里看还是在单位看，用户是自己一个人看还是和好友一起看，用户是和同学一起看还是和父母一起看，用户是喝着啤酒看还是吃着鸡翅看，这些都是上下文信息，而且这些上下文对用户当时观看什么电视剧都有很大影响。

本章我们主要讨论时间上下文，并简单介绍一下地点上下文，讨论如何将时间信息和地点信息建模到推荐算法中，从而让推荐系统能够准确预测用户在某个特定时刻及特定地点的兴趣。本章仍然研究TopN推荐，即如何给用户生成一个长度为N的推荐列表，而该列表包含了用户在某一时刻或者某个地方最可能喜欢的物品。

---

5.1 时间上下文信息

本节将重点讨论上下文信息中最重要的时间上下文信息。本节首先介绍各种不同的时间效应，然后研究如何将这些时间效应建模到推荐系统的模型中，最后通过实际数据集对比不同模型的效果。

5.1.1 时间效应简介

时间是一种重要的上下文信息，对用户兴趣有着深入而广泛的影响。一般认为，时间信息对用户兴趣的影响表现在以下几个方面。

 用户兴趣是变化的 我们这里提到的用户兴趣变化是因为用户自身原因发生的变化。比如随着年龄的增长，用户小时候喜欢看动画片，长大了喜欢看文艺片。一位程序员随着工作时间的增加，逐渐从阅读入门书籍过渡到阅读专业书籍。一个人参加工作了，工作后的兴趣和学生时代的兴趣相比发生了变化。那么，如果我们要准确预测用户现在的兴趣，就应该关注用户最近的行为，因为用户最近的行为最能体现他现在的兴趣。当然，考虑用户最近的兴趣只能针对渐变的用户兴趣，而对突变的用户兴趣很难起作用，比如用户突然中奖了.

 物品也是有生命周期的 一部电影刚上映的时候可能被很多人关注，但是经久不衰的电影是很少的，很多电影上映后不久就被人们淡忘了。此外，物品也可能受新闻事件的影响，比如一部已经被淡忘的电影会因为突然被某个新闻事件涉及而重新热门起来。因此，当我们决定在某个时刻给某个用户推荐某个物品时，需要考虑该物品在该时刻是否已经过时了。比如，我们给一个NBA迷推荐10年前的某个NBA新闻显然是不太合适的（当然这也不一定，比如用户当时就是在寻找旧的NBA新闻时）。不同系统的物品具有不同的生命周期，比如新闻的生命周期很短暂，而电影的生命周期相对较长。

 季节效应 季节效应主要反映了时间本身对用户兴趣的影响。比如人们夏天吃冰淇淋，冬天吃火锅，夏天穿T恤，冬天穿棉衣。当然，我们也不排除有特别癖好的人存在，但大部分用户都是遵循这个规律的。除此之外，节日也是一种季节效应：每年的圣诞节，人们都要去购物；每年的奥斯卡颁奖礼，人们都要关注电影。2011年ACM推荐大会的一个研讨会曾经举办过一次上下文相关的电影推荐算法比赛①，该比赛要求参赛者预测数据集中用户在奥斯卡颁奖礼附近时刻的行为。关注季节效应的读者可以关注一下这个研讨会上发表的相关论文。

5.1.2 时间效应举例

下面通过一些例子体会一下时间对用户兴趣的影响。我们通过Google Insights工具对时间效应进行一些分析。Google Insights提供了某个搜索词自2004年以来的搜索频率曲线，我们可以通过该曲线发现一些用户兴趣变化的例子.
图5-2展示了3个著名的社交网站名字自2004年以来在google上的搜索量变化曲线，从图中可以看到，facebook的搜索量直线上升，而myspace在2007年达到顶峰后开始下降，twitter的搜索量也在不断增长，但增长趋势明显低于facebook。这种变化的产生主要源于用户兴趣的变化。

图5-3展示了2004年以来著名手机品牌的搜索量变化曲线。从图中可以看到两个现象。第一是自2006年以来，iPhone的搜索量增长明显，反映了越来越多的用户开始喜欢iPhone。另一个现象是几乎所有品牌的手机在年底时搜索量都有一个尖峰，这是因为圣诞节附近手机的销售量会大增，因此这是一种典型的节日效应。

图5-4展示了一些食品的搜索量变化曲线。该图突显了季节效应对用户行为的影响。比如，用户在夏天吃冰淇淋(该图由美国用户统计得出，如果是南半球的澳大利亚，结论应该是相反的），冬天喝汤和咖啡。对于巧克力，可以明显看到两个尖峰，一个是圣诞节附近，而另一个是情人节附近，这也体现了巧克力的销售具有典型的节日效应。

5.1.3 系统时间特性的分析

在给定时间信息后，推荐系统从一个静态系统变成了一个时变的系统，而用户行为数据也变成了时间序列。研究一个时变系统，需要首先研究这个系统的时间特性。本节将通过研究时变的用户行为数据集来研究不同类型网站的时间特性。包含时间信息的用户行为数据集由一系列三元组构成，其中每个三元组(u,i,t)代表了用户u在时刻t对物品i产生过行为。在给定数据集后，本节通过统计如下信息研究系统的时间特性。

 数据集每天独立用户数的增长情况 有些网站处于快速增长期，它们每天的独立用户数都在线性（甚至呈指数级）增加。而有些网站处于平稳期，每天的独立用户数都比较平稳。还有一些网站处于衰落期，每天的用户都在流失。在3种不同的系统中用户行为是不一样的，因此我们首先需要确定系统的增长情况。
 系统的物品变化情况 有些网站，比如新闻网站，每天都会出现大量新的新闻，而每条热门的新闻其时间周期都不会太长，今天热门的新闻也许明天就被人忘记了。
 用户访问情况 有些网站用户来一次就永远不来了，有些网站用户每周来一次，而有些网站用户每天都来。为了度量这些特性，我们可以统计用户的平均活跃天数，同时也可以统计相隔T天来系统的用户的重合度。

1. 数据集的选择
本节将利用Delicious数据集进行离线实验以评测不同算法的预测精度。该数据集包含950 000个用户在2003年9月到2007年12月间对网页打标签的行为。该数据集中包含132 000 000个标签和420 000 000条标签行为记录。该数据集每行是一条标签行为记录，由4部分组成——用户ID、日期、网页URL和标签，代表了一个用户在某一天对某个网页打上了某个标签的行为。因为网页由URL标识，因此可以根据域名将网页分成不同的类别。本节选取了5个域名对应的网页，将整个数据集分成5个不同的数据集加以研究。这5个域名是nytimes.com、sourceforge.net、blogspot.com、wikipedia.org、youtube.com。表5-1给出了本节所用数据集的基本统计信息。

2. 物品的生存周期和系统的时效性
不同类型网站的物品具有不同的生命周期，比如新闻的生命周期很短，而电影的生命周期很长。我们可以用如下指标度量网站中物品的生命周期。

 物品平均在线天数 如果一个物品在某天被至少一个用户产生过行为，就定义该物品在这一天在线。因此，我们可以通过物品的平均在线天数度量一类物品的生存周期。考虑到物品的平均在线天数和物品的流行度应该成正比，因此给定一个数据集，我们首先将物品按照流行度分成20份，然后计算每一类物品的平均在线天数。图5-5展示了5个数据集中物品流行度和物品在线天数之间的关系。横坐标是每一类物品的平均流行度，纵轴是该类物品的平均在线天数。如图所示，不同数据集中的曲线具有不同的斜率。对于流行度相同的物品，维基百科的物品在线天数很长，而纽约时报的物品在线天数很短。这说明这两个网站具有不同的时效性。纽约时报等新闻类网站时效性很强，每一条新闻热起来很快，冷下去也很快，所以它们的物品生存周期都很短。维基百科的词条则不同，它们和百科全书的词条一样，经常会被用户查询到，因此具有比较长的生存周期。

 相隔T天系统物品流行度向量的平均相似度 取系统中相邻T天的两天，分别计算这两天的物品流行度，从而得到两个流行度向量。然后，计算这两个向量的余弦相似度，如果相似度大，说明系统的物品在相隔T天的时间内没有发生大的变化，从而说明系统的时效性不强，物品的平均在线时间较长。相反，如果相似度很小，说明系统中的物品在相隔T天的时间内发生了很大变化，从而说明系统的时效性很强，物品的平均在线时间很短。图5-6展示了5个数据集中相隔T天物品流行度向量的平均相似度。横坐标是T，纵坐标是系统中t时刻物品流行度向量和t+T时刻物品流行度向量的平均相似度（取不同的t计算相似度，取平均值）。图5-6中的结果首先说明了T越大，系统物品流行度分布差距越大——这一点是显然的。其次，可以看到，尽管所有的数据集中相似度都随T的增加而下降，但下降速率却是不同的。在纽约时报的数据集中，相似度下降很快，说明系统中物品流行度分布变化很快，系统时效性很强。而维基百科的数据集中，相似度的下降却相对比较慢，说明系统中物品流行度分布变化较慢，系统时效性比较弱。

5.1.4 推荐系统的实时性

用户兴趣是不断变化的，其变化体现在用户不断增加的新行为中。一个实时的推荐系统需要能够实时响应用户新的行为，让推荐列表不断变化，从而满足用户不断变化的兴趣。

如果仔细研究一下亚马逊网的推荐系统，就可以发现它是一个实时的推荐系统。如图5-7所示，我首先打开亚马逊网的推荐系统页面，大家可以看到亚马逊网给我推荐的图书。然后，我通过搜索找到关于MongoDB的一本书，单击了Liked（喜欢过）按钮。接着，我重新回到亚马逊网的推荐系统页面，发现我的推荐列表变化了，多了一本Mahout in Action，单击fix this recommendation（修正此推荐），可以看到亚马逊网给我推荐这本书的理由：因为我刚刚为MongoDB: The Definitive Guide单击了Linked。

这一切都发生在几十秒内。为了证明亚马逊网不是每次刷新都随机展示推荐列表，我曾经每隔十几秒就刷新一次亚马逊网的推荐列表，发现并没有任何变化。但一旦我产生了新的行为，变化就发生了。当然，并非我的任何新行为都能导致推荐列表的变化，比如如果我仅仅是浏览了MongoDB: The Definite Guide一书的网页，推荐列表并不会变化，但我的所有显性反馈行为都会导致推荐列表的变化。

实现推荐系统的实时性除了对用户行为的存取有实时性要求，还要求推荐算法本身具有实时性，而推荐算法本身的实时性意味着：
 实时推荐系统不能每天都给所有用户离线计算推荐结果，然后在线展示昨天计算出来的结果。所以，要求在每个用户访问推荐系统时，都根据用户这个时间点前的行为实时计算推荐列表。

 推荐算法需要平衡考虑用户的近期行为和长期行为，即要让推荐列表反应出用户近期行为所体现的兴趣变化，又不能让推荐列表完全受用户近期行为的影响，要保证推荐列表对用户兴趣预测的延续性。

5.1.5 推荐算法的时间多样性

很多推荐系统的研究人员经常遇到一个问题，就是每天给用户的推荐结果都差不多，没有什么变化。推荐系统每天推荐结果的变化程度被定义为推荐系统的时间多样性。时间多样性高的推荐系统中用户会经常看到不同的推荐结果。

那么推荐系统的时间多样性和用户满意度之间是否存在关系呢？时间多样性高是否就能提高用户的满意度？为了解答这些问题，英国研究人员进行了一次实验，他们设计了3种推荐系统。

A 给用户推荐最热门的10部电影。
B 从最热门的100部电影中推荐10部给用户，但保证了时间多样性，每周都有7部电影推荐结果不在上周的推荐列表中。
C 每次都从所有电影中随机挑选10部推荐给用户。

对比这3种算法可知，A算法每天给用户的推荐结果都一样，没有时间多样性，B算法保证了一定的时间多样性，同时推荐结果也是比较热门的电影，C算法具有完全的时间多样性，因为它每次推荐都是从所有电影中随机选择的，但是它并没有考虑电影的热门程度。
然后，研究人员进行了用户调查实验。他们每次给用户展示30个推荐结果（分别来自3个不同的算法）然后让用户给这些推荐结果评分。经过5周的实验后，研究人员统计了每一周不同算法的推荐结果的平均评分，发现了如下现象（具体结果分析请参考他们的论文）。

 A、B算法的平均分明显高于C算法。这说明纯粹的随机推荐虽然具有最高的时间多样性，但不能保证推荐的精度。
 A算法的平均分随时间逐渐下降，而B算法的平均分随时间基本保持不变。这说明A算法因为没有时间多样性，从而造成用户满意度不断下降，从而也说明了保证时间多样性的重要性。

在证明了时间多样性对推荐系统的正面意义之后，下面的问题就是如何在不损失精度的情况下提高推荐结果的时间多样性。

提高推荐结果的时间多样性需要分两步解决：首先，需要保证推荐系统能够在用户有了新的行为后及时调整推荐结果，使推荐结果满足用户最近的兴趣；其次，需要保证推荐系统在用户没有新的行为时也能够经常变化一下结果，具有一定的时间多样性。

对于第一步，又可以分成两种情况进行分析。第一是从推荐系统的实时性角度分析。有些推荐系统会每天离线生成针对所有用户的推荐结果，然后在线直接将这些结果展示给用户。这种类型的系统显然无法做到在用户有了新行为后及时调整推荐结果。第二，即使是实时推荐系统，由于使用的算法不同，也具有不同的时间多样性。对于不同算法的时间多样性，Neal Lathia博士在博士论文中进行了深入探讨②，这里就不再详述了。

那么，如果用户没有行为，如何保证给用户的推荐结果具有一定的时间多样性呢？一般的思路有以下几种。
 在生成推荐结果时加入一定的随机性。比如从推荐列表前20个结果中随机挑选10个结果
展示给用户，或者按照推荐物品的权重采样10个结果展示给用户。
 记录用户每天看到的推荐结果，然后在每天给用户进行推荐时，对他前几天看到过很多次的推荐结果进行适当地降权。
 每天给用户使用不同的推荐算法。可以设计很多推荐算法，比如协同过滤算法、内容过滤算法等，然后在每天用户访问推荐系统时随机挑选一种算法给他进行推荐。

当然，时间多样性也不是绝对的。推荐系统需要首先保证推荐的精度，在此基础上适当地考虑时间多样性。在实际应用中需要通过多次的实验才能知道什么程度的时间多样性对系统是最好的。

5.1.6 时间上下文推荐算法

上一节介绍了很多时间效应，本节主要讨论如何将这些时间效应应用到系统中。建模时间信息有很多方法，本节将分别介绍不同的方法，并通过实验对比这些方法。

1. 最近最热门
在没有时间信息的数据集中，我们可以给用户推荐历史上最热门的物品。那么在获得用户行为的时间信息后，最简单的非个性化推荐算法就是给用户推荐最近最热门的物品了。给定时间T，物品i最近的流行度 i( ) n T 可以定义为：

这里，α是时间衰减参数。
下面的Python代码实现了上面的计算公式：

def RecentPopularity(records, alpha, T): 
 ret = dict() 
 for user,item,tm in records: 
 if tm >= T: 
 continue 
 addToDict(ret, item, 1 / (1.0 + alpha * (T - tm))) 
 return ret
1
2
3
4
5
6
7

2. 时间上下文相关的ItemCF算法
基于物品（item-based）的个性化推荐算法是商用推荐系统中应用最广泛的，从前面几章的讨论可以看到，该算法由两个核心部分构成：
 利用用户行为离线计算物品之间的相似度；
 根据用户的历史行为和物品相似度矩阵，给用户做在线个性化推荐。时间信息在上面两个核心部分中都有重要的应用，这体现在两种时间效应上。
 物品相似度 用户在相隔很短的时间内喜欢的物品具有更高相似度。以电影推荐为例，用户今天看的电影和用户昨天看的电影其相似度在统计意义上应该大于用户今天看的电影和用户一年前看的电影的相似度。
 在线推荐 用户近期行为相比用户很久之前的行为，更能体现用户现在的兴趣。因此在预测用户现在的兴趣时，应该加重用户近期行为的权重，优先给用户推荐那些和他近期喜欢的物品相似的物品。

首先回顾一下前面提到的基于物品的协同过滤算法，它通过如下公式计算物品的相似度：

而在给用户u做推荐时，用户u对物品i的兴趣p(u,i)通过如下公式计算：

在得到时间信息（用户对物品产生行为的时间）后，我们可以通过如下公式改进相似度计算：

注意，上面的公式在分子中引入了和时间有关的衰减项，其中tui 是用户u对物品i产生行为的时间。f函数的含义是，用户对物品i和物品j产生行为的时间越远，则衰减项越小。我们可以找到很多数学衰减函数，本节使用如下衰减函数：

α是时间衰减参数，它的取值在不同系统中不同。如果一个系统用户兴趣变化很快，就应该取比较大的α，反之需要取比较小的α。
改进后ItemCF的相似度可以通过如下代码实现：

def ItemSimilarity(train, alpha): 
 #calculate co-rated users between items 
 C = dict() 
 N = dict() 
 for u, items in train.items(): 
 for i,tui in items.items(): 
 N[i] += 1 
 for j,tuj in items.items(): 
 if i == j: 
 continue 
 C[i][j] += 1 / (1 + alpha * abs(tui - tuj)) 
 #calculate finial similarity matrix W 
 W = dict() 
 for i,related_items in C.items(): 
 for j, cij in related_items.items(): 
 W[u][v] = cij / math.sqrt(N[i] * N[j]) 
 return W
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

除了考虑时间信息对相关表的影响，我们也应该考虑时间信息对预测公式的影响。一般来说，用户现在的行为应该和用户最近的行为关系更大。因此，我们可以通过如下方式修正预测公式：

其中，t0 是当前时间。上面的公式表明，tuj 越靠近t0 ，和物品j相似的物品就会在用户u的推荐列表中获得越高的排名。 是时间衰减参数，需要根据不同的数据集选择合适的值。上面的推荐算法可以通过如下代码实现。

def Recommendation(train, user_id, W, K, t0): 
 rank = dict() 
 ru = train[user_id] 
 for i,pi in ru.items(): 
 for j, wj in sorted(W[i].items(), \ 
 key=itemgetter(1), reverse=True)[0:K]: 
 if j,tuj in ru.items(): 
 continue 
 rank[j] += pi * wj / (1 + alpha * (t0 - tuj)) 
 return rank
1
2
3
4
5
6
7
8
9
10

3. 时间上下文相关的UserCF算法
和ItemCF算法一样，UserCF算法同样可以利用时间信息提高预测的准确率。首先，回顾一下前面关于UserCF算法的基本思想：给用户推荐和他兴趣相似的其他用户喜欢的物品。从这个基本思想出发，我们可以在以下两个方面利用时间信息改进UserCF算法。
 用户兴趣相似度 在第3章的定义中我们知道，两个用户兴趣相似是因为他们喜欢相同的物品，或者对相同的物品产生过行为。但是，如果两个用户同时喜欢相同的物品，那么这两个用户应该有更大的兴趣相似度。比如用户A在2006年对C++感兴趣，在2007年对Java感兴趣，用户B在2006年对Java感兴趣，2007年对C++感兴趣，而用户C和A一样，在2006年对C++感兴趣，在2007年对Java感兴趣。那么，根据第3章的定义，用户A和用户B的兴趣相似度等于用户A和用户C的兴趣相似度。但显然，在实际世界，我们会认为用户A和C的兴趣相似度要大于用户A和B。
 相似兴趣用户的最近行为 在找到和当前用户u兴趣相似的一组用户后，这组用户最近的兴趣显然相比这组用户很久之前的兴趣更加接近用户u今天的兴趣。也就是说，我们应该给用户推荐和他兴趣相似的用户最近喜欢的物品。

在新闻推荐系统中，时间信息在UserCF中的作用非常明显。假设我们今天要给一个NBA篮球迷推荐新闻。首先，我们需要找到一批和他一样的NBA迷，然后找到这批人在当前时刻最近阅读最多的新闻推荐给当前用户，而不是把这批人去年阅读的新闻推荐给当前用户，因为他们去年阅读最多的新闻在现在看显然过期了。

首先回顾一下UserCF的推荐公式。UserCF通过如下公式计算用户u和用户v的兴趣相似度：

其中N(u)是用户u喜欢的物品集合，N(v)是用户v喜欢的物品集合。可以利用如下方式考虑时间信息：

上面公式的分子对于用户u和用户v共同喜欢的物品i增加了一个时间衰减因子。用户u和用户v对物品i产生行为的时间越远，那么这两个用户的兴趣相似度就会越小。

def UserSimilarity(train): 
 # build inverse table for item_users 
 item_users = dict() 
 for u, items in train.items(): 
 for i,tui in items.items(): 
 if i not in item_users: 
 item_users[i] = dict() 
 item_users[i][u] = tui 
 
 #calculate co-rated items between users 
 C = dict() 
 N = dict() 
 for i, users in item_users.items(): 
 for u,tui in users.items(): 
 N[u] += 1 
 for v,tvi in users.items(): 
 if u == v: 
 continue 
 C[u][v] += 1 / (1 + alpha * abs(tui - tvi)) 
 #calculate finial similarity matrix W 
 W = dict() 
 for u, related_users in C.items(): 
 for v, cuv in related_users.items(): 
 W[u][v] = cuv / math.sqrt(N[u] * N[v]) 
 return W
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

在得到用户相似度后，UserCF通过如下公式预测用户对物品的兴趣：

其中，S(u,K)包含了和用户u兴趣最接近的K个用户。如果用户v对物品i产生过行为，那么
rvi = 1，否则 rvi = 0 。
如果考虑和用户u兴趣相似用户的最近兴趣，我们可以设计如下公式：

def Recommend(user, T, train, W): 
 rank = dict() 
 interacted_items = train[user] 
 for v, wuv in sorted(W[u].items, key=itemgetter(1), 
 reverse=True)[0:K]: 
 for i, tvi in train[v].items: 
 if i in interacted_items: 
 #we should filter items user interacted before 
 continue 
 rank[i] += wuv / (1 + alpha * (T - tvi)) 
 return rank
1
2
3
4
5
6
7
8
9
10
11

5.1.7 时间段图模型

基于图的模型在前面几章中得到了广泛应用。在时变个性化推荐系统中，它依然得到了广泛应用。我们在KDD会议上曾经提出过一个时间段图模型，试图解决如何将时间信息建模到图模型中的方法，最终取得了不错的效果。

时间段图模型 G(U,Su,I,Si,E,w,a) 也是一个二分图。U是用户节点集合， SU 是用户时间段节点集合。一个用户时间段节点 Vut∈Su 会和用户u在时刻t喜欢的物品通过边相连。I是物品节点集合，SI 是物品时间段节点集合。一个物品时间段节点 it I v S  会和所有在时刻t喜欢物品i的用户通过边相连。E是边集合，它包含了3种边：(1)如果用户u对物品i有行为，那么存在边 ；(2)如果用户u在t时刻对物品i有行为，那么就存在两条边 e(vut,vi),e(vu,vit)∈E。w(e)定义了边的权重，σ（e） 定义了顶点的权重。
图5-8是一个简单的时间段图模型示例。在这个例子中，用户A在时刻2对物品b产生了行为。因此，时间段图模型会首先创建4个顶点，即用户顶点A、用户时间段顶点A:2、物品顶点b、物品时间段顶点b:2。然后，图中会增加3条边，即(A, b)、(A:2, b)、(A, b:2)。这里不再增加(A:2, b:2)这条边，一方面是因为增加这条边后不会对结果有所改进，另一方面则是因为增加一条边会增加图的空间复杂度和图上算法的时间复杂度。

定义完图的结构后，最简单的想法是可以利用前面提到的PersonalRank算法给用户进行个性化推荐。但是因为这个算法需要在全图上进行迭代计算，所以时间复杂度比较高。因此我们提出了一种称为路径融合算法的方法，通过该算法来度量图上两个顶点的相关性。
一般来说，图上两个相关性比较高的顶点一般具有如下特征：
 两个顶点之间有很多路径相连；
 两个顶点之间的路径比较短；
 两个顶点之间的路径不经过出度比较大的顶点。

从这3条原则出发，路径融合算法首先提取出两个顶点之间长度小于一个阈值的所有路径，然后根据每条路径经过的顶点给每条路径赋予一定的权重，最后将两个顶点之间所有路径的权重之和作为两个顶点的相关度。

假设 P={v1,v2,…vn}是连接顶点 v1 和vn 的一条路径，这条路径的权重TP 取决于这条路径经过的所有顶点和边：

这里out(v)是顶点v指向的顶点集合，|out(v)|是顶点v的出度，σ（Vi）∈（0,1]定义了顶点的权重，w(Vi,Vi+1)∈（0,1定义了边 e(vi,vi+1)的权重。上面的定义符合上面3条原则的后两条 所以路径越长n越大，TP 就越小。同时，如果路径经过了出度大的顶点v’，那么因为|out(v’)|比较大，所以TP也会比较小。
在定义了一条路径的权重后，就可以定义顶点之间的相关度。对于顶点v和v’，令 p(v,v,K) 为这两个顶点间距离小于K的所有路径，那么这两个顶点之间的相关度可以定义为：

对于时间段图模型，所有边的权重都定义为1，而顶点的权重 σ（v）定义如下：

这里，α，β∈【0,1】是两个参数，控制了不同顶点的权重。
路径融合算法可以基于图上的广度优先搜索算法实现，下面的Python代码简单实现了路径融合算法。

 Q = [] 
 V = set() 
 depth = dict() 
 rank = dict() 
 depth['u:' + user] = 0 
 depth['ut:' + user + '_' + time] = 0 
 rank ['u:' + user] = alpha 
 rank ['ut:' + user + '_' + time] = 1 - alpha 
 Q.append('u:' + user) 
 Q.append('ut:' + user + '_' + time) 
 while len(Q) > 0: 
 v = Q.pop() 
 if v in V: 
 continue
 if depth[v] > 3: 
 continue 
 for v2,w in G[v].items(): 
 if v2 not in V: 
 depth[v2] = depth[v] + 1 
 Q.append(v2) 
 rank[v2] = rank[v] * w 
 return rank
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5.1.8 离线实验

为了证明时间上下文信息对推荐系统至关重要，本节将利用离线实验对比使用时间信息后不同推荐算法的离线性能。

1. 实验设置
在得到由（用户、物品、时间）三元组组成的数据集后，我们可以通过如下方式生成训练集和测试集。对每一个用户，将物品按照该用户对物品的行为时间从早到晚排序，然后将用户最后一个产生行为的物品作为测试集，并将这之前的用户对物品的行为记录作为训练集。推荐算法将根据训练集学习用户兴趣模型，给每个用户推荐N个物品，并且利用准确率和召回率评测推荐算法的精度。本节将选取不同的N(10,20,…,100)进行10次实验，并画出最终的准确率和召回率曲线，通过该曲线来比较不同算法的性能。

这里，R(u,N)是推荐算法给用户u提供的长度为N的推荐列表，T(u)是测试集中用户喜欢的物品集合。

本节的离线实验将同时对比如下算法，将它们的召回率和准确率曲线画在一张图上。
 Pop 给用户推荐当天最热门的物品。
 TItemCF 融合时间信息的ItemCF算法。
 TUserCF 融合时间信息的UserCF算法。
 ItemCF 不考虑时间信息的ItemCF算法。
 UserCF 不考虑时间信息的UserCF算法。
 SGM 时间段图模型。
 USGM 物品时间节点权重为0的时间段图模型。
 ISGM 用户时间节点权重为0的时间段图模型。

这里，我们没有对比不同参数下各个算法的性能，最终的实验结果是在最优参数下获得的。图5-9、图5-10、图5-11、图5-12、图5-13展示了5个不同数据集上各个算法的召回率和准确率曲线。

仔细研究不同数据集的召回率和准确率曲线可以发现，这些曲线的形状将数据集分成了两类。一类是BlogSpot、YouTube、NYTimes，另一类是Wikipedia和SourceForge。在第一类数据集中，有4个算法（SGM、ISGM、TUserCF、Pop）明显好于另外4个算法，而在第二类数据集中，不同算法的召回率和准确率曲线交织在一起，并不能明显分开。而且，在第一类数据集中，即使是非个性化推荐算法Pop也优于很多个性化推荐算法（TItemCF、USGM）。这主要是因为第一类数据集的时效性很强，因此用户兴趣的个性化不是特别明显，每天最热门的物品已经吸引了绝大多数用户的眼球，而长尾中的物品很少得到用户的关注。

5.2 地点上下文信息

除了时间，地点作为一种重要的空间特征，也是一种重要的上下文信息。不同地区的用户兴趣有所不同，用户到了不同的地方，兴趣也会有所不同。在中关村逛街逛累了，希望寻找美食时，你可能会考虑几个因素，包括距离、价位、口味和口碑，而在这些因素里，最重要的因素可能是距离。因此，很多基于位置的服务（LBS）软件都提供了推荐附近餐馆和商店的功能（如图5-14所示）。谷歌在2010年推出了一个叫做Hotpot①的服务，该服务让用户对自己去过的地点评分，然后通过用户评分给用户推荐地点（如图5-15所示）。Hotpot利用了用户在谷歌地图上标注和评论的5亿个不同的地点②，目的是帮助用户更方便地找到附近可能令他们感兴趣的地方，这些地方包括餐馆、酒店、咖啡馆和旅游景点等。

西班牙电信的研究人员曾经设计过一个基于位置的电影推荐系统，并且提供了详细的技术报告①。该报告详细地介绍了如何在iPhone上开发一个推荐系统，如何在电影推荐中融入用户的位置信息，感兴趣的读者可以仔细阅读他们的报告。

基于位置的推荐算法
明尼苏达大学的研究人员提出过一个称为LARS（Location Aware Recommender System,位置感知推荐系统）的和用户地点相关的推荐系统。该系统首先将物品分成两类，一类是有空间属性的，比如餐馆、商店、旅游景点等，另一类是无空间属性的物品，比如图书和电影等。同时，它将用户也分成两类，一类是有空间属性的，比如给出了用户现在的地址（国家、城市、邮编等），另一类用户并没有相关的空间属性信息。它使用的数据集有3种不同的形式。

 （用户，用户位置，物品，评分），每一条记录代表了某一个地点的用户对物品的评分。它们使用的是MovieLens数据集。该数据集给出了用户的邮编，从而可以知道用户的大致地址。
 （用户，物品，物品位置，评分），每一条记录代表了用户对某个地方的物品的评分。LARS使用了FourSquare的数据集，该数据集包含用户对不同地方的餐馆、景点、商店的评分。
 （用户，用户位置，物品，物品位置，评分），每一条记录代表了某个位置的用户对某个位置的物品的评分。
LARS通过研究前两种数据集，发现了用户兴趣和地点相关的两种特征。
 兴趣本地化 不同地方的用户兴趣存在着很大的差别。不同国家和地区用户的兴趣存在着一定的差异性。LARS一文通过MovieLens数据集上的用户邮编数据统计发现，佛罗里达州的用户喜欢的电影和威斯康星州的用户喜欢的电影类型存在很大差别。关于这一点，纽约时报曾经发表过一篇文章，它给出了每个不同地区的用户使用Netflix的情况①。在那篇文章中，它给出了不同电影在不同地区的DVD租赁情况。我们通过研究第2章提到的Lastfm数据集，也可以得到不同国家用户对歌手兴趣的差异（如表5-2所示）。
 活动本地化 一个用户往往在附近的地区活动。通过分析Foursqure的数据，研究人员发现45%的用户其活动范围半径不超过10英里②，而75%的用户活动半径不超过50英里。因此，在基于位置的推荐中我们需要考虑推荐地点和用户当前地点的距离，不能给用户推荐太远的地方。

对于第一种数据集，LARS的基本思想是将数据集根据用户的位置划分成很多子集。因为位置信息是一个树状结构，比如国家、省、市、县的结构。因此，数据集也会划分成一个树状结构。然后，给定每一个用户的位置，我们可以将他分配到某一个叶子节点中，而该叶子节点包含了所有和他同一个位置的用户的行为数据集。然后，LARS就利用这个叶子节点上的用户行为数据，通过ItemCF给用户进行推荐。

不过这样做的缺点是，每个叶子节点上的用户数量可能很少，因此他们的行为数据可能过于稀疏，从而无法训练出一个好的推荐算法。为此，我们可以从根节点出发，在到叶子节点的过程中，利用每个中间节点上的数据训练出一个推荐模型，然后给用户生成推荐列表。而最终的推荐结果是这一系列推荐列表的加权。文章的作者将这种算法成为金字塔模型，而金字塔的深度影响了推荐系统的性能，因而深度是这个算法的一个重要指标。下文用LARS-U代表该算法。

举一个简单的例子，如图5-16所示，假设有一个来自中国江苏南京的用户。我们会首先根据所有用户的行为利用某种推荐算法（假设是ItemCF）给他生成推荐列表，然后利用中国用户的行为给他生成第二个推荐列表，以此类推，我们用中国江苏的用户行为给该用户生成第三个推荐列表，并利用中国江苏南京的用户行为给该用户生成第四个推荐列表。然后，我们按照一定的权重将这4个推荐列表线性相加，从而得到给该用户的最终推荐列表。

对于第二种数据集，每条用户行为表示为四元组（用户、物品、物品位置、评分），表示了用户对某个位置的物品给了某种评分。对于这种数据集，LARS会首先忽略物品的位置信息，利用ItemCF算法计算用户u对物品i的兴趣P(u,i)，但最终物品i在用户u的推荐列表中的权重定义为

在该公式中，TravelPenalty(u,i)表示了物品i的位置对用户u的代价。计算TravelPenalty(u,i)的基本思想是对于物品i与用户u之前评分的所有物品的位置计算距离的平均值（或者最小值）。关于如何度量地图上两点的距离，最简单的是基于欧式距离①。当然，欧式距离有明显的缺点，因为人们是不可能沿着地图上的直线距离从一点走到另一点的。比较好的度量方式是利用交通网络数据，将人们实际需要走的最短距离作为距离度量①。

为了避免计算用户对所有物品的TravelPenalty，LARS在计算用户u对物品i的兴趣度RecScore(u,i)时，首先对用户每一个曾经评过分的物品（一般是餐馆、商店、景点），找到和他距离小于一个阈值d的所有其他物品，然后将这些物品的集合作为候选集，然后再利用上面的公式计算最终的RecScore。

对于第三种数据集，LARS一文没有做深入讨论。不过，从第三种数据集的定义可以看到，它相对于第二种数据集增加了用户当前位置这一信息。而在给定了这一信息后，我们应该保证推荐的物品应该距离用户当前位置比较近，在此基础上再通过用户的历史行为给用户推荐离他近且他会感兴趣的物品。

为了证明兴趣本地化和活动本地化两种效应，作者在FourSquare和MovieLens两个数据集上进行了离线实验。作者使用TopN推荐的Precision作为评测指标。

作者首先在FourSquare数据集上对比了ItemCF算法和考虑了TravelPenalty之后的算法（简称为LARS-T）。结果证明考虑TravelPenality确实能够提高TopN推荐的离线准确率，LARS-T算法明显优于ItemCF算法。

然后，作者在FourSquare数据集和MovieLens数据集上对比了普通的ItemCF算法和考虑用户位置的金字塔模型后的LARS-U算法。同时，作者对比了不同深度对LARS-U算法的影响。实验表明，选择合适的深度对LARS-U算法很重要，不过在绝大多数深度的选择下，LARS-U算法在两个数据集上都优于普通的ItemCF算法。

5.3 扩展阅读

时间上下文信息在Netflix Prize中得到了广泛关注，很多参赛者都研究了如何利用这一信息。这方面最著名的文章无疑是Koren的“collaborative filtering with temporal dynamics”，该文系统地总结了各种使用时间信息的方式，包括考虑用户近期行为的影响，考虑时间的周期性等。

英国剑桥大学的Neal Lathia在读博士期间对时间上下文信息以及推荐系统的时间效应进行了深入研究。他在“Temporal Diversity in Recommender Systems”一文中深入分析了时间多样性对推荐系统的影响。他的博士论文“Evaluating Collaborative Filtering Over Time”论述了各种不同推荐算法是如何随时间演化的。

如果要系统地研究与上下文推荐相关的工作，可以参考Alexander Tuzhili教授的工作（http://pages.stern.nyu.edu/~atuzhili/），他在最近几年和学生对上下文推荐问题进行了深入研究。