[PDF] [PDF] Arbres de décision - Formations en Informatique de Lille

[PDF] Chapitre III Arbres de classification - Université de Bordeaux

- En français on parle d'arbres de classification ou d'arbres de régression et plus généralement d'arbres de décision 2 / 32 Page 3 ▷ Variables d'entrées 

[PDF] Arbres de décision avec Scikit-Learn - Python

5 fév 2020 · Suivant cette idée, nous devrions aboutir à un arbre avec 3 feuilles dans notre exemple, avec exactement le même comportement en classement

[PDF] 52 Les arbres de décision - UNIVERSITÉ DU QUÉBEC MÉMOIRE

classification et de régression (CART), décrivant la génération d'arbres de décision binaires Des améliorations postérieures ont été faites tels que l' algorithme 

[PDF] Méthodes CART Introduction à la sélection de variables

Cependant, des investigations théoriques doivent encore être menées 4 Arbre de décision L'algorithme CART (Classification And Regression Trees), introduit 

[PDF] Arbres de décision - Formations en Informatique de Lille

15 jan 2009 · Algorithme de classification Prédiction Algorithme construisant un arbre `a partir d'exemples ? Trouver le Sortie : Un arbre de décision 1

[PDF] Vers la classification de matériaux à partir de - Hal-CEA

24 jan 2019 · Towards material classification from uncertain chemical compositions Arnaud Grivet Arbre de décision flou, r`egles floues, incertitude, clas-

[PDF] Thèse présentée pour lobtention du grade de Docteur de l - Thèses

28 mai 2014 · d'un arbre de décision, cette vraisemblance est maximisée via Les arbres de décision sont un modèle de classification/prédiction simple 

[PDF] Mesure de limportance de variables à partir de forêt - HEC Montréal

1 sept 2018 · CART Arbre de classification et de régression proposé par Breiman en 1984 L' objectif d'un arbre de décision est de prédire une variable Y à 

[PDF] arbre de décision exemple

[PDF] arbre de décision cart

[PDF] construire un arbre de décision

[PDF] arbre de décision définition

[PDF] dénombrement cours 1ere s

[PDF] apollon et daphné résumé

[PDF] apollon et daphné leur histoire

[PDF] expression etre nature

[PDF] tp mise en évidence d'une réaction d'oxydoréduction

[PDF] apollon et daphné peinture

[PDF] apollon et daphné le bernin

[PDF] tp chimie réaction d oxydoréduction

[PDF] vertebres avec quilles

[PDF] arbre de parenté des vertébrés

[PDF] innovation évolutive définition

Université de Caen-Normandie

Introduction aux arbres de d

´ecision (de type CART)Christophe Chesneau

https://chesneau.users.lmno.cnrs.fr/Petal.Length < 2.5

Petal.Width < 1.8

setosa .33 .33 .33 100%
setosa

1.00 .00 .00

33%
versicolor .00 .50 .50 67%
versicolor .00 .91 .09 36%
virginica .00 .02 .98 31%
yesno setosa versicolor virginicaCaen, le 02 Mars 2023

Table des matières

Table des matières

1 Arbres de régression (CART) 5

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2 Première approche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.3 Considérations mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.4 Mise en oeuvre avec R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2 Arbres de classification (CART) 25

2.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.2 Considérations mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

2.3 Mise en oeuvre avec R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

3 Forêts d"arbres de décision 36

3.1 Forêts d"arbres de régression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

3.2 Forêts d"arbres de classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

3.3 Mise en oeuvre avec R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

4 Pour aller plus loin 42

5 Exercices44

6 Solutions56

Note Ce document propose une introduction aux arbres de décision de type CART.

On y aborde principalement les arbres de régression, les arbres de classification et les forêts

aléatoires d"arbres de décision.

Le logiciel utilisé est R.

N"hésitez pas à me contacter pour tout commentaire : christophe.chesneau@gmail.com

Bonne lecture!C. Chesneau3

1 Arbres de régression (CART)

1 Arbres de régression (CART)

1.1 Introduction

Contexte :Pournindividus!1;:::;!nd"une population, on dispose des valeurs dep+1caractères X

1;:::;Xp;Y. Pour touti2 f1;:::;ng, les valeurs associées à!isont notéesx1;i;:::;xp;i;yi.

Elles sont généralement présentées sous la forme suivante :X

1...XpY!

1x1;1...xp;1y1.

nx1;n...xp;nynCes valeurs constituent les données.Dans ce c hapitre,on supp oseq ueYest quantitatif, on ne

fait pas d"hypothèse particulière sur les autres caractères. Objectif :Partant des données, l"objectif est de donner une valeur plausible deYpour un individu dont on connaît les valeurs deX1;:::;Xp. Aide à la décision :Pour décider d"une valeur plausible deY, on peut s"aider d"un arbre de régression de type CART (plus précisément, reposant sur l"algorithme CART, acronyme pour

Classification And Regression Trees).

Intérêts :Les intérêts d"un arbre de régression sont les suivants : Il est simple à comprendre, à interpréter et à communiquer. La nature des caractèresX1;:::;Xpn"a pas d"importance. Il est performant pour de grands jeux de données (big data).

Remarque :Pour atteindre le même objectif, on pourrait aussi utiliser un modèle de régression

linéaire (ou non-linéaire). Les avantages de l"arbre de régression par rapport au modèle de

régression linéaire sont les suivants : Il est plus simple et plus direct dans son approche.C. Chesneau5

1 Arbres de régression (CART)

La structure liantYàX1;:::;Xpn"importe pas; celle-ci peut être linéaire ou autre.

