用戶的協同過濾演算法

㈠ 矩陣分解在協同過濾推薦演算法中的應用

矩陣分解在協同過濾推薦演算法中的應用
推薦系統是當下越來越熱的一個研究問題，無論在學術界還是在工業界都有很多優秀的人才參與其中。近幾年舉辦的推薦系統比賽更是一次又一次地把推薦系統的研究推向了高潮，比如幾年前的Neflix百萬大獎賽，KDD CUP 2011的音樂推薦比賽，去年的網路電影推薦競賽，還有最近的阿里巴巴大數據競賽。這些比賽對推薦系統的發展都起到了很大的推動作用，使我們有機會接觸到真實的工業界數據。我們利用這些數據可以更好地學習掌握推薦系統，這些數據網上很多，大家可以到網上下載。
推薦系統在工業領域中取得了巨大的成功，尤其是在電子商務中。很多電子商務網站利用推薦系統來提高銷售收入，推薦系統為Amazon網站每年帶來30%的銷售收入。推薦系統在不同網站上應用的方式不同，這個不是本文的重點，如果感興趣可以閱讀《推薦系統實踐》（人民郵電出版社，項亮）第一章內容。下面進入主題。
為了方便介紹，假設推薦系統中有用戶集合有6個用戶，即U={u1,u2,u3,u4,u5,u6}，項目（物品）集合有7個項目，即V={v1,v2,v3,v4,v5,v6,v7}，用戶對項目的評分結合為R，用戶對項目的評分范圍是[0, 5]。R具體表示如下：

推薦系統的目標就是預測出符號「？」對應位置的分值。推薦系統基於這樣一個假設：用戶對項目的打分越高，表明用戶越喜歡。因此，預測出用戶對未評分項目的評分後，根據分值大小排序，把分值高的項目推薦給用戶。怎麼預測這些評分呢，方法大體上可以分為基於內容的推薦、協同過濾推薦和混合推薦三類，協同過濾演算法進一步劃分又可分為基於基於內存的推薦（memory-based）和基於模型的推薦（model-based），本文介紹的矩陣分解演算法屬於基於模型的推薦。
矩陣分解演算法的數學理論基礎是矩陣的行列變換。在《線性代數》中，我們知道矩陣A進行行變換相當於A左乘一個矩陣，矩陣A進行列變換等價於矩陣A右乘一個矩陣，因此矩陣A可以表示為A=PEQ=PQ（E是標准陣）。
矩陣分解目標就是把用戶-項目評分矩陣R分解成用戶因子矩陣和項目因子矩陣乘的形式，即R=UV，這里R是n×m， n =6， m =7，U是n×k，V是k×m。直觀地表示如下：

高維的用戶-項目評分矩陣分解成為兩個低維的用戶因子矩陣和項目因子矩陣，因此矩陣分解和PCA不同，不是為了降維。用戶i對項目j的評分r_ij =innerproct(u_i, v_j)，更一般的情況是r_ij =f(U_i, V_j)，這里為了介紹方便就是用u_i和v_j內積的形式。下面介紹評估低維矩陣乘積擬合評分矩陣的方法。
首先假設，用戶對項目的真實評分和預測評分之間的差服從高斯分布，基於這一假設，可推導出目標函數如下：

最後得到矩陣分解的目標函數如下：

從最終得到得目標函數可以直觀地理解，預測的分值就是盡量逼近真實的已知評分值。有了目標函數之後，下面就開始談優化方法了，通常的優化方法分為兩種：交叉最小二乘法（alternative least squares）和隨機梯度下降法（stochastic gradient descent）。
首先介紹交叉最小二乘法，之所以交叉最小二乘法能夠應用到這個目標函數主要是因為L對U和V都是凸函數。首先分別對用戶因子向量和項目因子向量求偏導，令偏導等於0求駐點，具體解法如下：

上面就是用戶因子向量和項目因子向量的更新公式，迭代更新公式即可找到可接受的局部最優解。迭代終止的條件下面會講到。
接下來講解隨機梯度下降法，這個方法應用的最多。大致思想是讓變數沿著目標函數負梯度的方向移動，直到移動到極小值點。直觀的表示如下：

