Login to your account

Username *
Password *
Remember Me

Create an account

Fields marked with an asterisk (*) are required.
Name *
Username *
Password *
Verify password *
Email *
Verify email *
Captcha *
Reload Captcha

Machine Learning

ML Supervised

Vote utilisateur: 0 / 5

Etoiles inactivesEtoiles inactivesEtoiles inactivesEtoiles inactivesEtoiles inactives

Objectifs

L'apprentissage par arbre de décision est une méthode classique en apprentissage automatique . Son but est de créer un modèle qui prédit la valeur d'une variable-cible depuis la valeur de plusieurs variables d'entrée.

Une des variables d'entrée est sélectionnée à chaque nœud intérieur (ou interne, nœud qui n'est pas terminal) de l'arbre selon une méthode qui dépend de l'algorithme et qui sera discutée plus loin. Chaque arête vers un nœud-fils correspond à un ensemble de valeurs d'une variable d'entrée, de manière que l'ensemble des arêtes vers les nœuds-fils couvrent toutes les valeurs possibles de la variable d'entrée.

Chaque feuille (ou nœud terminal de l'arbre) représente soit une valeur de la variable-cible, soit une distribution de probabilité des diverses valeurs possibles de la variable-cible. La combinaison des valeurs des variables d'entrée est représentée par le chemin de la racine jusqu'à la feuille.

L'arbre est en général construit en séparant l'ensemble des données en sous-ensembles en fonction de la valeur d'une caractéristique d'entrée. Ce processus est répété sur chaque sous-ensemble obtenu de manière récursive, il s'agit donc d'un partitionnement récursif.

La récursion est achevée à un nœud soit lorsque tous les sous-ensembles ont la même valeur de la caractéristique-cible, ou lorsque la séparation n'améliore plus la prédiction. Ce processus est appelé induction descendante d'arbres de décision (top-down induction of decision trees ou TDIDT), c'est un algorithme glouton puisqu'on recherche à chaque nœud de l'arbre le partage optimal, dans le but d'obtenir le meilleur partage possible sur l'ensemble de l'arbre de décision. C'est la stratégie la plus commune pour apprendre les arbres de décision depuis les données.

En fouille de données, les arbres de décision peuvent aider à la description, la catégorisation ou la généralisation d'un jeu de données fixé.

L'ensemble d'apprentissage est généralement fourni sous la forme d'enregistrements du type :

(x,Y) = (x1, x2, x3, …, xk, Y)

La variable Y désigne la variable-cible que l'on cherche à prédire, classer ou généraliser. Le vecteur x  est constitué des variables d'entrée x1, x2, x3 etc. qui sont utilisées dans ce but. Chaque nœud interne de l’arbre correspond à un test fait sur une des variables xi :

  • Variable catégorielle : génère une branche (un descendant) par valeur de l’attribut ;
  • Variable numérique : test par intervalles (tranches) de valeurs.

Les feuilles de l’arbre spécifient les classes.

Une fois l’arbre construit, classer un nouvel candidat se fait par une descente dans l’arbre, de la racine vers une des feuilles (qui encode la décision ou la classe). A chaque niveau de la descente on passe un nœud intermédiaire où une variable xi est testée pour décider du chemin (ou sous-arbre) à choisir pour continuer la descente.

Principe de la construction :

Au départ, les points dès la base d’apprentissage sont tous placés dans le nœud racine. Une des variables de description des points est la classe du point (la « vérité terrain ») ; cette variable est dite « variable cible ». La variable cible peut être catégorielle (problème de classement) ou valeur réelle (problème de régression). Chaque nœud est coupé (opération split) donnant naissance à plusieurs nœuds descendants. Un élément de la base d’apprentissage situé dans un nœud se retrouvera dans un seul de ses descendants.

L’arbre est construit par partition récursive de chaque nœud en fonction de la valeur de l’attribut testé à chaque itération (top-down induction). Le critère optimisé est l’homogénéité des descendants par rapport à la variable cible. La variable qui est testée dans un nœud sera celle qui maximise cette homogénéité.

Le processus s’arrête quand les éléments d’un nœud ont la même valeur pour la variable cible (homogénéité).

 

Figure 1: Au milieu, construction par partition récursive de l’espace : tests successifs sur les x1, x2 et x1. Chaque nœud feuille est homogène : ses éléments (points de chaque région) ont la même valeur pour l’attribut cible (la même classe). A gauche, division impossible à obtenir par partition récursive sur les attributs. (Source : wikimedia.org)

Figure 2: A gauche, séparation de classes par partition itérative des variables. A chaque étape le but est de couper le nœud en deux régions les plus homogènes possible. A droite, séparation par combinaison linéaire de plusieurs variables (peut conduire à des arbres plus simples mais au prix de la complexité accrue des tests dans les nœuds).

Exemple 1 : maladies

 

Figure 3: Un ensemble d’individus décrits par plusieurs variables catégorielles (Toux, Fievre, Poids, Douleur). En bas on voit l’arbre de décision obtenu. La variable cible se retrouve dans les feuilles.

Exemple 2 : oiseaux


Figure 4: Pour un ensemble d’éléments décrits par des variables catégorielles la classification résultante peut être vue comme une combinaison de règles booléennes.

Cadre algorithmique pour les arbres de décision

Les inducteurs d'arbre de décision sont des algorithmes qui construisent automatiquement un arbre de décision à partir d'un ensemble de données donné. En règle générale, l'objectif est de trouver l'arbre de décision optimal en minimisant l'erreur de généralisation. Cependant, d'autres fonctions cibles peuvent également être définies, par exemple, en minimisant le nombre de nœuds ou en minimisant la profondeur moyenne. 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: 

Client M A R E I
1 moyen moyen village oui Oui
2 élevé moyen bourg non Non
3 faible âgé bourg non Non
4 faible moyen bourg oui Oui
5 moyen jeune ville oui Oui
6 élevé âgé ville oui Non
7 moyen âgé ville oui Non
8 faible moyen village non Non

 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 nœud 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 5. 

                                                       (3,5)   —>   M (1,2) (2,1) (0,2)                                                            

                                                       (3,5)   —>   A (1,0) (2,2) (0,3)                                                            

                                                       (3,5)   —>    R (1,1) (1,2) (1,2)                                                            

                                                       (3,5)   —>    E (3,2) (0,3) 

Figure 5: choix possibles en racine où les branches du test M sont labelles dans l'ordre par faible, moyen et élevé ; du test A dans l'ordre par jeune, moyen et âgé ; du test R dans l'ordre par village, bourg et ville ; du test E dans l'ordre par oui et non.

Laquelle des quatre possibilités faut-il choisir ? Si on regarde le test sur le type de résidence R, on remarque que ce test ne permet une discrimination sur aucune des branches, on peut donc se dire que le choix de ce test ne fait rien gagner, il sera donc à rejeter. Par contre, pour le test sur l'âge A, on remarque que sur la première branche, tous les éléments correspondants de l'échantillon sont de classe oui et que sur la troisième branche, tous les éléments sont de classe non. Ce test peut donc être considéré comme << intéressant >>. Ce raisonnement informel doit être automatisé. 

Par conséquent, il nous faut introduire des quantités qui permettent de comparer les différents choix possibles. Dans ce but, on définit des fonctions qui permettent de mesurer le degré de mélange des exemples entre les différentes classes. Une telle fonction doit vérifier la propriété suivante : elle doit prendre son minimum lorsque tous les exemples sont dans une même classe (le nœud est pur) et son maximum lorsque les exemples sont équirépartis. Par exemple, si on dispose de 8 éléments et de deux classes, une telle fonction devra prendre son minimum pour les couples (0,8) et (8,0) et son maximum pour le couple (4,4). Il existe différentes fonctions qui satisfont ces propriétés, nous en citerons deux : la fonction de Gini et la fonction entropie. Soit S un échantillon, soit p une position, en reprenant les notations définies précédemment, ces fonctions sont définies par :

                                           Entropie (p) = -Sk=1c (k/p) × log((k/p))                                 (a)

                                                 Gini (p)  = 1 - Sk=1c (k/p)                                                              (b)                                                                                                   =Sk < k' (k/p)(k'/p                                             (c)

Considérons le cas de deux classes et appelons x la proportion d'éléments de classe 1 en position p. On a donc Entropie(p)= - x log x - (1-x) log (1-x). Cette fonction de x prend ses valeurs dans l'intervalle [0,1], a son minimum pour x=0 et x=1 qui vaut 0 et a son maximum pour x=1/2 qui vaut 1. La fonction de Gini est définie par Gini(p) = 2x(1-x). Cette fonction de x prend ses valeurs dans l'intervalle [0,1/2], a son minimum pour x=0 et x=1 qui vaut 0 et a son maximum pour x=1/2 qui vaut 1/2. Ces deux fonctions sont symétriques par rapport à x=1/2. Pour notre exemple courant, considérons, par exemple, l'arbre construit à l'aide de l'attribut E, nous avons :

  • Entropie(e)= -3/8 log 3/8-5/8 log 5/8~ 0,954
  • Entropie(1)= -3/5 log 3/5-2/5 log 2/5 ~ 0.970
  • Entropie(2)= -0/3 log 0/3-3/3 log 3/3=0
  • Gini(e)= 2 × 3/8 × 5/8 ~ 0,469
  • Gini(1)= 2 × 3/5 × 2/5 = 0.480
  • Gini(2)= 2 × 0/3× 3/3=0

On dispose ainsi de fonctions permettant de mesurer le degré de mélange des classes pour tout échantillon et donc pour toute position de l'arbre en construction. Appelons i la fonction choisie. Il reste à définir une fonction permettant de choisir le test qui doit étiqueter le nœud courant. Rappelons que, sur notre exemple, à la racine de l'arbre, il nous faut choisir entre les quatre tests correspondants aux quatre attributs disponibles. Dans ce but, on introduit une fonction gain par :


                                                                    

                                                   Gain (p,t) = i(p) - Σnj=1 P× i(pj)                                           (d)

 

où p désigne une position, test un test d'arité n et Pj est la proportion d'éléments de S à la position p qui vont en position pj (qui satisfont la jème branche du test test). Si on considère comme fonction i la fonction entropie, le terme i(p) représente l'entropie actuelle du noeud p, le deuxième terme de la différence représente l'entropie espérée en introduisant le test test qui est égale à la somme pondérée des entropies des nouveaux noeuds créés. On souhaite obtenir des entropies les plus faibles possibles car, d'après les propriétés de la fonction entropie, si l'entropie est faible, la plupart des éléments se trouvent dans une même classe. On cherche donc à obtenir le gain maximum. Sur notre exemple, nous obtenons :

  • Gain (e,M)=Entropie (e) - (3/8 Entropie (1) + 3/8 Entropie (2) + 2/8 Entropie (3)) = Entropie (e) - 0,620
  • Gain (e,A)=Entropie (e) -  (1/8 Entropie (1) + 4/8 Entropie (2) + 3/8 Entropie (3))= Entropie (e) - 0,500
  • Gain (e,R)=Entropie (e) - (2/8 Entropie (1) + 3/8 Entropie (2) + 3/8 Entropie (3)) = Entropie (e) - 0,870
  • Gain (e,E)=Entropie (e) - (5/8 Entropie (1) + 3/8 Entropie (2))= Entropie (e) - 0,607

Le gain maximal ou encore l'entropie espérée minimale est obtenue pour le choix du test A. On remarque que le choix du test R est très mauvais, ce qui correspond bien à l'intuition. Dans ce paragraphe, nous avons introduit la problématique et quelques éléments fondamentaux utilisés par les algorithmes d'apprentissage par arbre de décision. Nous allons, dans le paragraphe suivant, présenter le schéma général des algorithmes, puis présenter deux algorithmes particuliers CART et ID3.

Un premier algorithme : CART (Breiman et al. [1] )

Cette méthode permet d'inférer des arbres de décision binaires, i.e. tous les tests étiquetant les noeuds de décision sont binaires. Le langage de représentation est constitué d'un certain nombre d'attributs. Ces attributs peuvent être binaires, qualitatifs (à valeurs dans un ensemble fini de modalités) ou continus (à valeurs réelles). Le nombre de tests à explorer va dépendre de la nature des attributs. A un attribut binaire correspond un test binaire. A un attribut qualitatif ayant n modalités, on peut associer autant de tests qu'il y a de partitions en deux classes, soit 2n-1 tests binaires possibles. Enfin, dans le cas d'attributs continus, il y a une infinité de tests envisageables. Dans ce cas, on découpe l'ensemble des valeurs possibles en segments, ce découpage peut être fait par un expert ou fait de façon automatique.
Nous supposons prédéfini un ensemble de tests binaires. Pour définir l'algorithme, nous allons définir les trois opérateurs utilisés par la méthode CART pour calculer un bon arbre de décision (phase d'expansion), puis nous verrons la phase d'élagage. Nous nous plaçons dans le cas d'un échantillon S << assez grand >> qui peut être découpé en un ensemble d'apprentissage A et un ensemble test T.

