计算两个列表之间的相似度 [英] Computing similarity between two lists

问题描述

由于每个人都感到困惑，我想简化我的问题.我有两个有序列表.现在，我只想计算一个列表与另一个列表的相似程度.

as everyone is getting confused, I want to simplify my question. I have two ordered lists. Now, I just want to compute how similar one list is to the other.

例如，

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

什么是衡量这两个列表之间相似性的好方法，因此顺序很重要.例如，我们应该惩罚相似性，因为 4,5 在两个列表中交换?

What is a good measure of similarity between these two lists so that order is important. For example, we should penalize similarity as 4,5 is swapped in the two lists?

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

I have 2 systems. One state of the art system and one system that I implemented. Given a query, both systems return a ranked list of documents. Now, I want to compare the similarity between my system and the "state of the art system" in order to measure the correctness of my system. Please note that the order of documents is important as we are talking about a ranked system. Does anyone know of any measures that can help me find the similarity between these two lists.

推荐答案

DCG [Discounted Cumulative Gain] 和 nDCG [标准化 DCG] 通常是排名列表的一个很好的衡量标准.

The DCG [Discounted Cumulative Gain] and nDCG [normalized DCG] are usually a good measure for ranked lists.

如果排名第一，则给出相关文档的全部增益，随着排名下降，增益下降.

It gives the full gain for relevant document if it is ranked first, and the gain decreases as rank decreases.

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

注意:如果您将最先进的系统"返回的所有结果设置为相关，那么如果它们使用 DCG/nDCG 获得相同的排名，则您的系统与最先进的系统相同.

Note: If you set all results returned by "state of the art system" as relevant, then your system is identical to the state of the art if they recieved the same rank using DCG/nDCG.

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

Thus, a possible evaluation could be: DCG(your_system)/DCG(state_of_the_art_system)

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

To further enhance it, you can give a relevance grade [relevance will not be binary] - and will be determined according to how each document was ranked in the state of the art. For example rel_i = 1/log(1+i) for each document in the state of the art system.

如果这个评估函数得到的值接近 1:你的系统与基线非常相似.

示例:

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

首先你根据最先进的系统[使用上面的公式]为每个文档打分:

First you give score to each document, according to the state of the art system [using the formula from above]:

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
接下来，为您的系统计算它使用相同的相关权重并得到:DCG(mySystem) = 1.9784040064803783

Now you calculate DCG(stateOfTheArt), and use the relevance as stated above [note relevance is not binary here, and get DCG(stateOfTheArt)= 2.1100933062283396
Next, calculate it for your system using the same relecance weights and get: DCG(mySystem) = 1.9784040064803783

因此，评估为DCG(mySystem)/DCG(stateOfTheArt) = 1.9784040064803783/2.1100933062283396 = 0.9375907693942939

这篇关于计算两个列表之间的相似度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！