工作职位推荐系统的算法与架构

标签: bigdata | 发表时间:2017-05-18 00:00 | 作者:
出处:http://itindex.net/admin/pagedetail

大数据

作者:Preetha Appan

Indeed.com 每个月有两亿不同的访客,有每天处理数亿次请求的推荐引擎。在这篇文章里,我们将描述我们的推荐引擎是如何演化的,如何从最初的基于Apache Mahout建立的最简化可用行产品,到一个在线离线混合的成熟产品管道。我们将探索这些变化对产品性能指标的影响,以及我们是如何通过使用算法、架构和模型格式的增量修改来解决这些挑战的。进一步,我们将回顾在系统设计中的一些相关经验,相信可以适用于任何高流量的机器学习应用中。

从搜索引擎到推荐

Indeed的产品运行在世界各地的许多数据中心上。来自每个数据中心的点击流数据以及其他应用事件被复制到我们在奥斯丁数据中心的一个中心化的HDFS数据仓库中。我们在这个数据仓库上进行计算分析并且构建我们的机器学习模型。
我们的职位搜索引擎是简单而直观的,只有两个输入:关键字和地点。搜索结果页面展示了一个匹配的职位列表,并基于相关性进行了排序。搜索引擎是我们的用户发现职位的主要方式。
我们决定在搜索引擎之上加入职位推荐作为一个新的交互模式是基于以下几个关键原因:

  • Indeed上所有搜索的25%只指定了一个区域,并没有搜索关键字。有许多的求职者并不确定在他们的搜索中应该用什么关键字
  • 当我们发送有针对性的推荐时,求职者的体验是个性化的
  • 推荐可以帮助甚至最复杂的用户来发现额外的未被搜索所涵盖的职位
  • 推荐为亚马逊带来了额外35%的销量为Netflix75%的内容阅览。很显然,推荐能提供额外的价值

推荐职位与推荐产品或者是电影有很显著的区别。这里列举了一些我们在构建推荐引擎时仔细考虑过的因素:

  • (职位)库存快速增长:我们每天要聚合计算几百万新的职位。可以推荐的职位的集合在不断变化
  • 新用户:每天有几百万新的求职者访问我们的网站并开始他们的职位搜索。我们想要能够根据有限的用户数据生成推荐。
  • 流动性:在indeed上一个职位的平均生命周期是30天左右。内容的更新十分重要,因为老的职位的需要非常可能已经被满足了
  • 有限的供给关系:一个发布的职位通常只招一个的应聘者。这和书籍或者电影很不一样,并不是只要有库存就可以同时推荐给很多用户。如果我们过度推荐一个职位,我们可能会让雇主收到到上千个应聘申请的轰炸。

如何理解推荐算法

推荐是一个匹配问题。给定一个用户集合和一个物品集合,我们想要将用户匹配到他们喜欢的物品上。有两种高层次的方法可以达成这类匹配:基于内容的和基于行为的。它们各有优缺点,此外也有将两者结合起来从而发挥各自优势的方法。

基于内容的方法使用比如用户偏好设置、被推荐物品的特性之类的数据来决定最佳匹配。对于职位推荐来说,通过职位的描述中的关键字来匹配用户上传的简历中的关键字是一种基于内容的推荐方法。通过一个职位的关键字来找到其他看上去相似的职位是另外一种基于内容的推荐的实现方法。

基于行为的方法利用了用户的行为来生成推荐。这类方法是领域无关的,这意味着同样的算法如果对于音乐或者电影有效的话,也可以被应用在求职领域。基于行为的方法会遇到所谓的冷启动问题。如果你只有很少的用户活动数据,就很难去生成高质量的推荐。

Mahout协同过滤

我们从建立一个基于行为的推荐引擎开始,因为我们想要利用我们已有的求职用户和他们的点击数据,我们的首次个性化推荐尝试是基于Apache Mahout提供的基于用户间的协同过滤算法的实现。我们将点击流数据喂给一个运行在Hadoop集群上的Mahout构建器并产生一个用户到推荐职位的映射。我们建立一个新的服务使得可以运行时访问这个模型,且多个客户端应用可以同时访问这个服务来获取推荐的职位。

产品原型的结果和障碍

