推荐系统实践读书笔记-08评分预测问题

本书到目前为止都是在讨论TopN推荐，即给定一个用户，如何给他生成一个长度为N的推荐列表，使该推荐列表能够尽量满足用户的兴趣和需求。本书之所以如此重视TopN推荐，是因为它非常接近于满足实际系统的需求，实际系统绝大多数情况下就是给用户提供一个包括N个物品的个性化推荐列表。

但是，很多从事推荐系统研究的同学最早接触的却是评分预测问题。从GroupLens到Netflix Prize到Yahoo! Music的KDD Cup，评分预测问题都是推荐系统研究的核心。评分预测问题最基本的数据集就是用户评分数据集。该数据集由用户评分记录组成，每一条评分记录是一个三元组(u, i, r)，表示用户u给物品i赋予了评分r，本章用 rui 表示用户u对物品i的评分。因为用户不可能对所有物品都评分，因此评分预测问题就是如何通过已知的用户历史评分记录预测未知的用户评分记录。表8-1是一个评分预测问题的例子，在该例子中每个用户都对一些电影给出了评分，比如用户A给《虎口脱险》评了1分，给《唐山大兄》评了5分，给《少林足球》评了4分，给《大话西游》评了5分。但是，每个用户都没有对所有电影评分，比如用户A没有给《变形金刚》和《黑客帝国》评分。那么，当用户浏览网页并看到《变形金刚》和《黑客帝国》时，我们希望能够给用户一个分数表明我们认为用户是否会喜欢这部电影，而这个分数也可以帮助用户决策是否要看这部电影，而如何提高这个分数的预测精度就是评分预测要解决的主要问题。

本章将主要讨论评分预测这一推荐领域的经典问题。因为这一问题的研究集中在学术界，所以本章的介绍也比较偏学术，相对前面各章会增加一些公式和理论的讨论。

---

8.1 离线实验方法

评分预测问题基本都通过离线实验进行研究。在给定用户评分数据集后，研究人员会将数据集按照一定的方式分成训练集和测试集，然后根据测试集建立用户兴趣模型来预测测试集中的用户评分。对于测试集中的一对用户和物品（u, i），用户u对物品i的真实评分是 rui ，而推荐算法预测的用户u对物品i的评分为 rˆui ，那么一般可以用均方根误差RMSE度量预测的精度：

评分预测的目的就是找到最好的模型最小化测试集的RMSE。
关于如何划分训练集和测试集，如果是和时间无关的预测任务，可以以均匀分布随机划分数据集，即对每个用户，随机选择一些评分记录作为测试集，剩下的记录作为测试集。如果是和时间相关的任务，那么需要将用户的旧行为作为训练集，将用户的新行为作为测试集。Netflix通过如下方式划分数据集，首先将每个用户的评分记录按照从早到晚进行排序，然后将用户最后10%的评分记录作为测试集，前90%的评分记录作为训练集。

8.2 评分预测算法

自从Netflix Prize大赛以来，不同国家的不同研究人员提出了很多评分预测算法，而Netflix Prize的获胜队伍更是用了上百个不同的模型才取得了最终的成功。本节将从简单到复杂地介绍具有代表性的算法，并给出它们在Netflix数据集上的效果。

8.2.1 平均值

最简单的评分预测算法是利用平均值预测用户对物品的评分的。下面各节将分别介绍各种不同的平均值
1. 全局平均值
在平均值里最简单的是全局平均值。它的定义为训练集中所有评分记录的评分平均值：

而最终的预测函数可以直接定义为：

2. 用户评分平均值
用户u的评分平均值 ru 定义为用户u在训练集中所有评分的平均值：

而最终的预测函数可以定义为：

3. 物品评分平均值
物品i的评分平均值 ri 定义为物品i在训练集中接受的所有评分的平均值：

而最终的预测函数可以定义为：

4. 用户分类对物品分类的平均值
假设有两个分类函数，一个是用户分类函数∅ ，一个是物品分类函数ψ 。∅（u） 定义了用户u所属的类， ψ(i) 定义了物品i所属的类。那么，我们可以利用训练集中同类用户对同类物品评分的平均值预测用户对物品的评分，即：

