排名算法

零、好的排名算法

我们去影评类网站(豆瓣，IMDB), 资讯网站(hacker news), 问题问答网站(知乎, stackoverflow), 视频网站(腾讯视频，爱奇艺，优酷)等，如果没有目的性只是想随便逛逛时，常会去看排行榜看有没有感兴趣的内容。
当然有些技术实力的网站会首次给用户展示个性化相关的数据，这个话题后续有时间单独讨论，这里重点讨论下排行榜问题。
当然，这里也不介绍怎么防刷,防作弊,如果要介绍又是另一篇话题了。

对于榜单，根据几个重大特征分为几种不同的榜单。

• 比如按时间维度可以得到最新榜单
• 按访问量(点击量, 播放量等)可以得到最热榜单(可恶的标题党与刷量)
• 按评分可以得到好评榜单(可恶的刷分)。

我处于视频行业，这里就以电影为例了。
一个电影一旦发布，时间就固定了。如果这个时间不固定就存在刷时间的问题。
一个电影发布之后，随着网民的观看就产生了播放量。可能部分电影播放量特别高然后一直占据榜单前面。
一个电影默认是没有分数的，所以这里需要有一个打分入口。然后就存在分数怎么计算的问题。

所以如果我们想要有一个好的排行榜，就需要有一种好的排名算法来客观的达到对于维度排行榜的要求，而不能受其他因素影响。

一、简单粗暴的算法

初级算法实现简单，使用简单一个维度的数据算出一个值，然后按这个值排序即可。
比如最新就按发布时间的时间戳排序,最热就使用总播放量, 好评就是所有用户评分求平均。

这里的缺点也可以看出来(这里先不谈作弊):
由于视频每时每刻都在发布，所以一直在变化，没什么观看价值了，需要适当的考虑播放量权重。
当某个播放量很高时，一直都排在前面了， 随着时间的流逝，top的榜单几乎不变化了。
好评和最热有类似的问题，top榜单不会变化了。

以前Delicious网站有个热门书签排行榜，算法是最近一小时被收藏次数。
一方面没有考虑历史数据，榜单每小时都会有较大的变化。
另一方面没考虑时间因素，很热的书签一直占据前几名。

二、时间干预算法

前面提到的问题其实都是没考虑时间这个因素。
我们需要找到一个时间相关的因子，使得时间越久权重越低，是时间越近，权重越高。

观看常见的公式，发现倒数就是我们需要的公式。

比如这个应用到最热和好评上，就可以避免高访问量和高分的视频一直占着榜单。

Hacker News是个资讯排行榜，用户觉得某个资讯好了可以投一票，这样投票数就形成了一个最热排行榜。
然后Hacker News使用了时间维度干预每个资讯的权重，使得新的资讯有机会曝光。

发现大家介绍Hacker News的排行榜算法时，都会贴他的代码，无非就是lisp语言嘛。

其实这段代码相当简单，转换为数学公式就是下面的式子了。

• P代表投票数，因为发一篇资讯默认自己投了一票，所以需要把自己的减去。其实我认为不减可能更好。
• T代表资讯发布到现在的小时数，为什么需要加上一个数呢？我猜想是因为当时间较短时，分值可能太高。(数值大了曲线下降的很快)
• G是一个重力因子， 一般大于1，这样下面的值就会更大，然后投票的权重更低。

而且这个公式也满足我们的时间干预的需求：时间越旧，权重越低。
通过调整T加的数字和G, 我们还可以调整时间的权重。

三、反对票算法

只有一个维度的排行榜很容易想出简单合理的排名算法，但是对于多个维度的排行榜就比较难了。
比如对于一些问答网站，不但有支持按钮，还有反对按钮。

Reddit社区公布了其算法，我们来看看。

上源码。
其实贴上源码是为了说明算法很重要，有一个好像的算法，核心程序简单几行就搞定了，结果还相当令人满意。
而我作为ACM出身，对算法有种不一样的感情。

这次python代码很多同胞就可以看懂了吧。
赞成票和反对票之差求对数，如果赞成票多就加上时间干预的权重，如果反对票多就减去时间干预的权重.
可以写成一个公式。

这里有个特点：投票之差越大，分值越高。但是当分数越高的时候，分数对最终分的影响越小。
其实这个和倒数一样，是另一个干预权重的好公式: 有效的降低分数的权重。

这里时间因子使用简单的缩小常数倍，其实想要降低时间之间的变化的话，可以引入上面的倒数和log来使时间权重变化的更平滑。

当然这里有一个问题：赞成数和反对数差不多的时候，总分就很低了。
所以这个算法的排名就是赞成数越多的文章越靠前，反对多的和有争议的文章就排后面，也算合理。

四、用户行为

其实对于一个页面，被打开的次数也是一个不错的数据，也可以利用上。
打开了没有观看视频，打开了没有赞成或者反对等都是不错的信息。

Stack Overflow就使用了这三个维度来综合计算分数。

对于Stack Overflow，场景更复杂：问题浏览数，问题的赞成数与反对数，问题回答数量，每个问题的赞成与反对数，问题发布时间，最后一个回答时间等。

这里就不贴代码了，直接上公式。

我们重点关注这个公式是如何对各种因子干预权重的。