作为一个产品原型,基于行为的推荐引擎向我们展示了一步步迭代前进的重要性。通过快速建立起这个系统并将其展示给用户,我们发现这种推荐对于求职者来说是有用的。然而,我们很快就遇到了一些在我们的数据流上使用Mahout的问题:

  • 模型构建器需要花大约18个小时的时间来处理Indeed网站2013年的点击流数据,这个数据量要比今日的数据小了三倍。
  • 我们只能一天执行一个模型构造器,这意味着每天新加入的用户直到第二天为止看不到任何推荐。
  • 几百万新汇总的职位在模型构造器再次运行之前是不能作为可见的推荐的。
  • 我们产生的模型是一个很大的映射,大约占了50吉字节的空间,需要花费数个小时将其通过广域网从其生成的数据中心拷贝到全球各地的数据中心。
  • Mahout的实现的提供露了一些可配置参数,比如相似度阈值。我们可以调节算法的参数,但是我们想要测试整个不同的算法这样的灵活性。

为推荐实现最小哈希

我们先解决最重要的问题:构建器太慢了。我们发现在Mahout中的用户间相似度是通过在n^2复杂度下的用户间两两比较的来实现的。仅对于美国的网站用户来说(五千万的访问量),这个比较的数量将达到15 * 10^15次,这是难以接受的。而且这一计算本身也是批量处理的,新加一个用户或者一个新的点击事件就要求重新计算所有的相似度。

我们意识到推荐是一个非精确匹配问题。我们是在寻求方法来发现给定用户最相近的用户们,但是我们并不需要100%准确。我们找了一些估算相似度的方法,不需要准确的计算。

主要贡献者戴夫格里菲思从一篇谷歌新闻学术论文上看到了最小哈希方法。最小哈希(或者最小独立序列)允许近似计算杰卡德相似度。将这一方法应用到两个用户都点击过的职位上,我们发现两个用户有更多共同的职位点击,那么他们的杰卡徳相似度就越高。为所有的用户对计算杰卡徳相似度的复杂度是O(n^2),而有了最小哈希后,我们可以将复杂度降到O(n)。

给定一个哈希函数h1, 一个项目集合的最小哈希被定义为将集合中所有项用该哈希函数分别哈希,然后取其中最小的值。由于方差太大,单个哈希函数不足以计算近似杰卡徳相似度。我们必须使用一个哈希函数族来合理地计算近似的杰卡徳距离。通过使用一个哈希函数族,最小哈希可被用来实现可调节杰卡徳相似度阈值的个性化推荐。

“挖掘海量数据集”,一个最近的由斯坦福大学教授莱斯科维克、拉贾罗曼和厄尔曼讲解的Coursera课程,非常详细的解释了最小哈希。他们书的第三章——“挖掘海量数据集”,解释了最小哈希背后的数学证明原理。

我们针对推荐的最小哈希的实现涉及到以下三个阶段:

1. 签名计算和集群分配

每一个求职者被映射到一个h个集群的集合,对应了一个哈希函数族H(下面的伪代码展示了这一过程):

H = {H1, H2, ..H20}
for user in Users
       for hash in H
             minhash[hash] = min{x∈Itemsi| hash(x)}

这里H是一个包含h个哈希函数的族。这一步的最后,每一个用户被一个签名集合所代表,也即一个由h个值组成的集群。

2. 集群扩展

共享相同签名的用户被认为是相似的,他们的职位将为被互相推荐。因此我们从每一个在集群中的用户开始,用其所有的职位来扩展每个集群。

3.生成推荐

为了给一个用户生成推荐,我们将h个用户所在的集群中的职位并起来。然后我们除去任何用户已经访问过的职位,从而得到最后的职位推荐。

为新用户推荐职位

最小哈希的数学属性使得我们可以解决为新用户推荐职位的问题,并且可以向所有的用户推荐新的职位。当新的点击数据到来的时候,我们增量地更新最小哈希签名。我们也在内存中维护新职位和他们的最小哈希族的映射。通过在内存中保留这两部分数据,我们就可以在新用户点击了一些职位后为他们推荐职位。只要任何新发布的职位被点击访问过,它就可以被推荐给用户。

在转移到最小哈希方法后,我们有了一个混合的推荐模型,由一个在Hadoop上的构建的离线每日被更新的组件和一个由当日的点击数据组成、在内存缓存中实现的在线组件。这两个模型被整合起来用以计算每一个用户的最终推荐集合。在我们做了这些改变之后,每一个用户的推荐变得更加得动态,因为它们将随着用户点击感兴趣的职位的同时发生变化。

这些改变中我们认识到,我们可以在性能和准确度上做出权衡,用小的误差增加来换大的性能提升。我们也认识到可以将较慢的离线模型通过在线的模型进行补充,从而得到更新的推荐结果。

工程基础设施的影响

