推荐系统(一)—— 推荐系统概论

什么是推荐系统

推荐系统的定义

推荐系统是通过对用户的历史行为建模,自动联系用户和信息的一种工具。它能够在信息过载的环境中帮助用户发现他们感兴趣的信息,也能将信息推送给对它们感兴趣的用户。推荐系统已被广泛应用于电子商务、视频、音乐、阅读、社交网络、基于位置的服务、个性化邮件和广告等领域。

推荐系统的主要任务:

  • 联系用户和信息,解决信息过载问题:在信息过载的时代,信息消费者很难从大量信息中找到自己感兴趣的信息,而信息生产者也很难将自己的信息展现在对它感兴趣的用户面前。为了解决信息过载的问题,人们先后提出了很多解决方案,其中最具代表性的有以下三种:
解决方案 原理 代表公司 优点 缺点
分类目录 将著名的网站分门别类 雅虎、Hao123 方便用户对著名网站的访问 只能覆盖少量热门网站
搜索引擎 用户通过主动搜索关键词寻找自己需要的信息 谷歌、百度 方便用户按需查找信息 当用户无法准确描述自己需求时,无法进行查找
推荐系统 通过对用户的历史行为建模,自动为用户推荐满足他们兴趣的信息 亚马逊、今日头条 从用户角度:在用户在没有明确目的时也能帮助他们发现感兴趣的信息;从物品角度:能够更好地发掘物品的长尾 无法满足用户即时的有针对性的信息需求
  • 发掘长尾物品,解决长尾效应问题:在互联网领域,”长尾效应“战胜了”二八定律“,推荐系统能够充分发掘长尾物品(二八定律:经济学中的二八定律是指 80% 的销售额来自 20% 的热门商品;长尾效应:原来不受重视的销量小但种类多的产品由于总量巨大,累加起来的总收益可能会超过主流产品的现象)

推荐系统的架构

推荐系统核心组件有三层:数据层,计算逻辑层和推送服务层

  1. 数据层:是个性化推送的基础, 通过数据,将用户与信息相关联,通过特征,将用户与用户相区分,从而达到千人千面的效果;
  2. 逻辑层:是个性化推送的核心,通过特征匹配等相关的逻辑运算,将用户和信息做关联,筛选更合适的数据,计算逻辑直接影响到个性化推送的准确度;
  3. 推送层:是个性化推送与用户交互的通道。推送服务,间接的影响到个性化推送的到达率,影响着推送的效果;

数据层

可以从三个维度来把握推荐系统所依赖的数据:

  1. 用户维度:用来描述用户的特征数据,一般可以从用户属性和用户行为两个层面来了解用户,但不同行业会对用户在某一方面有更细致的特征描述;
    1. 用户属性:用户的静态特征属性,如年龄、性别、爱好等;
    2. 用户行为:用户的动态行为日志,如搜索行为、点击行为、评价行为等;
  2. 信息维度:用来描述信息的特征属性,不同种类的信息要用不同的特征指标来标识;
  3. 时空维度:与时间和位置相关的用户特征和信息特征,使用时一定要注意时效性;

按照前面数据的规模和是否需要实时存取,不同的行为数据将被存储在不同的媒介中。一般来说,需要实时存取的数据存储在数据库和缓存中,而大规模的非实时地存取数据存储在分布式文件系统(如HDFS)中。

逻辑层

基于用户数据和信息数据,推荐系统连接用户和信息的基本方式有三种:

  1. 基于用户的推荐:寻找与用户兴趣相似的用户,将相似用户感兴趣的信息推荐给该用户;
  2. 基于信息的推荐:寻找与用户之前感兴趣的信息相似的信息,将相似信息推荐给该用户;
  3. 基于特征的推荐:寻找用户感兴趣信息的特征,将具有相似特征的信息推荐给该用户;这里的特征具有不同的表现方式:
    1. 用户标签:为用户推荐他经常使用的标签下的物品;
    2. 物品属性:为用户推荐他比较感兴趣的某些类型的物品;
    3. 隐语义向量:计算用户对各种隐含类别的兴趣度,将兴趣度较高的类别中匹配度较高的物品推荐给用户;

