SegmentFault 热门内容优化

之前 SegmentFault 的热门内容算法没有考虑到时间因素,导致热门内容更新较慢,新的热门内容排不上位,所以最近对这块做了一些改动,主要参考了阮一峰老师的关于网站热门内容排序的一系列博客:

这几篇文章对于网站热门内容的计算研究有很好的指导作用,非常值得拜读。

言归正传,来说说 SegmentFault 的热门算法。

热门文章

对于热门文章,使用了如下公式:

其中

  • views:浏览量,对浏览量做了一次去对数处理,主要是为了防止某些浏览量较大的文章异军突起,待在榜单迟迟不动。
  • recommendScore / collectScore:文章的推荐数和收藏数,直接加和到分子中,作为文章热门程度的考虑因素。
  • articleComments:文章评论数,这个也作为一个影响文章热度的因素,不过为了降低其影响,对其作了一次取对数操作,主要是考虑到评论数量的影响力并没有上面两个的高。
  • (age/2 + update/2 + 1) ^ i:分母是对时间因子的考虑,宏观上来看,就是文章热度和创建时间成反比。细节上,做成了个指数函数,可以通过对 i 变量的调控来改变时间因子在对热度的影响。
    • age:内容发布时间
    • update:内容最后更新时间(所有时间值单位均为 h/3600)
    • i:重力因子,取值的大小会直接决定热门排序(后面将介绍这点)

热门问答

对于热门问答,使用了如下公式:

热门问答的计算参考了 Stack Overflow 对于回答数量和问题得票数的处理。同时,结合我们的实际,将评论的得票数也做为一个因素加入计算。

  • Qanswers / Qscore:分别是问题的答案数量和问题的得票数
  • anwserScores / commentSocres:分别是该问题下所有答案的总得票数和所有评论的总得票数
  • update:该问题下答案的最新更新时间

其余的变量含义和文章算法相同。

日/周/月热门如何区别?

首先要明确各类不同热门内容的目的。

  • 日热门的主要目的就是突出最近一天内的热门内容,更方便于内容被大家看到,文章快速地形成讨论、受关注的问题尽快得到解决;
  • 周热门的主要目的很明确,就是突出过去一周内的热门内容,同时,给新产生的优秀内容机会,让其有机会进入热门列表;
  • 月热门同周热门目的一样,但更需要给新内容进入列表的机会,以让内容经常更新。

所以,该怎么做呢?

对于同一内容,上面的计算公式均可化简为

可以看出,其热度和创建时间成反比,那么这个反比的值最终就由重力因子 i 来影响。

日热门为了突出新热内容、过滤时间过久的热门内容,需要增大重力因子,尽可能排除 24 小时之外的热门内容;周热门和月热门则需要按时间要求依次逐渐降小 i 值。

关于指数 i 值的选定,采取了估算:绘制出一定范围内时间和文章热度的指数函数的图,然后根据需求挑选满足自己条件的指数值。如下图

多次估值测试,最终分别将日、周、月的 i 值选取为 1.0、0.5、0.3。

总结

开始修改热门算法的时候,并没有收到计算周热门、月热门的需求,所以直接很暴力的将时间因子加入进去,这样的确能够满足需求,可以保证热门的内容随着时间的推移保持更新,而不会出现之前的某几篇文章的热度一直保持恒定,稳居榜首。

后来需要计算区间内的热门内容时,仍然使用开始的方案,因为时间因子的关系,会导致区间内的热门内容受时间的影响太大,出现的问题就是周热门、月热门榜首的内容依然是最新产生的内容占比重较多,所以才考虑对分母的时间因子做了动态调节的方案,也就是将分母的指数根据计算不同的区间,给出不同的值(但未找到更合适的取值方法,只能多次估值)。

我们目前的算法仍有需要完善之处,重力因子 i 的取值依旧是难点,大家如果有更好的方法,欢迎讨论。

转载:https://segmentfault.com/a/1190000004253816

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

上一篇介绍了“威尔逊区间”,它解决了投票人数过少、导致结果不可信的问题。

举例来说,如果只有2个人投票,”威尔逊区间”的下限值会将赞成票的比例大幅拉低。这样做固然保证了排名的可信性,但也带来了另一个问题:排行榜前列总是那些票数最多的项目,新项目或者冷门的项目,很难有出头机会,排名可能会长期靠后。

IMDB为例,它是世界最大的电影数据库,观众可以对每部电影投票,最低为1分,最高为10分。

系统根据投票结果,计算出每部电影的平均得分。然后,再根据平均得分,排出最受欢迎的前250名的电影。

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

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

排名页面的底部,IMDB给出了它的计算方法。

  

– WR, 加权得分(weighted rating)。
– R,该电影的用户投票的平均得分(Rating)。
– v,该电影的投票人数(votes)。
– m,排名前250名的电影的最低投票数(现在为3000)。
– C, 所有电影的平均得分(现在为6.9)。

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

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

把这个公式写成更一般的形式:

  

– C,投票人数扩展的规模,是一个自行设定的常数,与整个网站的总体用户人数有关,可以等于每个项目的平均投票数。
– n,该项目的现有投票人数。
– x,该项目的每张选票的值。
– m,总体平均分,即整个网站所有选票的算术平均值。

这种算法被称为“贝叶斯平均”(Bayesian average)。因为某种程度上,它借鉴了“贝叶斯推断”(Bayesian inference)的思想:既然不知道投票结果,那就先估计一个值,然后不断用新的信息修正,使得它越来越接近正确的值。

在这个公式中,m(总体平均分)是”先验概率”,每一次新的投票都是一个调整因子,使总体平均分不断向该项目的真实投票结果靠近。投票人数越多,该项目的”贝叶斯平均”就越接近算术平均,对排名的影响就越小。

因此,这种方法可以给一些投票人数较少的项目,以相对公平的排名。

=================================================

“贝叶斯平均”也有缺点,主要问题是它假设用户的投票是正态分布。比如,电影A有10个观众评分,5个为五星,5个为一星;电影B也有10个观众评分,都给了三星。这两部电影的平均得分(无论是算术平均,还是贝叶斯平均)都是三星,但是电影A可能比电影B更值得看。

解决这个问题的思路是,假定每个用户的投票都是独立事件,每次投票只有n个选项可以选择,那么这就服从“多项分布”(Multinomial distribution),就可以结合贝叶斯定理,估计该分布的期望值。由于这涉及复杂的统计学知识,这里就不深入了,感兴趣的朋友可以继续阅读William Morgan的How to rank products based on user input

转载:http://www.ruanyifeng.com/blog/2012/03/ranking_algorithm_bayesian_average.html