《推荐系统实践》第八章评分预测问题

2019-04-14 20:11发布生成海报

站内文章 / 模拟电子

15338 0

TopN推荐，即给定一个用户，如何给他生成一个长度为N的推荐列表，使该推荐列表能够尽量满足用户的兴趣和需求。TopN推荐非常接近于满足实际系统的需求，实际系统绝大多数情况下就是给用户提供一个包括N个物品的个性化推荐列表。评分预测问题最基本的数据集就是用户评分数据集。该数据集由用户评分记录组成，每一条评分记录是一个三元组(u,i, r)，表示用户u给物品i赋予了评分r，本章用 $r_{ui}$ 表示用户u对物品i的评分。因为用户不可能对所有物品都评分，因此评分预测问题就是如何通过已知的用户历史评分记录预测未知的用户评分记录。

8.1 离线实验方法

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

评分预测的目的就是找到最好的模型最小化测试集的RMSE。

8.2 评分预测算法

8.2.1 平均值

最简单的评分预测算法是利用平均值预测用户对物品的评分的。 1. 全局平均值 它的定义为训练集中所有评分记录的评分平均值：

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

2. 用户评分平均值 用户u的评分平均值 $overline{r_{u}}$ 定义为用户u在训练集中所有评分的平均值：

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

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

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

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

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

8.2.2 基于邻域的方法

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

S(u, K)是和用户u兴趣最相似的K个用户的集合，N(i)是对物品i评过分的用户集合， $r_{vi}$ 是用户v对物品i的评分， $overline{r_{v}}$ 是用户v对他评过分的所有物品评分的平均值。用户之间的相似度 $w_{uv}$ 可以通过皮尔逊系数计算：

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

S(i, K)是和i最相似的物品集合，N(u)是用户u评过分的物品集合， $w_{ij}$ 是物品之间的相似度， $overline{r_{i}}$ 是物品i的平均分。物品的相似度可以用以下方式进行计算。（参见Item-based Collaborative Filtering Recommendation Algorithms，http://files.grouplens.org/papers/www10_sarwar.pdf）第一种是普通的余弦相似度（cosine similarity）：

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

， $overline{r_{i}}$ 是物品i的平均分。第三种被Sarwar称为修正的余弦相似度（adjust cosine similarity）：

， $overline{r_{u}}$ 是用户u对他评过分的所有物品评分的平均值。实验结果表明利用修正后的余弦相似度进行评分预测可以获得最优的MAE。

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

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

其中 $Uin mathbb{R}^{k imes m}$ ， $Vin mathbb{R}^{k imes n}$ 是两个正交矩阵， $Sin mathbb{R}^{k imes k}$ 是对角阵，对角线上的每一个元素都是矩阵的奇异值。为了对R'进行降维，可以取最大的f个奇异值组成对角矩阵 $S_f$ ，并且找到这f个奇异值中每个值在U、V矩阵中对应的行和列，得到 $U_f$ 、 $V_f$ ，从而可以得到一个降维后的评分矩阵：

其中， ${R}'_f(u,i)$ 就是用户u对物品i评分的预测值。 SVD分解具有以下缺点，因此很难在实际系统中应用。  该方法首先需要用一个简单的方法补全稀疏评分矩阵。一般来说，推荐系统中的评分矩阵是非常稀疏的，一般都有95%以上的元素是缺失的。而一旦补全，评分矩阵就会变成一个稠密矩阵，从而使评分矩阵的存储需要非常大的空间，这种空间的需求在实际系统中是不可能接受的。
 该方法依赖的SVD分解方法的计算复杂度很高，特别是在稠密的大规模矩阵上更是非常慢。一般来说，这里的SVD分解用于1000维以上的矩阵就已经非常慢了. 2. Simon Funk的SVD分解 被Netflix Prize的冠军Koren称为Latent Factor Model（简称为LFM）。LFM在TopN推荐中的应用参见第二章。从矩阵分解的角度说，如果我们将评分矩阵R分解为两个低维矩阵相乘：

其中 $Pin mathbb{R}^{f imes m}$ 和 $Qin mathbb{R}^{f imes n}$ 是两个降维后的矩阵。那么，对于用户u对物品i的评分的预测值 $widehat{R}(u,i) = widehat{r}_{ui}$ ，可以通过如下公式计算：

其中 $p_{fu}=P(f,u)$ ， $q_{if}=Q(i,f)$ 。那么，Simon Funk的思想很简单：可以直接通过训练集中的观察值利用最小化RMSE学习P、Q矩阵。如果能找到合适的P、Q来最小化训练集的预测误差，那么应该也能最小化测试集的预测误差。因此，Simon Funk定义损失函数为：

直接优化上面的损失函数可能会导致学习的过拟合，因此还需要加入防止过拟合项 $lambda (||p_{u}||^{2}+||q_{i}||^{2})$ ，其中 $lambda$ 是正则化参数，从而得到：

