Arbres de décision : entropie et gain

Un arbre de décision est un modèle qui pose une suite de questions simples, comme « l’étudiant est-il assidu ? », pour arriver à une réponse. Pour le construire, il faut savoir quelle question poser en premier.

On mesure le désordre d’un groupe avec l’entropie, puis la meilleure question avec le gain d’information.

Dix étudiants passent une épreuve. Cinq réussissent et cinq échouent. Si l’on pioche un étudiant, on ne peut rien prévoir : le désordre est maximal et l’entropie vaut 1.

Si tous réussissent, on sait déjà la réponse : l’entropie vaut 0. Entre les deux, plus un groupe est mélangé, plus son entropie est haute.

import math

def entropie(etiquettes):
    total = len(etiquettes)
    comptes = {}
    for e in etiquettes:
        if e in comptes:
            comptes[e] = comptes[e] + 1
        else:
            comptes[e] = 1
    resultat = 0
    for e in comptes:
        p = comptes[e] / total
        resultat = resultat - p * math.log2(p)
    return resultat

# La réussite de dix étudiants, puis des deux groupes de la question « assidu ? ».
tous = ["oui", "oui", "oui", "non", "oui", "non", "non", "oui", "non", "non"]
assidus = ["oui", "oui", "oui", "non", "oui"]
absents = ["non", "non", "oui", "non", "non"]
print("entropie de départ", round(entropie(tous), 3))
apres = 5 / 10 * entropie(assidus) + 5 / 10 * entropie(absents)
print("entropie après la question", round(apres, 3))
print("gain", round(entropie(tous) - apres, 3))

Une question coupe le groupe en parties. On calcule l’entropie de chaque partie, puis on fait la moyenne en pesant chaque partie par sa taille.

Le gain d’information est l’entropie de départ moins cette moyenne. La meilleure question est celle dont le gain est le plus grand : elle range le mieux.

Revenons aux jours de hires.csv, où un jour est « plein » à 300 locations ou plus. La commande suivante affiche quatre nombres.

Le premier est l’entropie de l’année. Les trois autres sont les gains de trois questions : « est-ce un week-end ? », « fait-il 15 degrés ou plus ? » et « quelle est la météo ? ». Elle ne modifie aucun fichier.

docker exec jupyter python3 -c "import csv, math; L = list(csv.DictReader(open('hires.csv'))); n = len(L); busy = lambda g: sum(1 for r in g if int(r['hires']) >= 300); H = lambda g: -sum(p * math.log2(p) for p in (busy(g) / len(g), 1 - busy(g) / len(g)) if p > 0); gain = lambda gs: H(L) - sum(len(g) / n * H(g) for g in gs); W = [r for r in L if r['weekday'] in ('Sat', 'Sun')]; T = [r for r in L if float(r['temp_c']) >= 15]; print(round(H(L), 3), round(gain([W, [r for r in L if r not in W]]), 3), round(gain([T, [r for r in L if r not in T]]), 3), round(gain([[r for r in L if r['weather'] == w] for w in ('sunny', 'cloudy', 'rainy')]), 3))"

On choisit la question au plus grand gain, on coupe les données en branches, puis on recommence dans chaque branche. On s’arrête quand un groupe est pur ou trop petit.

Au bout de chaque branche, la feuille répond avec l’étiquette la plus fréquente. Pour prévoir un nouveau cas, on suit les réponses de la racine jusqu’à une feuille.

Dans votre carnet, changez le seuil de température de 15 à 10, puis à 20. Calculez à chaque fois le gain avec la même méthode que la commande.

Dites quel seuil sépare le mieux les jours pleins des jours calmes, et pourquoi.