如何解釋spark mllib中ALS演算法的原理?

ALS交替最小二乘法的協同過濾演算法,其原理是什麼,演算法的思想是怎樣的?找了好久的資料都是一大堆專業名詞和公式看著比較費力,有沒有大大能用比較通俗的語言描述一下ALS演算法


整理一下自己的理解。

對於一個users-products-rating的評分數據集,ALS會建立一個user*product的m*n的矩陣

其中,m為users的數量,n為products的數量

但是在這個數據集中,並不是每個用戶都對每個產品進行過評分,所以這個矩陣往往是稀疏的,用戶i對產品j的評分往往是空的

ALS所做的事情就是將這個稀疏矩陣通過一定的規律填滿,這樣就可以從矩陣中得到任意一個user對任意一個product的評分,ALS填充的評分項也稱為用戶i對產品j的預測得分

所以說,ALS演算法的核心就是通過什麼樣子的規律來填滿(預測)這個稀疏矩陣

它是這麼做的:

假設m*n的評分矩陣R,可以被近似分解成U*(V)T

U為m*d的用戶特徵向量矩陣

V為n*d的產品特徵向量矩陣((V)T代表V的轉置,原諒我不會打轉置這個符號。。)

d為user/product的特徵值的數量

關於d這個值的理解,大概可以是這樣的

對於每個產品,可以從d個角度進行評價,以電影為例,可以從主演,導演,特效,劇情4個角度來評價一部電影,那麼d就等於4

可以認為,每部電影在這4個角度上都有一個固定的基準評分值

例如《末日崩塌》這部電影是一個產品,它的特徵向量是由d個特徵值組成的

d=4,有4個特徵值,分別是主演,導演,特效,劇情

每個特徵值的基準評分值分別為(滿分為1.0):

主演:0.9(大光頭還是那麼霸氣)

導演:0.7

特效:0.8

劇情:0.6

矩陣V由n個product*d個特徵值組成

對於矩陣U,假設對於任意的用戶A,該用戶對一部電影的綜合評分和電影的特徵值存在一定的線性關係,即電影的綜合評分=(a1*d1+a2*d2+a3*d3+a4*d4)

其中a1-4為用戶A的特徵值,d1-4為之前所說的電影的特徵值

參考:

協同過濾中的矩陣分解演算法研究

那麼對於之前ALS演算法的這個假設

m*n的評分矩陣R,可以被近似分解成U*(V)T

就是成立的,某個用戶對某個產品的評分可以通過矩陣U某行和矩陣V(轉置)的某列相乘得到

那麼現在的問題是,如何確定用戶和產品的特徵值?(之前僅僅是舉例子,實際中這兩個都是未知的變數)

採用的是交替的最小二乘法

在上面的公式中,a表示評分數據集中用戶i對產品j的真實評分,另外一部分表示用戶i的特徵向量(轉置)*產品j的特徵向量(這裡可以得到預測的i對j的評分)

用真實評分減去預測評分然後求平方,對下一個用戶,下一個產品進行相同的計算,將所有結果累加起來(其中,數據集構成的矩陣是存在大量的空打分,並沒有實際的評分,解決的方法是就只看對已知打分的項)

參考:

ALS 在 Spark MLlib 中的實現

但是這裡之前問題還是存在,就是用戶和產品的特徵向量都是未知的,這個式子存在兩個未知變數

解決的辦法是交替的最小二乘法

首先對於上面的公式,以下面的形式顯示:

為了防止過度擬合,加上正則化參數

首先用一個小於1的隨機數初始化V

根據公式(4)求U

此時就可以得到初始的UV矩陣了,計算上面說過的差平方和

根據計算得到的U和公式(5),重新計算並覆蓋V,計算差平方和

反覆進行以上兩步的計算,直到差平方和小於一個預設的數,或者迭代次數滿足要求則停止

取得最新的UV矩陣

則原本的稀疏矩陣R就可以用R=U(V)T來表示了

以上公式內容截圖來自:

基於矩陣分解的協同過濾演算法

總結一下:

ALS演算法的核心就是將稀疏評分矩陣分解為用戶特徵向量矩陣和產品特徵向量矩陣的乘積

交替使用最小二乘法逐步計算用戶/產品特徵向量,使得差平方和最小

通過用戶/產品特徵向量的矩陣來預測某個用戶對某個產品的評分

不知道是不是理解正確了

有幾個問題想請教一下~

(1)在第一個公式中加入正則化參數是啥意思?為什麼是那種形態的?

(2)固定一個矩陣U,求偏導數之後可以得到求解V的公式,為什麼?


在ml中常見的優化演算法基本都是:

  • sgd 這種對每個單變數進行同步更新

  • als(交替最小二乘)/smo(序列最小優化)這種交替(固定一個單變數,優化另一個單變數)思路。如果你熟悉smo,那麼als就也可以理解了。
  • 其它(希望更多的人補充)


推薦看看Coursera上Andrew NG大神的machine learning課程, 裡面week9講了collaborative-filtering: https://www.coursera.org/learn/machine-learning/lecture/2WoBV/collaborative-filtering, 這裡有一篇文字總結基於協同過濾演算法的推薦系統


有一個事情,遍歷全網都沒有得到回答. 我想問一下,在用spark mllib 跑 movie推薦的時候, 最高分數為5分,最低分數為0分. 但是用spark跑出的預測,竟然很多的 8分 9分, 為啥會這麼高 嘞. 這也不符合推薦的需求啊...那位仁兄能否給講解下呢? 另外如何才能限制分數呢?


推薦閱讀:

關於Spark有哪些大牛們的博客?
有什麼關於 Spark 的書推薦?
想研讀下spark的源碼,怎麼搭閱讀和調試的環境呢?
如何高效閱讀 Spark 和 Hadoop 這類大型開源項目源代碼?有什麼工具可以藉助?
第四範式的人工智慧平台 Prophet 有可能替代 Spark 么?

TAG:演算法 | 協同過濾 | Spark |