要最小化上面的损失函数，我们可以利用随机梯度下降法。上面定义的损失函数里有两组参数（puf和qif），最速下降法需要首先对它们分别求偏导数，可以得到： $frac{partial C}{partial p_{uf}} = -2q_{if}*e_{ui} + 2lambda p_{uf}$ $frac{partial C}{partial q_{if}} = -2p_{uf}*e_{ui}+ 2lambda q_{if}$ 其中， $e_{ui} = r_{ui}-sum_{f=1}^{F}p_{uf}q_{if}$ 根据随机梯度下降法，需要将参数沿着最速下降方向向前推进，因此可以得到如下递推公式： $p_{uf} = p_{uf} + alpha (q_{if}*e_{ui} - lambda p_{uf})$ $q_{if} = q_{if} + alpha (p_{uf}*e_{ui} - lambda q_{if})$ 其中，α是学习速率（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][f] += alpha * (q[i][f] * eui - lambda * p[u][f])
                q[i][f] += alpha * (p[u][f] * eui - lambda * q[i][f])
         alpha *= 0.9
    return list(p, q)

LearningLFM主要包括两步。首先，需要对P、Q矩阵进行初始化，然后需要通过随机梯度下降法的迭代得到最终的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]))

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

这个预测公式中加入了3项 $mu$ 、 $b_u$ 、 $b_i$ 。本章将这个模型称为BiasSVD。这个模型中新增加的三项的作用如下。  $mu$ ：训练集中所有记录的评分的全局平均数。全局平均数可以表示网站本身对用户评分的影响。
 $b_u$ ：用户偏置（user bias）项。这一项表示了用户的评分习惯中和物品没有关系的那种因素。
 $b_i$ ：物品偏置（item bias）项。这一项表示了物品接受的评分中和用户没有什么关系的因素。增加的3个参数中，只有 $b_u$ 、 $b_i$ 是要通过机器学习训练出来的。同样可以求导，然后用梯度下降法求解这两个参数。此时损失函数为： $C(p,q) = sum_{(u,i)in Train} (r_{ui}-mu -b_u-b_i-sum_{f=1}^{F}p_{uf}q_{if})^{2}+lambda (||p_u||^2+||q_i||^2+||b_u||^2+||b_i||^2)$ 求偏导： $frac{partial C}{partial p_{uf}} = -2q_{if}*e_{ui} + 2lambda p_{uf}$ $frac{partial C}{partial q_{if}} = -2p_{uf}*e_{ui}+ 2lambda q_{if}$ $frac{partial C}{partial b_{u}} = -2e_{ui}+ 2lambda b_{u}$ $frac{partial C}{partial b_{i}} = -2e_{ui}+ 2lambda b_{i}$ 其中， $e_{ui} = r_{ui}-mu -b_u-b_i-sum_{f=1}^{F}p_{uf}q_{if}$ 递推公式： $p_{uf} = p_{uf} + alpha (q_{if}*e_{ui} - lambda p_{uf})$ $q_{if} = q_{if} + alpha (p_{uf}*e_{ui} - lambda q_{if})$ $b_{u} = b_{u} + alpha (e_{ui} - lambda b_{u})$ $b_{i} = b_{i} + alpha (e_{ui} - lambda b_{i})$ 我们对LearningLFM稍做修改，就可以支持BiasLFM模型：

def LearningBiasLFM(train, F, n, alpha, lambda, mu):
    [bu, bi, p,q] = InitBiasLFM(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][f] += alpha * (q[i][f] * eui - lambda * p[u][f])
                q[i][f] += alpha * (p[u][f] * eui - lambda * q[i][f])
        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比赛中提出了一个模型（参见Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model ，http://www.cs.rochester.edu/twiki/pub/Main/HarpSeminar/Factorization_Meets_the_Neighborhood-_a_Multifaceted_Collaborative_Filtering_Model.pdf），将用户历史评分的物品加入到了LFM模型中，Koren将该模型称为SVD++。如何将基于邻域的方法也像LFM那样设计成一个可以学习的模型，我们可以将ItemCF的预测算法改成如下方式：

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

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

这里， $x_i$ 、 $y_j$ 是两个F维的向量。由此可见，该模型用 $x_i^Ty_j$ 代替了 $w_{ij}$ ，从而大大降低了参数的数量和存储空间。再进一步，我们可以将前面的LFM和上面的模型相加，从而得到如下模型：

