一、spark-meetup阅读笔记

1.显式矩阵分解（Explicit Matrix Factorization）

• (1) 用户显式的给电影目录的一个子集打分

• (2) 目标：预测用户给新电影打的分数

• (3) 使均方根RMSE误差最小

公式：$$min_{x,y}\sum_{u,i}(r_{u,i} - x{_u^T}y_i - b_u - b_i)^2 - λ(\sum_u|x_u|^2 + \sum_i|y_i|^2)$$

• (4) 公式解析：
  • $λ$是正则化参数，控制着正则化的程度，用来避免过拟合的问题，通过交叉验证确定
  • $μ$表示所有评分的平均值，$b_u$和$b_i$描述用户和物品相对于平均值$μ$的偏差（有些用户普遍评价较低，有些用户普遍评价较高，添加一阶偏置项）
  • $X_u$表示用户$u$的潜在因子向量（特征向量），$Y_i$表示物品$i$的潜在因子向量（特征向量）

2.隐式矩阵分解

和显式矩阵不同的地方在于隐式矩阵的输入是用户的购买浏览等记录，隐式矩阵通常是稠密矩阵，而显式矩阵通常是稀疏矩阵。

公式：$$min_{x,y}\sum_{u,i}c_{u,i}(p_{u,i} - x{_u^T}y_i - b_u - b_i)^2 - λ(\sum_u|x_u|^2 + \sum_i|y_i|^2)$$

• 公式解析：
  • $C_{ui}$ 可信度，用户$u$对物品$i$隐式评价的权值
  • $P_{ui}$ 为user-item矩阵$P$的值，表示用户$u$对物品$i$的隐式评价
  • $μ$表示所有评分的平均值，$b_u$和$b_i$描述用户和物品相对于平均值$μ$的偏差（有些用户普遍评价较低，有些用户普遍评价较高，添加一阶偏置项）

3.迭代逼近的方法

由于数据量大，随机梯度下降的方法不再适合，使用易于并行的交替最小二乘法来逐步迭代逼近。

• (1) 目标：对于每一个用户$u$计算出$X_u$；对于每一个物品$i$计算出$Y_i$，最终通过计算出的$X_u$和$Y_i$向量计算出$P_{ui}$
• (2) 交替确定$X_u$和$Y_i$向量，计算出另外一个使得消耗函数的值减少，不断重复过程直至收敛或稳定
• (3) 矩阵计算优化：$Y^{TC_uY$的计算时间开销为$O(f}2n)$，而由于$C_u$中非0元素个数远小于n，因此可以在每次迭代时先提前计算出$Y^{TY$，再计算$Y}T(C_u-I)Y$，可以减少计算的时间开销
• (4) 每次迭代计算特征向量的公式：
  $$X_u = (Y^TCuY + λI)^{-1}YTC^up(u)$$

4.算法输入输出

• (1) 矩阵加载函数load_Matrix()

  • 参数：数据输入文件文件名，用户数量，物品数量
  • 输入：该函数输入数据为观测值统计文件，文件每行格式如下：
    [用户 物品 偏好值]
    • 观测值的意义尚未确定，可能是一项隐式反馈的值，比如用户观看物品的次数；也可能是多项隐式反馈的综合值
    • 观测值的定义是直接观测到的用户行为，在论文所做的实验中，是用户观看整部电影的次数，例如用户只观看了70%的时间，那么偏好值为0.7；而若用户观看了两次，那么偏好值为2
  • 输出：user-item观测值矩阵，其中第$u$行第$i$列元素为用户$u$对物品$i$的观测值，该观测值的意义和输入文件中观测值相同
  • 输出结构：Scipy库中的csr_Matrix类型，即压缩稀疏行矩阵（compressed sparse row）]

• (2) ImplicitMF类

  • 参数：user-item观测值矩阵，特征数量，迭代次数，归一化因子$λ$
    • user-item观测值矩阵即矩阵加载函数输出的观测值矩阵
    • 特征数量即用户特征向量和物品特征向量的长度
    • 迭代次数即使用交替最小二乘计算用户特征向量和物品特征向量的次数
  • 计算过程：
    • 首先对于输入的用户观测值矩阵$R$，将其转化为用户偏好矩阵$P$，$P_{ui}$为1说明用户对物品表现出偏好，为0说明用户对物品没有表现出偏好
      $$p_{ui} = \left{ \begin{array}
      \overline 1 & r_{ui} > 0 \ 0 & r_{ui} = 0 \
      \end{array}\right.$$
    • 使用置信度$C_{ui}$来为偏好度$P_{ui}$加权
    • 交替最小二乘的每次迭代首先固定物品特征矩阵$Y$来计算所有用户的用户特征向量$x_u,u\epsilon [0,Num_u]$；然后固定用户特征矩阵$X$来计算所有物品的物品特征向量$Y_i,i\epsilon [0,Num_i]$
  • 输出：所有用户特征向量user_vectors，所有物品特征向量item_vectors
    • 迭代结束后，根据最后输出的用户特征矩阵$X$和物品特征矩阵$Y$，即可计算出特定用户$u$对特定物品$i$的预测偏好度${P_{ui}}^\prime=Y_iT\times X_u$，该偏好度代表用户可能喜欢该物品的概率

5.隐式矩阵分解的Hadoop扩展

• (1).Map阶段
  • u % K = x & i % L = y 的向量，其中$u$，$i$为用户ID和物品ID，$K$和$L$是定义的分块数量
• (2).Reduce阶段
  • Reduce阶段将[用户/物品]分到$K$个节点进行处理，分别计算[用户向量/物品向量]
• (3).Hadoop的I/O瓶颈

6.隐式矩阵分解 in Spark

• (1).第一次尝试
  • 计算过程
    • 计算$Y^TY$并广播到所有节点
    • 将用户向量$X_u$和所有评分矩阵中的评分以及用户$u$有评分的物品向量$Y_i$进行Join
    • 将$Y^TCuIY$和$YTCuP(u)$加起来并求解
  • 缺陷
    • 多次将物品向量$Y$复制到各个节点上(没必要)
    • 每次迭代都对数据进行了shuffle(没必要)
    • 没有利用Spark的内存计算能力
• (2).第二次尝试
  • 计算过程
    • 计算$Y^TY$并广播到所有节点
    • 将评分矩阵按块分组，将每块与用户$u$有评分的物品向量$Y_i$进行Join
    • 将$Y^TCuIY$和$YTCuP(u)$加起来并求解
  • 缺陷
    • 每次迭代都对数据进行了shuffle(没必要)
    • 没有利用Spark的内存计算能力
• (3).第三次尝试
  • 计算过程
    • 首先，将评分矩阵、用户向量和物品向量按照用户和物品分区并缓冲在内存中
    • 其次，计算用户和物品的inlink映射和outlink映射
    • 计算$Y^TY$并广播到所有节点
    • 对于每个物品块，使用outlink映射将他们复制到必要的用户块中
    • 对于每个用户块，使用inlink映射和物品向量来更新用户向量