機器學習(36)之協同過濾典型演算法概述【精華】
微信公眾號
關鍵字全網搜索最新排名
【機器學習演算法】
：
排名第一
【機器學習】
：排名第一
【Python】
：排名第三
【演算法】
：排名第四
前言
推薦演算法具有非常多的應用場景和商業價值，因此對推薦演算法值得好好研究。
推薦演算法種類很多，但是目前應用最廣泛的應該是協同過濾類別的推薦演算法
，本文就對協同過濾類別的推薦演算法做一個概括總結，後續也會對一些典型的協同過濾推薦演算法做原理總結。
推薦演算法概述
推薦演算法是非常古老的，在機器學習還沒有興起的時候就有需求和應用了。概括來說，可以分為以下5種：
1）基於內容的推薦：
這一類一般依賴於自然語言處理NLP的一些知識，通過挖掘文本的TF-IDF特徵向量，來得到用戶的偏好，進而做推薦。這類推薦演算法可以找到用戶獨特的小眾喜好，而且還有較好的解釋性。這一類由於需要NLP的基礎，本文就不多講，在後面專門講NLP的時候再討論。2）協調過濾推薦：
本文後面要專門講的內容。協調過濾是推薦演算法中目前最主流的種類，花樣繁多，在工業界已經有了很多廣泛的應用。它的優點是不需要太多特定領域的知識，可以通過基於統計的機器學習演算法來得到較好的推薦效果。最大的優點是工程上容易實現，可以方便應用到產品中。目前絕大多數實際應用的推薦演算法都是協同過濾推薦演算法。3）混合推薦：
這個類似我們機器學習中的集成學習，博才眾長，通過多個推薦演算法的結合，得到一個更好的推薦演算法，起到三個臭皮匠頂一個諸葛亮的作用。比如通過建立多個推薦演算法的模型，最後用投票法決定最終的推薦結果。混合推薦理論上不會比單一任何一種推薦演算法差，但是使用混合推薦，演算法複雜度就提高了，在實際應用中有使用，但是並沒有單一的協調過濾推薦演算法，比如邏輯回歸之類的二分類推薦演算法廣泛。4）基於規則的推薦：
這類演算法常見的比如基於最多用戶點擊，最多用戶瀏覽等，屬於大眾型的推薦方法，在目前的大數據時代並不主流。5）基於人口統計信息的推薦：
這一類是最簡單的推薦演算法了，它只是簡單的根據系統用戶的基本信息發現用戶的相關程度，然後進行推薦，目前在大型系統中已經較少使用。協同過濾推薦概述
協同過濾(Collaborative Filtering)
作為推薦演算法中最經典的類型，包括在線的協同和離線的過濾兩部分。所謂在線協同，就是通過在線數據找到用戶可能喜歡的物品，而離線過濾，則是過濾掉一些不值得推薦的數據，比比如推薦值評分低的數據，或者雖然推薦值高但是用戶已經購買的數據。協同過濾的模型一般為m個物品，m個用戶的數據，只有部分用戶和部分數據之間是有評分數據的，其它部分評分是空白，此時我們要用已有的部分稀疏數據來預測那些空白的物品和數據之間的評分關係，找到最高評分的物品推薦給用戶。
一般來說，協同過濾推薦分為三種類型。第一種是基於用戶(user-based)的協同過濾，第二種是基於項目(item-based)的協同過濾，第三種是基於模型(model based)的協同過濾。
基於用戶(user-based)的協同過濾主要考慮的是用戶和用戶之間的相似度，只要找出相似用戶喜歡的物品，並預測目標用戶對對應物品的評分，就可以找到評分最高的若干個物品推薦給用戶。而基於項目(item-based)的協同過濾和基於用戶的協同過濾類似，只不過這時我們轉向找到物品和物品之間的相似度，只有找到了目標用戶對某些物品的評分，那麼我們就可以對相似度高的類似物品進行預測，將評分最高的若干個相似物品推薦給用戶。比如你在網上買了一本機器學習相關的書，網站馬上會推薦一堆機器學習，大數據相關的書給你，這裡就明顯用到了基於項目的協同過濾思想。
我們可以簡單比較下基於用戶的協同過濾和基於項目的協同過濾：基於用戶的協同過濾需要在線找用戶和用戶之間的相似度關係，計算複雜度肯定會比基於基於項目的協同過濾高。但是可以幫助用戶找到新類別的有驚喜的物品。而基於項目的協同過濾，由於考慮的物品的相似性一段時間不會改變，因此可以很容易的離線計算，準確度一般也可以接受，但是推薦的多樣性來說，就很難帶給用戶驚喜了。一般對於小型的推薦系統來說，基於項目的協同過濾肯定是主流。但是如果是大型的推薦系統來說，則可以考慮基於用戶的協同過濾，當然更加可以考慮我們的第三種類型，基於模型的協同過濾。
基於模型(model based)的協同過濾是目前最主流的協同過濾類型了，我們的一大堆機器學習演算法也可以在這裡找到用武之地。下面我們就重點介紹基於模型的協同過濾。
基於模型的協同過濾
基於模型的協同過濾作為目前最主流的協同過濾類型，其相關演算法可以寫一本書了，當然我們這裡主要是對其思想做有一個歸類概括。我們的問題是這樣的m個物品，m個用戶的數據，只有部分用戶和部分數據之間是有評分數據的，其它部分評分是空白，此時我們要用已有的部分稀疏數據來預測那些空白的物品和數據之間的評分關係，找到最高評分的物品推薦給用戶。
對於這個問題，用機器學習的思想來建模解決，主流的方法可以分為：用關聯演算法，聚類演算法，分類演算法，回歸演算法，矩陣分解，神經網路,圖模型以及隱語義模型來解決。下面我們分別加以介紹。
data space與weight space恰好是對稱的關係，在data space中，數據是點，weight vector對應經過原點的超平面。由於一定經過原點，所以無法區分這四個點。
用關聯規則做協同過濾
一般我們可以找出用戶購買的所有物品數據里頻繁出現的項集活序列，來做頻繁集挖掘，找到滿足支持度閾值的關聯物品的頻繁N項集或者序列。如果用戶購買了頻繁N項集或者序列里的部分物品，那麼我們可以將頻繁項集或序列里的其他物品按一定的評分準則推薦給用戶，這個評分準則可以包括支持度，置信度和提升度等。
常用的關聯推薦演算法有Apriori，FP Tree和PrefixSpan。如果大家不熟悉這些演算法，可以參考之前的文章：
機器學習(22)之Apriori演算法原理總結
機器學習(31)之頻繁集挖掘FP Tree詳解
機器學習(35)之PrefixSpan演算法原理詳解
用聚類演算法做協同過濾
用聚類演算法做協同過濾就和前面的基於用戶或者項目的協同過濾有些類似了。我們可以按照用戶或者按照物品基於一定的距離度量來進行聚類。如果基於用戶聚類，則可以將用戶按照一定距離度量方式分成不同的目標人群，將同樣目標人群評分高的物品推薦給目標用戶。基於物品聚類的話，則是將用戶評分高物品的相似同類物品推薦給用戶。
常用的聚類推薦演算法有K-Means, BIRCH, DBSCAN和譜聚類，如果大家不熟悉這些演算法，可以參考之前的文章：
機器學習(7) -- k-means 聚類
機器學習(25)之K-Means聚類演算法詳解
機器學習(26)之K-Means實戰與調優詳解
機器學習(34)之BIRCH層次聚類詳解
用分類演算法做協同過濾
如果我們根據用戶評分的高低，將分數分成幾段的話，則這個問題變成分類問題。比如最直接的，設置一份評分閾值，評分高於閾值的就是推薦，評分低於閾值就是不推薦，我們將問題變成了一個二分類問題。雖然分類問題的演算法多如牛毛，但是目前使用最廣泛的是邏輯回歸。為啥是邏輯回歸而不是看起來更加高大上的比如支持向量機呢？因為邏輯回歸的解釋性比較強，每個物品是否推薦我們都有一個明確的概率放在這，同時可以對數據的特徵做工程化，得到調優的目的。目前邏輯回歸做協同過濾在BAT等大廠已經非常成熟了。
常見的分類推薦演算法有邏輯回歸和樸素貝葉斯，兩者的特點是解釋性很強。如果大家不熟悉這些演算法，可以參考之前的文章：
機器學習(2) -- logistic regression
機器學習(6)之樸素貝葉斯NB及實例
機器學習(10)之趣味案例理解樸素貝葉斯
趣味理解樸素貝葉斯
用回歸演算法做協同過濾
用回歸演算法做協同過濾比分類演算法看起來更加的自然。我們的評分可以是一個連續的值而不是離散的值，通過回歸模型我們可以得到目標用戶對某商品的預測打分。
常用的回歸推薦演算法有Ridge回歸，回歸樹和支持向量回歸。如果大家不熟悉這些演算法，可以參考之前的文章：
線性回歸與評價指標-2
機器學習(5)之決策樹ID3及Python實現
機器學習(12)之決策樹總結與python實踐(~附源碼鏈接~)
乾貨 | 詳解scikit-learn中隨機森林(RF)和梯度提升決策樹(GBDT)的參數調優
6分鐘教你如何使用Python編寫、可視化決策樹演算法（Iris數據集）
機器學習（15）之支持向量機原理(一)線性支持向量機
機器學習(16)之支持向量機原理(二)軟間隔最大化
機器學習(18)之支持向量機原理(三)線性不可分支持向量機與核函數
機器學習(19)之支持向量回歸機
用矩陣分解做協同過濾
用矩陣分解做協同過濾是目前使用也很廣泛的一種方法。由於傳統的奇異值分解SVD要求矩陣不能有缺失數據，必須是稠密的，而我們的用戶物品評分矩陣是一個很典型的稀疏矩陣，直接使用傳統的SVD到協同過濾是比較複雜的。
目前主流的矩陣分解推薦演算法主要是SVD的一些變種，比如FunkSVD，BiasSVD和SVD++。這些演算法和傳統SVD的最大區別是不再要求將矩陣分解為UΣVT
的形式，而變是兩個低秩矩陣PTQ的乘積形式。
用神經網路做協同過濾
用神經網路乃至深度學習做協同過濾應該是以後的一個趨勢。目前比較主流的用兩層神經網路來做推薦演算法的是限制玻爾茲曼機(RBM)。在目前的Netflix演算法比賽中， RBM演算法的表現很牛。當然如果用深層的神經網路來做協同過濾應該會更好，大廠商用深度學習的方法來做協同過濾應該是將來的一個趨勢。
用圖模型做協同過濾
用圖模型做協同過濾，則將用戶之間的相似度放到了一個圖模型裡面去考慮，常用的演算法是SimRank系列演算法和馬爾科夫模型演算法。對於SimRank系列演算法，它的基本思想是被相似對象引用的兩個對象也具有相似性。演算法思想有點類似於大名鼎鼎的PageRank。而馬爾科夫模型演算法當然是基於馬爾科夫鏈了，它的基本思想是基於傳導性來找出普通距離度量演算法難以找出的相似性。
用隱語義模型做協同過濾
隱語義模型主要是基於NLP的，涉及到對用戶行為的語義分析來做評分推薦，主要方法有隱性語義分析LSA和隱含狄利克雷分布LDA，這些等講NLP的再專門講。
協同過濾的新方向
當然推薦演算法的變革也在進行中，就算是最火爆的基於邏輯回歸推薦演算法也在面臨被取代。哪些演算法可能取代邏輯回歸之類的傳統協同過濾呢？下面是我的理解：
a) 基於集成學習的方法和混合推薦:這個和混合推薦也靠在一起了。由於集成學習的成熟，在推薦演算法上也有較好的表現。一個可能取代邏輯回歸的演算法是GBDT。目前GBDT在很多演算法比賽都有好的表現，而有工業級的並行化實現類庫。
b)基於矩陣分解的方法：矩陣分解，由於方法簡單，一直受到青睞。目前開始漸漸流行的矩陣分解方法有分解機(Factorization Machine)和張量分解(Tensor Factorization)。
c) 基於深度學習的方法：目前兩層的神經網路RBM都已經有非常好的推薦演算法效果，而隨著深度學習和多層神經網路的興起，以後可能推薦演算法就是深度學習的天下了？目前看最火爆的是基於CNN和RNN的推薦演算法。
小結
協同過濾作為一種經典的推薦演算法種類，在工業界應用廣泛，它的優點很多，模型通用性強，不需要太多對應數據領域的專業知識，工程實現簡單，效果也不錯。這些都是它流行的原因。
當然，協同過濾也有些難以避免的難題，比如令人頭疼的「冷啟動」問題，我們沒有新用戶任何數據的時候，無法較好的為新用戶推薦物品。同時也沒有考慮情景的差異，比如根據用戶所在的場景和用戶當前的情緒。當然，也無法得到一些小眾的獨特喜好，這塊是基於內容的推薦比較擅長的。
歡迎分享給他人讓更多的人受益
參考：
宗成慶《統計自然語言處理》 第2版
博客園
http://www.cnblogs.com/pinard/p/6744056.html
周志華《機器學習》
李航《統計學習方法》
goodfollow《深度學習》
《機器學習實戰》
近期熱文
資源&教程 | Python數據分析，詳細的學習路徑
Python實現對12500張貓狗圖像的精準分類
乾貨 | 卷積神經網路入門這一篇就夠了
精華 | 機器學習崗面試，這些是基礎！(ML,DL,SL相關知識整理)
加入微信機器學習交流
群
請添加微信：guodongwe1991
備註姓名-單位-研究方向
廣告、商業合作
請添加微信：guodongwe1991
（備註：商務合作）
