Algoritmo de clasificación basado en comparación

Question

Me gustaría clasificar u ordenar una colección de elementos (con un tamaño potencialmente superior a 100.000) donde los elementos de la colección no tienen un valor intrínseco (comparable), en cambio todo lo que tengo son las comparaciones entre dos artículos que han sido provistos por los usuarios de una manera subjetiva.

Ejemplo: Considere una colección con elementos [a, b, c, d] y comparaciones por los usuarios b > a, a > d, d > c. El orden correcto de esta colección sería [b, a, d, c].

Este ejemplo es simple, sin embargo puede haber casos más complicados:

• Dado que las comparaciones son subjetivas, un usuario podría también decir que c > b. En ese caso, eso causaría un conflicto con el orden anterior.
• También es posible que no tenga comparaciones que "conecten" todos los elementos, es decir, b > a, d > c. En cuyo caso, el orden es ambiguo. Podría ser [b, a, d, c] o [d, c, b, a]. En este caso, cualquiera de los pedidos es aceptable.

De ser posible, sería bueno tener en cuenta varias instancias de la misma comparación y dar más peso a las que tienen una mayor ocurrencia. Pero una solución sin esta condición aún sería aceptable.

Una aplicación similar de este algoritmo fue utilizada por la aplicación FaceMash de Zuckerberg donde clasificó a las personas según las comparaciones (si lo entendía correctamente), pero no he podido encontrar qué era realmente ese algoritmo.

¿Existe un algoritmo que ya existe que pueda resolver el problema anterior? No me gustaría esforzarme tratando de encontrar uno si ese es el caso. Si no hay un algoritmo específico, ¿hay ciertos tipos de algoritmos o técnicas a los que me puede dirigir?

Answer 1

Este es un problema que ya se ha producido en otro ámbito: juegos competitivos! Aquí, también, el objetivo es asignar a cada jugador un "rango" global sobre la base de una serie de comparaciones de 1 contra 1. La dificultad, por supuesto, es que las comparaciones no son transitivas (tomo "subjetivo" para significar "proporcionado por un ser humano" en su pregunta). Kasparov vence a Fischer beats (¡no conozco a otro jugador de ajedrez!) Bob vence a Kasparov, potencialmente.

Esto representa algoritmos inútiles que dependen de la transitividad (es decir, a > b and b > c => a > c) a medida que termina con (probable) un gráfico muy cíclico.

Se han ideado varios sistemas de clasificación para resolver este problema.

El sistema más conocido es probablemente el Elo algorithm/score para los jugadores de ajedrez de la competencia. Sus descendientes (por ejemplo, el Glicko rating system) son más sofisticados y toman en cuenta las propiedades estadísticas del registro de ganar/perder --- en otras palabras, ¿qué tan confiable es una calificación? Esto es similar a su idea de ponderar más registros con más "juegos" jugados. Glicko también forma la base para el TrueSkill system utilizado en Xbox Live para videojuegos multijugador.

Answer 2

Puede que le interese el problema de configuración mínima del arco de retroalimentación. Básicamente, el problema es encontrar el número mínimo de comparaciones que "van por el camino equivocado" si los elementos se ordenan linealmente en algún orden. Esto es lo mismo que encontrar el número mínimo de bordes que se deben eliminar para que el gráfico sea acíclico. Desafortunadamente, resolver el problema exactamente es NP-hard.

Un par de enlaces que discutir el problema:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.8157&rep=rep1&type=pdf

http://en.wikipedia.org/wiki/Feedback_arc_set

Answer 3

I Googled esto, busque el capítulo 12.3, clasificación topológica y profundidad-primer Búsqueda

http://www.cs.cmu.edu/~avrim/451f09/lectures/lect1006.pdf

Su conjunto de relaciones describir un gráfico acíclico dirigido (esperemos acíclicos) y así gráfico de clasificación topológica es exactamente Que necesitas.