Koren又提出，为了不增加太多参数造成过拟合，可以令x = q，从而得到最终的SVD++模型： $widehat{r}_{ui} = mu +b_u+b_i+q_i^Tcdot (p_u+frac{1}{sqrt{|N(u)|}}sum_{jin N(u)}y_j)$ 此时，损失函数为 $C(p,q) = sum_{(u,i)in Train} (r_{ui}-mu -b_u-b_i-sum_{f=1}^{F}p_{uf}q_{if}-frac{q_i^T}{sqrt{|N(u)|}}sum_{jin N(u)}y_j)^{2}+lambda (||p_u||^2+||q_i||^2+||b_u||^2+||b_i||^2+||y_j||^2)$ 求偏导： $frac{partial C}{partial p_{uf}} = -2q_{if}*e_{ui} + 2lambda p_{uf}$ $frac{partial C}{partial q_{if}} = -2(p_{uf}+frac{1}{sqrt{|N(u)|}}sum_{jin N(u)}y_j)*e_{ui}+ 2lambda q_{if}$ $frac{partial C}{partial b_{u}} = -2e_{ui}+ 2lambda b_{u}$ $frac{partial C}{partial b_{i}} = -2e_{ui}+ 2lambda b_{i}$ $frac{partial C}{partial y_{j}} = -2frac{q_i^T}{sqrt{|N(u)|}}e_{ui}+ 2lambda y_{j}$ 其中， $e_{ui} = r_{ui}-mu -b_u-b_i-sum_{f=1}^{F}p_{uf}q_{if}-frac{q_i^T}{sqrt{|N(u)|}}sum_{jin N(u)}y_j$ 递推公式： $p_{uf} = p_{uf} + alpha (q_{if}*e_{ui} + frac{1}{sqrt{|N(u)|}}sum_{jin N(u)}y_j cdot e_{ui}- lambda p_{uf})$ $q_{if} = q_{if} + alpha (p_{uf}*e_{ui} - lambda q_{if})$ $b_{u} = b_{u} + alpha (e_{ui} - lambda b_{u})$ $b_{i} = b_{i} + alpha (e_{ui} - lambda b_{i})$ $y_{j} = y_{j} + alpha (frac{q_i^T}{sqrt{|N(u)|}}e_{ui} - lambda y_{j})$

def LearningSVDPlusPlus(train_ui, F, n, alpha, lambda, mu):
    [bu, bi, p, q, y] = InitSVDPlusPlus(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(u, i, p, q, bu, bi, mu, z)
                eui = rui - pui
                bu[u] += alpha * (eui - lambda * bu[u])
                bi[i] += alpha * (eui - lambda * bi[i])
                for f in range(0,F):
                    sum[f] += q[i][f] * eui * ru
                    p[u][f] += alpha * (q[i][f] * eui - lambda * p[u][f])
                    q[i][f] += alpha * ((z[u][f] + p[u][f]) * eui - lambda * q[i][f])
            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, y)


def Predict(u, i, p, q, bu, bi, mu, z):
    ret = mu + bu[u] + bi[i]
    ret += sum(p[u][f] * q[i][f] for f in range(0,len(p[u]))
    ret += sum(q[i][f] * z[u][f] for f in range(0, len(q[i])))
    return ret

8.2.4 加入时间信息

利用时间信息的方法也主要分成两种，一种是将时间信息应用到基于邻域的模型中，另一种是将时间信息应用到矩阵分解模型中。 1. 基于邻域的模型融合时间信息 Netflix Prize的参赛队伍BigChaos在技术报告中提出了一种融入时间信息的基于邻域的模型，本节将这个模型称为TItemCF。该算法通过如下公式预测用户在某一个时刻会给物品什么
评分：

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

$sigma (x)$ 是sigmoid函数，它的目的是将相似度压缩到（0，1）区间中。随着 $Delta t$ 增加， $f(w_{ij},Delta t)$ 会越来越小，也就是说用户很久之前的行为对预测用户当前评分的影响越来越小。 2. 基于矩阵分解的模型融合时间信息 在引入时间信息后，用户评分矩阵不再是一个二维矩阵，而是变成了一个三维矩阵。不过，我们可以仿照分解二维矩阵的方式对三维矩阵进行分解。我们可以将用户—物品—时间三维矩阵如下分解：

这里 $b_t$ 建模了系统整体平均分随时间变化的效应， $x_u^Tcdot y_t$ 建模了用户平均分随时间变化的效应， $s_i^Tcdot z_t$ 建模了物品平均分随时间变化的效应，而 $sum _fg_{u,f}h_{i,f}l_{t,f}$ 建模了用户兴趣随时间影响的效应。这个模型也可以很容易地利用前面提出的随机梯度下降法进行训练。本章将这个模型记为TSVD。 Koren在SVD++模型的基础上也引入了时间效应②，回顾一下SVD++模型：

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

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

8.2.5 模型融合

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

该方法每次产生一个新模型，按照一定的参数加到旧模型上去，从而使训练集误差最小化。每次都还是利用全样本集进行预测，但每次使用的模型都有区别。一般来说，级联融合的方法都用于简单的预测器，比如前面提到的平均值预测器。

由此可见，即使是利用简单的算法进行级联融合，也能得到比较低的评分预测误差。 2. 模型加权融合 假设我们有K个不同的预测器{ $widehat{r}^{(k)}$ , $widehat{r}^{(k)}$ , ..., $widehat{r}^{(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的相关实验结果

② 参见Arkadiusz Paterek的“Improving regularized singular value decomposition for collaborative filtering”（ACM International Conference on Knowledge Discovery and Data Mining，2007，39-42。
③ 同上。
④ 参见Yehuda Koren的“Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model”（ACM SIGKDD international conference on Knowledge discovery and data mining，2008，426-434。
⑤ 参见Yehuda Koren的“Collaborative Filtering with Temporal Dynamics”（ACM 2009 Article，2009）。