UserCF
?本系列文章主要介紹推薦系統(tǒng)領(lǐng)域相關(guān)算法原理及其實(shí)現(xiàn)。本文以項(xiàng)亮大神的《推薦系統(tǒng)實(shí)踐》作為切入點(diǎn)，介紹推薦系統(tǒng)最基礎(chǔ)的算法（可能也是最好用的）--基于用戶的協(xié)同過濾算法(UserCF)。參考書中P44-50。
1.簡(jiǎn)述
假設(shè)在一個(gè)個(gè)性化的推薦系統(tǒng)中，用戶A需要推薦，那么可以先找到與A有相似興趣的用戶，例如B、C、D把他們喜歡的，用戶A沒有聽說過的物品推薦給A。這種方法被稱為基于用戶的協(xié)同過濾。
2.計(jì)算用戶相似度
從算法原理中我們可以得到UserCF主要包括兩個(gè)步驟：
1.找到和A用戶興趣相似的用戶集合（B、C、D）。
2.找到這個(gè)集合中的用戶喜歡，且目標(biāo)用戶A還未聽說或購(gòu)買過的物品推薦給目標(biāo)用戶。
步驟1.的關(guān)鍵其實(shí)就是計(jì)算用戶興趣的相似度。這里主要是利用用戶行為來計(jì)算用戶相似度。給定用戶U和用戶V，令N(u)，N(v)分別表示用戶u，v曾經(jīng)有正反饋的用戶集合。用Jaccard公式計(jì)算：
W_{uv} = \frac{|N(u)\bigcap N(v)|}{|N(u)\bigcup N(v)|}
<img src="https://latex.codecogs.com/gif.latex?W_{uv}&space;=&space;\frac{|N(u)\bigcap&space;N(v)|}{|N(u)\bigcup&space;N(v)|}" title="W_{uv} = \frac{|N(u)\bigcap N(v)|}{|N(u)\bigcup N(v)|}" />
或者通過余弦相似度計(jì)算：
W_{uv} = \frac{|N(u)\bigcap N(v)|}{\sqrt{|N(u)||N(v)|}}
以書中數(shù)據(jù)為例：
train = {'A':('a','b','d'),'B':('a','c'),'C':('b','e'),'D':('c','d','e')}
W_{AB} = \frac{|\{a,b,d\} \bigcap \{a,c\}|}{\sqrt{|\{a,b,d\}||\{a,c\}|}} = \frac{1}{\sqrt{6}}
同理可計(jì)算Wac和Wad。
按書中對(duì)所有用戶兩兩計(jì)算余弦相似度，時(shí)間復(fù)雜度是O(U*U)，在用戶量很大時(shí)非常耗時(shí)，事實(shí)上，很多用戶之間并沒有對(duì)同樣的物品產(chǎn)生過行為，因此可以先過濾出N(u)交N(v)不等于0的用戶對(duì)(u,v)，然后再對(duì)其除以分母。
這里用item-user倒排表的方式，建立一個(gè)4*4的用戶相似度矩陣C，最終得到的W[u][v]就是(u,v)對(duì)相似度的分子部分，再除以分母即可得到最終的用戶相似度。如書中圖2-7：
def UserSimilarity(train , IIF = False):
# IIF 是否對(duì) 過于熱門即 購(gòu)買人數(shù)過于多的物品 在計(jì)算用戶相似度的時(shí)候進(jìn)行懲罰
# 因?yàn)楹芏嘤脩魧?duì)之間并沒有對(duì)相同的物品產(chǎn)生過行為，只計(jì)算對(duì)相同物品產(chǎn)生過行為的用戶之間的相似度。
# 采用余弦相似度
# 建立倒排表，對(duì)每個(gè)物品保存只對(duì)其產(chǎn)生過行為的用戶列表。
item_users = dict() # 物品-用戶 倒排表
for u, items in train.items():
for i in items:
# 這里將 item_users.keys() 改為 item_users , 文中例子 應(yīng)該用set 或 list存，而不是dict:
if i not in item_users:
item_users[i] = set()
item_users[i].add(u)
# 建立如圖2-7所示的倒排矩陣
C = dict() # key 用戶對(duì) value 購(gòu)買同一物品的次數(shù)
N = dict() # N(u) 表示用戶購(gòu)買的 商品數(shù) {'A': 3, 'B': 2, 'C': 2, 'D': 3}
for i,users in item_users.items():
for u in users:
if u not in N.keys():
N[u] = 0
N[u] += 1
for v in users:
if u == v:
continue
if (u,v) not in C.keys():
C[u,v] = 0
if IIF:
# len(users) 表示購(gòu)買此物品的用戶數(shù)，越熱門，購(gòu)買用戶越多,C[u,v] 就越小
# 相當(dāng)于之前的分子是相交個(gè)數(shù)，現(xiàn)在是
C[u,v] += 1 / math.log(1 + len(users))
else:
C[u,v] += 1
W = dict()
for co_user, cuv in C.items():
W[co_user] = cuv / math.sqrt(N[co_user[0]]*N[co_user[1]])
return W
這里可以看下return的 W：
3.計(jì)算推薦結(jié)果
這里直接用書中P47的解釋了，Wuv已經(jīng)有了，其實(shí)就是根據(jù)W再乘一個(gè)權(quán)重r就可以了，r可以根據(jù)比如那些用戶的行為更重要來改變，這里書中默認(rèn)r都是1。
[圖片上傳失敗...(image-3bde37-1558601635467)]
下述是推薦部分的代碼：
def UserCFRecommend(user,train,W,k):
# rvi 代表用戶v對(duì)物品i的權(quán)重
rvi = 1
rank = dict()
interacted_items = train[user]
related_user=[]
# 和 A 有相似度的用戶 ，B,C,D
for co_user,sim in W.items():
if co_user[0] == user:S
related_user.append((co_user[1],sim))
# v : 有相似度的用戶 , wuv : 用戶間相似度
for v , wuv in sorted(related_user , key = lambda a:a[1], reverse = True)[0:k]:
for item in train[v]:
if item in interacted_items:
continue
else:
# 還是得初始化，才可以賦值
if item not in rank.keys():
rank[item] = 0
rank[item] += wuv*rvi
return rank
最后選擇對(duì)A進(jìn)行推薦，K取3，由于A對(duì)a，b，d有過行為，K=3又代表相似用戶為B，C，D，所以會(huì)將c、e推薦給A。這里得到：
和書中結(jié)果一致。在書中對(duì)用戶相似度的改進(jìn)也在上述UserSimilarity部分的代碼中體現(xiàn)了，只需在計(jì)算W的時(shí)候?qū)?shù) IIF=True 即可。該改進(jìn)其實(shí)就是在計(jì)算u，v相似度時(shí)，對(duì)其進(jìn)行懲罰，懲罰是基于在倒排表中所有購(gòu)買此物品的用戶長(zhǎng)度，即此物品購(gòu)買人數(shù)越多，提供的相似度越小，具體理解請(qǐng)參考代碼。
代碼詳見：https://github.com/Alarical/Recommend/tree/master/UserCF
對(duì)于書中，表2-4 UserCF在movielens數(shù)據(jù)集中的運(yùn)用，主要參考https://blog.csdn.net/u012050154/article/details/52268057大神的博客和代碼，對(duì)與其代碼增加了部分注釋，詳見我的github。
