L’Arbre de décision

add2.png

\bullet Présentation:

L’Arbre de décision, qui a été élaboré en 1984 par Léo Breiman, Jerome Friedman, Richard Olsen et Charles Stone, permet de discriminer une variable réponse Y continue, binaire ou polychotomique (K \geq 2 classes) à partir d’une matrice de P variables explicatives \mathbf{X} = (X ^1, \cdots, X ^P) continues et/ou qualitatives.

L’Arbre de décision fait partie de la famille des outils à valider par méthode d’apprentissage, soit la construction de la règle décisionnel sur l’échantillon d’apprentissage et sa validation sur un échantillon test.

Il existe plusieurs algorithmes pour la construction d’un arbre de décision. Les plus populaires sont,

– l’algorithme MARS (Regression Multivariées par Spline Adaptative) lorsque Y est continue,

– l’algorithme QUEST (Quick, Unbiased, Efficient, claSsification Tree) lorsque Y est polychotomique et \mathbf{X} est composé exclusivement de variables qualitatives à grand nombre de modalités chacunes,

– l’algorithme CART (Classification And Regression Tree) basé sur l’indice de Gini et sur l’élaboration de noeuds binaires,

– l’algorithme CHAID (\chi ^2 Automatic Interaction Detection) qui met en avant les intéractions au sein de \mathbf{X},

– l’algorithme C5.0 qui est une amélioration de l’algorithme C4.5 lui même une amélioration de l’algorithme ID3 basé sur la méthode de l’entropie de Shannon.

L’arbre de décision construit des frontières continues par morceaux et qui se superposent les unes aux autres. Cette propriété fait de l’arbre de décision un outil qui s’adapte à toute forme de distribution de la variable réponse Y au détriment d’un manque de robustesse.

Une extension de l’arbre de décision permettant de pallier à ce désavantage est la forêt aléatoire qui consiste à créer un grand nombre d’arbres de décision sur un sous-ensemble de variables de \mathbf{X}. Le choix de la classe de prédiction se fait alors par un vote majoritaire au seins des différents arbres construits.

Il est bon de savoir que les algorithmes pour la construction d’arbre décisionnel restent très gourmand en temps de calcul étant donné qu’ils se basent, pour chaque nœud, sur le parcours de l’ensemble des variables à la recherche du seuil ou cut-off optimal qui maximisera de la classification.

Enfin, l’arbre de décision présente l’avantage de ne pas nécessiter d’hypothèse sur la distribution de \mathbf{X}, cependant il nécessite un paramétrage au préalable.

\bullet Les algorithmes CART et C5.0:

Hypothèses préliminaires: Variable réponse Y continue, binaire ou polychotomique à K \geq 2 classes. Variables explicatives \mathbf{X} continues et/ou qualitatives.

L’Algorithme:

Les algorithmes CART et C5.0 sont basés sur le principe de découper le plan en plusieurs sous-plans en fonction des variables explicatives de \mathbf{X} et d’un objectif de maximisation de la classification. Nous nous orientons vers une classification sous forme d’arbres binaires où chaque nœud est une décision prise et chaque feuille une catégorie d’individus.

L’algorithme en quelques étapes:

Procédure Construire-Arbre (D,T)
_ Début
___ Déterminer le meilleur attribut de coupure
___ Créer un nœud fils de T étiqueté par cet attribut
___ Créer autant de fils que l’attribut a de valeurs (attributs nominaux) et étiqueter les arcs par le prédicat ainsi formé pour chaque fils F faire
_______ Associer à ce fils les objets du nœud père vérifiant le prédicat
_______ Si le nœud vérifie le critère de terminaison alors
___________ Transformer ce nœud en feuille et lui attribuer une classe
_______ Sinon
___________ Construire-Arbre (D, F)
_______ Fin si
___ Fin tant que
_ Fin

Le paramétrage:

Plusieurs paramètres (à fixer au préalable) entrent donc en compte afin d’optimiser l’arbre final,

– le nombre d’individus pour construire les nœuds (la règle que nous retrouvons le plus souvent est n_{noeud} = \frac{n}{10}),

– le nombre d’individus pour construire les feuilles (la règle que nous retrouvons le plus souvent est n_{feuille} = \frac{n_{noeud}}{3}),

– la profondeur de l’arbre,

– le paramètre de complexité de l’arbre, dont la détermination se fait en fonction de critère bien précis, et qui représente le rapport entre qualité de prédiction – profondeur de l’arbre – nombre de noeuds construits.

