新生任务-5

一、Funk-SVD 分解算法

对于一个推荐系统, 用户和物品之间的关系可以整理为如下这样的一个矩阵.

User-Item 1 2 3 4
1 x 4.5 2.0 x
2 4.0 x 3.5 x
3 x 5.0 x 2.0
4 x 3.5 4.0 1.0

矩阵中每一行代表一个用户, 而每一列则代表一个物品. 若用户对物品有过评分, 则矩阵中处在用户对应的行与物品对应的列交叉的位置表示用户对物品的评分值. 矩阵中的 'x' 代表用户对物品未评分. 这个矩阵就叫做User-Item 评分矩阵, 这个矩阵中的数在实际统计后大多数现显示为问号.

推荐系统需要做的事情就是对于任意一个用户, 预测出所有未评分物品的分值, 并按分值大小从高到低的顺序推荐将对应的物品推荐给用户.

我们需要做的就是求出矩阵中 'x' 的值.

和 \(SVD\) 算法需要三个矩阵不同, \(Funk-SVD\) 算法只需要两个矩阵. 如下图所示

此时我们就有公式

\[ R_{m \times n} \approx P_{m \times k} Q_{k \times n} = \hat{M}_{m \times n} \]

评分矩阵 \(R\) 是一个 \(m \times n\) 的矩阵, 一共有 \(m\) 个用户, \(n\) 个物品. 通过一系列运算将矩阵 \(R\) 转化为两个矩阵 \(P\) 和 \(Q\), 矩阵 \(U\) 的大小是 \(m \times k\), 矩阵 \(Q\) 的大小是 \(k \times n\).

因为矩阵 \(R\) 中存在未知, 我们只是在对这个矩阵进行拟合, 所以是约等于.

该方法基于这样一个假设: 用户对一个物品的喜爱程度主要由 \(k\) 个因素决定, \(P_{ni}\) 表示第 \(n\) 个用户对第 \(i\) 个因素的偏好程度, 而 \(Q_{ix}\) 表示第 \(x\) 个物品满足第 \(i\) 个因素的程度, \(R_{nx}\) 表示用户 \(n\) 对物品 \(x\) 最终的喜好程度.

这时就存在着几个问题, 评价拟合程度的指标？如何获取 \(P,Q\) 两矩阵？

先回答第一个问题, 拟合程度越高就说明 \(P \ Q\) 两矩阵的乘积越靠近矩阵 \(R\). 这里用 \(SSE\) (和平方) 来表示, 那么就有公式.

\[ SSE = E_{U,I}^2 = {\textstyle \sum_{U,I}}(R_{U,I} \ - \ \hat{R}_{U,I})^2 \]

现在的问题就转化为了求在损失 \(SSE\) 最小时的矩阵 \(P\) 和 \(Q\). 这也回答了如何获取 \(P,Q\) 两矩阵这个问题.

二、梯度下降

对于多维变量的函数, 梯度为 0 的点有三种情况——极大值、极小值、鞍点. 极小值是梯度下降过程最稳定的不动点. 迭代过程可以参照下雨的时候水的流向, 水总是会聚集在坑 (极小值) 里面.

但是我们要找的是负梯度. 举个例子

函数 \(f(x)=x^2\) 就是一个凸函数, 满足 \(f(\frac{x_1+x_2}{2}) \le \frac{f(x_1)+f(x_2)}{2}\). 其图像如下所示:

假设点 (-5,25) 要朝向最低点移动, 它此时的梯度为 -10, 应该往 x 正方向移动使得梯度为 0.

假设点 (5,25) 要朝向最低点移动, 它此时的梯度为 10, 应该往 x 负方向移动使得梯度为 0.

回到之前求的损失函数, 就有以下两个步骤

1.求解损失函数的梯度

\[ SSE = E_{U,I}^2 = {\textstyle \sum_{U,I}}(R_{U,I} \ - \ {\textstyle \sum_{k=1}^{K}}P_{U,k} \ Q_{k,I} )^2 \]

\(SSE\) 是关于 \(P\) 和 \(Q\) 的多元函数, 当随机选定 \(U\) 和 \(I\) 后, 需要枚举所有的 \(k\), 并且对 \(P_{U,k}\) 以及 \(Q_{k,I}\) 求偏导数. \[ \frac{\partial}{\partial P_{U,k}}{E_{U,I}}^2 = 2 E_{U,I}\frac{\partial E_{U,I}}{\partial P_{U,k}} = -2E_{U,I}Q_{k,I} \]

\[ \frac{\partial}{\partial Q_{k,I}}{E_{U,I}}^2 = 2 E_{U,I}\frac{\partial E_{U,I}}{\partial Q_{k,I}} = -2E_{U,I}P_{U,k} \]

2.根据负梯度变化更新变量

\[ P_{U,k} = P_{U,k} - \alpha (-2E_{U,I}Q_{k,I}) = P_{u,k} + 2 \alpha E_{U,I}Q_{k,I} \]

\[ Q_{k,I} = Q_{k,I} - \alpha (-2E_{U,I}P_{U,k}) = Q_{k,I} + 2 \alpha E_{U,I}P_{U,k} \]

公式推导到此完结, \(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
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
from math import *
import numpy as np

def matrix_factorization(R, P, Q, steps = 5000, alpha = 0.0002):
    Q = Q.T

    for _ in range(steps):
        for i in range(len(R)):
            for j in range(len(R[i])):
                eij = R[i][j] - np.dot(P[i,:],Q[:,j])
                for k in range(K):
                    if R[i][j] > 0:
                        P[i][k] = P[i][k] + 2 * alpha * eij * Q[k][j]
                        Q[k][j] = Q[k][j] + 2 * alpha * eij * P[i][k]

        # SSE
        e = 0
        for i in range(len(R)):
            for j in range(len(R[i])):
                if R[i][j]>0:
                    e = e + pow(R[i][j] - np.dot(P[i,:],Q[:,j]),2)

        # Is result convergence?
        if e < 0.001:
            break

    return P,Q.T
 
if __name__ == '__main__':
    R = [
        [0,4.5,2,0],
        [4,0,3.5,0],
        [0,5,0,2],
        [0,3.5,4,1]
    ]
    R = np.array(R)
    # The Row of Matrix R
    M = len(R)
    # The Column of Matrix R
    N = len(R[0])
    # The Hidden factor number
    K = 2
    # Get a random matrix P : M rows K columns
    P = np.random.rand(M,K)
    # Get a random matrix Q : N rows K columns
    Q = np.random.rand(N,K)
    new_P, new_Q = matrix_factorization(R,P,Q)

    print("The original matrix is : ")
    print(R)

    print("The new matrix is : ")
    R_MF = np.dot(new_P,new_Q.T)
    print(R_MF)
1
2
3
4
5
6
7
8
9
10
11
输入 : 原始矩阵和隐藏因子 K. 例如下所示
[
    [0,4.5,2,0],
    [4,0,3.5,0],
    [0,5,0,2],
    [0,3.5,4,1]
]

代码示例中默认设置 K 为 2.

输出 : 通过矩阵分解拟合后的矩阵. 由此可得出未知评分.