前面提出的全局平均值，用户评分平均值和物品评分平均值都是类类平均值的一种特例。
 如果定义∅（u）=0， ψ(i)=0那么 rˆui 就是全局平均值。
 如果定义 ∅（u）=u， ψ(i)=0，那么 rˆui 就是用户评分平均值。
 如果定义∅（u）=0， ψ(i)=i ，那么 rˆui 就是物品评分平均值。
除了这3种特殊的平均值，在用户评分数据上还可以定义很多不同的分类函数。
 用户和物品的平均分 对于一个用户，可以计算他的评分平均分。然后将所有用户按照评分平均分从小到大排序，并将用户按照平均分平均分成N类。物品也可以用同样的方式分类。
 用户活跃度和物品流行度 对于一个用户，将他评分的物品数量定义为他的活跃度。得到用户活跃度之后，可以将用户通过活跃度从小到大排序，然后平均分为N类。物品的流行度定义为给物品评分的用户数目，物品也可以按照流行度均匀分成N类。

下面的Python代码给出了类类平均值的计算方法。

def PredictAll(records, user_cluster, item_cluster): 
 total = dict() 
 count = dict() 
 for r in records: 
 if r.test != 0: 
 continue 
 gu = user_cluster.GetGroup(r.user) 
 gi = item_cluster.GetGroup(r.item) 
 basic.AddToMat(total, gu, gi, r.vote) 
 basic.AddToMat(count, gu, gi, 1) 
 for r in records: 
 gu = user_cluster.GetGroup(r.user) 
 gi = item_cluster.GetGroup(r.item)
 average = total[gu][gi] / (1.0 * count[gu][gi] + 1.0) 
 r.predict = average
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在这段代码中，user_cluster.GetGroup函数接收一个用户ID，然后根据一定的算法返回用户的类别。item_cluster.GetGroup函数接收一个物品的ID，然后根据一定的算法返回物品的类别。total[gu][gi]/count[gu][gi]记录了第gu类用户给第gi类物品评分的平均分。

上文提到，user_cluster和item_cluster有很多不同的定义方式，下面的Python代码给出了不同的user_cluster和item_cluster定义方式。其中，Cluster是基类，对于任何用户和物品，它的GetGroup函数都返回0，因此如果user_cluster和item_cluter都是Cluster类型，那么最终的预测函数就是全局平均值。IdCluster的GetGroup函数接收一个ID，会返回这个ID，那么如果user_cluster是Cluster类型，而item_cluster是IdCluster类型，那么最终的预测函数给出的就是物品平均值。以此类推，表8-2展示了MovieLens数据集中利用不同平均值方法得到RMSE，实验结果表明对用户使用UserVoteCluster，对物品采用ItemVoteCluster，可以获得最小的RMSE。

class Cluster: 
 def __init__(self,records): 
 self.group = dict() 
 def GetGroup(self, i): 
 return 0 
class IdCluster(Cluster): 
 def __init__(self, records): 
 Cluster.__init__(self, records) 
 def GetGroup(self, i): 
 return i 
class UserActivityCluster(Cluster): 
 def __init__(self, records): 
 Cluster.__init__(self, records) 
 activity = dict() 
 for r in records: 
 if r.test != 0: 
 continue 
 basic.AddToDict(activity, r.user, 1) 
 k = 0 
 for user, n in sorted(activity.items(), \ 
 key=itemgetter(1), reverse=False): 
 c = int((k * 5) / (1.0 * len(activity))) 
 self.group[user] = c 
 k += 1 
 def GetGroup(self, uid): 
 if uid not in self.group: 
 return -1 
 else: 
 return self.group[uid]
 class ItemPopularityCluster(Cluster): 
 def __init__(self, records): 
 Cluster.__init__(self, records) 
 popularity = dict() 
 for r in records: 
 if r.test != 0: 
 continue 
 basic.AddToDict(popularity, r.item, 1) 
 k = 0 
 for item, n in sorted(popularity.items(), \ 
 key=itemgetter(1), reverse=False): 
 c = int((k * 5) / (1.0 * len(popularity))) 
 self.group[item] = c 
 k += 1 
 def GetGroup(self, item): 
 if item not in self.group: 
 return -1 
 else: 
 return self.group[item] 
