基于用户投票的打分算法

互联网社区，用户极易淹没在海量的信息中，如何从海量信息中，快速准确的找出热点内容，成了互联网社区的一大核心问题。各种各样的排名算法，是目前过滤信息的主要手段之一。

对信息进行排名，意味着将信息按照重要性依次排列，并且及时进行更新。排列的依据，可以基于信息本身的特征，也可以基于用户的投票，即让用户决定，什么样的信息可以排在第一位。一种最常见的错误算法是：

得分 = 赞成票数 - 反对票数

假定有两个项目，项目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前面。这显然错误。

亚马逊曾经一度使用这种排序算法。

亚马逊排序算法

威尔逊区间法

之前提到的两种算法都有这样或那样的问题，那么，更好的算法是什么呢？为了方便建模，我们先有如下假定：

每个用户的投票都是独立事件。

用户只有两个选择，要么投赞成票，要么投反对票。

如果投票总人数为n，其中赞成票为k，那么赞成票的比例p就等于k/n。

如果你认同以上假定，那么你就会发现，这其实用户的投票分布其实是一个二项分布。我们发现，p越大，表示这个项目的好评比例越高，越应该排在前面。但是p的置信度，取决于投票的人数，人数越多，p的可信度就越大，在给定置信度的情况下，其置信区间发散程度就越小，置信区间下限就越大；投票人数越少，p的可信度就越小，在给定置信度的情况下，其置信区间发散程度就越大，置信区间下限就越小。因此，我们可以采用如下排名算法：

计算每个项目的”好评率”（即赞成票的比例）。

计算每个”好评率”的置信区间（以95%的概率）。

根据置信区间的下限值，进行排名。这个值越大，排名就越高。

这样做的原理是，置信区间的宽窄与样本的数量有关。比如，A有8张赞成票，2张反对票；B有80张赞成票，20张反对票。这两个项目的赞成票比例都是80%，但是B的置信区间（假定[75%, 85%]）会比A的置信区间（假定[70%, 90%]）窄得多，因此B的置信区间的下限值（75%）会比A（70%）大，所以B应该排在A前面。置信区间的实质，就是进行可信度的修正，弥补样本量过小的影响。如果样本多，就说明比较可信，不需要很大的修正，所以置信区间会比较窄，下限值会比较大；如果样本少，就说明不一定可信，必须进行较大的修正，所以置信区间会比较宽，下限值会比较小。

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

$[\frac{\hat p + \frac{1}{2n}z_{1-\frac{\alpha}{2}}^2 - z_{1-\frac{\alpha}{2}}\sqrt{\frac{\hat p(1-\hat p)}{n}+\frac{z_{1-\frac{\alpha}{2}}^2}{4n^2}}}{1 + \frac{1}{n}z_{1-\frac{\alpha}{2}}^2},\frac{\hat p + \frac{1}{2n}z_{1-\frac{\alpha}{2}}^2 - z_{1-\frac{\alpha}{2}}\sqrt{\frac{\hat p(1-\hat p)}{n}+\frac{z_{1-\frac{\alpha}{2}}^2}{4n^2}}}{1 + \frac{1}{n}z_{1-\frac{\alpha}{2}}^2}]$

其中， $\hat p$ 表示赞成票比例， $n$ 为样本大小， $z_{1-\frac{\alpha}{2}}$ 为表示对应某个置信水平的 $z$ 统计量。威尔逊置信区间的均值为 $\frac{\hat p + \frac{1}{2n}z_{1-\frac{\alpha}{2}}^2}{1 + \frac{1}{n}z_{1-\frac{\alpha}{2}}}$ 。

它的下限值为 $\frac{\hat p + \frac{1}{2n}z_{1-\frac{\alpha}{2}}^2 - z_{1-\frac{\alpha}{2}}\sqrt{\frac{\hat p(1-\hat p)}{n}+\frac{z_{1-\frac{\alpha}{2}}^2}{4n^2}}}{1 + \frac{1}{n}z_{1-\frac{\alpha}{2}}^2}$ 。

由上述公式可见，当投票数量n很大时，下限值和上限值都会收缩，趋向于 $\hat p$ 。

美国社交新闻站点reddit的评论排名，目前使用这种威尔逊区间排序算法。 reddit投票算法

贝叶斯平均法

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

以世界上最大的电影点评网站IMDb为例。IMDb有一个top 250电影排行榜，它是根据用户对每部电影的投票(最低为1分，最高为10分)，计算出每部电影的平均得分。然后，再根据平均得分，排出最受欢迎的前250名的电影。 IMDb top 250

