计算两个列表之间的相似性

Question

编辑:因为每个人都感到困惑,我想简化我的问题.我有两个有序列表.现在,我只想计算一个列表与另一个列表的相似程度.

例如,

1,7,4,5,8,9
1,7,5,4,9,6

这两个列表之间的相似性的良好衡量标准是什么,以便顺序很重要.例如,我们应该惩罚相似性,因为在这两个列表中交换了4,5？

我有2个系统.一个最先进的系统和我实施的一个系统.给定查询,两个系统都返回排序的文档列表.现在,我想比较我的系统和"最先进的系统"之间的相似性,以便衡量我的系统的正确性.请注意,文档的顺序很重要,因为我们正在讨论排名系统.有没有人知道任何可以帮助我找到这两个列表之间相似性的措施.

Answer 1

该DCG [贴现累计收益]和NDCG [标准化DCG]通常是等级列表一个很好的措施.

如果排名第一,它会为相关文档提供全部收益,并且随着排名降低,收益会减少.

与SOA基线相比,使用DCG/nDCG评估系统:

注意:如果您将"最先进系统"返回的所有结果设置为相关,那么如果使用DCG/nDCG获得相同等级,则您的系统与现有技术相同.

因此,可能的评估可能是: DCG(your_system)/DCG(state_of_the_art_system)

为了进一步增强它,您可以给出相关性等级[ 相关性不是二进制 ] - 并且将根据每个文档在现有技术中的排名来确定.例如rel_i = 1/log(1+i),对于现有技术系统中的每个文档.

如果此评估函数收到的值接近1:您的系统与基线非常相似.

例:

mySystem = [1,2,5,4,6,7]
stateOfTheArt = [1,2,4,5,6,9]

首先,根据最新系统[使用上面的公式]给每个文档打分:

doc1 = 1.0
doc2 = 0.6309297535714574
doc3 = 0.0
doc4 = 0.5
doc5 = 0.43067655807339306
doc6 = 0.38685280723454163
doc7 = 0
doc8 = 0
doc9 = 0.3562071871080222

现在你计算DCG(stateOfTheArt),并使用上面所述的相关性[注意相关性在这里不是二进制,然后得到DCG(stateOfTheArt)= 2.1100933062283396
Next,使用相同的relecance权重为你的系统计算它并得到:DCG(mySystem) = 1.9784040064803783

因此,评估是 DCG(mySystem)/DCG(stateOfTheArt) = 1.9784040064803783 / 2.1100933062283396 = 0.9375907693942939

Answer 2

Kendalls tau 是您想要的指标。它测量列表中成对反转的数量。斯皮尔曼的脚法也是如此，但测量的是距离而不是倒数。它们都是为手头的任务设计的，测量两个排序列表的差异。