基于用户投票的排名算法

Posted on | In |

需求

基于用户投票的排名算法（一）：Delicious和Hacker News
基于用户投票的排名算法（二）：Reddit
基于用户投票的排名算法（三）：Stack Overflow
基于用户投票的排名算法（四）：牛顿冷却定律

对信息进行排名，意味着将信息按照重要性依次排列，并且及时进行更新。排列的依据，可以基于信息本身的特征，也可以基于用户的投票，即让用户决定，什么样的信息可以排在第一位。
根据用户的投票，决定最近一段时间内的”热文排名”。

最直觉、最简单的算法，莫过于按照单位时间内用户的投票数进行排名。得票最多的项目，自然就排在第一位。这个算法的优点是比较简单、容易部署、内容更新相当快；缺点是，一方面，排名变化不够平滑，前一个小时还排名靠前的内容，往往第二个小时就一落千丈，另一方面，缺乏自动淘汰旧项目的机制，某些热门内容可能会长期占据排行榜前列。
所以根据得票数，系统自动统计出热门文章排行榜。但是，并非得票最多的文章排在第一位，还要考虑时间因素，新文章应该比旧文章更容易得到好的排名。

公式： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

其中，　　P表示帖子的得票数，减去1是为了忽略发帖人的投票。 　　T表示距离发帖的时间（单位为小时），加上2是为了防止最新的帖子导致分母过小（之所以选择2，可能是因为从原始文章出现在其他网站，到转贴至Hacker News，平均需要两个小时）。　　G表示"重力因子"（gravityth power），即将帖子排名往下拉的力量，默认值为1.8，后文会详细讨论这个值。

从这个公式来看，决定帖子排名有三个因素：
第一个因素是得票数P。
在其他条件不变的情况下，得票越多，排名越高。 如果你不想让"高票帖子"与"低票帖子"的差距过大，可以在得票数上加一个小于1的指数，比如(P-1)^0.8。
第二个因素是距离发帖的时间T。
在其他条件不变的情况下，越是新发表的帖子，排名越高。或者说，一个帖子的排名，会随着时间不断下降。
第三个因素是重力因子G。
它的数值大小决定了排名随时间下降的速度。G值越大，曲线越陡峭，排名下降得越快，意味着排行榜的更新速度越快。

## 所有时段的排名

[基于用户投票的排名算法（五）：威尔逊区间](http://www.ruanyifeng.com/blog/2012/03/ranking_algorithm_wilson_score_interval.html)

一种常见的错误算法是： 　```　得分 = 赞成票 - 反对票

假定有两个项目，项目A是60张赞成票，40张反对票，项目B是550张赞成票，450张反对票。请问，谁应该排在前面？按照上面的公式，B会排在前面，因为它的得分（550 - 450 = 100）高于A（60 - 40 = 20）。但是实际上，B的好评率只有55%（550 / 1000），而A为60%（60 / 100），所以正确的结果应该是A排在前面。
另一种常见的错误算法是: 得分 = 赞成票 / 总票数 如果”总票数”很大，这种算法其实是对的。问题出在如果”总票数”很少，这时就会出错。假定A有2张赞成票、0张反对票，B有100张赞成票、1张反对票。这种算法会使得A排在B前面。这显然错误。

我们先做如下设定：
　　（1）每个用户的投票都是独立事件。
　　（2）用户只有两个选择，要么投赞成票，要么投反对票。
　　（3）如果投票总人数为n，其中赞成票为k，那么赞成票的比例p就等于k/n。
如果你熟悉统计学，可能已经看出来了，这是一种统计分布，叫做”二项分布”（binomial distribution）。这很重要，下面马上要用到。
们的思路是，p越大，就代表这个项目的好评比例越高，越应该排在前面。但是，p的可信性，取决于有多少人投票，如果样本太小，p就不可信。好在我们已经知道，p是”二项分布”中某个事件的发生概率，因此我们可以计算出p的置信区间。所谓”置信区间”，就是说，以某个概率而言，p会落在的那个区间。比如，某个产品的好评率是80%，但是这个值不一定可信。根据统计学，我们只能说，有95%的把握可以断定，好评率在75%到85%之间，即置信区间是[75%, 85%]。
这样一来，排名算法就比较清晰了：
　　第一步，计算每个项目的”好评率”（即赞成票的比例）。
　　第二步，计算每个”好评率”的置信区间（以95%的概率）。
　　第三步，根据置信区间的下限值，进行排名。这个值越大，排名就越高。

置信区间的实质，就是进行可信度的修正，弥补样本量过小的影响。如果样本多，就说明比较可信，不需要很大的修正，所以置信区间会比较窄，下限值会比较大；如果样本少，就说明不一定可信，必须进行较大的修正，所以置信区间会比较宽，下限值会比较小。

二项分布的置信区间有多种计算公式，最常见的是”正态区间”（Normal approximation interval），教科书里几乎都是这种方法。但是，它只适用于样本较多的情况（np > 5 且 n(1 − p) > 5），对于小样本，它的准确性很差。
1927年，美国数学家 Edwin Bidwell Wilson提出了一个修正公式，被称为”威尔逊区间”，很好地解决了小样本的准确性问题。

贝叶斯平均

基于用户投票的排名算法（六）：贝叶斯平均

介绍了”威尔逊区间”，它解决了投票人数过少、导致结果不可信的问题。
举例来说，如果只有2个人投票，”威尔逊区间”的下限值会将赞成票的比例大幅拉低。这样做固然保证了排名的可信性，但也带来了另一个问题：排行榜前列总是那些票数最多的项目，新项目或者冷门的项目，很难有出头机会，排名可能会长期靠后。

在排名页面的底部，IMDB给出了它的计算方法。WR = v/(v+m) * R + m/(v+m) *C

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

这种算法被称为”贝叶斯平均”（Bayesian average）。因为某种程度上，它借鉴了”贝叶斯推断”（Bayesian inference）的思想：既然不知道投票结果，那就先估计一个值，然后不断用新的信息修正，使得它越来越接近正确的值。
在这个公式中，m（总体平均分）是”先验概率”，每一次新的投票都是一个调整因子，使总体平均分不断向该项目的真实投票结果靠近。投票人数越多，该项目的”贝叶斯平均”就越接近算术平均，对排名的影响就越小。因此，这种方法可以给一些投票人数较少的项目，以相对公平的排名。
“贝叶斯平均”也有缺点，主要问题是它假设用户的投票是正态分布。比如，电影A有10个观众评分，5个为五星，5个为一星；电影B也有10个观众评分，都给了三星。这两部电影的平均得分（无论是算术平均，还是贝叶斯平均）都是三星，但是电影A可能比电影B更值得看。