推薦算法之用矩陣分解做協調過濾——LFM模型

隱語義模型(Latent factor model,以下簡稱LFM),是基於矩陣分解的推薦算法,在其基本算法上引入L2正則的FunkSVD算法在推薦系統領域更是廣泛使用,在Spark上也有其實現。本文將對 LFM原理進行詳細闡述,給出其基本算法原理。此外,還將介紹使得隱語義模型聲名大噪的算法FunkSVD和在其基礎上改進較為成功的BiasSVD。最後,對LFM進行一個較為全面的總結。

1. 矩陣分解應用於推薦算法要解決的問題

在推薦系統中,我們經常可能面臨的場景是:現有大量用戶和物品,以及少部分用戶對少部分物品的評分,我們需要使用現有的用戶對少部分物品的評分去推測用戶對物品集中其他物品的可能的評分,從而將預測中評分高的物品推薦給用戶。例如下面的用戶物品評分表:

用戶\物品 物品 1 物品 2 物品 3 物品 4 物品 5
用戶 1 3 2
用戶 2 1 2 6
用戶 3 3 4 6
用戶 4 1 2 5
用戶 5 4 2 3

對於每個用戶,我們希望較準確的預測出其對未評分物品的評分。將m個用戶和n個物品的評分看做一個矩陣M,從而將矩陣分解應用到該場景,即可解決這一問題。而本文,將關注於矩陣分解用於到推薦的方法之一,即LFM算法的解決方案。

2. LFM

LFM算法的核心思想是通過隱含特徵(Latent factor)聯繫用戶和物品,該算法最早在文本挖掘領域中被提出用於找到文本的隱含語義,相關名詞還有LDATopic Model等。

2.1 如何表示用戶的偏好和物品(item)屬性?

在被問到這個問題時,針對MovieLens(電影評分)數據集,你可能會說用戶是否喜歡動作片,物品所屬電影類型去回答。但用戶對其他類型的電影的偏好程度呢?物品在其它類型所佔的權重又是多少呢?就算針對現有的電影類型去表徵用戶偏好和物品,那麼能否能夠完全的表示出用戶的偏好和物品屬性呢?答案是不能,比如用戶喜歡看成龍的電影這個偏好沒法表示出來,電影由誰導演,主演是誰沒法表示。但你要問我用哪些屬性去表徵呢?這個誰也無法給出一個很好的答案,粒度很難控制。

2.2 LFM來救場

隱語義模型較好的解決了該問題,它從數據出發,通過基於用戶行為統計的自動聚類,可指定出表徵用戶偏好和物品的向量維度,最終得到用戶的偏好向量以及物品的表徵向量。LFM通過以下公式計算用戶u對物品i的偏好:
\[ preference(u, i)=p^T_u q_i=\sum_f^F{p_{u,k}q_{i,k}} \]
這個公式,\(p_{u,k}\)度量了用戶u的偏好和第f個隱類的關係,\(q_{i,k}\)度量了物品i和第f個隱類的關係。

那麼現在,我們期望用戶的評分矩陣M這樣分解:
\[ M_{m*n}=P^T_{m*k}Q_{k*n} \]
那麼,我們如何將矩陣分解呢?這裏採用了線性回歸的思想,即盡可能的讓用戶的評分和我們預測的評分的殘差盡可能小,也就是說,可以用均方差作為損失函數來尋找最終的PQ。考慮所有的用戶和樣本的組合,我們期望的最小化損失函數為:
\[ \sum_{i,j}{(m_{ij}-p_i^Tq_j)^2} \]
只要我們能夠最小化上面的式子,並求出極值所對應的\(p_i\)\(q_j\),則我們最終可以得到矩陣PQ,那麼對於任意矩陣M任意一個空白評分的位置,我們就可以通過\(p^T_i q_j\)計算預測評分。

2.3 FunkSVD用於推薦

上面是隱語義模型LFM的基本原理,但在實際業務中,為防止過擬合,我們常常會加入一個L2的正則化項,這也就誕生了我們的FunkSVD算法。其優化目標函數\(J(p,q)\)定義為:
\[ \underbrace{argmin}_{p_i,q_j}\sum_{i,j}{(m_{ij}-p^T_iq_j)^2+\lambda({\Arrowvert{p_i}\Arrowvert}^2_2+{\Arrowvert{q_i}\Arrowvert}^2_2)} \]
其中λ為正則化係數,需要調參。對於這個優化問題,我們一般通過梯度下降法來進行優化得到結果。

將上式分別對\(p_i\)\(q_j\)求導我們得到:
\[ \frac{\partial{J}}{\partial{p_i}}=-2(m_{ij}-p^T_iq_j)q_j+2\lambda{p_i} \]

\[ \frac{\partial{J}}{\partial{q_j}}=-2(m_{ij}-p^T_iq_j)p_i+2\lambda{q_j} \]

則梯度下降中迭代公式為:
\[ p_i = p_i +\alpha((m_{ij}-p^T_iq_j)q_j-\lambda{p_i}) \]

\[ q_j = q_j+\alpha((m_{ij}-p^T_iq_j)p_i-\lambda{q_j}) \]

通過迭代我們最終可以得到PQ,進而用於推薦。

