原鏈接：http://blog.csdn.net/gamer_gyt/article/details/51346159

目錄：

1：協(xié)同過(guò)濾算法簡(jiǎn)介

2：協(xié)同過(guò)濾算法的核心

3：協(xié)同過(guò)濾算法的應(yīng)用方式

4：基于用戶(hù)的協(xié)同過(guò)濾算法實(shí)現(xiàn)

5：基于物品的協(xié)同過(guò)濾算法實(shí)現(xiàn)

一：協(xié)同過(guò)濾算法簡(jiǎn)介

    關(guān)于協(xié)同過(guò)濾的一個(gè)最經(jīng)典的例子就是看電影，有時(shí)候不知道哪一部電影是我們喜歡的或者評(píng)分比較高的，那么通常的做法就是問(wèn)問(wèn)周?chē)呐笥?，看看最近有什么好的電影推薦。在問(wèn)的時(shí)候，都習(xí)慣于問(wèn)跟自己口味差不 多的朋友，這就是協(xié)同過(guò)濾的核心思想。

   協(xié)同過(guò)濾是在海量數(shù)據(jù)中挖掘出小部分與你品味類(lèi)似的用戶(hù)，在協(xié)同過(guò)濾中，這些用戶(hù)成為鄰居，然后根據(jù)他們喜歡的東西組織成一個(gè)排序的目錄推薦給你。所以就有如下兩個(gè)核心問(wèn)題

   （1）如何確定一個(gè)用戶(hù)是否與你有相似的品味？

   （2）如何將鄰居們的喜好組織成一個(gè)排序目錄？

   協(xié)同過(guò)濾算法的出現(xiàn)標(biāo)志著推薦系統(tǒng)的產(chǎn)生，協(xié)同過(guò)濾算法包括基于用戶(hù)和基于物品的協(xié)同過(guò)濾算法。

二：協(xié)同過(guò)濾算法的核心

      要實(shí)現(xiàn)協(xié)同過(guò)濾，需要進(jìn)行如下幾個(gè)步驟 

      1）收集用戶(hù)偏好

      2）找到相似的用戶(hù)或者物品

      3）計(jì)算并推薦

三：協(xié)同過(guò)濾算法的應(yīng)用方式

1：基于用戶(hù)的協(xié)同過(guò)濾算法   

基于用戶(hù)的協(xié)同過(guò)濾通過(guò)不同用戶(hù)對(duì)物品的評(píng)分來(lái)評(píng)測(cè)用戶(hù)之間的相似性，基于用戶(hù)的相似性做推薦，簡(jiǎn)單的講：給用戶(hù)推薦和他興趣相投的其他用戶(hù)喜歡的物品

算法實(shí)現(xiàn)流程分析：

(1)：計(jì)算用戶(hù)的相似度

計(jì)算用戶(hù)相似度的方法請(qǐng)參考這篇博客：點(diǎn)擊閱讀  這里我采用的是余弦相似度

下面我拿這個(gè)圖舉例

計(jì)算用戶(hù)的相似度，例如A,B為

同理

         但是這樣計(jì)算的效率是低的，因?yàn)槲覀冃枰?jì)算每一對(duì)用戶(hù)之間的相似度，事實(shí)上，很多用戶(hù)相互之間并沒(méi)有對(duì)同樣的物品產(chǎn)生過(guò)行為，所以很多時(shí)候當(dāng)分子為0的時(shí)候沒(méi)有必要再去計(jì)算分母，所以這里可以?xún)?yōu)化：即首先計(jì)算出|N(u) 并 N(v)| != 0 的用戶(hù)對(duì)(u,v)，然后對(duì)這種情況計(jì)算分母以得到兩個(gè)用戶(hù)的相似度。

針對(duì)此優(yōu)化，需要2步：

     （1）建立物品到用戶(hù)的倒查表T，表示該物品被哪些用戶(hù)產(chǎn)生過(guò)行為；

     （2）根據(jù)倒查表T，建立用戶(hù)相似度矩陣W：在T中，對(duì)于每一個(gè)物品i，設(shè)其對(duì)應(yīng)的用戶(hù)為j,k，在W中，更新相應(yīng)的元素值，w[j][k]=w[j][k]+1，w[k][j]=w[k][j]+1，以此類(lèi)推，掃描完倒查表T中的所有物品后，就可以得到最終的用戶(hù)相似度矩陣W，這里的W是余弦相似度中的分子部分，然后將W除以分母可以得到最終的用戶(hù)興趣相似度。

得到用戶(hù)的相似度后，便可以進(jìn)行下一步了

