Similitud informática entre dos listas

Question

EDITAR: Como todo el mundo se confunde, quiero simplificar mi pregunta. Tengo dos listas ordenadas. Ahora, solo quiero calcular cuán similar es una lista a la otra.

Por ejemplo,

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

¿Qué es una buena medida de similitud entre estas dos listas por lo que el orden es importante. Por ejemplo, debemos penalizar la similitud ya que 4,5 se intercambia en las dos listas.

Tengo 2 sistemas. Un sistema de vanguardia y un sistema que implementé. Dada una consulta, ambos sistemas devuelven una lista clasificada de documentos. Ahora, quiero comparar la similitud entre mi sistema y el "estado del arte del sistema" para medir la exactitud de mi sistema. Tenga en cuenta que el orden de los documentos es importante ya que estamos hablando de un sistema clasificado. ¿Alguien sabe de alguna medida que pueda ayudarme a encontrar la similitud entre estas dos listas?

Answer 1

El DCG [Descuento acumulado acumulado] y nDCG [DCG normalizado] suelen ser una buena medida para las listas clasificadas.

Proporciona la ganancia completa para el documento relevante si se clasifica primero, y la ganancia disminuye a medida que disminuye el rango.

Usando DCG/nDCG para evaluar el sistema en comparación con la línea base de SOA:

Nota: Si establece todos los resultados devueltos por el "estado del sistema del arte" según sea pertinente, a continuación, el sistema es idénticos al estado de la técnica si recibieron el mismo rango usando DCG/nDCG.

Por lo tanto, una posible evaluación podría ser: DCG(your_system)/DCG(state_of_the_art_system)

Para mejorar aún más, puede dar un grado de relevancia [relevancia no será binaria] - y será determinado de acuerdo con la forma en que cada documento fue clasificado en el estado del arte. Por ejemplo, rel_i = 1/log(1+i) para cada documento en el sistema del estado de la técnica.

Si el valor recibido por esta función de evaluación es cercano a 1: su sistema es muy similar a la línea base.

Ejemplo:

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

Primero le dan puntuación a cada documento, de acuerdo con el estado del sistema del arte [usando la fórmula de arriba]:

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 

