Classer des personnes, calculer des côtes

J’ai revu récemment le film The Social Network, film que je conseille à tous et pour de nombreuses raisons : l’histoire, évidemment, mais également David Fincher à la réalisation, Aaron Sorkin à l’écriture, Jesse Eisenberg et Justin Timberlake devant la caméra. Mais ce qui m’intéresse en l’occurrence, c’est l’algorithme présenté par Eduardo Saverin dans le cadre de la création du site facemash.com et qui permet de classer des personnes en fonction de leurs réussites ou échecs à des duels. Cet algorithme, connu sous le nom de son inventeur comme l’algorithme ELO, est intéressant à plus d’un titre, comme nous l’allons voir dans cet article. Pour une mise en oeuvre, je vous invite à visiter le site www.match2012.fr qui utilise cet algorithme pour classer les candidats à l’élection présidentielle de 2012.

Un classement objectif, une valeur absolue

Tout d’abord, le classement ELO (largement utilisé pour classer les joueurs d’échecs) a cela de particulier qu’il permet de classer des concurrents de façon complètement objective, et en leur affectant une valeur absolue : chaque candidat part d’un classement identique (généralement, un score de 1 500). Partant de là, plusieurs choses vont se produire lors d’un duel entre deux concurrents :

  • tout d’abord, un concurrent présumé meilleur a plus de chances de remporter le duel, et par conséquent moins de mérite;
  • par ailleurs, après un duel, le vainqueur prouve qu’il est un peu meilleur qu’il ne l’était, et le vaincu un peu moins;
  • enfin, et pour faire une analogie avec l’athlétisme, il est largement plus facile de passer de 20 sec à 15 sec pour un 100m que de passer de 11 sec à 10 sec.
L’algorithme ELO prend en compte tous ces paramètres.

L’algorithme ELO

Prenons deux concurrents, A et B; chacun de ces concurrents dispose d’un classement — ou score — sA et sB; pour fixer les esprits dans les calculs que nous effectuerons, disons que sA = 1 400 et que sB = 1600.

Avant le duel

B est donc mieux classé que A; la première étape, avant même que le duel entre A et B n’ait lieu, est de déterminer le résultat attendu de ce duel — un genre de probabilité que l’un ou l’autre gagne. ELO propose l’algorithme suivant :

$eA = 1 / ( 1 + pow(10, ($sB - $sA)/400 ) );

$eB = 1 / ( 1 + pow(10, ($sA - $sB)/400 ) );

Évidemment, comme pour tous les calculs de probabilités, nous pouvons rapidement déterminer que eA + eB = 1.

Ensuite, on constate que le score est logarithmique (ou exponentiel, c’est selon), avec une pondération de 400 : un écart de 400 points suggère une probabilité de réussite 10 fois plus grande (ou plus petite, c’est également selon).

Après le duel

Un des éléments importants de l’algorithme est de ne pas comptabiliser une défaite comme telle, mais simplement de comptabiliser une victoire ou pas de victoire.

Après chaque duel, les scores des deux concurrents sont recalculés fonction du résultat du duel :

nouveauScoreA = ancienScoreA + k X (resDueleA)

En précisant les points suivants :

  • resDuel vaut 1 si A est victorieux et 0 sinon;
  • k est un coefficient plus ou moins grand selon l’ancien score de A (c’est la mise en oeuvre de mon analogie de tout à l’heure avec l’athlétisme).
En fixant k de la façon suivante :
  • si le score est inférieur à 2 000 : k = 32;
  • si le score est inférieur ou égal à 2 400 : k = 24;
  • si le score est supérieur à 2 400 : k = 16.
On peut discuter de ces valeurs, on peut pondérer autant qu’on le souhaite, ce qui est intéressant est que le classement ne s’en retrouve pas changé pour autant, pour peu que les concurrents concourent (si un concurrent n’effectue aucun duel, on pourrait imaginer que son score reste indéfiniment inchangé; ce cas est traitable, mais je ne vais pas le faire — trop fatigué et pas assez intéressé).

Implémentation