以基于特征的推荐为例,推荐系统的核心任务可以被分解为两部分,一是如何为用户生成特征,另一个是如何根据特征找到物品。如果在一个系统中把上面提到的各种特征都统筹考虑,那么系统将会非常复杂,而且很难通过配置文件方便地配置不同特征和任何的权重。因此,推荐系统需要由多个推荐引擎组成,每个推荐引擎负责一类特征和一种任务,而推荐系统的任务只是将推荐引擎的结果按照一定权重或者优先级合并、过滤、排序然后返回。这样做的好处有:

  1. 可以方便地增加/删除引擎,控制不同引擎对推荐结果的影响。对于绝大多数需求,只需要通过不同的引擎组合实现;
  2. 可以实现推荐引擎级别的用户反馈,每一个推荐引擎其实代表了一种推荐策略,而不同的用户可能喜欢不同的推荐策略;

每个推荐引擎主要包括三个部分:

  1. 生成当前用户特征:该部分负责从数据库或者缓存中拿到用户行为数据,通过分析不同行为,生成当前用户的特征向量;
  2. 生成初始推荐列表:该部分负责将用户的特征向量通过特征-物品相关矩阵转化为初始推荐物品列表;
  3. 生成最终推荐列表:该部分负责对初始的推荐列表进行过滤、排名等处理,从而生成最终的推荐结果
    1. 过滤:主要是根据推送的历史,将之前推送过的信息过滤掉,同时,我们会根据实际情况,将不满足要求,或者质量比较差的信息过滤掉;
    2. 排名:主要是拟定推送信息的优先级,一般按照新颖性,多样性和用户反馈等规则来做排序,新颖性保证了尽量给用户推送他们不知道的、长尾的信息,多样性保证用户可以获取更广的内容,而用户反馈则通过收集用户真实的意愿(如通过用户对推送内容的打开,关闭操作反应用户的喜好)实现更优的排序;

推送层

个性化推送,在推送的内容和时机上都是离散的,所以很难做到批量推送,这就对推送服务的设计和性能提出了比较高的要求。 我们推送服务做了如下改进:

  1. 数据局部聚合:将相同消息内容的推送放在一起, 这样就可以做局部的批量推送,增加服务吞吐;
  2. 数据分片:将不同消息内容的推送分割为不同的数据片,不同的数据片可以并行推送, 提高推送效率;
  3. 守护线程:每台服务实例都保留一个守护线程,用于监控推送过程,确保推送有且仅有一次送达;

推荐系统的分类

按照数据分:

  1. 基于用户行为的方法:基于用户点击、购买行为的推荐;
  2. 基于用户标签的方法:基于用户为物品打标签的推荐;
  3. 基于上下文的方法:基于时间和空间的推荐;
  4. 基于社交网络的方法:基于好友的推荐;

按照算法分:

  1. 基于邻域的算法:协同过滤
  2. 基于概率模型的算法:LFM、LDA
  3. 基于图的算法:二分图随机游走

什么是好的推荐系统

在推荐系统的早期研究中,很多人将好的推荐系统定义为能够作出准确预测的推荐系统。然而从实践的角度来看,准确的预测并不是好的推荐

  1. 从用户角度看:推荐系统不仅要准确预测用户的行为,而且能够扩展用户的视野,帮助用户发现那些他们可能会感兴趣但不那么容易被发现的东西;
  2. 从商家角度看:不仅要将商家热门产品推荐给用户,还要将那些埋没在长尾的好商品介绍给用户;

好的推荐系统是能够让推荐系统参与三方(用户、商家、网站)共赢的系统:

评测方法

一般来说,一个新的推荐算法最终上线,需要完成以下三个实验:

  1. 首先,需要通过离线实验证明它在很多离线指标上优于现有的算法;
  2. 然后,需要通过用户调查确定它的用户满意度不低于现有的算法;
  3. 最后,通过在线的AB测试确定它在我们关心的指标上优于现有的算法;

离散实验

离线实验不需要一个实际的系统供它实验,而只要有一个从实际系统日志中提取的数据集即可,离线实验的一般步骤:

  1. 获取用户行为日志,按照一定格式生成标准数据集
  2. 将数据集划分为训练集和测试集
  3. 在训练集上训练用户兴趣模型,在测试集上进行预测
  4. 通过事先定义的离线指标评测模型在测试集上的效果
优点 缺点
不需要实际系统的控制权 无法计算商业上关心的指标
不需要用户参与 离线指标和商业指标存在差异
速度快,可以测试大量算法 -

用户调查

离线指标和商业指标存在差距,比如预测准确率和用户满意度之间就存在很大差别,如果要准确评测一个算法,需要相对比较真实的环境,最好的方法就是将算法直接上线测试,但在对算法不会降低用户满意度不太有把握的情况下,上线测试具有较大风险,所以在上线测试前需要做一次用户调查。

