推荐系统实践读书笔记（八）

第8章 评分预测问题

之前讨论的都是TopN推荐，但同样评分预测问题也是推荐系统研究的核心。评分预测问题就是如何通过已知的用户历史评分记录预测未知的用户评分记录。

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

8.1 离线实验方法

评分预测问题基本都通过离线实验进行研究。在给定用户评分数据集后，研究人员会将数据集按照一定的方式分成训练集和测试集，然后根据测试集建立用户兴趣模型来预测测试集中的用户评分。对于测试集中的一对用户和物品$(u, i)$，用户$u$对物品$i$的真实评分$r_{ui}$，而推荐算法预测的用户$u$对物品$i$的评分为$\hat r_{ui}$，那么一般可以用均方根误差RMSE度量预测的精度：
$$
RMSE = \frac{\sqrt{\sum_{(u,i)\in T}(r_{ui} - \hat r_{ui})^2}}{\vert Test \vert}
$$
评分预测的目的就是找到最好的模型最小化测试集的RMSE。

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

8.2 评分预测算法

本节从简单到复杂地介绍具有代表性的算法，并给出它们在Netflix数据集上的效果。

8.2.1 平均值

最简单的评分预测算法是利用平均值预测用户对物品的评分的。下面各节分别介绍各种不同的平均值。

1.全局平均值

在平均值里最简单的是全局平均值。它的定义为训练集中所有评分记录的评分平均值：
$$
\mu = \frac{\sum_{(u,i) \in Train}r_{ui}}{\sum_{(u,i) \in Train }1}
$$
而最终的预测函数可以直接定义为：
$$
\hat r_{ui} = \mu
$$

2.用户评分平均值

用户$u$的评分平均值$\bar r_u$定义为用户$u$在训练集中所有评分的平均值：
$$
\bar r_u = \frac{\sum_{i \in N(u)}r_{ui}}{\sum_{i \in N(u)}1}
$$

而最终的预测函数可以定义为：
$$
\hat r_{ui} = \bar r_{u}
$$

3.物品评分平均值

物品$i$的评分平均值$\bar r_i$定义为物品$i$在训练集中接收的所有评分的平均值：
$$
\bar r_i = \frac{\sum_{u \in N(i)}r_{ui}}{\sum_{u \in N(i)}1}
$$
而最终的预测函数可以定义为：
$$
\hat r_{ui} = \bar r_i
$$

4.用户分类对物品分类的平均值(类类平均值)

假设有两个分类函数，一个是用户分类函数$\phi$，一个是物品分类函数$\varphi$。$\phi(u)$定义了用户$u$所属的类，$\varphi(u)$定义了物品$i$所属的类。那么，我们可以利用训练集中同类用户对同类物品评分的平均值预测用户对物品的评分，即：
$$
\hat r_{ui} = \frac{\sum_{(v,j)\in Train, \phi(u)=\phi(v),\varphi(i)=\varphi(j)} r_{vj}}{\sum_{(v,j)\in Train, \phi(u)=\phi(v),\varphi(i)=\varphi(j)}1}
$$
前面提出的全局平均值，用户评分平均值和物品评分平均值都是类类平均值的一种特例。

• 如果定义$\phi(u)=0,\varphi(i)=0$，那么$\hat r_{ui}$就是全局平均值。
• 如果定义$\phi(u) = u,\varphi(i) = 0$，那么$\hat r_{ui}$就是用户评分平均值。
• 如果定义$\phi(u) = 0,\varphi(i) = i$，那么$\hat 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

在这段代码中，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类型，那么最终的预测函数给出的就是物品平均值。在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]

8.2.2 基于邻域的方法

基于用户的邻域算法和基于物品的邻域算法都可以应用到评分预测中。基于用户的邻域算法认为预测一个用户对一个物品的评分，需要参考和这个用户兴趣相似的用户对该物品的评分，即：
$$
\hat r_{ui} = \bar r_{u} + \frac{\sum_{v \in S(u,K) \cap N(i)}w_{uv}(r_{vi} - \bar r_v)}{\sum_{v \in S(u,K) \cap N(i)}\vert w_{uv} \vert}
$$
$S(u,K)$是和用户$u$兴趣最相似的$K$个用户的集合，$N(i)$是对物品$i$评过分的用户集合，$r_{vi}$是用户$v$对物品$i$的评分，$\bar r_v$是用户$v$对他评过分的所有物品评分的平均值。用户之间的相似度$w_{uv}$可以通过皮尔逊系数计算：
$$
w_{uv} = \frac{\sum_{i \in I}(r_{ui}-\bar r_u)\cdot (r_{vi} - \bar r_v)}{\sqrt{\sum_{i \in I} (r_{ui} - \bar r_u)^2 \sum_{i \in I} (r_{vi} - \bar r_v)^2}}
$$
下面的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]