这里就有一个问题：热门电影与冷门电影的平均得分，是否真的可比？举例来说，一部好莱坞大片有10000个观众投票，一部小成本的文艺片只有100个观众投票。这两者的投票结果，怎么比较？如果使用”威尔逊区间”，后者的得分将被大幅拉低，这样处理是否公平，能不能反映它们真正的质量？

一个合理的思路是，如果要比较两部电影的好坏，至少应该请同样多的观众观看和评分。既然文艺片的观众人数偏少，那么应该设法为它增加一些观众。

在top 250榜单的最后，IMDb公布了自己的打分算法：

$加权平均分(weighted \ rank, WR) = \frac{v}{v+m} × R +\frac{m}{v+m}× C$

R = 该电影的用户投票的算数平均得分(Rating)。

v = 该电影的投票人数。

m = 入围top 250榜单的电影的最低投票数，目前是25000。

C = 目前IMDb所有电影的平均得分，目前是7.0。

注意：IMDb在统计投票的时候，只会统计经常投票的用户的票数（regular votes)，并不统计那些不经常投票的用户的投票。

仔细研究这个公式，你会发现，IMDB为每部电影增加了25000张选票，并且这些选票的评分都为7.0。这样做的原因是，假设所有电影都至少有25000张选票，那么就都具备了进入前250名的评选条件；然后假设这25000张选票的评分是所有电影的平均得分（即假设这部电影具有平均水准）；最后，用现有的观众投票进行修正，长期来看， $\frac{v}{v+m}$ 这部分的权重将越来越大，得分将慢慢接近真实情况。

这样做拉近了不同电影之间投票人数的差异，使得投票人数较少的电影也有可能排名前列。

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

贝叶斯平均法有2个缺点： 1. 它假定用户的投票是正态分布，但是事实上，由于人类的情感倾向，投票会呈两级分化状态，即5星和1星多，中间分数少。另外，通常来说，评价成两级分化的产品往往较评价中庸的产品更有价值，比如电影A有10个观众评分，5个为五星，5个为一星；电影B也有10个观众评分，都给了三星。这两部电影的平均得分（无论是算术平均，还是贝叶斯平均）都是三星，但是电影A可能比电影B更值得看。 2. 它简单的认为各评分之间的权重是相等的，但是事实上，由于用户投票不是正态分布，所以5星、4星、3星、2星、1星的权重是不等的。

豆瓣电影的评分方法借鉴了IMDb的打分算法，但是为了和影托做斗争，加进了很多其它因素。具体细节没有公布，我们也无从得知。

豆瓣电影评分方法

贝叶斯平均法的改进——Dirichlet评分法

为了解决贝叶斯平均法存在的两个问题，我们必须抛弃投票的正态分布假设，改用多元分布假设。多元分布模型相比正态分布，能够更直观、精确的反应用户的投票情况，比如，对于豆瓣电影来说，多元分布能够捕捉到有多少用户打了一星，多少用户打了2星。

更一般的，如果我们允许用户评分为 $n$ 档，那么，每一个用户的打分可以格式化为一个 $n$ 维的0-1向量，这样，每一部电影的评分分布实际上为一个多元分布。为了解决小众电影投票过少的问题，我们必须同贝叶斯平均法一样，引入先验分布，事实上，引入先验之后的多元分布就变为了Dirichlet分布。有关Dirichlet分布的相关知识可以参考这篇博文 The Dirichlet Distribution 狄利克雷分布。

Dirichlet评分算法如下：

预估先验分布 $D(\alpha_1,\alpha_2,...,\alpha_n)$ ,可以采用领域知识，也可以直接用全局分布替代;

计算每一产品的多元分布 $M(\beta_1,\beta_2,...,\beta_n)$ ;

用多元分布修正先验分布为 $D(\alpha_1+\beta_1,\alpha_2+\beta_2,...,\alpha_n+\beta_n)$ ;

计算分布 $D(\alpha_1+\beta_1,\alpha_2+\beta_2,...,\alpha_n+\beta_n)$ 的均值为 $(\hat m_1，\hat m_2,...,\hat m_n)$ ;

利用步骤4中得到的均值，采用加权平均的方法求取最终得分。

iVoid's Blog

基于用户投票的打分算法

威尔逊区间法

贝叶斯平均法

贝叶斯平均法的改进——Dirichlet评分法

参考资料