用户调查需要一些真实用户,让他们在需要测试的推荐系统上完成一些任务,在他们完成任务时观察和记录他们的行为或让他们回答一些问题,最后通过分析他们的行为和答案了解系统的性能。

优点 缺点
可以获取体现用户主观感受的指标 代价较高,多数情况下难以设计双盲实验
- 用户行为在测试环境下和在真实环境下可能有所不同

在线实验——AB test

在完成离线实验和必要的用户调查后,可以将推荐系统上线做AB测试,将它和旧的算法进行比较。通过一定的规则将用户随机分成几组,并对不同组的用户采用不同的算法,然后通过统计不同组用户的各种不同的评测指标比较不同算法,比如可以统计不同组用户的点击率,通过点击率比较不同算法的性能。

优点 缺点
可以公平获得不同算法实际在线时的性能指标,包括商业指标 设计复杂、周期长

流量切分:

一个大型网站的架构分前端和后端,从前端展示给用户的界面到最后端的算法,中间往往经过了很多层,这些层往往由不同的团队控制,而且都有可能做AB测试。如果为不同的层分别设计AB测试系统,那么不同的AB测试之间往往会互相干扰。比如,当我们进行一个后台推荐算法的AB测试,同时网页团队在做推荐页面的界面AB测试,最终的结果就是你不知道测试结果是自己算法的改变,还是推荐界面的改变造成的。因此,切分流量是AB测试中的关键,不同的层以及控制这些层的团队需要从一个统一的地方获得自己AB测试的流量,而不同层之间的流量应该是正交的。

一个简单的AB测试系统:

用户进入网站后,流量分配系统决定用户是否需要被进行AB测试,如果需要的话,流量分配系统会给用户打上在测试中属于什么分组的标签。然后用户浏览网页,而用户在浏览网页时的行为都会被通过日志系统发回后台的日志数据库。此时,如果用户有测试分组的标签,那么该标签也会被发回后台数据库。在后台,实验人员的工作首先是配置流量分配系统,决定满足什么条件的用户参加什么样的测试。其次,实验人员需要统计日志数据库中的数据,通过评测系统生成不同分组用户的实验报告,并比较和评测实验结果。

评测指标

如果你需要设计一些评测指标来评价你的推荐系统,最好的方式就是假想你是推荐系统三个参与方中的其中一方,你最关注的是什么。

  1. 对于用户:
    1. 系统应该给我推荐一些我一直以来都感兴趣的物品——准确度;
    2. 系统推荐不能太单调——多样性;
    3. 系统应该给我推荐一些我还不知道但我可能感兴趣的物品——新颖度、惊喜度;
    4. 系统应该给我推荐最新的信息——实时性;
    5. 总之,系统应该推荐给我一些让我满意的内容——用户满意度;
  2. 对于商家:
    1. 系统不仅要帮我把热门产品推荐给用户,还要能够将长尾物品推荐给对它感兴趣的用户——覆盖率;
    2. 推荐系统能够将新加入系统的物品推荐给用户——实时性;
  3. 对于系统:
    1. 应该让用户信任我的平台,这样才能提高他们与系统交互的积极性——信任度;
    2. 系统应该具有抗击作弊的能力——健壮性;
    3. 系统应该能为公司创造价值——商业目标;

下面我们将介绍各种推荐系统的评测指标,这些指标可以用于评价推荐系统在不同方面的性能。这些指标中有些是定量的,有些是定性的,有些可以通过离线实验得到,有些需要通过用户调查获得,有些只能在线评测。

指标 离线实验 问卷调查 在线实验
用户满意度 ×
推荐准确度 ×
覆盖率
多样性
新颖性
惊喜度 × ×

离线指标最常用的三率:准确率、召回率、覆盖率(除了用户满意度和商业目标,大多数指标都可以通过离线实验来得到)

用户满意度

用户满意度是评测推荐系统的最重要指标,只能通过用户调查或在线实验得到:

  • 用户调查:用户调查通常采用调查问卷的方式,好的调查问卷不是简单地询问用户对结果是否满意,而是从具体的方面询问用户对结果的感受;
    • 推荐的论文都是我非常想看的。
    • 推荐的论文很多我都看过了,确实是符合我兴趣的不错论文。
    • 推荐的论文和我的研究兴趣是相关的,但我并不喜欢。
    • 不知道为什么会推荐这些论文,它们和我的兴趣丝毫没有关系。
  • 在线系统:通过对用户行为的统计数据得到,比如:
    • 购买率:在电子商务网站中,如果用户购买了推荐的商品,就代表了他们在一定程度上满意;
    • 用户反馈界面收集用户满意度:让用户点击对推荐结果满意或不满意;
    • 点击率:用户点击次数越多代表月满意;
    • 用户停留时间:用户在推荐商品上停留的时间越长,代表用户越满意;
    • 转化率:用户点击后成功购买的比例越高,代表用户越满意;