基于物品的邻域算法在预测用户$u$对物品$i$的评分时，会参考用户u对和物品i相似的其他物品的评分，即：
$$
\hat r_{ui} = \bar r_i + \frac{\sum_{j \in S(u,K) \cap N(u)}w_{ij} (r_{uj} - \bar r_i)}{\sum_{j \in S(u,K) \cap N(u)} \vert w_{ij} \vert}
$$
$S(i,K)$是和$i$最相似的物品集合，$N(u)$是用户$u$评过分的物品集合，$w_{ij}$是物品之间的相似度，$\bar r_i$是物品$i$的平均分。对于如何计算物品的相似度，Badrul Sarwar等在论文(参见Badrul Sarwar、George Karypis、Joseph Konstan和John Riedl的“Item-based Collaborative Filtering Recommendation Algorithms”（ACM 2001 Article，2001）)里做了详细的研究，文章比较了3种主要的相似度。

第一种是普通的余弦相似度(cosine similarity):
$$
w_{ij} = \frac{\sum_{u \in U} r_{ui} \cdot r_{uj}}{\sqrt{\sum_{u \in U} r_{ui}^2 \sum_{u \in U} r_{uj}^2}}
$$
第二种是皮尔逊系数(pearson correlation):
$$
w_{ij} = \frac{\sum_{u \in U}(r_{ui}-\bar r_i)\cdot (r_{uj} - \bar r_j)}{\sqrt{\sum_{u \in U} (r_{ui} - \bar r_i)^2 \sum_{u \in U} (r_{uj} - \bar r_j)^2}}
$$
第三种是被Sarwar称为修正的余弦相似度(adjust cosine similarity):
$$
w_{ij} = \frac{\sum_{u \in U}(r_{ui}-\bar r_u)\cdot (r_{uj} - \bar r_u)}{\sqrt{\sum_{u \in U} (r_{ui} - \bar r_u)^2 \sum_{u \in U} (r_{uj} - \bar r_u)^2}}
$$
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(奇异值分解)开始的(参见Daniel Billsus和Michael J. Pazzani的“Learning Collaborative Information Filters”（1998）)。给定$m$个用户和$n$个物品，和用户对物品的评分矩阵$\mathbb R^{m \times n}$。首先需要对评分矩阵中的缺失值进行简单地补全，比如用全局平均值，或者用户/物品平均值补全，得到补全后的矩阵$R’$。接着，可以用SVD分解将$R’$分解成如下形式：
$$
R’ = U^TSV
$$
其中$U \in \mathbb R^{k \times m}$，$V \in \mathbb R^{k \times m}$是两个正交矩阵，$S \in \mathbb R^{k \times k}$是对角阵，对角线上的每一个元素都是矩阵的奇异值。为了对$R’$进行降维，可以取最大的$f$个奇异值组成对角矩阵$S_f$，并且找到这$f$个奇异值中每个值在$U$、$V$矩阵中对应的行和列，得到$U_f$、$V_f$，从而可以得到一个降维后的评分矩阵：
$$
R_f’ = U^T_f S_f V_f
$$
其中，$R_(u, i )$就是用户$u$对物品$i$评分的预测值。

SVD分解是早期推荐系统研究常用的矩阵分解方法，不过该方法具有以下缺点，因此很难在实际系统中应用。

• 该方法首先需要用一个简单的方法补全稀疏评分矩阵。一般来说，推荐系统中的评分矩阵是非常稀疏的，一般都有95%以上的元素是缺失的。而一旦补全，评分矩阵就会变成一个稠密矩阵，从而使评分矩阵的存储需要非常大的空间，这种空间的需求在实际系统中是不可能接受的。
• 该方法依赖的SVD分解方法的计算复杂度很高，特别是在稠密的大规模矩阵上更是非常慢。

2.Simon Funk的SVD分解

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

第3章曾经简单介绍过LFM在TopN推荐中的应用，因此这里不再详细介绍这一方面背后的思想。从矩阵分解的角度说，如果将评分矩阵$R$分解为两个低维矩阵相乘：
$$
\hat R = P^TQ
$$
其中$P \in \mathbb R^{f \times m}$和$Q \in \mathbb R^{f \times n}$是两个降维后的矩阵。 那么，对于用户$u$对物品$i$的评分的预测值$\hat R(u,i) = \hat r_{ui}$，可以通过如下公式计算：
$$
\hat r_{ui} = \sum_f{p_{uf} q_{if}}
$$
其中$p_{uf} = P(u,f)$，$q_{if} = Q(i,f) $。那么，Simon Funk的思想很简单：可以直接通过训练集中的观察值利用最小化RMSE学习$P$、$Q$矩阵。

