博客
博客
文章目录
  1. 什么是推荐系统
  2. 推荐系统的评测
    1. 评测方法
    2. 评测指标
      1. 覆盖率
  3. 常用推荐算法
    1. 基于用户的协同过滤算法
      1. 找到相似用户群
      2. 推荐物品
    2. 基于物品的协同过滤算法
      1. 计算物品之间的相似度
      2. 根据物品的相似度生成推荐列表
    3. 基于图的模型
  4. 推荐系统冷启动
    1. 常见解决方式
  5. 总结

推荐系统入门

什么是推荐系统

维基百科定义如下:

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

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

e.g.

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

twitter 推荐
今日头条推荐

推荐系统的使命:为用户(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 篇

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

image

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

覆盖率

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

怎么定义覆盖率?

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

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

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

image

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

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

image

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

常用推荐算法

image

基于用户的协同过滤算法

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

原理:

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

找到相似用户群

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

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

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

image

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

假设目前共有 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

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 已经喜欢的物品。

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

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

基于物品的协同过滤算法

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

image

原理:

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

计算物品之间的相似度

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

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

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

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

image

也可以先建立倒排表。

image

image

根据上表,计算相似度。

同时喜欢 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 算法

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

总结

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

支持一下
扫一扫,支持一下
  • 微信扫一扫
  • 支付宝扫一扫