2012年3月7日星期三

阮一峰的网络日志

阮一峰的网络日志

基于用户投票的排名算法（二）：Reddit

Posted: 07 Mar 2012 12:24 AM PST

（不好意思，这个系列中断了近两周，我会尽快在这几天，把后面几篇写完。）

上一次，我介绍了Hacker News的排名算法。它的特点是用户只能投赞成票，但是很多网站还允许用户投反对票。就是说，除了好评以外，你还可以给某篇文章差评。

Reddit是美国最大的网上社区，它的每个帖子前面都有向上和向下的箭头，分别表示"赞成"和"反对"。用户点击进行投票，Reddit根据投票结果，计算出最新的"热点文章排行榜"。

怎样才能将赞成票和反对票结合起来，计算出一段时间内最受欢迎的文章呢？如果文章A有100张赞成票、5张反对票，文章B有1000张赞成票、950张反对票，谁应该排在前面呢？

Reddit的程序是开源的，使用Python语言编写。排名算法的代码大致如下：

这段代码考虑了这样几个因素：

（1）帖子的新旧程度t

　　t = 发贴时间 - 2005年12月8日7:46:43

t的单位为秒，用unix时间戳计算。不难看出，一旦帖子发表，t就是固定值，不会随时间改变，而且帖子越新，t值越大。至于2005年12月8日，应该是Reddit成立的时间。

（2）赞成票与反对票的差x

　　x = 赞成票 - 反对票

（3）投票方向y

　　

y是一个符号变量，表示对文章的总体看法。如果赞成票居多，y就是+1；如果反对票居多，y就是-1；如果赞成票和反对票相等，y就是0。

（4）帖子的受肯定（否定）的程度z

　　

z表示赞成票与反对票之间差额的绝对值。如果对某个帖子的评价，越是一边倒，z就越大。如果赞成票等于反对票，z就等于1。

结合以上几个变量，Reddit的最终得分计算公式如下：

　　

这个公式可以分成两个部分来讨论：

（一）

　　

这个部分表示，赞成票与反对票的差额z越大，得分越高。

需要注意的是，这里用的是以10为底的对数，意味着z=10可以得到1分，z=100可以得到2分。也就是说，前10个投票人与后90个投票人（乃至再后面900个投票人）的权重是一样的，即如果一个帖子特别受到欢迎，那么越到后面投赞成票，对得分越不会产生影响。

当赞成票等于反对票，z=1，因此这个部分等于0，也就是不产生得分。

（二）

　　

这个部分表示，t越大，得分越高，即新帖子的得分会高于老帖子。它起到自动将老帖子的排名往下拉的作用。

分母的45000秒，等于12.5个小时，也就是说，后一天的帖子会比前一天的帖子多得2分。结合前一部分，可以得到结论，如果前一天的帖子在第二天还想保持原先的排名，在这一天里面，它的z值必须增加100倍（净赞成票增加100倍）。

y的作用是产生加分或减分。当赞成票超过反对票时，这一部分为正，起到加分作用；当赞成票少于反对票时，这一部分为负，起到减分作用；当两者相等，这一部分为0。这就保证了得到大量净赞成票的文章，会排在前列；赞成票与反对票接近或相等的文章，会排在后面；得到净反对票的文章，会排在最后（因为得分是负值）。

（三）

这种算法的一个问题是，对于那些有争议的文章（赞成票和反对票非常接近），它们不可能排到前列。假定同一时间有两个帖子发表，文章A有1张赞成票（发帖人投的）、0张反对票，文章B有1000张赞成票、1000张反对票，那么A的排名会高于B，这显然不合理。

结论就是，Reddit的排名，基本上由发帖时间决定，超级受欢迎的文章会排在最前面，一般性受欢迎的文章、有争议的文章都不会很靠前。这决定了Reddit是一个符合大众口味的社区，不是一个很激进、可以展示少数派想法的地方。

[参考资料]

　　* How Reddit ranking algorithms work

（完）

文档信息
发帖者 时间：

阮一峰的网络日志

阮一峰的网络日志

基于用户投票的排名算法（二）：Reddit

Posted: 07 Mar 2012 12:24 AM PST

（不好意思，这个系列中断了近两周，我会尽快在这几天，把后面几篇写完。）

上一次，我介绍了Hacker News的排名算法。它的特点是用户只能投赞成票，但是很多网站还允许用户投反对票。就是说，除了好评以外，你还可以给某篇文章差评。

Reddit是美国最大的网上社区，它的每个帖子前面都有向上和向下的箭头，分别表示"赞成"和"反对"。用户点击进行投票，Reddit根据投票结果，计算出最新的"热点文章排行榜"。

怎样才能将赞成票和反对票结合起来，计算出一段时间内最受欢迎的文章呢？如果文章A有100张赞成票、5张反对票，文章B有1000张赞成票、950张反对票，谁应该排在前面呢？

