摘要：最近寫(xiě)搜索引擎文章寫(xiě)多了，來(lái)一篇之前寫(xiě)的老文，給那些對(duì)推薦算法感興趣想入門的人吧，最近也在做推薦廣告系統(tǒng)，又翻出來(lái)看了看。

最近寫(xiě)搜索引擎文章寫(xiě)多了，來(lái)一篇之前寫(xiě)的老文，給那些對(duì)推薦算法感興趣想入門的人吧，最近也在做推薦廣告系統(tǒng)，又翻出來(lái)看了看。

推薦算法最早在1992年就提出來(lái)了，但是火起來(lái)實(shí)際上是最近這些年的事情，因?yàn)榛ヂ?lián)網(wǎng)的爆發(fā)，有了更大的數(shù)據(jù)量可以供我們使用，推薦算法才有了很大的用武之地。

最開(kāi)始，所以我們?cè)诰W(wǎng)上找資料，都是進(jìn)yahoo，然后分門別類的點(diǎn)進(jìn)去，找到你想要的東西，這是一個(gè)人工過(guò)程，到后來(lái)，我們用google，直接搜索自己需要的內(nèi)容，這些都可以比較精準(zhǔn)的找到你想要的東西，但是，如果我自己都不知道自己要找什么腫么辦？最典型的例子就是，如果我打開(kāi)豆瓣找電影，或者我去買說(shuō)，我實(shí)際上不知道我想要買什么或者看什么，這時(shí)候推薦系統(tǒng)就可以派上用場(chǎng)了。

推薦算法從92年開(kāi)始，發(fā)展到現(xiàn)在也有20年了，當(dāng)然，也出了各種各樣的推薦算法，但是不管怎么樣，都繞不開(kāi)幾個(gè)條件，這是推薦的基本條件

根據(jù)和你共同喜好的人來(lái)給你推薦

根據(jù)你喜歡的物品找出和它相似的來(lái)給你推薦

根據(jù)你給出的關(guān)鍵字來(lái)給你推薦，這實(shí)際上就退化成搜索算法了

根據(jù)上面的幾種條件組合起來(lái)給你推薦

實(shí)際上，現(xiàn)有的條件就這些啦，至于怎么發(fā)揮這些條件就是八仙過(guò)海各顯神通了，這么多年沉淀了一些好的算法，今天這篇文章要講的基于用戶的協(xié)同過(guò)濾算法就是其中的一個(gè)，這也是最早出現(xiàn)的推薦算法，并且發(fā)展到今天，基本思想沒(méi)有什么變化，無(wú)非就是在處理速度上，計(jì)算相似度的算法上出現(xiàn)了一些差別而已。

我們先做個(gè)詞法分析基于用戶說(shuō)明這個(gè)算法是以用戶為主體的算法，這種以用戶為主體的算法比較強(qiáng)調(diào)的是社會(huì)性的屬性，也就是說(shuō)這類算法更加強(qiáng)調(diào)把和你有相似愛(ài)好的其他的用戶的物品推薦給你，與之對(duì)應(yīng)的是基于物品的推薦算法，這種更加強(qiáng)調(diào)把和你你喜歡的物品相似的物品推薦給你。

然后就是協(xié)同過(guò)濾了，所謂協(xié)同就是大家一起幫助你啦，然后后面跟個(gè)過(guò)濾，就是大家是商量過(guò)后才把結(jié)果告訴你的，不然信息量太大了。。

所以，綜合起來(lái)說(shuō)就是這么一個(gè)算法，那些和你有相似愛(ài)好的小伙伴們一起來(lái)商量一下，然后告訴你什么東西你會(huì)喜歡。

相似性計(jì)算

我們盡量不使用復(fù)雜的數(shù)學(xué)公式，一是怕大家看不懂，難理解，二是我是用mac寫(xiě)的blog,公式不好畫(huà)，太麻煩了。。

所謂計(jì)算相似度，有兩個(gè)比較經(jīng)典的算法

Jaccard算法，就是交集除以并集，詳細(xì)可以看看我這篇文章。

余弦距離相似性算法，這個(gè)算法應(yīng)用很廣，一般用來(lái)計(jì)算向量間的相似度，具體公式大家google一下吧，或者看看這里

各種其他算法，比如歐氏距離算法等等。

不管使用Jaccard還是用余弦算法，本質(zhì)上需要做的還是求兩個(gè)向量的相似程度，使用哪種算法完全取決于現(xiàn)實(shí)情況。

我們?cè)诒疚闹杏玫氖怯嘞揖嚯x相似性來(lái)計(jì)算兩個(gè)用戶之間的相似度。

與目標(biāo)用戶最相鄰的K個(gè)用戶

