专栏首页小七的各种胡思乱想打分排序系统漫谈1 - 时间衰减

打分排序系统漫谈1 - 时间衰减

打分排序系统的应用非常普遍,比如电影的评分,知乎帖子的热度,和新闻文章的排序。让我们从最简单直观的平均打分开始, 聊聊各种打分方法的利弊和使用场景。

最简单的打分方法当然是一段时间的点赞量综述。显而易见的缺点就是越老的帖子容易拿到更多的赞而长期霸榜,HN用了一种简单的时间方法来考虑时间衰减。

Hacker News Algo - 只有点赞

\[ \begin{align} score & = \frac{(v-1)}{(t+2)^G} * pen \\ where & v-1 剔除只有一个用户点赞的情况 \\ & t+2 保证除数永远大于1 \\ & G:衡量打分随时间的衰减程度 \\ &pen: 争议,过短,没有跳转的文章打分会打折\\ \end{align} \]

def hacker_news_ranking(votes, item_age, gravity = 1.8, penalties):
    score = (votes-1)/(item_age +2)**gravity * penalties 
    return score 

Hacker News 的打分方式,主要考虑到了时间衰减。保证老的新闻不会因为累计更多的点赞而始终在排在前面。并且点赞数和帖子新旧程度的权衡可以通过G的大小来调整。但仍然有几个未解问题:

  1. 时间衰减过快,对于一些有长实效性的打分并不适用。能否在打分上加入指数?
  2. 如何考虑时间衰减和当前时段的关系。不同时段浏览量不同,如果一篇很好的文章在凌晨发布,因为当时浏览量低,文章可能永远没有置顶机会。能否对时间进行加权?
  3. 没有考虑到点赞量和文章热度的非线性关系。简单说就是点赞量可以接近无限大,但文章热度是有限的。能否对打分进行非线性压缩?
  4. 不同类型文章热度是否可比,例如有的文章质量高但是相对小众。能否做组内排序?或者用点赞率来衡量
  5. 同理也应该考虑到浏览量(PV)和点赞量的关系。点赞率高的应该考虑排在前面,但同样浏览量过小的点赞率也要考虑置信度的问题

Reddit Hot Formula - 包括点赞和拍砖

同时考虑点赞和拍砖,Reddit 的 Hot Formula采用了和Hacker News相似的打分方式,来推荐优质高热度的文章。并针对上述问题(1)和(3)给出了不同的处理。公式如下: \[ \begin{align} score & = up - down \\ score_{adj} & = \log_{10}{(max(score,1))}\\ sign &= \begin{cases} 1 & if score > 0 \\ 0 & if score = 0 \\ -1& if score <0 \\ \end{cases}\\ score &= score_{adj} * sign + \frac{seconds}{45000} \\ where \, seconds & =发帖时间 - 2015年12月8日 \end{align} \] 和Hacker News相比, Reddt Hot Formula有几个不同点:

  • 用取Log的方式解决了上述提出的第三个问题就是文章热度和点赞量之间的非线性关系,文章热度不会随着点赞量的增加无限线性增长。而压缩的强度可以通过改变log的底数来调整,底数越大点赞量对文章的影响
  • 处理时间递减上,Hot Formula采用了线性递减处理。新的帖子因为距历史时点更远会拿到更高的时间加分项\(\frac{seconds}{45000}\)。和上述指数衰减相比,线性不会过度惩罚老文章。

思考:时间衰减

比较Hacker News,和Reddit Hot Formula, 主要的两点区别在于对点赞量(拍砖)取log进行压缩,以及不同的时间衰减项。 log运算单调所以如果只用排序不用分数的话并不会对最终排序产生影响,所以让我们再来深入讨论一下时间衰减项的选取。

简单来说时间衰减的意义就是为了让新老文章的热度具有可比性,否则老的帖子会因为在更长的时间累计了更多的帖子而始终置顶。一种直观的解决办法就是给老的帖子增加时间惩罚项。几种常见的时间衰减项包括:

  • 线性衰减 \[ score_t = score_0 - T/G \]
  • 幂指数衰减 \[ score_t = score_0 / (T + 2)^G \] 幂指数衰减的衰减速度会随着时间加速,加速时间惩罚项对打分的影响。如果觉得幂指数的表达形式不够直观,我们可以对等式左右取个对数,会发现对数打分的变化是对数时间的线性函数,可以用这个方式来判断幂指数打分是否适用,如下: \[ log(score_t) = log(score_0) - G * log(T+2) \]
  • 指数衰减 \[ score_t = score_0 * exp( - \lambda * T ) \] 指数衰减可以由牛顿冷却定律的一阶微分方程得到,\(\lambda\)是衰减速率,速率恒定,经过t时间衰减的量和N当前的值正相关