准确度(precision)

准确度反映了系统准确预测用户行为的能力,几乎 99% 的推荐相关的论文都在讨论这个指标,主要是因为该指标可以通过离线实验计算,方便学术界研究人员研究推荐算法,准确度可以通过离线实验在测试集上计算得到;实际使用中,TopK 推荐相比评分预测更符合实际应用需要,因为预测用户是否会看一部电影比预测用户看了电影后会给它评多少分更重要:

  • 评分预测:如果推荐系统预测的是用户对物品的评分,一般采用均方根(RMSE)和平均绝对误差(MAE)作为评测指标;RMSE更加严格,因为它加大了对预测不准的评分的乘法(平方项);对于测试集中的一个用户 u 和物品 i,令 $r{ui}$ 是用户 u 对物品 i 的实际评分,而 $\hat{r}{ui}$ 是推荐算法给出的预测评分;
  • TOPK 推荐:如果推荐系统为每个用户一个个性化推荐列表,一般通过准确率(precision)或召回率(recall)来度量;有时为了全面评测 TopK 的准确率和召回率,一般会选取不同的推荐列表长度 K,计算一组准确率和召回率,然后画出准确率/召回率曲线(precision/recall curve);令 $R(u)$ 是根据用户在训练集上的行为给用户作出的推荐列表,而 $T(u)$ 是用户在测试集上的行为列表。那么,推荐结果的准确率和召回率可定义为:

覆盖率(coverage)

覆盖率描述了系统发掘长尾物品的能力,覆盖率是物品提供者会关心的指标,好的推荐系统不仅要让用户满意还要让商家满意,覆盖率可以通过离线实验获取,覆盖率有以下几种形式:

  • 覆盖比例:推荐系统能够推荐出来的物品占总物品集合的比例,假设系统的用户集合为U,推荐系统给每个用户推荐一个长度为N的物品列表R(u)。那么推荐系统的覆盖率可以通过下面的公式计算:
  • 覆盖分布:覆盖比例过于粗略,为了更细致地描述推荐系统发掘长尾的能力,需要描述推荐列表中物品出现次数的分布情况,经济学中有两个著名的指标可以用来定义覆盖率:熵和基尼系数
    • 信息熵(Entropy):熵越大代表覆盖率越
    • 基尼系数(Gini index):$i_j$是按照物品流行度p从小到大排序列表中第j个物品,在洛伦兹曲线上G=A/(A+B),基尼系数越大代表覆盖率越低

推荐系统的马太效应:推荐系统设计的初衷是为了消除马太效应,但很多研究表明,现在主流的推荐算法(如热门推荐、PageRank、协同过滤)是具有马太效应的,进入推荐列表的如果都是热门商品,因为有更多被曝光的机会,会变得更热门。

多样性

多样性是指推荐列表要能够覆盖用户的不同兴趣领域,可以通过离线计算或用户调查获取。多样性描述了推荐列表中两个物品之间的不相似性,多样性和相似性是对应的,可以通过物品间的相似性来定义推荐的多样性。假设s(i,j)∈[0,1]定义了物品i和j之间的相似度,那么用户u的推荐列表R(u)的多样性定义如下:

而推荐系统整体的多样性可以被定义为所有用户推荐列表的多样性的平均值:

新颖性

新颖性是指给用户推荐那些他们以前没有听说过的物品,可以通过离线计算和用户调查获取。评测新颖度的最简单方法是利用推荐结果的平均流行度,因为越不热门的物品越可能让用户觉得新颖。

惊喜度

惊喜度是指推荐的结果和用户的历史兴趣不相似,但却让用户觉得满意,可以通过离线计算和用户调查获取。个性化和多样性-新颖度-惊喜度是一对矛盾:ACM的推荐系统会议在2011年有一个专门的研讨会讨论推荐的多样性和新颖性。该研讨会的组织者认为,通过牺牲精度来提高多样性和新颖性是很容易的,而困难的是如何在不牺牲精度的情况下提高多样性和新颖性。

其他评测指标

信任度