我們知道，在找和你興趣愛(ài)好相似的小伙伴的時(shí)候，我們可能可以找到幾百個(gè)，但是有些是好基友，但有些只是普通朋友，那么一般的，我們會(huì)定一個(gè)數(shù)K，和你最相似的K個(gè)小伙伴就是你的好基友了，他們的愛(ài)好可能和你的愛(ài)好相差不大，讓他們來(lái)推薦東西給你（比如肥皂）是最好不過(guò)了。

何為和你相似呢？簡(jiǎn)單的說(shuō)就是，比如你喜歡macbook,iphone,ipad，A小伙伴喜歡macbook,iphone,note2,小米盒子,肥皂，蠟燭,B小伙伴喜歡macbook,iphone,ipad,肥皂,潤(rùn)膚霜,C女神喜歡雅詩(shī)蘭黛,SK2,香奈兒，D屌絲喜歡ipad,諾基亞8250,小霸王學(xué)習(xí)機(jī)那么很明顯，B小伙伴和你更加相似，而C女神完全和你不在一個(gè)檔次上，那我們推薦的時(shí)候會(huì)把肥皂推薦給你，因?yàn)槲覀冇X(jué)得肥皂可能最適合你。

那么，如何找出這K個(gè)基友呢？最直接的辦法就是把目標(biāo)用戶和數(shù)據(jù)庫(kù)中的所有用戶進(jìn)行比較，找出和目標(biāo)用戶最相似的K個(gè)用戶，這就是好基友了。

這么做理論上是沒(méi)什么問(wèn)題的，但是當(dāng)數(shù)據(jù)量巨大的時(shí)候，計(jì)算K個(gè)基友的時(shí)間將會(huì)非常長(zhǎng)，而且你想想就知道，數(shù)據(jù)庫(kù)中的大部分用戶其實(shí)和你是沒(méi)有什么交集的，所沒(méi)必要計(jì)算所有用戶了，只需要計(jì)算和你有交集的用戶就行了。

要計(jì)算和你有交集的用戶，就要用到物品到用戶的反查表，什么是反查表呢？很簡(jiǎn)單，還是是上面那個(gè)AB小伙伴和C女神的例子，反查表就是喜歡macbook的有你，A，B，喜歡iphone的有你，B。。。就是喜歡某些物品的用戶，有了這個(gè)表，我們就可以看出來(lái)，和你有關(guān)系的用戶就只有A和B，D了，而C女神和你沒(méi)有任何交集，所以不用去想C了。

這樣，我們有了A和B,D，然后就分別計(jì)算A和B,D與你的相似度，不管用哪個(gè)相似性公式，我們算出來(lái)都是B和你更相似(在這個(gè)例子中，一般會(huì)用Jaccard來(lái)計(jì)算，因?yàn)檫@些向量不是特別好余弦化)，但如果此時(shí)我們的K設(shè)定為2，那么我們就得出了與你最相鄰的基友是B和A。

這就是與目標(biāo)用戶最相鄰的K個(gè)用戶的計(jì)算。

通過(guò)這K個(gè)用戶來(lái)推薦商品了

好了，你的好基友我們也算出來(lái)了，接下來(lái)要向你推薦商品了。但是我們可推薦的商品有小米盒子，note2，蠟燭，潤(rùn)膚霜，肥皂這么四種，到底哪種才是你需要的呢？這里的算法就比較廣泛了，我們可以不排序，都一股腦推薦給你，但這明顯可能有些你不怎么感興趣，我們也可以做一些處理，假如我們算出來(lái)A和你的相似度是25%，B和你的相似度是80%，那么對(duì)于上面這些產(chǎn)品，我們的推薦度可以這么來(lái)算

小米盒子: 1*0.25 = 0.25

note2: 1*0.25 = 0.25

蠟燭: 1*0.25 = 0.25

潤(rùn)膚霜: 1*0.8 = 0.8

肥皂: 10.8+10.25=1.05

這樣就一目了然了，很明顯，我們會(huì)首先把肥皂推薦給你，這個(gè)可能是你最需要的，其次是潤(rùn)膚霜，然后才是蠟燭，小米盒子和note2。

當(dāng)然，你可以把上述結(jié)果歸一化或者用其他你覺(jué)得合適的方式來(lái)計(jì)算推薦度，不管怎么算，推薦度還是得和基友與你相似度有關(guān)系，就是那個(gè)0.8和0.25一定要用上，不然前面白算了。

算法總結(jié)

好了，通過(guò)這個(gè)例子，你大概知道了為什么會(huì)推薦肥皂給你了吧，這就是基于用戶的協(xié)同推薦算法的描述，總結(jié)起來(lái)就是這么幾步

計(jì)算其他用戶和你的相似度，可以使用反差表忽略一部分用戶