Phase d'expansion. On dispose en entrée d'un ensemble d'apprentissage A. La fonction utilisée pour mesurer le degré de mélange est la fonction de Gini (ou indice d'impureté de Gini) définie par l'équation (b). 

  1. Décider si un noeud est terminal. Un noeud p est terminal si Gini(p) £ i0 ou N(p) £ n0, où i0 et n0 sont des paramètres à fixer.
  2. Sélectionner un test à associer à un noeud. Soit p une position et soit test un test. Si ce test devient l'étiquette du noeud à la position p, alors on appelle Pgauche (respectivement Pdroite) la proportion d'éléments de l'ensemble des exemples associés à pqui vont sur le noeud en position p1 (respectivement p2). La réduction d'impureté définie par le test test est identique au gain et définie par :

                                         Gain (p,test) = Gini(p)-(Pgauche × Gini(p1) + Pdroite × Gini(p2)) .   (e)


Cette équation correspond à la définition du gain de l'équation (d) dans le cas de deux classes en choisissant pour fonction i la fonction de Gini. En position p (non maximale), on choisit le test qui maximise la quantité Gain(p,test).

  1. Affecter une classe à une feuille. On attribue la classe majoritaire.


Soit t l'arbre obtenu en sortie. Pour élaguer, on utilise l'ensemble test T. On suppose, en effet, que l'erreur apparente sur T est une bonne estimation de l'erreur réelle. Un élagué de t est obtenu en remplaçant un sous-arbre de t par une feuille. Une première solution serait d'estimer l'erreur réelle pour tous les élagués de t. Cette méthode est trop coûteuse en temps de calcul. Il faut, par conséquent, introduire une heuristique permettant de limiter le nombre d'élagués de t sur lesquels on va estimer l'erreur réelle. Nous décrivons maintenant la phase d'élagage qui prend pour entrée l'ensemble d'apprentissage A, l'arbre t produit et un ensemble test T.

  • Phase d'élagage. 
    1. construction de la suite des arbres. On construit une suite t0=t,...,tp telle que t0 soit l'arbre obtenu à la fin de la phase d'expansion, pour tout i, ti+1 est un élagué de ti et le dernier arbre de la suite tp est réduit à une feuille. Il nous faut définir le procédé de construction de ti+1 à partir de ti. Pour toute position p de ti, on note up le sous-arbre de ti en position p. On calcule la quantité

                                                                              g(p) = ∆app(p) / |up|-1                                            (f)


