大数据文摘基于大数据垂直领域50万粉丝的优势
想要发起一次众包的行业调研。
我们诚挚的邀请您用5分钟填写
《大数据行业从业者调研报告》
共同促成整个大数据行业的一次调研
·
授权转自
OReillyData
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个用户所在的集群中的职位并起来。然后我们除去任何用户已经访问过的职位，从而得到最后的职位推荐。
