推荐系统（三）：基于矩阵分解的推荐算法

2019-12-16 本文已影响0人 fromeast

一、矩阵分解原理

1.1、奇异值分解

奇异值分解（Singular Value Decomposition，SVD）是一种常见的矩阵分解方式，对于一个 $m \times n$ 的矩阵 $A$ ，可定义其SVD为：
$A=U \Sigma V^{*}$
其中 $U$ 为 $m \times m$ 矩阵， $V$ 是 $n \times n$ 矩阵， $\Sigma$ 为 $m \times n$ 矩阵，其除了对角线元素外全为0，即
$\boldsymbol{\Sigma}=\left(\begin{array}{cccccc}{\lambda_{1}} & {0} & {0} & {\cdots} & {\cdots} & {0}\\ {0} & {\lambda_{2}} & {0} & {\cdots} & {\cdots} & {0}\\ {0} & {0} & {\cdots} & {\cdots} & {\cdots} & {0}\\ {\cdots} & {\cdots} & {\cdots} & {\lambda_{n-1}} & {\cdots}& {0} \\ {\cdots} & {\cdots} & {\cdots} & {\cdots} & {\lambda_{n}} & {0} \\ {0}& {0}& {0}& {0}& {0}& {\mathbf{0}}\end{array}\right)$
由于奇异值矩阵包含了原矩阵的信息，其其中主要信息由较大的几个奇异值所表征，因此奇异值分解可用来作为矩阵降维，即：
$A_{m \times n}=U_{m \times m} \Sigma_{m \times n} V_{n \times n}^{\mathrm{*}} \approx U_{m \times k} \Sigma_{k \times k} V_{k \times n}^{\mathrm{*}}$
在推荐系统中， $m$ 代表样本的用户数，维度通常会很高，当 $k \ll m$ 时会大大减轻线上存储和计算的压力。基于矩阵分解的推荐算法的步骤可以分为：
（1）加载用户对物品的评分矩阵；
（2）矩阵分解，求奇异值，根据奇异值的能量占比确定降维至 $k$ 的数值；
（3）使用矩阵分解对物品评分矩阵进行降维；
（4）使用降维后的物品评分矩阵计算物品相似度，对用户未评分过的物品进行预测；
（5）产生前 $n$ 个评分值高的物品，返回编号并预测评分值。

1.2、PQ分解

SVD计算之前需要先把评分矩阵 $A$ 补全，将稀疏矩阵变为稠密矩阵，这样就会带来一些问题：1. 稠密矩阵需要耗费巨大的存储空间；2. SVD计算复杂度很高，在大规模稠密矩阵上计算不现实。隐语义模型也是基于矩阵分解的，但是是将原始矩阵分解成两个矩阵相乘的形式：
$A=P Q^{*}$
其中 $P$ 为用户因子矩阵， $Q$ 为物品因子矩阵。
通常上式不会精确相等，需要最小化二者之间的差异，可通过如下损失函数来表达：
$\min \left(c_{i j}\left\|r_{i j}-\sum_{i=1}^{K} p_{i k} q_{k j}\right\|_{2}^{2}+\beta\left\|p_{i}\right\|^{2}+\gamma\left\|q_{j}\right\|^{2}\right)$
其中 $r_{ij}$ 表示用户 $i$ 对物品 $j$ 的评分交互，1表示有交互，0表示无交互， $c_{ij}$ 表示用户偏爱某个商品的置信参数，交互次数多权重就会增加，如果用 $d_{ij}$ 表示交互次数的话，则可表示为 $c_{ij}=1+\alpha d_{ij}$ 。
通过上述方法将协同过滤问题转化为了一个优化问题，求解上述损失函数通常采用交替最小二乘法(alternating least squares) ，计算过程如下：
（1）随机初始化 $Q$ ，对上式中 $p_i$ 求偏导，令导数为0，得到当前最优解 $p_i$
$\nabla_{p_i} \text {loss}=\frac{\partial \operatorname{loss}}{\partial p_{i}}=-2c_{ij}\left(r_{i j}-\sum_{i=1}^{K} p_{i k} q_{k j}\right) q_{k j}+2\beta p_{i}$
（2）固定 $p$ ，对上式 $q_j$ 求偏导，令导数为0，得到当前最优解 $q_j$
$\nabla_{q_j} \text {loss}=\frac{\partial \operatorname{loss}}{\partial q_{j}}=-2c_{ij}\left(r_{i j}-\sum_{i=1}^{K} p_{i k} q_{k j}\right) p_{ik}+2\gamma q_{j}$
（3）固定 $q$ ，对上式中 $p_i$ 求偏导，令导数为0，得到当前最优解 $p_i$
（4）重复以上（2）到（3），直至达到迭代次数或收敛
$\begin{array}{l}{p_{i k}=p_{i k}-\nabla_{p_i} l o s s} \\ {q_{k j}=q_{k j}-\nabla_{q_j} l o s s}\end{array}$

