Apprentissage automatique : les arbres de décision

Pour certains domaines d’application, il est essentiel de produire des procédures de classification compréhensibles par l’utilisateur. C’est en particulier le cas pour l’aide au diagnostic médical où le médecin doit pouvoir interpréter les raisons du diagnostic. Les arbres de décision répondent à cette contrainte car ils représentent graphiquement un ensemble de règles et sont aisément interprétables. Pour les arbres de grande taille, la procédure globale peut être difficile à appréhender, cependant, la classification d’un élément particulier est toujours compréhensible. Les algorithmes d’apprentissage par arbres de décision sont efficaces, disponibles dans la plupart des environnements de fouille de données. Ils constituent l’objet de ce chapitre.

Les arbres de décision

Exemple 7   La population est constituée d’un ensemble de patients. Il y a deux classes : malade et bien portant. Les descriptions sont faites avec les deux attributs : Température qui est un attribut à valeurs décimales et gorge irritée qui est un attribut logique. On considère l’arbre de décision de la figure ??. 

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 {1,…,p}*, où p est l’arité maximale des noeuds. Si on note le mot vide par e, les positions pour l’arbre de la figure ?? sont :

•  étiquetée par le test Température<37,5,
• 1 étiquetée par le test Gorge irritée,
• 2 étiquetée par la feuille malade,
• 21 étiquetée par la feuille malade,
• 22 étiquetée par la feuille bien portant.

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. En général, chaque test examine la valeur d’un unique attribut de l’espace des descriptions. Les réponses possibles au test correspondent aux labels des arcs issus de ce noeud. 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.

Un arbre de décision est la représentation graphique d’une procédure de classification. En effet, à toute description complète 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.

Exemple 8   Soit l’arbre de décision de la figure ??. Un patient ayant une température de 39 et ayant la gorge non irritée sera classé comme malade par cet arbre. La traduction de cet arbre en règles de décision est :

• SI Température<37,5 ET gorge irritée ALORS malade
• SI Température<37,5 ET NON(gorge irritée) ALORS bien portant
• SI NON(Température<37,5) ALORS malade

Nous allons dans ce chapitre étudier différents algorithmes d’apprentissage par arbres de décision, c’est-à-dire des algorithmes qui, prenant en entrée un échantillon S, construisent un arbre de décision. Nous allons, tout d’abord, introduire quelques notations. Étant donnés un échantillon S, un ensemble de classes {1,…,c} et un arbre de décision t, à 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.

Exemple introductif et préliminaires

Nous allons considérer l’exemple très simple suivant pour introduire les algorithmes d’apprentissage par arbres de décision. Une banque dispose des informations suivantes sur un ensemble de clients:

L’attribut ternaire M décrit la moyenne des montants sur le compte client. Le second attribut ternaire A donne la tranche d’âge du client. Le troisième attribut ternaire R décrit la localité de résidence du client. Le dernier attribut binaire E a la valeur oui si le client a un niveau d’études supérieures. La classe associée à chacun de ces clients correspond au contenu de la colonne I. La classe oui correspond à un client qui effectue une consultation de ses comptes bancaires en utilisant Internet. On souhaite trouver un arbre de décision qui soit capable de dire si un client effectue des consultations de ses comptes par Internet en connaissant les valeurs des attributs M (montant), A (âge), R (résidence) et E (études) pour ce client.

À partir de ce tableau, il s’agit donc de construire un arbre de décision qui classifie les clients. Les algorithmes construisent les arbres de façon descendante. Lorsqu’un test est choisi, on divise l’ensemble d’apprentissage pour chacune des branches et on réapplique récursivement l’algorithme. Sur notre exemple, on initialise avec l’arbre vide. L’échantillon contient 8 éléments, 3 sont de classe oui et 5 de classe non. Donc, à la racine de l’arbre qui n’est étiqueté par aucun test, l’échantillon peut être caractérisé par le couple (3,5). On se pose alors la question de savoir si ce noeud est terminal, c’est-à-dire encore s’il est nécessaire de rechercher un test qui discrimine de façon intéressante l’échantillon. Par exemple, on attribuerait une feuille si nous étions dans le cas (0,8), c’est-à-dire si aucun client n’utilise Internet. Pour notre cas supposons que nous devions choisir un test. Nous aurions quatre choix possibles qui sont décrits dans la figure ??.