推荐系统入门

维基百科定义如下：

推荐系统是一种信息过滤系统，用于预测用户对物品的 “评分” 或 “偏好”。

首先推荐系统是一个过滤系统，这里对 “物品” 的定义很宽泛，物品可以是人、消费品、服务、信息等等，不同的业务场景的 “物品” 是不同的。

e.g.

• 电商业务（淘宝、京东）的推荐系统中物品指商品；
• 社交业务（微博、facebook）的推荐系统中物品指人；
• 信息流业务（今日头条）中的推荐系统物品指信息。

推荐系统的使命：为用户（user）与物品（item）之间建立连接。

推荐系统的评测

亚马逊曾经表示过，他们有 20% ~ 30% 的销量来自于推荐系统，但是想要验证出具体的真实数据，只有将推荐系统从去除，然后对比有推荐系统和没有推荐系统的网站收入，当然这件事情永远不可能发生。如何确定一个推荐系统是否是一个好的推荐系统，推荐的物品是否符合用户预期？

虽然不能确定推荐算法对业务具体有多少帮助，但是我们还是能通过一些实验来测试推荐算法是否靠谱。

评测方法

这里是三种主流的评测推荐效果的实验方法：

1. 离线实验

   通过日志系统收集用户行为数据，将数据集按一定规则划分为训练集和测试集。

   在训练集进行训练模型，测试集进行预测。

1. 在线实验

   AB 测试，通过一定的规则将用户随机分成几组，并对不同组的用户采用不同的算法，然后通过统计不同组用户的各种不同的评测指标比较不同算法，比如可以统计不同组用户的点击率，通过点击率比较不同算法的性能。

2. 用户调查

   系统上线后，对部分用户灰度，然后对测试用进行调查，选择的测试用户需要保证用户的分布情况，在各个标签尽可能均衡。缺点是成本较高。

评测指标

评分预测

很多提供网站都会让用户给一个物品打分，如果知道用户对物品的历史评分，就可以学习到用户的兴趣模型，然后预测用户没有评分过的物品的评分。

• MSE： 均方误差

• RMSE： 均方根误差

• MAE：平均绝对误差

TopN 推荐

TopN 推荐的预测准确率一般通过精确率（ precision ） / 召回率（ recall ）度量。

1. 精确率 = 提取出的正确信息条数 / 提取出的信息条数

   TP / TP + FP

2. 召回率 = 提取出的正确信息条数 / 样本中的信息条数

   TP / TP + FN

TP (true positive)、FP (false positive)、TN (true negtive)、FN (false negtive)

具体怎么算，这里举个栗子。假设一共有 22 篇文章，里面 12 篇是你要找的。根据你某个算法，选出了其中 8 篇认为是你要找的，但是实际上在这 8 篇里面，只有 5 篇是真正你要找的。

precision 是 5/8=62.5% ，也就是，你找的这 8 篇，有 5 篇是真正对的

recall 是 5/12=41.7% ，也就是，一共有用的这 12 篇里面，你找到了其中 5 篇

看下图，可以很容易的理解这两个概念。

精确率和召回率是互相影响的，理想情况下肯定是做到两者都高，但是一般情况下准确率高、召回率就低，召回率低、准确率高，当然如果两者都低，那是什么地方出问题了 。

覆盖率

覆盖率（ coverage ）描述一个推荐系统对物品长尾的发掘能力。

怎么定义覆盖率？

推荐系统能够推荐出来的物品占总物品集合的比例。

这里会用到一个额外指标： 基尼系数 ，一般是通过这个指标来估算覆盖率。基尼系数本来是判断年收入分配公平程度的指标，基尼系数越小，年收入分配越平均；基尼系数越大，年收入分配越不平均。下面我们看看基尼系数的公式。

首先，我们将物品按照热门程度从低到高排列，横坐标可以理解为物品的热门度，纵坐标可以理解为物品的销售量，也就是越热门的商品销量越多。这条曲线肯定是在 y=x 曲线之下的，而且和 y=x 曲线相交在 (0,0) 和 (1,1)。

基尼系数的定义是 A 面积 除以 整个三角形面积。

B 的面积可以看出多个梯形相加：

最后推算出基尼系数的公式：

常用推荐算法

基于用户的协同过滤算法

基本思想：

当用户 A 需要推荐时，先找到与他兴趣相似的用户群体 G，然后把 G 喜欢，但是 A 没有接触过的物品推荐给 A。

原理：

1. 找到与目标用户兴趣相似的用户集合
2. 找到集合中用户喜欢，并且目标用户未接触过物品进行推荐

找到相似用户群

通常使用的方式为：Jaccard 公式、余弦相似度。

Jaccard 系数的计算方式为：样本交集个数和样本并集个数的比值，用 J (A,B) 表示。

余弦相似度，又称为余弦相似性，是通过计算两个向量的夹角余弦值来评估他们的相似度。

计算方式：两个向量的点积比向量的模的乘积，这里只是二维向量的计算方式，如果要扩展到 N 维向量，计算方式如下

假设目前共有 4 个用户： A、B、C、D；共有 5 个物品：a、b、c、d、e。用户与物品的关系（用户喜欢物品）如下图所示：

我们可以用物品作为向量的维度来表示用户，比如用户 A： A [1, 1, 0, 1, 0]
计算 A {a,b,d} 和 B {a,c} 的相似度为 0.408

上面这种方式对所有用户都进行了两两求其相似度，这种做法是非常耗时的，很多用户之间根本就没有相似度，比如 B、C 用户之间。我们可以换一个思路，站在物品的维度，先统计对物品产生过行为的用户，建立倒排表，然后只对共同物品产生过行为的用户才计算相似度。