根據(jù)相似度的高低找出K個(gè)與你最相似的鄰居

在這些鄰居喜歡的物品中，根據(jù)鄰居與你的遠(yuǎn)近程度算出每一件物品的推薦度

根據(jù)每一件物品的推薦度高低給你推薦物品。

比如上面那個(gè)例子，首先，我們通過(guò)反查表忽略掉了C女神，然后計(jì)算出A和B,D與你的相似度，然后根據(jù)K=2找出最相似的鄰居A和B，接著根據(jù)A,B與你相似度計(jì)算出每件物品的推薦度并排序，最后根據(jù)排好序的推薦度給你推薦商品。

怎么樣，是不是很簡(jiǎn)單啊。

這個(gè)算法實(shí)現(xiàn)起來(lái)也比較簡(jiǎn)單，但是在實(shí)際應(yīng)用中有時(shí)候也會(huì)有問(wèn)題的。

比如一些非常流行的商品可能很多人都喜歡，這種商品推薦給你就沒(méi)什么意義了，所以計(jì)算的時(shí)候需要對(duì)這種商品加一個(gè)權(quán)重或者把這種商品完全去掉也行。

再有，對(duì)于一些通用的東西，比如買書(shū)的時(shí)候的工具書(shū)，如現(xiàn)代漢語(yǔ)詞典，新華字典神馬的，通用性太強(qiáng)了，推薦也沒(méi)什么必要了。

這些都是推薦系統(tǒng)的臟數(shù)據(jù)，如何去掉臟數(shù)據(jù)，這是數(shù)據(jù)預(yù)處理的時(shí)候事情了，這里就不多說(shuō)了。

說(shuō)了這么多，肥皂也推薦了，那么我們來(lái)點(diǎn)實(shí)際的，我這里下載了movieLens的數(shù)據(jù)集，至于這個(gè)集合是什么大家google一下，反正很多地方用來(lái)做測(cè)試算法的數(shù)據(jù)，這個(gè)數(shù)據(jù)集里面有很多用戶對(duì)于電影的打分，我們的需求是隨便輸入一個(gè)用戶，然后根據(jù)協(xié)同算法，給他推薦一些個(gè)電影。

由于用戶給電影打分有好有壞[1到5分]，而我們上面的例子中都是說(shuō)的喜歡某件物品而沒(méi)有說(shuō)不喜歡的情況，所以首先，我們要把數(shù)據(jù)處理一下，簡(jiǎn)單的來(lái)做，我們可以認(rèn)為3分以上的話代表這個(gè)用戶喜歡這個(gè)電影，否則就是不喜歡，這樣顯得有點(diǎn)太死板了，我們也可以這么來(lái)定義，比如用戶A對(duì)30部電影打分了，首先求出他打分的平均值，然后高于這個(gè)平均值的我們覺(jué)得用戶喜歡這個(gè)電影，否則認(rèn)為他不喜歡。

好了，用戶的喜歡與不喜歡的問(wèn)題解決了。下面就可以開(kāi)始算法了，代碼不全貼出來(lái)了，貼個(gè)流程吧，具體代碼可以去看我的github

#讀取文件數(shù)據(jù)
test_contents=readFile(file_name)
#文件數(shù)據(jù)格式化成二維數(shù)組 List[[用戶id,電影id,電影評(píng)分]...] 
test_rates=getRatingInformation(test_contents)  
#格式化成字典數(shù)據(jù) 
#    1.用戶字典：dic[用戶id]=[(電影id,電影評(píng)分)...]
#    2.電影用戶反查表：dic[電影id]=[用戶id1,用戶id2...]
test_dic,test_item_to_user=createUserRankDic(test_rates)
#尋找鄰居   
neighbors=calcNearestNeighbor(userid,test_dic,test_item_to_user)[:k]
#計(jì)算推薦列表 
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)

對(duì)于隨便輸入一個(gè)用戶，我們得到以下這個(gè)推薦結(jié)果

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                

多輸入幾個(gè)用戶你就會(huì)發(fā)現(xiàn)，像Titanic，Star Wars這種超級(jí)熱門的電影，只要你選的這個(gè)用戶沒(méi)看過(guò)，推薦系統(tǒng)就一定會(huì)推薦給你，這就是我們前面說(shuō)的臟數(shù)據(jù)，實(shí)際系統(tǒng)中這種數(shù)據(jù)是需要處理掉得。我們這篇文章只做算法講解，就不去管這些東西了。

最后，歡迎關(guān)注我的公眾號(hào)，很多東西會(huì)在那里發(fā)出來(lái)，13年就申請(qǐng)了，一直太忙沒(méi)時(shí)間更新運(yùn)營(yíng)過(guò)，現(xiàn)在又激活了。