user-based CF

user-based CF

当一个用户A需要个性化推荐时，先找到"和A有相似兴趣的其他用户"，然后把"这些用户喜欢&A没听过的物品"推荐给A。

算法步骤

（1）找到和目标用户兴趣相似的用户集合
（2）找到这个集合中的用户喜欢的&目标用户没听说过的物品推荐给目标用户
$$w_{uv}=\frac{|N(u)\cap N(v)|}{|N(u)\cup N(v)|},w_{uv}=\frac{|N(u)\cap N(v)|}{\sqrt{|N(u)||N(v)|}}$$
上式，即为用户$u$和用户$v$的用户兴趣相似度，其中$N(u)$表示用户$u$曾经有过正反馈的物品集合，$N(v)$表示用户$v$曾经有过正馈的物品集合，$|\cdot |$表示集合元素个数。

物品-用户倒排表

通常为了节省计算，可以先计算出$|N(u)\cap N(v)|\ne 0$的用户对$(u,v)$，然后再对这种情况除以分母，即建立"物品到用户"的倒排表。
（1）对于"每个物品"，都保存对该物品产生过行为的"用户列表"。
（2）记$C[u][v]=|N(u)\cap N(v)|$，扫描倒排表里"每个物品"对应的"用户列表"，将"用户列表"中的两两用户对应的$C[u][v]$加$1$，最终即可得所有用户之间不为0的$C[u][v]$。如果用户$u$和用户$v$同时属于倒排表中的$K$个物品对应的"用户列表"，则有$C[u][v]=K$。

def reverse_list(train):
    #生成item-users倒排表
    item_users = dict()
    for u, items in train.items():
        for i in items:   #用户u的物品i
            if i not in item_users:
                item_users[i] = []
            item_users[i].append(u)   #倒排表: 用户u的每一个物品i都对应有值u
    return item_users

#test:
train = {'a':{'A','B'},
         'b':{'A','C'},
         'c':{'B','D'},
         'd':{'A','D'},
         'e':{'C','D'}}
item_users = reverse_list(train)
print(item_users)
#Output:
{'B': ['a', 'c'], 
 'A': ['a', 'b', 'd'], 
 'C': ['b', 'e'], 
 'D': ['c', 'd', 'e']}

import math
def UserSimilarity(item_users):
    #计算用户间的共现矩阵
    C = dict()
    N = dict()
    for i, users in item_users.items():   #遍历物品-用户倒排表
        for u in users:
            if u not in N:
                N[u] = 0
            N[u] += 1   #统计每个用户 喜欢 几个物品
            for v in users:
                if u == v:
                    continue
                if u not in C:
                    C[u] = dict()
                if v not in C[u]:
                    C[u][v] = 0
                C[u][v] += 1   #用户u和用户v 同时喜欢 物品i

    #计算用户间的相似矩阵
    W = dict()
    for u, related_users in C.items():
        for v, cuv in related_users.items():
            if u not in W:
                W[u] = dict()
            if v not in W[u]:
                W[u][v] = 0
            W[u][v] = cuv/math.sqrt(N[u] * N[v])
    return W

#test:
W = UserSimilarity(item_users)
print(W)
#Output:
{'a': {'c': 0.5, 'b': 0.5, 'd': 0.5}, 
 'c': {'a': 0.5, 'd': 0.5, 'e': 0.5}, 
 'b': {'a': 0.5, 'd': 0.5, 'e': 0.5}, 
 'd': {'a': 0.5, 'b': 0.5, 'c': 0.5, 'e': 0.5}, 
 'e': {'b': 0.5, 'c': 0.5, 'd': 0.5}}

from operator import itemgetter
def Recommend(user, train, W, K):
    #为指定用户user生成推荐列表
    rank = dict()
    interacted_items = train[user]   #用户user喜欢的物品集合
    if user not in W:
        return rank
    for v, wuv in sorted(W[user].items(), key=itemgetter(1), reverse=True)[0:K]:   #与用户user相似度最大的K个用户
        for i in train[v]:   #相似用户v 喜欢的 物品i
            if i in interacted_items:   #如果相似用户v喜欢的物品i,在用户user原本喜欢的物品集合里,不进行推荐
                continue
            if i not in rank:
                rank[i] = 0
            rank[i] += wuv
    return rank

#test:
print(Recommend('a',train,W,1))
#Output:
{'D': 0.5}