对于访问量，一般比较大，所以需要降低对应的权重，这里使用了log干预算法。
对于回答数，可以理解为视频的弹幕数和评论数，而Qscore是赞成数与反对数之差。为什么相乘呢？
需要先看看后面的式子是所有回答得分之和。
那这两个式子合起来就是问题的得分分别加到回答的得分上去，然后再求所有问题的得分之和。
由于大部分用户是只观看不参与互动的，所以这里就不进行降低权重了。
访问量，投票，评论等都算是对这个问题的互动，所以用户任何形式的数据都计算进来就会比较全面了。

另一个因子就是时间了，需要满足越旧分越低，所以使用倒数算法。
不过这里时间维度考虑了最后一次交互，相当于提高了时间的权重。
所以对于时间因子，我们不但要考虑发布时间，还需要考虑用户观看时间，评论时间，投票时间等得出一个综合时间。

这里我们也看出来了，对于排行榜本质上只有两个维度：参与度与时间，然后综合得到分数，也就是对应的质量。

五、时间模型

先看看上面的总结，我们的目的是根据用户的行为，得到当前时刻内的某种质量分数，最后得到一个榜单。

我们先不关心当前分数怎么来，我们把焦点放在分数的变化上。
对于同一个视频，当他已经有一个分数后，后续分数的变化肯定是连续的。
有用户与视频互动了，视频的分数应该对于上升，没有用户与视频互动了，视频的分数应该降低。

于是有人发现这个现象和物体的温度一样，互动升温，放久了降温。

让我们就需要来看看温度变化的公式了。
牛顿老人家早在17世纪就得出了温度变化的公式：物体的冷却速度，与其当前温度与室温之间的温差成正比。

这个公式是递归的，想求出当前温度，依赖与当前温度变化的速率。
这样的方程在数学书叫做微分方程。

• T(t)是温度的时间函数
• H代表目标温度
• α 是一个常数
• T’(t)就是温度变化速率

有了方程，理科男很快就能推导出对应的答案了。

看到这个式子，不知道大家有没有想起我的第一张图片。
这个式子算是倒数算法的优化吧。

于是我们的时间权重就是：

当前得分 = 上一期分数 / ( e^ (系数 x 间隔的小时数) )
注： e^-t = 1/ (e^t)

再来看看第一张图片吧, 就是那个e^-t。

六、新数据

上面一直在使用时间维度来降低旧文章的权重。
但是有时候，对于好评，我们确实需要哪些真正高分的，即使是很旧的片子。

这个时候看看上面的式子，除了log法降低权重外，其他的都是简单的加减乘除来干预权重。
这个对于有用户大量数据的视频来说，计算出来的分数还算准确。
但是对于冷视频，计算偏差就会很大。

用户的行为实际很丰富的，浏览，观看时长比例，评论，点赞，反对票等。
而我们应该想办法利用上这些信息，来降低计算的偏差。

比如拿投票的赞成和反对来说吧,都会使用赞成比当做权重因子。
投赞成票的 比例P 越大，说明这个视频好评的比例越高,应该排在前面。
但是这个赞成比例P 的可靠性取决于投票人数的多少。
如果投票的人太少，这个赞成比就不可靠了。

数学中有一个叫做概率分布的概念。
然后还有一个根据当前人数和赞成比，反推未来赞成分布在某个区间的概率，这里我们使用区间的最低概率。

举个简单的例子。
一个视频A目前有8票赞成，2票反对。B视频有80票赞成，20票反对。则赞成比都是80%.
但是假设投票数达到10W+时，B的赞成比有很大的概率分布在[75%, 85%], 而A的赞成比分布在[70%, 90%].
B的最低概率是75%, 相对于A 70%来说更高，所以B的分数应该比A的分数高。

初中的时候大家都听说过正态分布与正态区间用于解决大样本概率问题，一个老外提出了威尔逊区间用于解决小样本问题。

对于新数据，相应的数据比较少，我们使用概率学来计算一个分数也是一个不错的选择。

七、贝叶斯方法

上面提到的概率方法会有一个问题：冷门电影因为样本小，计算出的的最低概率也会比较小，从而导致冷门电影没机会曝光了。

IMDB 使用了一个贝叶斯平均思想：既然不知道投票结果，那就先估计一个值，然后不断用新的信息修正，使得它越来越接近正确的值。
官方公式如下：

简单的说就是默认给所有电影固定的投票，每个投票都是固定的分数。
这样这个电影就有机会曝光出去了。
当初期真实投票较少时，真实的投票交过对最终投票结果影响很小。
当后面真实投票多了起来时，默认加的固定投票也会多最终结果影响很小。

当然，因为IMDB只是简单的使用了平均算法，所以不能解决分布不均匀问题，再结合上面的概率方法应该可以得到不错的效果。

八、总结

对于用户行为，我们需要综合计算出来，如果数据分布较广，我们需要使用log或者缩小若干倍来降低数据分布区间。
对于时间维度，我们直接除以时间维度即可，有时候为了更平滑，时间维度上可以引入一下不错的公式。
对于冷数据，我们可以使用概率学和预先打默认分来提高排名，避免样本太小而分布不稳定。

排名算法十年前就很成熟了，现在我们可以综合各种算法然后计算出自己的评分，计算出自己的排行榜。

九、参考资料

• 谷文栋先生介绍的Ranking算法
• SEOmoz网站的排序算法全揭秘

---

长按图片关注公众号, 接受最新文章消息.