Как я упоминал в предыдущем посте в блоге, я изучал системы ранжирования, и одной из первых, с которой я столкнулся, была система рейтингов Elo, которая наиболее широко используется для ранжирования шахматистов.
Система рейтинга Elo использует следующую формулу для определения рейтинга игрока / команды после того, как они приняли участие в матче:
R ‘= R + K * (S — E)
- R ‘- новый рейтинг
- R старый рейтинг
- K — максимальное значение для увеличения или уменьшения рейтинга (16 или 32 для ELO)
- S — счет за игру
- E — ожидаемый результат игры
Я преобразовал эту формулу в следующие функции Clojure:
01
02
03
04
05
06
07
08
09
10
11
|
(defn ranking-after-win [{ ranking :ranking opponent-ranking : opponent-ranking importance :importance}] (+ ranking (* importance (- 1 (expected ranking opponent-ranking) )))) (defn ranking-after-loss [{ ranking :ranking opponent-ranking : opponent-ranking importance :importance}] (+ ranking (* importance (- 0 (expected ranking opponent-ranking) )))) (defn expected [my-ranking opponent-ranking] (/ 1.0 (+ 1 (math/expt 10 (/ (- opponent-ranking my-ranking) 400 ))))) |
который будет назван так, чтобы выработать новый рейтинг команды с рейтингом 1200, которая превзойдет команду с рейтингом 1500:
1
2
|
> (ranking-after-win { :ranking 1200 : opponent-ranking 1500 :importance 32 }) 1227.1686541692377 |
То, как это работает, заключается в том, что мы сначала выясняем вероятность того, что мы должны выиграть матч, позвонив ожидаемо :
1
2
|
> (expected 1200 1500 ) 0.15097955721132328 |
Это говорит нам о том, что у нас есть 15% -ный шанс выиграть матч, поэтому, если мы выиграем, наш рейтинг должен быть увеличен на большую сумму, поскольку мы не ожидаем, что выиграем. В этом случае выигрыш дает нам увеличение очков на «32 * (1-0,15)», что составляет ~ 27 баллов.
Я держал вещи простыми, всегда устанавливая значение / максимальное значение увеличения или уменьшения до 32. Мировые футбольные рейтинги использовали другой подход, в котором они варьируются в зависимости от важности матча и предела победы.
Я решил опробовать алгоритм в сезоне Лиги чемпионов 2002/2003. Мне удалось получить данные из Фонда спортивной футбольной статистики Rec, и я ранее писал о том, как я их очистил с помощью Enlive .
С большой помощью Пола Бострома я в итоге получил следующий код для выполнения сокращения по матчам при обновлении рейтинга команд после каждого матча:
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
(defn top-teams [number matches] (let [teams-with-rankings (apply array-map (mapcat (fn [x] [x {:points 1200 }]) (extract-teams matches)))] (take number (sort-by (fn [x] (:points (val x))) > (seq (reduce process-match teams-with-rankings matches)))))) (defn process-match [ts match] (let [{:keys [home away home_score away_score]} match] (cond (> home_score away_score) (-> ts (update-in [home :points] #(ranking-after-win {:ranking % : opponent-ranking (:points (get ts away)) :importance 32 })) (update-in [away :points] #(ranking-after-loss {:ranking % : opponent-ranking (:points (get ts home)) :importance 32 }))) (> away_score home_score) (-> ts (update-in [home :points] #(ranking-after-loss {:ranking % : opponent-ranking (:points (get ts away)) :importance 32 })) (update-in [away :points] #(ranking-after-win {:ranking % : opponent-ranking (:points (get ts home)) :importance 32 }))) (= home_score away_score) ts))) |
Параметр match, который мы передаем в топ-команды, выглядит следующим образом :
1
2
|
> (take 5 all-matches) ({:home "Tampere" , :away "Pyunik Erewan" , :home_score 0 , :away_score 4 } {:home "Pyunik Erewan" , :away "Tampere" , :home_score 2 , :away_score 0 } {:home "Skonto Riga" , :away "Barry Town" , :home_score 5 , :away_score 0 } {:home "Barry Town" , :away "Skonto Riga" , :home_score 0 , :away_score 1 } {:home "Portadown" , :away "Belshina Bobruisk" , :home_score 0 , :away_score 0 }) |
И вызывая к нему команды extract, мы получаем набор всех задействованных команд:
1
2
|
> (extract-teams (take 5 all-matches)) #{ "Portadown" "Tampere" "Pyunik Erewan" "Barry Town" "Skonto Riga" } |
Затем мы сопоставляем его с mapcat, чтобы получить вектор, содержащий пары точек team / default:
1
2
|
> (mapcat (fn [x] [x {:points 1200 }]) (extract-teams (take 5 all-matches))) ( "Portadown" {:points 1200 } "Tampere" {:points 1200 } "Pyunik Erewan" {:points 1200 } "Barry Town" {:points 1200 } "Skonto Riga" {:points 1200 }) |
перед вызовом array-map сделать хеш результата:
1
2
|
> (apply array-map (mapcat (fn [x] [x {:points 1200 }]) (extract-teams (take 5 all-matches)))) { "Portadown" {:points 1200 }, "Tampere" {:points 1200 }, "Pyunik Erewan" {:points 1200 }, "Barry Town" {:points 1200 }, "Skonto Riga" {:points 1200 }} |
Затем мы применяем сокращение ко всем совпадениям и вызываем функцию process-match на каждой итерации, чтобы соответствующим образом обновлять рейтинги команд. Последний шаг — отсортировать команды по рейтингу, чтобы мы могли составить список лучших команд:
01
02
03
04
05
06
07
08
09
10
11
|
> (top-teams 10 all-matches) ([ "CF Barcelona" {:points 1343.900393287903 }] [ "Manchester United" {:points 1292.4731214788262 }] [ "FC Valencia" {:points 1277.1820905112208 }] [ "Internazionale Milaan" {:points 1269.8028023141364 }] [ "AC Milan" {:points 1257.4564374787687 }] [ "Juventus Turijn" {:points 1254.2498432522466 }] [ "Real Madrid" {:points 1248.0758162475993 }] [ "Deportivo La Coruna" {:points 1235.7792317210403 }] [ "Borussia Dortmund" {:points 1231.1671952364256 }] [ "Sparta Praag" {:points 1229.3249513256828 }]) |
Интересно, что победители (Ювентус) находятся только на 5-м месте, а первые 2 места занимают команды, проигравшие в четвертьфинале. Я написал следующие функции, чтобы выяснить, что происходит:
1
2
3
4
5
6
7
8
9
|
(defn show-matches [team matches] (->> matches (filter #(or (= team (:home %)) (= team (:away %)))) (map #(show-opposition team %)))) (defn show-opposition [team match] ( if (= team (:home match)) {:opposition (:away match) :score (str (:home_score match) "-" (:away_score match))} {:opposition (:home match) :score (str (:away_score match) "-" (:home_score match))})) |
Если мы назовем это с Ювентусом, мы увидим, как они выступили в своих матчах:
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
|
ranking-algorithms.parse> (show-matches "Juventus Turijn" all-matches) ({:opposition "Feyenoord" , :score "1-1" } {:opposition "Dynamo Kiev" , :score "5-0" } {:opposition "Newcastle United" , :score "2-0" } {:opposition "Newcastle United" , :score "0-1" } {:opposition "Feyenoord" , :score "2-0" } {:opposition "Dynamo Kiev" , :score "2-1" } {:opposition "Deportivo La Coruna" , :score "2-2" } {:opposition "FC Basel" , :score "4-0" } {:opposition "Manchester United" , :score "1-2" } {:opposition "Manchester United" , :score "0-3" } {:opposition "Deportivo La Coruna" , :score "3-2" } {:opposition "FC Basel" , :score "1-2" } {:opposition "CF Barcelona" , :score "1-1" } {:opposition "CF Barcelona" , :score "2-1" } {:opposition "Real Madrid" , :score "1-2" } {:opposition "Real Madrid" , :score "3-1" }) |
Хотя я пропускаю финал — мне нужно исправить парсер, чтобы подобрать этот матч, и в любом случае это была ничья — они фактически выиграли только 8 из своих матчей. Барселона, с другой стороны, выиграла 13 матчей, хотя 2 из них были квалификационными.
Следующий шаг — принять во внимание важность матча, а не применять значение 32 по всем направлениям и добавить некоторую ценность к победе в ничьей / матче, даже если это на пенальти или голах.
Код на github, если вы хотите поиграть с ним или есть предложения для чего-то еще, я могу попробовать.