推荐算法——ALS模型算法分析、LFM算法

简介

• ALS(Alternating Least Squares)，即交替最小二乘法，因利用两个矩阵进行交替优化而得名。求解大致步骤如下：
  • 定义原始矩阵 $A_{m,n}=U_{m,k}\ast V_{k,n}$
  • 为$U_{m,k}$随机取值，固定$U_{m,k}$，利用最小二乘法求出$V_{k,n}$
  • 固定$V_{k,n}$，利用最小二乘法求出$U_{m,k}$
  • 持续交替进行求解，直到损失达到阈值（即新矩阵近似于原始矩阵）
• 比较经典的应用则是隐语义分析-推荐算法：原始矩阵为稀疏矩阵，通过ALS计算出的新矩阵则拥有原始矩阵缺失的值，即预测值。

ALS算法流程分析

• 数据（矩阵$A_{mn}$）

  user/item	商品1	商品2	商品3	商品4
  用户1	9	-	6	8
  用户2	3	9	-	4
  用户3	-	-	6	8
  用户4	9	8	5	9
  用户5	8	7	6	-

  • 我们的原始数据是不同用户对于不同商品的评分或喜好程度。因为用户不可能买过每样商品，因此会存在部分商品未评分的情况。

• 算法目标：挖掘出用户对未购买过的商品的喜好程度，也就是说要分析出原始稀疏矩阵$A_{m,n}$中的缺失值。

• 利用ALS算法，将稀疏矩阵$A_{m,n}$拆解为两个矩阵$U_{m,k}$ 、$V_{k,n}$，即$A_{m,n}=U_{m,k}\ast V_{k,n}$

  • k代表了用户与商品的隐含关联特征个数，需要使用者指定
  • $U_{m,k}$代表了用户与k个隐含特征的值
  • $V_{k,n}$代表了商品与k个隐含特征的值（不过是逆矩阵形式）

• 按照ALS算法的流程，需要先固定矩阵$U_{m,k}$

  • 此处数据中：m=5，n=4。我们假定 k=3，并随机充填矩阵$U_{5,3}$
  • 得到的矩阵$U_{5,3}$，如下

    user/k	k1	k2	k3
    用户1	3	5	6
    用户2	4	3	3
    用户3	2	5	3
    用户4	6	2	2
    用户5	5	3	4

• 此时，已知矩阵$A_{5,4}$部分值(稀疏)、矩阵$U_{5,3}$所有值，需要求解矩阵$V_{3,4}$

  • 未知矩阵$V_{3,4}$，如下

    k/item	商品1	商品2	商品3	商品4
    k1	w11	w12	w13	w14
    k2	w21	w22	w23	w24
    k3	w31	w32	w33	w34

• 那么该如何求解呢？不急，我们先看看矩阵乘法计算公式，$U_{5,3}\ast V_{3,4}=A_{5,4}$的示例如下

  • 商品1与所有用户的计算，如下
    • $3\ast w_{11}+5\ast w_{21}+6\ast w_{31}=9$
    • $4\ast w_{11}+3\ast w_{21}+3\ast w_{31}=3$
    • $2\ast w_{11}+5\ast w_{21}+3\ast w_{31}=缺失值$
    • $6\ast w_{11}+2\ast w_{21}+2\ast w_{31}=9$
    • $5\ast w_{11}+3\ast w_{21}+4\ast w_{31}=8$
  • 商品2与所有用户的计算，如下
    • $3\ast w_{12}+5\ast w_{22}+6\ast w_{32}=缺失值$
    • $4\ast w_{12}+3\ast w_{22}+3\ast w_{32}=9$
    • $2\ast w_{12}+5\ast w_{22}+3\ast w_{32}=缺失值$
    • $6\ast w_{12}+2\ast w_{22}+2\ast w_{32}=8$
    • $5\ast w_{12}+3\ast w_{22}+4\ast w_{32}=7$
  • 其他同理…

• 从每个商品与所有用户的计算公式中，不难发现一个商品的所有w值与其他商品的w值无关！因此，不同商品的w值计算，我们可以分开来做。

• 回想一下，机器学习中的线性回归！同理，我们可以将求一个商品的多个w值看作多元线性回归：

  • 例如求商品1的多个w值
    • 矩阵$V_{3,4}$中的第一列的$w_{11}$、$w_{21}$、$w_{31}$是待求的系数
    • 矩阵$U_{5,3}$中的所有行的值是用于训练的数据
    • 矩阵$A_{5,4}$中第一列的9、3、缺失值、9、8是标签数据
    • 注意：标签为缺失值的部分，即待预测的值，不参与计算
  • 其他商品同理

• 因此，我们可以利用线性回归（ALS中是最小二乘法）求出所有商品的w值，即得到矩阵$V_{3,4}$

• 接着，固定矩阵$V_{3,4}$，反过来求解矩阵$U_{5,3}$

• 如此反复的进行多次求值

• 直到$U_{5,3}\ast V_{3,4}$得到得矩阵与矩阵$A_{5,4}$的损失小于某个阈值（或是达到一定次数），既可完成求解

• 最终，推荐算法使用时，利用求得的矩阵$U_{5,3}\ast V_{3,4}$，可以预测出用户对未购买过的商品的喜好程度，从而进行推荐！

• Spark ALS模型使用示例：《Spark高级数据分析》——音乐推荐（ALS算法）

LFM梯度下降算法-示例

• 导包

  import numpy as np
  import pandas as pd
  

