推荐系统的数学模型-从矩阵分解到推荐系统（Scala实现）

2021-04-13 11:49:30 浏览数 (1)

词汇：

Matrix Factorization 矩阵分解

Recommendation System 推荐系统

User 用户 Feature 特征 Item 物品

简介：

不论有没有觉察到，互联网的搜索模式在近几年已经发生了颠覆性的变化。如果说是十年前叫做百度模式，那今天可以被称之为头条模式。两者的区别在于，百度模式提供一个入口，让用户按照自己的需求查询关心的内容（各种广告暂不考虑），头条是按照用户的搜索历史及浏览记录，推送与之相似的内容，如此，用户可以投入更少的精力，更大概率的得到符合自己喜好的节目。

这篇文章不讨论两种模式孰优孰劣，或者谁更有发展前景，只是从纯技术的角度，分析实现推荐系统的数学模型。

业务场景：

假设我们在豆瓣上获取了一组用户评分，我们整理了四位用户 的评分信息，整理如下：

第一滴血

风月俏佳人

小萝莉的猴神大叔

海王

愤怒的黄牛

我是山姆

我不是药神

唐人街探案

星际穿越

变态假面

李雷

9.0

-

-

8.5

7.0

2.0

6.5

8.0

-

-

韩梅梅

-

9.5

9.0

2.0

-

9.0

9.3

-

9.5

-

Jim Green

9.5

2

8.0

9.0

-

7.0

-

8.0

6.0

6.0

Lucy

3.0

10.0

-

4.0

8.5

-

9.5

4.0

-

-

这里面 - 表示用户对某部电影没有相应的评分记录，可以理解成用户并没有看过这部电影，这部电影具有潜在推荐价值。

面对这样一组数据，你最直接的反应是什么？

我们先对这些电影打一个粗略的标签：

特征

电影

剧情类

唐人街探案、我不是药神、星际穿越、我不是药神

动作类

第一滴血、愤怒的黄牛、海王

情感类

风月俏佳人、我是山姆、小萝莉的猴神大叔、星际穿越

恶趣味类

变态假面

如果我们把李雷和Jim Green分成一组，韩梅梅和Lucy分成一组，会发现同一组的成员对电影的喜好更为一致。那么，我们可不可以这样操作，将李雷看过但是Jim Green没有看过的电影推荐给Jim Green，对其他人也采取相同的推荐方法。

这正是推荐系统要实现的。就好比两个好朋友互相推荐或者相约去电影院一样。唯一不同的地方就是，这里的两个人可能完全不知道对方的存在，但是通过推荐系统，我们帮助他们建立了”品味相近的朋友关系“。

引入特征：

接下来，我们在 用户user 和 物品item（在上面的例子中就是电影）引入特征 feature，并且将 user 对具体 item 的喜好转换成 user 对具有某一类特征的item具有倾向性，也就是说，如果两个 user 对相同的特征具有倾向性，那么他们也大概率会喜欢彼此关注的具有这类feature 的 item。feature可以是各种因素，比如两个 user 都喜欢同一个明星，或者喜欢某一种导演的风格。在我们的分析中，我们不会挖掘究竟 user 是被哪一种 feature 吸引。

此外，我们还假设每一次分析，feature的个数都要小于 user 的个数以及 item 的个数。理由如下：我们不会考虑每一个 user 都只关心一种 feature，而不会和别的 user 共同关注一个feature的情况。否则的话，推荐就毫无意义，因为每一个 user 都对其他 user 关注的 item 毫无兴趣。对于 item 而言，也是一样的道理。

矩阵分解：

假设我们获得了 user-item 矩阵，R: |U|✖|D|, |U| 表示 user 的个数，|D| 表示 item 的个数。元素

r_{ij}

表示第i个user对第j个item的评分，如果用户对某一个产品没有评分，设为0。

接下来，我们将矩阵 R 分解成 user-feature 和 feature-item 矩阵的乘积：

R ≈ P ✖ Q = R = widehat{R}

P ：|U|✖|K|，|K| 表示 feature 的个数，元素

p_{ik}

表示第i个user对第k个feature的喜好程度；

Q：|K|✖|D|，|K| 表示 feature 的个数，元素

q_{jk}

表示第第j个item对第k个feature的符合程度。item-feature关联矩阵为

Q^T

，求出Q之后，一般还要做一次转置或者item-feature矩阵。