信任度是指推荐结果要提升用户对推荐系统的信任,这样才能增加用户和系统的交互。可以通过用户调查和在线实验获取。

  • 用户调查:通过问卷调查的方式,询问用户是否信任推荐系统的结果;
  • 提供推荐解释:增加系统的透明度;
  • 基于好友推荐:让用户的好友向他推荐;
  • 对评论设置可信度:在每条评论显示作者信息,并让用户判断是否信任该条评论;
实时性

因为物品(新闻、微博)具有很强的时效性,所以需要在物品还具有时效性时就将它推荐给用户。事实性可以通过在线实验获取,实时性保函两个方面:

  1. 与用户相对应的实时性:推荐系统需要实时更新推荐列表来满足用户新的行为变化;
  2. 与物品相对应的实时性:推荐系统能够将新加入系统的物品推荐给用户;这主要考验系统处理物品冷启动的能力;

衡量推荐系统实时性的指标有:

  • 与用户相对应的实时性指标:可以通过推荐列表变化速率来评测,如果推荐列表在用户有行为后变化不大,说明推荐系统的实时性不高;
  • 与物品相对应的实时性指标:可以利用用户推荐列表中有多大比例是当天新加进来的来进行评测
健壮性

健壮性衡量了一个推荐系统抗共计作弊的能力,最著名的作弊方式是行为注入攻击:

  1. 可以注册很多账号,用这些账号同时购买A和自己的商品
  2. 雇用一批人给自己的商品非常高的评分,而评分行为是推荐系统依赖的重要用户行为

可以通过模拟攻击来测试推荐系统的健壮性,给定一个数据集和一个算法,可以用这个算法给这个数据集中的用户生成推荐列表。然后,用常用的攻击方法向数据集中注入噪声数据,然后利用算法在注入噪声后的数据集上再次给用户生成推荐列表。最后,通过比较攻击前后推荐列表的相似度评测算法的健壮性。

提高推荐系统健壮性的方法:

  1. 选择健壮性高的算法
  2. 设计推荐系统时尽可能使用代价比较高的用户行为:比如购买行为要比浏览点击行为代价更高
  3. 在使用数据前,进行攻击检测,从而对数据进行清理
商业目标

很多时候,网站评测推荐系统更加注重网站的商业目标是否达成。而商业目标和网站的盈利模式是息息相关的:

  1. 电子商务:主要目标是销售额
  2. 基于展示广告盈利的网站:广告展示总数
  3. 基于点击广告盈利的网站:广告点击总数

离线指标很多,在线指标也很多,如何优化离线指标来提高在线指标是推荐系统研究的重要问题,关于这个问题目前没有定论,只是不同系统的研究人员有不同的感性认识。对于可以离线优化的指标,《推荐系统实践》的作者认为应该在给定覆盖率、多样性、新颖性等限制条件下,尽量优化预测准确度:

1
2
3
4
5
6
max 准确度
s.t. 覆盖率>A
多样性>B
新颖性>C

A,B,C的取值视不同应用而定

推荐系统冷启动问题

冷启动问题:如何在没有大量用户数据的情况下设计个性化推荐系统并让用户对推荐结果满意。

冷启动问题分类:

  1. 用户冷启动:如何给新用户做推荐;
  2. 物品冷启动:如何将新物品推荐给可能对它感兴趣的用户;
  3. 系统冷启动:如何在一个新开发的网站上(还没有用户,只有一些物品信息)设计个性化推荐系统;

冷启动问题的一般解决方案:如何获取”第一推动力“

  1. 用户冷启动解决方案:
    1. 提供非个性推荐:可以先给用户推荐热门排行榜,等到用户数据收集到一定程度的时候再切换为个性化推荐;
    2. 利用用户注册信息推荐:获取用户的注册信息,根据用户的注册信息对用户分类,给用户推荐他所属分类中用户喜欢的物品;
    3. 利用社交账号好友推荐:当一个新用户通过社交账号登录网站时,可以从社交网站中获取用户的好友列表,然后给用户推荐好友在网站上喜欢的物品;
    4. 利用首次登陆反馈推荐:在新用户第一次登陆时,给用户提供一些物品,让用户反馈他们对这些物品的兴趣,然后根据用户反馈提供个性化推荐;
  2. 物品冷启动解决方案:利用物品信息,将新物品推荐给喜欢过相似物品的用户
  3. 系统冷启动解决方案:在系统冷启动时,通过专家进行标注

参考

坚持原创技术分享,您的支持将鼓励我继续创作!