上一篇文章介绍了Reddit的排名算法，今天继续上一篇文章，需要学习的是reddit的评论排名算法。与文章新闻类排名不同的事，评论类的算法可能发表时间没有什么关系。

    目前很多网站采用的评论排名主要有两种，即绝对好评数(好评减去差评)和好评率(好评/总评)。这两种评价方式 都存在很明显的缺陷，以下为事例：

    首先是A与B比较，A的绝对好评数是550-450=100，B的绝对好评数是60-40=20，从绝对好评数比较，A的排名应该在B的前面；A的好评率为550/(450+550)=55%，B的好评率为60/(40+60)=60%，从好评率来说B的排名要比A的排名好。

    再来比较下C与D，从好评率出发，C的好评率为100%，而D的好评率为9/(1+9)=90%，单纯从数据上看D的排名要比C的排名落后。对于评论排名上述的方法是否是我们所需要的呢？这样的计算才能更好的体现评论价值？正确的排名算法应该是怎样的？

    我们先做如下设定：

    如果你熟悉统计学，可能已经看出来了，p服从一种统计分布，叫做“两项分布”(binomial distribution)。

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

    通过上面的分析，我们就可以推断出，如果要给一个评论进行排名，就需要考虑一下内容：

    这样做的原理是，置信区间的宽窄与样本的数量有关。比如，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 提出了一个修正公式，被称为“威尔逊区间”，很好地解决了小样本的准确性问题。Reddit 目前使用的是评论算法就是基于威尔逊得分区间 (Wilson score interval)。具体代码片段可从开放的源代码中找到，将其转化成Python代码后：

from math import sqrt

def _confidence(ups, downs):
    n = ups + downs

    if n == 0:
        return 0

    z = 1.0 #1.0 = 85%, 1.6 = 95%
    phat = float(ups) / n
    return (phat+z*z/(2*n)-z*sqrt((phat*(1-phat)+z*z/(4*n))/n))/(1+z*z/n)

def confidence(ups, downs):
    if ups + downs == 0:
        return 0
    else:
        return _confidence(ups, downs)

    使用到的威尔逊得分区间具体公式如下：

    其中

    参考文章：

    http://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval#Wilson_score_interval

    http://blog.reddit.com/2009/10/reddits-new-comment-sorting-system.html

    http://www.evanmiller.org/how-not-to-sort-by-average-rating.html

建议继续学习：

1. 数学之美：StackOverflow问答排名算法    (阅读：9835)
2. 用skip list实现实时排名?    (阅读：5373)
3. Hacker News 排名算法工作原理    (阅读：5408)
4. IMDB评分排名算法    (阅读：4139)
5. 数学之美：Hacker News的热门排名算法    (阅读：4049)
6. 实时排名，其实很简单    (阅读：3388)
7. Reddit排名算法工作原理    (阅读：2258)
8. 浅谈 WHR 全历史排名    (阅读：1582)
9. 教你如何查询当前主流数据库及其排名？    (阅读：1562)