大数据工程师:如何改进豆瓣电影Top250的算法思路

作者:飞林沙 算法工程师

影迷们经常关注的电影排行榜里,一部由100人评出9.0分的电影,和一部由10000人评出8.0分的电影,谁应该排在前面呢?

这是我们算法工程师时常会面对的问题。

一些深度影迷可能会想到 imdb.com (互联网电影数据库) 所采用的贝叶斯公式[见附注],这个公式的思路就是通过每部影片的[评分人数]作为调节排序的杠杆:如果这部影片的评分人数低于一个预设值,则影片的最终得分会向全部影片的平均分拉低。

由此可见,平衡评分人数和得分,避免小众高分影片排前,是这个计算方法的出发点。可问题在于:调节整个榜单的排序主要依赖于这个[评分人数预设值]。如果它设置的很低,那么最终的排序结果,就是每部影片自身评分从高到低在排序;如果它被设置得过高,那么只适用高曝光率的影片。据说 imdb.com 的这个预设值从500一路调整到了25000,遗憾的是这个算法仍然无法很好的解决他们的问题。

我们看看国内电影市场的现状。2013年上映的《疯狂原始人》两个月内在豆瓣电影得到了13万人次的评分,而1974年上映的《教父2》,到目前为止的评分总人数还不到10万人。近几年观影方式的多样化以及影院观影的持续火爆,使得新近上映的影片很轻松地就能获得大量的评分,相较之下,老片子的曝光机会少了很多。显然,继续调节 [评分人数的预设值] 已无法满足当前国内电影排行榜的实际需求。

如何解决这个问题呢?对算法工程师而言,我们通常会先用最基本的算法模型来应对,然后针对该算法带来的问题再修改并衍生出新的算法。比如针对这里的[评分人数预设值],我们可以分出老片和新片两个排行分别对待,也可以把时间因素考虑在内,如此等等。

不过这次我们决定换个做法。

在重新审视过 [豆瓣电影TOP250] 这一产品之后,我们提炼出两个关键指标:

1 它应该具备人群的广泛适应性。

例如一些动漫作品,因为拥有大量的粉丝,容易得到高分。如果采用 imdb.com 的榜单公式计算,这些影片的排名就会很靠前,但它们显然不适合被推荐给非动漫迷。

我们的解决办法,是将电影划分为若干分类,每一分类对应着喜欢此类有显著代表性的人群。如此一来,排序问题就变成了推荐问题,即把某部影片分别向所有类人群做推荐,能被推荐给越多人群的电影也就越具备广泛性。

实际上,实验的结果也证明了《肖申克的救赎》这类电影的人群广泛度远远超越了《EVA》这样的动漫作品。

2 它还需要具备持续关注度,不能昙花一现。

1957年的《十二怒汉》时至今日仍然被人津津乐道,而一些票房大片上映时非常红,过后就乏人问津。如何解决他们的排序关系?

我们取得每部影片在不同时间周期内的收藏人数和评分,将其汇成一条收藏曲线,再分析不同的曲线及其间关系,计算相应的分数。

