基于使用者的協同過濾算法
一、基本思路
在一個推薦場景，你需要給使用者推薦一些商品，基本思路是：
（1）找到和目标使用者興趣相似的使用者集合。
（2）找到這個集合中的使用者喜歡的，且目标使用者沒有聽說過的物品推薦給目标使用者。
二、相似度度量
可以有許多不同的方式用于度量，常見的有Jaccard公式，餘弦相似度等等。
餘弦相似度公式如下：
duv=|N(u)∩N(v)||N(u)||N(v)|−−−−−−−−−−√ d u v = | N ( u ) ∩ N ( v ) | | N ( u ) | | N ( v ) |
N(u) 表示使用者u給過正回報的商品集合，所謂正回報就是使用者傾向于喜歡該物品。N(v)表示使用者v給過正回報的商品集合。分子表示使用者u和使用者v都喜歡的物品集合。
三、實驗設計
資料集：GroupLens提供的MovieLens資料集（http://www.grouplens.org/node/73)
本次實驗采用1m資料集，該資料集包含了6000多使用者對4000多部電影的100多萬個評分。本實驗讨論的是TopN問題，是以對于評分不予讨論。
3.1 評測名額
将資料集劃分成訓練集和測試集，對于訓練集的每一個使用者，利用協同過濾算法向其推薦商品，若推薦結果中的某個商品在測試集中的該使用者的記錄中出現了，則代表該結果是真正例。下面公式的R(u)表示對使用者u推薦的商品集合，T(u)表示使用者u在測試集上喜歡的物品集合。
3.1.1 召回率
Recall=∑u|R(u)∩T(u)|∑u|T(u)| R e c a l l = ∑ u | R ( u ) ∩ T ( u ) | ∑ u | T ( u ) |
3.1.2 準确率
Precision=∑u|R(u)∩T(u)|∑u|R(u)| P r e c i s i o n = ∑ u | R ( u ) ∩ T ( u ) | ∑ u | R ( u ) |
3.1.3 覆寫率
覆寫率反映了推薦算法發掘長尾的能力，說明推薦算法越能将長尾中的物品推薦給使用者。下面的公式表示的就是最終的推薦清單中包含多大比例的商品。I表示所有商品的集合。
Coverage=⋃u∈UR(u)|I| C o v e r a g e = ⋃ u ∈ U R ( u ) | I |
3.1.4 新穎性
新穎的推薦是指給使用者推薦那些他們以前沒有聽說過的物品，最簡單的評測方法就是利用推薦結果的平均流行度。
3.1.5測評名額的代碼實作
# 名 稱: evaluate
# 功 能: 計算評測名額
# 參 數: trainset, 訓練集
# testset, 測試集
# moviepopularity, 商品的流行度
# numofmovies, 所有電影的數量
# usersim, 相似使用者matrix
# K, 算法選擇K個相似使用者
# N, 算法最終選擇N個商品
# 返 回 值: precision, 準确率 recall, 召回率,coverage,覆寫率 popularity, 新穎度
# 修 改: 2018/5/29
def evaluate(trainset,testset,moviepopularity,numofmovies,usersim,K,N):
print('Evaluation start...')
hit =
TPFN =
TPFP =
allrecmovies = set()
popular_sum =
index=
print("starting evaluate...")
print("total number of users is: " + str(len(trainset)))
for user in trainset.keys():
index +=
if index % ==:
print("evaluate..." + str(index) + str(len(trainset)))
# 協同過濾算法對使用者user的推薦結果
rec_movies = recommend(usersim,trainset,user,K,N)
if user not in testset.keys():
continue
testmovies = testset[user]
for rec_movie,_ in rec_movies:
# R(u)∩T(U)的情況
if rec_movie in testmovies:
# 真正例
hit+=
allrecmovies.add(rec_movie)
# 計算平均流行度，使用log是為了使均值比較穩定，moviepopularity裡面存儲的是每個電影被正回報操作的次數。
popular_sum += math.log( + moviepopularity[rec_movie])
# 所有的正例
TPFN += len(testmovies)
# 所有推薦給使用者的商品數量
TPFP += N
# 準确率
precision = hit * / TPFP
# 召回率
recall = hit * /TPFN
# 覆寫率
coverage = len(allrecmovies) / ( * numofmovies)
# 流行度
popularity = popular_sum / ( * TPFP)
print('precision=%.4f\trecall=%.4f\tcoverage=%.4f\tpopularity=%.4f' %
(precision, recall, coverage, popularity))
return precision,recall,coverage,popularity
3.2 具體步驟
3.2.1 獲得訓練集和測試集
# 名 稱: produceData
# 功 能: 獲得訓練集和測試集
# 參 數: filepath, 檔案路徑
# pivot, 随機機率
# 返 回 值: trainset, 訓練集
# testset 測試集
# 修 改:2018/5/29
def produceData(filepath,pivot=):
trainset={}
testset={}
file = open(filepath,'r')
lines = file.readlines()
l = len(lines)
print("Number of data is" + str(l))
for i in range(l):
if i%==:
print("loading data......" + str(i) + '/' + str(l))
user,movie,ranting,_ = lines[i].split('\n')[].split('::')
if random.random() < pivot:
trainset.setdefault(user,{})
trainset[user][movie] = ranting
else:
testset.setdefault(user,{})
testset[user][movie] = ranting
return trainset,testset
3.2.2 獲得movie-user以及moviepopularity
該步是為了擷取以movie為key,user為value的字典，以及每部電影的popularity。
# 名 稱: FindRelativeDict
# 功 能: 獲得相關字典
# 參 數: trainset 訓練集
# 返 回 值: movie2user, {'movie':users}字典
# moviepopularity, {'movie': popularity}字典
# 修 改: 2018/5/29
def FindRelativeDict(trainset):
movie2user = {}
moviepopularity ={}
for user,movies in trainset.items():
for movie in movies:
if movie not in movie2user.keys():
movie2user[movie] = set()
movie2user[movie].add(user)
if movie not in moviepopularity.keys():
moviepopularity[movie] =
# popularity 定義為電影被所有使用者給過正回報的次數
moviepopularity[movie] +=
return movie2user,moviepopularity
3.2.3 計算相似使用者dict
在這裡運用到上面的使用者相似度度量的餘弦相似度公式。
# 名 稱: FindUserSimilarity
# 功 能: 計算使用者相似性字典
# 參 數: trainset 訓練集
# movie2user {'movie':users}字典
# 返 回 值: usersim 相似使用者矩陣 {'user':{'similar_user': 相似程度}}
# 修 改: 2018/5/29
def FindUserSimilarity(trainset,movie2user):
usersim = {}
for movie,users in movie2user.items():
for u in users:
usersim.setdefault(u,defaultdict(int))
for v in users:
if u==v:
continue
else:
usersim[u][v] +=
print( "starting calculate the similarity matrix of users...")
index=
for u,simiusers in usersim.items():
for v,count in simiusers.items():
index+=
if index % == :
print("calculating...." + str(index))
usersim[u][v] = count / math.sqrt(
len(trainset[u]) * len(trainset[v]))
return usersim
3.2.4 對某使用者進行推薦
# 名 稱: recommand
# 功 能: 給某使用者推薦N件商品
# 參 數: usersim 相似使用者字典
# trainset 訓練集
# user 使用者
# K 在推薦時選取K個最接近的相似使用者
# N 最終選取N件商品給使用者
# 返 回 值: recommendres 推薦的商品字典
# 修 改: 2018/5/29
def recommend(usersim,trainset,user,K,N):
userrec = {}
currentmovies = trainset[user]
for similar_user, similarity_factor in sorted(usersim[user].items(),
key=itemgetter(), reverse=True)[:K]:
for movie in trainset[similar_user]:
if movie in currentmovies:
continue
userrec.setdefault(movie,)
userrec[movie] += similarity_factor
recommendres = sorted(userrec.items(), key=itemgetter(), reverse=True)[:N]
return recommendres
實驗結果
可以發現随着K的增加，準确率，召回率，流行度會随之升高，但是覆寫率變差，這是因為随着K的增加，該算法會傾向于推薦熱門的物品，而對長尾物品的推薦越來越少，是以造成了覆寫率的降低。
[1]: https://github.com/Lockvictor/MovieLens-RecSys 協同過濾算法
[2]: 項亮. 推薦系統實踐[M]. 人民郵電出版社, 2012.
![TestLink導出用例轉換工具(XML2Excel)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)