où ∆app(p) est la variation d'erreur apparente mesurée sur l'ensemble d'apprentissage A lorsqu'on élague t en position p et |up| est la taille de up. On peut remarquer que                                                                       


                                                                       app(p) = MC(p)-MC(up) / N(p)                                (g)

    1. où N(p) est le cardinal de l'ensemble des exemples de A associé à la position p de ti, MC(p) est le nombre d'éléments de A mal classés à la position p lorsqu'on élague ti en position p et MC(up) est le nombre d'éléments de A associés à la position p de ti mal classés par up.

      On considère alors la position p pour laquelle g(p) est minimale et ti+1 est l'élagué de ti en position p.
    2. choix final. On calcule pour chaque arbre ti de la suite construite au point précédent l'erreur apparente sur l'ensemble Test T. Cette valeur est prise comme estimation de l'erreur réelle. On retourne donc l'arbre qui minimise l'erreur apparente sur T.

Lorsque la taille de l'échantillon ne permet pas le découpage en ensembles de test et d'apprentissage, on utilise alors d'autres méthodes d'élagage. Le principe reste similaire, la différence est que l'on utilise la validation croisée pour obtenir des approximations de l'erreur réelle. 

Les principes de base de l'algorithme CART sont l'utilisation de la fonction de Gini et un élagage effectué soit à l'aide d'un ensemble test soit par validation croisée. Cependant, CART a été intégré à de nombreux environnements de fouille de données et a subi de nombreuses modifications et améliorations.

