|
1 推薦算法概述 只知用戶評分矩陣（User-Item Matrix），試向用戶(User)推薦產品(Item)。 輸入：  上圖所示為用戶評分矩陣，其中用戶評分為1-5，?所示為需要估算的用戶評分。如果能夠快速估算出用戶的評分那么就可以對用戶進行推薦了，實現的方法非常多，但并不是本次討論的重點，一筆飛過——以下為常用的推薦算法概括。 實現：  一般來說，推薦系統通常往往是多個推薦算法的疊加或集合，其中協同過濾算法和基于內容推薦、流行度推薦使用最廣。而基于內容推薦需要較多的用戶維度信息及與產品的相關程度，有比較大的工作量；流行度推薦對于新的產品及用戶個性化滿足不夠。協同過濾分析用戶以及用戶相關的產品的相關性，用以識別新的用戶-產品相關性。協同過濾系統需要的唯一信息是用戶過去的行為信息，比如對產品的評價信息。相較而言，協同過濾算法能夠比較快速同時能夠個性化地實現推薦。 使用協同過濾的算法，同時結合分布式大數據系統能夠構建出高效且可應用于大規模人群的推薦系統，在電商及視頻等行業應用較廣，銀行業也有著相似的需求和應用，特別是在理財推薦方面。 基于鄰域的協同過濾要計算大量的相似性距離，因而選擇基于用戶還是基于物品有較大的性能差異；兩者目前還沒能實現分布式的算法，在用戶量大于千萬級或數億級規模時，與下面要說的基于Spark的協同過濾算法（ALS算法）有較大的性能差距。 2 什么是ALS ALS是交替最小二乘（Alternating Least Squares）的簡稱。在機器學習中，ALS特指使用交替最小二乘求解的一個協同推薦算法。它通過觀察到的所有用戶給商品的評分，通過提取主要因素來對上圖中”?”進行評分，進而推斷每個用戶的喜好并向用戶推薦適合的商品。 2.1低秩假設 ALS的核心就是這樣一個假設：評分矩陣是近似低秩的。換句話說，就是一個m*n的評分矩陣可以由分解的兩個小矩陣U（m*k）和V（k*n）的乘積來近似，即A=UV^T,k≤m,n。這就是ALS的矩陣分解方法。這樣我們把系統的自由度從O(mn)降到了O((m+n)k)。 那么ALS的低秩假設合理嗎？這個問題正是利用了人類的概括能力，通常我們描述一個人的喜好，我們并不需要一一列出他喜好的事物，而是概括他喜歡哪些類型。例如，我喜好看偵探類型，可能代表我喜歡《神探夏洛特》、《柯南》等。這些影片都符合我對自己喜好的描述，也就是說他們在這個抽象的低維空間的投影和我的喜好相似。 再抽象一些來描述這個問題，我們把某個人的喜好映射到了低維向量ui上，同時將某個影片的特征映射到了維度相同的向量vj上，那么這個人和這個影片的相似度就可以表述成這兩個向量之間的內積([u_i]^T)* vj。我們把評分理解成相似度，那么評分矩陣A就可以由用戶喜好矩陣和產品特征矩陣的乘積UV^T來近似了。 2.2ALS最優求解 基于以上假設我們把評分矩陣A通過UV^T來近似，那么究竟合理不合理，怎么量化?一個最直接的可量化的目標就是通過U,V重構A所產生的誤差。在ALS里，我們使用Frobenius范數，來量化重構誤差，即每個元素的重構誤差的平方和。這里存在一個問題，我們只觀察到一部分評分，A中的大量未知評分正是我們想推斷的，所以這個重構誤差是包含未知數的。解決方案：只看對已知評分的重構誤差，因為沒評分的不可衡量。所以ALS的優化函數是：f=min( 這樣協同推薦的問題通過低秩假設成功轉變成了一個優化問題。 下面要討論的內容很顯然：這個優化問題怎么解？其實答案已經在ALS的名字已經給出——交替最小二乘。ALS的目標函數不是凸的，而且變量互相耦合在一起，很難求解。但如果我們把用戶特征矩陣U和產品特征矩陣V固定一個，這個問題立刻變成了一個凸的且可拆分的問題。比如我們固定U，那么目標函數就可以寫成  3 Spark中ALS的實現原理 Spark利用交換最小二乘解決矩陣分解問題分兩種情況：數據集是顯式反饋和數據集是隱式反饋。隱式反饋算法的原理是在顯示反饋算法原理的基礎上作一定的修改，所以在此我們只會具體講解數據集為隱式反饋的算法。 推薦系統依賴不同類型的輸入數據，最方便的是高質量的顯式反饋數據，它們包含用戶對感興趣商品明確的評價。例如，大眾點評中對餐廳的評價數據，但是顯式反饋數據不一定總是找得到。好在推薦系統還可以從更豐富的隱式反饋信息中推測用戶的偏好。隱式反饋類型包括購買歷史、瀏覽歷史、搜索模式甚至鼠標動作。例如，反復瀏覽某一個類型理財產品的用戶可能喜歡這類理財產品。 了解隱式反饋的特點非常重要，因為這些特質使我們避免了直接調用基于顯式反饋的算法。最主要的特點有如下幾種： （1）沒有負反饋。通過觀察用戶行為，我們可以推測那個商品他可能喜歡，然后購買，但是我們很難推測哪個商品用戶不喜歡。這在顯式反饋算法中并不存在，因為用戶明確告訴了我們他喜歡什么他不喜歡什么。 （2）隱式反饋是內在的噪音。雖然我們拼命的追蹤用戶行為，但是我們僅僅只是猜測他們的偏好和真實動機。例如，我們可能知道一個人的購買行為，但是這并不能完全說明偏好和動機，因為這個商品可能作為禮物被購買而用戶并不喜歡它。 （3）顯示反饋的數值表示偏好（preference），隱式回饋的數值表示信任（confidence）。基于顯示反饋的系統用星星等級讓用戶表達他們的喜好程度，例如一顆星表示很不喜歡，五顆星表示非常喜歡。基于隱式反饋的數值描述的是動作的頻率，例如用戶購買特定商品的次數。一個較大的值并不能表明更多的偏愛。但是這個值是有用的，它描述了在一個特定觀察中的信任度。一個發生一次的事件可能對用戶偏愛沒有用，但是一個周期性事件更可能反映一個用戶的選擇。 （4）評價隱式反饋推薦系統需要合適的手段。 3.1顯式反饋模型 潛在因素模型由一個針對協同過濾的交替方法組成，它以一個更加全面的方式發現潛在特征來解釋觀察的ratings數據。我們關注的模型由奇異值分解（SVD）推演而來。一個典型的模型將每個用戶u（包含一個用戶-因素向量u_i）和每個商品v（包含一個用戶-因素向量v_j）聯系起來。預測通過內積r_ij=(u_i^T )v_j來實現。另一個需要關注的地方是參數估計。許多當前的工作都應用到了顯式反饋數據集中，這些模型僅僅基于觀察到的rating數據直接建模，同時通過一個適當的正則化來避免過擬合。公式如下： 在上述公式中，lambda是正則化的參數。正規化是為了防止過擬合的情況發生。這樣，我們用最小化重構誤差來解決協同推薦問題。我們也成功將推薦問題轉換為了最優化問題。 3.2隱式反饋模型 在顯式反饋的基礎上，我們需要做一些改動得到我們的隱式反饋模型。首先，我們需要形式化由r_ij變量衡量的信任度的概念。我們引入了一組二元變量p_ij，它表示用戶u對商品v的偏好。p_ij的公式如下： 換句話說，如果用戶購買了商品，我們認為用戶喜歡該商品，否則我們認為用戶不喜歡該商品。然而我們的信念（beliefs）與變化的信任（confidence）等級息息相關。首先，很自然的，p_ij的值為0和低信任有關。用戶對一個商品沒有得到一個正的偏好可能源于多方面的原因，并不一定是不喜歡該商品。例如，用戶可能并不知道該商品的存在。 另外，用戶購買一個商品也并不一定是用戶喜歡它。因此我們需要一個新的信任等級來顯示用戶偏愛某個商品。一般情況下，r_ij越大，越能暗示用戶喜歡某個商品。因此，我們引入了一組變量C_ij，它衡量了我們觀察到p_ij的信任度。C_ij一個合理的選擇如下所示： 按照這種方式，我們存在最小限度的信任度，并且隨著我們觀察到的正偏向的證據越來越多，信任度也會越來越大。 我們的目的是找到用戶向量以及商品向量v_j來表明用戶偏好。這些向量分別是用戶因素（特征）向量和商品因素（特征）向量。本質上，這些向量將用戶和商品映射到一個公用的隱式因素空間，從而使它們可以直接比較。這和用于顯式數據集的矩陣分解技術類似，但是包含兩點不一樣的地方：（1）我們需要考慮不同的信任度。 （2）最優化需要考慮所有可能的u，v對，而不僅僅是和觀察數據相關的u，v對。 因此，通過最小化下面的損失函數來計算相關因素（factors）。 3.3求解最小化損失函數 考慮到損失函數包含m*n個元素，m是用戶的數量，n是商品的數量。一般情況下，m*n可以到達幾百億。這么多的元素應該避免使用隨機梯度下降法來求解，Spark選擇使用交替最優化方式求解。 交替最小二乘的計算過程是：交替的重新計算用戶-特征向量和商品-特征向量，每一步都保證降低損失函數的值，直到找到極小值。交替最小二乘法的處理過程如下所示： 初始化U^1 和V^1 迭代直到損失函數不在變化或變化極小 在Spark的源代碼中，ALS算法實現于org.apache.Spark.ml.recommendation.ALS.scala文件中。有興趣的同學可以直接查看相關Scala代碼。 基于Spark ALS我們結合Spark Streaming構建了一個實時的推薦系統（基于Netflix電影評分的Demo），有興趣的同學可以回復”ALS”查看數據與源碼鏈接。 團隊介紹：我們是畢馬威旗下的專業數據挖掘團隊，）每周六晚8點準時推送一篇原創數據科學文章。我們的作品都由項目經驗豐富的博士或資深顧問精心準備，分享結合實際業務的理論應用和心得體會。歡迎大家關注我們的微信公眾號，關注原創數據挖掘精品文章；您也可以在公眾號中直接發送想說的話，與我們聯系交流。 即可關注！也請隨手推薦我們給你的小伙伴 ↓↓↓↓ |
|
|
