algorithm - Similitud computacional entre dos listas

search statistics

Question

EDITAR: como todo el mundo se confunde, quiero simplificar mi pregunta. Tengo dos listas ordenadas. Ahora, solo quiero calcular qué tan similar es una lista a la otra.

P.ej,

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

¿Cuál es una buena medida de la similitud entre estas dos listas para que el orden sea importante? Por ejemplo, ¿deberíamos penalizar la similitud ya que 4,5 se intercambia en las dos listas?

Tengo 2 sistemas. Un sistema avanzado 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 "sistema de vanguardia" para medir la corrección 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

¿La lista de documentos es exhaustiva? Es decir, ¿todos los documentos ordenados por el sistema 1 también ordenados por el sistema 2? Si es así, un rho de Spearman puede servir a tus 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 a esa pregunta, aunque puede haber algunas que implementen una respuesta implícita.

Answer 2

Además de lo que ya se ha dicho, me gustaría señalarle el excelente artículo siguiente: W. Webber et al, Una Medida de Similitud para las Clasificaciones Indefinidas (2010) . Además de contener una buena revisión de las medidas existentes (como la regla de Kendall Tau y Spearman antes mencionada), los autores proponen una medida probabilística intuitivamente atractiva que es aplicable para longitudes variables de listas de resultados y cuando no todos los elementos aparecen en ambas listas. En términos generales, está parametrizado por una probabilidad de "persistencia" p de que un usuario escanee el ítem k + 1 después de haber inspeccionado el ítem k (en lugar de abandonar). La superposición de rango parcial (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; Puedes echar un vistazo a una implementación en Apache Pig here .

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

1. Para cada elemento i en la lista 1, deje h_1 (i) = 1 / rank_1 (i). Para cada elemento i en la lista 2 que no aparezca en la lista 1, h_1 (i) = 0. Haga lo mismo para h_2 con respecto a la lista 2.
2. Calcular v12 = sum_i h_1 (i) * h_2 (i); v11 = sum_i h_1 (i) * h_1 (i); v22 = sum_i h_2 (i) * h_2 (i)
3. Devolver v12 / sqrt (v11 * v22)

Para su ejemplo, esto da un valor de 0.7252747.

Por favor, permítame darle algunos consejos prácticos más allá de su pregunta inmediata. A menos que la línea de base de su ''sistema de producción'' sea perfecta (o estamos tratando con un conjunto de oro), casi siempre es mejor comparar una medida de calidad (como la nDCG mencionada anteriormente) en lugar de la similitud; una nueva clasificación será a veces mejor, a veces peor que la línea de base, y usted quiere 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 al decir que, por ejemplo, un nuevo método de clasificación 1 está más cerca de la producción que otro método de clasificación nuevo 2.

Answer 3

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 un enfoque de división y conquista de O (NlogN) para esto. Es un enfoque muy simple para medir la "similitud" entre dos listas.

por ejemplo, si desea comparar qué tan similares son los gustos musicales de dos personas en un sitio web de música, tome su clasificación de un conjunto de canciones y cuente el no. de las inversiones en ella. Cuanto menor sea el recuento, más "similar" es su sabor.

Dado que ya está considerando que el "sistema de vanguardia" es un punto de referencia de corrección, contar Inversiones debería darle una medida básica de "similitud" de su clasificación. Por supuesto, esto es solo un enfoque de iniciación, pero puede desarrollarlo según lo estricto que quiera ser 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]

Dado que las clasificaciones están en el orden de los documentos, puede escribir su propia función de comparador basada en R1 (clasificación del "sistema de vanguardia" y, por lo tanto, contar las inversiones en comparación con ese comparador.

Puede "penalizar" la "similitud" para cada inversión encontrada: i <j pero R2 [i]> ''R2 [j]
( > '' Aquí usas tu propio comparador)

Enlaces que te pueden resultar útiles:
Link1
Link2
Link3

Answer 4

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

Da la ganancia completa para el documento relevante si se clasifica primero, y la ganancia disminuye a medida que disminuye la clasificación.

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

Nota: Si configura todos los resultados devueltos por "sistema de vanguardia" como relevantes, entonces su sistema es idéntico al estado de la técnica si obtuvieron 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 una calificación de relevancia [la relevancia no será binaria ], y se determinará de acuerdo con la clasificación de cada documento en el estado de la técnica. Por ejemplo, rel_i = 1/log(1+i) para cada documento en el sistema más moderno.

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, otorgue una puntuación a cada documento, de acuerdo con el sistema de vanguardia [utilizando 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 calcula DCG(stateOfTheArt) , y usa la relevancia como se indicó anteriormente [la relevancia de la nota no es binaria aquí, y obtienes DCG(stateOfTheArt)= 2.1100933062283396
A continuación, calcúlelo para su sistema utilizando los mismos pesos de relecancia y obtenga: DCG(mySystem) = 1.9784040064803783

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

Answer 5

En realidad sé cuatro medidas diferentes para ese propósito.

Ya se han mencionado tres:

• NDCG
• Tau de Kendall
• Rho de Spearman

Pero si tiene que comparar más de dos rangos, use W de Kendall .

Answer 6

Kendalls tau es la métrica que deseas. 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 7

Supongo que está hablando de comparar dos sistemas de recuperación de información que confían en mí no es algo trivial. Es un problema complejo de informática.

Para medir la relevancia o realizar una prueba A / B, necesita tener un par de cosas:

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

2. Necesitas puntuar manualmente los resultados. Puede pedir a sus colegas que califiquen pares de consulta / url para consultas populares y luego para los orificios (es decir, el par de consulta / url no calificado puede tener alguna función de clasificación dinámica usando el algoritmo "Aprendiendo para clasificar" http://en.wikipedia.org/wiki/Learning_to_rank . No se sorprenda por eso, pero eso es cierto (lea a continuación 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 en todo el mundo e invierten millones en ellos, para calificar sus resultados para consultas. Por lo tanto, para cada consulta / pares de url, generalmente se clasifican los resultados top 3 o top 5. Según estas clasificaciones, pueden usar una métrica como NDCG (Ganancia acumulada descontada normalizada), que es una de las mejores métricas y una de las más populares.

Según wikipedia:

La ganancia acumulada descontada (DCG) es una medida de la efectividad de un algoritmo de motor de búsqueda web o aplicaciones relacionadas, a menudo utilizadas en la recuperación de información. Al usar una escala de relevancia graduada de los documentos en un conjunto de resultados del 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 rangos más bajos.

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