Algoritmo di classificazione basato su confronto

Question

Desidero classificare o ordinare una raccolta di elementi (con dimensioni potenzialmente maggiori di 100.000) in cui gli articoli nella raccolta non hanno valore intrinseco (comparabile), invece tutto ciò che ho è il confronto tra qualsiasi due articoli forniti dagli utenti in modo soggettivo.

Esempio: considerare una raccolta con elementi [a, b, c, d] e confronti degli utenti b > a, a > d, d > c. L'ordine corretto di questa raccolta sarebbe [b, a, d, c].

Questo esempio è semplice, ma ci potrebbero essere casi più complicati:

• Dal momento che i confronti sono soggettivi, un utente potrebbe anche dire che c > b. In tal caso ciò causerebbe un conflitto con l'ordine di cui sopra.
• Inoltre potresti non avere confronti che "connette" tutti gli elementi, ad esempio b > a, d > c. In tal caso l'ordine è ambiguo. Potrebbe essere [b, a, d, c] o [d, c, b, a]. In questo caso, l'ordine è accettabile.

Se possibile sarebbe bello in qualche modo prendere in considerazione più istanze dello stesso confronto e dare più peso a quelle con occorrenze più elevate. Ma una soluzione senza questa condizione sarebbe comunque accettabile.

Un'applicazione simile di questo algoritmo è stata utilizzata dall'applicazione FaceMash di Zuckerberg in cui ha classificato le persone in base ai confronti (se l'avessi capito correttamente), ma non sono stato in grado di trovare cosa fosse effettivamente quell'algoritmo.

Esiste un algoritmo già esistente in grado di risolvere il problema sopra riportato? Non vorrei spendere sforzi cercando di inventarne uno, se è il caso. Se non esiste un algoritmo specifico, esistono forse determinati tipi di algoritmi o tecniche a cui puoi indirizzarmi?

Answer 1

Questo è un problema che si è già verificato in un'altra arena: giochi competitivi! Anche qui, l'obiettivo è assegnare a ciascun giocatore un "rank" globale sulla base di una serie di confronti 1 contro 1. La difficoltà, naturalmente, è che i confronti non sono transitivi (io considero "soggettivo" come "fornito da un essere umano" nella tua domanda). Kasparov batte battiti Fischer (non si conosce un altro giocatore di scacchi!) Bob batte Kasparov, potenzialmente.

Ciò rende algoritmi inutili che si basano sulla transitività (ad esempio a > b and b > c => a > c) quando si finisce con (probabilmente) un grafico altamente ciclico.

Diversi sistemi di classificazione sono stati concepiti per affrontare questo problema.

Il sistema più conosciuto è probabilmente lo Elo algorithm/score per i giocatori di scacchi competitivi. I suoi discendenti (ad esempio, lo Glicko rating system) sono più sofisticati e tengono conto delle proprietà statistiche del record di vittorie/perdite --- in altre parole, quanto è affidabile una valutazione? Questo è simile alla tua idea di pesare più pesantemente i record con più "giochi" giocati. Glicko costituisce anche la base per lo TrueSkill system utilizzato su Xbox Live per i videogiochi multiplayer.

Answer 2

Potrebbe essere interessato al problema dell'arco minimo di feedback. Essenzialmente il problema è trovare il numero minimo di confronti che "vanno nella direzione sbagliata" se gli elementi sono ordinati linearmente in qualche ordine. Questo è lo stesso di trovare il numero minimo di bordi che devono essere rimossi per rendere il grafico aciclico. Sfortunatamente, risolvere il problema è esattamente NP-difficile.

un paio di link che discutere il 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

Ho cercato su google questo fuori, guardare per il capitolo 12.3, ordinamento topologico e depth prima Ricerca

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

tuo insieme di relazioni descrivono un grafo orientato aciclico (si spera aciclico) e così grafico ordinamento topologico è esattamente quello che ti serve.