Un arbre de classification résulte d’un partitionnement récursif binaire de l’ensemble de données d’apprentissage d’origine. Tout nœud parent (sous-ensemble de données d’apprentissage) dans un arbre peut être divisé en deux nœuds enfants qui s’excluent mutuellement d’un nombre limité de façons, en fonction des valeurs réelles des données recueillies dans le nœud.

La procédure de partition traite les variables de prédiction comme étant continues ou de catégorie. Pour une variable continue X et une valeur c, la division est définie par l’envoi de toutes les données avec des valeurs de X inférieures ou égales à c au nœud gauche, et de toutes les données restantes au nœud droit. CART utilise toujours la moyenne de deux valeurs adjacentes afin de calculer c. Une variable continue avec N valeurs distinctes génère jusqu’à N-1 divisions potentielles du nœud parent (le nombre réel sera plus petit lorsque des limites sur la taille minimale autorisée du nœud sont imposées).

Par exemple, un prédicteur continu comprend les valeurs 55, 66 et 75. Il est possible de diviser cette variable en envoyant toutes les valeurs inférieures ou égales à (55+66)/2 = 60,5 à un nœud enfant et toutes les valeurs supérieures à 60,5 à l’autre nœud enfant. Les cas avec la valeur de prédiction 55 sont envoyés à un nœud et les cas avec les valeurs 66 et 75 sont envoyés à l’autre nœud. Il est également possible de diviser cette variable de prédiction en envoyant toutes les valeurs inférieures ou égales à 70,5 à un nœud enfant et toutes les valeurs supérieures à 70,5 à l’autre nœud. Les cas avec les valeurs 55 et 66 sont envoyés à un nœud et les cas avec la valeur 75 sont envoyés à l’autre nœud.

Pour une variable de catégorie X avec des valeurs distinctes {c1, c2, …, ck}, une division est définie comme un sous-ensemble de niveaux qui sont envoyés au nœud enfant gauche. Une variable de catégorie avec K niveaux génère jusqu’à 2K-1–1 divisions.

Par exemple, une variable de catégorie comprend les valeurs Rouge, Bleu et Jaune. Ce nœud peut créer trois divisions différentes :
Nœud enfant gauche Nœud enfant droit
Rouge, Bleu Jaune
Rouge, Jaune Bleu
Bleu, Jaune Rouge

Dans les arbres de classification, la cible est multinomiale avec K classes distinctes. L’objectif principal de l’arbre est de trouver un moyen de séparer les différentes classes cibles en nœuds individuels de la manière la plus pure possible. Le nombre de nœuds terminaux qui en résulte n’a pas besoin d’être K. Plusieurs nœuds terminaux peuvent être utilisés pour représenter une classe cible spécifique. Un utilisateur peut spécifier les probabilités antérieures pour les classes cibles et ces probabilités seront comptabilisées par CART pendant le processus de croissance des arbres.

Dans les sections suivantes, Minitab utilise les définitions suivantes pour une variable de réponse binaire :

Probabilité conditionnelle d’un événement étant donné que le cas se trouve dans le nœud t
Probabilité conditionnelle d’un non-événement étant donné que le cas se trouve dans le nœud t:

Dans les sections suivantes, Minitab utilise les définitions suivantes pour une variable de réponse multinomiale :

Probabilité a priori du nœud t :

Probabilité de classe j nœud donné t:

Ces définitions donnent les probabilités à l’intérieur du nœud. Minitab calcule ces probabilités pour n’importe quel nœud et n’importe quelle division potentielle. Minitab calcule l’amélioration globale d’une division potentielle de ces probabilités avec l’un des critères suivants.

Notation

TermeDescription
Knombre de classes dans la variable de réponse
probabilité a priori pour la classe j
nombre d’observations pour la classe j dans un nœud
nombre d’observations pour la classe j dans les données

Critère de Gini

Pour une variable de réponse binaire, la formule suivante donne l’impureté du nœud :

La formule plus générale suivante s’applique à une variable de réponse multinomiale :

Notez que si toutes les observations pour un nœud sont dans une classe, alors .

Critère d’entropie

Pour une variable de réponse binaire, la formule suivante donne l’impureté du nœud :

La formule plus générale suivante s’applique à une variable de réponse multinomiale :

Notez que si toutes les observations pour un nœud sont dans une classe, alors .

Critère de twoing