Un deuxième algorithme : C4.5 (Quinlan93 [2] )

On suppose toujours que le langage de représentation est constitué d'un certain nombre d'attributs. Ces attributs peuvent être binaires, qualitatifs (à valeurs dans un ensemble fini de modalités) ou continus (à valeurs réelles). Pour les attributs continus, on utilise des heuristiques qui permettent de les discrétiser. On utilise pour cela des critères statistiques qui permettent d'atteindre les deux objectifs suivants : un nombre de classes pas trop important et une bonne répartition entre les différentes classes. On peut par exemple utiliser la fonction entropie pour atteindre ces objectifs. Nous supposons maintenant que les attributs ont été discrétisés.

Nous supposons prédéfini un ensemble de tests n-aires. Pour définir l'algorithme, nous allons définir les trois opérateurs utilisés par l'algorithme C4.5 pour calculer un bon arbre de décision (phase d'expansion), puis nous verrons la phase d'élagage. On suppose disposer d'un ensemble d'apprentissage A.

On dispose en entrée d'un ensemble d'apprentissage A. On utilise la fonction entropie définie par l'équation (a). 

  1. Décider si un nœud est terminal. Un nœud p est terminal si tous les éléments associés à ce nœud sont dans une même classe ou si aucun test n'a pu être sélectionné (voir ci-après).
  2. Sélectionner un test à associer à un nœud. À chaque étape, dans l'ensemble des tests disponibles, ne peuvent être envisagés que les tests pour lesquels il existe au moins deux branches ayant au moins deux éléments (cette valeur par défaut peut être modifiée). Si aucun test ne satisfait cette condition alors le nœud est terminal. Soit p une position, on choisit alors le test qui maximise le gain défini dans l'équation (d) en utilisant la fonction entropie définie dans l'équation (a) pour mesurer le degré de mélange. La fonction Gain, ainsi définie, privilégie les attributs ayant un grand nombre de valeurs . Elle est donc pondérée par une fonction qui pénalise les tests qui répartissent les éléments en un trop grand nombre de sous-classes. Cette mesure de la répartition est nommée SplitInfo et est définie par :

                                                           SplitInfo(p,test) = - Σnj=1 P'(j/p) × log(P'(j/p))                        (h)

