基于协同过滤（CF）算法的推荐系统

前言

         随着计算机领域技术的高速发展，电子商务时代的普及，个性化的推荐系统深入生活应用的各个方面。个性化推荐算法是推荐系统中最核心的技术，在很大程度上决定了电子商务推荐系统性能的优劣。而协同过滤推荐是个性化推荐系统应用最为广泛的技术，协同过滤推荐主要分为基于用户的协同过滤推荐、基于项目的协同过滤推荐和基于模型的协同过滤推荐。

一、协同过滤算法描述

        大数据时代产生了海量的数据，里面蕴含了丰富的价值。但是，大数据体量之大、种类之繁以及产生速率之快，海量的数据并不都是有价值的，用户从海量的数据中提取有用的、针对性的信息需要花费很大的时间成本。比如，当你面对如此多的电影列表，你想找到一部最符合自己兴趣的电影，因为电影数量之多，你不可能把所有的电影简介都看一遍。那么怎么解决这个问题呢？电影平台搜集你过去看过的全部电影，分析了解你对什么类型电影感兴趣，然后针对性的把你感兴趣的电影主动的罗列给你，你不用花费太多的精力便可快速找到满足自己需求的电影。推荐算法便是为解决这类实际需求而诞生了。

         推荐系统应用数据分析技术，找出用户最可能喜欢的东西推荐给用户，现在很多电子商务网站都有这个应用。目前用的比较多、比较成熟的推荐算法是协同过滤（Collaborative Filtering，简称CF）推荐算法，CF的基本思想是根据用户之前的喜好以及其他兴趣相近的用户的选择来给用户推荐物品。

        如图所示，在CF中，用m×n的矩阵表示用户对物品的喜好情况，一般用打分表示用户对物品的喜好程度，分数越高表示越喜欢这个物品，0表示没有买过该物品。图中行表示一个用户，列表示一个物品，Uij表示用户i对物品j的打分情况。CF分为两个过程，一个为预测过程，另一个为推荐过程。预测过程是预测用户对没有购买过的物品的可能打分值，推荐是根据预测阶段的结果推荐用户最可能喜欢的一个或Top-N个物品。

二、协同过滤的实现

要实现协同过滤的推荐算法，要进行以下三个步骤：

• 收集数据
• 找到相似用户或物品
• 进行推荐

1、收集数据

        这里的数据指的都是用户的历史行为数据，比如用户的购买历史，关注，收藏行为，或者发表了某些评论，给某个物品打了多少分等等，这些都可以用来作为数据供推荐算法使用，服务于推荐算法。需要特别指出的在于，不同的数据准确性不同，在使用时需要考虑到噪音所带来的影响。         要从用户的行为和偏好中发现规律，并基于此给予推荐，如何收集用户的偏好信息成为系统推荐效果最基础的决定因素。用户有很多方式向系统提供自己的偏好信息，而且不同的应用也可能大不相同，如下图：

2、找到相似用户或物品

        这一步其实就是计算用户间以及物品间的相似度。         关于相似度的计算，现有的几种基本方法都是基于向量（Vector）的，其实也就是计算两个向量的距离，距离越近相似度越大。在推荐的场景中，在用户 - 物品偏好的二维矩阵中，我们可以将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，或者将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度。下面我们详细介绍几种常用的相似度计算方法：

下一步是作出预测。你可以运用下面的公式做一个预测：

3、进行推荐

3.1、基于用户的协同过滤推荐(User-based Collaborative Filtering Recommendation)

        基于用户的协同过滤推荐算法先使用统计技术寻找与目标用户有相同喜好的邻居，然后根据目标用户的邻居的喜好产生向目标用户的推荐。基本原理就是利用用户访问行为的相似性来互相推荐用户可能感兴趣的资源，如图所示：

        上图示意出基于用户的协同过滤推荐机制的基本原理，假设用户 A 喜欢物品 A、物品 C，用户 B 喜欢物品 B，用户 C 喜欢物品 A 、物品 C 和物品 D；从这些用户的历史喜好信息中，我们可以发现用户 A 和用户 C 的口味和偏好是比较类似的，同时用户 C 还喜欢物品 D，那么我们可以推断用户 A 可能也喜欢物品 D，因此可以将物品 D 推荐给用户 A。         基于用户的协同过滤推荐机制和基于人口统计学的推荐机制都是计算用户的相似度，并基于“邻居”用户群计算推荐，但它们所不同的是如何计算用户的相似度，基于人口统计学的机制只考虑用户本身的特征，而基于用户的协同过滤机制可是在用户的历史偏好的数据上计算用户的相似度，它的基本假设是，喜欢类似物品的用户可能有相同或者相似的口味和偏好。

3.2、基于项目的协同过滤推荐(Item-based Collaborative Filtering Recommendation)

        根据所有用户对物品或者信息的评价，发现物品和物品之间的相似度，然后根据用户的历史偏好信息将类似的物品推荐给该用户，如图所示：

        上图表明基于项目的协同过滤推荐的基本原理，用户A喜欢物品A和物品C，用户B喜欢物品A、物品B和物品C，用户C喜欢物品A，从这些用户的历史喜好中可以认为物品A与物品C比较类似，喜欢物品A的都喜欢物品C，基于这个判断用户C可能也喜欢物品C，所以推荐系统将物品C推荐给用户C。          基于项目的协同过滤推荐和基于内容的协同过滤推荐都是基于物品相似度预测推荐，只是相似度度量的方法不一样，前者是从用户历史的偏好推断，而后者是基于物品本身的属性特征信息。

3.3、UserCF和ItemCF的区别

