Vergleichsbasierter Ranking-Algorithmus

Question

Ich möchte eine Sammlung von Elementen (mit einer Größe von potenziell über 100.000) ordnen oder sortieren, wobei Elemente in der Sammlung keinen intrinsischen (vergleichbaren) Wert haben, stattdessen ist alles, was ich vergleiche zwei Artikel, die von Benutzern auf subjektive Weise zur Verfügung gestellt wurden.

Beispiel: Stellen Sie sich eine Sammlung mit Elementen [a, b, c, d] und Vergleichen von anderen Nutzern b > a, a > d, d > c. Die richtige Reihenfolge dieser Sammlung wäre [b, a, d, c].

Dieses Beispiel ist einfach, jedoch könnte es kompliziertere Fälle sein:

• Da die Vergleiche subjektiv sind, ein Benutzer auch, dass c > b sagen kann. In diesem Fall würde dies zu einem Konflikt mit der obigen Anordnung führen.
• Sie können auch keine Vergleiche haben, die alle Elemente "verbinden", d. H. b > a, d > c. In diesem Fall ist die Reihenfolge nicht eindeutig. Es könnte [b, a, d, c] oder [d, c, b, a] sein. In diesem Fall ist die Bestellung akzeptabel.

Wenn möglich wäre es schön, irgendwie mehrere Instanzen des gleichen Vergleichs zu berücksichtigen und solche mit höheren Vorkommen mehr Gewicht geben. Aber eine Lösung ohne diese Bedingung wäre immer noch akzeptabel.

Eine ähnliche Anwendung dieses Algorithmus wurde von Zuckerbergs FaceMash-Anwendung verwendet, wo er Leute basierend auf Vergleichen (wenn ich es richtig verstanden habe) einordnete, aber ich konnte nicht herausfinden, was dieser Algorithmus tatsächlich war.

Gibt es einen bereits existierenden Algorithmus, der das obige Problem lösen kann? Ich möchte keine Mühe darauf verwenden, einen zu finden, wenn das der Fall ist. Wenn es keinen spezifischen Algorithmus gibt, gibt es vielleicht bestimmte Arten von Algorithmen oder Techniken, auf die Sie mich hinweisen können?

Answer 1

Dies ist ein Problem, das in einer anderen Arena bereits aufgetreten ist: Pflichtspiele! Ziel ist es auch hier, jedem Spieler auf der Basis einer Reihe von 1 gegen 1-Vergleichen einen globalen "Rang" zuzuweisen. Die Schwierigkeit besteht natürlich darin, dass die Vergleiche nicht transitiv sind (ich nehme "subjektiv" in Ihrer Frage "von einem Menschen"). Kasparov schlägt Fischer Beats (kenne keinen anderen Schachspieler!) Bob schlägt möglicherweise Kasparov.

Dies macht nutzlose Algorithmen erforderlich, die auf Transitivität beruhen (d. H. a > b and b > c => a > c), da Sie (wahrscheinlich) einen stark zyklischen Graphen haben.

Mehrere Bewertungssysteme wurden entwickelt, um dieses Problem anzugehen.

Das bekannteste System ist wahrscheinlich die Elo algorithm/score für wettbewerbsfähige Schachspieler. Seine Nachkommen (zum Beispiel die Glicko rating system) sind anspruchsvoller und berücksichtigen statistische Eigenschaften des Gewinn/Verlust-Datensatzes --- mit anderen Worten, wie zuverlässig ist eine Bewertung? Dies entspricht Ihrer Idee, mehr Platten mit mehr gespielten "Spielen" zu gewichten. Glicko bildet auch die Basis für die TrueSkill system Xbox Live für Multiplayer-Videospiele.

Answer 2

Möglicherweise haben Sie Interesse an dem Problem mit dem Mindestlichtbogen. Im Wesentlichen besteht das Problem darin, die minimale Anzahl von Vergleichen zu finden, die "in die falsche Richtung gehen", wenn die Elemente in einer Reihenfolge linear geordnet sind. Dies entspricht der Suche nach der Mindestanzahl von Kanten, die entfernt werden müssen, um das Diagramm azyklisch zu machen. Leider ist die Lösung des Problems genau NP-schwer.

Ein paar Links, die das Problem diskutieren:

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

Ich googeln diese aus, suchen Sie nach Kapitel 12.3, topologische Sortierung und Tiefen- ersten Suche

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

Setliste Beziehungen ein gerichteter azyklischer Graph (hoffentlich azyklisch) und so Graph topologische Sortierung ist genau beschreiben was du brauchst.