dans laquelle n est l'arité de test et P'(j/p) est la proportion des éléments présents à la position p prenant la j-ème valeur de test. Il faut remarquer que, contrairement à l'entropie, la définition précédente est indépendante de la répartition des exemples à l'intérieur des différentes classes. La valeur de Splitinfo ne dépend que de la répartition entre les différentes valeurs possibles pour le test. Cette fonction a des valeurs grandes lorsque le test a un grand nombre de valeurs possibles avec peu d'éléments pour chacune des valeurs. En effet, considérons le cas extrême d'un attribut n-aire avec un exemple par classe, la fonction vaut alors log n. À l'inverse, considérons la cas d'un attribut binaire pour lequel les exemples sont répartis uniformément entre ces deux valeurs, la fonction vaut alors 1. La nouvelle fonction de gain, appelée ratio de gain et notée GainRatio, est alors définie par :


                                                                 GainRatio (p,T) =  Gain (p,T) / SplitInfo (p,T)                        (i)

En position p (non maximale), on choisit le test qui maximise le GainRatio (option par défaut de C4.5). On peut modifier les options pour utiliser le Gain.

  1. Affecter une classe à une feuille. On attribue la classe majoritaire. S’il n'y a aucun exemple on attribue la classe majoritaire du nœud père.

Conclusion