二、算法实现

1、SVD的实现与说明

为简明说明SVD的作用过程，采用 $10\times 11$ 维的用户评分矩阵，行代表用户，列代表物品，数值代表评分，未评分值为0。

import numpy as np
def load_data():
    return [[0,0,1,0,0,2,0,0,0,0,5],
            [0,0,0,5,0,3,0,0,0,0,3],
            [0,0,0,0,4,1,0,1,0,4,0],
            [3,3,4,0,0,0,0,2,2,0,0],
            [5,4,2,0,0,0,0,5,5,0,0],
            [0,0,0,0,5,0,1,0,0,0,0],
            [4,1,4,0,0,0,0,4,5,0,1],
            [0,0,0,4,0,4,0,0,0,0,4],
            [0,0,0,2,0,2,5,0,0,1,2],
            [1,0,0,4,0,0,0,1,2,0,0]
            ]
data = load_data()
mat = np.mat(data)

原始数据

U,Sigma,VT = np.linalg.svd(mat)

rate = sum(Sigma[0:4]**2)/sum(Sigma**2)
rawdata = U[:,:10]*np.mat(np.diag(Sigma[:10]))*VT[:10,:]
recondata = U[:,:4]*np.mat(np.diag(Sigma[:4]))*VT[:4,:]

进行SVD分解，可以得到 $U， \Sigma ，V^{*}$ 三个矩阵， $\Sigma$ 值如下：

Sigma
可见前4个值能量占比为，说明了SVD的降维作用，下表分别为全10个奇异值的重构表和前4个奇异值的重构表，可以看出后者能够较好地代表前者。

全10个奇异值的重构表

前4个奇异值的重构表
即将物品的评分矩阵映射到低维空间，亦即矩阵的转置，如下：

降维后的物品评分矩阵

2、SVD推荐算法的实现

数据加载与相似度计算函数
定义几种相似度计算方法，包括Cosine相似度、欧几里得距离、皮尔逊相关系数，本文采用Cosine相似度。

import data
import numpy as np

def cos_sim(X,Y):
    num = float(X.T*Y)
    denum = np.linalg.norm(X)*np.linalg.norm(Y)
    return 0.5+0.5*(num/denum)
def eclud_sim(X,Y):
    return 1.0/(1.0+np.linalg.norm(X-Y))
def pears_sim(X,Y):
    if len(X)<3:
        return 1.0
    return 0.5+0.5*np.corrcoef(X,Y,rowvar=0)[0][1]

SVD评分估计
基于矩阵奇异值分解转换的商品评价估计，实现过程的详述见注释

def svd_estimate(data,user,sim_measure,item):
    n = data.shape[1]   # 列维度，物品数量
    sim_total,rate_sim_total = 0.0,0.0  # 相似度初始化
    
    U,Sigma,VT = np.linalg.svd(data)   #SVD分解
    low_dim = data.T * U[:,:4] * np.mat(np.diag(Sigma[:4])).I  # 将数据降到低维空间
    for j in range(n):  #对于给定用户，循环所有物品，计算与item的相似度
        user_rating = data[user,j]  #用户user对物品j的评分
        if user_rating == 0 or j == item:  # 未评价 或 item本身
            continue
        similarity = sim_measure(low_dim[item,:].T,low_dim[j,:].T)  #相似度计算
        print ('%d and %d similarity is:%f'%(item,j,similarity))
        
        sim_total += similarity  #相似度求和
        rate_sim_total += similarity*user_rating  #对相似度及评分值的乘积求和
    if sim_total == 0:
        return 0 
    else:
        return rate_sim_total/sim_total

基于SVD进行推荐
寻找未评级的物品，对给定用户建立一个未评分物品列表，并计算评价值，进而推荐

def recommend(data,user,N=3,sim_measure=cos_sim,est_method=svd_estimate):
    unrated_item = np.nonzero(data[user,:].A == 0)[1]  #未评价的物品
    if len(unrated_item) == 0:
        return ('you rated everything')
    print(unrated_item)
    item_score = []    
    for item in unrated_item:  #在未评价的物品中
        estimate_score = est_method(data,user,sim_measure,item)  #计算评价值
        item_score.append((item,estimate_score))  #记录商品及对应评价值
    return sorted(item_score,key=lambda x: x[1],reverse=True)[:N]  #推荐前N个未评价物品

