推薦算法中協同過濾的原理及實現

我有個兄弟，是抖音的點贊狂魔，他的點贊次數高達6924次，而且他大多數的贊都是給那些青春靚麗的小姐姐們，如下圖。看他的抖音推薦內容，都是滿目的小姐姐唱啊跳啊不亦樂乎，他也覺得甚爽。不過，好景不長，沒多久他就跟我說：“我再也不敢再點了，我老婆已經發現我給小姐姐們點了上1000個贊，而且知道我點贊的視頻，也會推薦給她”。

把好友看過的視頻推薦給用戶，這就是協同過濾。準確地說，叫用戶協同過濾（User Collaborative Filtering）。

一、協同過濾概述（Collaborative Filtering）

協同過濾（簡稱CF）是推薦系統最重要的思想之一。在早期，協同過濾幾乎等同于推薦系統。協同過濾思想產生于1994年，被用于郵件系統上。2001年，亞馬遜用協同過濾算法來推薦相似商品。

協同過濾的思想比較簡單，主要有三種：

用戶協同過濾（UserCF）：相似的用戶可能喜歡相同物品。如加了好友的兩個用戶，或者點擊行為類似的用戶被視為相似用戶。如我兄弟和她的太太互加了抖音好友，他們兩人各自喜歡的視頻，可能會產生互相推薦。

物品協同過濾（ItemCF）：相似的物品可能被同個用戶喜歡。這個就是著名的世界杯期間沃爾瑪尿布和啤酒的故事了。這里因為世界杯期間，奶爸要喝啤酒看球，又要帶娃，啤酒和尿布同時被奶爸所需要，也就是相似商品，可以放在一起銷售。

模型協同過濾：使用矩陣分解模型來學習用戶和物品的協同過濾信息。一般這種協同過濾模型有：SVD，SVD++等。這種協同過濾要比前兩個來得抽象些，這里先不解釋，后面詳述。

下面按照物品協同過濾，用戶協同過濾和模型協同過濾的順序，詳細解釋這幾種算法。

二、物品協同過濾的計算

2003年，亞馬遜發表了一篇論文，闡述了他們如何用物品協同過濾算法（Item-to-Item Collaborative Filtering），搭建他們“看了又看”功能。如下圖：

這是17年前的截圖，圖跟紙質老照片那樣變得斑駁。圖中是在購物車關聯頁面的相關推薦。那么，這個協同過濾推薦是如何做計算出來的呢？

前面第一章說到，人工智能實踐過程三個步驟：數據，學習和決策。這里也將用同樣步驟，以圖書銷售推薦為例，解釋物品協同過濾的過程。為了簡單化，假設某圖書銷售平臺總共有6本書銷售，有6個用戶購買。

數據：用戶的評分數據，分值1-5分。每個用戶對圖書的評分如下圖矩陣所示。

學習算法：前面說到ItemCF的定義是，相似的物品可能被同個用戶喜歡。反過來講，就是被同個用戶喜歡的物品是相似商品。如上圖中，圖書1和圖書2兩本書，被用戶A同時喜歡，這兩本書具有相似性。而圖書5和圖書6，沒有被同個用戶同時喜歡，不具有相似性。

如果用余弦相似度計算圖書1和圖書2的相似度，也叫做cosine距離，計算過程為：

回想高中時候的課本我們就可以知道，上面的similarity計算公式，實際上就是計算書籍1的評分向量（4,5,4,0,0,0）和書籍2的評分向量（3,0,3,3,4,0）的 cos 夾角。

用同樣的方式，可以算出圖書1跟其他五本圖書相似度分別為0.27, 0 .79，0.32,0.99和0。對每兩本書計算完這個相似度后，就可以獲得全部圖書的相似矩陣。

一個平臺不僅僅有6本圖書6個用戶，我們再擴展到一般的情況。計算物品的相似度，實際是計算每兩個物品評分向量的cosine距離，評分向量的每一維，代表了一個用戶，下圖中，表格的第一行代表了所有用戶對物品A的評分。當有100萬個用戶時，也就是計算每兩個100萬維向量的距離。這樣就導致計算量很大，而且很多平臺不僅僅只有100萬用戶，因而這個低效的計算方式需要改進。

預測決策：

有了評分矩陣之后，預測決策一般有兩種場景。

一種是根據相似度排序推薦最近鄰物品。類似于“看了還看”，“買了還買”場景。在這里的例子中，我們知道圖書1和其他圖書的相似度排序分別是圖書5，圖書3，圖書4和圖書2。當用戶點擊了圖書1時，就可以按照相似順序從高到低推薦。

第二種是根據相似度預測評分推薦物品。如何決策要不要給用戶B推薦圖書2，圖書4和圖書6呢？如下圖，通過用戶B對圖書1的評分 * 未知圖書與圖書1的相似度來預測用戶B對剩下圖書的評分。如圖書2的預測評分 = ?圖書1的評分5分 * 圖書1和圖書2的相似度0.27 ，從而用戶B對圖書2的評分是：5*0.27=1.35。同樣方式計算出其他圖書的評分預測。