(2)：給用戶(hù)推薦興趣最相近的k個(gè)用戶(hù)所喜歡的物品

公式如下：

其中，p(u,i)表示用戶(hù)u對(duì)物品i的感興趣程度，S(u,k)表示和用戶(hù)u興趣最接近的K個(gè)用戶(hù)，N(i)表示對(duì)物品i有過(guò)行為的用戶(hù)集合，Wuv表示用戶(hù)u和用戶(hù)v的興趣相似度，Rvi表示用戶(hù)v對(duì)物品i的興趣（這里簡(jiǎn)化，所有的Rvi都等于1）。

根據(jù)UserCF算法，可以算出，用戶(hù)A對(duì)物品c、e的興趣是：

2：基于物品的協(xié)同過(guò)濾算法

基于item的協(xié)同過(guò)濾通過(guò)不同用戶(hù)對(duì)不同item的評(píng)分來(lái)評(píng)測(cè)item之間的相似性，基于item的相似性做推薦，簡(jiǎn)單的講：給用戶(hù)推薦和他之前喜歡物品相似的物品

算法流程分析：

同樣拿上邊的圖舉例，在這里默認(rèn)用戶(hù)對(duì)物品的打分均為1

(1)：構(gòu)建物品的同現(xiàn)矩陣

在這里對(duì)矩陣做歸一化處理就可以得到物品之間的余弦相似度矩陣了其中歸一化處理

按照標(biāo)準(zhǔn)定義

、

這里，分母|N(i)|是喜歡物品i的用戶(hù)數(shù)，而分子 N(i)? N( j) 是同時(shí)喜歡物品i和物品j的用戶(hù)數(shù)。因此，上述公式可以理解為喜歡物品i的用戶(hù)中有多少比例的用戶(hù)也喜歡物品j。

進(jìn)行處理后的結(jié)果為：

當(dāng)然為了出現(xiàn)推薦熱門(mén)的商品，對(duì)上述公式的優(yōu)化為：

這個(gè)公式懲罰了物品j的權(quán)重，因此減輕了熱門(mén)物品會(huì)和很多物品相似的可能性（此種情況下感興趣的自己推導(dǎo)）。

(2)：建立用戶(hù)對(duì)物品的評(píng)分矩陣（以A舉例，沒(méi)有評(píng)分的物品為0）

(3)：矩陣計(jì)算推薦結(jié)果

這里N(u)是用戶(hù)喜歡的物品的集合，S(j,K)是和物品j最相似的K個(gè)物品的集合，wji是物品j和i的相似度，rui是用戶(hù)u對(duì)物品i的興趣。（對(duì)于隱反饋數(shù)據(jù)集，如果用戶(hù)u對(duì)物品i有過(guò)行為，即可令rui=1。）該公式的含義是，和用戶(hù)歷史上感興趣的物品越相似的物品，越有可能在用戶(hù)的推薦列表中獲得比較高的排名。

推薦結(jié)果=同現(xiàn)矩陣 * 評(píng)分矩陣

從中去掉A已經(jīng)打過(guò)分的物品，a，b，d，則可以看出，A對(duì)e的喜歡程度和c一樣，和上邊計(jì)算結(jié)果一致，所以就會(huì)將兩者推薦給A

3：混合推薦

所謂的混合算法，主體思路還是基于用戶(hù)的協(xié)同過(guò)濾，只是在計(jì)算兩個(gè)用戶(hù)的相似度時(shí)又嵌套了item-based CF思想。

度量用戶(hù)i和用戶(hù)j相似度更好的方法是：

1.用戶(hù)i參與評(píng)分的項(xiàng)目集合為IiIi，用戶(hù)j參與評(píng)分的項(xiàng)目集合為IjIj，找到它們的并集Uij=Ii∪IjUij=Ii∪Ij

2.在集合UijUij中用戶(hù)i未評(píng)分的項(xiàng)目是Ni=Uij?IiNi=Uij?Ii，采用item-based CF方法重新估計(jì)用戶(hù)i對(duì)NiNi中每個(gè)項(xiàng)目的評(píng)分。

3.這樣用戶(hù)i和j對(duì)UijUij的評(píng)分就都是非0值了，在此情況下計(jì)算他們的相似度。

四：基于用戶(hù)的協(xié)同過(guò)濾算法實(shí)現(xiàn)

[python] view plain copy