包含每一个用户到他们的推荐的映射的推荐模型是一个相当庞大的文件。由于职位对于每个国家来说都是本地的,我们首先尝试将我们的数据基于大约的地理边界进行分片。我们在每一块区域运行模型构造器,而不是在整个世界运行一个。每一个地区都有多个国家组成。举个例子,东亚地区包括为中国、日本、韩国、香港、台湾以及印度的推荐。

但是在分片之后,一些区域产生的数据仍然十分庞大,需要花好几个小时才能通过广域网从欧洲数据中心拷贝到奥斯丁的Hadoop集群。为了解决这个问题,我们决定增量的传输推荐数据,而不是一天一次。我们重用了连续先写日志(sequential write ahead logs)的方法,通过日志结构合并树来实现。这一方法已经在Indeed的其他大型产品应用中得到验证,比如我们的文档服务。

我们修改了我们的模型构建器,将推荐数据存储成小的分段,而不是产生一个单独庞大的模型文件。每一个段文件使用顺序输入输出,并且为快速复制做了优化。这些分段在远程数据中心运行推荐服务时将被重新组装成一个日志结构合并树。

这一基础架构的改变使得用户可以比之前快数个小时在远程的数据中心上看到他们新的推荐。从我们的A/B测试的结果来看,由用户更快的得到新职位推荐带来了30%的点击量提升。

这一改进展示了工程基础设施的改进与算法的改进带来的影响不相上下。

改进A/B测试的速度

建立起计算和更新推荐的管道只是一个开始。为了改进覆盖率和推荐质量,我们需要加快我们的A/B测试的速度。我们为了调整最后的推荐集合做了很多决策。这些决策包括,相似度阈值,每一个用户的推荐包含的职位数量,以及各种不同的用来过滤掉低质量推荐的方法。我们想要调节和优化计算推荐的各个方面,但是这需要逐个对算法的每个改进都构建新的模型。测试多个改进想法意味着处理用户请求的服务器上多倍的磁盘以内存占用。

我们开始通过传输计算推荐的单独组件而不是最终的结果来改进我们的A/B测试。我们改变了推荐服务来执行最后的计算,即通过将碎片整合起来,而不是简单的读取模型返回结果。重要的推荐子组件是每个用户的集群分配,从每一个集群到这个集群中的职位的映射以及一个对于每个用户来说包含不应该推荐给他们的职位的黑名单。我们修改了我们的构建器,来产生这些组件,并且修改了我们的服务,将他们在收到请求时组合起来从而返回最终的推荐列表。

通过实现这种架构上的改变,我们只传输那些在每一个A/B测试中改变的子组件。比如说,如果测试只调节了什么样的职位会从一个用户的推荐中除去,那么我们只需要传输这个测试组的黑名单。

这一改变改进了A/B测试的速度的数量级。我们能够在很短的时间内测试并验证多个可以改进推荐质量和覆盖率的想法。之前,由于设置环境的开销较大,我们平均每个季度只能测试一个模型中的改进,

我们的经验表明A/B测试的速度应该在设计大型机器学习系统时就被考虑进去。你能越快地将你的想法放在用户面前,那么你就能越快地在上面迭代。

这篇文章总结了我们在构建我们的推荐引擎时做出的一系列算法和架构上的改变。我们迭代地构建软件,我们从一个最简单原型开始,从中获取经验,并不断改进。这些改变带来的成果是职位推荐的点击增加从2014年初最简原型时的3%增长到了14%。

我们将继续精炼我们的推荐引擎。我们正在使用Apache Spark建立一个原型模型,建立一个模型集成组合,并精炼我们的优化参数来应对流行偏见问题。

End.

转载请注明来自36大数据(36dsj.com): 36大数据» 工作职位推荐系统的算法与架构

相关 [工作 推荐系统 算法] 推荐:

工作职位推荐系统的算法与架构

- - IT瘾-bigdata
作者:Preetha Appan. Indeed.com 每个月有两亿不同的访客,有每天处理数亿次请求的推荐引擎. 在这篇文章里,我们将描述我们的推荐引擎是如何演化的,如何从最初的基于Apache Mahout建立的最简化可用行产品,到一个在线离线混合的成熟产品管道. 我们将探索这些变化对产品性能指标的影响,以及我们是如何通过使用算法、架构和模型格式的增量修改来解决这些挑战的.

推荐系统的常见推荐算法的性能比较