從上面的結果來看，用戶B對其他圖書評分比較低，這幾本圖書推薦的可能性大大減少。

物品協同過濾實際使用

這是推薦系統里最樸素的算法，因為它的計算量會隨著用戶和物品的數量呈指數增長，所以它并不適合在大量用戶或大量物品的場景使用。在它誕生的年代，還沒有大數據，這種計算方式耗費大量內存，需要做大量的優化。我嘗試過用100萬用戶，100萬物品和500萬條的數據在256G內存的機器上做過嘗試，計算一分鐘后就宣告內存耗盡。確實需要計算的話，一般使用Spark來實現。

因為這個缺點，就需要新的算法來計算物品的協同過濾。

前面提到，計算任意兩物品之間的相似度后，有兩個使用場景。針對這兩個場景，分別有不同的迭代算法：

根據相似度排序推薦最近鄰物品：使用如Word2vec，Item2vec等Embedding類的算法，將物品嵌入固定的向量空間中，再使用LSH算法(局部敏感哈希算法)取最近鄰物品。這個后續文章會介紹。
根據相似度預測評分推薦物品：本章后續介紹的SVD算法。

雖然這個算法使用較少了，但是物品協同過濾的思想都是一脈相乘的，理解了這個簡單的cosine相似度計算方式，可以更好理解后續的迭代算法。

最后補充一下，物品協同過濾的一個缺點，或者說是協同過濾的缺點，對于一個新物品，協同過濾是無法推薦的。因為新物品用戶無評分，導致它跟所有物品的相似度都是為0。這個是使用這個算法時非常需要注意的一個點。

三、用戶協同過濾計算

用戶協同過濾（UserCF）的計算方式跟物品協同過濾（ItemCF）的計算方式類似。不同的是由計算兩兩物品的相似度，轉換成計算兩兩用戶的相似度。如下圖所示：

評分了相同圖書的用戶為相似用戶，他們的相似度同樣也用cosine相似度公式來計算。計算完相似度后，就可以根據用戶間的相似性，預測用戶對未評分圖書進行評分預測。

但是在亞馬遜上，由于用戶評分的稀疏性（很多用戶壓根不評分），沒有評分的用戶無法跟其他用戶計算相似性，從而導致很多用戶之間沒有相似度。所以2001年的時候，亞馬遜選擇物品協同過濾算法來做推薦，并發表了論文。這個論文也導致大家一度認為物品協同過濾優于用戶協同過濾。

其實只有最合適的算法，沒有最優的算法

時間到了移動互聯網的今天，我們更多是用點擊數據，用戶好友關系，通訊錄或者甚至是同一個WIFI地址來計算用戶協同過濾，數據稀疏性得到一定程度上的解決。現在，用戶的協同過濾在信息流內容推薦，社交性的推薦系統有著很好的利用。比如抖音，因為內容更新頻繁，用戶協同過濾可以作為很好的召回手段，所以也就會出現老公點贊的視頻會被推薦給他老婆的情景。

同樣地，這里介紹的cosine相似度的算法，也不是工業界現在最佳實踐的用戶相似度計算方式了。用戶相似度的計算，現在的最佳實踐也同樣也是用Embedding的方式實現。

而且，用戶相似度的計算，最有效的方式不一定是通過本節中介紹的計算方式，帶社交功能的APP可以通過用戶的好友關系，一般的APP可以通過獲取用戶的通訊錄實現用戶協同過濾。這些方式都來的更加簡單和直接。

四、模型協同過濾-矩陣分解（SVD）

對于很多沒有計算機專業背景的人來說，直接理解SVD算法是很困難的。需要有高等數學，線性代數，還要理解機器學習模型中的目標函數，損失函數，梯度，正則化，最小二乘法等概念。很多文章介紹SVD都很技術，這里不準備采用技術大咖們的方式。我還是繼續用圖文的方式介紹，這也許是世界上最簡單的理解SVD的方式。

首先介紹一下背景。

SVD算法的誕生，跟美國Netflix公司有關。這家公司中文名叫網飛，拍了大家熟悉的網劇《紙牌屋》。

時間來到2006年，Netflix發起一個推薦系統的懸賞競賽。他們公開了自己網站的用戶數據評分數據包，并放出100萬美元懸賞優化推薦算法。凡是能在Netflix現有的推薦系統基礎上，把均方根誤差降低10%的人，都能參與瓜分這100萬美元。消息一放出，引來了無數高手參加。這場比賽中，最佳算法就是SVD。

背景介紹完了，接下來直接介紹SVD是怎么計算的。

還是跟前面那樣，簡單化問題：假設一個平臺只有4個用戶和4本圖書。

1、數據：用戶對物品評分1-5分，且有以下評分記錄。

2、學習算法：

根據線性代數我們知道，一個矩陣可以分解為多個矩陣的乘積。SVD英文全稱叫做Singular Value Decomposition，這個算法是個矩陣分解的通用名稱，在不同領域有不同的形式。在推薦系統領域，可以簡單的認為，SVD就是將一個矩陣，在一定的精度損失下，將一個矩陣分解成兩個矩陣。運用這個算法，我們可以將上圖的矩陣做以下的近似分解：