Figure 4.1: Un exemple d'arbre de décision
Un arbre de décision est un arbre au sens informatique du
terme. On rappelle que les noeuds d'un arbre sont repérés par des
positions qui sont des mots sur 
, où p est
l'arité maximale des noeuds. Les noeuds internes sont appelés
noeuds de décision. Un tel noeud est étiqueté par un test qui
peut être appliqué à toute description d'un individu de la
population. Les réponses possibles correspondent aux labels des
arcs. Dans le cas de noeuds de décision binaires, les labels des
arcs sont omis et, par convention, l'arc gauche correspond à une
réponse positive au test. Les feuilles sont étiquetées par
une classe appelée classe par défaut.
A tout arbre de décision, on associe de façon naturelle une procédure de classification. En effet, à toute description est associée une seule feuille de l'arbre de décision. Cette association est définie en commençant à la racine de l'arbre et en descendant dans l'arbre selon les réponses aux tests qui étiquettent les noeuds internes. La classe associée est alors la classe par défaut associée à la feuille qui correspond à la description. La procédure de classification obtenue a une traduction immédiate en terme de règles de décision. Les systèmes de règles obtenus sont particuliers car l'ordre dans lequel on examine les attributs est fixé et les règles de décision sont mutuellement exclusives.
Soit un échantillon S, un ensemble de classes 
et
un arbre de décision t. A chaque position p de t correspond un
sous-ensemble de l'échantillon qui est l'ensemble des exemples qui
satisfont les tests de la racine jusqu'à cette position. Par
conséquent, on peut définir, pour toute position p de t, les
quantités suivantes :
N(p) est le cardinal de l'ensemble des exemples associé à p,
N(k/p) est le cardinal de l'ensemble des exemples associé à p qui sont de classe k,
P(k/p) = N(k/p)/N(p) la proportion d'éléments de classe k à la position p.
A toute position p d'un arbre de décision, on peut associer une quantité i(p) qui représente le degré de mélange des classes à la position p. Plus i(p) sera élevée, plus le mélange des classes sera important. La fonction i devra atteindre son maximum lorsque les exemples sont équitablement répartis entre les différentes classes et son minimum lorsqu'une classe contient tous les exemples (le noeud est pur). Il existe différentes fonctions qui satisfont ces propriétés, nous en citerons deux : la fonction de Gini et la fonction entropie.