其實負梯度的負方向，當函數是凸函數時是函數值減小的方向走；當函數是凹函數時是往函數值增大的方向移動。而矩陣分解的目標函數L是凸函數，因此，通過梯度下降法我們能夠得到目標函數L的極小值（理想情況是最小值）。
言歸正傳，通過上面的講解，我們可以獲取梯度下降演算法的因子矩陣更新公式，具體如下：

（3）和（4）中的γ指的是步長，也即是學習速率，它是一個超參數，需要調參確定。對於梯度見（1）和（2）。
下面說下迭代終止的條件。迭代終止的條件有很多種，就目前我了解的主要有
1） 設置一個閾值，當L函數值小於閾值時就停止迭代，不常用
2） 設置一個閾值，當前後兩次函數值變化絕對值小於閾值時，停止迭代
3） 設置固定迭代次數
另外還有一個問題，當用戶-項目評分矩陣R非常稀疏時，就會出現過擬合（overfitting）的問題，過擬合問題的解決方法就是正則化（regularization）。正則化其實就是在目標函數中加上用戶因子向量和項目因子向量的二范數，當然也可以加上一范數。至於加上一范數還是二范數要看具體情況，一范數會使很多因子為0，從而減小模型大小，而二范數則不會它只能使因子接近於0，而不能使其為0，關於這個的介紹可參考論文Regression Shrinkage and Selection via the Lasso。引入正則化項後目標函數變為：

（5）中λ_1和λ_2是指正則項的權重，這兩個值可以取一樣，具體取值也需要根據數據集調參得到。優化方法和前面一樣，只是梯度公式需要更新一下。
矩陣分解演算法目前在推薦系統中應用非常廣泛，對於使用RMSE作為評價指標的系統尤為明顯，因為矩陣分解的目標就是使RMSE取值最小。但矩陣分解有其弱點，就是解釋性差，不能很好為推薦結果做出解釋。
後面會繼續介紹矩陣分解演算法的擴展性問題，就是如何加入隱反饋信息，加入時間信息等。

㈡ 推薦系統UserCF和ItemCF

UserCF（User Collaboration Filter），又稱 基於用戶的協同過濾演算法。

協同過濾：就是指眾多的用戶可以齊心協力，通過不斷地和網站互動，使 自己的推薦列表能夠不斷過濾掉自己不感興趣的物品，從而越來越滿足自己的需求。

而基於用戶是指通過分析用戶對商品的行為（如瀏覽、收藏、加入購物車、購買……）計算出哪些用戶是興趣相似的，然後把興趣相似的用戶所關注的商品相互推薦。

舉個例子：

由上表可以看出用戶A和用戶C比較相似，所以把用戶A感興趣的商品4推薦給用戶C。

步驟一般分為兩步：

再舉個詳細點的例子：

假設我們這么一些數據(用戶(字母) 商品(數字)_行為，)：

我們可以給不同的行為賦予不同的評分（假設瀏覽1分、收藏3分、加入購物車5分、購買10分），得到以下數據：

這樣看著比較累，而且也不方便計算，可以把它轉換為矩陣形式,稱之為 評分矩陣 ：

計算相似度

計算相似度的方式有很多，如餘弦相似度、切比雪夫距離、歐里幾得距離、曼哈頓距離、傑卡德距離、皮爾森系數……計算相似度的方式不同計算出來的相似度也不同。

這里只介紹餘弦相似度，其他的請自行網路。

假設有二維向量a,b如下圖所示

則他們的餘弦相似度為

推廣到多維向量a(a1,a2,a3,a4……)，b(b1,b2,b3,b4……)

有了公式就能計算出用戶相似度了：

推薦列表 = 相似度矩陣 X 評分矩陣

由於用戶已經對推薦列表中的一些商品有過行為，所以還要把這些商品給濾除掉

得到最終的推薦列表，其數值代表的意義是用戶對商品的感興趣程度：

ItemCF（Item Collaboration Filter），又稱 基於商品(物品)的協同過濾演算法。