Simon Funk认为，既然用RMSE作为评测指标，那么如果能找到合适的$P$、$Q$来最小化训练集的预测误差，那么应该也能最小化测试集的预测误差。因此，Simon Funk定义损失函数为：
$$
C(p,q) = \sum_{(u,i) \in Train}(r_{ui} - \hat r_{ui})^2 = \sum_{(u,i) \in Train}(r_{ui} - \sum_{f = 1}^F p_{uf}q_{if})^2
$$
直接优化上面的损失函数可能会导致学习的过拟合， 因此还需要加入防止过拟合项$\lambda(\Vert p_u \Vert^2 + \Vert q_i \Vert^2)$，其中$\lambda$是正则化参数，从而得到：
$$
C(p,q) = \sum_{(u,i) \in Train}(r_{ui} - \sum_{f = 1}^F p_{uf}q_{if})^2 + \lambda(\Vert p_u \Vert^2 + \Vert q_i \Vert^2)
$$
要最小化上面的损失函数，可以利用随机梯度下降法(参见http://en.wikipedia.org/wiki/Stochastic_gradient_descent )。该算法是最优化理论里最基础的优化算法，它首先通过求参数的偏导数找到最速下降方向，然后通过迭代法不断地优化参数。下面介绍优化方法的数学推导。

上面定义的损失函数里有两组参数$p_{uf}$和$q_{if}$，最速下降法需要首先对它们分别求偏导数，可以得到：
$$
\frac{\partial C}{\partial p_{uf}} = -2q_{ik} + 2\lambda p_{uk}
$$

$$
\frac{\partial C}{\partial p_{if}} = -2p_{uk} + 2\lambda q_{ik}
$$

然后，根据随机梯度下降法，需要将参数沿着最速下降方向向前推进，因此可以得到如下递推公式：
$$
p_{uf} = p_{uf} + \alpha(q_{ik} - \lambda p_{uk}) \\
q_{if} = q_{if} + \alpha(p_{uk} - \lambda q_{ik})
$$
其中，$\alpha$是学习速率(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)

如上面的代码所示，LearningLFM主要包括两步。(1)需要对P、Q矩阵进行初始化，(2)需要通过随机梯度下降法的迭代得到最终的$P$、$Q$矩阵。在迭代时，需要在每一步对学习参数$\alpha$进行衰减(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)

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

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

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

3.加入偏置项后的LFM

上节提出的LFM预测公式通过隐类将用户和物品联系在一起。但是，实际情况下，一个评分系统有些固有属性和用户物品无关，而用户也有些属性和物品无关，物品也有些属性和用户无关。因此， Netflix Prize中提出了另一种LFM，其预测公式如下：
$$
\hat r_{ui} = \mu + b_u + b_i + p_u^T \cdot q_i
$$
相比上节的LFM预测公式增加了3项$\mu$、$b_u$、$b_i$。本章将这个模型称为BiasSVD。新增三项的作用如下：

• $\mu$ 训练集中所有记录的评分的全局平均数。在不同网站中，因为网站定位和销售的物品不同，网站的整体评分分布也会显示出一些差异。比如有些网站中的用户就是喜欢打高分，而另一些网站的用户就是喜欢打低分。而全局平均数可以表示网站本身对用户评分的影响。
• $b_u$ 用户偏置(user bias)项。这一项表示了用户的评分习惯中和物品没有关系的那种因素。有的用户对什么都喜欢打高分或者低分。
• $b_i$ 物品偏置(item bias)项。这一项表示了物品接受的评分中和用户没有什么关系的因素。与用户偏置项同理。

增加的3个参数中，只有$b_u$、$b_i$是要通过机器学习训练出来的。同样可以求导，然后用梯度下降法求解这两个参数，只需对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)

而$b_u$、$b_i$在一开始只要初始化成全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

4.考虑邻域影响的LFM

前面的LFM模型中并没有显式地考虑用户的历史行为对用户评分预测的影响。为此，Koren在Netflix Prize比赛中提出了一个模型(参见Yehuda Koren的“Factor in the Neighbors: Scalable and Accurate Collaborative Filtering”（ACM 2010 Article，2010）)，将用户历史评分的物品加入到了LFM模型中，Koren将该模型称为SVD++。

