基于用户投票的排名算法(五):威尔逊区间

标签: IT | 发表时间:2012-03-20 02:49 | 作者:
出处:http://www.ruanyifeng.com/blog/

迄今为止,这个系列都在讨论,如何给出 "某个时段"的排名,比如"过去24小时最热门的文章"。

但是,很多场合需要的是 "所有时段"的排名,比如"最受用户好评的产品"。

这时,时间因素就不需要考虑了。这个系列的最后两篇,就研究不考虑时间因素的情况下,如何给出排名。

一种常见的错误算法是:

  得分 = 赞成票 - 反对票

假定有两个项目,项目A是60张赞成票,40张反对票,项目B是550张赞成票,450张反对票。请问,谁应该排在前面?按照上面的公式,B会排在前面,因为它的得分(550 - 450 = 100)高于A(60 - 40 = 20)。但是实际上,B的好评率只有55%(550 / 1000),而A为60%(60 / 100),所以正确的结果应该是A排在前面。

Urban Dictionary就是这种错误算法的实例。

  

另一种常见的错误算法是

  得分 = 赞成票 / 总票数

如果"总票数"很大,这种算法其实是对的。问题出在如果"总票数"很少,这时就会出错。假定A有2张赞成票、0张反对票,B有100张赞成票、1张反对票。这种算法会使得A排在B前面。这显然错误。

Amazon就是这种错误算法的实例。

  

那么,正确的算法是什么呢?

我们先做如下设定:

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

  (2)用户只有两个选择,要么投赞成票,要么投反对票。

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

如果你熟悉统计学,可能已经看出来了,p服从一种统计分布,叫做 "两项分布"(binomial distribution)。这很重要,下面马上要用到。

我们的思路是,p越大,就代表这个项目的好评比例越高,越应该排在前面。但是,p的可信性,取决于有多少人投票,如果样本太小,p就不可信。好在我们已经知道,p服从"两项分布",因此我们可以计算出p的置信区间。所谓 "置信区间",就是说,以某个概率而言,p会落在的那个区间。比如,某个产品的好评率是80%,但是这个值不一定可信。根据统计学,我们只能说,有95%的把握可以断定,好评率在75%到85%之间,即置信区间是[75%, 85%]。