class UserVoteCluster(Cluster): 
 def __init__(self, records): 
 Cluster.__init__(self, records) 
 vote = dict() 
 count = dict() 
 for r in records: 
 if r.test != 0: 
 continue 
 basic.AddToDict(vote, r.user, r.vote) 
 basic.AddToDict(count, r.user, 1) 
 k = 0 
 for user, v in vote.items(): 
 ave = v / (count[user] * 1.0) 
 c = int(ave * 2) 
 self.group[user] = c 
 def GetGroup(self, uid): 
 if uid not in self.group: 
 return -1 
 else: 
 return self.group[uid] 
class ItemVoteCluster(Cluster): 
 def __init__(self, records): 
 Cluster.__init__(self, records) 
 vote = dict() 
 count = dict() 
 for r in records: 
 if r.test != 0: 
 continue 
 basic.AddToDict(vote, r.item, r.vote) 
 basic.AddToDict(count, r.item, 1) 
 k = 0
 for item, v in vote.items(): 
 ave = v / (count[item] * 1.0) 
 c = int(ave * 2) 
 self.group[item] = c 
 def GetGroup(self, item): 
 if item not in self.group: 
 return -1 
 else: 
 return self.group[item]
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

8.2.2 基于邻域的方法

基于用户的邻域算法和基于物品的邻域算法都可以应用到评分预测中。基于用户的邻域算法认为预测一个用户对一个物品的评分，需要参考和这个用户兴趣相似的用户对该物品的评分，即:

这里，S(u, K)是和用户u兴趣最相似的K个用户的集合，N(i)是对物品i评过分的用户集合，rvi是用户v对物品i的评分，rv 是用户v对他评过分的所有物品评分的平均值。用户之间的相似度 wuv可以通过皮尔逊系数计算：

下面的Python代码实现了用户相似度的计算和最终的预测函数：

def UserSimilarity(records): 
 item_users = dict() 
 ave_vote = dict() 
 activity = dict() 
 for r in records: 
 addToMat(item_users, r.item, r.user, r.value) 
 addToVec(ave_vote, r.user, r.value) 
 addToVec(activity, r.user, 1) 
 ave_vote = {x:y/activity[x] for x,y in ave_vote.items()} 
 nu = dict() 
 W = dict() 
 for i,ri in item_users.items(): 
 for u,rui in ri.items(): 
 addToVec(nu, u, (rui - ave_vote[u])*(rui - ave_vote[u])) 
 for v,rvi in ri.items(): 
 if u == v: 
 continue 
 addToMat(W, u, v, \ 
 (rui - ave_vote[u])*(rvi - ave_vote[v])) 
 for u in W: 
 W[u] = {x:y/math.sqrt(nu[x]*nu[u]) for x,y in W[u].items()} 
 return W 
def PredictAll(records, test, ave_vote, W, K): 
 user_items = dict() 
 for r in records: 
 addToMat(user_items, r.user, r.item, r.value) 
 for r in test: 
 r.predict = 0 
 norm = 0 
 for v,wuv in sorted(W[r.user].items(), \ 
 key=itemgetter(1), reverse=True)[0:K]: 
 if r.item in user_items[v]: 
 rvi = user_items[v][r.item] 
 r.predict += wuv * (rvi - ave_vote[v]) 
 norm += abs(wuv) 
 if norm > 0: 
 r.predict /= norm 
 r.predict += ave_vote[r.user]
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
26
27
28
29
30
31
32
33
34
35
36
37
38

基于物品的邻域算法在预测用户u对物品i的评分时，会参考用户u对和物品i相似的其他物品的评分，即：