为了将基于邻域的方法设计成一个像LFM那样可以学习的模型，可以将ItemCF的预测算法改成如下形式：
$$
\hat r_{ui} = \frac{1}{\sqrt{\vert N(u) \vert}} \sum_{j \in N(u)}w_{ij}
$$
公式中的$w_{ij}$不再是根据ItemCF算法计算出的物品相似度矩阵，而是一个和P、Q一样的参数，它通过优化如下的损失函数进行优化：
$$
C(w) = \sum_{(u,i) \in Train}(r_{ui} - \sum_{j \in N(u)} w_{ij}r_{uj})^2 + \lambda w_{ij}^2
$$
这个模型有一个缺点，就是$w$将是一个比较稠密的矩阵，存储它需要比较大的空间。此外，如果有$n$个物品，那么该模型的参数个数就是$n^2$个，这个参数个数比较大容易造成结果的过拟合。因此，Koren提出用该对$w$矩阵也进行分解，将参数个数降低到$2 \times n \times F$个，模型如下：
$$
\hat r_{ui} = \frac{1}{\sqrt{\vert N(u) \vert}} \sum_{j \in N(u)}x_i^Ty_j = \frac{1}{\sqrt{\vert N(u) \vert}}x_i^T \sum_{j \in N(u)}y_j
$$
$x_i$、$y_j$是两个$F$维的向量。由此可见，该模型用$x_i^Ty_j$代替了$w_{ij}$，从而大大降低了参数的数量和存储空间。

再进一步，可以将前面的LFM和上面的模型相加，从而得到如下模型：
$$
\hat r_{ui} = \mu + b_u + b_i + p_u^T \cdot q_i + \frac{1}{\sqrt{\vert N(u) \vert}}x_i^T \sum_{j \in N(u)}y_j
$$
Koren又提出为了不增加太多参数造成过拟合，可以令$x=q$，从而得到最终的SVD++模型：
$$
\hat r_{ui} = \mu + b_u + b_i + q_i^T \cdot (p_u + \frac{1}{\sqrt{\vert N(u) \vert}} \sum_{j \in N(u)}y_j)
$$
通过将损失函数对各个参数求偏导数，也可以轻松推导出迭代公式。下面给出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)

8.2.4 加入时间信息

利用时间信息的方法也主要分为两种，一种是将时间信息应用到基于邻域的模型中，另一种是将时间信息应用到矩阵分解模型中。

1.基于邻域的模型融合时间信息

由于实际生活中用户数目太大，所以基于用户的邻域模型很少被使用，主要是因为存储用户相似度矩阵非常困难。因此，本节主要讨论如何将时间信息融合到基于物品的邻域模型中。

Netflix Prize 的参赛队伍 BigChaos在技术报告中提到了一种融入时间信息的基于邻域的模型，本节将这个模型称为TItemCF。该算法通过如下公式预测用户在某一个时刻会给物品什么评分：
$$
\hat r_{uit} = \frac{\sum_{j \in N(u) \cap S(i,K)}f(w_{ij}, \Delta t)r_{uj}}{\sum_{j \in N(u) \cap S(i,K)}f(w_{ij},\Delta t)}
$$
$\Delta t = t_{ui} - t_{uj}$是用户$u$对物品$i$和物品$j$评分的时间差，$w_{ij}$是物品$i$和$j$的相似度，$f(w_{ij}, \Delta t)$是一个考虑了时间衰减后的相似度函数，它的主要目的是提高用户最近的评分行为对推荐结果的影响，BigChaos在模型中采用了如下的$f$：
$$
f(w_{ij},\Delta t) = \sigma(\delta \cdot w_{ij} \cdot \text{exp}(\frac{-|\Delta t|}{\beta}) + \gamma) \\
\sigma(x) = \frac{1}{1+ \text{exp}(-x)}
$$
$\sigma(x)$是sigmoid函数，它的目的是将相似度压缩到(0，1)区间中。从上面的定义可以发现，随着$\Delta t$增加，$f(w_{ij}, \Delta t)$会越来越小，也就是说用户很久之前的行为对预测用户当前评分的影响越来越小。

2.基于矩阵分解的模型融合时间信息

