Chapitre 2 Apprentissage automatique : les arbres de décision Les ...
Les algorithmes d'apprentissage par arbres de décision sont efficaces, .... Le
dernier attribut binaire E a la valeur oui si le client a un niveau d'études ...
part of the document
e des arbres de décision
HYPERLINK "http://www.grappa.univ-lille3.fr/polys/apprentissage/sortie004.html" \l "toc9" Un premier algorithme : CART (Breiman et al. [ HYPERLINK "http://www.grappa.univ-lille3.fr/polys/apprentissage/" \l "Breiman84" BFOS84])
HYPERLINK "http://www.grappa.univ-lille3.fr/polys/apprentissage/sortie004.html" \l "toc10" Un deuxième algorithme : C4.5 (Quinlan 93 [ HYPERLINK "http://www.grappa.univ-lille3.fr/polys/apprentissage/" \l "Quinlan93" Qui93])
HYPERLINK "http://www.grappa.univ-lille3.fr/polys/apprentissage/sortie004.html" \l "toc11" Conclusion
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.
2.1
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 HYPERLINK "http://www.grappa.univ-lille3.fr/polys/apprentissage/" \l "arbredesmalades" ??.
INCLUDEPICTURE "http://www.grappa.univ-lille3.fr/polys/apprentissage/sortie003.gif" \* MERGEFORMATINET
Figure 2.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 {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 HYPERLINK "http://www.grappa.univ-lille3.fr/polys/apprentissage/" \l "arbredesmalades" ?? sont :
eð étiquetée par le test Température it performs quite well on large samples with at least 1000 test cases. With fewer cases, the risks of training on the test cases is greater.
Cette méthode est présentée dans l'exercice HYPERLINK "sortie006.html" \l "exo:elagagec45" ??. Une autre heuristique est proposée par C4.5. On construit le système à base de règles associé à l'arbre de décision produit en sortie de la phase d'expansion. On choisit ensuite une méthode permettant de coder à la fois les règles et les exceptions (exemples mal classifiés par les règles). Lorsqu'on supprime une règle, on risque de voir augmenter le nombre d'exceptions. Mais il se peut aussi que la taille du codage diminue globalement. Dans ce cas, on choisit la règle dont la suppression produit la plus forte diminution. On applique ce procédé de façon itérative tant que la taille des codages diminue. Cette méthode est une application du principe MDL (Minimum Description Length) qui consiste à choisir parmi plusieurs théories celle dont le codage (théorie plus exceptions) est minimal.
2.5.3
Améliorations
Attributs discrets
Pour les attributs discrets possédant un grand nombre de valeurs, nous avons vu que la fonction GainRatio permettait d'éviter de privilégier ces attributs. Il existe, de plus, une option de C4.5 qui permet le regroupement des valeurs. Par exemple, si on dispose d'un attribut A prenant les valeurs a, b, c et d, en standard le test considéré serait 4-aire. Si on active l'option regroupement, seront également considéré des tests de la forme : le test binaire AÎð {a,b} et AÎð {c,d} ; le test ternaire A=a , A=c et AÎð {b,d} ; ...
Attributs continus
Pour les attributs continus, la discrétisation peut être laissée à un expert du domaine d'application. Par exemple, en médecine, l'expérience du domaine peut avoir permis la mise en évidence l'existence de valeurs seuil pour un attribut correspond à une mesure médicale. Sinon, l'algorithme gère les attributs continus de la façon suivante : les exemples sont triés dans l'ordre croissant pour l'attribut continu A considéré, on considère alors tous les tests de la forme A>ai + ai+1/2 où ai et ai+1 sont deux valeurs consécutives de l'attribut A. Par exemple, supposons que A prenne les valeurs 1 ; 3 ; 6 ; 10 ; 12, alors on considère les tests A>1,5 ; A>4,5 ; A>8 et A>11, ces tests participent alors à la compétition dans la recherche du test apportant le meilleur gain (fonction Gain ou GainRatio, selon l'option choisie).
Attributs à valeurs manquantes
Dans de nombreux problèmes concrets, il existe certains attributs dont les valeurs ne sont pas renseignées. Par exemple, si on dispose du descriptif de patients, il est très probable que toutes les mesures ne soient pas disponibles car elles n'ont pas pu être faites pour tous les patients. Pour classifier un exemple possédant des valeurs manquantes à l'aide d'arbres de décision, on procède comme dans le cas standard, lorsque l'on rencontre un test et que la valeur de l'attribut est manquante, on considère la branche majoritaire. Pour la phase d'apprentissage, on suppose que la valeur de cet attribut suit la distribution des valeurs connues. Le lecteur peut se reporter à l'exercice HYPERLINK "sortie006.html" \l "exo:valeursmanquantes" ??.
2.6
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 noeud. 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 (voir [ HYPERLINK "http://www.grappa.univ-lille3.fr/polys/apprentissage/sortie008.html" \l "Quinlan93" Qui93]). On ne se restreint pas à des attributs binaires. Le choix du test associé à un noeud 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 [ HYPERLINK "http://www.grappa.univ-lille3.fr/polys/apprentissage/sortie008.html" \l "QuinlanRivest89" 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 terme 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 ce chapitre 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 > et > ê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 terme 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.
HYPERLINK "http://www.grappa.univ-lille3.fr/polys/apprentissage/sortie003.html" INCLUDEPICTURE "http://www.grappa.univ-lille3.fr/polys/apprentissage/previous_motif.gif" \* MERGEFORMATINET HYPERLINK "http://www.grappa.univ-lille3.fr/polys/apprentissage/index.html" INCLUDEPICTURE "http://www.grappa.univ-lille3.fr/polys/apprentissage/contents_motif.gif" \* MERGEFORMATINET HYPERLINK "http://www.grappa.univ-lille3.fr/polys/apprentissage/sortie005.html" INCLUDEPICTURE "http://www.grappa.univ-lille3.fr/polys/apprentissage/next_motif.gif" \* MERGEFORMATINET
