Classification de l'arbre de décision

Introduction

Les arbres de décision (DT) sont une méthode d'apprentissage supervisé non paramétrique utilisée pour la classification et la régression. L'objectif est de créer un modèle qui prédit la valeur d'une variable cible en apprenant des règles de décision simples déduites des caractéristiques des données.

Entropie

Le but de la formation est de trouver les meilleurs splits dans les nœuds afin de trouver l'arbre le plus optimal. Les fractionnements se font en utilisant certains critères tels que : Entropie.

Il existe de nombreuses définitions de l'entropie telles que :

L'entropie correspond à la quantité d'informations contenues dans une source d'information.
L'entropie peut aussi être vue comme le caractère aléatoire ou la mesure de la surprise dans un ensemble.
L'entropie est une métrique qui mesure l'imprévisibilité ou l'impureté du système.

Dans les arbres de décision, nous considérerons l’entropie comme la mesure de la pureté à l’intérieur d’un nœud. L'objectif du modèle d'arbre de décision est de réduire l'entropie des nœuds à chaque scission :

Ainsi, nous voulons maximiser la différence entre l’entropie du nœud parent et l’entropie des nœuds enfants. Cette différence est appelée le gain d'information.

L'Entropie $H$ d'un ensemble $X$ est mathématiquement formulée comme suit :

H(X) = - \sum\limits\_{x \in X} p(x) \log p(x)

Gain d'informations

Le gain d'information est la différence entre l'entropie du nœud parent et la somme pondérée des entropies des nœuds enfants, et il peut donc être formulé comme suit :

$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$

$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$

où:

$H(.)$ est l'entropie.
$Y$ est la population avant la scission, elle représente le nœud parent.
$X$ est la variable que l'on souhaite utiliser pour le fractionnement.
$x$ est une valeur unique de X.
$Y[X==x]$ est une liste divisée avec seulement des valeurs $x$ .

Prenons un exemple approprié :

Nous allons calculer le gain d'information lorsque nous divisons le nœud parent en utilisant les valeurs de X :

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

Tout d’abord, nous calculons l’entropie du nœud parent :

$H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow)$

$= - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3$

Ensuite, nous allons calculer la probabilité interne de chaque nœud enfant après la scission en utilisant les valeurs uniques de X :

$unique(X) = [Circle, Square]$

$\sum\_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square)$

$+ P(Circle|X) \times H(Y | X = Circle)$

$= \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle)$

Tel que:

$H(Y | X = Square)$ : représente l'entropie du premier nœud enfant.
$H(Y | X = Circle)$ : représente l'entropie du deuxième nœud enfant.

Nous commençons par le premier nœud enfant :

$H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square)$

$- P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square)$

$= - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23$

Et puis le deuxième nœud enfant :

$H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle)$

$- P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle)$

$= - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28$

Enfin, nous substituons les entropies dans la formule de gain d'information :

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

$= 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041$

Comme indiqué précédemment, l'objectif d'une division de nœud est de maximiser le gain d'information, et ainsi de minimiser l'entropie dans le nœud enfant résultant. Pour ce faire, nous devons essayer de diviser le nœud avec différents ensembles d'entrées $X_1, X_2, \ldots, Xn$ et nous ne conservons que la division qui maximise le gain d'information :

$X^{\*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i)$

Quand arrêter le fractionnement

La division des nœuds dans les arbres de décision est récursive, il doit donc y avoir un critère que nous pouvons utiliser pour arrêter la division. Voici quelques-uns des critères les plus mis en œuvre :

Lorsque le nœud est pur : H(node) = 0. Il est inutile de diviser davantage le nœud.
Nombre maximum de profondeur : Nous pouvons définir une profondeur maximale que le modèle peut atteindre, cela signifie que même si le nœud n'est pas pur, le fractionnement est arrêté.
Nombre minimum d'échantillons par nœud : Nous pouvons également définir un nombre minimum $N$ d'échantillons par nœud. Si le nombre d'échantillons par nœud est égal à $N$ alors on arrête le fractionnement même si le nœud n'est pas pur.

À la fin de l'entraînement (le fractionnement), chaque nœud qui s'appuie sur la fin de l'arbre de décision est appelé une "Feuille", car il ne s'agit d'une racine d'aucun sous-arbre. Chaque feuille représentera le rendement de la classe avec le plus d'échantillons.

Conclusion

L'arbre de décision est l'un des algorithmes d'apprentissage automatique les plus connus en raison de son efficacité, de son contexte intuitif et de sa mise en œuvre simple. Cet algorithme peut en outre être utilisé avec des variables indépendantes numériques (arbre de décision gaussien) et il peut également être étendu pour résoudre des tâches de régression.