\[ \frac{dN(t)}{dt} = - \lambda N(t) \\ \frac{dN(t)}{N(t)} = -\lambda dt \\ log(\frac{N(t)}{N_0}) = - \lambda t \\ \] 也可以从指数分布的角度来理解,\(N_0\)是集合初始的元素数量,其中每个元素都在衰减,在t时刻依旧存在的元素数量期望是\(N(t)\)。元素的生命长度符合指数分布:

\[ f(t) \sim \lambda e^{-\lambda t} \\ P(x>t) = 1 - F(x<t) = e^{-\lambda t } \\ N(t) = N_0 * P(x>t) \]

下一节我们接着就上述提出的几个问题中还没有解决的如何综合考虑浏览量和点赞量来打分的问题进行讨论。 要是您感兴趣请戳下方

https://www.cnblogs.com/gogoSandy/p/10358961.html

To be Continue.


Reference

  1. http://www.evanmiller.org/rank-hotness-with-newtons-law-of-cooling.html
  2. http://www.ruanyifeng.com/blog/2012/02/ranking_algorithm_hacker_news.html
  3. https://medium.com/hacking-and-gonzo/how-reddit-ranking-algorithms-work-ef111e33d0d9

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • AB实验的高端玩法系列3 - AB组不随机?观测试验?Propensity Score

    都说随机是AB实验的核心,为什么随机这么重要呢?有人说因为随机所以AB组整体不存在差异,这样才能准确估计实验效果(ATE)

    风雨中的小七
  • AB实验人群定向HTE模型4 - Double Machine Learning

    Hetergeneous Treatment Effect旨在量化实验对不同人群的差异影响,进而通过人群定向/数值策略的方式进行差异化实验,或者对实验进行调整。...

    风雨中的小七
  • 无所不能的Embedding5 - skip-thought的兄弟们[Trim/CNN-LSTM/quick-thought]

    这一章我们来聊聊skip-thought的三兄弟,它们在解决skip-thought遗留问题上做出了不同的尝试【Ref1~4】, 以下paper可能没有给出最优...

    风雨中的小七
  • MySQL 从零开始:07 数据搜索与搜索

    数据库表中包含了很多数据,一般我们不会检索表中的所有行。通常会根据特定的条件来提取出表的子集,此时我们需要指定搜索条件(search criteria),搜索条...

    王强
  • 不用SQL,也可以实现数据集的合并和连接

    数据(集)处理是数据分析过程中的重要环节,今天特别整理数据(集)合并、增减与连接的相关内容,并逐一作出示例。

    1480
  • R语言 数据(集)合并与连接/匹配 | 专题2

    数据(集)处理是数据分析过程中的重要环节,今天特别整理数据(集)合并、增减与连接的相关内容,并逐一作出示例。

    拴小林
  • 小学生SQL50题

    已知有如下4张表: 学生表: student(s_id,s_name,s_birth,s_sex) –学生编号,学生姓名, 出生年月,学生性别 课程表: cou...

    大数据真好玩
  • SQL 求平均值时去掉极值

    在一些比赛中,为了公平起见,算法端会在评委给出的分数里面去掉一个最高分和一个最低分,再求平均分,平均分即是选手的最后得分。

    白日梦想家
  • 大数据-Hive查询语法

    因此,如果分桶和sort字段是同一个时,此时, cluster by = distribute by + sort by 分桶表的作用:最大的作用是用来提高j...

    cwl_java
  • Hive快速入门系列(10) | Hive的查询语法

    注: 1、order by 会对输入做全局排序,因此只有一个reducer,会导致当输入规模较大时,需要较长的计算时间。 2、sort by不是全局排序,其...

    不温卜火

扫码关注云+社区

领取腾讯云代金券