对于

widetilde{R}

中的每一个因子，有

widehat{r}_{ij} = p_{i}q_{j}^T = sum_{k=1}^{K}{p_{ik}q_{kj}}

我们希望R 和

widehat{R}

尽可能的接近，因为每一个元素的差异可能为正，可能为负，我们采用所有元素差值的平方和作为R 和

widehat{R}

差异的表征。

e_{ij}^2 = (r_{ij} - widehat{r}_{ij})^2 = (r_{ij} - sum_{k=1}^{K}{p_{ik}q_{kj}})^2

接下来就要用到梯度下降法了，以

p_{ik}

,

q_{kj}

为自变量，求梯度。一个多元函数的梯度表示这个函数值增长最快的方向，因此如果要求这个函数的最小值，只要每次都沿着梯度的反方向移动就行。

计算梯度如下：

frac{partial}{partial{p_{ik}}}e_{ij}^2 = -2(r_{ij} - widehat{r}_{ij})(q_{kj}) = -2e_{ij}q_{kj}
frac{partial}{partial{p_{ik}}}e_{ij}^2 = -2(r_{ij} - widehat{r}_{ij})(q_{kj}) = -2e_{ij}q_{ik}

每次移动的步长取α = 0.002，如果α 取得太大，可能会越过最小值，结果就是在最小值附近来回跳动。

