推薦系統(tǒng)-協(xié)同過(guò)濾在Spark中的實(shí)現(xiàn)
作者 ｜ vivo 互聯(lián)網(wǎng)服務(wù)器團(tuán)隊(duì)-Tang Shutao
現(xiàn)如今推薦無(wú)處不在，例如抖音、淘寶、京東App均能見(jiàn)到推薦系統(tǒng)的身影，其背后涉及許多的技術(shù)。
本文以經(jīng)典的協(xié)同過(guò)濾為切入點(diǎn)，重點(diǎn)介紹了被工業(yè)界廣泛使用的矩陣分解算法，從理論與實(shí)踐兩個(gè)維度介紹了該算法的原理，通俗易懂，希望能夠給大家?guī)?lái)一些啟發(fā)。
筆者認(rèn)為要徹底搞懂一篇論文，最好的方式就是動(dòng)手復(fù)現(xiàn)它，復(fù)現(xiàn)的過(guò)程你會(huì)遇到各種各樣的疑惑、理論細(xì)節(jié)。
一、 背景
1.1 引言
在信息爆炸的二十一世紀(jì)，人們很容易淹沒(méi)在知識(shí)的海洋中，在該場(chǎng)景下搜索引擎可以幫助我們迅速找到我們想要查找的內(nèi)容。
在電商場(chǎng)景，如今的社會(huì)物質(zhì)極大豐富，商品琳瑯滿(mǎn)目，種類(lèi)繁多。消費(fèi)者很容易挑花眼，即用戶(hù)將會(huì)面臨信息過(guò)載的問(wèn)題。
為了解決該問(wèn)題，推薦引擎應(yīng)運(yùn)而生。例如我們打開(kāi)淘寶App，JD app，B站視頻app，每一個(gè)場(chǎng)景下都有推薦的模塊。
那么此時(shí)有一個(gè)幼兒園小朋友突然問(wèn)你，為什么JD給你推薦這本《程序員頸椎康復(fù)指南》？你可能會(huì)回答，因?yàn)槲业穆殬I(yè)是程序員。
接著小朋友又問(wèn)，為什么《Spark大數(shù)據(jù)分析》這本書(shū)排在第6個(gè)推薦位，而《Scala編程》排在第2位？這時(shí)你可能無(wú)法回答這個(gè)問(wèn)題。
為了回答該問(wèn)題，我們?cè)O(shè)想下面的場(chǎng)景：
在JD的電商系統(tǒng)中，存在著用戶(hù)和商品兩種角色，并且我們假設(shè)用戶(hù)都會(huì)對(duì)自己購(gòu)買(mǎi)的商品打一個(gè)0-5之間的分?jǐn)?shù)，分?jǐn)?shù)越高代表越喜歡該商品。
基于此假設(shè)，我們將上面的問(wèn)題轉(zhuǎn)化為用戶(hù)對(duì)《程序員頸椎康復(fù)指南》，《Spark大數(shù)據(jù)分析》，《Scala編程》這三本書(shū)打分的話(huà)，用戶(hù)會(huì)打多少分（用戶(hù)之前未購(gòu)買(mǎi)過(guò)這3本書(shū)）。因此物品在頁(yè)面的先后順序就等價(jià)于預(yù)測(cè)用戶(hù)對(duì)這些物品的評(píng)分，并且根據(jù)這些評(píng)分進(jìn)行排序的問(wèn)題。
為了便于預(yù)測(cè)用戶(hù)對(duì)物品的評(píng)分問(wèn)題，我們將所有三元組(User, Item, Rating)，即用戶(hù)User給自己購(gòu)買(mǎi)的商品Item的評(píng)分為Rating，組織為如下的矩陣形式：
其中，表格包含 m 個(gè)用戶(hù)和n個(gè)物品，將表格定義為評(píng)分矩陣 Rm×nRm×n ，其中的元素 ru,iru,i 表示第u個(gè)用戶(hù)對(duì)第i個(gè)物品的評(píng)分。
例如，在上面的表格中，用戶(hù)user-1購(gòu)買(mǎi)了物品 item-1， item-3， item-4，并且分別給出了4，2，5的評(píng)分。最終，我們將原問(wèn)題轉(zhuǎn)化為預(yù)測(cè)白色空格處的數(shù)值。
1.2 協(xié)同過(guò)濾
協(xié)同過(guò)濾，簡(jiǎn)單來(lái)說(shuō)是利用與用戶(hù)興趣相投、擁有共同經(jīng)驗(yàn)之群體的喜好來(lái)推薦給用戶(hù)感興趣的物品。興趣相投使用數(shù)學(xué)語(yǔ)言來(lái)表達(dá)就是相似度 (人與人，物與物)。因此，根據(jù)相似度的對(duì)象，協(xié)同過(guò)濾可以分為基于用戶(hù)的協(xié)同過(guò)濾和基于物品的協(xié)同過(guò)濾。
以評(píng)分矩陣為例，以行方向觀測(cè)評(píng)分矩陣，每一行代表每個(gè)用戶(hù)的向量表示，例如用戶(hù)user-1的向量為 [4, 0, 2, 5, 0, 0]。以列方向觀測(cè)評(píng)分矩陣，每一列表示每個(gè)物品的向量表示，例如物品item-1的向量為[4, 3, 0, 0, 5]。
基于向量表示，相似度的計(jì)算有多種公式，例如余弦相似度，歐氏距離，皮爾森。這里我們以余弦相似度為例，它是我們中學(xué)學(xué)過(guò)的向量夾角 (中學(xué)只涉及2維和3維) 的高維推廣，余弦相似度公式很容易理解和使用。給定兩個(gè)向量 A={a1,?,an}A={a1,?,an} 和?B={b1,?,bn}B={b1,?,bn} ，其夾角定義如下：
例如，我們計(jì)算user-3和user-4的余弦相似度，二者對(duì)應(yīng)的向量分別為 [0, 2, 0, 3, 0, 4]，[0, 3, 3, 5, 4, 0]
向量夾角的余弦值越接近1代表兩個(gè)物品方向越接近平行，也就是越相似，反之越接近-1代表兩個(gè)物品方向越接近反向，表示兩個(gè)物品相似度接近相反，接近0，表示向量接近垂直/正交，兩個(gè)物品幾乎無(wú)關(guān)聯(lián)。顯然，這和人的直覺(jué)完全一致。
例如，我們?cè)谝曨lApp中經(jīng)常能看到"相關(guān)推薦"模塊，其背后用到的原理之一就是相似度計(jì)算，下圖展示了一個(gè)具體的例子。
我們用《血族第一部》在向量庫(kù) (存儲(chǔ)向量的數(shù)據(jù)庫(kù)，該系統(tǒng)能夠根據(jù)輸入向量，用相似度公式在庫(kù)中進(jìn)行檢索，找出TopN的候選向量) 里面進(jìn)行相似度檢索，找到了前7部高相似度的影片，值得注意的是第一部是自己本身，相似度為1.0，其他三部是《血族》的其他3部同系列作品。
1.2.1 基于用戶(hù)的協(xié)同過(guò)濾 (UserCF)
基于用戶(hù)的協(xié)同過(guò)濾分為兩步
- 找出用戶(hù)相似度TopN的若干用戶(hù)。
- 根據(jù)TopN用戶(hù)評(píng)分的物品，形成候選物品集合，利用加權(quán)平均預(yù)估用戶(hù)u對(duì)每個(gè)候選物品的評(píng)分。
例如，由用戶(hù)u的相似用戶(hù){u1, u3, u5, u9}可得候選物品為
我們現(xiàn)在預(yù)測(cè)用戶(hù)u對(duì)物品i1的評(píng)分，由于物品在兩個(gè)用戶(hù){u1, u5}的購(gòu)買(mǎi)記錄里，因此用戶(hù)u對(duì)物品i1的預(yù)測(cè)評(píng)分為：
其中sim(u,u1)sim(u,u1) 表示用戶(hù) u與用戶(hù) u1u1的相似度。
在推薦時(shí)，根據(jù)用戶(hù)u對(duì)所有候選物品的預(yù)測(cè)分進(jìn)行排序，取TopM的候選物品推薦給用戶(hù)u即可。
1.2.2 基于物品的協(xié)同過(guò)濾 (ItemCF)
基于物品的協(xié)同過(guò)濾分為兩步
- 在用戶(hù)u購(gòu)買(mǎi)的物品集合中，選取與每一個(gè)物品TopN相似的物品。
- TopN相似物品形成候選物品集合，利用加權(quán)平均預(yù)估用戶(hù)u對(duì)每個(gè)候選物品的評(píng)分。
例如，我們預(yù)測(cè)用戶(hù)u對(duì)物品i3的評(píng)分，由于物品i3與物品{i6, i1, i9}均相似，因此用戶(hù)u對(duì)物品i3的預(yù)測(cè)評(píng)分為：
其中 sim(i6,i3)sim(i6,i3) 表示物品 i6i6 與物品 i3的相似度，其他符號(hào)同理。
1.2.3 UserCF與ItemCF的比較
我們對(duì)ItemCF和UserCF做如下總結(jié)：
UserCF主要用于給用戶(hù)推薦那些與之有共同興趣愛(ài)好的用戶(hù)喜歡的物品，其推薦結(jié)果著重于反映和用戶(hù)興趣相似的小群體的熱點(diǎn)，更社會(huì)化一些，反映了用戶(hù)所在的小型興趣群體中物品的熱門(mén)程度。在實(shí)際應(yīng)用中，UserCF通常被應(yīng)用于用于新聞推薦。
ItemCF給用戶(hù)推薦那些和他之前喜歡的物品類(lèi)似的物品，即ItemCF的推薦結(jié)果著重于維系用戶(hù)的歷史興趣，推薦更加個(gè)性化，反應(yīng)用戶(hù)自己的興趣。在實(shí)際應(yīng)用中，圖書(shū)、電影平臺(tái)使用ItemCF，比如豆瓣、亞馬遜、Netflix等。
除了基于用戶(hù)和基于物品的協(xié)同過(guò)濾，還有一類(lèi)基于模型的協(xié)同過(guò)濾算法，如上圖所示。此外基于用戶(hù)和基于物品的協(xié)同過(guò)濾又可以歸類(lèi)為基于鄰域 (K-Nearest Neighbor, KNN) 的算法，本質(zhì)都是在找"TopN鄰居"，然后利用鄰居和相似度進(jìn)行預(yù)測(cè)。
二、矩陣分解
經(jīng)典的協(xié)同過(guò)濾算法本身存在一些缺點(diǎn)，其中最明顯的就是稀疏性問(wèn)題。我們知道評(píng)分矩陣是一個(gè)大型稀疏矩陣，導(dǎo)致在計(jì)算相似度時(shí)，兩個(gè)向量的點(diǎn)積等于0 (以余弦相似度為例)。為了更直觀的理解這一點(diǎn)，我們舉例如下：
rom sklearn.metrics.pairwise import cosine_similarity
a = [
[ 0, 0, 0, 3, 2, 0, 3.5, 0, 1 ],
[ 0, 1, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 1, 0, 0, 0, 0, 0, 0 ],
[4.1, 3.8, 4.6, 3.8, 4.4, 3, 4, 0, 3.6]
]
cosine_similarity(a)
# array([[1. , 0. , 0. , 0.66209271],
# [0. , 1. , 0. , 0.34101639],
# [0. , 0. , 1. , 0.41280932],
# [0.66209271, 0.34101639, 0.41280932, 1. ]])
我們從評(píng)分矩陣中抽取item1 - item4的向量，并且利用余弦相似度計(jì)算它們之間的相似度。
通過(guò)相似度矩陣，我們可以看到物品item-1, item-2, item-3的之間的相似度均為0，而且與item-1, item-2, item-3最相似的物品都是item-4，因此在以ItemCF為基礎(chǔ)的推薦場(chǎng)景中item-4將會(huì)被推薦給用戶(hù)。
但是，物品item-4與物品item-1, item-2, item-3最相似的原因是item-4是一件熱門(mén)商品，購(gòu)買(mǎi)的用戶(hù)多，而物品item-1, item-2, item-3的相似度均為0的原因僅僅是它們的特征向量非常稀疏，缺乏相似度計(jì)算的直接數(shù)據(jù)。
綜上，我們可以看到經(jīng)典的基于用戶(hù)/物品的協(xié)同過(guò)濾算法有天然的缺陷，無(wú)法處理稀疏場(chǎng)景。為了解決該問(wèn)題，矩陣分解被提出。
2.1 顯示反饋
我們將用戶(hù)對(duì)物品的評(píng)分行為定義為顯示反饋。基于顯示反饋的矩陣分解是將評(píng)分矩陣Rm×n 用兩個(gè)矩陣 Xm×k和Yn×k的乘積近似表示，其數(shù)學(xué)表示如下：
其中， k?m/nk?m/n 表示隱性因子，以用戶(hù)側(cè)來(lái)理解，?k=2k=2 表示的就是用戶(hù)的年齡和性別兩個(gè)屬性。此外有個(gè)很好的比喻就是物理學(xué)的三棱鏡，白光在三棱鏡的作用下被分解為7種顏色的光，在矩陣分解算法中，分解的作用就類(lèi)似于"三棱鏡"，如下圖所示，因此，矩陣分解也被稱(chēng)為隱語(yǔ)義模型。矩陣分解將系統(tǒng)的自由度從 O(mn) 降到了O((m+n)k，從而實(shí)現(xiàn)了降維的目的。
為了求解矩陣?Xm×kXm×k 和Yn×k，需要最小化平方誤差損失函數(shù)，來(lái)盡可能地使得兩個(gè)矩陣的乘積逼近評(píng)分矩陣 Rm×nRm×n ，即
其中， λ(∑uxTuxu+∑iyTiyi)λ(∑uxuTxu+∑iyiTyi) 為懲罰項(xiàng)，λ為懲罰系數(shù)/正則化系數(shù)，xu表示第u個(gè)用戶(hù)的k維特征向量，yiyi 表示第 i 個(gè)物品的k維特征向量。
全體用戶(hù)的特征向量構(gòu)成了用戶(hù)矩陣 ?Xm×kXm×k ，全體物品的特征向量構(gòu)成了物品矩陣 Yn×k。
我們訓(xùn)練模型的時(shí)候，就只需要訓(xùn)練用戶(hù)矩陣中的m×k個(gè)參數(shù)和物品矩陣中的n×k個(gè)參數(shù)。因此，協(xié)同過(guò)濾就成功轉(zhuǎn)化成了一個(gè)優(yōu)化問(wèn)題。
2.2 預(yù)測(cè)評(píng)分
通過(guò)模型訓(xùn)練 (即求解模型系數(shù)的過(guò)程)，我們得到用戶(hù)矩陣Xm×k 和物品矩陣 Yn×kYn×k，全部用戶(hù)對(duì)全部物品的評(píng)分預(yù)測(cè)可以通過(guò) Xm×k(Yn×k)TXm×k(Yn×k)T 獲得。如下圖所示。
得到全部的評(píng)分預(yù)測(cè)后，我們就可以對(duì)每個(gè)物品進(jìn)行擇優(yōu)推薦。需要注意的是，用戶(hù)矩陣和物品矩陣的乘積，得到的評(píng)分預(yù)估值，與用戶(hù)的實(shí)際評(píng)分不是全等關(guān)系，而是近似相等的關(guān)系。如上圖中兩個(gè)矩陣粉色部分，用戶(hù)實(shí)際評(píng)分和預(yù)估評(píng)分都是近似的，有一定的誤差。
2.3 理論推導(dǎo)
矩陣分解ALS的理論推導(dǎo)網(wǎng)上也有不少，但是很多推導(dǎo)不是那么嚴(yán)謹(jǐn)，在操作向量導(dǎo)數(shù)時(shí)有的步驟甚至是錯(cuò)誤的。有的博主對(duì)損失函數(shù)的求和項(xiàng)理解解出現(xiàn)錯(cuò)誤，例如
但是評(píng)分矩陣是稀疏的，求和并不會(huì)貫穿整個(gè)用戶(hù)集和物品集。正確的寫(xiě)法應(yīng)該是
其中，(u,i) is known(u,i) is known表示已知的評(píng)分項(xiàng)。
我們?cè)诒竟?jié)給出詳細(xì)的、正確的推導(dǎo)過(guò)程，一是當(dāng)做數(shù)學(xué)小練習(xí)，其次也是對(duì)算法有更深層的理解，便于閱讀Spark ALS的源碼。
將?(u,i) is known(u,i) is known 使用數(shù)學(xué)語(yǔ)言描述，矩陣分解的損失函數(shù)定義如下：
其中 K 為評(píng)分矩陣中已知的(u,i) 集合。例如下面的評(píng)分矩陣對(duì)應(yīng)的 K為
求解上述損失函數(shù)存在兩種典型的優(yōu)化方法，分別為
- 交替最小二乘 (Alternating Least Squares, ALS)
- 隨機(jī)梯度下降 (Stochastic Gradient Descent, SGD)
交替最小二乘，指的是固定其中一個(gè)變量，利用最小二乘求解另一個(gè)變量，以此交替進(jìn)行，直至收斂或者到達(dá)最大迭代次數(shù)，這也是“交替”一詞的由來(lái)。
隨機(jī)梯度下降，是優(yōu)化理論中最常用的一種方式，通過(guò)計(jì)算梯度，然后更新待求的變量。
在矩陣分解算法中，Spark最終選擇了ALS作為官方的唯一實(shí)現(xiàn)，原因是ALS很容易實(shí)現(xiàn)并行化，任務(wù)之間沒(méi)有依賴(lài)。
下面我們動(dòng)手推導(dǎo)一下整個(gè)計(jì)算過(guò)程，在機(jī)器學(xué)習(xí)理論中，微分的單位一般在向量維度，很少去對(duì)向量的分量為偏微分推導(dǎo)。
首先我們固定物品矩陣 Y，將物品矩陣 Y看成常量。不失一般性，我們定義用戶(hù)u 評(píng)分過(guò)的物品集合為 IuIu，利用損失函數(shù)對(duì)向量?xuxu 求偏導(dǎo)，并且令導(dǎo)數(shù)等于0可得：
因?yàn)橄蛄?nbsp;xuxu與求和符號(hào) ∑i∈Iu∑i∈Iu無(wú)關(guān)，所有將其移出求和符號(hào)，因?yàn)?nbsp;?xTuyiyTixuTyiyiT 是矩陣相乘 (不滿(mǎn)足交換性)，因此 xuxu 在左邊
等式兩邊取轉(zhuǎn)置，我們有
為了化簡(jiǎn) ∑i∈IuyiyTi∑i∈IuyiyiT 與 ∑i∈Iuru,iyi∑i∈Iuru,iyi，我們將 ?Iu 展開(kāi)。
假設(shè)Iu={ic1,?,icN} , 其中N表示用戶(hù)u評(píng)分過(guò)的物品數(shù)量，iciici表示第 cici個(gè)物品對(duì)應(yīng)的索引/序號(hào)，借助于 Iu ，我們有
其中，
YIuYIu 為以?Iu={ic1,?icN}Iu={ic1,?icN} 為行號(hào)在物品矩陣 Y 中選取的N個(gè)行向量形成的子矩陣
Ru,Iu為以Iu={ic1,?icN} 為索引，在評(píng)分矩陣 R的第u 行的行向量中選取的N 個(gè)元素，形成的子行向量
因此，我們有
網(wǎng)上的博客，許多博主給出類(lèi)似下面形式的結(jié)論不是很?chē)?yán)謹(jǐn)，主要是損失函數(shù)的理解不到位導(dǎo)致的。
同理，我們定義物品 i 被評(píng)分的用戶(hù)集合為 Ui={ud1,?udM}Ui={ud1,?udM}
根據(jù)對(duì)稱(chēng)性可得
其中，
?XUiXUi 為以 ?Ui={ud1,?,udM}Ui={ud1,?,udM} 為行號(hào)在用戶(hù)矩陣X中選取的M個(gè)行向量形成的子矩陣
Ri,UiRi,Ui 為以 Ui={ud1,?,udM}Ui={ud1,?,udM} 為索引，在評(píng)分矩陣 R的第i列的列向量中選取的 M個(gè)元素，形成的子列向量
此外，IkIk 為單位矩陣?
如果讀者感覺(jué)上述的推導(dǎo)還是很抽象，我們也給一個(gè)具體實(shí)例來(lái)體會(huì)一下中間過(guò)程
注意到損失函數(shù)是一個(gè)標(biāo)量，這里我們只展開(kāi)涉及到x1,1,x1,2x1,1,x1,2的項(xiàng)，如下所示
讓損失函數(shù)對(duì) x1,1,x1,2x1,1,x1,2 分別求偏導(dǎo)數(shù)可以得到
寫(xiě)成矩陣形式可得
利用我們上述的規(guī)則，很容易檢驗(yàn)我們導(dǎo)出的結(jié)論。
總結(jié)來(lái)說(shuō)，ALS的整個(gè)算法過(guò)程只有兩步，涉及2個(gè)循環(huán)，如下圖所示：
算法使用RMSE（root-mean-square error）評(píng)估誤差。
當(dāng)RMSE值變化很小時(shí)或者到達(dá)最大迭代步驟時(shí)，滿(mǎn)足收斂條件，停止迭代。
“Talk is cheap. Show me the code.” 作為小練習(xí)，我們給出上述偽代碼的Python實(shí)現(xiàn)。
import numpy as np
from scipy.linalg import solve as linear_solve
# 評(píng)分矩陣 5 x 6
R = np.array([[4, 0, 2, 5, 0, 0], [3, 2, 1, 0, 0, 3], [0, 2, 0, 3, 0, 4], [0, 3, 3,5, 4, 0], [5, 0, 3, 4, 0, 0]])
m = 5 # 用戶(hù)數(shù)
n = 6 # 物品數(shù)
k = 3 # 隱向量的維度
_lambda = 0.01 # 正則化系數(shù)
# 隨機(jī)初始化用戶(hù)矩陣, 物品矩陣
X = np.random.rand(m, k)
Y = np.random.rand(n, k)
# 每個(gè)用戶(hù)打分的物品集合
X_idx_dict = {1: [1, 3, 4], 2: [1, 2, 3, 6], 3: [2, 4, 6], 4: [2, 3, 4, 5], 5: [1, 3, 4]}
# 每個(gè)物品被打分的用戶(hù)集合
Y_idx_dict = {1: [1, 2, 5], 2: [2, 3, 4], 3: [1, 2, 4, 5], 4: [1, 3, 4, 5], 5: [4], 6: [2, 3]}
# 迭代10次
for iter in range(10):
for u in range(1, m+1):
Iu = np.array(X_idx_dict[u])
YIu = Y[Iu-1]
YIuT = YIu.T
RuIu = R[u-1, Iu-1]
xu = linear_solve(YIuT.dot(YIu) + _lambda * np.eye(k), YIuT.dot(RuIu))
X[u-1] = xu
for i in range(1, n+1):
Ui = np.array(Y_idx_dict[i])
XUi = X[Ui-1]
XUiT = XUi.T
RiUi = R.T[i-1, Ui-1]
yi = linear_solve(XUiT.dot(XUi) + _lambda * np.eye(k), XUiT.dot(RiUi))
Y[i-1] = yi
最終，我們打印用戶(hù)矩陣，物品矩陣，預(yù)測(cè)的評(píng)分矩陣如下，可以看到預(yù)測(cè)的評(píng)分矩陣非常逼近原始評(píng)分矩陣。
# X
array([[1.30678487, 2.03300876, 3.70447639],
[4.96150381, 1.03500693, 1.62261161],
[6.37691007, 2.4290095 , 1.03465981],
[0.41680155, 3.31805612, 3.24755801],
[1.26803845, 3.57580564, 2.08450113]])
# Y
array([[ 0.24891282, 1.07434519, 0.40258993],
[ 0.12832662, 0.17923216, 0.72376732],
[-0.00149517, 0.77412863, 0.12191856],
[ 0.12398438, 0.46163336, 1.05188691],
[ 0.07668894, 0.61050204, 0.59753081],
[ 0.53437855, 0.20862131, 0.08185176]])
# X.dot(Y.T) 預(yù)測(cè)評(píng)分
array([[4.00081359, 3.2132548 , 2.02350084, 4.9972158 , 3.55491072, 1.42566466],
[3.00018371, 1.99659282, 0.99163666, 2.79974661, 1.98192672, 3.00005934],
[4.61343295, 2.00253692, 1.99697545, 3.00029418, 2.59019481, 3.99911584],
[4.97591903, 2.99866546, 2.96391664, 4.99946603, 3.99816006, 1.18076534],
[4.99647978, 2.31231627, 3.02037696, 4.0005876 , 3.5258348 , 1.59422188]])
# 原始評(píng)分矩陣
array([[4, 0, 2, 5, 0, 0],
[3, 2, 1, 0, 0, 3],
[0, 2, 0, 3, 0, 4],
[0, 3, 3, 5, 4, 0],
[5, 0, 3, 4, 0, 0]])
三、Spark ALS應(yīng)用
Spark的內(nèi)部實(shí)現(xiàn)并不是我們上面所列的算法，但是核心原理是完全一樣的，Spark實(shí)現(xiàn)的是上述偽代碼的分布式版本，具體算法參考Large-scale Parallel Collaborative Filtering for the Netflix Prize。其次，查閱Spark的官方文檔，我們也注意到，Spark使用的懲罰函數(shù)與我們上文的有細(xì)微的差別。
其中 nu,ninu,ni分別表示用戶(hù)u打分的物品數(shù)量和物品 i 被打分的用戶(hù)數(shù)量。即
本小節(jié)通過(guò)兩個(gè)案例來(lái)了解Spark ALS的具體使用，以及在面對(duì)互聯(lián)網(wǎng)實(shí)際工程場(chǎng)景下的應(yīng)用。
3.1 Demo案例
以第一節(jié)給出的數(shù)據(jù)為例，將三元組(User, Item, Rating)組織為als-demo-data.csv，該demo數(shù)據(jù)集涉及5個(gè)用戶(hù)和6個(gè)物品。
userId,itemId,rating
1,1,4
1,3,2
1,4,5
2,1,3
2,2,2
2,3,1
2,6,3
3,2,2
3,4,3
3,6,4
4,2,3
4,3,3
4,4,5
4,5,4
5,1,5
5,3,3
5,4,4
使用Spark的ALS類(lèi)使用非常簡(jiǎn)單，只需將三元組(User, Item, Rating)數(shù)據(jù)輸入模型進(jìn)行訓(xùn)練。
import org.apache.spark.sql.SparkSession
import org.apache.spark.ml.recommendation.ALS
val spark = SparkSession.builder().appName("als-demo").master("local[*]").getOrCreate()
val rating = spark.read
.options(Map("inferSchema" -> "true", "delimiter" -> ",", "header" -> "true"))
.csv("./data/als-demo-data.csv")
// 展示前5條評(píng)分記錄
rating.show(5)
val als = new ALS()
.setMaxIter(10) // 迭代次數(shù)，用于最小二乘交替迭代的次數(shù)
.setRank(3) // 隱向量的維度
.setRegParam(0.01) // 懲罰系數(shù)
.setUserCol("userId") // user_id
.setItemCol("itemId") // item_id
.setRatingCol("rating") // 評(píng)分列
val model = als.fit(rating) // 訓(xùn)練模型
// 打印用戶(hù)向量和物品向量
model.userFactors.show(truncate = false)
model.itemFactors.show(truncate = false)
// 給所有用戶(hù)推薦2個(gè)物品
model.recommendForAllUsers(2).show()
上述代碼在控制臺(tái)輸出結(jié)果如下：
+------+------+------+
|userId|itemId|rating|
+------+------+------+
| 1| 1| 4|
| 1| 3| 2|
| 1| 4| 5|
| 2| 1| 3|
| 2| 2| 2|
+------+------+------+
only showing top 5 rows
+---+------------------------------------+
|id |features |
+---+------------------------------------+
|1 |[-0.17339179, 1.3144133, 0.04453602]|
|2 |[-0.3189066, 1.0291641, 0.12700711] |
|3 |[-0.6425665, 1.2283803, 0.26179287] |
|4 |[0.5160747, 0.81320006, -0.57953185]|
|5 |[0.645193, 0.26639006, 0.68648624] |
+---+------------------------------------+
+---+-----------------------------------+
|id |features |
+---+-----------------------------------+
|1 |[2.609607, 3.2668495, 3.554771] |
|2 |[0.85432494, 2.3137972, -1.1198239]|
|3 |[3.280517, 1.9563107, 0.51483333] |
|4 |[3.7446978, 4.259611, 0.6640027] |
|5 |[1.6036265, 2.5602736, -1.8897828] |
|6 |[-1.2651576, 2.4723763, 0.51556784]|
+---+-----------------------------------+
+------+--------------------------------+
|userId|recommendations |
+------+--------------------------------+
|1 |[[4, 4.9791617], [1, 3.9998217]]| // 對(duì)應(yīng)物品的序號(hào)和預(yù)測(cè)評(píng)分
|2 |[[4, 3.273963], [6, 3.0134287]] |
|3 |[[6, 3.9849386], [1, 3.2667015]]|
|4 |[[4, 5.011649], [5, 4.004795]] |
|5 |[[1, 4.994258], [4, 4.0065994]] |
+------+--------------------------------+
我們使用numpy來(lái)驗(yàn)證Spark的結(jié)果，并且用Excel可視化評(píng)分矩陣。
import numpy as np
X = np.array([[-0.17339179, 1.3144133, 0.04453602],
[-0.3189066, 1.0291641, 0.12700711],
[-0.6425665, 1.2283803, 0.26179287],
[0.5160747, 0.81320006, -0.57953185],
[0.645193, 0.26639006, 0.68648624]])
Y = np.array([[2.609607, 3.2668495, 3.554771],
[0.85432494, 2.3137972, -1.1198239],
[3.280517, 1.9563107, 0.51483333],
[3.7446978, 4.259611, 0.6640027],
[1.6036265, 2.5602736, -1.8897828],
[-1.2651576, 2.4723763, 0.51556784]])
R_predict = X.dot(Y.T)
R_predict
輸出預(yù)測(cè)的評(píng)分矩陣如下：
array([[3.99982136, 2.84328038, 2.02551472, 4.97916153, 3.0030386, 3.49205357],
[2.98138452, 1.96660155, 1.03257371, 3.27396294, 1.88351875, 3.01342882],
[3.26670123, 2.0001004 , 0.42992289, 3.00003605, 1.61982132, 3.98493822],
[1.94325135, 2.97144913, 2.98550149, 5.011649 , 4.00479503, 1.05883274],
[4.99425778, 0.39883335, 2.99113433, 4.00659955, 0.41937014, 0.19627587]])
從Excel可視化的評(píng)分矩陣可以觀察到預(yù)測(cè)的評(píng)分矩陣非常逼近原始的評(píng)分矩陣，以u(píng)ser-3為例，Spark推薦的物品是item-6和item-1, [[6, 3.9849386], [1, 3.2667015]]，這和Excel展示的預(yù)測(cè)評(píng)分矩陣完全一致。
從Spark函數(shù)recommendForAllUsers()給出的結(jié)果來(lái)看，Spark內(nèi)部并沒(méi)有去除用戶(hù)已經(jīng)購(gòu)買(mǎi)的物品。
3.2 工程應(yīng)用
在互聯(lián)網(wǎng)場(chǎng)景，用戶(hù)數(shù) m(千萬(wàn)~億級(jí)別) 和物品數(shù) n (10萬(wàn)~100萬(wàn)級(jí)別) 規(guī)模很大，App的埋點(diǎn)數(shù)據(jù)一般會(huì)保存在HDFS中，以互聯(lián)網(wǎng)的長(zhǎng)視頻場(chǎng)景為例，用戶(hù)的埋點(diǎn)信息最終聚合為用戶(hù)行為表 t_user_behavior。
行為表包含用戶(hù)的imei，物品的content-id，但是沒(méi)有直接的用戶(hù)評(píng)分，實(shí)踐中我們的解決方案是利用用戶(hù)的其他行為進(jìn)行加權(quán)得出用戶(hù)對(duì)物品的評(píng)分。即
rating = w1 * play_time (播放時(shí)長(zhǎng)) + w2 * finsh_play_cnt (完成的播放次數(shù)) + w3 * praise_cnt (點(diǎn)贊次數(shù)) + w4 * share_cnt (分享次數(shù)) + 其他適合于你業(yè)務(wù)邏輯的指標(biāo)
其中, wi為每個(gè)指標(biāo)對(duì)應(yīng)的權(quán)重。
如下的代碼塊演示了工程實(shí)踐中對(duì)大規(guī)模用戶(hù)和商品場(chǎng)景進(jìn)行推薦的流程。
import org.apache.spark.ml.feature.{IndexToString, StringIndexer}
// 從hive加載數(shù)據(jù)，并利用權(quán)重公式計(jì)算用戶(hù)對(duì)物品的評(píng)分
val rating_df = spark.sql("select imei, content_id, 權(quán)重公式計(jì)算評(píng)分 as rating from t_user_behavior group by imei, content_id")
// 將imei和content_id轉(zhuǎn)換為序號(hào)，Spark ALS入?yún)⒁髐serId, itemId為整數(shù)
// 使用org.apache.spark.ml.feature.StringIndexer
val imeiIndexer = new StringIndexer().setInputCol("imei").setOutputCol("userId").fit(rating_df)
val contentIndexer = new StringIndexer().setInputCol("content_id").setOutputCol("itemId").fit(rating_df)
val ratings = contentIndexer.transform(imeiIndexer.transform(rating_df))
// 其他code，類(lèi)似于上述demo
val model = als.fit(ratings)
// 給每個(gè)用戶(hù)推薦100個(gè)物品
val _userRecs = model.recommendForAllUsers(100)
// 將userId, itemId轉(zhuǎn)換為原來(lái)的imei和content_id
val imeiConverter = new IndexToString().setInputCol("userId").setOutputCol("imei").setLabels(imeiIndexer.labels)
val contentConverter = new IndexToString().setInputCol("itemId").setOutputCol("content_id").setLabels(contentIndexer.labels)
val userRecs = imeiConverter.transform(_userRecs)
// 離線(xiàn)保存供線(xiàn)上調(diào)用
userRecs.foreachPartition {
// contentConverter 將itemId轉(zhuǎn)換為content_id
// 保存redis邏輯
}值得注意的是，上述的工程場(chǎng)景還有一種解決方案，即隱式反饋。用戶(hù)給商品評(píng)分很單一，在實(shí)際的場(chǎng)景中，用戶(hù)未必會(huì)給物品打分，但是大量的用戶(hù)行為，同樣能夠間接反映用戶(hù)的喜好，比如用戶(hù)的購(gòu)買(mǎi)記錄、搜索關(guān)鍵字，加入購(gòu)物車(chē)，單曲循環(huán)播放同一首歌。我們將這些間接用戶(hù)行為稱(chēng)之為隱式反饋，以區(qū)別于評(píng)分對(duì)應(yīng)的顯式反饋。胡一凡等人在論文Collaborative filtering for implicit feedback datasets中針對(duì)隱式反饋場(chǎng)景提出了ALS-WR模型 (ALS with Weighted-λ-Regularization)，并且Spark官方也實(shí)現(xiàn)了該模型，我們將在以后的文章中介紹該模型。
四、總結(jié)
本文從推薦的場(chǎng)景出發(fā)，引出了協(xié)同過(guò)濾這一經(jīng)典的推薦算法，并且由此講解了被Spark唯一實(shí)現(xiàn)和維護(hù)的矩陣分解算法，詳細(xì)推導(dǎo)了顯示反饋下矩陣分解的理論原理，并且給出了Python版本的單機(jī)實(shí)現(xiàn)，能夠讓讀者更好的理解矩陣這一算法，最后我們以demo和工程實(shí)踐兩個(gè)實(shí)例講解了Spark ALS的使用，能夠讓沒(méi)有接觸過(guò)推薦算法的同學(xué)有個(gè)直觀的理解，用理論與實(shí)踐的形式明白矩陣分解這一推薦算法背后的原理。
參考文獻(xiàn)：
- 王喆, 深度學(xué)習(xí)推薦系統(tǒng)
- Hu, Yifan, Yehuda Koren, and Chris Volinsky. "Collaborative filtering for implicit feedback datasets." 2008 Eighth IEEE International Conference on Data Mining. IEEE, 2008.
- Zhou, Yunhong, et al. "Large-scale parallel collaborative filtering for the Netflix prize." International conference on algorithmic applications in management. Springer, Berlin, Heidelberg, 2008.
