¿Cuál es el mejor algoritmo para hacer emparejamientos para una clasificación de fuentes multitudinarias?

Question

Me gustaría configurar un sistema que agrupe las fuentes de los mejores 10 elementos de un conjunto que puede variar de 20 a 2000 elementos (el ranking entre los diez primeros no es importante). Existe una excelente publicación de stackoverflow en algoritmos para hacer la clasificación real en How to rank a million images with a crowdsourced sort. Me inclino por preguntar a los usuarios cuál les gusta más entre dos elementos y luego usar el algoritmo TrueSkill.

Mi pregunta es porque estoy usando algo así como TrueSkill, ¿cuál es el mejor algoritmo para decidir qué pares de elementos mostrar a un usuario para evaluar? Tendré un número limitado de oportunidades para preguntar a las personas qué artículos les gustan más, así que es importante que los pares presentados le den al sistema la información más valiosa para identificar los 10 primeros. De nuevo, estoy más que interesado en encontrar los diez primeros, menos, entonces, cómo el resto de los artículos se clasifican entre ellos o incluso cómo los primeros diez se clasifican entre ellos.

Answer 1

Este problema es muy similar a organizar un torneo eliminatorio donde las habilidades de los jugadores no son bien conocidas y el número de jugadores es muy alto (piense en torneos de tenis a nivel escolar). Dado que el round robin (O (n^2) coincide) es muy costoso, pero un simple torneo eliminatorio es demasiado simplista, la opción habitual es ir con la estructura de eliminación de k. Esencialmente, cada jugador (en su contexto un elemento) queda fuera de competencia después de perder k juegos. Eche un vistazo a la estructura de doble eliminación: http://en.wikipedia.org/wiki/Double-elimination_tournament.

Quizás pueda modificarlo lo suficiente como para satisfacer sus necesidades.

Answer 2

Otro algoritmo bien conocido para esto se produjo para calcular las clasificaciones en torneos Go o Chess. Puede echarle un vistazo al MacMahon Algorithms que calcula dichos emparejamientos y rangos al mismo tiempo. Debería ser posible truncar este algoritmo, de modo que solo produzca un conjunto de 10 mejores elementos.

Puede encontrar más detalles en Christian Gerlach's thesis, donde describe el algoritmo de optimización real (lamentablemente la tesis está en alemán).