Il n"y a pas d"hypothèse mathématique sous-jacente (pas d"hypothèse de normalité ou autre).

Les dépendances éventuelles entreX1;:::;Xpne posent pas de problème.

1.2 Première approche

Arbre binaire, racine, branche, noeud et feuille :Un arbre binaire est une construction hié-

rarchique de forme "triangulaire en escaliers" constitué de plusieurs éléments : l"élément fonda-

teur est au sommet de la construction; il est appelé racine, les traits qui partent en descendant de cette racine sont appelés branches, elles joignent des éléments appelés noeuds. De chaque noeud, partent0ou2branchesjoig nantalors d"a utresnoeuds, et ai nside suite. Un noeud dont part2branches est dit coupé. Un noeud dont ne part aucune branche est appelé feuille. Ainsi, un arbre se parcours de la racine aux feuilles (donc de haut en bas). Exemple :Un exemple d"arbre de régression est présenté ci-dessous.C. Chesneau6

1 Arbres de régression (CART)

Arbre de régression : principe :Avant toute chose, un arbre de régression de type CART est

un arbre binaire aidant à la décision d"une valeur plausible deYpour un individu dont on connaît

les valeursX1;:::;Xp. Sa construction repose sur un partitionnement récursif des individus à l"aide des données. Ce partitionnement se fait par une succession de noeuds coupés. La coupure d"un noeud, et ce qui la caractérise, se fait avec des règles d"arrêt, des conditions de coupure. Les règles d"arrêts reposent souvent sur des principes simples (il faut un minimum d"individus au noeud pour envisager une coupure ...). Les conditions de coupures reposent sur des critères mathématiques. Une particularité est que chaque condition de coupure met en jeu un, et un

seul, caractère parmiX1;:::;Xp(un même caractère peut être utilisé pour définir plusieurs

conditions de coupure). À la fin du partitionnement, il ne reste plus que des feuilles. Les données

des individus associés aux feuilles sont alors utilisées à des fins prédictives sur le caractèreY.

Le schéma général est résumé dans l"image suivante :

C. Chesneau7

1 Arbres de régression (CART)

Commandes R :

On utilise rpartde la librarierpart(rpartest l"acronyme derecursive partitioning). Exemple de syntaxe avecp= 2:arbre = rpart(Y~X1 + X2). Énventuel- lement, on peut activer l"optionmethod = "anova"s"il peu y avoir confusion sur la nature quantitative deY. Pour afficher l"arbre, on utiliserpart.plotde la librairierpart.plot. Utilisation :Pour déterminer une valeur plausible deYpour un individu dont on connaît les

valeursX1;:::;Xp, on procède étape par étape de la manière suivante. En partant de la racine,

à chaque noeud, on vérifie si la condition de coupure est vérifiée ou pas : si la condition est

vérifiée, on se dirige vers la branche associée à la réponse "Oui" (répondant à la question

implicite "Est-ce la condition est vérifiée?"), sinon, on se dirige vers la branche associée à la

réponse "Non". À la derni èreétap e,on ab outitalors à une seule feuille de l"arbre . Dès lors, une valeur plausible deYpour l"individu est la moyenne des valeurs deYassociées aux individus

de cette feuille. En général, un arbre de régression construit avec un logiciel statistique affiche

la moyenne des valeurs deYet ce, pour chaque noeud et feuille.

Commandes R :

On utilise predict.

1.3 Considérations mathématiques

Questions centrales :Ainsi, pour construire un arbre de régression, deux questions se posent : Comment définir la condition de coupure d"un noeud?

Comment définir la règle d"arrêt?

Des réponses à ces questions sont apportées par des critères mathématiques. Pour les définir

clairement, quelques outils sont à présenter, ce qui est fait ci-dessous. Dans un premier temps, on suppose que les caractèresX1;:::;Xpsont quantitatifs. Outils :Soientj2 f1;:::;pgetc2R. Pour un noeud donné, on pose : y j;c;gauchela moyenne des valeurs deYpour les individus vérifiantXj< c, y j;c;droitla moyenne des valeurs deYpour les individus vérifiantXjc, SSgauche(j;c)la somme des carrés des écarts entre les valeurs deYety j;c;gauche, pour les individus vérifiantXj< c,C. Chesneau8

1 Arbres de régression (CART)

SSdroit(j;c)la somme des carrés des écarts entre les valeurs deYety j;c;droit, pour les individus vérifiantXjc.

Idée :Pour un noeud donné, l"erreur globale que l"on commet en séparant les individus selon que

X j< couXjcest donnée par

E(j;c) =SSgauche(j;c) +SSdroit(j;c):

L"idée est donc de minimiser cette erreur.

Condition de coupure :Pour un noeud donné, la condition de coupure adoptée est X jc; oùjetcrendent minimale l"erreurE(j;c), i.e, pour toutj2 f1;:::;pgetc2R,E(j;c) E(j;c). Le caractèreXjest alors appelé caractère de coupure etcest appelée valeur seuil. Ainsi, on sépare les individus en2groupes selon qu"ils vérifientXj< couXjc;Xjest le plus influant des caractère quant à la séparation des individus du noeud en2groupes.En outre, le plus influant des caractères surYquant à la séparation des individus du noeud en2 groupes est le caractère de coupure de la racine.

Remarque :

En général, la maximisation surcne se fait pas surRtout entier;el lese fait sur une grille de valeurs données par les moyennes de deux observations consécutives du caractèreXj. Commandes R :rpartfonctionne ainsi pour déterminer les valeurs seuils candidates. On peut également écrire la condition de coupure commeXj< c, puisque seule la réponse "Oui" ou "Non" importe dans une prédiction. SiXjcest "Oui",Xj< csera "Non", et vice-versa.

Indice d"amélioration :Pour un noeud donné, on appelle indice d"amélioration le réelIdéfini

quotesdbs_dbs2.pdfusesText_2