1. #-*-coding:utf-8-*-  
2. ''''' 
3. Created on 2016年5月2日 
4.  
5. @author: Gamer Think 
6. '''  
7. from math import sqrt  
8.   
9. fp = open("uid_score_bid","r")  
10.   
11. users = {}  
12.   
13. for line in open("uid_score_bid"):  
14.     lines = line.strip().split(",")  
15.     if lines[0] not in users:  
16.         users[lines[0]] = {}  
17.     users[lines[0]][lines[2]]=float(lines[1])  
18.   
19.   
20. #----------------新增代碼段END----------------------  
21.   
22.   
23.   
24. class recommender:  
25.     #data：數(shù)據(jù)集，這里指users  
26.     #k：表示得出最相近的k的近鄰  
27.     #metric：表示使用計(jì)算相似度的方法  
28.     #n：表示推薦book的個(gè)數(shù)  
29.     def __init__(self, data, k=3, metric='pearson', n=12):  
30.   
31.         self.k = k  
32.         self.n = n  
33.         self.username2id = {}  
34.         self.userid2name = {}  
35.         self.productid2name = {}  
36.   
37.         self.metric = metric  
38.         if self.metric == 'pearson':  
39.             self.fn = self.pearson  
40.         if type(data).__name__ == 'dict':  
41.             self.data = data  
42.         
43.     def convertProductID2name(self, id):  
44.   
45.         if id in self.productid2name:  
46.             return self.productid2name[id]  
47.         else:  
48.             return id  
49.   
50.     #定義的計(jì)算相似度的公式，用的是皮爾遜相關(guān)系數(shù)計(jì)算方法  
51.     def pearson(self, rating1, rating2):  
52.         sum_xy = 0  
53.         sum_x = 0  
54.         sum_y = 0  
55.         sum_x2 = 0  
56.         sum_y2 = 0  
57.         n = 0  
58.         for key in rating1:  
59.             if key in rating2:  
60.                 n += 1  
61.                 x = rating1[key]  
62.                 y = rating2[key]  
63.                 sum_xy += x * y  
64.                 sum_x += x  
65.                 sum_y += y  
66.                 sum_x2 += pow(x, 2)  
67.                 sum_y2 += pow(y, 2)  
68.         if n == 0:  
69.             return 0  
70.           
71.         #皮爾遜相關(guān)系數(shù)計(jì)算公式   
72.         denominator = sqrt(sum_x2 - pow(sum_x, 2) / n)  * sqrt(sum_y2 - pow(sum_y, 2) / n)  
73.         if denominator == 0:  
74.             return 0  
75.         else:  
76.             return (sum_xy - (sum_x * sum_y) / n) / denominator  
77.       
78.     def computeNearestNeighbor(self, username):  
79.         distances = []  
80.         for instance in self.data:  
81.             if instance != username:  
82.                 distance = self.fn(self.data[username],self.data[instance])  
83.                 distances.append((instance, distance))  
84.   
85.         distances.sort(key=lambda artistTuple: artistTuple[1],reverse=True)  
86.         return distances  
87.       
88.     #推薦算法的主體函數(shù)  
89.     def recommend(self, user):  
90.         #定義一個(gè)字典，用來(lái)存儲(chǔ)推薦的書(shū)單和分?jǐn)?shù)  
91.         recommendations = {}  
92.         #計(jì)算出user與所有其他用戶(hù)的相似度，返回一個(gè)list  
93.         nearest = self.computeNearestNeighbor(user)  
94.         # print nearest  
95.           
96.         userRatings = self.data[user]  
97. #         print userRatings  
98.         totalDistance = 0.0  
99.         #得住最近的k個(gè)近鄰的總距離  
100.         for i in range(self.k):  
101.             totalDistance += nearest[i][1]  
102.         if totalDistance==0.0:  
103.             totalDistance=1.0  
104.               
105.         #將與user最相近的k個(gè)人中user沒(méi)有看過(guò)的書(shū)推薦給user，并且這里又做了一個(gè)分?jǐn)?shù)的計(jì)算排名  
106.         for i in range(self.k):  
107.               
108.             #第i個(gè)人的與user的相似度，轉(zhuǎn)換到[0,1]之間  
109.             weight = nearest[i][1] / totalDistance  
110.               
111.             #第i個(gè)人的name  
112.             name = nearest[i][0]  
113.   
114.             #第i個(gè)用戶(hù)看過(guò)的書(shū)和相應(yīng)的打分  
115.             neighborRatings = self.data[name]  
116.   
117.             for artist in neighborRatings:  
118.                 if not artist in userRatings:  
119.                     if artist not in recommendations:  
120.                         recommendations[artist] = (neighborRatings[artist] * weight)  
121.                     else:  
122.                         recommendations[artist] = (recommendations[artist]+ neighborRatings[artist] * weight)  
123.   
124.         recommendations = list(recommendations.items())  
125.         recommendations = [(self.convertProductID2name(k), v)for (k, v) in recommendations]  
126.           
127.         #做了一個(gè)排序  
128.         recommendations.sort(key=lambda artistTuple: artistTuple[1], reverse = True)  
129.   
130.         return recommendations[:self.n],nearest  
131.    
132. def adjustrecommend(id):  
133.     bookid_list = []  
134.     r = recommender(users)  
135.     k,nearuser = r.recommend("%s" % id)  
136.     for i in range(len(k)):  
137.         bookid_list.append(k[i][0])  
138.     return bookid_list,nearuser[:15]        #bookid_list推薦書(shū)籍的id，nearuser[:15]最近鄰的15個(gè)用戶(hù)  