这样,更新后的算法便初步形成了。算法更新后,榜单产生了一些变化,具体哪些变化?这就去看看吧!( http://movie.douban.com/top250 )

再说两句题外话,其实依靠简单的维度去做排序的榜单,我们平时也见的很多。这也许能解决一时的问题。对比简单排序甚至人工编辑的方式,一个算法模型在结果展示上可能没有优势,但面对环境因素的应变和扩展性上,算法有能力自我学习和进化,相信这也是产品生命力的一种体现吧。

附录: imdb.com 的top榜单公开公式(http://www.imdb.com/chart/top)

The formula for calculating the Top Rated 250 Titles gives a true Bayesian estimate:

weighted rating (WR) = (v ÷ (v+m)) × R + (m ÷ (v+m)) × C

where:

R = average for the movie (mean) = (Rating) -单部电影的得分 v = number of votes for the movie = (votes) -单部电影的有效评分人数 m = minimum votes required to be listed in the Top 250 (currently 25000) -入选top250榜单所需最低的有效评分人数 C = the mean vote across the whole report (currently 7.0) -所有影片的平均分

一直以来,我都很想借助一个例子来说明一个算法的诞生过程,或者说是思考的迭代过程,但是或者算法过于复杂,不利于初学者看懂,或者涉及到一些公司本身的机密,不便公开。正好这次有着这么一个不但容易而且比较典型的例子上线,就借机来说一下这个产品的诞生过程吧。 1. IMDB的TOP250 自IMDB以来,Top250就几乎成了各大网站的标配,而IMDB更是开放了自己Top250的算法: The formula for calculating the Top Rated 250 Titles gives a true Bayesian estimate: weighted rating (WR) = (v ÷ (v+m)) × R + (m ÷ (v+m)) × C where: R = average for the movie (mean) = (Rating) v = number of votes for the movie = (votes) m = minimum votes required to be listed in the Top 250 (currently 25000) C = the mean vote across the whole report (currently 7.0) for the Top 250, only votes from regular voters are considered. 方法其实很简单,就是一个基础的贝叶斯平均,随着互联网访问人数的日益增长,IMDB将自己最初的平均值m从500一路调整到了25000,而且据我所知,大部分公司的Top榜也是依据这样的方式来进行计算,甚至原封不动地去沿用了IMDB的参数设置,那么我们不妨来思考下传统的贝叶斯平均所带来的弊病,以及Top250产生本身的意义。 2. 分析贝叶斯平均带来的问题 我们首先思考一下贝叶斯平均中m和c的意义,从算法本身出发,贝叶斯平均希望把不足评分人数的电影评分向平均值(也就是7.0)去拉近。 首先说m和c本身,这个m和c是否具有通用性?很明显并不是,而是一个经统计得出的值。那么这个值到底应该是一个平均值还是分位数,我觉得依然需要我们依照实际的数据分布来评估界定。 另外说这个公式本身,大部分网站使用的都是所有电影的均值或者是中位数,比如说IMDB的25000,那么这个值是否真的可以起到贝叶斯平均的意义?如果大家感兴趣,也许可以尝试着根据豆瓣电影的评分以及收藏人数数据设置对应的v1,v2,r1,r2来做一次简单的不等式推导,我们会发现,所得出的排序几乎就是按照分数从高到低的排序。 究其原因,其实还是因为互联网上本身长尾现象的存在,这就需要我们更恰当地来选择m和c本身的统计值。接下来的问题就属于细节问题,每个人有每个人的解决办法,也许并不通用。 3. 重新思考Top250的产品意义 解决一个问题,或者为一个产品定制算法,整体我更愿意把他分成两步来走: A. 用最最基本的算法实现(对于这个例子来说就是贝叶斯平均) B. 思考该算法所带来的问题,然后改善原有算法或者产生新算法,接下来重新开始B的迭代过程。

回归正文,我们思考Top250本身的产品意义是什么,在我眼里Top250的意义如下: A. 非个性化推荐。也就是说对于一个电影的新用户,或者一个不知道该看什么的电影老用户,为其推荐Top250总是没有错,而且是最保险的。简而言之,就是具备人群的广泛适应性。 B. Top250的电影应该是经过时间考验的,而不是上映之初评分红极一时然后迅速跌落的。 那么接下来我们就分别来解决以上的两个问题。 4. 如何保证人群的广泛性 我们对人群广泛性举一个简单的例子,例如EVA是一部深受动漫迷喜爱的日本动漫作品,所以评分也都会达到9分以上,但是对于非动漫迷来说,为其推荐EVA明显并不是一个合适的做法。

我一直很努力地在强调数据中心和工具中心的概念,在软件世界中,重用是亘古不变的一个话题,那么在我看来,数据和工具这两个位于软件世界最底层的东西是可被最广泛重用的东西。

在之前的一段时间中,我们花费很大精力建设了一个豆瓣所有类型条目的聚类的一个数据中心,那么接下来我们便可以依据这个已有的数据来解决这个问题。

假设说我们已经对电影划分成了100个类,而这100个类分别又对应着其具有显著代表性的100类人群(例如A类喜欢看爱情动作片),也就是说相当于把Rank问题转换成了推荐问题,即我把某电影分别像向100类人群做推荐,可以被推荐给越多人群的电影说明就是一个越具有广泛性的电影。 在最终的结果评测时,我们也可以发现如肖申克的救赎一类电影的人群广泛程度远远超过了足球小将,EVA这样的受众比较局限的动漫。 5. 如何达到持续关注的目的 关于持续关注,我们也举一个简单的例子,1957年的十二怒汉距今已经过去半个世纪了,但是至今人们依旧对其津津乐道,而太多的爆米花大片可能在上映之初红极一时,然后随着偶像的跌落神坛,或者走出电影院的3D效果,也许就很快变得无人问津了。

在这里,我的方法是得到每一部电影在不同的时间间隔内对应的收藏人数和评分,这样其实类似与对每一部电影都得到了一条收藏和评分的曲线。那么接下来只分析不同的曲线以及之间的关系便可得出结论。 例如如果某部电影的曲线下降的很迅速,那么我们便可以说该电影只在上映之初得到了好评和关注。这样我们便可以评估每条曲线的质量并计算相应的分数,对之前的Rank做一次Rerank。 6. 效率没问题之前,效率都不是问题 除非极少数极为复杂的算法之外,在算法初步完成之前,我并不愿意去过多地考虑效率相关的问题。因为我总是固执地认为效率问题往往都可以在后期通过很多办法来解决掉,或者并行化计算,或者用C/C++来改进,或者增加预处理,或者干脆去做一些近似计算。 7. 总结 其实这个例子本身很简单,我想讲述的不过是如何诞生新产品的思维方式: 先框架,再细节。 先整体,再局部。 先简单,再迭代。 先阐述问题,再解决问题。 先广度优先,再深度优先。 最后说一句,某人(还是很懂算法的某人)在某天跟我吐槽首页豆瓣猜不需要算法,我说为什么呢?他说不就是热点和友邻广播么?我说OK,那你说热点怎么做呢?他说就依靠喜欢数来做order by。 我说那阿北写了一篇日记有100喜欢,我写了一篇日记有99喜欢,到底哪一个算是热点呢?如果你想评估每个人在过往日记的表现,那么修女每次的日记都有几百的喜欢,那么没有超过他的均值他就永远都上不了热点了么?如果你希望用户之间的比较,又要怎么样比较才能达到性能和质量的折中?

具体算法也许不便透露,我只是想说,永远不要认为一个外表看上去简单的产品在内部也是一样简单的,因为每个算法的背后都隐藏着无数你所忽略或者不去在意的种种细节。

再说两句题外话,其实依靠简单的维度去做排序的榜单,我们平时也见的很多。这也许能解决一时的问题。对比简单排序甚至人工编辑的方式,一个算法模型在结果展示上可能没有优势,但面对环境因素的应变和扩展性上,算法有能力自我学习和进化,相信这也是产品生命力的一种体现吧。

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2015-10-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据科学与人工智能

【陆勤践行】数据挖掘从入门到进阶

做数据挖掘也有些年头了,写这篇文一方面是写篇文,给有个朋友作为数据挖掘方面的参考,另一方面也是有抛砖引玉之意,希望能够和一些大牛交流,相互促进,让大家见笑了。 ...

2095
来自专栏新智元

【Nature封面论文】大脑词汇地图

【新智元导读】Nature 4月27日发表封面论文 The Brain Dictionary ,美国加州大学伯克利分校的科学家将常见的985个英语词汇相对应大脑...

3287
来自专栏大数据文摘

2017 NIPS 哪家强?我们统计了大会发文数量,谷歌和CMU稳居老大

1173
来自专栏PPV课数据科学社区

给外行能看懂的科普:这就叫自然语言处理

前几年曾经马少平老师的引荐,为某科普图书写过一篇短文介绍自然语言处理。如果只是介绍NLP的概念、任务和挑战,应该可以参考这篇小文。原文如下,仅供参考。 自然语言...

3236
来自专栏华章科技

【膜拜大神】当今世界最牛的25位顶尖大数据科学家

在大数据技术飞速发展的今天,谁才是我们大数据科研与工业界中最有威望的科学家呢?下面我们来进行梳理,共罗列了25位当今世界,无论是在学术与工业界都产生巨大影响的数...

752
来自专栏腾讯研究院的专栏

何为实在

image.png 推荐语: 霍金的《大设计》(The Grand Design)与其说是本科普读物,莫如说是相关“实在与终极”的著作。过去几千年间,...

2125
来自专栏AI科技评论

金句频出,16位大神在ICML上展开了一场机器学习的Great Debates

AI 科技评论按:机器学习圈子这几天发生了一件有趣的事,一群知名学者在 ICML 2018 上抱着吵架(辩论)的心思坐到一起,结果却没能吵起来。

1254
来自专栏AI科技评论

动态 | Nature机器学习子刊封闭式访问遭Jeff Dean等大牛联合抵制

AI 科技评论按:还记得之前韩国将 AI 应用于军事用途吗遭各国大牛联合抵制吗?近期又有人搞事情遭到这帮牛人的联合抵制,其实更准确来说搞事情的是刊物。

882
来自专栏新智元

论文 | 预测 API 从谷歌、亚马逊等大平台盗取机器学习算法

2016年10月18日, 世界人工智能大会技术分论坛,特设“新智元智库院长圆桌会议”,重量级研究院院长 7 剑下天山,汇集了中国人工智能产学研三界最豪华院长阵容...

3436
来自专栏AI科技评论

业界 | 谷歌的神经翻译系统并不意味着机器翻译到头了

AI科技评论按:本文是清华大学教授、中国中文信息学会副理事长孙茂松在MIFS 2016上的演讲实录,AI科技评论编辑整理。此次在北京举办的MIFS 2016是由...

2656

扫描关注云+社区