Arbres de Décision

• Intuition :
  • Divisez les données d'entraînement en fonction de "la meilleure" question (e.g. est-il plus âgé que 27 ans ?). Divisez récursivement les données tant que vous n'êtes pas satisfait des résultats de classification.
  • Les arbres de décision sont essentiellement l'algorithme à utiliser pour le jeu des "20 questions". Akinator est un bon exemple de ce qui peut être implémenté avec des arbres de décision. Akinator est probablement basé sur des systèmes experts de logique floue (car il peut fonctionner avec des réponses erronées), mais vous pourriez faire une version plus simple avec des arbres de décision.
  • Les divisions "optimales" sont trouvées par maximisation du gain d'information ou des méthodes similaires.
• Pratique :
  • Les arbres de décision sont performants lorsque vous avez besoin d'un modèle simple et interprétable, mais que la relation entre $y$ et $\mathbf{x}$ est complexe.
  • Complexité d'entraînement : $O(MND + ND\log(N) )$ .
  • Complexité de test : $O(MT)$ .
  • Notation utilisée : $M=profondeur$ ; \(N= \#_{train}\) ; \(D= \#_{features}\) ; \(T= \#_{test}\).
• Avantage :
  • Interprétable .
  • Peu d'hyper-paramètres.
  • Nécessite moins de nettoyage de données :
    • Pas de normalisation nécessaire.
    • Peut gérer les valeurs manquantes.
    • Gère les variables numériques et catégorielles.
  • Robuste aux valeurs aberrantes.
  • Ne fait pas d'hypothèses sur la distribution des données.
  • Effectue une sélection de caractéristiques.
  • S'adapte bien à l'échelle.
• Inconvénient :
  • Précision généralement faible en raison de la sélection gloutonne.
  • Forte variance car si la première division change, tout le reste change.
  • Les divisions sont parallèles aux axes des caractéristiques => besoin de multiples divisions pour séparer 2 classes avec une frontière de décision à 45°.
  • Pas d'apprentissage en ligne.

L'idée derrière les arbres de décision est de partitionner l'espace d'entrée en plusieurs régions. Par exemple : région des hommes de plus de 27 ans. Ensuite, prédire la classe la plus probable pour chaque région en assignant la modalité des données d'entraînement dans cette région. Malheureusement, trouver une partition optimale est généralement infaisable en termes de calcul (NP-complet) en raison du nombre combinatoire de possibles arbres. En pratique, les différents algorithmes utilisent donc une approche gloutonne. C'est-à-dire chaque division de l'arbre de décision essaie de maximiser un certain critère sans tenir compte des divisions suivantes.

Comment définir un critère d'optimalité pour une division ? Définissons une impureté (erreur) de l'état actuel, que nous allons essayer de minimiser. Voici 3 impuretés d'état possibles :

• Erreur de Classification :
  • L'erreur de précision : $1-Acc$ de l'état actuel. C'est-à-dire l'erreur que nous commettrions en nous arrêtant à l'état actuel.
  • \[ErreurClassification = 1 - \max_c (p(c))\]
• Entropie :
  • À quel point les classes de l'état actuel sont-elles imprévisibles.
  • Minimiser l'entropie correspond à maximiser le gain d'information.
  • \[Entropie = - \sum_{c=1}^C p(c) \log_2 \ p(c)\]
• Impureté de Gini :
  • Probabilité attendue ($\mathbb{E}[\cdot] = \sum_{c=1}^C p(c) (\cdot) $) de mauvaise classification ($\sum_{c=1}^C p(c) (1-\cdot)$) d'un élément sélectionné au hasard, s'il était classé selon la distribution des étiquettes ($\sum_{c=1}^C p(c) (1-p(c))$).
  • \[ErreurClassification = \sum_c^C p_c (1-p_c) = 1- \sum_c^C p_c^2\]

Voici un graphique rapide montrant l'impureté en fonction de la distribution des classes dans un cadre binaire :

Notes annexes :

• L'erreur de classification peut sembler un choix naturel, mais ne vous laissez pas tromper par les apparences : elle est généralement moins performante que les 2 autres méthodes :
  • Elle est "plus" gloutonne que les autres. En effet, elle ne se concentre que sur l'erreur actuelle, tandis que Gini et l'Entropie essaient de faire une division plus pure qui facilitera les étapes suivantes. Supposons que nous ayons une classification binaire avec 100 observations dans chaque classe $(100,100)$. Comparons une division qui sépare les données en $(20,80)$ et $(80,20)$, à une autre qui les divise en $(40,100)$ et $(60,0)$. Dans les deux cas, l'erreur de précision serait de $0,20\%$. Mais nous préférerions le deuxième cas, qui est pur et n'aura pas besoin d'être divisé davantage. L'impureté de Gini et l'Entropie choisiraient correctement ce dernier.
  • L'erreur de classification ne prend en compte que la classe la plus probable. Ainsi, avoir une division avec 2 classes extrêmement probables aura une erreur similaire à une division avec une classe extrêmement probable et plusieurs classes improbables.
• L'impureté de Gini et l'Entropie diffèrent moins de 2% du temps comme vous pouvez le voir dans le graphique ci-dessus. L'Entropie est un peu plus lente à calculer en raison de l'opération logarithmique.

Quand devons-nous arrêter de diviser ? Il est important de ne pas diviser trop de fois pour éviter le sur-apprentissage. Voici quelques heuristiques qui peuvent être utilisées comme critère d'arrêt :

• Lorsque le nombre d'exemples d'entraînement dans un nœud feuille est faible.
• Lorsque la profondeur atteint un seuil.
• Lorsque l'impureté est faible.
• Lorsque le gain de pureté dû à la division est faible.

Ces heuristiques nécessitent des seuils dépendants du problème (hyperparamètres) et peuvent donner des résultats relativement mauvais. Par exemple, les arbres de décision peuvent devoir diviser les données sans aucun gain de pureté pour atteindre de hauts gains de pureté à l'étape suivante. Il est donc courant de développer de grands arbres en utilisant le nombre d'exemples d'entraînement dans un nœud feuille comme critère d'arrêt. Pour éviter le sur-apprentissage, l'algorithme élaguera ensuite l'arbre résultant. Dans CART, le critère d'élagage $C_{pruning}(T)$ équilibre l'impureté et la complexité du modèle par régularisation. La variable régularisée est souvent le nombre de nœuds feuille $\vert T \vert$, comme ci-dessous :

$\lambda$ est sélectionné via validation croisée et fait un compromis entre l'impureté et la complexité du modèle, pour un arbre donné $T$, avec les nœuds feuille $v=1…\vert T \vert$ utilisant la mesure d'impureté $I$.

Variantes : il existe différentes méthodes d'arbres de décision, qui diffèrent selon les points suivants :

• Critère de division ? Gini / Entropie.
• Technique pour réduire le sur-apprentissage ?
• Combien de variables peuvent être utilisées dans une division ?
• Création d'arbres binaires ?
• Gestion des valeurs manquantes ?
• Peuvent-ils gérer la régression ?
• Robustesse aux valeurs aberrantes ?

Variantes célèbres :

• ID3 : première implémentation d'arbre de décision. Pas utilisé en pratique.
• C4.5 : Amélioration par rapport à ID3 par le même développeur. Élagage basé sur l'erreur. Utilise l'entropie. Gère les valeurs manquantes. Sensible aux valeurs aberrantes. Peut créer des branches vides.
• CART : Utilise Gini. Élagage basé sur la complexité des coûts. Arbres binaires. Gère les valeurs manquantes. Gère la régression. Pas sensible aux valeurs aberrantes.
• CHAID : Trouve une variable de division en utilisant le test du Chi-carré pour tester la dépendance entre une variable et une réponse. Pas d'élagage. Semble mieux pour décrire les données, mais moins performant pour la prédiction.

Autres variantes : C5.0 (version suivante de C4.5, probablement moins utilisée car brevetée), MARS.

Ressources : Une étude comparative de différentes méthodes d'arbres de décision.

• Pseudocode La version simple d'un arbre de décision peut être écrite en quelques lignes de pseudocode Python :

def construireArbre(X,Y):
    if critere_arret(X,Y) :
        # si arrêt, alors stocker la classe majoritaire
        arbre.classe = mode(X) 
        return Null

    impureteMin = infini
    meilleureDivision = None
    for j in caracteristiques:
        for T in seuils:
            if impurete(X,Y,j,T) < impureteMin:
                meilleureDivision = (j,T)
                impureteMin = impurete(X,Y,j,T) 

    X_gauche, Y_gauche, X_droite, Y_droite = diviser(X,Y,meilleureDivision)

    arbre.division = meilleureDivision # ajoute la division actuelle
    arbre.gauche = construireArbre(X_gauche, Y_gauche) # ajoute les divisions suivantes à gauche
    arbre.droite = construireArbre(X_droite, Y_droite) # ajoute les divisions suivantes à droite

return arbre

def predireUnArbre(arbre, xi):
    if arbre.classe n'est pas Null:
        return arbre.classe

    j, T = arbre.division
    if xi[j] >= T:
        return predireUnArbre(arbre.droite, xi)
    else:
        return predireUnArbre(arbre.gauche, xi)

def predireTousArbre(arbre, Xt):
    t, d = Xt.shape
    Yt = vecteur(d)
    for i in t:
        Yt[i] = predireUnArbre(arbre, Xt[i,:])

    return Yt

• Complexité Je vais utiliser la notation suivante : \(M=profondeur\) ; \(K=\#_{seuils}\) ; \(N = \#_{train}\) ; \(D = \#_{caractéristiques}\) ; \(T = \#_{test}\).

Commençons par réfléchir à la complexité de la construction de la première souche de décision (premier appel de fonction) :

• Dans une souche de décision, nous bouclons sur toutes les caractéristiques et les seuils $O(KD)$, puis nous calculons l'impureté. L'impureté dépend uniquement des probabilités de classe. Calculer les probabilités signifie boucler sur tous les $X$ et compter les $Y$ : $O(N)$. Avec ce pseudocode simple, la complexité temporelle pour construire une souche est donc $O(KDN)$.
• En réalité, nous n'avons pas besoin de rechercher des seuils arbitraires, uniquement pour les valeurs uniques prises par au moins un exemple. Par exemple, pas besoin de tester $caractéristique_j>0.11$ et $caractéristique_j>0.12$ lorsque toutes les $caractéristique_j$ sont soit $0.10$ soit $0.80$. Remplaçons le nombre de seuils possibles $K$ par la taille du jeu d'entraînement $N$. $O(N^2D)$
• Actuellement, nous bouclons deux fois sur tous les $X$, une fois pour le seuil et une fois pour calculer l'impureté. Si les données étaient triées par la caractéristique actuelle, l'impureté pourrait simplement être mise à jour au fur et à mesure que nous parcourons les exemples. Par exemple, en considérant la règle $caractéristique_j>0.8$ après avoir déjà considéré $caractéristique_j>0.7$, nous n'avons pas besoin de recalculer toutes les probabilités de classe : nous pouvons simplement prendre les probabilités de $caractéristique_j>0.7$ et faire les ajustements en connaissant le nombre d'exemples avec $caractéristique_j==0.7$. Pour chaque caractéristique $j$, nous devons d'abord trier toutes les données $O(N\log(N))$, puis boucler une fois en $O(N)$, la finalité serait en $O(DN\log(N))$.

Nous avons maintenant la complexité d'une souche de décision. Vous pourriez penser que trouver la complexité de la construction d'un arbre serait de la multiplier par le nombre d'appels de fonction : Vrai ? Pas vraiment, ce serait une surestimation. En effet, à chaque appel de fonction, la taille des données d'entraînement $N$ aura diminué. L'intuition du résultat que nous recherchons est qu'à chaque niveau $l=1…M$, la somme des données d'entraînement dans chaque fonction est toujours $N$. Plusieurs fonctions travaillant en parallèle avec un sous-ensemble d'exemples prennent le même temps qu'une seule fonction avec l'ensemble d'entraînement complet $N$. La complexité à chaque niveau est donc toujours $O(DN\log(N))$, donc la complexité pour construire un arbre de profondeur $M$ est $O(MDN\log(N))$. Preuve que le travail à chaque niveau reste constant :

À chaque itération, le jeu de données est divisé en $\nu$ sous-ensembles de $k_i$ éléments et un ensemble de $n-\sum_{i=1}^{\nu} k_i$. À chaque niveau, le coût total serait donc (en utilisant les propriétés des logarithmes et le fait que $k_i \le N$ ) :

Le dernier ajustement possible que je vois est de tout trier une fois, de le stocker et d'utiliser simplement ces données pré-calculées à chaque niveau. La complexité d'entraînement finale est donc $O(MDN + ND\log(N))$ .

La complexité temporelle pour faire des prédictions est simple : pour chaque $t$ exemple, parcourez une question à chaque niveau $M$. C'est-à-dire $O(MT)$ .