L’indice de performance:

Le choix de la variable, et de son seuil ou cut-off associé, optimisant les performances pour un nœud en cours de construction se fait selon l’indice de pureté de Gini (CART) où l’entropie de Shannon (C5.0).

Nous poserons f_{k,+}, respectivement f_{k,-}, la fréquence de la classe k \in [1,K] au sein de la population dont la valeur pour X ^p, p \in [1,P] est supérieure, respectivement inférieure, au cutoff testé. n_-, n_+ étant les effectifs de part et d’autres du cutoff fixé.

Nous avons alors l’indice de Gini de formule:

I_{Gini} = \frac{n_-}{n} [1 - \sum_{k = 1} ^K f_{k,-} ^2] + \frac{n_+}{n} [1 - \sum_{k = 1} ^K f_{k,+} ^2]

, plus l’indice est faible plus le nœud est considéré comme pur.

Et l’entropie de Shannon de formule (avec la convention 0 \cdot log(0) = 0):

I_{Shannon} = \sum_{k = 1} ^K f_k \cdot log(f_k)

, plus l’indice est élevé, plus le nœud est considéré comme pur.

Sur-ajustement du modèle:

L’Arbre de décision est particulièrement victime du sur-apprentissage. Ces problèmes de sur-ajustement interviennent lorsque nous nous orientons vers des arbres trop complexes, trop dépendants de l’échantillon utilisé pour l’apprentissage. Pour pallier à cette difficulté nous pratiquons deux stratégies connues sous les noms de: post-élagage et pré-élagage.

Le pré-élagage propose de mettre en place un ou plusieurs critères d’arrêt lors de la phase d’expansion de l’arbre. Par exemple, nous considérons qu’une segmentation n’est plus nécessaire lorsque le groupe est d’effectif trop faible, ou encore si la pureté d’un sommet a atteint un niveau suffisant. Une autre façon est d’utiliser un test statistique pour évaluer si la segmentation introduit un apport d’information significatif quant à la prédiction des valeurs de la variable réponse.

Le post-élagage consiste en la construction de l’arbre en deux temps. Nous cherchons à produire l’arbre le plus pur possible dans une phase d’expansion en utilisant une première fraction de l’échantillon de données. Puis, effectuer un retour en arrière pour réduire l’arbre en s’appuyant sur une autre fraction des données de manière à optimiser ses performances. Les méthodes d’apprentissage sont utilisées tout au long de cette phase.

Le paramètre de complexité servant à effectuer l’élagage de l’arbre sera déterminé en fonction des valeurs de l’erreur croisée, de l’écart-type minimal, de l’erreur relative et du R^2.

\bullet Annexe théorique:

Nous présentons ici la démonstration du calcul de complexité dans le cas d’un arbre infixe.

Le pseudo-code classique d’un arbre est:

Parcours (arbre binaire A de racine A_0)
——- Si A_0 distinct de NIL \Rightarrow temps constant T(0)=c pour un sous-arbre vide
——- alors
——- Parcours (arbre de racine fils_gauche A_0) \Rightarrow temps T( k )
——- Afficher clé A_0 \Rightarrow temps constant d
——- Parcours (arbre de racine fils_droit A_0) \Rightarrow temps T(n-k-1)
——- FinSi

Le calcul de complexité associé à cet algorithme est:

– Étape initiale:

T(0) = (c + d) \times 0 + 1 = 1

– Étape suivante:

T(n) = T(k) + T(n - k - 1) + d

= [(c + d) k + c] + [(c + d) (n - k - 1) + c] + d

= (c + d) n + c - (c + d) + c + d

= (c + d) n + c

\bullet Exemple:

Soit la base de données suivante,

add

Nous fixons comme paramètres: 5 observations minimum requises pour créer un nœud et une feuille.

Nous allons construire l’arbre de décision sur le couple de variables explicatives: \mathbf{X} = (X ^1, X ^2), via l’indice de Gini afin de discriminer la variable réponse « Statut ». Trouvons ci-dessous l’évolution de l’indice de Gini au fur et à mesure que nous décalons, de façon croissante, le cut-off:

X ^1 = 9.3500,

\Rightarrow I_{Gini} = \frac{5}{20} \times [1 - (\frac{5}{5}) ^2 - (\frac{0}{5}) ^2] + \frac{15}{20} \times [1 - (\frac{5}{15}) ^2 - (\frac{10}{15}) ^2] = \frac{1}{3}

