如何比较排名列表

Question

我有两个排名项目的列表。每个项目都有一个排名和相应的分数。分数决定了排名。这两个列表可以包含（通常是不同的）不同项目，它们的交集可能为空。我需要比较这些排名的度量方法。是否有已知算法（在文献或现实世界中）来做到这一点？距离的度量应考虑到项目的得分和排名。

- Valerio Schiavoni

---

Cavnar＆Trenkle提出了一种简单易懂的方法，用于度量两个排名列表之间的差异。Wilcoxon ranked-sum test提供了（不）相似性的度量值，但如果两个列表没有交集，您需要发明一些技巧（例如使用某个最大分数; 再次参见Cavnar＆Trenkle）。 - Fred Foo

所提及的文章《基于N-Gram的文本分类》（1994年）提供了一种可能的距离度量方法，用于排名列表之间的比较。然而，给出的示例（比较n-gram的排名列表）并未详细说明极端情况或如何在无匹配项的情况下定义“max”距离。此外，这些项目没有关联得分。 - Valerio Schiavoni

实际上，如果我没记错的话，已经讨论了不匹配的情况。在制作一个前k个列表时，任何只出现在一个列表中的项目都会受到k+1的惩罚。 - Fred Foo

Answer 1

这个问题以前从未被回答过，但我仍然认为它对很多人来说非常重要：

您提出的两个要求，即列表的非共同性和排名的重要性，没有被常见的相关性测试所满足。此外，它们中的大部分（例如Kendall-Tau）都没有考虑顺序：

>>> from scipy.stats import kendalltau
>>> kendalltau([1,2,3,4,5], [2,1,3,4,5])
KendalltauResult(correlation=0.79999999999999982, value=0.050043527347496564)
>>> kendalltau([1,2,3,4,5], [1,2,3,5,4])
KendalltauResult(correlation=0.79999999999999982, value=0.050043527347496564)

第一个比较应该产生一个明显小于第二个的值，因为列表的头部比尾部更重要（第二个要求）。

除此之外，可以看到两个列表需要具有相同的大小和相同的元素类型（第一个要求）

可能的解决方案:

满足您所有需求的度量称为Rank Biased Overlap。它是所谓的基于平均的重叠的推广，这在这个博客中得到了精彩的阐述。 同一个人还发布了RBO的一个实现。

更新于2018年1月：

• 针对python 3.5.2的另一个RBO实现

- Mike Dooley

---

谢谢，这对我很有效。我有一个固定的股票清单[50]，想知道它们每天的变化幅度，并且将得分最高的股票赋予更高的权重。干杯！ - run-out

非常好的文章！ - Christoph

Answer 2

也许无法完全解决问题，但绝对值得看一下Kendall's weighted tau。它提供了一种更好的计算排名列表相似度的方法，当顺序很重要时，它允许基于排名顺序进行任意加权。例如，人们可能更感兴趣的是在列表前20个项目中加强相似性，而不是均匀地分配。同时，在scipy中还有一个不错的实现。

- alex_sp

Answer 3

有许多措施用于比较排名前k（排名）列表。一些非常容易计算，但需要做出几个简化假设，而其他措施则更加严格地评估了列表之间的排名相似性。最近我遇到一篇论文，它以统计意义的方式处理这个问题，使用了信息论和数据压缩的概念：http://arxiv.org/abs/1310.0110

- user4504777