这里，S(i, K)是和i最相似的物品集合，N(u)是用户u评过分的物品集合， wij 是物品之间的相似度， ri 是物品i的平均分。对于如何计算物品的相似度，Badrul Sarwar等在论文①里做了详细的研究，文章比较了3种主要的相似度。
第一种是普通的余弦相似度（cosine similarity）：

第二种是皮尔逊系数（pearson correlation)：

第三种被Sarwar称为修正的余弦相似度（adjust cosine similarity）

Sarwar利用MovieLens最小的数据集对3种相似度进行了对比①，并将MAE作为评测指标。实验结果表明利用修正后的余弦相似度进行评分预测可以获得最优的MAE。不过需要说明的是，在一个数据集上的实验并不意味着在其他数据集上也能获得相同的结果。

8.2.3 隐语义模型与矩阵分解模型

最近这几年做机器学习和数据挖掘研究的人经常会看到下面的各种名词，即隐含类别模型（Latent Class Model）、隐语义模型（Latent Factor Model）、pLSA、LDA、Topic Model、Matrix Factorization、Factorized Model。

这些名词在本质上应该是同一种思想体系的不同扩展。在推荐系统领域，提的最多的就是潜语义模型和矩阵分解模型。其实，这两个名词说的是一回事，就是如何通过降维的方法将评分矩阵补全。

用户的评分行为可以表示成一个评分矩阵R，其中R[u][i]就是用户u对物品i的评分。但是，用户不会对所有的物品评分，所以这个矩阵里有很多元素都是空的，这些空的元素称为缺失值（missing value）。因此，评分预测从某种意义上说就是填空，如果一个用户对一个物品没有评过分，那么推荐系统就要预测这个用户是否是否会对这个物品评分以及会评几分。
1. 传统的SVD分解
对于如何补全一个矩阵，历史上有过很多的研究。一个空的矩阵有很多种补全方法，而我们要找的是一种对矩阵扰动最小的补全方法。那么什么才算是对矩阵扰动最小呢？一般认为，如果补全后矩阵的特征值和补全之前矩阵的特征值相差不大，就算是扰动比较小。所以，最早的矩阵分解模型就是从数学上的SVD（奇异值分解）开始的。给定m个用户和n个物品，和用户对物品的评分矩阵 R 首先需要对评分矩阵中的缺失值进行简单地补全，比如用全局平均值，或者用户/物品平均值补全，得到补全后的矩阵R’。接着，可以用SVD分解将R’分解成如下形式：

其中U ，V 是两个正交矩阵， S 是对角阵，对角线上的每一个元素都是矩阵的奇异值。为了对R’进行降维，可以取最大的f个奇异值组成对角矩阵Sf，并且找到这f个奇异值中每个值在U、V矩阵中对应的行和列，得到Uf、Vf，从而可以得到一个降维后的评分矩阵：

其中， R\ 就是用户u对物品i评分的预测值。
SVD分解是早期推荐系统研究常用的矩阵分解方法，不过该方法具有以下缺点，因此很难在实际系统中应用。
 该方法首先需要用一个简单的方法补全稀疏评分矩阵。一般来说，推荐系统中的评分矩阵是非常稀疏的，一般都有95%以上的元素是缺失的。而一旦补全，评分矩阵就会变成一个稠密矩阵，从而使评分矩阵的存储需要非常大的空间，这种空间的需求在实际系统中是不可能接受的。

 该方法依赖的SVD分解方法的计算复杂度很高，特别是在稠密的大规模矩阵上更是非常慢。一般来说，这里的SVD分解用于1000维以上的矩阵就已经非常慢了，而实际系统动辄是上千万的用户和几百万的物品，所以这一方法无法使用。如果仔细研究关于这一方法的论文可以发现，实验都是在几百个用户、几百个物品的数据集上进行的

2. Simon Funk的SVD分解
正是由于上面的两个缺点，SVD分解算法提出几年后在推荐系统领域都没有得到广泛的关注。直到2006年Netflix Prize开始后，Simon Funk在博客上公布了一个算法①（称为Funk-SVD），一下子引爆了学术界对矩阵分解类方法的关注。而且，Simon Funk的博客也成为了很多学术论文经常引用的对象。Simon Funk提出的矩阵分解方法后来被Netflix Prize的冠军Koren称为Latent Factor Model（简称为LFM）。