Reddit的程序是开源的，使用Python语言编写。排名算法的代码大致如下：

这段代码考虑了这样几个因素：

（1）帖子的新旧程度t

　　t = 发贴时间 - 2005年12月8日7:46:43

t的单位为秒，用unix时间戳计算。不难看出，一旦帖子发表，t就是固定值，不会随时间改变，而且帖子越新，t值越大。至于2005年12月8日，应该是Reddit成立的时间。

（2）赞成票与反对票的差x

　　x = 赞成票 - 反对票

（3）投票方向y

　　

y是一个符号变量，表示对文章的总体看法。如果赞成票居多，y就是+1；如果反对票居多，y就是-1；如果赞成票和反对票相等，y就是0。

（4）帖子的受肯定（否定）的程度z

　　

z表示赞成票与反对票之间差额的绝对值。如果对某个帖子的评价，越是一边倒，z就越大。如果赞成票等于反对票，z就等于1。

结合以上几个变量，Reddit的最终得分计算公式如下：

　　

这个公式可以分成两个部分来讨论：

（一）

　　

这个部分表示，赞成票与反对票的差额z越大，得分越高。

需要注意的是，这里用的是以10为底的对数，意味着z=10可以得到1分，z=100可以得到2分。也就是说，前10个投票人与后90个投票人（乃至再后面900个投票人）的权重是一样的，即如果一个帖子特别受到欢迎，那么越到后面投赞成票，对得分越不会产生影响。

当赞成票等于反对票，z=1，因此这个部分等于0，也就是不产生得分。

（二）

　　

这个部分表示，t越大，得分越高，即新帖子的得分会高于老帖子。它起到自动将老帖子的排名往下拉的作用。

分母的45000秒，等于12.5个小时，也就是说，后一天的帖子会比前一天的帖子多得2分。结合前一部分，可以得到结论，如果前一天的帖子在第二天还想保持原先的排名，在这一天里面，它的z值必须增加100倍（净赞成票增加100倍）。

y的作用是产生加分或减分。当赞成票超过反对票时，这一部分为正，起到加分作用；当赞成票少于反对票时，这一部分为负，起到减分作用；当两者相等，这一部分为0。这就保证了得到大量净赞成票的文章，会排在前列；赞成票与反对票接近或相等的文章，会排在后面；得到净反对票的文章，会排在最后（因为得分是负值）。

（三）

这种算法的一个问题是，对于那些有争议的文章（赞成票和反对票非常接近），它们不可能排到前列。假定同一时间有两个帖子发表，文章A有1张赞成票（发帖人投的）、0张反对票，文章B有1000张赞成票、1000张反对票，那么A的排名会高于B，这显然不合理。

结论就是，Reddit的排名，基本上由发帖时间决定，超级受欢迎的文章会排在最前面，一般性受欢迎的文章、有争议的文章都不会很靠前。这决定了Reddit是一个符合大众口味的社区，不是一个很激进、可以展示少数派想法的地方。

[参考资料]

　　* How Reddit ranking algorithms work

（完）

文档信息
发帖者 时间：

2012年2月25日星期六

阮一峰的网络日志

阮一峰的网络日志

基于用户投票的排名算法（一）：Delicious和Hacker News

Posted: 24 Feb 2012 05:50 AM PST

互联网的出现，意味着"信息大爆炸"。

用户担心的，不再是信息太少，而是信息太多。如何从大量信息之中，快速有效地找出最重要的内容，成了互联网的一大核心问题。

各种各样的排名算法，是目前过滤信息的主要手段之一。对信息进行排名，意味着将信息按照重要性依次排列，并且及时进行更新。排列的依据，可以基于信息本身的特征，也可以基于用户的投票，即让用户决定，什么样的信息可以排在第一位。

下面，我将整理和分析一些基于用户投票的排名算法，打算分成四个部分连载，今天是第一篇。

一、Delicious

最直觉、最简单的算法，莫过于按照单位时间内用户的投票数进行排名。得票最多的项目，自然就排在第一位。

旧版的Delicious，有一个"热门书签排行榜"，就是这样统计出来的。

它按照"过去60分钟内被收藏的次数"进行排名。每过60分钟，就统计一次。

这个算法的优点是比较简单、容易部署、内容更新相当快；缺点是排名变化不够平滑，前一个小时还排在前列的内容，往往第二个小时就一落千丈。

二、Hacker News

Hacker News是一个网络社区，可以张贴链接，或者讨论某个主题。

每个帖子前面有一个向上的三角形，如果你觉得这个内容很好，就点击一下，投上一票。根据得票数，系统自动统计出热门文章排行榜。但是，并非得票最多的文章排在第一位，还要考虑时间因素，新文章应该比旧文章更容易得到好的排名。