Avec une réponse multinomiale, Minitab offre le critère de twoing. Les approches de calcul de l’amélioration des critères de Gini et d’entropie traitent l’une comme l’autre les classes cibles individuelles comme des entités distinctes. Cependant, il est également possible de combiner toutes les classes cibles disponibles en deux super classes qui s’excluent mutuellement. Par exemple, si la variable de réponse comprend les classes 1, 2, 3 et 4, alors le tableau suivant donne les ensembles possibles de super classes :
Super classe 1 Super classe 2
1, 2, 3 4
1, 2, 3 3
1, 3, 4 2
2, 3, 4 1
1, 2 3, 4
1, 3 2, 4
1, 4 2, 3
Minitab évalue les résultats comme s’il s’agissait d’un cas de classification binaire en utilisant la formule d’amélioration du critère de Gini. L’amélioration est la meilleure amélioration binaire du critère de Gini pour toutes les super classes. Les probabilités à l’intérieur du nœud des enfants gauche et droit de toute division possible indiquent la meilleure super classe possible. Il n’est donc pas nécessaire d’évaluer toutes les super classes pour chaque division candidate. Les règles suivantes déterminent les super classes optimales pour la division candidate :

La super classe gauche comprend toutes les classes cibles qui ont tendance à aller à gauche. La super classe droite comprend toutes les classes cibles qui ont tendance à aller à droite.

Supposons, par exemple, que les résultats potentiels d’une variable de réponse soient 1, 2, 3 et 4. Le tableau suivant donne les probabilités de nœud pour la division candidate :
Classe Probabilité de nœud enfant gauche Probabilité de nœud enfant droit
1 0,67 0,33
2 0,82 0,18
3 0,23 0,77
4 0,89 0,11

Ensuite, la meilleure façon de créer les super classes pour la division candidate est de définir que {1, 2, 4} est une super classe et {3} l’autre super classe.

Le reste du calcul est identique au calcul du critère de Gini avec les super classes comme cible binaire.

Calcul de l’amélioration des critères

Une fois l’impureté du nœud calculée, Minitab calcule les probabilités conditionnelles de division du nœud avec un prédicteur :

et

Ensuite, l’amélioration d’une division provient de la formule suivante :

La division avec la valeur d’amélioration la plus élevée devient une partie de l’arbre.

Probabilité de classe

Les partitions de nœuds maximisent la probabilité d’une classe dans un nœud donné.

Nœuds terminaux

Lors du processus de partition des nœuds, trois conditions créent un nœud terminal. Si l’une des trois conditions s’applique, alors un nœud devient un nœud terminal. Une fois qu’un nœud est un nœud terminal, aucune autre évaluation n’est effectuée pour diviser le nœud. Voici les trois conditions :
  • Le nombre de cas dans le nœud atteint la taille minimale pour l’analyse. Le minimum par défaut dans Minitab Statistical Software est de 3.
  • Tous les cas d’un nœud ont la même classe de réponse.
  • Tous les cas d’un nœud ont les mêmes valeurs de prédiction.

Classe prévue pour un nœud terminal

La classe prévue pour un nœud terminal est la classe qui minimise le coût de mauvais classement pour le nœud. Les représentations du coût de mauvais classement dépendent du nombre de classes dans la variable de réponse. Etant donné que la classe prévue pour un nœud terminal provient des données d’apprentissage lorsque vous utilisez une méthode de validation, toutes les formules suivantes utilisent les probabilités de l’ensemble de données d’apprentissage.

Variable de réponse binaire

L’équation suivante donne le coût de mauvais classement pour la prédiction que les cas dans le nœud appartiennent à la classe d’événement :

L’équation suivante donne le coût de mauvais classement pour la prédiction que les cas dans le nœud appartiennent à la classe de non-événement :

TermeDescription
PY=0|tprobabilité conditionnelle qu’un cas dans le nœud t appartienne à la classe de non-événement
C1|0coût de mauvais classement lorsque le modèle prédit à tort qu’un cas appartient à de la classe d’événement
PY=1|tprobabilité conditionnelle qu’un cas dans le nœud t appartienne à la classe d’événement
C0|1coût de mauvais classement lorsque le modèle prédit à tort qu’un cas appartient à de la classe de non-événement

La classe prévue pour un nœud terminal est la classe avec le coût minimum de mauvais classement.

Variable de réponse multinomiale

Pour le cas multinomial, l’équation étend la formule de la variable de réponse binaire pour tenir compte de tous les types possibles de mauvais classements. Par exemple, pour une réponse multinomiale avec k classes, le coût de mauvais classement pour Y = 1 est déterminé par l’équation suivante :

Prenons, par exemple, une variable de réponse avec trois classes et les coûts de mauvais classement suivants :

Classe prévue
Classe réelle 1 2 3
1 0,0 4,1 3,2
2 5,6 0,0 1,1
3 0,4 0,9 0,0

Ensuite, considérez que les classes de la variable de réponse ont les probabilités suivantes pour le nœud t:

Les équations suivantes donnent les coûts associés au mauvais classement pour chaque classe dans la variable de réponse :

Le coût de mauvais classement le moins élevé est celui de la prédiction Y = 3, 1,164. Cette classe est la classe prévue pour le nœud terminal.

En utilisant ce site, vous acceptez l'utilisation de cookies à des fins d'analyse et de personnalisation du contenu.  Lisez notre politique