其原理與UserCF類似，是基於用戶對商品的偏好找到相似的商品，然後推薦相似的商品品給他。
計算過程也非常相似，區別在於計算時把UserCF的 評分矩陣轉置 ，再計算商品與商品之間的相似度得到 商品之間的相似度矩陣 。
最後的 推薦列表 = 商品之間的相似度矩陣 X 評分矩陣轉置

對於電子商務，用戶數量一般大大超過商品數量，此時Item CF的計算復雜度較低。
比如在購書網站上，當你看一本書的時候，推薦引擎會給你推薦相關的書籍，這個推薦的重要性進進超過了網站首頁對該用戶的綜合推薦。可以看到，在這種情況下，Item CF 的推薦成為了引導用戶瀏覽的重要手段。基於物品的協同過濾演算法，是目前電子商務採用最廣泛的推薦演算法。

在非社交網路的網站中，內容內在的聯系是很重要的推薦原則，它比基於相似用戶的推薦原則更加有效。在社交網路站點中，User CF 是一個更好錯的選擇，User CF 加上社會網路信息，可以增加用戶對推薦解釋的信服程度。

推薦多樣性和精度，各有千秋。

參考：
Spark基於用戶的協同過濾演算法 https://www.toutiao.com/a6498952374487368205/?tt_from=mobile_qq&utm_campaign=client_share&app=news_article&utm_source=mobile_qq&iid=15393016323&utm_medium=toutiao_android

推薦系統_itemCF和userCF
http://blog.csdn.net/u011263983/article/details/51498458

㈢ 協同過濾演算法

用戶行為數據在網站上最簡單的存在形式就是日誌，比如用戶在電子商務網站中的網頁瀏覽、購買、點擊、評分和評論等活動。 用戶行為在個性化推薦系統中一般分兩種——顯性反饋行為(explicit feedback)和隱性反饋 行為(implicit feedback)。顯性反饋行為包括用戶明確表示對物品喜好的行為。網站中收集顯性反饋的主要方式就是評分和喜歡/不喜歡。隱性反饋行為指的是那些不能明確反應用戶喜好 的行為。最具代表性的隱性反饋行為就是頁面瀏覽行為。 按照反饋的明確性分，用戶行為數據可以分為顯性反饋和隱性反饋，但按照反饋的方向分， 又可以分為正反饋和負反饋。正反饋指用戶的行為傾向於指用戶喜歡該物品，而負反饋指用戶的 行為傾向於指用戶不喜歡該物品。在顯性反饋中，很容易區分一個用戶行為是正反饋還是負反饋， 而在隱性反饋行為中，就相對比較難以確定。

在利用用戶行為數據設計推薦演算法之前，研究人員首先需要對用戶行為數據進行分析，了解 數據中蘊含的一般規律，這樣才能對演算法的設計起到指導作用。

(1) 用戶活躍度和物品流行度

(2) 用戶活躍度和物品流行度的關系

一般認為，新用戶傾向於瀏覽熱門的物品，因為他 們對網站還不熟悉，只能點擊首頁的熱門物品，而老用戶會逐漸開始瀏覽冷門的物品。如果用橫坐標表示用戶活躍度，縱坐標表示具有某個活躍度的所有用戶評過分的物品的平均流行度。圖中曲線呈明顯下 降的趨勢，這表明用戶越活躍，越傾向於瀏覽冷門的物品。

僅僅基於用戶行為數據設計的推薦演算法一般稱為協同過濾演算法。學術界對協同過濾演算法進行了深入研究，提出了很多方法，比如基於鄰域的方法(neighborhood-based)、隱語義模型 (latent factor model)、基於圖的隨機遊走演算法(random walk on graph)等。在這些方法中， 最著名的、在業界得到最廣泛應用的演算法是基於鄰域的方法，而基於鄰域的方法主要包含下面兩種演算法。

基於用戶的協同過濾演算法 ：這種演算法給用戶推薦和他興趣相似的其他用戶喜歡的物品

基於物品的協同過濾演算法： 這種演算法給用戶推薦和他之前喜歡的物品相似的物品