这样一来,排名算法就比较清晰了:

   第一步,计算每个项目的"好评率"(即赞成票的比例)。

   第二步,计算每个"好评率"的置信区间(以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提出了一个修正公式,被称为 "威尔逊区间",很好地解决了小样本的准确性问题。

  

在上面的公式中, 表示样本的"赞成票比例",n表示样本的大小, 表示对应某个置信水平的z统计量,这是一个常数,可以通过查表或统计软件包得到。一般情况下,在95%的置信水平下,z统计量的值为1.96。

威尔逊置信区间的均值为

  

它的下限值为

  

可以看到,当n的值足够大时,这个下限值会趋向 。如果n非常小(投票人很少),这个下限值会大大小于 。实际上,起到了降低"赞成票比例"的作用,使得该项目的得分变小、排名下降。

Reddit的评论排名,目前就使用这个算法。

  

[参考文献]

  * How Not To Sort By Average Rating

(完)

文档信息

相关 [用户 投票 排名] 推荐:

基于用户投票的排名算法(一):Delicious和Hacker News

- - 阮一峰的网络日志
互联网的出现,意味着"信息大爆炸". 用户担心的,不再是信息太少,而是信息太多. 如何从大量信息之中,快速有效地找出最重要的内容,成了互联网的一大核心问题. 各种各样的排名算法,是目前过滤信息的主要手段之一. 对信息进行排名,意味着将信息按照重要性依次排列,并且及时进行更新. 排列的依据,可以基于信息本身的特征,也可以基于用户的投票,即让用户决定,什么样的信息可以排在第一位.

基于用户投票的排名算法(二):Reddit

- - 阮一峰的网络日志
(不好意思,这个系列中断了近两周,我会尽快在这几天,把后面几篇写完. 上一次,我介绍了 Hacker News的排名算法. 它的特点是用户只能投赞成票,但是很多网站还允许用户投反对票. 就是说,除了好评以外,你还可以给某篇文章差评. Reddit是美国最大的网上社区,它的每个帖子前面都有向上和向下的箭头,分别表示"赞成"和"反对".

基于用户投票的排名算法(三):Stack Overflow

- - 阮一峰的网络日志
上一篇文章,我介绍了 Reddit的排名算法. 它的特点是,用户可以投赞成票,也可以投反对票. 也就是说,除了时间因素以外,只要考虑两个变量就够了. 但是,还有一些特定用途的网站,必须考虑更多的因素. 世界排名第一的程序员问答社区 Stack Overflow,就是这样一个网站. 你在上面提出各种关于编程的问题,等待别人回答.

基于用户投票的排名算法(六):贝叶斯平均

- - 阮一峰的网络日志
(这个系列实在拖得太久,今天是最后一篇. 上一篇介绍了 "威尔逊区间",它解决了投票人数过少、导致结果不可信的问题. 举例来说,如果只有2个人投票,"威尔逊区间"的下限值会将赞成票的比例大幅拉低. 这样做固然保证了排名的可信性,但也带来了另一个问题:排行榜前列总是那些票数最多的项目,新项目或者冷门的项目,很难有出头机会,排名可能会长期靠后.

基于用户投票的排名算法(四):牛顿冷却定律

- - 阮一峰的网络日志
这个系列的前三篇,介绍了 Hacker News, Reddit和 Stack Overflow的排名算法. 今天,讨论一个更一般的数学模型. 这个系列的每篇文章,都是可以分开读的. 但是,为了保证所有人都在同一页上,我再说一下,到目前为止, 我们用不同方法,企图解决的都是同一个问题:根据用户的投票,决定最近一段时间内的"热文排名".

基于用户投票的排名算法(五):威尔逊区间

- - 阮一峰的网络日志
迄今为止,这个系列都在讨论,如何给出 "某个时段"的排名,比如"过去24小时最热门的文章". 但是,很多场合需要的是 "所有时段"的排名,比如"最受用户好评的产品". 这时,时间因素就不需要考虑了. 这个系列的最后两篇,就研究不考虑时间因素的情况下,如何给出排名.   得分 = 赞成票 - 反对票.

Apache投票接受OpenOffice.org

- 灰灰 - Solidot
甲骨文已宣布将开源办公软件项目OpenOffice.org捐赠给Apache基金会. 6月13日,Apache基金会进行了投票表决,以压倒性多数同意接受OpenOffice.org成为Apache的一个孵化器项目. OpenOffice.org将转交给Apache基金会管理,它可能需要数个月时间才能变成Apache的新顶级项目.

投票的过程好…

- 俊超 - 爱胡扯
投票的过程好…太能创意了吧,这也行.

ChinaMode2010评选活动投票入围公司及投票

- scaoen - 天涯海阁-Web2.0Share
之前我总结了我今年在博客介绍的2010年优秀初创企业,颇受欢迎. 而最近由我们Chinamode组织的由用户来提名和专家评审来评审的评选活动经过3周时间,目前已经评选出第二阶段投票阶段的入围公司,现汇总如下,其中不乏一些非常优秀的互联网/移动互联网初创企业,大家可以到Chinamode首页进行投票选择每个类别您最喜欢的公司.

世界黑客排名

- 2楼水饺 - 煎蛋
黑客世界也有这自己的排名,如果你打算雇佣牛逼黑客做点xxxx事情,不妨看看这个网站 RankMyHack.com ,它号称是世界上第一个黑客排名系统. 除了能够收集到一些黑客战绩和信息之外,RankMyHack.com 还开放给任何一个想加入该排名的盆友. 提交你的战绩,然后将RankMyHack 给出的一段代码插入到你所黑掉的网站予以证明.