Arbres de Décision

Les Arbres de Décision sont parmi les techniques de classification de Data Mining les plus populaires. Une fois construit, un Arbre se présente sous la forme d'une arborescence inversée dont chaque nœud terminal (ou "feuille") contient une fraction de l'échantillon original dont les individus appartiennent presque tous à une seule et même classe.

 Un nouvel individu "descend" l'Arbre depuis la racine jusqu'à une unique feuille (voir image inférieure). Son trajet dans l'Arbre est entièrement déterminé par les valeurs de ses attributs (ou "prédicteurs"). Il est alors affecté à la classe dominante de la feuille. Plus précisément, pour chaque k, la probabilité a posteriori de la classe k peut être estimée par la proportion d'individus dans la feuille qui appartiennent à cette classe.

Chaque feuille est un "segment" de l'échantillon qui est aussi homogène que possible par rapport à la variable dépendante (classe). C'est la raison pour laquelle les Arbres de Décision sont également appelés "Arbres de Segmentation".

Les Arbres de Décision acceptent tout type de prédicteur : numérique, ordinal ou nominal. Ils sont rapides, peuvent traiter d'importants volumes de données, et leurs décisions peuvent être transcrites sous forme de "règles logiques" très prisées (mais aux pouvoirs explicatifs souvent limités). Ces avantages sont contrebalancés par un certain manque de précision dans leurs prédictions, comparées à celles de techniques plus sophistiquées comme la Régression Logistique ou les Réseaux de Neurones.

Plusieurs types d'Arbres de Décision sont commercialement disponibles. Leurs différences sont surtout dans la façon dont ils choisissent et effectuent les branchements, et comment ils gèrent les prédicteurs nominaux. Les types principaux ont pour noms :

    * CART

    * CHAID

    * C5

    * QUEST

_______________________________________________________________________________

Les Tutoriels sur les Arbres de Décision ne sont pas encore disponibles en français. Nous vous prions de nous excuser pour cette gêne.

In this first Tutorial, we go over the basic principles of Decision Trees. Although there are many different types of Trees, they differ mostly by the way nodes are split, but they share a large body of common strategy that is dictated by the desire to consider variables one at a time.

OVERVIEW OF DECISION TREES

___________________________________________

So far, we paid no attention to whether the predictors were categorical, ordinal or numerical. In fact, Decision Trees always consider predictors as categorical. What we mean is that if a predictor is numerical, it is first quantized into contiguous blocks that are then considered as modalities. Let's go over the details.

THE VARIOUS TYPES OF PREDICTORS

_________________________________________

We now go over the various criteria used for deciding which node to split next, and how to define the split.

SPLITTING NODES

_________________________________________

Like all models, whether "parametric" or "non parametric", Decision Trees are prone to overfitting. When the process of tree growing is pushed beyond a certain limit, the predictive performance of the tree starts deteriorating : the leaves are then determined by the finest details of the data, that is, by noise.

Two approaches are used for avoiding overfitting :

    * Early stopping of the tree growth,

    * And pruning of a certainly overgrown tree.

THE "RIGHT SIZE" TREE

_________________________________________