基于物品的协同过滤算法-简核网

基于物品的协同过滤算法

Poblog 07月31日 2018

基于用户的协同过滤算法:
1.随着网站的用户数目越来越大，计算用户兴趣相似度矩阵将越来越困难，其运算时间复杂度和空间复杂度的增长和用户数的增长近似于平方关系
2.基于用户的协同过滤很难对推荐结果作出解释

给用户推荐那些和他们之前喜欢的物品相似的物品(ItemCF)

通过分析用户的行为记录计算物品之间的相似度

算法认为，物品 A 和物品 B 具有很大的相似度是因为喜欢物品 A 的用户大都也喜欢物品B

基于物品的协同过滤算法可以利用用户的历史行为给推荐结果提供推荐解释:比如给用户推荐《天龙八部》的解释可以是因为用户之前喜欢《射雕英雄传》

算法主要分为两步:
(1.) 计算物品之间的相似度。
(2.) 根据物品的相似度和用户的历史行为给用户生成推荐列表

公式:喜欢物品 i 的用户中有多少比例的用户也喜欢物品 j
存在一个问题。如果物品 j 很热门，很多人都喜欢，那么 W ij 就会很大，接近 1

为了避免推荐出热门的物品，惩罚了物品 j 的权重，因此减轻了热门物品会和很多物品相似的可能性

用户都可以通过他们的历史兴趣列表给物品“贡献”相似度

蕴涵着一个假设，就是每个用户的兴趣都局限在某几个方面，因此如果两个物品属于一个用户的兴趣列表，那么这两个物品可能就属于有限的几个领域，而如果两个物品属于很多用户的兴趣列表，那么它
们就可能属于同一个领域，因而有很大的相似度

首先建立用户 — 物品倒排表

然后对于每个用户，将他物品列表中的物品两两在共现矩阵 C 中加 1

C[i][j] 记录了同时喜欢物品 i和物品 j 的用户数

C 矩阵归一化可以得到物品之间的余弦相似度矩阵 W

在 MovieLens 数据集上,尽管在计算过程中没有利用任何内容属性，但利用 ItemCF 计算的结果却是可以从内容上看出某种相似度的,一般来说，同系列的电影、同主角的电影、同风格的电影、同国家和地区的电影会有比较大的相似度

ItemCF通过如下公式计算用户u对一个物品j的兴趣
N(u)是用户喜欢的物品的集合
S(j,K)是和物品j最相似的K个物品的集合
w ji 是物品j和i的相似度
r ui 是用户u对物品i的兴趣

公式的含义是，和用户历史上感兴趣的物品越相似的物品，越有可能在用户的推荐列表中获得比较高的排名

算法分析(代码流程)

计算物品之间的相似度

def ItemSimilarity(train):
    //train:{'196': {'242': 1.0,'241': 1.0},
	       '198': {'243': 1.0,'246': 1.0}
	        ....}  训练集字典  user:{movieId1,....}
    //

    #calculate co-rated users between items
    #构建用户-物品表
    C =dict()
    N = dict()
    for u,items in train.items():
    //u:'196'
	items:{'242': 1.0,....}
	//

        for i in items:
	//i:'242'
	    //

            N.setdefault(i,0)
            N[i] += 1
	    //N:记录物品出现的总次数
	    {'242': 1}
	    //

            C.setdefault(i,{})
	    //C:记录物品-物品在同一用户列表出现次数
	    {'242': {}}
	    //

            for j in items:
                if i == j:
                    continue
                C[i].setdefault(j,0)
                C[i][j] += 1
                //C:'242'和'393'共同出现在一个用户的列表中
		{'242': {'393': 1}}
		//

   //C:'242'和'393'共同出现在5用户的列表中
    {'242': {'393': 6, '381': 5, '251': 1, '655': 1, '663': 1, .....}
     ...}
   //

    #calculate finial similarity matrix W
    W = C.copy()
    //W和C一样,用于存储物品之间的相似度
    //

    for i,related_items in C.items():
       //i:'242'  物品1
         related_items:{'393': 6, '381': 5, '251': 1, '655': 1, '663': 1, .....}  和物品有关联的物品列表
       //

        for j,cij in related_items.items():
	  //j:'393' 有关联的物品2
	    cij:6   关联次数
	  //

            W[i][j] = cij / math.sqrt(N[i] * N[j])
	    //W:赋值i和j的相似度  * N[j]的缘故是对热门物品进行惩罚避免推荐的全部是热门物品
	    //

    return W

//给user_id推荐 K*评价过的物品数量 个相似度最高的商品
 def Recommend(user_id,train, W,K = 3):
   //user:'1'
    train:{'user':{goods...},...}
    W:{'goods1':{'goods2':like,...},...}
    //

    rank = dict()
    //rank:user_id每个评价过的物品找出对应相似的物品
    //

    ru = train[user_id]
    //ru:{'61': 1.0, '33': 1.0, ...}
      存放user评价过的电影
    //

    for i,pi in ru.items():
        //i:'61'
	  pi:1.0
	//

        for j,wij in sorted(W[i].items(), \
                           key = operator.itemgetter(1), reverse = True)[0:K]:
	   //后面的公式找出物品i最相似的k个物品
	   sorted:
	   : [('59', 0.6040404496926219), ('60', 0.5457051563317492), ('462', 0.38018781261549794)]
	      j:'59'  物品id
	      wij:0.6040404496926219  相似度
	   //

            if j in ru:
	        //已经出现过的不推荐

                continue
            rank.setdefault(j,0)
            rank[j] += pi * wij
	    //计算推荐的物品的相似度
	    //

    return rank
    //rank:给user_id推荐的物品以及相似度
    {'59': 1.6877785618790362, '462': 0.7885750339292101, '576': 0.4968275423500662, '578': 2.392579109269496, ...}
    //

获取推荐

def Recommendation(users, train, W, K = 10):
    //users:(['22', '122', '291', '308', '63', '7',...])
      测试集中的所有用户
      train:{'user':{goods...},...}
      W:{'i':{'j':like,...},...}
      K = 10 计算相似物品的个数
    //

    result = dict()
    for user in users:
        //user:'22'
	//

        rank = Recommend(user,train,W,K)
	//rank:根据user的物品推荐多个物品
	{'1055': 0.40555355282690636, '585': 0.35410026391408517, ....}
	//

        R = sorted(rank.items(), key = operator.itemgetter(1), \
                   reverse = True)
	//R:推荐列表的排序
	: [('202', 3.309368093882904), ('228', 2.3711020273149623), ....]
	//

        result[user] = R
	//result:用户和对应的推荐列表
	{'22': [('202', 3.309368093882904), ('228', 2.3711020273149623), ....]}
	//

    return result