基於鄰域的演算法是推薦系統中最基本的演算法，該演算法不僅在學術界得到了深入研究，而且在 業界得到了廣泛應用。基於鄰域的演算法分為兩大類，一類是基於用戶的協同過濾演算法，另一類是 基於物品的協同過濾演算法。現在我們所說的協同過濾，基本上就就是指基於用戶或者是基於物品的協同過濾演算法，因此，我們可以說基於鄰域的演算法即是我們常說的協同過濾演算法

(1) 基於用戶的協同過濾演算法（UserCF）

基於用戶的協同過濾演算法的基本思想是：在一個在線個性化推薦系統中，當一個用戶A需要個性化推薦 時，可以先找到和他有相似興趣的其他用戶，然後把那些用戶喜歡的、而用戶A沒有聽說過的物品推薦給A。

Ø 從上面的描述中可以看到，基於用戶的協同過濾演算法主要包括兩個步驟。 第一步：找到和目標用戶興趣相似的用戶集合。 第二步： 找到這個集合中的用戶喜歡的，且目標用戶沒有聽說過的物品推薦給目標用戶。

這里，步驟1的關鍵是計算兩個用戶的興趣相似度，協同過濾演算法主要利用行為的相似度計算興趣的相似度。給定用戶u和用戶v，令N(u)表示用戶u曾經有過正反饋的物品集合，令N(v) 為用戶v曾經有過正反饋的物品集合。那麼我們可以通過以下方法計算用戶的相似度：

基於餘弦相似度

(2) 基於物品的協同過濾演算法（itemCF）
與UserCF同理
(3) UserCF和itemCF的比 較

首先我們提出一個問題，為什麼新聞網站一般使用UserCF，而圖書、電商網站一般使用ItemCF呢？ 首先回顧一下UserCF演算法和ItemCF演算法的推薦原理。UserCF給用戶推薦那些和他有共同興 趣愛好的用戶喜歡的物品，而ItemCF給用戶推薦那些和他之前喜歡的物品類似的物品。從這個算 法的原理可以看到，UserCF的推薦結果著重於反映和用戶興趣相似的小群體的熱點，而ItemCF 的推薦結果著重於維系用戶的歷史興趣。換句話說，UserCF的推薦更社會化，反映了用戶所在的小型興趣群體中物品的熱門程度，而ItemCF的推薦更加個性化，反映了用戶自己的興趣傳承。 在新聞網站中，用戶的興趣不是特別細化，絕大多數用戶都喜歡看熱門的新聞。個性化新聞推薦更加強調抓住 新聞熱點，熱門程度和時效性是個性化新聞推薦的重點，而個性化相對於這兩點略顯次要。因 此，UserCF可以給用戶推薦和他有相似愛好的一群其他用戶今天都在看的新聞，這樣在抓住熱 點和時效性的同時，保證了一定程度的個性化。同時，在新聞網站中，物品的更新速度遠遠快於新用戶的加入速度，而且 對於新用戶，完全可以給他推薦最熱門的新聞，因此UserCF顯然是利大於弊。

但是，在圖書、電子商務和電影網站，比如亞馬遜、豆瓣、Netflix中，ItemCF則能極大地發 揮優勢。首先，在這些網站中，用戶的興趣是比較固定和持久的。一個技術人員可能都是在購買 技術方面的書，而且他們對書的熱門程度並不是那麼敏感，事實上越是資深的技術人員，他們看 的書就越可能不熱門。此外，這些系統中的用戶大都不太需要流行度來輔助他們判斷一個物品的 好壞，而是可以通過自己熟悉領域的知識自己判斷物品的質量。因此，這些網站中個性化推薦的 任務是幫助用戶發現和他研究領域相關的物品。因此，ItemCF演算法成為了這些網站的首選演算法。 此外，這些網站的物品更新速度不會特別快，一天一次更新物品相似度矩陣對它們來說不會造成 太大的損失，是可以接受的。同時，從技術上考慮，UserCF需要維護一個用戶相似度的矩陣，而ItemCF需要維護一個物品 相似度矩陣。從存儲的角度說，如果用戶很多，那麼維護用戶興趣相似度矩陣需要很大的空間， 同理，如果物品很多，那麼維護物品相似度矩陣代價較大

