如何进入邮箱的网站,网站优化怎么做ppt,北京模板网站建设,天津建设工程协会网站作者: 阮一峰 发布时间: 2012-03-29 13:33 阅读: 7323 次 推荐: 6 原文链接 [收藏] 目录 基于用户投票的排名算法#xff08;一#xff09;#xff1a;Delicious和Hacker News 基于用户投票的排名算法#xff08;二#xff09;#xff1a;Reddit 基于用户…作者: 阮一峰 发布时间: 2012-03-29 13:33 阅读: 7323 次 推荐: 6 原文链接 [收藏] 目录 基于用户投票的排名算法一Delicious和Hacker News 基于用户投票的排名算法二Reddit 基于用户投票的排名算法三Stack Overflow 基于用户投票的排名算法四牛顿冷却定律 基于用户投票的排名算法五威尔逊区间 基于用户投票的排名算法六贝叶斯平均 基于用户投票的排名算法一Delicious和Hacker News 互联网的出现意味着信息大爆炸。 用户担心的不再是信息太少而是信息太多。如何从大量信息之中快速有效地找出最重要的内容成了互联网的一大核心问题。 各种各样的排名算法是目前过滤信息的主要手段之一。对信息进行排名意味着将信息按照重要性依次排列并且及时进行更新。排列的依据可以基于信息本身的特征也可以基于用户的投票即让用户决定什么样的信息可以排在第一位。 下面我将整理和分析一些基于用户投票的排名算法打算分成四个部分连载今天是第一篇。 一、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 基于用户投票的排名算法二Reddit 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就等于1。 结合以上几个变量Reddit 的最终得分计算公式如下 这个公式可以分成两个部分来讨论 一 这个部分表示赞成票超过反对票的数量越多得分越高。 需要注意的是这里用的是以 10 为底的对数意味着z10可以得到 1 分z100可以得到 2 分。也就是说前 10 个投票人与后 90 个投票人乃至再后面 900 个投票人的权重是一样的即如果一个帖子特别受到欢迎那么越到后面投赞成票对得分越不会产生影响。 当反对票超过或等于赞成票z1因此这个部分等于0也就是不产生得分。 二 这个部分表示t越大得分越高即新帖子的得分会高于老帖子。它起到自动将老帖子的排名往下拉的作用。 分母的 45000 秒等于 12.5 个小时也就是说后一天的帖子会比前一天的帖子多得 2 分。结合前一部分可以得到结论如果前一天的帖子在第二天还想保持原先的排名在这一天里面它得到的净赞成票必须增加 100 倍。 y 的作用是用来产生正分和负分。当赞成票超过反对票时得分为正当赞成票少于反对票时得分为负当两者相等得分为0。这就保证了得到大量净赞成票的文章会排在前列得到大量净反对票的文章会排在最后。 三 这种算法的一个问题是对于那些有争议的文章赞成票和反对票非常接近它们不可能排到前列。假定同一时间有两个帖子发表文章A有 1 张赞成票发帖人投的、0张反对票文章B有 1000 张赞成票、1000张反对票那么A的排名会高于B这显然不合理。 结论就是Reddit 的排名基本上由发帖时间决定超级受欢迎的文章会排在最前面一般性受欢迎的文章、有争议的文章都不会很靠前。这决定了 Reddit 是一个符合大众口味的社区不是一个很激进、可以展示少数派想法的地方。 [参考资料] * How Reddit ranking algorithms work 基于用户投票的排名算法三Stack Overflow Reddit 排名算法的特点是用户可以投赞成票也可以投反对票。也就是说除了时间因素以外只要考虑两个变量就够了。 但是还有一些特定用途的网站必须考虑更多的因素。世界排名第一的程序员问答社区 Stack Overflow就是这样一个网站。 你在上面提出各种关于编程的问题等待别人回答。访问者可以对你的问题进行投票赞成票或反对票表示这个问题是不是有价值。 一旦有人回答了你的问题其他人也可以对这个回答投票赞成票或反对票。根据投票结果系统自动找出最佳回答。 排名算法的作用是找出某段时间内的热点问题即哪些问题最被关注、得到了最多的讨论。 在 Stack Overflow 的页面上每个问题前面有三个数字分别表示问题的得分、回答的数目和该问题的浏览次数。以这些变量为基础就可以设计算法了。 创始人之一的 Jeff Atwood曾经在几年前公布过排名得分的计算公式。 写成 php 代码就是下面这样 各个算法变量的含义如下 1Qviews问题的浏览次数 某个问题的浏览次数越多就代表越受关注得分也就越高。这里使用了以 10 为底的对数用意是当访问量越来越大它对得分的影响将不断变小。 2Qscore问题得分和 Qanswers回答的数量 首先Qscore问题得分 赞成票-反对票。如果某个问题越受到好评排名自然应该越靠前。 Qanswers 表示回答的数量代表有多少人参与这个问题。这个值越大得分将成倍放大。这里需要注意的是如果无人回答Qanswers 就等于0这时 Qscore 再高也没用意味着再好的问题也必须有人回答否则进不了热点问题排行榜。 3Ascores回答得分 一般来说回答比问题更有意义。这一项的得分越高就代表回答的质量越高。 但是我感觉简单加总的设计还不够全面。这里有两个问题。首先一个正确的回答胜过一百个无用的回答但是简单加总会导致1个得分为 100 的回答与 100 个得分为 1 的回答总得分相同。其次由于得分会出现负值因此那些特别差的回答会拉低正确回答的得分。 4Qage距离问题发表的时间和 Qupdated距离最后一个回答的时间 改写一下可以看得更清楚 Qage 和 Qupdated 的单位都是秒。如果一个问题的存在时间越久或者距离上一次回答的时间越久Qage 和 Qupdated 的值就相应增大。 也就是说随着时间流逝这两个值都会越变越大导致分母增大因此总得分会越来越小。 总结 Stack Overflow 热点问题的排名与参与度Qviews 和 Qanswers和质量Qscore 和 Ascores成正比与时间Qage 和 Qupdated成反比。 基于用户投票的排名算法四牛顿冷却定律 这个系列的前三篇介绍了 Hacker NewsReddit 和 Stack Overflow 的排名算法。 今天讨论一个更一般的数学模型。 这个系列的每篇文章都是可以分开读的。但是为了保证所有人都在同一页上我再说一下到目前为止我们用不同方法企图解决的都是同一个问题根据用户的投票决定最近一段时间内的热文排名。 你可能会觉得这是一个全新的课题伴随着互联网而产生需要全新的方法来解决。但是实际上不是。我们可以把热文排名想象成一个自然冷却的过程 1任一时刻网站中所有的文章都有一个当前温度温度最高的文章就排在第一位。 2如果一个用户对某篇文章投了赞成票该文章的温度就上升一度。 3随着时间流逝所有文章的温度都逐渐冷却。 这样假设的意义在于我们可以照搬物理学的冷却定律使用现成的公式建立温度与时间之间的函数关系轻松构建一个指数式衰减Exponential decay的过程。 伟大的物理学家牛顿早在 17 世纪就提出了温度冷却的数学公式被后人称作牛顿冷却定律Newtons Law of Cooling。我们就用这个定律构建排名算法。 牛顿冷却定律非常简单用一句话就可以概况 物体的冷却速度与其当前温度与室温之间的温差成正比。 写成数学公式就是 其中 - T (t)是温度T的时间t函数。微积分知识告诉我们温度变化冷却的速率就是温度函数的导数T(t)。 - H 代表室温T(t)-H就是当前温度与室温之间的温差。由于当前温度高于室温所以这是一个正值。 - 常数αα0表示室温与降温速率之间的比例关系。前面的负号表示降温。不同的物质有不同的α值。 这是一个微分方程为了计算当前温度需要求出T(t)的函数表达式。 第一步改写方程然后等式两边取积分。 第二步求出这个积分的解c为常数项。 第三步假定在时刻t0该物体的温度是T(t0)简写为T0。代入上面的方程得到 第四步将上一步的C代入第二步的方程。 假定室温H为 0 度即所有物体最终都会冷寂方程就可以简化为 上面这个方程就是我们想要的最终结果 本期温度 上一期温度 x exp (-(冷却系数) x 间隔的小时数) 将这个公式用在排名算法就相当于假定本期没有增加净赞成票 本期得分 上一期得分 x exp (-(冷却系数) x 间隔的小时数) 其中冷却系数是一个你自己决定的值。如果假定一篇新文章的初始分数是 100 分24小时之后冷却为 1 分那么可以计算得到冷却系数约等于0.192。如果你想放慢热文排名的更新率冷却系数就取一个较小的值否则就取一个较大的值。 [参考文献] Rank Hotness With Newtons Law of Cooling 基于用户投票的排名算法五威尔逊区间 迄今为止这个系列都在讨论如何给出某个时段的排名比如过去 24 小时最热门的文章。 但是很多场合需要的是所有时段的排名比如最受用户好评的产品。 这时时间因素就不需要考虑了。这个系列的最后两篇就研究不考虑时间因素的情况下如何给出排名。 一种常见的错误算法是 得分 赞成票 - 反对票 假定有两个项目项目A是 60 张赞成票40张反对票项目B是 550 张赞成票450张反对票。请问谁应该排在前面按照上面的公式B会排在前面因为它的得分550 - 450 100高于A60 - 40 20。但是实际上B的好评率只有 55%550 / 1000而A为 60%60 / 100所以正确的结果应该是A排在前面。 Urban Dictionary 就是这种错误算法的实例。 另一种常见的错误算法是 得分 赞成票 / 总票数 如果总票数很大这种算法其实是对的。问题出在如果总票数很少这时就会出错。假定A有 2 张赞成票、0张反对票B有 100 张赞成票、1张反对票。这种算法会使得A排在B前面。这显然错误。 Amazon 就是这种错误算法的实例。 那么正确的算法是什么呢 我们先做如下设定 1每个用户的投票都是独立事件。 2用户只有两个选择要么投赞成票要么投反对票。 3如果投票总人数为n其中赞成票为k那么赞成票的比例p就等于k/n。 如果你熟悉统计学可能已经看出来了p服从一种统计分布叫做两项分布binomial distribution。这很重要下面马上要用到。 我们的思路是p越大就代表这个项目的好评比例越高越应该排在前面。但是p的可信性取决于有多少人投票如果样本太小p就不可信。好在我们已经知道p服从两项分布因此我们可以计算出p的置信区间。所谓置信区间就是说以某个概率而言p会落在的那个区间。比如某个产品的好评率是 80%但是这个值不一定可信。根据统计学我们只能说有 95% 的把握可以断定好评率在 75% 到 85% 之间即置信区间是[75% 85%]。 这样一来排名算法就比较清晰了 第一步计算每个项目的好评率即赞成票的比例。 第二步计算每个好评率的置信区间以 95% 的概率。 第三步根据置信区间的下限值进行排名。这个值越大排名就越高。 这样做的原理是置信区间的宽窄与样本的数量有关。比如A有 8 张赞成票2张反对票B有 80 张赞成票20张反对票。这两个项目的赞成票比例都是 80%但是B的置信区间假定[75% 85%]会比A假定[70% 90%]窄得多因此B的置信区间的下限值75%会比A70%大所以B应该排在A前面。 置信区间的实质就是进行可信度的修正弥补样本量过小的影响。如果样本多就说明比较可信不需要很大的修正所以置信区间会比较窄下限值会比较大如果样本少就说明不一定可信必须进行较大的修正所以置信区间会比较宽下限值会比较小。 二项分布的置信区间有多种计算公式最常见的是正态区间Normal approximation interval教科书里几乎都是这种方法。但是它只适用于样本较多的情况np 5 且 n (1 − p) 5对于小样本它的准确性很差。 1927年美国数学家 Edwin Bidwell Wilson 提出了一个修正公式被称为威尔逊区间很好地解决了小样本的准确性问题。 在上面的公式中表示样本的赞成票比例n表示样本的大小表示对应某个置信水平的z统计量这是一个常数可以通过查表或统计软件包得到。一般情况下在 95% 的置信水平下z统计量的值为1.96。 威尔逊置信区间的均值为 它的下限值为 可以看到当n的值足够大时这个下限值会趋向。如果n非常小投票人很少这个下限值会大大小于。实际上起到了降低赞成票比例的作用使得该项目的得分变小、排名下降。 Reddit 的评论排名目前就使用这个算法。 [参考文献] * How Not To Sort By Average Rating 基于用户投票的排名算法六贝叶斯平均 上一篇介绍了威尔逊区间它解决了投票人数过少、导致结果不可信的问题。 举例来说如果只有 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/(vm)这部分的权重将越来越大得分将慢慢接近真实情况。 这样做拉近了不同电影之间投票人数的差异使得投票人数较少的电影也有可能排名前列。 把这个公式写成更一般的形式 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。 转载于:https://www.cnblogs.com/liuchaogege/p/5217274.html