结果分析

data = np.mat(data.load_data())
result = recommend(data,2,N=3,sim_measure=cos_sim,est_method=svd_estimate)
print(result)

对于第2号用户， $[0,0,0,0,4,1,0,1,0,4,0]$ ，其未评价的列表为 $[ 0~1~2~3~6~8~10]$ ，则可计算得到未评价物品与所有已评价物品的相似度为：

0 and 4 similarity is:0.481378
0 and 5 similarity is:0.457935
0 and 7 similarity is:0.986661
0 and 9 similarity is:0.481274
1 and 4 similarity is:0.488477
1 and 5 similarity is:0.453733
1 and 7 similarity is:0.973832
1 and 9 similarity is:0.489637
2 and 4 similarity is:0.461096
2 and 5 similarity is:0.587373
2 and 7 similarity is:0.825805
2 and 9 similarity is:0.479893
3 and 4 similarity is:0.476120
3 and 5 similarity is:0.693686
3 and 7 similarity is:0.545381
3 and 9 similarity is:0.487154
6 and 4 similarity is:0.874726
6 and 5 similarity is:0.869111
6 and 7 similarity is:0.526060
6 and 9 similarity is:0.906349
8 and 4 similarity is:0.481115
8 and 5 similarity is:0.445549
8 and 7 similarity is:0.980209
8 and 9 similarity is:0.477279
10 and 4 similarity is:0.447311
10 and 5 similarity is:0.933246
10 and 7 similarity is:0.453173
10 and 9 similarity is:0.496646

对所有未评分物品的评分为：

[(0, 2.1996914641365213), (1, 2.219755646468587), (2, 2.1991365553488067), (3, 2.3121588279962424), (6, 2.6822454316204456), (8, 2.205955763398433), (10, 2.2151987747133908)]

推荐其中的前三个：

[(6, 2.6822454316204456), (3, 2.3121588279962424), (1, 2.219755646468587)]

3、PQ分解推荐算法的实现

按照上述算法实现PQ分解的过程如下：

def matrix_factorization(matrix,k,lr):
    matrix = np.mat(matrix)
    m,n = matrix.shape
    P = np.mat(np.random.random((m,k)))
    Q = np.mat(np.random.random((k,n)))
    loss = 1.0
    epoch = 0
    while loss>=0.0005 and epoch<=epochs:
        loss = 0.0
        for i in range(m):
            for j in range(n):
                r = matrix[i,j]
                r_ = 0
                l2_p,l2_q = 0,0
                for t in range(k):
                    r_ += P[i,t]*Q[t,j]
                    l2_p += P[i,t]**2
                    l2_q += Q[t,j]**2
                e = r-r_
                loss += e**2+beta*l2_p+gamma*l2_q
                for t in range(k):
                    P[i,t] += lr*(2*e*Q[t,j]-2*beta*P[i,t])
                    Q[t,j] += lr*(2*e*P[i,t]-2*gamma*Q[t,j])
        epoch += 1
    return P,Q

设置参数并对比分解后复原的结果原数据的差异

beta = 0.001
gamma = 0.001
epochs = 20000
data = np.mat(data.load_data())
P,Q = matrix_factorization(data,10,0.002)
result = P*Q
print(P*Q)

可见当k=10时，与原数据已十分接近，k=4时也比较接近，说明了矩阵分解能够表征原数据。

k=10时的结果

k=4时的结果

另外可以看出P,Q矩阵分别从横轴和纵轴提取了原矩阵的信息，进而可利用Q矩阵替代上文的V矩阵的作用而进行推荐，在此不予赘述。

P值

Q值

参考资料

[1]. https://blog.csdn.net/xiaoxiaowenqiang/article/details/78076984
[2]. 推荐系统与深度学习. 黄昕等. 清华大学出版社. 2019.
[3]. 推荐系统算法实践. 黄美灵. 电子工业出版社. 2019.
[4]. 推荐系统算法. 项亮. 人民邮电出版社. 2012.
[5]. 美团机器学习实践. 美团算法团队. 人民邮电出版社. 2018.
[6]. https://blog.csdn.net/recall_tomorrow/article/details/80218051

花萼楼前雨露新，长安城里太平人。—— 张说《十五日夜御前口号踏歌词二首》