Ce n’est bien sûr pas très compliqué, mais histoire de vous simplifier la vie encore un peu, voici la classe Ranking qui permet de calculer les résultats attendus, les valeurs de la constante k et les nouveaux scores selon le résultat d’un duel :

<?
class Ranking {
    public static function getEstimations($rankingA,$rankingB) {
        $estA = 1 / ( 1 + (pow(10,($rankingB - $rankingA)/400)));
        $estB = 1 / ( 1 + (pow(10,($rankingA - $rankingB)/400)));
        return array("A" => $estA, "B" => $estB);
    }

    public static function getConstant($ranking) {
        if ($ranking < 2000)
            return 32;
        if ($ranking < 2401)
            return 24;
        return 16;
    }

    public static function getNewRankings($rankingA,$rankingB,$victoryA) {
        $ests = self::getEstimations($rankingA,$rankingB);
        $newRankA = $rankingA + (self::getConstant($rankingA)*(($victoryA ? 1 : 0) - $ests["A"]));
        $newRankB = $rankingB + (self::getConstant($rankingB)*(($victoryA ? 0 : 1) - $ests["B"]));
        return array("A" => round($newRankA), "B" => round($newRankB));
    }
}
?>

Bilan

J’ai récemment mis cela en oeuvre sur le site www.match2012.fr qui permet de confronter deux à deux, de façon aléatoire, tous les candidats à l’élection présidentielle 2012. Pour des raisons de pertinence, les scores ne seront affichés qu’à partir du 15 octobre (pour éviter d’avoir tous les candidats à 1 500, notamment). Par ailleurs, les scores pris en compte sont à la fois les scores des candidats eux-mêmes, ceux de leur parti et ceux de leur aile politique.

Évidemment, pour que ces résultats soient pertinents, il est nécessaire que de nombreux utilisateurs participent, et qu’ils participent plusieurs fois. Ceci est un message à peine déguisé pour vous demander de tweeter et de facebook-murer sur ce site.

Amusez-vous bien ! Et si vous avez de bonnes idées de classements à mettre en oeuvre, les commentaires sont là pour les présenter…

3 réponses à to “Classer des personnes, calculer des côtes”

  • GreG:

    Yo.

    Je te propose une autre méthode, moins amusante, et plus politique que sportive (ou du moins très contraignante sportivement puisqu’uniquement adaptée aux championnats):

    http://fr.wikipedia.org/wiki/M%C3%A9thode_Condorcet

    ++

  • greg, je sais que je suis ne retard de deux ans sur le sujet mais j’espère que tu lira et répondra à mon commentaire. la méthode Condorcet est restrictive! je pense que quand tu veux faire un système de vote simple et léger, ELO est suffisant, pas que suffisant, énormément adaptée. mais je soutiens ton idée que cette méthode s’adapte au système de vote comme le sport(foot, basket et autre). mais quand on voit les deux méthodes, elles ont sont tellement différentes( sur la démarche et le résultat) que j’aimerais savoir si tu n’en connais pas d’autres.

    en passant, ce suggère, dans ELO, d’intégrer une auto-élimination des candidats dès que sa cote arrive à zero

  • Ne t’inquiète pas, Fabrice, il n’y a pas de retard, puisqu’il n’y avait pas de deadline. J’attends également de lire la réponse de GreG sur le sujet. Pour ma part, je m’interroge également aujourd’hui sur le fait de mettre en place un classement dit « objectif », c’est-à-dire où chaque élément est classé tout à fait indépendamment des autres. Le meilleur exemple (en tout cas, sinon le meilleur, le plus évident) est le ranking d’un moteur de recherche (pensez Google) sur lequel des millions (pour être gentil) de pages sont classées, mais évidemment pas les unes par rapport aux autres. Cela fait intervenir une notion de score, évidemment, mais également une notion d’expiration de ce dernier.

    Il serait intéressant de savoir s’il existe des méthodes formelles sur ce sujet (plutôt que des méthodes empiriques disant « tiens, disons que chaque jour sans être requêtée, une page perd 10 points »).