一、概念

1、什么是稀疏矩阵

在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。

2、推荐系统中的稀疏矩阵

一般在推荐系统中，数据往往是使用用户-物品矩阵来表示的。用户对其接触过的物品进行评分，评分表示了用户对于物品的喜爱程度，分数越高，表示用户越喜欢这个物品。而这个矩阵往往是稀疏的，空白项是用户还未接触到的物品，推荐系统的任务则是选择其中的部分物品推荐给用户。

对于这个用户-物品矩阵，可以利用非空项的数据来预测空白项的数据，即预测用户对于其未接触到的物品的评分，并根据预测情况，将评分高的物品推荐给用户。预测评分的方式有很多，矩阵分解是一种非常适合的方法。

3、SVD及其三种改进算法

（1）传统的SVD
SVD分解要求矩阵是稠密的，也就是说矩阵的所有位置不能有空白。有空白时我们的矩阵是没法直接去用SVD分解的。大家会说，如果这个矩阵是稠密的，那不就是说我们都已经找到所有用户物品的评分了嘛，那还要SVD干嘛! 的确，这是一个问题，传统SVD采用的方法是对评分矩阵中的缺失值进行简单的补全，比如用全局平均值或者用用户物品平均值补全，得到补全后的矩阵。接着可以用SVD分解并降维。
虽然有了上面的补全策略，我们的传统SVD在推荐算法上还是较难使用。因为我们的用户数和物品一般都是超级大，随便就成千上万了。这么大一个矩阵做SVD分解是非常耗时的。
（2）FunkSVD
FunkSVD是在传统SVD面临计算效率问题时提出来的，既然将一个矩阵做SVD分解成3个矩阵很耗时，同时还面临稀疏的问题，那么我们能不能避开稀疏问题，同时只分解成两个矩阵呢？FunkSVD就解决了这一问题，它将矩阵R分解为P和Q
$R_{m*n} = P^T_{m*k}* Q_{k*n}$
它是怎么做到的呢？这里采用了线性回归的思想，目标是让用户的评分和用矩阵乘积得到的评分残差尽可能的小，也就是说，可以用均方差作为损失函数，来寻找最终的P和Q。

构造目标函数如下（后面两项为正则项）

P、Q两个矩阵的乘积 R' 去逼近矩阵R
接下来就成了一个数值优化问题，一般通过梯度下降法来得到结果。
（3）BiasSVD
在FunkSVD算法火爆之后，出现了很多FunkSVD的改进版算法。其中BiasSVD算是改进的比较成功的一种算法。BiasSVD假设评分系统包括三部分的偏置因素：和用户物品无关的评分因素，用户偏置项（用户自带的和物品无关的评分因素），物品偏置项（物品自带的和用户无关的评分因素）。
以物品偏置项为例，一个自带垃圾山寨货属性的商品评分不可能高，由于这个因素会直接导致用户评分低，与用户无关。
该方法在目标函数中加入了相应的偏置项，求解过程与FunkSVD一样。在某些场景下BiasSVD会比FunkSVD表现好。
（4）SVD++
SVD++算法在BiasSVD算法上进一步做了增强，这里它增加考虑用户的隐式反馈。

二、实现矩阵分解推荐

以下以FunkSVD算法作为示例

# coding = utf-8
import numpy as np
import matplotlib.pyplot as plt

#========================================================
#  准备数据
#========================================================

def loadDataSet():
    R = [
        [5,3,0,1],
        [4,0,3,1],
        [1,1,0,5],
        [1,0,0,4],
        [0,1,5,4],
    ]
    return np.array(R)

#========================================================
#  FunkSVD算法
#========================================================

def FunkSVD(R, K, epochs = 1000, alpha = 0.1, beta = 0.02):
    result=[]

    # P、Q矩阵初始化
    P = np.random.rand(R.shape[0], 2)
    Q = np.random.rand(R.shape[1], 2)

    for epoch in range(epochs):
        print("current epoch is {}".format(epoch))
        for i in range(R.shape[0]):
            for j in range(R.shape[1]):
                if(R[i][j] > 0):
                    P[i] = P[i] + alpha * ((R[i][j] - np.dot(P[i],Q[j].T))*Q[j] - beta * P[i])
                    Q[j] = Q[j] + alpha * ((R[i][j] - np.dot(P[i],Q[j].T))*P[i] - beta * Q[j])
        loss = 0
        num = 0
        for i in range(R.shape[0]):
            for j in range(R.shape[1]):
                # 对有评分的项目，计算损失
                if(R[i][j] > 0):
                    num += 1
                    loss += np.power(R[i][j] - np.dot(P[i],Q[j].T), 2)
        loss = loss / num
        result.append(loss)
        if(loss < 0.01):
            print("finish")
            break
    return P, Q, result

def plot_train(result):
    n = len(result)
    x = range(n)
    plt.plot(x, result, color='r', linewidth=3)
    plt.title("Convergence curve")
    plt.xlabel("generation")
    plt.ylabel("loss")
    plt.show()

#========================================================
#  主程序
#========================================================

if __name__ == '__main__':
    R = loadDataSet()

    pred_P, pred_Q, result = FunkSVD(R, 2)
    plot_train(result)
    pred_R = np.dot(pred_P, pred_Q.T)
    print(pred_R)

三、Spark MLlib中的矩阵分解

在Spark MLlib中，推荐算法只实现了基于矩阵分解的协同过滤推荐算法。其中，矩阵分解算法使用的是 FunkSVD 算法。
数据集取自movielens 数据集

# coding = utf-8
from pyspark import SparkContext
from pyspark import SparkConf

#========================================================
#  数据准备
#========================================================

sc = SparkContext("local", "testing")
# 打开用户评分文件，此文件是用户对项目的评分，文件每一行前3项分别是用户id，物品id，评分
user_data = sc.textFile("D:/movielens/ml-100k/u.data")
# 获取相关数据，即前3列
rates = user_data.map(lambda x: x.split("\t")[0:3])
# 将数据封装成 Rating 类
from pyspark.mllib.recommendation import Rating
rates_data = rates.map(lambda x: Rating(int(x[0]),int(x[1]),int(x[2]))) # 将字符串转为整型

#========================================================
#  训练模型
#========================================================

from  pyspark.mllib.recommendation import ALS
from pyspark.mllib.recommendation import MatrixFactorizationModel
sc.setCheckpointDir('checkpoint/')
ALS.checkpointInterval = 2
model = ALS.train(ratings=rates_data, rank=20, iterations=5, lambda_=0.02)

#========================================================
#  预测评分与推荐
#========================================================
# 预测用户38对物品20的评分
print (model.predict(38,20))
# 预测用户38最喜欢的10个物品
print (model.recommendProducts(38,10))

拓展1：使用SVD做推荐
 拓展2：使用funkSVD做推荐