Hacker News使用Paul Graham开发的Arc语言编写，源码可以从arclanguage.org下载。它的排名算法是这样实现的：

将上面的代码还原为数学公式：

其中，

　　P表示帖子的得票数，减去1是为了忽略发帖人的投票。

　　T表示距离发帖的时间（单位为小时），加上2是为了防止最新的帖子导致分母过小（之所以选择2，可能是因为从原始文章出现在其他网站，到转贴至Hacker News，平均需要两个小时）。

　　G表示"重力因子"（gravityth power），即将帖子排名往下拉的力量，默认值为1.8，后文会详细讨论这个值。

从这个公式来看，决定帖子排名有三个因素：

第一个因素是得票数P。

在其他条件不变的情况下，得票越多，排名越高。

从上图可以看到，有三个同时发表的帖子，得票分别为200票、60票和30票（减1后为199、59和29），分别以黄色、紫色和蓝色表示。在任一个时间点上，都是黄色曲线在最上方，蓝色曲线在最下方。

如果你不想让"高票帖子"与"低票帖子"的差距过大，可以在得票数上加一个小于1的指数，比如(P-1)^0.8。

第二个因素是距离发帖的时间T。

在其他条件不变的情况下，越是新发表的帖子，排名越高。或者说，一个帖子的排名，会随着时间不断下降。

从前一张图可以看到，经过24小时之后，所有帖子的得分基本上都小于1，这意味着它们都将跌到排行榜的末尾，保证了排名前列的都将是较新的内容。

第三个因素是重力因子G。

它的数值大小决定了排名随时间下降的速度。

从上图可以看到，三根曲线的其他参数都一样，G的值分别为1.5、1.8和2.0。G值越大，曲线越陡峭，排名下降得越快，意味着排行榜的更新速度越快。

知道了算法的构成，就可以调整参数的值，以适用你自己的应用程序。

[参考文献]

　　* How Hacker News ranking algorithm works

　　* How to Build a Popularity Algorithm You can be Proud of

（完）

文档信息
发帖者 时间：

2012年2月17日星期五

阮一峰的网络日志

阮一峰的网络日志

墙上的44句话

Posted: 17 Feb 2012 03:36 AM PST

2010年，芬兰艺术家Mikko Kuorinki做了一件独特的艺术品。

他在赫尔辛基的奇亚斯玛当代艺术博物馆（Kiasma museum），找了一堵墙，装了一个175 x 320cm的木架子，上面用不同的字母组合出一句话。每周换一次内容，一共持续了44周。

这个作品的用意在于，完全剥离了外在形式，只呈现语言的基本内容，让观众与文字背后的思想直接面对面，感受词语带来的力量。这种独特的形式，取得了意想不到的效果，很多人经过它的时候，都不由自主停下脚步，仔细观看。

我很喜欢这个作品，简洁的形式表达出丰富的内涵。下面就是这44句话中，我最喜欢的10句话。我梦想有一天，自己也可以在上海的地铁站里，做一个中文版。

（预告：本文结尾处，我要做一个广告，请一直往下读。）

1.

If you were alone, you would cut yourself in two, so that one part would shape the other.

如果你感到孤独，请把自己一切为二，一个半边就有另一个半边陪伴。

出处：Elias Canetti, The Human Province (1973)

2.

Looking in the mirror is like asking stranger for directions.

照镜子就像向一个陌生人问路。

出处：Ronald Koertge, 12 Photographs of Yellowstone (1976)

3.

My fake plants died, because I did not pretend to water them.

我的假花死了，因为我没有假装给它们浇水。

出处：Mitch Hedberg, Mitch All Together (2003)

4.

In the struggle between yourself and the world, second the world.

当你与社会发生冲突，请站在社会这一边。

出处：Franz Kafka, Unpublished Works 1916-1918

5.

Sometimes everything seems so... OH, I don't know

有时，一切看起来如此......哦，我也不知道

出处：Joe Brainard, Poem (1971)

6.

Without a sense of identity, there can be no real struggle.

如果没有清晰的自我意识，也就不存在真正的抗争。

出处：Paulo Freire, Pedagogy of the Oppressed (1970)

7.

Pleasure may come from illusion, but happiness can come only of reality.

欢愉也许来自幻觉，但幸福只能来自现实。

出处：Nicolas Chamfort

8.

We must travel in the direction of our fear.

我们恐惧的地方，就是应该探索的地方。

出处：John Berryman

9.

I want to keep smashing myself until I am whole.

我要不停地粉碎自己，直到变得完整。

出处：Elias Canetti, The Human Province (1973)

10.

In the morning, there is meaning.

在早晨，你能找到意义。

出处：Gertrude Stein, Tender Buttons (1914)

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

下面是广告时间。

