Scribd Logo
Importer

Bienvenue sur Scribd !

  • 67 vues

    Arb Dec

    Transféré par

    test
    Cet article décrit les arbres de décision, qui sont des outils d'aide à la décision représentant une situation sous forme d'arbres. Il explique leur construction, leur fonctionnement et leurs applications comme la classification, le diagnostic ou la prédiction.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Arb Dec

    Transféré par

    test
    67 vues19 pages
    Cet article décrit les arbres de décision, qui sont des outils d'aide à la décision représentant une situation sous forme d'arbres. Il explique leur construction, leur fonctionnement et leurs applications comme la classification, le diagnostic ou la prédiction.

    Description originale:

    arbre decision

    Titre original

    arbDec

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Cet article décrit les arbres de décision, qui sont des outils d'aide à la décision représentant une situation sous forme d'arbres. Il explique leur construction, leur fonctionnement et leurs applications comme la classification, le diagnostic ou la prédiction.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    67 vues19 pages

    Arb Dec

    Transféré par

    test
    Cet article décrit les arbres de décision, qui sont des outils d'aide à la décision représentant une situation sous forme d'arbres. Il explique leur construction, leur fonctionnement et leurs applications comme la classification, le diagnostic ou la prédiction.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 19

    Systèmes intélligents

    Les arbres de décision

    Nadia Abchiche
    Laboratoire IBISC
    [email protected]
    Définition

    • Un arbre de décision est un outil d'aide à la


    décision qui représente une situation plus ou
    moins complexe à laquelle on doit faire face
    sous la forme d'un arbre de façon à faire
    apparaître l'extrémité de chaque branche les
    différents résultats possibles en fonction des
    décisions prises à chaque nœud
    Exemple
    Tousse t˚c > 38 Classe

    Patient 1 oui oui malade


    Patient 2 oui non malade
    Patient 3 non non sain

    t˚c > 38 non


    oui
    Malade Tousse Tousse
    oui non oui non
    Malade ¬Malade Malade ¬Malade

    • Construction à partir de données.


    • La manière de le construire influe sur les performances.
    • Un arbre parfait est un arbre de décision tel que tout les
    exemples de l’ensemble d’apprentissage soient bien classés.
    Généralités

    • Objectifs :
    – Minimiser la taille de l’arbre (facilitant la recherche)
    – Établir un compromis entre le taux d’erreurs de classification sur
    l’ensemble d’apprentissage (données utilisées pour la construction)
    et sur l’ensemble de test (données utilisées pour valider la
    classification) afin de pouvoir de procéder à une généralisation.
    • On intervient à 2 niveaux :
    – 1. On sélectionne les attributs qui minimisent la taille de l’arbre tout
    en classant correctement les exemples de l’ensemble
    d’apprentissage.
    – 2. On élague certaines branches de manière à garder un pouvoir
    de généralisation (au prix de faire augmenter l’erreur sur
    l’ensemble d’apprentissage) (pendant la construction ou bien après
    la construction de l’arbre)
    Utilisation des ArbDec

    • Classification : données de toutes sortes


    • Apprentissage
    • Diagnostic : médical, de pannes,…
    • Supervision : réseau, matériel, applications,
    industrielles,…
    • Conception : produits, applications,
    territoriale,…
    • Prédiction : météo, trajectoire,…
    Utilisation des ArbDec
    • Classification
    – Les arbres de décision sont une
    représentation commode de fonctions de
    classification, moins puissants que les
    règles de production mais plus facile à
    utiliser.
    – Un arbre de décision permet de classer un
    objet à l’aide de questions : chaque nœud
    de l’arbre représente une question, chaque
    lien est une réponse à la question, et
    chaque feuille est une classe.
    Utilisation des ArbDec
    Classification
    • Exemple 1: la ballade du chien
    Les attributs:
    • Quel temps fait-il?{pluvieux, ensoleillé, couvert}
    • Température extérieure : attribut numérique
    • Voisin parti avec son chat : attribut booléen

    La décision à prendre : vais-je sortir mon chien?

    Temps? Cet arbre est équivalent à un


    couvert pluvieux
    soleil système déductif. Lequel?
    Température? tv
    Voisin abs?
    >10° <=10° non oui
    ballade Tv
    tv ballade
    Avantage des arbres de décision

    • 1. Faciles à comprendre et à utiliser.


    • 2. Nombre de tests limité par le nombre
    d’attributs (de questions).
    • 3. Construction efficace (mais
    technique)
    Construction d’un arbre de décision
    • À l’aide d’apprentissage par optimisation
    (pour obtenir un arbre petit et “correct").
    • On dispose d’un ensemble d’exemples
    E=(x,c). Chaque exemple est constitué:
    – 1. D’un ensemble x de réponses aux questions
    (possibles) de l’arbre. On appelle ces réponses
    (avec les questions qui y sont associé) des
    attributs.
    – 2. De la classe c de l’exemple, qui appartient à
    l’ensemble des classes possibles C
    Construction d’un arbre de décision (suite)

    Principe
    • Construction récursive, en découpant
    successivement l’ensemble d’exemples E.
    – 1. Si tous les exemples sont dans une seule
    classe, on place une feuille de cette classe.
    – 2. Sinon, on choisit une question (la plus
    discriminante possible), on découpe l’ensemble
    d’exemples suivant cette question. Pour chaque
    nouvel ensemble, on construit un sous-arbre de
    décision.
    Note : il est classique d’élaguer l’arbre ensuite à
    l’aide d’un ensemble d’exemples supplémentaires.
    Construction d’un arbre de décision
    (suite)
    Algorithme (cas binaire)
    • On suppose que toutes les questions ont comme réponse oui
    ou non.
    • X un ensemble de données
    • Procedure Construit_arbre(X)
    debut
    Si tous les points de X sont dans la même classe
    alors Créer une feuille de cette classe
    sinon choisir le meilleur sélecteur (la meilleure question) pour créer
    un noeud. Séparer X suivant ce sélecteur en Xd et Xg .
    Construit_arbre(Xd )
    Construit_arbre(Xg )
    finsi
    Fin
    Construction d’un arbre de décision (suite)
    Exemple 2
    Un écolier peut-il aller jouer dehors ? Voilà ce qu’il a observé :

    Devoir fini? Mère de Fait beau ? Goûter pris Réponse


    bonne ?
    humeur ?
    oui non oui non oui
    non oui non oui oui
    oui oui oui non oui
    oui non oui oui oui
    non oui oui oui non
    non oui non non non
    oui non non oui non
    oui oui non non non
    Construction d’un arbre de décision (suite)
    Exemple 2
    Choix de la question :

    •On dispose de 4 questions (DF, MBH, FB, GP).


    •Chaque question sépare les réponses positives (4 en
    tout) et négatives (4 en tout) en deux ensembles.
    •Par exemple, avec la question « Devoirs finis ? », on
    trouve trois réponses positives et deux réponses négatives
    pour OUI, et une réponse négative et deux réponses
    positives pour NON.
    •L’idée est de maximiser la séparation globale.
    •Les formules utilisées dérivent de la théorie de
    l’information : on cherche à maximiser le gain
    d’information.
    Construction d’un arbre de décision (suite)
    • Information : éléments techniques
    • (1) Les calculs dérivent des probabilités. L’entropie
    d’une variable ω pouvant prendre les valeurs {ωi }i∈I
    avec des probabilités p(ωi ) est définie comme :
    H(ω)= −∑i∈I p(ωi) log(p(ωi ))
    • L’entropie note l’incertitude sur la valeur de la
    variable.
    • Par exemple, initialement l’entropie de "Je peux aller
    jouer" est (en considérant le logarithme à base 2),
    H(c) = 1. Si on sait que les devoirs ne sont pas finis,
    elle devient H (c) = 0,8. La décroissance de l’entropie
    note une diminution de l’incertitude, donc un
    augmentation de l’information.
    Construction d’un arbre de décision (suite)
    Information : éléments techniques (suite)
    • Dans le cas de deux variables, ω pouvant prendre les
    valeurs {ωi }, et a pouvant prendre les valeurs {aj },
    on définit l’entropie de ω conditionnée par a comme :
    H(ω|a)=-∑i,j p(ωi ∧ aj ) log p(ωi |aj )
    • (note : lorsque p(ωi |aj ) = 0, p(ωi ∧ aj) = 0 donc le
    terme doit être considérée comme nul).
    • Cette entropie représente une incertitude sur ω
    indépendamment de a. Elle est d’autant plus faible
    que a permet de différencier les valeurs de ω. Ainsi
    pour a = ω, elle vaut 0 : connaître ω lève l’incertitude
    sur ω.
    Calcul des entropies conditionnées pour chaque question :
    • 1. Pour DF
    H = -3/ 8 ∗ log 3/5-2/8 ∗ log 2/5-1/8 ∗ log 1/3-2/8 ∗log 2/3=0, 95.
    • 2. Pour FB
    H = -2 ∗ 3/8 ∗ log 3/4 − 2 ∗ 1/8 ∗ log 1/4 = 0, 81.
    • 3. Pour MBH
    H = -2/8 ∗ log 24 − 28 ∗ log 24 − 38 ∗ log 34 − 18 ∗ log 14 = 0, 91.
    • 4. Pour GP
    H = 1.

    On choisit alors le test qui minimise l’entropie, soit FB, et on recommence.


    On obtient l’arbre suivant

    Temps = beau ?

    Faux Vrai

    Devoirs finis ?
    Goûter pris ?

    Maman Non Oui


    Non de bonne
    humeur ?

    Oui Non
    • Adaptations possibles:
    – Pour des attributs à plusieurs réponses
    (couleurs...), on peut soit traiter toutes les
    réponses à la fois, soit revenir à des questions
    oui/non.
    – Pour les attributs continus (numériques), on peut
    tester d’éventuels "seuils" dans les valeurs
    (exemple pour un poids : moins de 50 g, plus de
    500 g, etc.).
    – Peut être étendu pour traiter des données bruitées
    ou contradictoires.
    • Inconvénient majeur : difficile à maintenir
    (modification)
    Quelques références
    • L. Breiman, J. H. Friedman, R. A. Olshen, and C. J.
    Stone. Classification and regression trees. Technical
    report, Wadsworth International, Monterey, CA, 1984
    • Algorithme de base (ID3) :
    – J.R. Quinlan, "Discovering rules by induction from
    large collections of examples", D. Michie ed., Expert
    Systems in the Microelectronic age, pp. 168-201,
    1979.
    • Algorithme amélioré (ID3-IV) -
    – J.R. Quinlan, "Induction of Decision Trees", Machine
    Learning, vol. 1, pp. 81-106, 1986.
    • Ajouter article.

    Vous aimerez peut-être aussi