自然醒的博客

推荐系统入门

· shenfq

什么是推荐系统§

维基百科定义如下:

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

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

e.g.

twitter推荐 今日头条推荐

推荐系统的使命:为用户(user)与物品(item)之间建立连接。

推荐系统的评测§

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

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

评测方法§

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

  1. 离线实验

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

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

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

  2. 用户调查

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

评测指标§

评分预测

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

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

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

1mi=1m(yiyi)\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 面积 除以 整个三角形面积。

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

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

image

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

=121n(w0+w1)+121n(w1+w2)+...+121n(wn1+wn)= \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)

=121n(0+2w1+2w2+...+2wn1+1)= \frac{1}{2} \frac{1}{n} (0 + 2w_1 + 2w_2 + ... + 2w{n-1} + 1)

=1ni=1nwi+121n= \frac{1}{n} \sum_{i=1}^{n}w_i + \frac{1}{2} \frac{1}{n}

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

G=11n(2i=1nwi+1)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)=ABABJ(A, B) = \frac{ |A \bigcap B| }{ |A \bigcup B| }

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

image

cosθ=ABAB=xAxB+yAyBxA2+yA2×xB2+yB2cos\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θ=i=1n(Ai×Bi)i=1n(Ai)2×i=1n(Bi)2cos\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

WAB=1×1+1×0+0×1+1×012+12+0+12+0×12+0+12+0+0=12×3=0.408W_{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)=vS(u,K)N(i)wuv×rvip(u,i) = \sum_{v \in S(u,K) \bigcap N(i)} w_{uv} \times r_{vi}

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

p(A,c)=wAB+wAD=16+19=0.7416p(A,e)=wAC+wAD=16+19=0.7416 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. 根据物品的相似度和用户的历史行为给用户生成推荐列表

计算物品之间的相似度§

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

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

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

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

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

wij=N(i)N(j)N(i)N(j)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相似度。

wac=01×3=0wbc=23×3=0.667wcd=23×4=0.577w_{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)=iN(u)S(i,K)wji×ruip(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.244p(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

常见解决方式§

总结§

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