三、算法实例

以ItemCF为例子具体介绍下整个算法流程。 算法流程：

1. 构建用户–>物品的倒排；
2. 构建物品与物品的同现矩阵；
3. 计算物品之间的相似度，即计算相似矩阵；
4. 根据用户的历史记录，给用户推荐物品；

算法流程1

构建用户–>物品的倒排 如下表，行表示用户，列表示物品，1表示用户喜欢该物品

例如python构建的数据格式如下
{
'A': {'a': '1', 'b': '1', 'd': '1'}, 
'B': {'c': '1', 'b': '1', 'e': '1'}, 
'C': {'c': '1', 'd': '1'}, 
'D': {'c': '1', 'b': '1', 'd': '1'},
'E': {'a': '1', 'd': '1'}
}

算法流程2

构建物品与物品的同现矩阵

共现矩阵C表示同时喜欢两个物品的用户数，是根据用户物品倒排表计算出来的。如根据上面的用户物品倒排表可以计算出如下的共现矩阵C：

算法流程3

计算物品之间的相似度，即计算相似矩阵

其中两个物品之间的相似度如何计算？         设|N(i)|表示喜欢物品i的用户数，|N(i)⋂N(j)|表示同时喜欢物品i，j的用户数，则物品i与物品j的相似度为：

        (1)式有一个问题，当物品j是一个很热门的商品时，人人都喜欢，那么wijwij就会很接近于1，即(1)式会让很多物品都和热门商品有一个很大的相似度，所以可以改进一下公式：

        算法流程2中的共现矩阵C其实就是式(2)的分子，矩阵N（用于计算分母）表示喜欢某物品的用户数（是总的用户数），则(2)式中的分母便很容易求解出来了。

矩阵N如下所示：

利用式（2）便能计算物品之间的余弦相似矩阵如下：

算法流程4

根据用户的历史记录，给用户推荐物品；

最终推荐的是什么物品，是由预测兴趣度决定的。

物品j预测兴趣度=用户喜欢的物品i的兴趣度×物品i和物品j的相似度

例如：A用户喜欢a，b，d ，兴趣度分别为1,1,1

        推荐c的预测兴趣度=1X0.67+1X0.58=1.25         推荐e的预测兴趣度=1X0.58=0.58

四、python实现案例

from math import sqrt
import operator

#1.构建用户-->物品的倒排
def loadData(files):
    data ={}
    for line in files:
        user,score,item=line.split(",")  #按","将每组数据单独分开,并将每组的数据赋予对应变量
        data.setdefault(user,{})
        data[user][item]=score
    print ("----1.用户：物品的倒排----")
    print (data)
    return data

#2.计算
# 2.1 构造物品-->物品的共现矩阵
# 2.2 计算物品与物品的相似矩阵
def similarity(data):
    # 2.1 构造物品：物品的共现矩阵
    N={};#喜欢物品i的总人数
    C={};#喜欢物品i也喜欢物品j的人数
    for user,item in data.items():
        for i,score in item.items():
            N.setdefault(i,0)
            N[i]+=1
            C.setdefault(i,{})
            for j,scores in item.items():
                if j not in i:
                    C[i].setdefault(j,0)
                    C[i][j]+=1

    print ("---2.构造的共现矩阵---")
    print ('N:',N)
    print ('C:',C)

    #2.2 计算物品与物品的相似矩阵
    W={};
    for i,item in C.items():
        W.setdefault(i,{})
        for j,item2 in item.items():
            W[i].setdefault(j,0)
            W[i][j]=C[i][j]/sqrt(N[i]*N[j])
    print ("---3.构造的相似矩阵---")
    print (W)
    return W

#3.根据用户的历史记录，给用户推荐物品
def recommandList(data,W,user,k=3,N=10):
    rank={}
    for i,score in data[user].items():#获得用户user历史记录，如A用户的历史记录为{'a': '1', 'b': '1', 'd': '1'}
        for j,w in sorted(W[i].items(),key=operator.itemgetter(1),reverse=True)[0:k]:#获得与物品i相似的k个物品
            if j not in data[user].keys():#该相似的物品不在用户user的记录里
                rank.setdefault(j,0)
                rank[j]+=float(score) * w

    print ("---4.推荐----")
    print (sorted(rank.items(),key=operator.itemgetter(1),reverse=True)[0:N])
    return sorted(rank.items(),key=operator.itemgetter(1),reverse=True)[0:N]

if __name__=='__main__':
    #用户，兴趣度，物品
    uid_score_bid = ['A,1,a', 'A,1,b', 'A,1,d', 'B,1,b', 'B,1,c', 'B,1,e', 'C,1,c', 'C,1,d', 'D,1,b', 'D,1,c', 'D,1,d',
                     'E,1,a', 'E,1,d']
    data=loadData(uid_score_bid)#获得数据
    W=similarity(data)#计算物品相似矩阵
    recommandList(data,W,'A',3,10)#推荐

        为了方便理解python的实现过程，这里只用了少数数据集并是手输上去的，具体情况运用可再加段代码用于读取并处理数据文件。

五、算法的优缺点

        这个算法实现起来也比较简单，但是在实际应用中有时候也会有问题的。

        比如一些非常流行的商品可能很多人都喜欢，这种商品推荐给你就没什么意义了，所以计算的时候需要对这种商品加一个权重或者把这种商品完全去掉也行。

        再有，对于一些通用的东西，比如买书的时候的工具书，如现代汉语词典，新华字典神马的，通用性太强了，推荐也没什么必要了。

UserCF和ItemCF优缺点的对比