第3章曾经简单介绍过LFM在TopN推荐中的应用，因此这里我们不再详细介绍这一方面背后的思想。从矩阵分解的角度说，如果我们将评分矩阵R分解为两个低维矩阵相乘：

其中 P和 Q 是两个降维后的矩阵。那么，对于用户u对物品i的评分的预测值
Rˆ（u,i) ，可以通过如下公式计算：

其中 Puf，Qi f 。那么，Simon Funk的思想很简单：可以直接通过训练集中的观察值利用最小化RMSE学习P、Q矩阵。
Simon Funk认为，既然我们用RMSE作为评测指标，那么如果能找到合适的P、Q来最小化训练集的预测误差，那么应该也能最小化测试集的预测误差。因此，Simon Funk定义损失函数为：

直接优化上面的损失函数可能会导致学习的过拟合，因此还需要加入防止过拟合项，其中λ 是正则化参数，从而得到

要最小化上面的损失函数，我们可以利用随机梯度下降法。该算法是最优化理论里最基础的优化算法，它首先通过求参数的偏导数找到最速下降方向，然后通过迭代法不断地优化参数。下面我们将介绍优化方法的数学推导

上面定义的损失函数里有两组参数（puf和qif），最速下降法需要首先对它们分别求偏导数，可以得到：

然后，根据随机梯度下降法，需要将参数沿着最速下降方向向前推进，因此可以得到如下递推公式：

其中，α 是学习速率（learning rate），它的取值需要通过反复实验获得。
下面的代码实现了学习LFM模型时的迭代过程。在LearningLFM函数中，输入train是训练集中的用户评分记录，F是隐类的格式，n是迭代次数。

def LearningLFM(train, F, n, alpha, lambda): 
 [p,q] = InitLFM(train, F) 
 for step in range(0, n): 
 for u,i,rui in train.items(): 
 pui = Predict(u, i, p, q) 
 eui = rui - pui 
 for f in range(0,F): 
 p[u][k] += alpha * (q[i][k] * eui - lambda * p[u][k]) 
 q[i][k] += alpha * (p[u][k] * eui - lambda * q[i][k]) 
 alpha *= 0.9 
 return list(p, q)
1
2
3
4
5
6
7
8
9
10
11

如上面的代码所示，LearningLFM主要包括两步。首先，需要对P、Q矩阵进行初始化，然后需要通过随机梯度下降法的迭代得到最终的P、Q矩阵。在迭代时，需要在每一步对学习参数α进行衰减(alpha *= 0.9)，这是随机梯度下降法算法要求的，其目的是使算法尽快收敛。如果形象一点说就是，如果需要在一个区域找到极值，一开始可能需要大范围搜索，但随着搜索的进行，搜索范围会逐渐缩小。

初始化P、Q矩阵的方法很多，一般都是将这两个矩阵用随机数填充，但随机数的大小还是有讲究的，根据经验，随机数需要和1/sqrt(F)成正比。下面的代码实现了初始化功能。

def InitLFM(train, F): 
 p = dict() 
 q = dict() 
 for u, i, rui in train.items(): 
 if u not in p: 
 p[u] = [random.random()/math.sqrt(F) \ 
 for x in range(0,F)] 
 if i not in q: 
 q[i] = [random.random()/math.sqrt(F) \ 
 for x in range(0,F)] 
 return list(p, q)
1
2
3
4
5
6
7
8
9
10
11

而预测用户u对物品i的评分可以通过如下代码实现：