下表是對二者的一個全面的表較：

㈣ 個性化推薦演算法——協同過濾

電子商務推薦系統的一種主要演算法。
協同過濾推薦（Collaborative Filtering recommendation）是在信息過濾和信息系統中正迅速成為一項很受歡迎的技術。與傳統的基於內容過濾直接分析內容進行推薦不同，協同過濾分析用戶興趣，在用戶群中找到指定用戶的相似（興趣）用戶，綜合這些相似用戶對某一信息的評價，形成系統對該指定用戶對此信息的喜好程度預測。
與傳統文本過濾相比，協同過濾有下列優點:
（1）能夠過濾難以進行機器自動基於內容分析的信息。如藝術品、音樂;
（2）能夠基於一些復雜的，難以表達的概念（信息質量、品位)進行過濾;
（3）推薦的新穎性。
正因為如此，協同過濾在商業應用上也取得了不錯的成績。Amazon，CDNow，MovieFinder，都採用了協同過濾的技術來提高服務質量。
缺點是:
（1）用戶對商品的評價非常稀疏，這樣基於用戶的評價所得到的用戶間的相似性可能不準確（即稀疏性問題）;
（2）隨著用戶和商品的增多，系統的性能會越來越低;
（3）如果從來沒有用戶對某一商品加以評價，則這個商品就不可能被推薦（即最初評價問題）。
因此，現在的電子商務推薦系統都採用了幾種技術相結合的推薦技術。
案例: AMAZON 個性化推薦系統先驅 (基於協同過濾)
AMAZON是一個虛擬的網上書店,它沒有自己的店面,而是在網上進行在線銷售. 它提供了高質量的綜合節目資料庫和檢索系統,用戶可以在網上查詢有關圖書的信息.如果用戶需要購買的化,可以把選擇的書放在虛擬購書籃中,最後查看購書籃中的商品,選擇合適的服務方式並且提交訂單,這樣讀者所選購的書在幾天後就可以送到家.
AMAZON書店還提供先進的個性化推薦功能,能為不同興趣偏好的用戶自動推薦符合其興趣需要的書籍. AMAZON使用推薦軟體對讀者曾經購買過的書以及該讀者對其他書的評價進行分析後,將向讀者推薦他可能喜歡的新書,只要滑鼠點一下,就可以買到該書了;AMAZON能對顧客購買過的東西進行自動分析,然後因人而異的提出合適的建議. 讀者的信息將被再次保存.這樣顧客下次來時就能更容易的買到想要的書. 此外,完善的售後服務也是AMAZON的優勢,讀者可以在拿到書籍的30天內,將完好無損的書和音樂光碟退回AMAZON, AMAZON將原價退款. 當然AMAZON的成功還不止於此, 如果一位顧客在AMAZON購買一本書,下次他再次訪問時,映入眼簾的首先是這位顧客的名字和歡迎的字樣.

㈤ 關於演算法

阿朱對於演算法的了解不多，總結如下，希望多多交流，改正瑕疵。

演算法推薦主要有5種方式：

基於內容推薦：這是基於用戶個人興趣的推薦。根據用戶個體的歷史行為，計算對內容特徵的偏好程度，進而推薦出與用戶特徵偏好匹配的內容。

協同過濾演算法：這是基於群體的推薦。基於用戶的相似度、內容的共現度，以及基於人口特徵將用戶聚集為不同群體來推薦。（解釋一下：常見的協同過濾演算法有兩種，一種是基於用戶的（user-based），也即計算用戶之間的相似性，如果A和B的興趣相近，那麼A喜歡的電影，B也很有可能喜歡。另一種是基於物品的（item-based），也即計算物品之間的相似性，如果電影C和電影D很相似，那麼喜歡電影C的人，可能也會喜歡電影D。）

擴展推薦：基於用戶興趣點、內容類別等擴展。（你喜歡歷史資訊，我推考古、尋寶的資訊給你）

