Algorithme de classement basé sur la comparaison

Question

Je voudrais classer ou trier une collection d'éléments (avec une taille potentiellement supérieure à 100 000) lorsque les éléments de la collection n'ont pas de valeur intrinsèque (comparable), à ​​la place tout ce que j'ai sont les comparaisons entre deux éléments qui ont été fournis par des utilisateurs de manière subjective.

Exemple: Considérons une collection avec les éléments [a, b, c, d] et les comparaisons par les utilisateurs b > a, a > d, d > c. L'ordre correct de cette collection serait [b, a, d, c].

Cet exemple est simple, mais il pourrait y avoir des cas plus compliqués:

• Comme les comparaisons sont subjectives, un utilisateur pourrait également dire que c > b. Dans ce cas, cela entraînerait un conflit avec la commande ci-dessus.
• De même, vous pouvez ne pas avoir de comparaisons qui "connecte" tous les éléments, c'est-à-dire b > a, d > c. Dans ce cas, la commande est ambiguë. Il pourrait être [b, a, d, c] ou [d, c, b, a]. Dans ce cas, chaque commande est acceptable.

Si possible, il serait souhaitable de prendre en compte plusieurs instances de la même comparaison et de donner plus de poids à celles qui ont des occurrences plus élevées. Mais une solution sans cette condition serait encore acceptable. Une application similaire de cet algorithme a été utilisée par l'application FaceMash de Zuckerberg où il classait les personnes en fonction de comparaisons (si je l'ai bien compris), mais je n'ai pas réussi à trouver ce que cet algorithme était réellement.

Y at-il un algorithme qui existe déjà qui peut résoudre le problème ci-dessus? Je ne voudrais pas dépenser d'efforts pour en trouver un si c'est le cas. S'il n'y a pas d'algorithme spécifique, y a-t-il peut-être certains types d'algorithmes ou de techniques auxquels vous pouvez me diriger?

Answer 1

Ceci est un problème qui a déjà eu lieu dans un autre domaine: les jeux de compétition! Ici aussi, le but est d'attribuer à chaque joueur un «rang» global sur la base d'une série de comparaisons 1 contre 1. La difficulté, bien sûr, est que les comparaisons ne sont pas transitives (je considère «subjectif» comme signifiant «fourni par un être humain» dans votre question). Kasparov bat les battements de Fischer (ne connais pas un autre joueur d'échecs!) Bob bat Kasparov, potentiellement. Cela rend les algorithmes inutiles qui reposent sur la transitivité (c'est-à-dire a > b and b > c => a > c) car vous vous retrouvez avec (probablement) un graphe hautement cyclique.

Plusieurs systèmes de classification ont été conçus pour résoudre ce problème.

Le système le plus connu est probablement le Elo algorithm/score pour les joueurs d'échecs compétitifs. Ses descendants (par exemple, le Glicko rating system) sont plus sophistiqués et prennent en compte les propriétés statistiques de l'enregistrement de gain/perte --- en d'autres termes, quelle est la fiabilité d'une note? Ceci est similaire à votre idée de pondérer plus lourdement les enregistrements avec plus de "jeux" joués. Glicko constitue également la base du TrueSkill system utilisé sur Xbox Live pour les jeux vidéo multijoueurs.

Answer 2

Vous pouvez être intéressé par le problème d'arc de retour minimum. Essentiellement, le problème est de trouver le nombre minimum de comparaisons qui "vont dans le mauvais sens" si les éléments sont ordonnés linéairement dans un certain ordre. Cela revient à trouver le nombre minimal d'arêtes à supprimer pour rendre le graphique acyclique. Malheureusement, résoudre le problème est NP-difficile.

Quelques liens qui traitent le problème:

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

Je googlé ceci, recherchez le chapitre 12.3, tri topologique et profondeur- premiers Recherche

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

Votre ensemble de relations décrivent un graphe orienté acyclique (espérons-acyclique) et donc graphique tri topologique est exactement De quoi as-tu besoin.