大数据工程师：如何改进豆瓣电影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喜欢，到底哪一个算是热点呢？如果你想评估每个人在过往日记的表现，那么修女每次的日记都有几百的喜欢，那么没有超过他的均值他就永远都上不了热点了么？如果你希望用户之间的比较，又要怎么样比较才能达到性能和质量的折中？

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

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