文章目錄
- 推薦算法——ALS模型算法分析、LFM算法
-
- 簡介
- ALS算法流程分析
- LFM梯度下降算法-示例
推薦算法——ALS模型算法分析、LFM算法
簡介
- ALS(Alternating Least Squares)，即交替最小二乘法，因利用兩個矩陣進行交替優化而得名。求解大緻步驟如下：
- 定義原始矩陣 A m , n = U m , k ∗ V k , n A_{m,n} = U_{m,k} * V_{k,n} Am,n=Um,k∗Vk,n
- 為 U m , k U_{m,k} Um,k随機取值，固定 U m , k U_{m,k} Um,k，利用最小二乘法求出 V k , n V_{k,n} Vk,n
- 固定 V k , n V_{k,n} Vk,n，利用最小二乘法求出 U m , k U_{m,k} Um,k
- 持續交替進行求解，直到損失達到門檻值（即新矩陣近似于原始矩陣）
- 比較經典的應用則是隐語義分析-推薦算法：原始矩陣為稀疏矩陣，通過ALS計算出的新矩陣則擁有原始矩陣缺失的值，即預測值。
ALS算法流程分析
- 資料（矩陣 A m n A_{mn} Amn）
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 A_{m,n} Am,n中的缺失值。
- 利用ALS算法，将稀疏矩陣 A m , n A_{m,n} Am,n拆解為兩個矩陣 U m , k U_{m,k} Um,k 、 V k , n V_{k,n} Vk,n，即 A m , n = U m , k ∗ V k , n A_{m,n} = U_{m,k} * V_{k,n} Am,n=Um,k∗Vk,n
- k代表了使用者與商品的隐含關聯特征個數，需要使用者指定
- U m , k U_{m,k} Um,k代表了使用者與k個隐含特征的值
- V k , n V_{k,n} Vk,n代表了商品與k個隐含特征的值（不過是逆矩陣形式）
- 按照ALS算法的流程，需要先固定矩陣 U m , k U_{m,k} Um,k
- 此處資料中：m=5，n=4。我們假定 k=3，并随機充填矩陣 U 5 , 3 U_{5,3} U5,3
- 得到的矩陣 U 5 , 3 U_{5,3} U5,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 A_{5,4} A5,4部分值(稀疏)、矩陣 U 5 , 3 U_{5,3} U5,3所有值，需要求解矩陣 V 3 , 4 V_{3,4} V3,4
- 未知矩陣 V 3 , 4 V_{3,4} V3,4，如下
k/item 商品1 商品2 商品3 商品4 k1 w11 w12 w13 w14 k2 w21 w22 w23 w24 k3 w31 w32 w33 w34
- 未知矩陣 V 3 , 4 V_{3,4} V3,4，如下
- 那麼該如何求解呢？不急，我們先看看矩陣乘法計算公式， U 5 , 3 ∗ V 3 , 4 = A 5 , 4 U_{5,3} * V_{3,4} = A_{5,4} U5,3∗V3,4=A5,4的示例如下
- 商品1與所有使用者的計算，如下
- 3 ∗ w 11 + 5 ∗ w 21 + 6 ∗ w 31 = 9 3 * w_{11} + 5 * w_{21} + 6 * w_{31} = 9 3∗w11+5∗w21+6∗w31=9
- 4 ∗ w 11 + 3 ∗ w 21 + 3 ∗ w 31 = 3 4 * w_{11} + 3 * w_{21} + 3 * w_{31} = 3 4∗w11+3∗w21+3∗w31=3
- 2 ∗ w 11 + 5 ∗ w 21 + 3 ∗ w 31 = 缺 失 值 2 * w_{11} + 5 * w_{21} + 3 * w_{31} = 缺失值 2∗w11+5∗w21+3∗w31=缺失值
- 6 ∗ w 11 + 2 ∗ w 21 + 2 ∗ w 31 = 9 6 * w_{11} + 2 * w_{21} + 2 * w_{31} = 9 6∗w11+2∗w21+2∗w31=9
- 5 ∗ w 11 + 3 ∗ w 21 + 4 ∗ w 31 = 8 5 * w_{11} + 3 * w_{21} + 4 * w_{31} = 8 5∗w11+3∗w21+4∗w31=8
- 商品2與所有使用者的計算，如下
- 3 ∗ w 12 + 5 ∗ w 22 + 6 ∗ w 32 = 缺 失 值 3 * w_{12} + 5 * w_{22} + 6 * w_{32} = 缺失值 3∗w12+5∗w22+6∗w32=缺失值
- 4 ∗ w 12 + 3 ∗ w 22 + 3 ∗ w 32 = 9 4 * w_{12} + 3 * w_{22} + 3 * w_{32} = 9 4∗w12+3∗w22+3∗w32=9
- 2 ∗ w 12 + 5 ∗ w 22 + 3 ∗ w 32 = 缺 失 值 2 * w_{12} + 5 * w_{22} + 3 * w_{32} = 缺失值 2∗w12+5∗w22+3∗w32=缺失值
- 6 ∗ w 12 + 2 ∗ w 22 + 2 ∗ w 32 = 8 6 * w_{12} + 2 * w_{22} + 2 * w_{32} = 8 6∗w12+2∗w22+2∗w32=8
- 5 ∗ w 12 + 3 ∗ w 22 + 4 ∗ w 32 = 7 5 * w_{12} + 3 * w_{22} + 4 * w_{32} = 7 5∗w12+3∗w22+4∗w32=7
- 其他同理…
- 商品1與所有使用者的計算，如下
- 從每個商品與所有使用者的計算公式中，不難發現一個商品的所有w值與其他商品的w值無關！是以，不同商品的w值計算，我們可以分開來做。
- 回想一下，機器學習中的線性回歸！同理，我們可以将求一個商品的多個w值看作多元線性回歸：
- 例如求商品1的多個w值
- 矩陣 V 3 , 4 V_{3,4} V3,4中的第一列的 w 11 w_{11} w11、 w 21 w_{21} w21、 w 31 w_{31} w31是待求的系數
- 矩陣 U 5 , 3 U_{5,3} U5,3中的所有行的值是用于訓練的資料
- 矩陣 A 5 , 4 A_{5,4} A5,4中第一列的9、3、缺失值、9、8是标簽資料
- 注意：标簽為缺失值的部分，即待預測的值，不參與計算
- 其他商品同理
- 例如求商品1的多個w值
- 是以，我們可以利用線性回歸（ALS中是最小二乘法）求出所有商品的w值，即得到矩陣 V 3 , 4 V_{3,4} V3,4
- 接着，固定矩陣 V 3 , 4 V_{3,4} V3,4，反過來求解矩陣 U 5 , 3 U_{5,3} U5,3
- 如此反複的進行多次求值
- 直到 U 5 , 3 ∗ V 3 , 4 U_{5,3} * V_{3,4} U5,3∗V3,4得到得矩陣與矩陣 A 5 , 4 A_{5,4} A5,4的損失小于某個門檻值（或是達到一定次數），既可完成求解
- 最終，推薦算法使用時，利用求得的矩陣 U 5 , 3 ∗ V 3 , 4 U_{5,3} * V_{3,4} U5,3∗V3,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]]
![27. Remove Element(清單)題目代碼[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)