排名相关算法

我有一个朋友的排名列表。然后，我再收到几个同样朋友的列表，但排名不同。是否有算法来检查哪个列表与最初的排名列表最接近？排名相关算法

谢谢

2013-03-21 Mike

我想你可以通过使用[数组倒数算法]（http://stackoverflow.com/questions/337664/counting-inversions-in-array）在O（n日志n）中运行。基本上，你把你原来的排名，你分配给每个项目一个ID递增顺序，然后你在“不同的排名”为您的每个项目分配给他们相应的ID从初始排名（你应该能够要有效地做到这一点），然后你应用我上面提到的算法分配给“不同排名”的ID。 – 2013-03-21 12:09:30

这可能取决于您对两个排名之间“距离”的衡量标准。

例如，如果我们定义

dist(R1, R2) = Sum abs(position of i in R1 - position of i in R2), over all i

然后可以存储在第一排名每i位置在阵列

即

pos[Peter] = 3

装置那Peter显示为你的第三个朋友排行。

通过使用pos计算上述总和，可以在线性时间内找到最接近的排名。

来源

2013-03-21 14:53:08 abeln

这是一个很好的解决方案。然而，它并没有告诉我很多关于距离的重要性。比方说，我有一个排名榜，有200个朋友排在第一位，另一方面，我有一个排名榜，其中一个朋友排名下了200个排名。距离将是相同的。然而，第二排名表比第一排名表要好得多。 – Mike 2013-04-02 23:01:55

您可以通过获取位置差异的平方或立方体来惩罚较大的差异。 – abeln 2013-04-03 13:38:15

我想我可以。谢谢 – Mike 2013-04-05 12:27:13

我认为你应该比较它们之间的等级距离，但使用权重。例如，如果用户排名第一位在第十位，这是一个很大的差异，但如果用户排名第101位在第110位，这不是一个大的变化。所以你应该对更高等级的用户差异设置更高的系数。

来源

2013-03-21 15:55:08 aram90

排名相关算法

回答

相关问题