自然醒的博客

推荐系统入门

1/30/2019 机器学习推荐系统算法数学

# 什么是推荐系统

维基百科定义如下：

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

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

e.g.

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

twitter推荐 今日头条推荐

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

# 推荐系统的评测

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

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

# 评测方法

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

  1. 离线实验

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

优点 缺点
不需要对实际系统的控制权 无法计算商业上关心的指标（点击率、转化率）
不需要用户参与 离线实验的指标和商业指标存在差异
速度快，可测试大量算法 -

  1. 在线实验

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

  2. 用户调查

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

# 评测指标

评分预测

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

  • MSE： 均方误差

$$ \frac{1}{m} \sum_{i=1}^{m} (y_i - y_i^{'})^2 $$

  • RMSE： 均方根误差

$$ \sqrt{ \frac{1}{m} \sum_{i=1}^{m} (y_i - y_i^{'})^2 } $$

  • MAE：平均绝对误差

$$ \frac{1}{m} \sum_{i=1}^{m} |(y_i - y_i^{'})| $$

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篇

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

image

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

# 覆盖率

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

怎么定义覆盖率？

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

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

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

image

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

$$ \frac{ SA }{( SA + SB )} = \frac{ \frac{1}{2} - SB }{\frac{1}{2}} $$

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

image

$$ B = \sum_{i=1}^{n} \frac{1}{2} \frac{1}{n} (w_{i-1} + w_i) $$

$$ = \frac{1}{2} \frac{1}{n} (w_0 + w_1) + \frac{1}{2} \frac{1}{n} (w_1 + w_2) + ... + \frac{1}{2} \frac{1}{n} (w_{n-1} + w_n) $$

$$ = \frac{1}{2} \frac{1}{n} (0 + 2w_1 + 2w_2 + ... + 2w{n-1} + 1) $$

$$ = \frac{1}{n} \sum_{i=1}^{n}w_i + \frac{1}{2} \frac{1}{n} $$

最后推算出基尼系数的公式： $$ G = 1 - \frac{1}{n} (2 \sum_{i=1}^{n}w_i + 1) $$

# 常用推荐算法

image

# 基于用户的协同过滤算法

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

原理：

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

# 找到相似用户群

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

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

$$ J(A, B) = \frac{ |A \bigcap B| }{ |A \bigcup B| } $$

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

image

$$ cos\theta = \frac{ A \cdot B }{|A| |B|} = \frac{ x_{A}x_{B} + y_{A}y_{B} }{\sqrt{x^2_A + y^2_A} \times \sqrt{x^2_B + y^2_B}} $$

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

$$ cos\theta = \frac{ \sum_{i=1}^{n}(A_i \times B_i) }{ \sqrt{\sum_{i=1}^{n}(A_i)^2} \times \sqrt{\sum_{i=1}^{n}(B_i)^2} } $$

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

image

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

$$ W_{AB} = \frac{ 1\times1+1\times0+0\times1+1\times0 }{ \sqrt{1^2+1^2+0+1^2+0} \times \sqrt{1^2+0+1^2+0+0} } = \frac{1}{\sqrt{2}\times\sqrt{3}} = 0.408 $$

image

上面这种方式对所有用户都进行了两两求其相似度，这种做法是非常耗时的，很多用户之间根本就没有相似度，比如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 已经喜欢的物品。

$$ p(u,i) = \sum_{v \in S(u,K) \bigcap N(i)} w_{uv} \times r_{vi} $$

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

$$

p(A,c) = w_{AB} + w_{AD} = \frac{1}{\sqrt{6}} + \frac{1}{\sqrt{9}} = 0.7416

p(A,e) = w_{AC} + w_{AD} = \frac{1}{\sqrt{6}} + \frac{1}{\sqrt{9}} = 0.7416

$$

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

# 基于物品的协同过滤算法

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

image

原理：

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

# 计算物品之间的相似度

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

$$ w_{ij} = \frac{| N(i) \bigcap N(j) |}{ | N(i) | } $$

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

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

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

$$ w_{ij} = \frac{| N(i) \bigcap N(j) |}{ \sqrt{|N(i)||N(j)|} } $$

image

也可以先建立倒排表。

image

image

根据上表，计算相似度。

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

$$ w_{ac} = \frac{0}{\sqrt{1 \times 3}} = 0

w_{bc} = \frac{2}{\sqrt{3 \times 3}} = 0.667

w_{cd} = \frac{2}{\sqrt{3 \times 4}} = 0.577 $$

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

$$ p(u,j) = \sum_{i \in N(u) \bigcap S(i,K) } w_{ji} \times r_{ui} $$

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产生过行为，所以

$$ p(A,c) = 0.667 + 0.577 = 1.244 $$

# 基于图的模型

随机游走的PersonalRank算法

image

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

image

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

PR计算方式：

image

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)

image

# 推荐系统冷启动

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

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

image

# 常见解决方式

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

    image

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

    image

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

    image

# 总结

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

更新时间: 10/12/2022, 2:41:00 AM