為讀者進一步理解,筆者實現了基於MovieLens數據集實現了該方法。代碼詳見github:

2.4 BiasSVD用於推薦

BiasSVDFunkSVD較為成功的改進版算法。BiasSVD假設評分系統包括三部分的偏置因素:一些和用戶物品無關的評分因素。用戶有一些和物品無關的評分因素,稱為用戶偏置項。而物品也有一些和用戶無關的評分因素,稱為物品偏置項。這很好理解,對於樂觀的用戶來說,它的評分行為普遍偏高,而對批判性用戶來說,他的評分記錄普遍偏低,即使他們對同一物品的評分相同,但是他們對該物品的喜好程度卻並不一樣。同理,對物品來說,以電影為例,受大眾歡迎的電影得到的評分普遍偏高,而一些爛片的評分普遍偏低,這些因素都是獨立於用戶或產品的因素,而和用戶對產品的的喜好無關。

假設評分系統平均分為μ,第i個用戶的用戶偏置項為\(b_i\),而第j個物品的物品偏置項為\(b_j\),則加入了偏置項以後的優化目標函數\(J(p_i,q_j)\)是這樣的:
\[ \underbrace{argmin}_{p_i,q_j}\sum_{i,j}{(m_{ij}-p^T_iq_j-u-b_i-b_j)^2+\lambda({\Arrowvert{p_i}\Arrowvert}^2_2+{\Arrowvert{q_i}\Arrowvert}^2_2+{\Arrowvert{b_i}\Arrowvert}^2_2+{\Arrowvert{b_j}\Arrowvert}^2_2)} \]
這個優化目標也可以採用梯度下降法求解。和FunkSVD不同的是,此時我們多了兩個偏執項\(b_i\)\(b_j\)\(p_i\)\(q_j\)的迭代公式和FunkSVD類似,只是每一步的梯度導數稍有不同而已。\(b_i\)\(b_j\)一般可以初始設置為0,然後參与迭代。迭代公式為:
\[ p_i = p_i +\alpha((m_{ij}-p^T_iq_j-u-b_i-b_j)q_j-\lambda{p_i}) \]

\[ q_j = q_j+\alpha((m_{ij}-p^T_iq_j-u-b_i-b_j)p_i-\lambda{q_j}) \]

\[ b_i=b_i+\alpha(m_{ij}-p^T_iq_j-u-b_i-b_j-\lambda{b_i}) \]

\[ b_j=b_j+\alpha(m_{ij}-p^T_iq_j-u-b_i-b_j-\lambda{b_j}) \]

通過迭代我們最終可以得到PQ,進而用於推薦。BiasSVD增加了一些額外因素的考慮,因此在某些場景會比FunkSVD表現好。

為讀者進一步理解,筆者實現了基於MovieLens數據集實現了該方法。代碼詳見github

小結

LFM 是一種基於機器學習的方法,具有比較好的理論基礎,通過優化一個設定的指標建立最優的模型。它實質上是矩陣分解應用到推薦的方法,其中FunkSVD更是將矩陣分解用於推薦方法推到了新的高度,在實際應用中使用非常廣泛。當然矩陣分解方法也在不停的進步,目前矩陣分解推薦算法中分解機方法(factorization machine, FM)已成為一個趨勢。

對於矩陣分解用於推薦方法本身來說,它容易編程實現,實現複雜度低,預測效果也好,同時還能保持擴展性。這些都是其寶貴的優點。但是LFM 無法給出很好的推薦解釋,它計算出的隱類雖然在語義上確實代表了一類興趣和物品,卻很難用自然語言描述並生成解釋展現給用戶。

LFM 在建模過程中,假設有 M 個用戶、 N 個物品、 K 條用戶對物品的行為記錄,如果是 F 個隱類,那麼它離線計算的空間複雜度是 \(O(F*(M+N))\) ,迭代 S次則時間複雜度為 \(O(K * F * S)\)。當 M(用戶數量)和 N(物品數量)很大時LFM相對於ItemCFUserCF可以很好地節省離線計算的內存,在時間複雜度由於LFM會多次迭代上所以和ItemCFUserCF沒有質的差別。

同時,遺憾的是,LFM 無法進行在線實時推薦,即當用戶有了新的行為後,他的推薦列表不會發生變化。而從 LFM的預測公式可以看到, LFM 在給用戶生成推薦列表時,需要計算用戶對所有物品的興趣權重,然後排名,返回權重最大的 N 個物品。那麼,在物品數很多時,這一過程的時間複雜度非常高,可達 \(O(M*N*F)\) 。因此, LFM 不太適合用於物品數非常龐大的系統,如果要用,我們也需要一個比較快的算法給用戶先計算一個比較小的候選列表,然後再用LFM重新排名。另一方面,LFM 在生成一個用戶推薦列表時速度太慢,因此不能在線實時計算,而需要離線將所有用戶的推薦結果事先計算好存儲在數據庫中。

參考:

  • 推薦系統實戰—項亮

(歡迎轉載,轉載請註明出處。歡迎溝通交流: losstie@outlook.com)

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※廣告預算用在刀口上,網站設計公司幫您達到更多曝光效益

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

您可能也會喜歡…