寻找优秀的问题排序算法

Viewed 11478

目前segmentfault使用的热门排序算法是根据reddit算法修改而来的,他的具体细节如下

reddit算法

这个算法的好处在于

  1. 时间值被固定了,不需要像其他算法一样每次排序都要计算一次时间因子,它的分值是固定的,只需要在每次写入时计算一遍就行了
  2. 可以快速聚合最新最热的事件

但我们使用了一段时间后,发现它也有一个明显的缺点

这是一个新闻热点排序的算法,不适用于问答网站。它的时间影响太大,比如现在一个月内的排序,排在前面的往往是最新发布的问题,而真正评分和回答数多的问题都往后靠了,而后者才是我们希望排在前面的问题。

因此我们需要一个如下要求的算法

  1. 一次计算,不需要每次排序都实时计算,排序因子是一个固定值
  2. 时间影响在刚开始发布时影响较大,但当过了一段时间后就逐渐变小
  3. 主要的影响因子是问题评分和问题回答数

需求要明确,定义“刚开始发布”和“过了一段时间”的界限

1. 一次计算,不需要每次排序都实时计算,排序因子是一个固定值 这个是什么意思?你每次点up, down的时候,难道不重新计算?

图挂了。

8 Answers

需求2决定时间因数的计算应该是类似指数衰减的过程,每次都需要计算,跟需求1矛盾,reddit为了避免每次计算使用是线性化的办法。
“这是一个新闻热点排序的算法,不适用于问答网站。”这句其实不对,你可以根据情况加大那个45000以削减时间的因素。我认为正确的做法应该是根据目前社区的活跃度动态调整。

也可以在时间上加点变化:
时间因数=( T(问题创建时的Unix纪元)-修正值 )/因数M
修正值决定基础值,因数决定斜率。

投票这个按之前的就好,回答数也许没必要加(见下文)。
logZ的那个因为不是原点对称,所以我不喜欢。我的方案是log(U-D+1)

最重要的还是这两部分的平衡,主调M,可以试试在Excel里比划比划。

回答数的问题:
若回答数为N,N越大越倾向于提前?不见得吧,对于没有回答的问题没有照顾吗?回答少的问题就没意义吗?因为容易所以获得很多回答的问题就有意义吗?所以我倾向于让N见鬼去吧。

PS:编辑器的问题,把转义的热键绑定成Ctrl+C有点反人类了吧。

ctrl+c确实有问题,我调整一下

总觉得1和2看起来似乎是矛盾的。
如果不把现在的时间加入考量,让这个时间影响在过了一段时间后逐渐变小,我想不出怎么做到这一点;更何况期望排序因子是一个固定值,又怎么逐渐改变呢。

我也觉得1和2似乎矛盾

@R2D2 它们是不矛盾的,仔细看这个算法的注释,你会发现它不是以现在的时间作为基准的,而是以一个固定的时间,比如你的开站时间。这样时间的影响就是一个固定值了

@joyqi 是啊,时间影响是一个固定值,但为什么还要求它逐渐变小呢?

没有太好的点子,给点建议:

1、这个不太好吧?
2、可以参考decaying window,满足条件且计算量非常小;
3、影响因子作为参数需要慢慢调,写个反馈或自适应框架也行。

让时间因素衰减不可能,因为衰减就要重新计算,但是可以让新近的排序因子中的时间因素增长。
不过这样有个问题,排序因子的绝对值会暴增,可能很快就增长到一个不可控的水平。
所以,可以考虑延时计算,比如每天重新计算一次,在这里做时间因素的衰减。

1、以问题评分、问题回答数、领袖用户参与度、问题页PV(需要排除首页推荐的噪声)作为排序的基本位置
2、以固定次数(从新到旧,如最近100次)的用户反馈行为作为(评分、评论等产生内容的行为)作为排序调权,用来替代按时间衰减,有反馈才计算

我说说我之前的应用方法,我之前用python写了一个类reddit的行业信息推荐网站
在排序方面我没做那么复杂,实施方法如下:
1、topic表会建一个叫Sort的字段,用来做排序
2、当发布topic的时候Sort内容为int型int(time.time())
3、当被up的时候将该topic的Sort+x
4、当被down的时候将该topic的Sort-x
5、检索时直接按Sort从大到小排序

x的数值取决于时间对排序的影响和网站的活跃程度

针对提出的几点需求:
1.一次计算,不需要每次排序都实时计算,排序因子是一个固定值
2.时间影响在刚开始发布时影响较大,但当过了一段时间后就逐渐变小
3.主要的影响因子是问题评分和问题回答数

1和2确实有些矛盾,如果要把时间动态性考虑进去的话,每次排序都需要进行一次计算。或者可以把时间给分段,每一段用一个固定的时间因子。
其实你们的想法是想找出真正热门的问题。去年我们这针对Stack Overflow的数据集做过一些挖掘,通过提取问题和答案的features验证了问题的质量和答案的质量基本是正相关的(用真实的up vote和down vote来做ground truth)。你们可以试试看用DM的方法来事先预测问题的质量好坏,用于热门问题的排序。

= =。突然发现我是在挖坟了。。就纯当技术讨论。

Hacker News的算法

Score = (P-1) / (T+2)^G

where,
P = points of an item (and -1 is to negate submitters vote)
T = time since submission (in hours)
G = Gravity, defaults to 1.8 in news.arc