Les méthodes à base d'arbres de décision les plus importantes sont :

  • CART développée par Breiman et al. en 84. Cette méthode, développée par des statisticiens, construit des arbres de décision binaires. Cette méthode peut être étendue pour traiter le cas d'attributs continus. Le critère de Gini est utilisé pour associer un test à un nœud. L'élagage de l'arbre se fait par estimation de l'erreur réelle en utilisant un ensemble test. La phase d'élagage peut être modifiée pour le cas d'échantillons de plus petite taille, on utilise alors la validation croisée comme estimation de l'erreur réelle.
  • ID3 développée par Quinlan en 83, améliorée en 93 par une nouvelle version C4.5. On ne se restreint pas à des attributs binaires. Le choix du test associé à un nœud se fait à l'aide de la fonction Gain ou de la fonction GainRatio basées sur la fonction entropie. La méthode peut prendre en compte le cas où les valeurs de certains attributs sont non spécifiées. Elle prend également en compte le problème des attributs continus. On peut choisir entre arbres et règles, l'élagage se fait sur l'arbre ou sur le système de règles et se base sur une estimation de l'erreur réelle à partir de l'ensemble d'apprentissage.
  • Signalons une dernière méthode basée sur le principe MDL (Minimum Description Length) de Rissanen. Cette méthode a été développée par Quinlan et Rivest [QR89]. Elle construit l'arbre de décision qui permet de coder de la façon la plus courte possible l'échantillon (on code l'arbre et les exceptions). Cette méthode permet de faire des ponts intéressants entre codages et probabilités et a des performances satisfaisantes.

Les arbres de décision fournissent des méthodes effectives qui obtiennent de bons résultats dans la pratique. Les arbres de décision possèdent l'avantage d'être compréhensibles par tout utilisateur (si la taille de l'arbre produit est raisonnable) et d'avoir une traduction immédiate en termes de règles de décision. Pour le système à base de règles induit, les règles sont mutuellement exclusives et l'ordre dans lequel sont examinés les attributs est figé. Les méthodes sont non optimales : les arbres produits ne sont pas les meilleurs. En effet, les choix dans la construction des arbres, basées sur de nombreuses heuristiques, ne sont jamais remis en question (pas de retour en arrière (ou backtraking)). Enfin, il est possible de modifier les valeurs de nombreux paramètres, de choisir entre de nombreuses variantes et faire le bon choix n'est pas toujours aisé. La taille des échantillons influera sur les critères d'élagage à choisir (sur l'ensemble d'apprentissage, sur un ensemble test, validation croisée, ...).

Enfin, comme les algorithmes présentés dans si-déçus permettent la génération de systèmes à base de règles, il nous faut faire le lien avec l'approche Systèmes Experts. Les deux approches << à partir de données >> et << par expertise >> être considérées comme concurrentes et complémentaires :

  • L'approche système expert peut être envisagée si l'on dispose d'une expertise suffisante dans le domaine d'application visé et si cette expertise est formalisable en termes de règles. La taille du domaine d'application doit être bien délimitée. L'expérience a prouvé que la maintenance et l'évolution des systèmes experts était une tâche difficile.
  • Les méthodes d'apprentissage sont utilisés dans des domaines où les experts n'arrivent pas à dégager les règles qu'ils utilisent (et d'ailleurs, en utilisent-ils ?). Les règles sont générées à partir de données (souvent des données historiques pour le problème).
  • Mais il arrive également que ces deux approches soient utilisées conjointement : des experts seront souvent de bon conseil pour dégager les attributs pertinents relativement à un problème donné ; dans certains cas, des systèmes d'apprentissage produiront automatiquement des règles qui pourront être directement insérés dans un système expert.

ML Supervised

Vote utilisateur: 0 / 5

Etoiles inactivesEtoiles inactivesEtoiles inactivesEtoiles inactivesEtoiles inactives

Objectifs

Dans cet article nous présentons les arbres de décision, qu’est-ce qu’un arbre de décision ? Quelques symboles pour bien comprendre les composent d’un arbre, comment dessiné un arbre ? Exemple d’analyse d’un arbre de décision, les avantages et les inconvénients de ce dernier et finalement la projection des arbres de décision sur l’apprentissage automatique et l’exploration de données.

Qu’est-ce qu’un arbre de décision ?

En théorie des graphes, un arbre est un graphe non orienté, acyclique et connexe. L’ensemble des nœuds se divise en trois catégories :

  • Nœud racine (l’accès à l’arbre se fait par ce nœud),
  • Nœuds internes : les nœuds qui ont des descendants (ou enfants), qui sont à leur tour des nœuds,
  • Nœuds terminaux (ou feuilles) : nœuds qui n’ont pas de descendant.

NB :

  • Non orienté = Un graphe non orienté -à-d. les arrêtes qui lie les nœuds n’ont pas un sens.
  • Acyclique = ou sans cycle c.-à-d. on ne peut pas construire un cycle qui passe par tous les nœuds.
  • Connexe = Un graphe est connexe s’il est possible, à partir de n’importe quel sommet (Nœud), de rejoindre tous les autres en suivant les arêtes.

Un arbre de décision est un schéma représentant les résultats possibles d'une série de choix interconnectés. Il permet à une personne ou une organisation d'évaluer différentes actions possibles en fonction de leur coût, leur probabilité et leurs bénéfices. Il peut être utilisé pour alimenter une discussion informelle ou pour générer un algorithme qui détermine le meilleur choix de façon mathématique.

Un arbre de décision commence généralement par un nœud d'où découlent plusieurs résultats possibles. Chacun de ces résultats mène à d'autres nœuds, d'où émanent d'autres possibilités. Le schéma ainsi obtenu rappelle la forme d'un arbre.

Les arbres de décision (AD) sont une catégorie d’arbres utilisée dans l’exploration de données et en informatique décisionnelle. Ils emploient une représentation hiérarchique de la structure des données sous forme des séquences de décisions (tests) en vue de la prédiction d’un résultat ou d’une classe. Chaque individu (ou observation), qui doit être attribué(e) à une classe, est décrit(e) par un ensemble de variables qui sont testées dans les nœuds de l’arbre. Les tests s’effectuent dans les nœuds internes et les décisions sont prise dans les nœuds feuille.

Symboles des arbres de décision

Forme

Nom

Signification

                

Nœud de décision

Indique une décision à prendre

 

Nœud de hasard (internes)

Illustre plusieurs résultats 


Branches alternatives

Chaque branche indique un résultat ou une action possible

 

Nœud terminal

Indique un résultat final

 

Comment dessiner un arbre de décision ?

Pour dessiner un arbre de décision, choisissez d'abord un support. Vous pouvez le dessiner à main levée sur du papier ou sur un tableau blanc, ou vous pouvez utiliser un logiciel d'arbres de décision spécialisé. Dans tous les cas, voici les étapes à suivre :

  1. Commencez par la décision principale. Dessinez une petite boîte pour la représenter, puis dessinez une ligne partant de la boîte vers la droite pour chaque solution ou action possible. Étiquetez-les.
  2. Ajoutez des nœuds internes et de décisionpour développer l'arborescence comme suit :
  • Si une autre décision est nécessaire, dessinez une autre boîte.
  • Si le résultat est incertain, dessinez un cercle (les cercles représentent les nœuds de hasard).
  • Si le problème est résolu, n'ajoutez rien (pour l'instant).

