基于用戶的協同過濾算法
什么是推薦算法
推薦算法最早在1992年就提出來了，但是火起來實際上是最近這些年的事情，因為互聯網的爆發，有了更大的數據量可以供我們使用，推薦算法才有了很大的用武之地。
最開始，所以我們在網上找資料，都是進yahoo，然后分門別類的點進去，找到你想要的東西，這是一個人工過程，到后來，我們用google，直接搜索自己需要的內容，這些都可以比較精準的找到你想要的東西，但是，如果我自己都不知道自己要找什么腫么辦？最典型的例子就是，如果我打開豆瓣找電影，或者我去買說，我實際上不知道我想要買什么或者看什么，這時候推薦系統就可以派上用場了。
推薦算法的條件
推薦算法從92年開始，發展到現在也有20年了，當然，也出了各種各樣的推薦算法，但是不管怎么樣，都繞不開幾個條件，這是推薦的基本條件
- 根據和你共同喜好的人來給你推薦
- 根據你喜歡的物品找出和它相似的來給你推薦
- 根據你給出的關鍵字來給你推薦，這實際上就退化成搜索算法了
- 根據上面的幾種條件組合起來給你推薦
實際上，現有的條件就這些啦，至于怎么發揮這些條件就是八仙過海各顯神通了，這么多年沉淀了一些好的算法，今天這篇文章要講的基于用戶的協同過濾算法就是其中的一個，這也是最早出現的推薦算法，并且發展到今天，基本思想沒有什么變化，無非就是在處理速度上，計算相似度的算法上出現了一些差別而已。
基于用戶的協同過濾算法
我們先做個詞法分析 基于用戶 說明這個算法是以用戶為主體的算法，這種以用戶為主體的算法比較強調的是社會性的屬性，也就是說這類算法更加強調把 和你有相似愛好的其他的用戶的物品 推薦給你，與之對應的是基于物品的推薦算法，這種更加強調把 和你你喜歡的物品相似的物品 推薦給你。
然后就是 協同過濾 了，所謂 協同 就是大家一起幫助你啦，然后后面跟個 過濾 ，就是大家是商量過后才把結果告訴你的，不然信息量太大了。。
所以，綜合起來說就是這么一個算法，那些和你有相似愛好的小伙伴們一起來商量一下，然后告訴你什么東西你會喜歡。
算法描述
相似性計算
我們盡量不使用復雜的數學公式，一是怕大家看不懂，難理解，二是我是用mac寫的blog,公式不好畫，太麻煩了。。
所謂計算相似度，有兩個比較經典的算法
- Jaccard算法，就是交集除以并集，詳細可以看看我 這篇 文章。
- 余弦距離相似性算法，這個算法應用很廣，一般用來計算向量間的相似度，具體公式大家google一下吧，或者看看 這里
- 各種其他算法，比如歐氏距離算法等等。
不管使用Jaccard還是用余弦算法，本質上需要做的還是求兩個向量的相似程度，使用哪種算法完全取決于現實情況。
我們在本文中用的是余弦距離相似性來計算兩個用戶之間的相似度。
與目標用戶最相鄰的K個用戶
我們知道，在找和你興趣愛好相似的小伙伴的時候，我們可能可以找到幾百個，但是有些是好基友，但有些只是普通朋友，那么一般的，我們會定一個數K，和你最相似的K個小伙伴就是你的好基友了，他們的愛好可能和你的愛好相差不大，讓他們來推薦東西給你（比如肥皂）是最好不過了。
何為和你相似呢？簡單的說就是，比如你喜歡 macbook,iphone,ipad ，A小伙伴喜歡 macbook,iphone,note2,小米盒子,肥皂，蠟燭 ,B小伙伴喜歡 macbook,iphone,ipad,肥皂,潤膚霜 ,C女神喜歡 雅詩蘭黛,SK2,香奈兒 ，D屌絲喜歡 ipad,諾基亞8250,小霸王學習機 那么很明顯，B小伙伴和你更加相似，而C女神完全和你不在一個檔次上，那我們推薦的時候會把 肥皂 推薦給你，因為我們覺得肥皂可能最適合你。
那么，如何找出這K個基友呢？最直接的辦法就是把目標用戶和數據庫中的所有用戶進行比較，找出和目標用戶最相似的K個用戶，這就是好基友了。
這么做理論上是沒什么問題的，但是當數據量巨大的時候，計算K個基友的時間將會非常長，而且你想想就知道，數據庫中的大部分用戶其實和你是沒有什么交集的，所沒必要計算所有用戶了，只需要計算和你有交集的用戶就行了。
要計算和你有交集的用戶，就要用到 物品到用戶的反查表 ，什么是反查表呢？很簡單，還是是上面那個AB小伙伴和C女神的例子，反查表就是喜歡macbook的有 你，A，B ，喜歡iphone的有 你，B 。。。就是喜歡某些物品的用戶，有了這個表，我們就可以看出來，和你有關系的用戶就只有A和B，D了，而C女神和你沒有任何交集，所以不用去想C了。
這樣，我們有了A和B,D，然后就分別計算A和B,D與你的相似度，不管用哪個相似性公式，我們算出來都是B和你更相似(在這個例子中，一般會用Jaccard來計算，因為這些向量不是特別好余弦化)， 但如果此時我們的 K 設定為2，那么我們就得出了與你最相鄰的基友是B和A。
這就是與目標用戶最相鄰的K個用戶的計算。
通過這K個用戶來推薦商品了
好了，你的好基友我們也算出來了，接下來要向你推薦商品了。但是我們可推薦的商品有 小米盒子，note2，蠟燭，潤膚霜，肥皂 這么四種，到底哪種才是你需要的呢？這里的算法就比較廣泛了，我們可以不排序，都一股腦推薦給你，但這明顯可能有些你不怎么感興趣，我們也可以做一些處理，假如我們算出來A和你的相似度是25%，B和你的相似度是80%，那么對于上面這些產品，我們的推薦度可以這么來算
- 小米盒子: 1*0.25 = 0.25
- note2: 1*0.25 = 0.25
- 蠟燭: 1*0.25 = 0.25
- 潤膚霜: 1*0.8 = 0.8
- 肥皂: 1*0.8+1*0.25=1.05
這樣就一目了然了，很明顯，我們會首先把肥皂推薦給你，這個可能是你最需要的，其次是潤膚霜，然后才是蠟燭，小米盒子和note2。
當然，你可以把上述結果歸一化或者用其他你覺得合適的方式來計算推薦度，不管怎么算，推薦度還是得和基友與你相似度有關系，就是那個0.8和0.25一定要用上，不然前面白算了。
算法總結
好了，通過這個例子，你大概知道了為什么會推薦肥皂給你了吧，這就是基于用戶的協同推薦算法的描述，總結起來就是這么幾步
- 計算其他用戶和你的相似度，可以使用反差表忽略一部分用戶
- 根據相似度的高低找出K個與你最相似的鄰居
- 在這些鄰居喜歡的物品中，根據鄰居與你的遠近程度算出每一件物品的推薦度
- 根據每一件物品的推薦度高低給你推薦物品。
比如上面那個例子，首先，我們通過反查表忽略掉了C女神，然后計算出A和B,D與你的相似度，然后根據K=2找出最相似的鄰居A和B，接著根據A,B與你相似度計算出每件物品的推薦度并排序，最后根據排好序的推薦度給你推薦商品。
怎么樣，是不是很簡單啊。
算法存在的問題
這個算法實現起來也比較簡單，但是在實際應用中有時候也會有問題的。
比如一些非常流行的商品可能很多人都喜歡，這種商品推薦給你就沒什么意義了，所以計算的時候需要對這種商品加一個權重或者把這種商品完全去掉也行。
再有，對于一些通用的東西，比如買書的時候的工具書，如現代漢語詞典，新華字典神馬的，通用性太強了，推薦也沒什么必要了。
這些都是推薦系統的臟數據，如何去掉臟數據，這是數據預處理的時候事情了，這里就不多說了。
來個實戰的吧
說了這么多，肥皂也推薦了，那么我們來點實際的，我這里下載了 movieLens 的數據集，至于這個集合是什么大家google一下，反正很多地方用來做測試算法的數據，這個數據集里面有很多用戶對于電影的打分，我們的需求是隨便輸入一個用戶，然后根據協同算法，給他推薦一些個電影。
由于用戶給電影打分有好有壞[1到5分]，而我們上面的例子中都是說的喜歡某件物品而沒有說不喜歡的情況，所以首先，我們要把數據處理一下，簡單的來做，我們可以認為3分以上的話代表這個用戶喜歡這個電影，否則就是不喜歡，這樣顯得有點太死板了，我們也可以這么來定義，比如用戶A對30部電影打分了，首先求出他打分的平均值，然后高于這個平均值的我們覺得用戶喜歡這個電影，否則認為他不喜歡。
好了，用戶的喜歡與不喜歡的問題解決了。下面就可以開始算法了，代碼不全貼出來了，貼個流程吧，具體代碼可以去看我的 github
#讀取文件數據
test_contents=readFile(file_name)
#文件數據格式化成二維數組 List[[用戶id,電影id,電影評分]...]
test_rates=getRatingInformation(test_contents)
#格式化成字典數據
# 1.用戶字典：dic[用戶id]=[(電影id,電影評分)...]
# 2.電影用戶反查表：dic[電影id]=[用戶id1,用戶id2...]
test_dic,test_item_to_user=createUserRankDic(test_rates)
#尋找鄰居
neighbors=calcNearestNeighbor(userid,test_dic,test_item_to_user)[:k]
#計算推薦列表
recommend_dic={}
for neighbor in neighbors:
neighbor_user_id=neighbor[1]
movies=test_dic[neighbor_user_id]
for movie in movies:
if movie[0] not in recommend_dic:
recommend_dic[movie[0]]=neighbor[0]
else:
recommend_dic[movie[0]]+=neighbor[0]
#建立推薦列表
recommend_list=[]
for key in recommend_dic:
recommend_list.append([recommend_dic[key],key]
recommend_list.sort(reverse=True)
#讀取文件數據
test_contents=readFile(file_name)
#文件數據格式化成二維數組 List[[用戶id,電影id,電影評分]...]
test_rates=getRatingInformation(test_contents)
#格式化成字典數據
# 1.用戶字典：dic[用戶id]=[(電影id,電影評分)...]
# 2.電影用戶反查表：dic[電影id]=[用戶id1,用戶id2...]
test_dic,test_item_to_user=createUserRankDic(test_rates)
#尋找鄰居
neighbors=calcNearestNeighbor(userid,test_dic,test_item_to_user)[:k]
#計算推薦列表
recommend_dic={}
for neighborin neighbors:
neighbor_user_id=neighbor[1]
movies=test_dic[neighbor_user_id]
for moviein movies:
if movie[0] not in recommend_dic:
recommend_dic[movie[0]]=neighbor[0]
else:
recommend_dic[movie[0]]+=neighbor[0]
#建立推薦列表
recommend_list=[]
for keyin recommend_dic:
recommend_list.append([recommend_dic[key],key]
recommend_list.sort(reverse=True)
對于隨便輸入一個用戶，我們得到以下這個推薦結果
movie name release ======================================================= Contact (1997) 11-Jul-1997 Scream (1996) 20-Dec-1996 Liar Liar (1997) 21-Mar-1997 Saint, The (1997) 14-Mar-1997 English Patient, The (1996) 15-Nov-1996 Titanic (1997) 01-Jan-1997 Air Force One (1997) 01-Jan-1997 Star Wars (1977) 01-Jan-1977 Conspiracy Theory (1997) 08-Aug-1997 Toy Story (1995) 01-Jan-1995 Fargo (1996) 14-Feb-1997
moviename release ======================================================= Contact (1997) 11-Jul-1997 Scream (1996) 20-Dec-1996 LiarLiar (1997) 21-Mar-1997 Saint, The (1997) 14-Mar-1997 EnglishPatient, The (1996) 15-Nov-1996 Titanic (1997) 01-Jan-1997 AirForceOne (1997) 01-Jan-1997 StarWars (1977) 01-Jan-1977 ConspiracyTheory (1997) 08-Aug-1997 ToyStory (1995) 01-Jan-1995 Fargo (1996) 14-Feb-1997
多輸入幾個用戶你就會發現，像Titanic，Star Wars這種超級熱門的電影，只要你選的這個用戶沒看過，推薦系統就一定會推薦給你，這就是我們前面說的臟數據，實際系統中這種數據是需要處理掉得。我們這篇文章只做算法講解，就不去管這些東西了。