【算法笔记】基于用户投票的排序算法

这是一篇拖了很久的文章，其实很早之前便想把它写出来，但无奈只能拖到了现在。希望现在趁着还有些闲心，可以把以前记录过的坑全给填齐了。

基于用户投票的排序算法十分多样，不同社交平台的机制（点赞，点踩，热度等）会基于不同变量的排序算法。为了保证算法的普遍适用性，文章仅对一般的基于用户投票的算法模型进行介绍，全文使用“主题”作为排序的元素。

牛顿冷却算法

这是一个常用的基于时间和投票的排序算法，使用了指数式衰减的牛顿冷却公式为基础。其最为直观的结果就是投票高且时间较近的主题的排名会更为靠前，然后随着时间的增加，该主题便会“冷却”，排名逐渐降低。

公式如下：

$$T’(t)=-\alpha(T(t)-H)$$

$T(t)$：温度 $T$ 的时间 $t$ 的函数
$T’(t)$：温度 $T$ 的时间 $t$ 的导数
$H$ 代表室温，$T(t)-H$ 就是当前温度与室温之间的温差
常数 $\alpha(\alpha>0)$：室温与降温速率之间的比例关系，不同的物质有不同的 $\alpha$ 值。

基于这样的式子，我们可以进一步将其化简，得出我们最终在排序算法中所使用的式子：

$$T=T_0e^{-\alpha(t-t_0)}$$

$T$ 和 $t$：当前时刻的温度和时间
$T_0$ 和 $t_0$：之前的某一时刻的温度和时间
$\alpha$ ：冷却系数，一般根据需求计算得出，且 $\alpha$ 越大，同一时间衰减的速度越快

可以看出，牛顿冷却算法在需要考虑时间和票数两种因素的情况下，可以做一个很好的权衡。

威尔逊区间

因为“牛顿冷却算法”的指数衰减特性，其只适用于一段时间内的排序，而“威尔逊区间” 则适用于对整体的主题进行排序。

为什么需要“威尔逊区间”算法来进行排序呢，直接赞的数量减去踩的数量不好吗？这就涉及到样本空间的问题了。

假设现在有两个主题，一个有 500 赞和 450 踩，另一个有 60 赞和 0 踩，那么按照直观的解法 $60 - 0 > 500 - 450$，第二个放在了前面。实际上这样并不合理，因为明显第一个主题的讨论更高，这便意味着该主题的权重应该更高，更具有代表性，所以理应让第一个主题排序靠前。同理，$Score=\frac{赞成票}{总票数}$ 在有很多小样本的情况下也十分不准确。

基于这样的想法，有了下面这个~~太长不看的~~公式：

$$\frac{\bar{p}+\frac{1}{2n}z_{1-\frac{\alpha}{2}}^2\pm z_{1-\frac{\alpha}{2}}\sqrt{\frac{\bar{p}(1-\bar{p})}{n}+\frac{z_{1-\frac{\alpha}{2}}^2}{4n^2}}}{1+\frac{1}{n}z_{1-\frac{\alpha}{2}}^2}$$

$\bar{p}$：赞成票比例
$n$：样本大小
$z_{1-\frac{\alpha}{2}}$：对应某个置信水平的 $z$ 统计量（参考概率论）

通过式子我们可以看出，最大值为 $\frac{\bar{p}+\frac{1}{2n}z_{1-\frac{\alpha}{2}}^2+z_{1-\frac{\alpha}{2}}\sqrt{\frac{\bar{p}(1-\bar{p})}{n}+\frac{z_{1-\frac{\alpha}{2}}^2}{4n^2}}}{1+\frac{1}{n}z_{1-\frac{\alpha}{2}}^2}$，最小值为 $\frac{\bar{p}+\frac{1}{2n}z_{1-\frac{\alpha}{2}}^2-z_{1-\frac{\alpha}{2}}\sqrt{\frac{\bar{p}(1-\bar{p})}{n}+\frac{z_{1-\frac{\alpha}{2}}^2}{4n^2}}}{1+\frac{1}{n}z_{1-\frac{\alpha}{2}}^2}$（就是取了个正负号）。当 n 足够大时，最小值便会趋向于 $\bar{p}$，反之在样本量小时，该值便会远远小于 $\bar{p}$。这就达到了样本量大的权重更高这一要求。

在之前参加的数模美赛中，我曾经使用过威尔逊算法来进行排名计算每一项数据的总体分数用于排序，代码如下：

def wilson_score(pos, total, p_z=2.):
    if total == 0:
        total = 1
    pos_rat = pos * 1. / total * 1.  # 正例比率
    score = (pos_rat + (np.square(p_z) / (2. * total))
             - ((p_z / (2. * total)) * np.sqrt(4. * total * (1. - pos_rat) * pos_rat + np.square(p_z)))) / \
            (1. + np.square(p_z) / total)
    return score

贝叶斯平均

威尔逊区间算法的特性决定了其只能够在主题、商品和热度排序中有着准确的排序顺序，在电影评分这类不同电影的观众数量之间方差极大的方面就表现不佳了——文艺片看的人少，难道其质量就一定差吗？

所以贝叶斯平均算法应运而生，其借鉴了“贝叶斯推断”思想——不知道投票结果的情况下先估计一个值，然后使用新的信息修正以接近正确的值。

公式如下：

$$\bar{x}=\frac{C\times m+\sum^n_{i=1}x_i}{n+C}$$

$C$：投票人数扩展的规模，根据网站总体的用户量而定
$n$：该项目的现有投票人数
$x$：该项目的每张选票的值
$m$：总体的算数平均值

该算法也存在不足之处，在于它会预先假设用户的投票属于正态分布。

【算法笔记】基于用户投票的排序算法.

牛顿冷却算法

威尔逊区间

贝叶斯平均