标点符(钱魏 Way)

数学之美:IMDB.COM排名算法

IMDB.COM是目前互联网上最为权威、系统、全面的电影资料网站,里面包括了几乎所有的电影,以及1982 年以后的电视剧集。 它所特有的电影评分系统深受影迷的欢迎,注册的用户可以给任何一部影片打分并加以评述,而网站又会根据影片所得平均分、选票的数目等计算得出影片的加权平均分并以此进行TOP250(最佳250部影片)和Bottom100(最差100部影片)的排行。

评选最佳250部电影时只考虑正式的投票者的投票结果。分值系统采用10分制,最低为awful(令人厌恶)的1分,最高为excellent(出类拔萃)的10分。值得注意的是,虽然很多影片在资料系统中得分很高,但由于未能达到TOP所要求的最低投票数而无法参加排行。

下面就一起来学习下IMDB所使用的排名算法。 imdb top 250用的是贝叶斯统计的算法得出的加权分(Weighted Rank-WR),公式如下:

  •  WR, 加权得分(weighted rating)。
  •  R,该电影的用户投票的平均得分(Rating)。
  •  v,该电影的投票人数(votes)。
  •  m,排名前 250 名的电影的最低投票数(现在为 3000)。
  •  C, 所有电影的平均得分(现在为6.9)。

仔细研究这个公式,你会发现,IMDB 为每部电影增加了 3000 张选票,并且这些选票的评分都为6.9。这样做的原因是,假设所有电影都至少有 3000 张选票,那么就都具备了进入前 250 名的评选条件;然后假设这 3000 张选票的评分是所有电影的平均得分(即假设这部电影具有平均水准);最后,用现有的观众投票进行修正,长期来看,v/(v+m)这部分的权重将越来越大,得分将慢慢接近真实情况。这样做拉近了不同电影之间投票人数的差异,使得投票人数较少的电影也有可能排名前列。

把这个公式写成更一般的形式:

  •  C,投票人数扩展的规模,是一个自行设定的常数,与整个网站的总体用户人数有关,可以等于每个项目的平均投票数。
  •  n,该项目的现有投票人数。
  •  x,该项目的每张选票的值。
  • m,总体平均分,即整个网站所有选票的算术平均值。

这种算法被称为”贝叶斯平均”(Bayesian average)。因为某种程度上,它借鉴了”贝叶斯推断”(Bayesian inference)的思想:既然不知道投票结果,那就先估计一个值,然后不断用新的信息修正,使得它越来越接近正确的值。

在这个公式中,m(总体平均分)是”先验概率”,每一次新的投票都是一个调整因子,使总体平均分不断向该项目的真实投票结果靠近。投票人数越多,该项目的”贝叶斯平均”就越接近算术平均,对排名的影响就越小。因此,这种方法可以给一些投票人数较少的项目,以相对公平的排名。

“贝叶斯平均”也有缺点,主要问题是它假设用户的投票是正态分布。比如,电影A有 10 个观众评分,5个为五星,5个为一星;电影B也有 10 个观众评分,都给了三星。这两部电影的平均得分(无论是算术平均,还是贝叶斯平均)都是三星,但是电影A可能比电影B更值得看。

解决这个问题的思路是,假定每个用户的投票都是独立事件,每次投票只有n个选项可以选择,那么这就服从“多项分布”(Multinomial distribution),就可以结合贝叶斯定理,计算该分布的期望值。由于这涉及复杂的统计学知识,这里就不深入了,感兴趣的朋友可以继续阅读 William Morgan 的How to rank products based on user input

另外对于无时间参与的评价系统,也可以参考威尔逊得分区,威尔逊得分分区的缺点在于排行榜前列总是那些票数最多的项目,新项目或者冷门的项目,很难有出头机会,排名可能会长期靠后。

参考地址:http://www.imdb.com/chart/top

码字很辛苦,转载请注明来自标点符《数学之美:IMDB.COM排名算法》

评论