Come posso classificare le squadre in base a vittorie / sconfitte testa a testa

1

Sto provando a scrivere un algoritmo (specificamente in Ruby) che classificherà le squadre in base al loro record l'uno contro l'altro. Se una squadra A e una squadra B hanno vinto la stessa quantità di giochi l'una contro l'altra, allora va giù per puntare ai differenziali.

Ecco un esempio:

A beat B two times
B beats C one time
A beats D three times
C bests D two times
D beats C one time
B beats A one time

Che tipo di riduce a

A[B] = 2
B[C] = 1
A[D] = 3
C[D] = 2
D[C] = 1
B[A] = 1

Che tipo di riduce a

A[B] = 1
B[C] = 1
A[D] = 3
C[D] = 1
D[C] = -1
B[A] = -1

Che è su quanto lontano ho

Penso che i risultati di questo specifico algoritmo sarebbero:

A, B, C, D

Ma sono bloccato su come passare dalla struttura nidificata ad hash ai risultati.

Il mio psuedo-code è il seguente (posso postare anche il mio codice ruby se qualcuno vuole):

For each game(g):
  hash[g.winner][g.loser] += 1

Questo lascia hash come prima riduzione sopra

hash2 = clone of hash
For each key(winner), value(losers hash) in hash:
  For each key(loser), value(losses against winner):
    hash2[loser][winner] -= losses

Che lascia hash2 come seconda riduzione

Sentitevi liberi di chiedere o modificare questo per essere più chiari, non sono sicuro di come metterlo in un modo molto eloquente. Grazie!

    
posta Tom Prats 12.06.2014 - 05:16
fonte

3 risposte

2

Valutare i punti di forza relativi di squadre / concorrenti è una sorta di problema risolto, quindi perché reinventare la ruota?

C'è il sistema di valutazione Elo , concepito originariamente per gli scacchi, e vi è anche il Glicko ( pdf ) sistema di valutazione .

Entrambi i sistemi cercano di modellare la probabilità che un concorrente vincerà contro un altro e di produrre un punteggio che rappresenti la loro forza relativa. Cioè punteggio più alto significa un giocatore più strong.

Il sistema Elo è a somma zero e presenta alcuni casi di bordo spinoso.

Il sistema Glicko non è a somma zero, ma modella anche la sicurezza del punteggio; cioè un giocatore con un singolo punto dati non è ponderato alto come un giocatore con molti punti dati. Prova a correggere alcuni aspetti negativi del sistema Elo.

In base alla tua domanda, probabilmente vorrai uno di questi sistemi, anche se non te ne rendi ancora conto.

    
risposta data 08.07.2015 - 03:17
fonte
1

Sembra che tu abbia a che fare con un set di arco di feedback . Poiché ogni squadra gioca più di una volta, stai considerando una situazione più complessa del caso minimo, anche se potresti teoricamente fare il numero di vittorie come un peso e comunque finire con un caso limitato che ha un soluzione approssimativa valida in O (log | V | loglog | V |) time.

    
risposta data 12.06.2014 - 05:41
fonte
1

Se questo è un problema di vita reale, devi aspettarti dati inconsistenti, come A batte B, B batte C, C batte A. Hai già mostrato un'infinità di informazioni: A giocava B e D tre volte ciascuno, ma non non suonare affatto

Creo un modello che descriva la probabilità di una squadra di battere un altro team e di trovare valori che concordino meglio con il modello. Ad esempio "ogni squadra ha una forza da 0 a 10. Se una squadra è più strong di un ammontare x ≥ 0 di un'altra squadra, allora la squadra verrà battuta con probabilità 1 - exp (-x ^ 2) / 2". Quindi con identiche possibilità di forza sono pari, ma è molto probabile che una squadra molto più strong vinca la maggior parte dei giochi.

Potresti iniziare con un'ipotesi iniziale che ogni squadra ha una forza di 5 e stimare le possibilità di ottenere il risultato dei tuoi dati. Quindi modifichi i dati casualmente e controlla se ciò migliora le possibilità di ottenere i tuoi dati.

    
risposta data 09.04.2015 - 01:32
fonte

Leggi altre domande sui tag