一尘不染

基于比较的排名算法

algorithm

我想对一个项目集合(大小可能大于100,000)进行排序或排序,其中该集合中的项目没有内在(可比较)值,而 我所拥有的只是 用户在其中提供的
任何两个项目之间的比较 主观的方式。

例如:考虑的元素的集合[a, b, c, d]用户和比较b > aa > dd > c。此集合的正确顺序为[b, a, d, c]

这个例子很简单,但是可能会有更复杂的情况:

  • 由于比较是主观的,因此用户也可以这样说c > b。在这种情况下,将导致与上述顺序发生冲突。
  • 你也可能没有对比的是“所连接”中的所有项目,即b > ad > c。在这种情况下,顺序是不明确的。可能是[b, a, d, c][d, c, b, a]。在这种情况下,任何一种订购都是可以接受的。

如果可能的话,最好以某种方式考虑同一比较的多个实例,并为出现次数更高的实例赋予更大的权重。但是没有这种情况的解决方案仍然可以接受。

扎克伯格的FaceMash应用程序使用了该算法的类似应用程序,他在该应用程序中根据比较对人进行排名(如果我理解正确的话),但是我无法找到该算法的真正含义。

是否已经存在可以解决上述问题的算法? 如果是这样的话,我不想花力气想出一个。如果没有特定的算法,您可能会指出某些类型的算法或技术吗?


阅读 243

收藏
2020-07-28

共1个答案

一尘不染

这是另一个领域已经出现的问题:竞技游戏!同样,这里的目标是根据一系列1对1的比较为每个玩家分配一个全局“排名”。当然,困难在于比较不是可传递的(在您的问题中,我将“主观”理解为“由人提供”)。卡斯帕罗夫击败了费舍尔(不认识其他国际象棋选手!)鲍勃可能会击败卡斯帕洛夫。

这导致无用的算法依赖于传递性(即a > b and b > c => a > c),最终导致(可能)出现一个高度循环的图。

已经设计出几种评级系统来解决这个问题。

最著名的系统可能是竞技棋手的Elo算法/得分。它的后代(例如,Glicko评分系统)更加复杂,并考虑了获胜/失败记录的统计属性-
换句话说,评分的可靠性如何?这类似于您对播放更多“游戏”的记录进行加权的想法。Glicko还构成了Xbox
Live上用于多人视频游戏的TrueSkill系统的基础。

2020-07-28