程序調(diào)用：

[python] view plain copy

1. bookid_list,near_list = adjustrecommend("changanamei")  
2. print ("bookid_list:",bookid_list)  
3. print ("near_list:",near_list)  

五：基于物品的協(xié)同過(guò)濾算法的實(shí)現(xiàn)

參考項(xiàng)亮的《推薦系統(tǒng)實(shí)戰(zhàn)》結(jié)合上例中的數(shù)據(jù)進(jìn)行算法實(shí)現(xiàn)

[python] view plain copy

1. #-*-coding:utf-8-*-  
2.   
3. ''''' 
4. Created on 2016-5-30 
5.  
6. @author: thinkgamer 
7. '''  
8. import math  
9.   
10. class ItemBasedCF:  
11.     def __init__(self,train_file):  
12.         self.train_file = train_file  
13.         self.readData()  
14.     def readData(self):  
15.         #讀取文件，并生成用戶(hù)-物品的評(píng)分表和測(cè)試集  
16.         self.train = dict()     #用戶(hù)-物品的評(píng)分表  
17.         for line in open(self.train_file):  
18.             # user,item,score = line.strip().split(",")  
19.             user,score,item = line.strip().split(",")  
20.             self.train.setdefault(user,{})  
21.             self.train[user][item] = int(float(score))  
22.   
23.     def ItemSimilarity(self):  
24.         #建立物品-物品的共現(xiàn)矩陣  
25.         C = dict()  #物品-物品的共現(xiàn)矩陣  
26.         N = dict()  #物品被多少個(gè)不同用戶(hù)購(gòu)買(mǎi)  
27.         for user,items in self.train.items():  
28.             for i in items.keys():  
29.                 N.setdefault(i,0)  
30.                 N[i] += 1  
31.                 C.setdefault(i,{})  
32.                 for j in items.keys():  
33.                     if i == j : continue  
34.                     C[i].setdefault(j,0)  
35.                     C[i][j] += 1  
36.         #計(jì)算相似度矩陣  
37.         self.W = dict()  
38.         for i,related_items in C.items():  
39.             self.W.setdefault(i,{})  
40.             for j,cij in related_items.items():  
41.                 self.W[i][j] = cij / (math.sqrt(N[i] * N[j]))  
42.         return self.W  
43.   
44.     #給用戶(hù)user推薦，前K個(gè)相關(guān)用戶(hù)  
45.     def Recommend(self,user,K=3,N=10):  
46.         rank = dict()  
47.         action_item = self.train[user]     #用戶(hù)user產(chǎn)生過(guò)行為的item和評(píng)分  
48.         for item,score in action_item.items():  
49.             for j,wj in sorted(self.W[item].items(),key=lambda x:x[1],reverse=True)[0:K]:  
50.                 if j in action_item.keys():  
51.                     continue  
52.                 rank.setdefault(j,0)  
53.                 rank[j] += score * wj  
54.         return dict(sorted(rank.items(),key=lambda x:x[1],reverse=True)[0:N])  
55.       
56. #聲明一個(gè)ItemBased推薦的對(duì)象      
57. Item = ItemBasedCF("uid_score_bid")  
58. Item.ItemSimilarity()  
59. recommedDic = Item.Recommend("xiyuweilan")  
60. for k,v in recommedDic.iteritems():  
61.     print k,"\t",v  

運(yùn)行結(jié)果：

1080309     8.18161438413
1119522     11.8165100292
1040104     7.92927319995
1254588     12.8331124639
1082138     7.72409411532
3131626     11.3426906217
26669243     6.96972128519
26305561     6.24816554216
26384985     6.36064881658
1085799     8.20314297616