去年9月，我转贴了《思思诞生记》，请大家帮忙，为我认识10年的好朋友Pin介绍工作。

现在，Pin即将告别半岁的女儿，独自到深圳的一家外贸公司上班。为了多挣奶粉钱，上班之余，她开了一家淘宝店，专营菲律宾进口的7D芒果干。

我在这里为她的淘宝店做广告。如果你需要休闲食品，欢迎购买Pin销售的7D芒果干：http://shop70350073.taobao.com/。

不仅因为这是世界上最有名、最好吃的芒果干，还因为这样可以帮到一个失去父亲、也没有母亲在身边的半岁女婴。

作为10年的朋友，我深知Pin的人品，对她销售的产品非常有信心。我敢以人格担保，这些都是菲律宾原产的正品，绝无假冒伪劣之虞。如果有人问起，为什么淘宝上还有一些价格低得多的相同商品，Pin发给我一张照片，这是她在菲律宾超市拍的。你可以根据菲律宾比索的汇率算一下，正品在原产地是什么价格。

（完）

文档信息
发帖者 时间：

阮一峰的网络日志

阮一峰的网络日志

墙上的44句话

Posted: 17 Feb 2012 03:36 AM PST

2010年，芬兰艺术家Mikko Kuorinki做了一件独特的艺术品。

他在赫尔辛基的奇亚斯玛当代艺术博物馆（Kiasma museum），找了一堵墙，装了一个175 x 320cm的木架子，上面用不同的字母组合出一句话。每周换一次内容，一共持续了44周。

这个作品的用意在于，完全剥离了外在形式，只呈现语言的基本内容，让观众与文字背后的思想直接面对面，感受词语带来的力量。这种独特的形式，取得了意想不到的效果，很多人经过它的时候，都不由自主停下脚步，仔细观看。

我很喜欢这个作品，简洁的形式表达出丰富的内涵。下面就是这44句话中，我最喜欢的10句话。我梦想有一天，自己也可以在上海的地铁站里，做一个中文版。

（预告：本文结尾处，我要做一个广告，请一直往下读。）

1.

If you were alone, you would cut yourself in two, so that one part would shape the other.

如果你感到孤独，请把自己一切为二，一个半边就有另一个半边陪伴。

出处：Elias Canetti, The Human Province (1973)

2.

Looking in the mirror is like asking stranger for directions.

照镜子就像向一个陌生人问路。

出处：Ronald Koertge, 12 Photographs of Yellowstone (1976)

3.

My fake plants died, because I did not pretend to water them.

我的假花死了，因为我没有假装给它们浇水。

出处：Mitch Hedberg, Mitch All Together (2003)

4.

In the struggle between yourself and the world, second the world.

当你与社会发生冲突，请站在社会这一边。

出处：Franz Kafka, Unpublished Works 1916-1918

5.

Sometimes everything seems so... OH, I don't know

有时，一切看起来如此......哦，我也不知道

出处：Joe Brainard, Poem (1971)

6.

Without a sense of identity, there can be no real struggle.

如果没有清晰的自我意识，也就不存在真正的抗争。

出处：Paulo Freire, Pedagogy of the Oppressed (1970)

7.

Pleasure may come from illusion, but happiness can come only of reality.

欢愉也许来自幻觉，但幸福只能来自现实。

出处：Nicolas Chamfort

8.

We must travel in the direction of our fear.

我们恐惧的地方，就是应该探索的地方。

出处：John Berryman

9.

I want to keep smashing myself until I am whole.

我要不停地粉碎自己，直到变得完整。

出处：Elias Canetti, The Human Province (1973)

10.

In the morning, there is meaning.

在早晨，你能找到意义。

出处：Gertrude Stein, Tender Buttons (1914)

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

下面是广告时间。

去年9月，我转贴了《思思诞生记》，请大家帮忙，为我认识10年的好朋友Pin介绍工作。

现在，Pin即将告别半岁的女儿，独自到深圳的一家外贸公司上班。为了多挣奶粉钱，上班之余，她开了一家淘宝店，专营菲律宾进口的7D芒果干。

我在这里为她的淘宝店做广告。如果你需要休闲食品，欢迎购买Pin销售的7D芒果干：http://shop70350073.taobao.com/。

不仅因为这是世界上最有名、最好吃的芒果干，还因为这样可以帮到一个失去父亲、也没有母亲在身边的半岁女婴。

作为10年的朋友，我深知Pin的人品，对她销售的产品非常有信心。我敢以人格担保，这些都是菲律宾原产的正品，绝无假冒伪劣之虞。如果有人问起，为什么淘宝上还有一些价格低得多的相同商品，Pin发给我一张照片，这是她在菲律宾超市拍的。你可以根据菲律宾比索的汇率算一下，正品在原产地是什么价格。

（完）

文档信息
发帖者 时间：
订阅： 博文 (Atom)