\cdots

X ^1 = 10.4733,

\Rightarrow I_{Gini} = \frac{10}{20} \times [1 - (\frac{8}{10}) ^2 - (\frac{2}{10}) ^2] + \frac{10}{20} \times [1 - (\frac{2}{10}) ^2 - (\frac{8}{10}) ^2] = \frac{8}{25}

\cdots

X ^1 = 16.8407,

\Rightarrow I_{Gini} = \frac{15}{20} \times [1 - (\frac{10}{15}) ^2 - (\frac{5}{15}) ^2] + \frac{5}{20} \times [1 - (\frac{0}{5}) ^2 - (\frac{5}{5}) ^2] = \frac{1}{3}

X ^2 = 9.054,

\Rightarrow I_{Gini} = \frac{5}{20} \times [1 - (\frac{5}{5}) ^2 - (\frac{0}{5}) ^2] + \frac{15}{20} \times [1 - (\frac{5}{15}) ^2 - (\frac{10}{15}) ^2] = \frac{1}{3}

\cdots

X ^2 = 10.5678,

\Rightarrow I_{Gini} = \frac{10}{20} \times [1 - (\frac{7}{10}) ^2 - (\frac{3}{10}) ^2] + \frac{10}{20} \times [1 - (\frac{3}{10}) ^2 - (\frac{7}{10}) ^2] = \frac{21}{50}

\cdots

X ^2 = 16.1622,

\Rightarrow I_{Gini} = \frac{15}{20} \times [1 - (\frac{10}{15}) ^2 - (\frac{5}{15}) ^2] + \frac{5}{20} \times [1 - (\frac{0}{5}) ^2 - (\frac{5}{5}) ^2] = \frac{1}{3}

Pour le premier split l’algorithme désigne la variable X ^1 comme la plus adéquate pour la séparation du plan et présente deux cut-offs optimaux: 9.8308 et 11.3517. Par défaut nous choisissons le premier, permettant d’isoler sept observations Y = 1 avant le cutoff et de regrouper trois observations Y =1 et dix Y = 2 après.

Maintenant que nous avons séparé une première fois le jeu de données, il convient de relancer la procédure sur \mathbf{X}|_{X ^1 < 9.8308} et \mathbf{X}|_{X ^1 \geq 9.8308}. En réalité, seul le second groupe est à considérer étant donné que le premier est totalement pur.

Nous obtenons alors,

X ^1 = 11.2511,

\Rightarrow I_{Gini} = \frac{5}{13} \times [1 - (\frac{2}{5}) ^2 - (\frac{3}{5}) ^2] + \frac{8}{13} \times [1 - (\frac{1}{8}) ^2 - (\frac{7}{8}) ^2] = \frac{83}{260}

\cdots

X ^1 = 16.8407,

\Rightarrow I_{Gini} = \frac{8}{13} \times [1 - (\frac{3}{8}) ^2 - (\frac{5}{8}) ^2] + \frac{5}{13} \times [1 - (\frac{0}{5}) ^2 - (\frac{5}{5}) ^2] = \frac{15}{52}

X ^2 = 10.5308,

\Rightarrow I_{Gini} = \frac{5}{13} \times [1 - (\frac{3}{5}) ^2 - (\frac{2}{5}) ^2] + \frac{8}{13} \times [1 - (\frac{0}{8}) ^2 - (\frac{8}{8}) ^2] = \frac{12}{65}

\ldots

X ^2 = 16.1632,

\Rightarrow I_{Gini} = \frac{8}{13} \times [1 - (\frac{3}{8}) ^2 - (\frac{5}{8}) ^2] + \frac{5}{13} \times [1 - (\frac{0}{5}) ^2 - (\frac{5}{5}) ^2] = \frac{15}{52}

Pour le second split, c’est la variable X ^2 avec le cut-off 10.53846 qui permet de maximiser la classification en isolant huit observations Y = 2 sur les treize restantes. Nous avons alors un second nœud qui devient une feuille puisque totalement pur.

Il ne reste plus que le nœud contenant les trois observations Y = 1 et les deux observations Y = 2 restantes. Hors nous avons fixé comme paramètre une taille minimale pour construire un nœud ou une feuille de cinq observations, par conséquent nous ne pouvons séparer à nouveau le plan.

