CART est une méthode d'apprentissage pour la distribution de probabilité conditionnelle de la variable aléatoire de sortie Y étant donné la variable aléatoire d'entrée X.

définition

CART suppose que l'arbre de décision est un arbre binaire et que les valeurs des caractéristiques des nœuds internes sont « oui » et « non ». La branche de gauche est la branche avec la valeur « oui », et la branche de droite est la branche avec la valeur « non ». Un tel arbre de décision équivaut à diviser récursivement chaque caractéristique en deux, à diviser l'espace d'entrée, c'est-à-dire l'espace des caractéristiques, en un nombre fini d'unités, et à déterminer la distribution de probabilité prédite sur ces unités, c'est-à-dire la distribution de probabilité conditionnelle de la sortie dans des conditions d'entrée données.

L'algorithme CART comprend les deux étapes suivantes :

1. Génération d'arbres : générer un arbre de décision basé sur l'ensemble de données de formation. L’arbre de décision généré doit être aussi grand que possible.
2. Élagage des arbres : utilisez l’ensemble de données de validation pour élaguer l’arbre généré et sélectionner le sous-arbre optimal. La fonction de perte minimale est utilisée comme critère d’élagage.

La génération d'un arbre de décision est un processus de construction récursive d'un arbre de décision binaire. Le critère de minimisation de l'erreur carrée est utilisé pour l'arbre de régression et le critère de minimisation de l'indice de Gini est utilisé pour l'arbre de classification pour effectuer la sélection des caractéristiques et générer un arbre binaire.

Génération d'arbres de régression

Supposons que X et Y sont respectivement des vecteurs d’entrée et de sortie, et que Y est une variable continue. Étant donné l'ensemble de données d'entraînement $latex { D}=\left\{\left(x\_{1}, y\_{1}\right),\left(x\_{2}, y\_{2}\right), \ldots,\left(x\_{N}, y\_{N}\right)\right\}$latexD={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}, réfléchissons à la manière de générer un arbre de régression.

Un arbre de régression correspond à une partition de l'espace d'entrée (c'est-à-dire l'espace des caractéristiques) et à la valeur de sortie de chaque unité de la partition. Supposons que l'espace d'entrée a été divisé en M unités $latex R\_{1}, R\_{2}, \ldots, R\_{M}$latexR_1,R_2,…,R_M et qu'il existe une valeur de sortie fixe $latex c\_{m}$latexc_m sur chaque unité $latex R\_{m}$latexR_m. Le modèle d'arbre de régression peut alors être exprimé comme $latex f(x)=\sum\_{m=1}^{M} c\_{m} I\left(x \in R\_{m}\right)$latexf(x)=∑_m=1Mc_mI(x∈R_m)

Lorsque la partition de l'espace d'entrée est déterminée, l'erreur quadratique peut être utilisée$latex \sum\_{x\_{i} \in R\_{m}}\left(y\_{i}-f\left(x\_{i}\right)\right)^{2}$latex∑_x_i∈R_m(y_i−f(x_i))2

Pour représenter l’erreur de prédiction de l’arbre de régression pour les données d’apprentissage, la valeur de sortie optimale de chaque unité est résolue à l’aide du critère de l’erreur carrée minimale. Il est facile de voir que la valeur optimale $latex c\_{m}$latexc_m de l'unité $latex R\_{m}$latexR_m est la moyenne de la sortie $latex y\_{i}$latexy_i pour toutes les instances d'entrée $latex x\_{i}$latexx_i sur $latex R\_{m}$latexR_m, c'est-à-dire

La question est de savoir comment diviser l’espace d’entrée. Ici, nous utilisons une méthode heuristique pour sélectionner le premier j variables $latex x^{(j)}$latexx(j) et les valeurs qu'elle prends , comme variable de segmentation et point de segmentation, et définissent deux régions :

Trouvez ensuite la variable de division optimale j et le point de partage optimal s . Plus précisément, résoudre

Pour les variables d'entrée fixes j Le point de partage optimal peut être trouvé s

Parcourez toutes les variables d'entrée et trouvez la variable de segmentation optimale j , formant une paire $latex (j, s)$latex(j,s), qui à son tour divise l'espace d'entrée en deux régions. Ensuite, le processus de division ci-dessus est répété pour chaque région jusqu’à ce que la condition d’arrêt soit remplie.

Génération d'arbres de classification

L'arbre de classification utilise l'indice de Gini pour sélectionner la fonctionnalité optimale et déterminer le point de coupure binaire optimal pour la fonctionnalité.

Indice de Gini

Dans le processus de classification, en supposant qu'il existe K classes, la probabilité qu'un point d'échantillon appartienne à la k-ième classe est $latex p\_{k}$latexp_k, alors l'indice de Gini de la distribution de probabilité est défini comme :

Pour un problème de classification à deux classes, si la probabilité qu'un point d'échantillon appartienne à la première classe est p, l'indice de Gini de la distribution de probabilité est :

Pour un ensemble d'échantillons D donné, son indice de Gini est :

Parmi eux, $latex C\_{k}$latexC_k est le sous-ensemble d'échantillons dans D appartenant à la k-ième classe, et K est le nombre de classes.

Si l'ensemble d'échantillons D est divisé en deux parties, $latex D\_{1}$latexD_1 et $latex D\_{2}$latexD_2, selon que la caractéristique A prend une certaine valeur possible a, c'est-à-dire :

Alors, sous la condition de la caractéristique A, l'indice de Gini de l'ensemble D est défini comme :

L'indice de Gini $latex {Gini}(D)$latexGini(D) représente l'incertitude de l'ensemble D, et l'indice de Gini $latex {Gini}(D, A)$latexGini(D,A) représente l'incertitude de l'ensemble D après partition par A=a. Plus l’indice de Gini est élevé, plus l’incertitude de l’ensemble d’échantillons est grande, ce qui est similaire à l’entropie.

Algorithmes génératifs

Entrée : ensemble de données d'entraînement D, conditions d'arrêt du calcul

Sortie : arbre de décision CART

Selon l'ensemble de données d'entraînement, en partant du nœud racine, effectuez de manière récursive les opérations suivantes sur chaque nœud pour créer un arbre de décision binaire :

1. Supposons que l’ensemble de données d’entraînement du nœud soit D et calculez le coefficient de Gini des fonctionnalités existantes pour l’ensemble de données. À ce stade, pour chaque caractéristique A, pour chaque valeur possible a, D est divisé en deux parties, $latex D\_{1}$latexD_1 et $latex D\_{2}$latexD_2, selon que le test du point d'échantillonnage A=a est « oui » ou « non », et l'indice de Gini lorsque A=a est calculé
2. Parmi toutes les caractéristiques possibles A et tous les points de division possibles a, sélectionnez la caractéristique avec le plus petit indice de Gini et son point de division correspondant comme caractéristique optimale et point de division optimal. En fonction de la fonctionnalité optimale et du point de division optimal, générez deux nœuds enfants à partir du nœud actuel et distribuez l'ensemble de données d'apprentissage aux deux nœuds enfants en fonction des fonctionnalités.
3. Appelez récursivement (1) et (2) pour les deux nœuds enfants jusqu'à ce que la condition d'arrêt soit remplie.
4. Générer un arbre de décision CART