À partir de chaque nœud de décision, dessinez les solutions possibles. À partir de chaque nœud interne, dessinez des lignes représentant les résultats possibles. Si vous avez l'intention d'évaluer vos options de façon numérique, ajoutez la probabilité de chaque résultat et le coût de chaque action.

  1. Continuez à développer l'arbre jusqu'à ce que chaque ligne débouche sur un nœud terminal, indiquant qu'il n'y a plus de choix à faire ni de résultats possibles à prendre en considération. Ensuite, assignez une valeur à chaque résultat possible. Cela peut être un score abstrait ou une somme d'argent. Ajoutez des triangles pour signaler les nœuds terminaux.

Une fois l'arbre de décision terminé, vous pouvez commencer à analyser la décision qui s'impose à vous.

Exemple de création d'un arbre de décision

Météo et match de foot

 

Quel attribut faut-il sélectionner?

Arbre de décision final

 

 

Exemple d'analyse d'un arbre de décision

En calculant l'utilité ou la valeur attendue de chaque choix de l'arbre, vous pouvez minimiser les risques et optimiser les chances de parvenir à un résultat satisfaisant.

Pour calculer l'utilité espérée d'un choix, il vous suffit de soustraire le coût de cette décision des bénéfices attendus. Les bénéfices attendus sont égaux à la valeur totale de tous les résultats qui pourraient être dus à ce choix, chaque valeur étant multipliée par la probabilité de réalisation du choix qui lui est associé. Voici comment nous calculerions ces valeurs pour l'exemple ci-dessus :

Lors de l'identification du résultat le plus souhaitable, il est important de prendre en compte les préférences du décideur. Par exemple, certains peuvent préférer des options à faible risque tandis que d'autres sont prêts à prendre des risques pour gagner davantage.

Lorsque vous utilisez votre arbre de décision avec un modèle de probabilité, vous pouvez l'utiliser pour calculer la probabilité conditionnelle d'un événement, ou la probabilité qu'il ait lieu, à supposer qu'un autre événement se produise. Pour ce faire, il suffit de commencer par l'événement initial, puis de suivre le chemin depuis cet événement jusqu'à l'événement cible, en multipliant la probabilité de chacun de ces événements ensemble.

Utilisé ainsi, l'arbre de décision équivaut à un diagramme arborescent classique, schématisant les probabilités de certains événements, par exemple le fait de tirer à pile ou face deux fois.

Avantages et inconvénients