L’algorithme se termine à cette étape. Nous pouvons construire la matrice de confusion suivante:

\begin{tabular}{|l|c|c|} \hline & Predit Y1 & Predit Y2 \\ \hline Y1 & 10 & 0 \\ \hline Y2 & 2 & 8 \\ \hline \end{tabular}

\bullet Application informatique:

Procédure SAS:

%macro decision_noeud(DATA=,Y=,n_noeud=);

 /* Macro-programme pour la détermination du cutoff optimal (variable + seuil/modalité) optimisant la classification selon l’indice de pureté de Gini.
       Les paramètres: – DATA, indique la base de données à traiter,
                       – Y, la variable réponse binaire ou multiclasse,
                       – n_noeud, le nombre minimal d’observations que doit contenir les feuilles terminales
       Sortie: la table Resultat_best indiquant la variable et son seuil/modalité optimisant l’indice de pureté de Gini */

    /* Options nécessaires pour éviter de saturer le log et mettre en évidence les erreurs */
options nonotes spool;

    /* Sortie de l’effectif total en cours */
proc sql noprint;
select count(*) into: n_encours from &DATA.;
quit;

    /* Ajustement de l’intervalle d’observations à prendre en compte en fonction du paramètre n_noeud */
%let n_encoursp = %eval(&n_encours. – &n_noeud. + 1);

    /* Sortie du nombre de variables à gérer */
proc contents data = &DATA. (drop =  &Y.) out = biblio noprint;
run;

    /* Mise sous macro-variable des noms et du nombre de variables à gérer */
proc sql noprint;
select distinct(name) into: list_var separated by  »  » from biblio;
select count(*) into: nb_var from biblio;
quit;

    /* Sortie des informations sur la variable réponse Y */
proc freq data = &DATA. noprint;
tables &Y. / out = Y;
run;

data Y;
set Y;
copy = compress(« ‘ »||&Y.|| »‘n »);
run;

    /* Sortie de la liste des classes de la variable réponse Y */
proc sql noprint;
select distinct(copy) into: list_class separated by « , » from Y;
select distinct(&Y.) into: list_class2 separated by  »  » from Y;
select count(distinct(&Y.)) into: nb_class from Y;
quit;

    /* Initialisation de la table des résultats finaux */
data Resultats_best;
length var $50. cutoffQ $50.;
cutoffC = .;
run;

    /* Pour chaque variable explicative */
%do p = 1 %to &nb_var.;

       /* Récupération du format de la variable pour ajuster le traitement */
data _null_;
set biblio;
if name = « %scan(&list_var.,&p.) »;
call symput(« Type »,Type);
run;

   /* Initialisation de la table des résultats associés à la variable en cours et venant compléter la table des résultats finaux */
data Resultats_encours;
length var $50. cutoffQ $50.;
cutoffC = .;
run;

/* Si la variable est continue */
%if &Type. = 1 %then %do;

proc sort data = &DATA.;
by %scan(&list_var.,&p.);
run;

/* Chaque observation équivaut alors à un cutoff sous condition de respecter le paramètre n_noeud */
%do i = &n_noeud. %to &n_encoursp.;

     /* Fixation du cutoff <, >= */
data encours;
set &DATA.;
length cutoff $2.;
cutoff = « <« ; if _n_ >= &i. then cutoff = « >= »;
run;

     /* Répartition des classes de Y en fonction du cutoff temporaire */
proc freq data = encours noprint;
tables &Y.*cutoff / out = Gini;
run;

    /* Pour les valeurs inférieures au cutoff temporaire */
data inf;
set Gini;
if cutoff = « <« ;
run;

       /* Détermination de l’effectif */
proc sql noprint;
select sum(count) into: card_inf from inf;
quit;

 /* Calcul de l’indice de Gini pour les termes inférieurs */
data inf;
set inf;
count_sqr = (count/&card_inf.)**2;
run;

proc sql noprint;
select sum(count_sqr) into: somme_sqr from inf;
quit;

%let som1 = %sysevalf((1 – &somme_sqr.)*&card_inf./&n_encours.);

   /* Pour les valeurs supérieures au cutoff temporaire */
data sup;
set Gini;
if cutoff = « >= »;
run;

        /* Détermination de l’effectif */
proc sql noprint;
select sum(count) into: card_sup from sup;
quit;

 /* Calcul de l’indice de Gini pour les termes supérieurs */
data sup;
set sup;
count_sqr = (count/&card_sup.)**2;
run;