def Predict(u, i, p, q): 
 return sum(p[u][f] * q[i][f] for f in range(0,len(p[u]))
1
2

LFM提出之后获得了很大的成功，后来很多著名的模型都是通过对LFM修修补补获得的，下面的各节将分别介绍一下改进LFM的各种方法。这些改进有些是对模型的改进，有些是将新的数据引入到模型当中。

3. 加入偏置项后的LFM
再次回顾一下上一节提出的LFM预测公式：

这个预测公式通过隐类将用户和物品联系在了一起。但是，实际情况下，一个评分系统有些固有属性和用户物品无关，而用户也有些属性和物品无关，物品也有些属性和用户无关。因此，Netflix Prize中提出了另一种LFM，其预测公式如下：

这个预测公式中加入了3项 μ 、bu 、bi 。本章将这个模型称为BiasSVD。这个模型中新增加的三项的作用如下。
 μ 训练集中所有记录的评分的全局平均数。在不同网站中，因为网站定位和销售的物品不同，网站的整体评分分布也会显示出一些差异。比如有些网站中的用户就是喜欢打高分，而另一些网站的用户就是喜欢打低分。而全局平均数可以表示网站本身对用户评分的影响。
 bu 用户偏置（user bias）项。这一项表示了用户的评分习惯中和物品没有关系的那种因素。比如有些用户就是比较苛刻，对什么东西要求都很高，那么他的评分就会偏低，而有些用户比较宽容，对什么东西都觉得不错，那么他的评分就会偏高。
 bi 物品偏置（item bias）项。这一项表示了物品接受的评分中和用户没有什么关系的因素。比如有些物品本身质量就很高，因此获得的评分相对都比较高，而有些物品本身质量很差，因此获得的评分相对都会比较低。

增加的3个参数中，只有bu 、bi 是要通过机器学习训练出来的。同样可以求导，然后用梯度下降法求解这两个参数，我们对LearningLFM稍做修改，就可以支持BiasLFM模型：

def LearningBiasLFM(train, F, n, alpha, lambda, mu): 
 [bu, bi, p,q] = InitLFM(train, F) 
 for step in range(0, n): 
 for u,i,rui in train.items(): 
 pui = Predict(u, i, p, q, bu, bi, mu) 
 eui = rui - pui 
 bu[u] += alpha * (eui - lambda * bu[u]) 
 bi[i] += alpha * (eui - lambda * bi[i]) 
 for f in range(0,F): 
 p[u][k] += alpha * (q[i][k] * eui - lambda * p[u][k]) 
 q[i][k] += alpha * (p[u][k] * eui - lambda * q[i][k]) 
 alpha *= 0.9 
 return list(bu, bi, p, q)
1
2
3
4
5
6
7
8
9
10
11
12
13

而bu 、bi 在一开始只要初始化成全0的向量。

def InitBiasLFM(train, F): 
 p = dict() 
 q = dict() 
 bu = dict() 
 bi = dict() 
 for u, i, rui in train.items(): 
 bu[u] = 0 
 bi[i] = 0 
 if u not in p: 
 p[u] = [random.random()/math.sqrt(F) for x in range(0,F)] 
 if i not in q: 
 q[i] = [random.random()/math.sqrt(F) for x in range(0,F)] return 
list(p, q) 
def Predict(u, i, p, q, bu, bi, mu): 
 ret = mu + bu[u] + bi[i] 
 ret += sum(p[u][f] * q[i][f] for f in range(0,len(p[u])) 
 return ret
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4. 考虑邻域影响的LFM
前面的LFM模型中并没有显式地考虑用户的历史行为对用户评分预测的影响。为此，Koren在Netflix Prize比赛中提出了一个模型①，将用户历史评分的物品加入到了LFM模型中，Koren将该模型称为SVD++。

在介绍SVD++之前，我们首先讨论一下如何将基于邻域的方法也像LFM那样设计成一个可以学习的模型。其实很简单，我们可以将ItemCF的预测算法改成如下方式：

这里， wij 不再是根据ItemCF算法计算出的物品相似度矩阵，而是一个和P、Q一样的参数，它可以通过优化如下的损失函数进行优化：

不过，这个模型有一个缺点，就是w将是一个比较稠密的矩阵，存储它需要比较大的空间。此外，如果有n个物品，那么该模型的参数个数就是n2个，这个参数个数比较大，容易造成结果的过拟合。因此，Koren提出应该对w矩阵也进行分解，将参数个数降低到2nF个，模型如下：

这里， xi 、 y j 是两个F维的向量。由此可见，该模型用 T xi j y 代替了 wij ，从而大大降低了参数的数量和存储空间。
再进一步，我们可以将前面的LFM和上面的模型相加，从而得到如下模型：

Koren又提出，为了不增加太多参数造成过拟合，可以令x = q，从而得到最终的SVD++模型：

通过将损失函数对各个参数求偏导数，我们也可以轻松推导出迭代公式。这里，我们给出了SVD++模型训练的实现代码，如下所示。

def LearningBiasLFM(train_ui, F, n, alpha, lambda, mu): 
 [bu, bi, p, q, y] = InitLFM(train, F) 
 z = dict() 
 for step in range(0, n): 
 for u,items in train_ui.items(): 
 z[u] = p[u] 
 ru = 1 / math.sqrt(1.0 * len(items)) 
 for i,rui in items items(): 
 for f in range(0,F): 
 z[u][f] += y[i][f] * ru 
 sum = [0 for i in range(0,F)] 
 for i,rui in items items(): 
 pui = Predict() 
 eui = rui - pui 
 bu[u] += alpha * (eui - lambda * bu[u]) 
 bi[i] += alpha * (eui - lambda * bi[i]) 
 for f in range(0,F): 
 sum[k] += q[i][k] * eui * ru 
 p[u][k] += alpha * (q[i][k] * eui \
 - lambda * p[u][k]) 
 q[i][k] += alpha * ((z[u][k] + p[u][k]) * eui \ 
 - lambda * q[i][k]) 
 for i,rui in items items(): 
 for f in range(0,F): 
 y[i][f] += alpha * (sum[f] - lambda * y[i][f]) 
 alpha *= 0.9 
 return list(bu, bi, p, q)
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
26
27

8.2.4 加入时间信息

无论是MovieLens数据集还是Netflix Prize数据集都包含时间信息，对于用户每次的评分行为，都给出了行为发生的时间。因此，在Netflix Prize比赛期间，很多研究人员提出了利用时间信息降低预测误差的方法。

利用时间信息的方法也主要分成两种，一种是将时间信息应用到基于邻域的模型中，另一种是将时间信息应用到矩阵分解模型中。下面将分别介绍这两种算法。
1. 基于邻域的模型融合时间信息
因为Netflix Prize数据集中用户数目太大，所以基于用户的邻域模型很少被使用，主要是因为存储用户相似度矩阵非常困难。因此，本节主要讨论如何将时间信息融合到基于物品的邻域模型中。

Netflix Prize的参赛队伍BigChaos在技术报告中提到了一种融入时间信息的基于邻域的模型，本节将这个模型称为TItemCF。该算法通过如下公式预测用户在某一个时刻会给物品什么评分：

这里，△t=tui-tuj是用户u对物品i和物品j评分的时间差，wij 是物品i和j的相似度，f(wij,△t)是一个考虑了时间衰减后的相似度函数，它的主要目的是提高用户最近的评分行为对推荐结果的影响，BigChaos在模型中采用了如下的 f ：

这里， σ( x) 是sigmoid函数，它的目的是将相似度压缩到（0，1）区间中。从上面的定义可以发现，随着 △t 增加，f(wij,△t) 会越来越小，也就是说用户很久之前的行为对预测用户当前评分的影响越来越小。

2. 基于矩阵分解的模型融合时间信息
在引入时间信息后，用户评分矩阵不再是一个二维矩阵，而是变成了一个三维矩阵。不过，我们可以仿照分解二维矩阵的方式对三维矩阵进行分解①。回顾一下前面的BiasSVD模型：

这里，μ 可以看做对二维矩阵的零维分解，bu 、bi 可以看做对二维矩阵的一维分解，而 PQ可以看做对二维矩阵的二维分解。仿照这种分解，我们可以将用户—物品—时间三维矩阵如下分解：

这里 bt 建模了系统整体平均分随时间变化的效应， xu yt 建模了用户平均分随时间变化的效应， si t z 建模了物品平均分随时间变化的效应，建模了用户兴趣随时间影响的效应。这个模型也可以很容易地利用前面提出的随机梯度下降法进行训练。本章将这个模型记为TSVD。

Koren在SVD++模型的基础上也引入了时间效应②，回顾一下SVD++模型：

我们可以对这个模型做如下改进以融合时间信息：

这里，tu 是用户所有评分的平均时间。 period(t) 考虑了季节效应，可以定义为时刻t所在的月份。该模型同样可以通过随机梯度下降法进行优化。

8.2.5 模型融合

Netflix Prize的最终获胜队伍通过融合上百个模型的结果才取得了最终的成功。由此可见模型融合对提高评分预测的精度至关重要。本节讨论模型融合的两种不同技术。

1. 模型级联融合
   假设已经有一个预测器 rˆ(k) ，对于每个用户—物品对(u, i)都给出预测值，那么可以在这个预测器的基础上设计下一个预测器 rˆ( k+1) 来最小化损失函数：

由上面的描述可以发现，级联融合很像Adaboost算法。和Adaboost算法类似，该方法每次产生一个新模型，按照一定的参数加到旧模型上去，从而使训练集误差最小化。不同的是，这里每次生成新模型时并不对样本集采样，针对那些预测错的样本，而是每次都还是利用全样本集进行预测，但每次使用的模型都有区别。

一般来说，级联融合的方法都用于简单的预测器，比如前面提到的平均值预测器。下面的Python代码实现了利用平均值预测器进行级联融合的方法。

def Predict(train, test, alpha): 
 total = dict() 
 count = dict() 
 for record in train: 
 gu = GetUserGroup(record.user) 
 gi = GetItemGroup(record.item) 
 AddToMat(total, gu, gi, record.vote - record.predict) 
 AddToMat(count, gu, gi, 1) 
 for record in test: 
 gu = GetUserGroup(record.user) 
 gi = GetUserGroup(record.item) 
 average = total[gu][gi] / (1.0 * count[gu][gi] + alpha) 
 record.predict += average
1
2
3
4
5
6
7
8
9
10
11
12
13

表8-3展示了MovieLens数据集上对平均值方法采用级联融合后的RMSE。如果和表8-2的结果对比就可以发现，采用级联融合后，测试集的RMSE从0.9342下降到了0.9202。由此可见，即使是利用简单的算法进行级联融合，也能得到比较低的评分预测误差。

2. 模型加权融合
假设我们有K个不同的预测器，本节主要讨论如何将它们融合起来获得最低的预测误差。
最简单的融合算法就是线性融合，即最终的预测器 rˆ 是这K个预测器的线性加权：

一般来说，评分预测问题的解决需要在训练集上训练K个不同的预测器，然后在测试集上作出预测。但是，如果我们继续在训练集上融合K个预测器，得到线性加权系数，就会造成过拟合的问题。因此，在模型融合时一般采用如下方法。

 假设数据集已经被分为了训练集A和测试集B，那么首先需要将训练集A按照相同的分割方法分为A1和A2，其中A2的生成方法和B的生成方法一致，且大小相似。
 在A1上训练K个不同的预测器，在A2上作出预测。因为我们知道A2上的真实评分值，所以可以在A2上利用最小二乘法①计算出线性融合系数k 。  在A上训练K个不同的预测器，在B上作出预测，并且将这K个预测器在B上的预测结果按照已经得到的线性融合系数加权融合，以得到最终的预测结果。除了线性融合，还有很多复杂的融合方法，比如利用人工神经网络的融合算法。其实，模型融合问题就是一个典型的回归问题，因此所有的回归算法都可以用于模型融合。

8.2.6 Netflix Prize的相关实验结果

Netflix Prize比赛的３年时间里，很多研究人员在同一个数据集上重复实验了前面几节提到的各种算法。因此，本章我们引用他们的实验结果对比各个算法的性能。Netflix Prize采用RMSE评测预测准确度，因此本节的评测指标也是RMSE，具体见表8-4。