新熱推薦：基於全局內容的時效性、熱度推薦。（在產品初期同時缺乏用戶數據和內容數據時，內容分發效率很低。使用基於內容推薦演算法效果不顯著，而使用一些熱點話題可在保證一定流量的同時，不斷通過用戶的個人行為（點贊、評論、瀏覽、收藏）來逐步精確用戶畫像和進行內容沉澱，為之後的個性化推薦做准備）。

環境特徵：基於地域、時間、場景等推薦。（知乎上你們市的牙科診所廣告、婚慶廣告）

每種演算法的效果不一，組合味道更佳，因此很多公司都是採用「演算法矩陣」的方式來推薦feed。（後文也會談到這一點）

優勢:

內容質量審核、社區治理（辱罵、撕逼），推薦商品，減少人工運營成本。

源源不斷推薦給你感興趣的feed，提升了用戶粘性，商業化的潛力進一步加大。

讓用戶 kill time 的需求更好地被滿足，增強用戶體驗

弊端：

1.演算法本身或者演算法背後的人產生技術錯誤——只要是人寫的演算法，就一定有出錯的概率，比如德國居民凌晨發飆的智能音箱、失控的Uber自動駕駛汽車就是程序上的Bug導致的，這一類我們克服的辦法其實相對簡單。但對於另一種人為算計消費者的演算法有時候可能我們就無能為力了，比如大數據殺熟現象，無論真實與否，這類問題往往很難識別，因此也加大了監管的難度；（抖音視頻里你見不到「錢」字，只能看到「Q」來代替）

2.演算法對於人性部分的忽略——現在的人工智慧離真正理解人類的感情和行為依然有巨大的鴻溝，Facebook提醒你給去世的親人發生日祝福背後本質的原因在於AI無法真正理解死亡對於人類意味著什麼；因此需要人機結合（平台人工參與，用戶舉報等自治措施），不能單獨依靠演算法。

3.演算法訓練數據本身的偏見——目前人工智慧的基本邏輯是先構建一個合適的機器學習模型，然後用大量的數據去訓練模型，然後用訓練好的模型再來預測新的數據，這里邊有一個非常重要前提就是輸入數據的重要性，比如變壞的微軟機器人Tay之所以產生問題就是因為輸入的數據中本身就存在偏見，如果現實世界數據本身就存在偏見，那麼預測結果也一定會有偏見；

先下結論吧：演算法不會導致「信息繭房」

「社交媒體和演算法推薦導致信息繭房」這一判斷成立的一個重要前提是：我們只會點擊那些我們熟悉的、贊同的內容，不斷讓機器加深對我們的印象：原來他們只喜歡看這些！

但在現實中，這個前提是過於簡化的，乃至是錯誤的。

在個體層面，我們有著多樣的閱讀動機，受到各種認知偏見的影響，可能傾向於點擊某些特定類型的內容，但絕不僅僅局限於自己認同的那些。

在社交層面：我們在大多數APP上都存在著社交關系，以及主動選擇關注的帳號，這些都對我們能接觸到的內容產生重要影響。一個在APP上擁有一定社交關系的人，不太可能陷入狹窄的視野當中。

在技術層面：在演算法的分類里說了，每種演算法都有其利弊，因此很多公司都是採用「演算法矩陣」的方式來推薦feed。但在普羅大眾眼裡，演算法=基於內容的推薦演算法，而忽略了「基於內容的推薦演算法」只是演算法種類里的一種，其他類型演算法也會被產品使用。

在企業層面：沒有一個商場的經理，希望顧客每一次來到商場都只關注同一類別的商品。用戶興趣窄化對於商業化目標並不是一個好的選擇。

博弈：

推薦太強了，關注力量就會弱。抖音沉浸式交互和基於內容的演算法推薦是 kill time 的利器，推薦feed刷的過癮了，你還會去刷關注feed嗎？

共生：

演算法有弊端，關注可以彌補或有所增益。推薦feed是忽略了人"社交性「這個特點，以知乎為例，關注的內容生產者傳遞給我們價值，所以我們需要一個途徑來知道那幾十個或上百的關注對象的產出內容。朋友圈滿足我們窺探的信息需求，也同理。（另外從結果反推過程，大家看一下手裡的B站、知乎、抖音、快手就清楚了）