proc sql noprint;
select sum(count_sqr) into: somme_sqr from sup;
quit;

%let som2 = %sysevalf((1 – &somme_sqr.)*&card_sup./&n_encours.);

        /* Calcul de l’indice de pureté de Gini */
%let Gini = %sysevalf(&som1. + &som2.);

       /* Récupératin du cutoff */
data _null_;
set &DATA.;
if _n_ = &i.;
call symput(« Cutoff »,%scan(&list_var.,&p.));
run;

       /* Préparation des résultats d’intérêt à insérer */
data add;
Var = « %scan(&list_var.,&p.) »;
CutoffC = &Cutoff.;
Gini = &Gini.;
type = 1;
run;

                /* Sortie de la répartition par classe en fonction du cutoff temporaire */
proc freq data = encours noprint;
tables &Y. / out = Ventilation;
where cutoff = « >= »;
run;

proc transpose data = Ventilation out = Ventilation;
id &Y.;
var count;
run;

/* Fusion des différentes résultats */
data add;
merge add ventilation;
run;

 /* Insertion des nouveaux résultats au tableau de résultats globaux */
data Resultats_encours;
set Resultats_encours add;
run;

%end;

%end;

        /* Si la variable est qualitative */
%if &Type. = 2 %then %do;

     /* Sortie de la liste des modalités pour la variable en cours */
proc freq data = &DATA. noprint;
tables %scan(&list_var.,&p.) / out = list_modas;
run;

proc sql noprint;
select count(*) into: nb_modas from list_modas;
select distinct(%scan(&list_var.,&p.)) into: list_modas separated by  »  » from list_modas;
quit;

         /* Pour chaque modalité */
%do m = 1 %to &nb_modas.;

 /* Regroupement modalité en cours vs le reste du monde */
data encours;
set &DATA.;
length cutoff $2.;
cutoff = « * »;
if %scan(&list_var.,&p.) = « %scan(&list_modas.,&m.) » then cutoff = « ** »;
run;

/* Répartition de la classe de Y en fonction de la modalité considérée */
proc freq data = encours noprint;
tables &Y.*cutoff / out = Gini;
run;

data inf;
set Gini;
if cutoff = « * »;
run;

 /* Récupération des effectifs pour le reste du monde */
proc sql noprint;
select sum(count) into: card_inf from inf;
quit;

                /* Calcul de l’indice de Gini pour les termes considérés */
data inf;
set inf;
count_sqr = (count/&card_inf.)**2;
run;

proc sql noprint;
select sum(count_sqr) into: somme_sqr from inf;
quit;

%let som1 = %sysevalf((1 – &somme_sqr.)*&card_inf./&n_encours.);

     /* Récupération des effectifs pour la modalité considérée */
data sup;
set Gini;
if cutoff = « ** »;
run;

   /* Récupération des effectifs pour la modalité considérée */
proc sql noprint;
select sum(count) into: card_sup from sup;
quit;

 /* Calcul de l’indice de Gini pour les termes considérés */
data sup;
set sup;
count_sqr = (count/&card_sup.)**2;
run;

proc sql noprint;
select sum(count_sqr) into: somme_sqr from sup;
quit;

%let som2 = %sysevalf((1 – &somme_sqr.)*&card_sup./&n_encours.);

    /* Calcul de l’indice de pureté de Gini */
%let Gini = %sysevalf(&som1. + &som2.);

    /* Préparation des résultats d’intérêt à insérer */
data add;
Var = « %scan(&list_var.,&p.) »;
CutoffQ = « %scan(&list_modas.,&m.) »;
Gini = &Gini.;
type = 2;
run;

           /* Sortie de la répartition par classe en fonction du cutoff temporaire */
proc freq data = encours noprint;
tables &Y. / out = Ventilation;
where cutoff = « ** »;
run;

proc transpose data = Ventilation out = Ventilation;
id &Y.;
var count;
run;

   /* Fusion des différentes résultats */
data add;
merge add ventilation;
run;

 /* Insertion des nouveaux résultats au tableau de résultats globaux */
data Resultats_encours;
set Resultats_encours add;
run;

%end;

%end;

     /* Recherche de la valeur minimale de Gini pour déterminer le cutoff optimal chez la variable en cours */
data Resultats_encours;
set Resultats_encours;
if Gini ne .;
run;