在引入时间信息后，用户评分矩阵不再是一个二维矩阵，而是变成了一个三维矩阵。不过可以仿照二维矩阵的方式对三维矩阵进行分解(参见Liang Xiang和Qing Yang的“Time-Dependent Models in Collaborative Filtering Based Recommender S WI-IAT 09)。回顾之前的BiasSVD模型：
$$
\hat r_{ui} = \mu + b_u + b_i + p^T_u \cdot q_i
$$
$\mu$可以看做对二维矩阵的零维分解，$b_u$、$b_i$可以看做对二维矩阵的一维分解，而$p^T_u \cdot q_i$则看做对二维矩阵的二维分解。仿照这种分解，将用户-物品-时间三维矩阵如下分解：
$$
\hat r_{uit} = \mu + b_u +b_i + b_t+ p^T_u \cdot q_i + x^T_u \cdot y_t + s^T_i z_t + \sum_f g_{u,f} h_{i,f}l_{t,f}
$$
这里$b_t$建模了系统整体平均分随时间变化的效应，$x^T_u \cdot y_t$建模了用户平均分随时间变化的效应，$s^T_i z_t$建模了物品平均分随时间变化的效应，而$\sum_f g_{u,f} h_{i,f}l_{t,f}$建模了用户兴趣随时间影响的效应。这个模型也可以很容易地利用前面提出的随机梯度下降法进行训练。本章将这个模型记为TSVD。

Koren在SVD++模型的基础上也引入了时间效应(参见Yehuda Koren的“Collaborative Filtering with temporal dynamics”（ACM 2009 Article，2009）)，回顾一下SVD++模型：
$$
\hat r_{ui} = \mu + b_u + b_i + q_i^T \cdot (p_u + \frac{1}{\sqrt{\vert N(u) \vert}} \sum_{j \in N(u)}y_j)
$$
对这个模型做如下改进以融合时间信息：
$$
\hat r_{ui} = \mu + b_u(t) + b_i(t) + q_i^T \cdot (p_u(t) + \frac{1}{\sqrt{\vert N(u) \vert}} \sum_{j \in N(u)}y_j) \\
b_u(t) = b_u + \alpha_u \cdot dev_u(t) + b_{ut} + b_{u,period(t)} \\
dev_u(t) = sign(t - t_u) \cdot \vert t - t_u \vert^\beta \\
b_i(t) = b_i + b_{it} + b_{i, period(t)}\\
p_{uf}(t) = p_{uf} + p_{utf}
$$
这里$t_u$是用户所有评分的平均时间。$period(t)$考虑了季节效应，可以定义为时刻$t$所在的月份。该模型同样可以通过随机梯度下降法进行优化。

8.2.5 模型融合

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

1.模型级联融合

假设已经有一个预测器$\hat r^{(k)}$，对于每个用户-物品对$(u,i)$都给出预测值，那么可以在这个预测器的基础上设计骗一个预测期$\hat r^{(k + 1)}$来最小化损失函数：

$$
C = \sum_{(u,i) \in Train}(r_{ui} - \hat r_{ui}^{(k)} - \hat r_{ui}^{(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

通过在MovieLens数据集计算对平均值方法采用级联融合后的RMSE，可见即使是利用简单的算法进行级联融合，也能得到比较低的评分预测误差。

2.模型加权融合

假设有$K$个不同的预测器${\hat r^{(1)}，\hat r^{(2)}，···，\hat r^{(K)}}，本节主要讨论如何将它们融合起来获得最低的预测误差。

最简单的融合算法就是线性融合，即最终的预测器$\hat r$是这$K$个预测器的线性加权：
$$
\hat r = \sum_{k = 1}^K \alpha_k \hat r^{(k)}
$$
一般来说，评分预测问题的解决需要在训练集上训练$K$个不同的预测器，然后在测试集上作出预测。但是，如果我们继续在训练集上融合$K$个预测器，得到线性加权系数，就会造成过拟合的问题。因此，在模型融合时一般采用如下方法。

• 假设数据集已经被分为了训练集A和测试集B，那么首先需要将训练集A按照相同的分割方法分为A1和A2，其中A2的生成方法和B的生成方法一致，且大小相似。
• 在A1上训练$K$个不同的预测器，在A2上作出预测。因为我们知道A2上的真实评分值，所以可以在A2上利用最小二乘法计算出线性融合系数$\alpha_k$。
• 在A上训练$K$个不同的预测器，在B上作出预测，并且将这$K$个预测器在B上的预测结果按照已经得到的线性融合系数加权融合，以得到最终的预测结果。

除了线性融合，还有很多复杂的融合方法，比如利用人工神经网络的融合算法。其实，模型融合问题就是一个典型的回归问题，因此所有的回归算法都可以用于模型融合。

8.2.6 Netflix Prize的相关实验结果

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