- - ITeye博客
数据集是movielens-1M( 下载)版本. 使用SlopeOne算法,每次随机选取6%的用户预测其喜好,进行5次实验,取MAE的均值,得到下表:. 绘制成折线图,如下图所示:.  由此可知,训练集越大,则推荐的准确率越高. 使用ItemCF算法,训练集大小为数据集的90%,每次随机选取30%的用户预测其喜好,进行5次实验,取MAE的均值,得到下表:.

推荐系统中常用算法 以及优点缺点对比

- - 人人都是产品经理
【Martin导读】随着互联网特别是社会化网络的快速发展,我们正处于信息过载的时代. 用户面对过量的信息很难找到自己真正感兴趣的内容,而内容提供商也很难把优质的内容准确推送给感兴趣的用户. 推荐系统被认为是解决这些问题的有效方法,它对用户的历史行为进行挖掘,对用户兴趣进行建模,并对用户未来的行为进行预测,从而建立了用户和内容的关系.

基于Spark MLlib平台的协同过滤算法---电影推荐系统

- - zzm
又好一阵子没有写文章了,阿弥陀佛...最近项目中要做理财推荐,所以,回过头来回顾一下协同过滤算法在推荐系统中的应用.     说到推荐系统,大家可能立马会想到协同过滤算法. 本文基于Spark MLlib平台实现一个向用户推荐电影的简单应用. 基于模型的协同过滤应用---电影推荐.     一、协同过滤算法概述.

用Hadoop流实现mapreduce版推荐系统基于物品的协同过滤算法

- - CSDN博客推荐文章
       以个性化新闻推荐为例,整个过程分成两个mapreduce阶段,由于hadoop流不支持多个mapreduce过程的自动化,所以所有mapreduce过程命令必须人工一个一个的执行. 1、首先需要将原始数据处理成如下形式的两个文件. 文件一:Item_user_score.txt. 如下图中第一行,物品100655565被用户1634974浏览过,则将分数记为1.

Min-Hash和推荐系统

- - xlvector - Recommender System
前几年看Google News Recommendation的那篇Paper,对里面提到的MinHash的算法基本没有注意,因为之前的习惯都是只注意论文的模型那块,至于怎么优化模型一般都只是扫一眼. 不过最近看了大量的Google Paper,发现Google在实现一个算法方面确实有很多独到之处. 其实,Min-Hash是LSH(Locality Sensitive Hash)的一种,我之前对LSH的了解仅仅限于知道它能把两个相似的东西Hash成两个汉明距离接近的2进制数.

推荐系统实战

- - 博客园_首页
推荐算法:基于特征的推荐算法. 推荐算法准确度度量公式:. 其中,R(u)表示对用户推荐的N个物品,T(u)表示用户u在测试集上喜欢的物品集合. 集合相似度度量公式(N维向量的距离度量公式):. 其中,N(u)表示用户u有过正反馈的物品集合. 其中,S(u,k)表示和用户u兴趣最接近的K个用户集合;N(i)表示对物品i有过正反馈的用户集合;w(u,v)表示用户u和用户v的兴趣相似度;r(v,i)表示用户v对物品i的兴趣.

推荐系统杂谈

- - 后端技术杂谈 | 飒然Hang
推荐系统是近些年非常火的技术,不管是电商类软件还是新闻类app,都号称有精准的推荐系统能给你推送你最感兴趣的内容. 现象级的资讯类app“今日头条”就得益于此成为了势头非常猛的一款产品. 本文就针对推荐系统讲述一些相关概念和实践经验. 首先需要明确的就是推荐系统的目标,一般来说不外乎以下几个:. 用户满意性:首当其冲的,推荐系统主要就是为了满足用户的需求,因此准确率是评判一个推荐系统好坏的最关键指标.

个性化推荐系统综述

- Tony - 所有文章 - UCD大社区
上个月写过一篇产品推荐的文章,详情请见《我所了解的产品推荐》,内容很泛,多为工作心得. 本周读了几篇相关的论文,收获颇多,分享点干货. 以下内容摘自《个性化推荐系统的研究进展》,该文发表于2009年1月的《自然科学进展》专题评述,作者是刘建国、周涛、汪秉宏. 我略去了具体的算法和许多公式,重点看原理、思路和比较.

推荐系统开源工具 – SVDFeature

- Roger - Resys China
SVDFeature是我们(上海交大Apex实验室)在参加KDDCUP 2011期间开发的. 通过这个工具,我们和港科大(HKUST)的联合小组InnerPeace在KDDCUP 2011中获得Track 1第三名,并创造单模型最好成绩. 在此分享给大家,并希望和大家有更多的交流. (1)基于feature的可扩展性 —— SVDFeature实现了我们的基础模型feature-based matrix factorization.