proc sql noprint;
create table Resultats_encours2 as select min(Gini) as min_gini, Var, cutoffC, cutoffQ, Gini, &list_class., type from Resultats_encours;
quit;

data Resultats_encours;
set Resultats_encours2;
if Gini = min_gini;
run;

data Resultats_best;
set Resultats_best Resultats_encours;
run;

%end;

    /* Recherche de la valeur minimale de Gini pour déterminer le cutoff optimal */
data Resultats_best;
set Resultats_best;
n_tot = sum(&list_class.);
if n_tot >= &n_noeud.;
run;

proc sql noprint;
create table Resultats_best2 as select min(Gini) as min_gini, Var, cutoffC, cutoffQ, Gini, &list_class., n_tot, type from Resultats_best;
quit;

data Resultats_best;
set Resultats_best2;
if Gini = min_gini;
run;

    /* Nous retenons le premier de la liste */
data Resultats_best;
set Resultats_best;
if _n_ = 1;
run;

    /* Suppression des tables temporaires et inutiles */
proc datasets lib = work nolist;
delete add Y Ventilation Resultats_encours Resultats_encours2 encours gini Resultats_best2 biblio list_gini list_modas sup inf;
run;

 /* Reset des options d’affichage de la log */
options notes nospool;

%mend;

%macro DT(DATA=,Y=,n_noeud=);

 /* Le macro-programme suivant permet la construction de l’arbre de décision CART et se base sur la macro decision_noeud (application de l’indice de pureté de Gini).
       Les paramètres: – DATA, la base de données à traiter,
                       – Y, la variable réponse binaire ou multiclasse,
                       – n_noeud, le nombre d’observations à considérer pour pouvoir construire un noeud, une feuille.
       Sortie: la table parcours recensant les différentes étapes de construction des feuilles et la table DATA mise à jour avec les prédictions.
       NB: ce programme nécessite plusieurs tests de validation et reste inachevé. Parmi les actions à faire: la phase de post-élagage, l’ajout d’un critère d’arrêt lorsqu’un noeud est totalement pur ainsi que quelques contrôles de bug. */

    /* Pour l’itération d’origine nous lançons l’algorithme afin de déterminer la racine de l’arbre */
%decision_noeud(DATA=&DATA.,Y=&Y.,n_noeud=&n_noeud.);

 /* Options nécessaires pour éviter de saturer le log et mettre en évidence les erreurs */
    options nonotes spool;

    /* Sortie des effectifs totaux */
data _null_;
set Resultats_best;
call symput(« n_tot »,n_tot);
run;

    /* Edition du cutoff optimal pour la table de synthèse des différents parcours menant aux feuilles terminales */
data parcours;
set Resultats_best;
if Type = 1 then do;
cond_G = catx(‘ ‘,Var, »>= »,CutoffC);
cond_D = catx(‘ ‘,Var, »<« ,CutoffC);
end;
if Type = 2 then do;
cond_G = cat(compress(Var), » = ‘ »,compress(CutoffQ), »‘ »);
cond_D = cat(compress(Var), » ne ‘ »,compress(CutoffQ), »‘ »);
end;
drop Gini min_gini;
run;

proc transpose data = parcours out = parcours;
var cond_G cond_D;
run;

data new_parcours;
set parcours;
rename COL1 = cond;
run;

 /* Si l’effectif total est supérieur à la condition d’arrêt n_noeud alors nous pouvons continuer l’algorithme */
%if &n_tot. >= &n_noeud. %then %do;

%do a = 1 %to 1;

data parcours;
set new_parcours;
if _name_ ne «  »;
run;

 /* Sortie du nombre de noeud à parcourir */
proc sql noprint;
select count(*) into: nb_noeud from parcours;
quit;

data new_parcours;
run;

   /* Pour chaque noeud */
%do n = 1 %to &nb_noeud.;

   /* Sortie du parcours en cours */
data _null_;
set parcours;
if _n_ = &n.;
call symput(« critere »,cond);
run;

             /* Réduction de la base via le parcours considéré */
data traitement;
set &DATA.;
if &critere.;
run;

    /* Sortie de l’effectif restant */
proc sql noprint;
select count(*) into: todo from traitement;
quit;

 /* Si la condition est respectée sur l’effectif n_noeud alors nous lançons la procédure pour créer une nouvelle feuille à la profondeur suivante */
%if &todo. >= %eval(2*&n_noeud.) %then %do;

 /* Détermination du cutoff optimal */
