《推薦系統》基于用戶和Item的協同過濾算法的分析與實現（Python）

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

目錄：

1：協同過濾算法簡介

2：協同過濾算法的核心

3：協同過濾算法的應用方式

4：基于用戶的協同過濾算法實現

5：基于物品的協同過濾算法實現

一：協同過濾算法簡介

    關于協同過濾的一個最經典的例子就是看電影，有時候不知道哪一部電影是我們喜歡的或者評分比較高的，那么通常的做法就是問問周圍的朋友，看看最近有什么好的電影推薦。在問的時候，都習慣于問跟自己口味差不 多的朋友，這就是協同過濾的核心思想。

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

   （1）如何確定一個用戶是否與你有相似的品味？

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

   協同過濾算法的出現標志著推薦系統的產生，協同過濾算法包括基于用戶和基于物品的協同過濾算法。

二：協同過濾算法的核心

      要實現協同過濾，需要進行如下幾個步驟 

      1）收集用戶偏好

      2）找到相似的用戶或者物品

      3）計算并推薦

三：協同過濾算法的應用方式

1：基于用戶的協同過濾算法   

基于用戶的協同過濾通過不同用戶對物品的評分來評測用戶之間的相似性，基于用戶的相似性做推薦，簡單的講：給用戶推薦和他興趣相投的其他用戶喜歡的物品

算法實現流程分析：

(1)：計算用戶的相似度

計算用戶相似度的方法請參考這篇博客：點擊閱讀  這里我采用的是余弦相似度

下面我拿這個圖舉例

計算用戶的相似度，例如A,B為

同理

         但是這樣計算的效率是低的，因為我們需要計算每一對用戶之間的相似度，事實上，很多用戶相互之間并沒有對同樣的物品產生過行為，所以很多時候當分子為0的時候沒有必要再去計算分母，所以這里可以優化：即首先計算出|N(u) 并 N(v)| != 0 的用戶對(u,v)，然后對這種情況計算分母以得到兩個用戶的相似度。

針對此優化，需要2步：

     （1）建立物品到用戶的倒查表T，表示該物品被哪些用戶產生過行為；

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

得到用戶的相似度后，便可以進行下一步了

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

公式如下：

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

根據UserCF算法，可以算出，用戶A對物品c、e的興趣是：

2：基于物品的協同過濾算法

基于item的協同過濾通過不同用戶對不同item的評分來評測item之間的相似性，基于item的相似性做推薦，簡單的講：給用戶推薦和他之前喜歡物品相似的物品

算法流程分析：

同樣拿上邊的圖舉例，在這里默認用戶對物品的打分均為1

(1)：構建物品的同現矩陣

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

按照標準定義

、

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

進行處理后的結果為：

當然為了出現推薦熱門的商品，對上述公式的優化為：

這個公式懲罰了物品j的權重，因此減輕了熱門物品會和很多物品相似的可能性（此種情況下感興趣的自己推導）。

(2)：建立用戶對物品的評分矩陣（以A舉例，沒有評分的物品為0）

(3)：矩陣計算推薦結果

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

推薦結果=同現矩陣 * 評分矩陣

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

3：混合推薦

所謂的混合算法，主體思路還是基于用戶的協同過濾，只是在計算兩個用戶的相似度時又嵌套了item-based CF思想。

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

1.用戶i參與評分的項目集合為IiIi，用戶j參與評分的項目集合為IjIj，找到它們的并集Uij=Ii∪IjUij=Ii∪Ij

2.在集合UijUij中用戶i未評分的項目是Ni=Uij?IiNi=Uij?Ii，采用item-based CF方法重新估計用戶i對NiNi中每個項目的評分。

3.這樣用戶i和j對UijUij的評分就都是非0值了，在此情況下計算他們的相似度。

四：基于用戶的協同過濾算法實現

[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：數據集，這里指users  
26.     #k：表示得出最相近的k的近鄰  
27.     #metric：表示使用計算相似度的方法  
28.     #n：表示推薦book的個數  
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.     #定義的計算相似度的公式，用的是皮爾遜相關系數計算方法  
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.         #皮爾遜相關系數計算公式   
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.     #推薦算法的主體函數  
89.     def recommend(self, user):  
90.         #定義一個字典，用來存儲推薦的書單和分數  
91.         recommendations = {}  
92.         #計算出user與所有其他用戶的相似度，返回一個list  
93.         nearest = self.computeNearestNeighbor(user)  
94.         # print nearest  
95.           
96.         userRatings = self.data[user]  
97. #         print userRatings  
98.         totalDistance = 0.0  
99.         #得住最近的k個近鄰的總距離  
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個人中user沒有看過的書推薦給user，并且這里又做了一個分數的計算排名  
106.         for i in range(self.k):  
107.               
108.             #第i個人的與user的相似度，轉換到[0,1]之間  
109.             weight = nearest[i][1] / totalDistance  
110.               
111.             #第i個人的name  
112.             name = nearest[i][0]  
113.   
114.             #第i個用戶看過的書和相應的打分  
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.         #做了一個排序  
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推薦書籍的id，nearuser[:15]最近鄰的15個用戶  

程序調用：

[python] view plain copy

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

五：基于物品的協同過濾算法的實現

參考項亮的《推薦系統實戰》結合上例中的數據進行算法實現

[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.         #讀取文件，并生成用戶-物品的評分表和測試集  
16.         self.train = dict()     #用戶-物品的評分表  
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.         #建立物品-物品的共現矩陣  
25.         C = dict()  #物品-物品的共現矩陣  
26.         N = dict()  #物品被多少個不同用戶購買  
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.         #計算相似度矩陣  
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.     #給用戶user推薦，前K個相關用戶  
45.     def Recommend(self,user,K=3,N=10):  
46.         rank = dict()  
47.         action_item = self.train[user]     #用戶user產生過行為的item和評分  
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. #聲明一個ItemBased推薦的對象      
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  

運行結果：

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