La popularité des arbres de décision se justifie par les raisons suivantes :

  • Ils sont faciles à comprendre.
  • Ils peuvent être utiles avec ou sans données concrètes, et les données quelles qu'elles soient nécessitent une préparation minimale.
  • De nouvelles options peuvent être ajoutées aux arbres existants.
  • Ils permettent de sélectionner l'option la plus appropriée parmi plusieurs.
  • Il est facile de les associer à d'autres outils de prise de décision.

Les arbres de décision peuvent toutefois devenir extrêmement complexes. Dans ce cas, un diagramme d'influence, plus compact, peut représenter une bonne alternative. Les diagrammes d'influence se focalisent sur les décisions, données et objectifs critiques.

Les arbres de décision dans l'apprentissage automatique et l'exploration de données

Un arbre de décision peut également servir à bâtir des modèles prédictifs automatisés, dont les applications peuvent concerner l'apprentissage automatique, l'exploration de données ou les statistiques. Cette méthode, appelée « apprentissage par arbre de décision », s'appuie sur les observations relatives à un élément pour prédire la valeur de cet élément.

Dans ces arbres de décision, les nœuds représentent les données plutôt que les décisions. Ce type d'arbre est aussi appelé arbre de classification. Chaque branche contient un ensemble d'attributs (règles de classification), associés à une étiquette de classe spécifique que l'on retrouve à l'extrémité de la branche.

Ces règles, également appelées règles de décision, peuvent être exprimées sous forme de clause « si... alors », où chaque décision ou valeur de donnée forme une clause, par exemple : « si les conditions 1, 2 et 3 sont remplies, alors l'issue x sera le résultat avec une certitude de y. »

Chaque donnée supplémentaire aide le modèle à prédire avec davantage de précision à quel ensemble limité de valeurs le sujet en question appartient. Cette information peut alors être utilisée comme entrée dans un modèle de prise de décision plus vaste.

Parfois, la variable prédite est un chiffre réel, par exemple un prix. Les arbres de décision avec une infinité de résultats possibles sont appelés des arbres de régression.

Pour une précision accrue, on regroupe quelquefois plusieurs arbres dans des méthodes d'ensembles :

  • L'ensachage (ou « bagging ») crée de multiples arbres en ré-échantillonnant les données source, puis fait voter ces arbres pour parvenir à un consensus.
  • Une classification par forêts aléatoires consiste en de multiples arbres conçus pour accroître le taux de classification.
  • Les arbres boostés peuvent être utilisés pour des arbres de régression et de classification.
  • Les arbres d'une forêt de rotation sont tous formés en utilisant l'analyse en composantes principales (Principal component analysis, PCA) sur une portion aléatoire des données.

Un arbre de décision est considéré comme optimal lorsqu'il représente la plus grande quantité de données possible avec un nombre minimal de niveaux ou de questions. Les algorithmes conçus pour créer des arbres de décision optimisés incluent notamment CART, ASSISTANT, CLS et ID3/4/5. Il est également possible de créer un arbre de décision en générant des règles d'associations, en plaçant la variable cible sur la droite.

Chaque méthode doit déterminer quelle est la meilleure façon de répartir les données à chaque niveau. Les méthodes courantes pour ce faire comprennent l'indice d'impureté de Gini, le gain d'information et la réduction de la variance.

L'utilisation des arbres de décision dans l'apprentissage automatique présente plusieurs avantages :

  • Le coût d'utilisation de l'arbre pour prédire des données diminue à chaque point de donnée supplémentaire.
  • Ils fonctionnent aussi bien pour les données de catégorie que numériques.
  • La modélisation des problèmes est possible avec plusieurs données de sortie.
  • Ils utilisent un modèle de boîte blanche, ce qui rend les résultats faciles à expliquer.
  • La fiabilité d'un arbre peut être testée et quantifiée.
  • Ils tendent à être précis, même si les hypothèses des données source ne sont pas respectées.

Mais ils présentent aussi quelques inconvénients :

  • Lors de la gestion de données de catégorie comportant plusieurs niveaux, le gain d'information est biaisé en faveur des attributs disposant du plus de niveaux.
  • Les calculs peuvent devenir compliqués lorsqu'une certaine incertitude est de mise et que de nombreux résultats sont liés entre eux.
  • Les conjonctions entre les nœuds sont limitées à l'opérateur « ET », alors que les graphiques décisionnels permettent de connecter des nœuds avec l'opérateur « OU ».