%decision_noeud(DATA=traitement,Y=&Y.,n_noeud=&n_noeud.);
options nonotes spool;

                    /* Pour eviter le bug lors de la manipulation des variables qualitatives */
%let controlQ = 0;

data _null_;
set Resultats_best;
if Type = 2 then do;
call symput(« controlQ »,n_tot);
end;
run;

         /* Edition du cutoff optimal pour insertion dans la table des parcours */
data add_parcours;
set Resultats_best;
if Type = 1 then do;
cond_G = catx(‘ ‘, »&critere. », »& »,Var, »>= »,CutoffC);
cond_D = catx(‘ ‘, »&critere. », »& »,Var, »<« ,CutoffC);
end;
%if &controlQ. ne &todo. %then %do;
if Type = 2 then do;
cond_G = cat(catt(« &critere. »), » & « ,compress(Var), » = ‘ »,compress(CutoffQ), »‘ »);
cond_D = cat(catt(« &critere. »), » & « ,compress(Var), » ne ‘ »,compress(CutoffQ), »‘ »);
end;
%end;
drop Gini min_gini;
run;

proc transpose data = add_parcours out = add_parcours;
var cond_G cond_D;
run;

data add_parcours;
set add_parcours;
rename COL1 = cond;
run;

                    /* Si le cutoff est le même que celui d’origine, bug en cas de variable qualitative, alors on zap l’étape */
%if &controlQ. = &todo. %then %do;

data add_parcours;
cond = « &critere. »;
_name_ = « Stop!   « ;
run;

%end;

data new_parcours;
set new_parcours add_parcours;
run;

%end;

 /* Si le noeud en cours ne respecte pas le critère, alors nous le fermons */
%if &todo. < %eval(2*&n_noeud.)  %then %do;

data add_parcours;
cond = « &critere. »;
_name_ = « Stop!   « ;
run;

data new_parcours;
set new_parcours add_parcours;
run;

%end;

%end;

proc sql noprint;
select count(*) into: stop_or_not from new_parcours where _name_ = « Stop!   « ;
quit;

/* Tant que tous les noeuds ne sont pas fermés, on relance l’itération pour continuer à creuser l’arbre */
%if &stop_or_not. < &nb_noeud. %then %do;
%let a = 0;
%end;

%end;

%end;

data parcours;
set new_parcours;
if cond ne «  »;
run;

/* Nous sortons le nombre de feuilles/parcours de l’arbre terminé */
proc sql noprint;
select count(*) into: nb_feuille from parcours;
quit;

 /* Pour chaque parcours */
%do c = 1 %to &nb_feuille.;

data _null_;
set parcours;
if _n_ = &c.;
call symput(« critere »,cond);
run;

data pred;
set &DATA.;
if &critere.;
run;

   /* Sortie de la classe dominante pour le noeud considéré afin de déterminer la prédiction */
proc freq data = pred noprint;
tables &Y. / out = pred;
run;

proc sql noprint;
select max(count) into: class_pred from pred;
quit;

data pred;
set pred;
if count = &class_pred.;
run;

data pred;
set pred;
if _n_ = 1;
call symput(« class_pred »,&Y.);
run;

 /* Nous appliquons la prédiction déterminée à la table de données */
data &DATA.;
set &DATA.;
if &critere. then prediction = &class_pred.;
run;

/* Nous renseignons dans la foulée le vote majoritaire du parcours considéré */
data parcours;
set parcours;
if _n_ = &c. then prediction = &class_pred.;
run;

%end;

/* Sortie des prédictions pour les indicateurs de performance */
proc freq data = &DATA.;
tables &Y. * prediction;
run;

 /* Suppression des tables temporaires et inutiles */
proc datasets lib = work nolist;
delete Resultats_best new_parcours add_parcours traitement pred;
run;

/* Reset des options d’affichage de la log */
options notes nospool;

%mend;

Package et fonction R: https://stat.ethz.ch/R-manual/R-devel/library/rpart/html/rpart.html

\bullet Bibliographie:

– Classification and regression tree de Leo Breiman, Jerome Friedman, Richard Olsen et Charles Stone

– Comprendre et utiliser les statistiques dans les sciences de la vie de Bruno Falissard

– The top ten algorithms in data minig de Windong Wu et Vipin Kumar

– Probabilité, analyse des données et Statistique de Gilbert Saporta

– Data mining et statistique décisionnelle. L’intelligence des données de Stéphane Tufféry