def UserSimilarity(train):
    # build inverse table for item_users
    item_users = dict ()
    for u, items in train.items ():
        for i in items.keys ():
            if i not in item_users:
                item_users [i] = set ()
            item_users [i].add (u)
            
    #calculate co-rated items between users
    C = dict ()
    N = dict ()
    for i, users in item_users.items ():
        for u in users:
            N [u] += 1
            for v in users:
                if u == v:
                    continue
                C [u][v] += 1
                
    #calculate finial similarity matrix W
    W = dict ()
    for u, related_users in C.items ():
        for v, cuv in related_users.items ():
            W [u][v] = cuv /math.sqrt (N [u] * N [v])
    return W

根据倒查表 C，建立用户相似度矩阵 W：在 C 中，对于每一个物品 i，设其对应的用户为 u,v，在 W 中，更新相应的元素值，W [u][v]+=1, 最终得到的 W，就是用来计算余弦相似度的分子不为 0 的部分，最后，再除以分母即可得到最终的用户兴趣相似度。

推荐物品

下面用一个算法 p (u,i) 来计算用户 u 对物品 i 感兴趣的程度，找出与目标用户 u 最相似的 K 个用户，用集合 S (u, K) 表示，将 S 中用户喜欢的物品全部提取出来，并去除 u 已经喜欢的物品。

其中 $ r_{vi} $ 表示用户 v 对 i 的喜欢程度，在本例中都是为 1，在一些需要用户给予评分的推荐系统中，则要代入用户评分。

看样子用户 A 对 c 和 e 的喜欢程度可能是一样的，在真实的推荐系统中，只要按得分排序，取前几个物品就可以了。

基于物品的协同过滤算法

基本思想：

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

原理：

1. 计算物品之间的相似度
2. 根据物品的相似度和用户的历史行为给用户生成推荐列表

计算物品之间的相似度

我们可以使用下面公式定义物品相似度

分母表示喜欢物品 i 的用户数，分子表示同时喜欢 i 和 j 的用户数，该公式可以理解为，喜欢物品 i 的用户中有多少同时也喜欢物品 j。

但是该公式存在一个问题，如果 j 是热门物品，很多人都喜欢，那么 $ w_{ij} $ 就会无限接近 1。所有热门物品和其他物品就会有很大的相似度，这不利于发觉长尾信息。

为了避免热门商品，我们对 j 的权重进行惩罚。这和 UserCF 算法类似。

也可以先建立倒排表。

根据上表，计算相似度。

同时喜欢 a 的用户是 0 个，喜欢 a 和 c 的用户为别有 2 个和 3 个，得到 ac 相似度为 0，同理可以求 bc 和 cd 相似度。

根据物品的相似度生成推荐列表

S (i,K) 是和物品 j 最相似的 K 个物品的集合，对于不同的 i，物品 j 都必须满足与 i 的相似度在前 K 个，否则跳过该物品 i。最后得到的是物品 j 在用户喜欢的物品中的加权和，再进行 排序 即可向用户推荐其最感兴趣的物品。

# 结合用户喜好对物品排序 
def recommondation(user_id,user_dict,K):
    rank=defaultdict (int)
    l=list ()
    W=itemCF (user_dict)
    #i 为特定用户的电影 id，score 为其相应评分 
    for i,score in user_dict [user_id]: 
        #sorted () 的返回值为 list
        for j,wj in sorted (W [i].items (),key=itemgetter (1),reverse=True)[0:K]: 
            if j in user_dict [user_id]:
                continue
            rank [j] += score * wj 
    l=sorted (rank.items (),key=itemgetter (1),reverse=True)[0:10]
    return l

对用户 A 推荐 c 物品，根据用户 A 对 abd 产生过行为，所以

基于图的模型

随机游走的 PersonalRank 算法

将用户行为表示成二部图的形式，我们先不考虑各边的权重（即 u 对 i 的兴趣度），权重都默认为 1。感兴趣即有边相连，不感兴趣则没有边相连。

通过图，我们可以将对用户 u 推荐物品转换成计算用户顶点 u 和所有物品顶点之间的相关性，然后取出之前没有关联的物品，按照相关性排序。

PR 计算方式：

def PersonalRank(G, alpha, root, max_step):
    rank = dict ()
    rank = {x: 0 for x in G.keys ()}
    rank [root] = 1
    
    for _ in range (max_step):
        tmp = {x: 0 for x in G.keys ()}
        for i, ri in G.items ():
            for j in ri.keys ():
                tmp [j] += alpha * rank [i] / (1.0 * len (ri))
                if j == root:
                    tmp [j] += 1 - alpha
        rank = tmp

    return rank

if __name__ == '__main__':
    G = {'A': {'a': 1, 'c': 1},
         'B': {'a': 1, 'b': 1, 'c': 1, 'd': 1},
         'C': {'c': 1, 'd': 1},
         'a': {'A': 1, 'B': 1},
         'b': {'B': 1},
         'c': {'A': 1, 'B': 1, 'C': 1},
         'd': {'B': 1, 'C': 1}}

    rank = PersonalRank (G, 0.85, 'A', 20)
    
    for key, value in rank.items ():
        print (key, value)

推荐系统冷启动

所谓冷启动就是新物品和新用户进入系统后如何推荐以及被推荐。

新用户进入系统后，如何给用户推荐物品？

新物品进入系统后，如何将它推荐给用户？

常见解决方式

• 提供非个性推荐（热门排行榜）

  

• 利用用户注册信息（第三方授权信息、手机获取）

  

• 选择合适的物品启动用户的兴趣

  

总结

推荐系统是一个很庞大的体系，这里只是对一些很基本的东西做了很简单的介绍，推荐大家去看看项亮的《推荐系统实践》，文章的内容基本都来自这本书。