p^{'}_{ik} = p_{ik} αfrac{partial}{partial{p_{ik}}}e_{ij}^2 = p_{ik} 2αe_{ij}q_{kj}
q^{'}_{kj} = q_{kj} αfrac{partial}{partial{p_{kj}}}e_{ij}^2 = q_{kj} 2αe_{ij}p_{ik}

对于总偏差，有如下公式：

frac{partial}{partial{p_{ik}}}sum_{m=1,j=1}^{M,J}e_{mj}^2 =frac{partial}{partial{p_{ik}}}sum_{j=1}^{J}e_{ij}^2 =sum_{j=1}^{J}frac{partial}{partial{p_{ik}}}e_{ij}^2
= -sum_{j=1}^{J} 2(r_{ij} - widehat{r}_{ij})(q_{kj})= -sum_{j=1}^{J} 2e_{ij}q_{kj}
frac{partial}{partial{q_{kj}}}sum_{m=1,j=1}^{M,J}e_{mj}^2 =frac{partial}{partial{q_{kj}}}sum_{j=1}^{J}e_{ij}^2 =sum_{j=1}^{J}frac{partial}{partial{q_{kj}}}e_{ij}^2
= -sum_{j=1}^{J} 2(r_{ij} - widehat{r}_{ij})(p_{ik})= -sum_{j=1}^{J} 2e_{ij}p_{ik}

我们在初始化 user item 矩阵时，对于 user 没有评分的 item 直接赋值为 0。这样就会产生一个问题，当矩阵P ✖ Q 不断逼近 R 时，未评分项都会趋近于0。产生的结果就是 user 对这个 item 没有任何兴趣。实际应用中，我们并不会让P Q的乘积和R一模一样。相反，我们只是试图减少已经评分的 user - item 的偏差值。比如我们将所有已经评分的 (user，item，rating) 组成一个集合T（T也是常说的训练数据 training data），我们需要的是对这个集合内的元素偏差

e_{ij}

之和 尽可能的小。而对于那些未知的评分，一旦我们通过已知项计算出了矩阵P，Q，自然可以计算出结果。

基于以上分析，我们将偏差 e 的定义域重新现在在集合T上，由此得到偏差的表达式为：

E = sum_{(u_i, d_j, r_{ij} in T)}e_{ij} = sum_{(u_i, d_j, r_{ij} in T)}(r_{ij} - sum_{k=1}^{K}{p_{ik}q_{kj}})^2

正则化

上面的算法是分解矩阵最基础的算法。还有更多的分解方法，当然这些方法也会更复杂。一个常用的扩展方法是，通过正则化避免过度拟合。这个方法是通过增加参数β和调节平方差实现的：

e_{ij}^2 = (r_{ij} - widehat{r}_{ij})^2 = (r_{ij} - sum_{k=1}^{K}{p_{ik}q_{kj}})^2 frac{β}{2}sum_{k=1}^{K}({||P||}^2 {||Q||}^2)

新参数 β 用来控制空值 user-feature 和 item-feature 向量的量级，这样不需要包含大数字就可以较好的近似R。在实际应用中，β 一般被设置为0.02。通过类似的步骤，更新的平方差公式如下：

p^{'}_{ik} = p_{ik} αfrac{partial}{partial{p_{ik}}}e_{ij}^2 = p_{ik} α(2e_{ij}q_{kj}-βp_{ik})
q^{'}_{kj} = q_{kj} αfrac{partial}{partial{p_{kj}}}e_{ij}^2 = q_{kj} α(2e_{ij}p_{ik}-βq_{kj})

Scala 代码实现

只是为了展示推荐算法的原理，代码采用未经过正则化处理的公式。

代码语言：javascript复制
package pers.machi

import java.io.{File, PrintWriter}
import breeze.linalg.DenseMatrix
import breeze.linalg._

object RecomendationSystem {
  def main(args: Array[String]): Unit = {
    val v1 = Array[Double](9.0, 0, 0, 8.5, 7.0, 2.0, 6.5, 8.0, 0, 0)
    val v2 = Array[Double](0, 9.5, 9.0, 2.0, 0, 9.0, 9.3, 0, 9.5, 0)
    val v3 = Array[Double](9.5, 2, 8.0, 9.0, 0, 7.0, 0, 8.0, 6.0, 6.0)
    val v4 = Array[Double](3.0, 10.0, 0, 4.0, 8.5, 0, 9.5, 4.0, 0, 0)
	
	// R是评分矩阵
	val R = DenseMatrix(Array(v1, v2, v3, v4): _*)

    val N: Int = R.rows
    val M: Int = R.cols
    
    // 假设有三个feature会对user的喜好造成影响
    val K: Int = 3

	// 步长
    val alpha = 0.002

	// 随机初始化P Q两个矩阵
    var P: DenseMatrix[Double] = DenseMatrix.rand(N, K)
    var Q: DenseMatrix[Double] = DenseMatrix.rand(K, M)

	// 开始循环
    while (true) {
      var R_ = P * Q
      
      // 偏差矩阵，如果用户评分为零，表示用户没有看过这个电影，对应的偏差值为0
      val E = R.mapPairs((t, v) => {
        if (v == 0)
          0
        else {
          v - R_.valueAt(t._1, t._2)
        }
      }
      )
		
	  // 求偏差矩阵平方和，平方和小于0.1时，退出循环，打印输出结果
      val s = sum(E.map(e => e * e))
      if (s < 0.1) {
        val writer = new PrintWriter(new File("D:\saveTextTitle.txt"))
        writer.println(R_.toString(100, 1000000))
        writer.close()
        System.exit(0)
      }
		
	  // 每次对P进行更新
      P = P.mapPairs((t, v) => {
        v   alpha * 2 * E(t._1, ::).inner.dot(Q(t._2, ::).inner)
      })
		
	  // 每次对Q进行更新
      Q = Q.mapPairs((t, v) => {
        v   alpha * 2 * E(::, t._2).dot(P(::, t._1))
      })
    }
  }
}

结果分析

第一滴血

风月俏佳人

小萝莉的猴神大叔

海王

愤怒的黄牛

我是山姆

我不是药神

唐人街探案

星际穿越

变态假面

李雷

9.00

-2.98

**3.55 **

8.50

7.00

2.00

6.50

8.00

**0.93 **

**4.01 **

韩梅梅

**2.56 **

9.50

9.00

2.00

8.07

9.00

9.30

2.00

9.50

**4.28 **

Jim Green

9.50

2.00

8.00

9.00

10.57

7.00

**10.72 **

8.00

6.00

6.00

Lucy

3.00

10.00

**8.27 **

4.00

8.50

**6.11 **

9.50

4.00

**7.59 **

**3.77 **

加粗的评分是我们通过算法预计得到。可以抓取几组数据做个简单的说明：

韩梅梅和Lucy具有相近的偏好，李雷和Jim Green具有相近的偏好。因此，Lucy不喜欢第一滴血，预测韩梅梅对第一滴血的评分也较低。对于风月俏佳人，李雷的评分也较低。可见，尽管我们使用的算法很粗糙，但是其结果还具有一定参考价值。

扩展

如果能和Spark流计算整合，某一时间段内所有用户做相互推荐，或许能实现较好的推荐效果。

编程算法 推荐系统

0 人点赞