• 准备User-Item数据

  # 定义User-Item稀疏矩阵
  # 0代表矩阵的缺失值
  R = np.array(
      [[8, 9, 2, 2,0, 1],
      [3, 2, 5, 6, 0, 0],
      [8, 8, 0, 3, 7, 2],
      [3, 3, 0, 8, 8, 1],
      [7, 0, 3, 2, 5, 9],
      [0, 2, 2, 6, 7, 1],
      [8, 0, 3, 0, 4, 0],
      [3, 9, 0, 8, 6, 8],
      [3, 2, 5, 0, 8, 0],
      [6, 2, 3, 8, 0, 7]]
  )
  

• LFM梯度下降算法

  def lfm_gradient_descent(R, k=3, steps=1000, alpha=0.001, lam=0.0001):
      """
      LFM梯度下降算法
      
      :param R: 原始稀疏矩阵 User-Item
      :param k: User与Item之间的隐含特征个数
      :param steps: 最大迭代次数
      :param alpha: 学习曲率
      :param lam: 正则化系数
      """
      
      m = len(R)
      n = len(R[0])
      
      # 随机初始化矩阵U，V
      P = np.random.rand(m, k)
      Q =  np.random.rand(k, n)
      
      # 最大迭代steps次
      for step in range(steps):
          # 修正矩阵P、Q
          for user in range(m):
              for item in range(n):
                  # 跳过稀疏矩阵A的缺失值部分
                  if R[user][item] > 0:
                      # 误差
                      error = np.dot(P[user,:], Q[:, item]) - R[user][item]
                      # 利用误差error更新矩阵P、Q
                      for i in range(k):
                          P[user][i] -= alpha * (2 * error * Q[i][item] + 2 * lam * P[user][i])
                          Q[i][item] -= alpha * (2 * error * P[user][i] + 2 * lam * Q[i][item])
          # 计算新矩阵与原始稀疏矩阵的损失
          # newR = np.dot(P, Q)
          cost = 0
          for user in range(m):
              for item in range(n):
                  if R[user][item] > 0:
                 		# 损失
                      cost += (np.dot(P[user,:], Q[:,item]) - R[user][item]) ** 2
                      # 正则化
                      cost += lam * sum(P[user,:]**2) + lam * sum(Q[:,item]**2)
                             
          # 达到阈值，跳出迭代
          if cost < 0.5:
              break;
              
      return P,Q
  

• 调用算法与结果展示

  P,Q = lfm_gradient_descent(R, 4, 10000, 0.005, 0.0005)
  
  print("--------- 矩阵P ---------")
  print(P)
  print("--------- 矩阵Q ---------")
  print(Q)
  print("--------- 新矩阵P*Q ---------")
  print(np.dot(P, Q))
  print("--------- 原始稀疏矩阵R ---------")
  print(R)
  

• 打印结果展示

  --------- 矩阵P ---------
  [[ 2.47101945 -0.09314859  1.38122566  0.23276072]
   [-0.4175392   0.88409428  0.62463847  2.39820982]
   [ 2.10106116  0.1731982   1.56076663  0.37699979]
   [ 0.98266167  2.10821349  0.74604873  0.13698655]
   [ 0.46591391 -0.45260323  1.54408459  1.95285085]
   [ 0.62855731  1.56571349  1.05862982  0.00706062]
   [ 0.95726687 -1.11403965  1.48064885  2.10244858]
   [ 1.97143103  1.32056111 -0.72112522  2.56245347]
   [ 0.07027225  2.03254073  0.78322988  1.50645914]
   [-0.04846877  1.64219853  2.02188288  1.15083635]]
   --------- 矩阵Q ---------
  [[ 1.58242819  3.19303543  0.95667258  0.48655993  1.21054208 -0.6060828 ]
   [-0.35870851 -0.34836087  1.15881715  3.27881658  2.32052529  0.09664613]
   [ 2.78744452  0.53842092 -0.49708206  0.58858015  2.40623536  1.15769018]
   [ 0.92791198  1.38316166  1.951467    1.22337834  0.88932108  3.86373607]]
   --------- 新矩阵P*Q ---------
  [[ 8.00969538  8.98812847  2.02365673  1.99459832  6.30567239  0.99171252]
   [ 2.98861476  2.01222899  4.99458605  5.99719289  5.1819201  10.32769524]
   [ 7.96302376  8.0102283   2.17060619  2.97002692  7.03617947  2.0068338 ]
   [ 3.0054383   2.99441722  3.2795967   7.99726497  7.99870986  1.00114949]
   [ 7.01575177  5.17782475  2.96462993  2.04058504  4.96587355  9.00674711]
   [ 3.39043557  2.04132685  1.90325185  6.07124444  6.94776448  1.02320811]
   [ 7.99253533  7.14991343  2.99167776  0.2566066   4.00619612  9.14958844]
   [ 3.01358624  8.99083579  8.77530468  7.99950709  5.99454255  7.99858102]
   [ 2.96318244  2.02170798  4.97304635  9.00248294  8.02599098  6.88114446]
   [ 6.03799225  1.95357653  3.09741652  7.9588332   9.64067885  6.97533011]]
   --------- 原始稀疏矩阵R ---------
  [[8 9 2 2 0 1]
   [3 2 5 6 0 0]
   [8 8 0 3 7 2]
   [3 3 0 8 8 1]
   [7 0 3 2 5 9]
   [0 2 2 6 7 1]
   [8 0 3 0 4 0]
   [3 9 0 8 6 8]
   [3 2 5 0 8 0]
   [6 2 3 8 0 7]]