基于比较的排名算法比较

25
我想对一个包含多个元素(可能大于100,000)的集合进行排序或排名,但是集合中的元素没有固有的(可比较的)价值,而是我所拥有的只有用户提供的任意两个元素之间的比较结果,这些结果是主观的。
例如:考虑一个元素为[a, b, c, d]的集合以及用户给出的比较结果b > a, a > d, d > c,则正确的排序应该是[b, a, d, c]
这个例子很简单,但是还有更复杂的情况:
- 由于比较结果是主观的,某个用户还可能说c > b。在这种情况下,它会与上面的排序产生冲突。 - 你也可能没有将所有元素“连接”起来的比较,即b > ad > c。在这种情况下,排序是不明确的。它可能是[b, a, d, c],也可能是[d, c, b, a]。在这种情况下,任何一种排序都可以接受。
如果可能的话,最好考虑到同样的比较出现多次,并给予较高的权重。但是如果没有这个条件,解决方案仍然可接受。
类似的算法也被 Zuckerberg 的 FaceMash 应用程序所使用,他根据比较结果对人物进行排名(如果我理解得正确的话),但我没有找到该算法实际上是什么。 是否存在可以解决上述问题的算法?如果已经有了特定的算法,我不想浪费精力来尝试创造一个新算法。如果没有特定的算法,您是否可以指向某些类型的算法或技术?
3个回答

21

这个问题已经在另一个领域中出现过:竞技游戏!在这里,目标也是基于一系列1对1的比较为每个玩家分配一个全局“排名”。当然,困难在于这些比较不是可传递的(我认为您在问题中使用的“主观”是指由人类提供)。卡斯帕罗夫能打败菲舍尔,而鲍勃也能打败卡斯帕罗夫,潜在地形成高度循环图,这使得依赖传递性(即a>b和b>c => a>c)的算法无用。

已经制定了几种评级系统来解决这个问题。其中最著名的系统可能是针对竞技象棋选手的Elo算法/得分。它的后裔(例如Glicko评级系统)更加复杂,并考虑了胜负记录的统计特性——换句话说,评级的可靠程度如何?这类似于您的想法,即更重视完成更多“游戏”的记录。Glicko还构成了Xbox Live多人视频游戏中使用的TrueSkill系统的基础。


1
如果你对使用(而不是开发)感兴趣,那么你应该尝试一下我们的排名系统rankade。它与Elo和Glicko排名系统不同(这里有一个比较),因为它可以管理具有2个或更多派系(即,在您的情况下是项目)的比赛。与TrueSkill不同,rankade是免费且易于使用的。 - Tomaso Neri

4

我已经寻找像第一个链接那样的东西好几个月了,谢谢!或许直接在你的评论中包含文档的标题会更方便别人查找。 - Pend

0

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接