Ahora se calcula DCG(stateOfTheArt), y use la relevancia como se indicó anteriormente [note que la relevancia no es binaria aquí, y obtenga DCG(stateOfTheArt)= 2.1100933062283396
A continuación, cal culate para su sistema utilizando los mismos pesos relecance y obtener: DCG(mySystem) = 1.9784040064803783

Por lo tanto, la evaluación es DCG(mySystem)/DCG(stateOfTheArt) = 1.9784040064803783/2.1100933062283396 = 0.9375907693942939

Answer 2

supongo que usted está hablando de la comparación de dos sistema de recuperación de información, que confía en mí no es algo trivial. Es un problema complejo de Informática.

Para medir la relevancia o haciendo tipo de pruebas A/B es necesario tener dos cosas:

1. Un competidor para medir la relevancia. Como tiene dos sistemas, este prerrequisito se cumple.

2. Tienes que calificar manualmente los resultados. Puede pedir a sus colegas que califiquen los pares consulta/url para consultas populares y luego para los huecos (es decir, consulta/par de url no calificados puede tener alguna función de clasificación dinámica usando el algoritmo "Learning to Rank" http://en.wikipedia.org/wiki/Learning_to_rank. No se sorprenda, pero thats de verdad (por favor, lea a continuación de un ejemplo de Google/Bing).

Google y Bing son competidores en el mercado de búsqueda horizontal. Estos motores de búsqueda emplean jueces manuales de todo el mundo e invierten millones en ellos, y vota sus resultados para las consultas. Por lo tanto, para cada consulta/url, generalmente se clasifican los mejores 3 o los 5 principales. Según estas clasificaciones, pueden usar una métrica como NDCG (ganancia acumulada descontada normalizada), que es una de las mejores métricas y la de el más popular.

Según Wikipedia:

ganancia acumulada actualizado (DCG) es una medida de la eficacia de un algoritmo del motor de búsqueda web o aplicaciones relacionadas, a menudo utilizado en la recuperación de información. Utilizando una escala de relevancia graduada de documentos en un conjunto de resultados de motor de búsqueda, DCG mide la utilidad o ganancia de un documento en función de su posición en la lista de resultados. La ganancia se acumula desde la parte superior de la lista de resultados hasta la parte inferior con la ganancia de cada resultado descontado en los rangos inferiores.

Wikipedia explica NDCG de una manera excelente. Es un breve artículo, por favor revisa eso.

Answer 3

¿La lista de documentos es exhaustiva? Es decir, ¿cada rango de documento ordenado por el sistema 1 también está ordenado por el sistema 2? Si es así, a Spearman's rho puede servir para sus propósitos. Cuando no comparten los mismos documentos, la gran pregunta es cómo interpretar ese resultado. No creo que haya una medida que responda esa pregunta, aunque puede haber algunos que implementen una respuesta implícita.

Answer 4

Como dijiste, quieres calcular cuán similar es una lista a la otra. Creo que de manera simplista, puedes comenzar contando el número de inversiones.Hay una aproximación de O (NlogN) para dividir y conquistar esto. Es un enfoque muy simple para medir la "similitud" entre dos listas.

p. Ej. desea comparar cuán "similares" son los gustos de la música para dos personas en un sitio web de música, tome su clasificación de un conjunto de canciones y cuente el no. de inversiones en ella. Menor el recuento, más 'similar' es su gusto.

ya que ya está considerando el "estado del arte del sistema" para ser un punto de referencia de corrección, contando Inversions debe darle una medida básica de "similitud" de su clasificación. Por supuesto, esto es sólo una aproximación empezar, pero se puede construir sobre ella como lo estricto que desea estar con la "brecha de inversión", etc.

D1 D2 D3 D4 D5 D6 
    ----------------- 
R1: 1, 7, 4, 5, 8, 9 [Rankings from 'state of the art' system] 
R2: 1, 7, 5, 4, 9, 6 [ your Rankings] 

Desde clasificaciones son con el fin de documentos que puede escribir su propia función de comparación basado en R1 (rango de la "estado del sistema del arte" y por lo tanto contar los inversiones que comparan a que comparador

puede "penalizar" 'similitud' para cada inversiones encontrados:. i < j pero R2 [ i]> 'R2 [j]
(>' aquí utilizar su propio comparador)

Enlaces que pueden ser de utilidad:
Link1
Link2
Link3

Answer 5

Kendalls tau es la métrica que desee. Mide el número de inversiones por pares en la lista. La regla del pie de Spearman hace lo mismo, pero mide la distancia en lugar de la inversión. Ambos están diseñados para la tarea en cuestión, midiendo la diferencia en dos listas ordenadas por rango.

Answer 6

De hecho, conozco cuatro medidas diferentes para ese fin.

Tres de ellos ya se han mencionado:

• NDCG
• Tau de Kendall
• de Spearman Rho

Pero si usted tiene más de dos filas que tienen que ser comparado, use K endall's W.

Answer 7

Además de lo que ya se ha dicho, me gustaría señalarle el siguiente documento excelente: W. Webber et al, A Similarity Measure for Indefinite Rankings (2010). Además de contener una buena revisión de las medidas existentes (como Kendall Tau antes mencionada y la regla de Spearman), los autores proponen una medida probabilística intuitivamente atractiva que es aplicable para diferentes longitudes de listas de resultados y cuando no todos los elementos aparecen en ambas listas. En términos generales, se parametriza mediante una probabilidad de "persistencia" p que un usuario escanea el elemento k + 1 después de haber inspeccionado el elemento k (en lugar de abandonarlo). Superposición por posición de rango (RBO) es la relación de superposición esperada de los resultados en el punto en que el usuario deja de leer.

La implementación de RBO es un poco más complicada; Puede echar un vistazo a una implementación en Apache Pig here.

Otra medida simple es similitud del coseno, el coseno entre dos vectores con las dimensiones correspondientes a los elementos, y los rangos inversos como los pesos. Sin embargo, no maneja los elementos correctamente que solo ocurren en una de las listas (ver la implementación en el enlace de arriba).

1. Para cada elemento yo en la lista 1, h_1 (i) = 1/rank_1 (i). Para cada elemento i en la lista 2 que no aparece en la lista 1, h_1 (i) = 0. Haga lo mismo para h_2 con respecto a la lista 2.
2. Compute v12 = sum_i h_1 (i) * h_2 (i); v11 = suma_i h_1 (i) * h_1 (i); v22 = sum_i H_2 (i) * H_2 (i)
3. v12 Retorno/sqrt (v11 v22 *)

Para su ejemplo, esto le da un valor de 0,7252747.

Permítame darle algunos consejos prácticos más allá de su pregunta inmediata. A menos que su línea base de 'sistema de producción' sea perfecta (o estamos tratando con un conjunto de oro), casi siempre es mejor comparar una medida de calidad (como nDCG antes mencionado) en lugar de similitud; una nueva clasificación será a veces mejor, a veces peor que la línea de base, y desea saber si el primer caso ocurre con más frecuencia que el segundo. En segundo lugar, las medidas de similitud no son triviales para interpretar en una escala absoluta. Por ejemplo, si obtiene una puntuación de similitud de, por ejemplo, 0,72, ¿significa esto que es realmente similar o significativamente diferente? Las medidas de similitud son más útiles para decir que, p. un nuevo método de clasificación 1 está más cerca de la producción que otro nuevo método de clasificación 2.