Algorithmes d'apprentissage par arbres de décision

Géneralités

Algorithmes d'apprentissage par arbres de décision

• Une variable cible avec plusieurs variables prédictives.
• Un ensemble de nœuds de décision connectés par des branches.
• Un nœud racine et des feuilles.
• Le nœud racine au sommet du diagramme
• Chaque nœud non-feuille correspond à une variable prédictive subie à un test sur sa valeur

Les types d'arbre de décision sont basés sur le type devariable cible que nous avons. Il peut être de deux types:

• Variable catégoriale: Arbre de décision qui a une variable cible catégorielle. Exemple: «L'élève jouera au cricket ou non», c'est-à- dire OUI ou NON. En parle de la classification.
• Variable continu: Arbre de décision a une variable cible continue.

Début

L’algorithme part de la racine de l’arbre.

Boucle de parcours de l’arbre

Pour chaque nœud, on choisit la variable qui sépare le mieux les individus en fonction des catégories de la variable cible.

Séparation des individus.

Fin de boucle

Fin

• Chaque branche précise la valeur que prend la variable prédictive du nœud à l‟origine de la branche.
• Chaque nœud feuille correspond à la variable cible représente une classe.
• Un nœud feuille est pur si les valeurs de la variable cible sont les mêmes pour tous les enregistrements de ce nœud,

Exemple de construction d'un arbre

Temps = beau ?

Conditions d'arrêt du partitionnement :

1. Tous les enregistrements d'un nœud se trouvent dans la même classe,

2. Il n'y a plus d'attributs pour faire le partitionnement, dans ce cas, le nœud est transformé en feuille et la classe associée est la

plus fréquente dans l'ensemble,

3. Il n'y a plus d'enregistrements.

Vrai

Faux

Algorithme d'apprentissage générique

entrée : langage de description ; échantillon S

début

Initialiser à l'arbre vide ; la racine est le noeud courant

répéter

Décider si le noeud courant est terminal

Si le noeud est terminal alors

Affecter une classe

sinon

Sélectionner un test et créer le sous-arbre

FinSi

Passer au noeud suivant non exploré s'il en existe

Jusqu'à obtenir un arbre de décision

fin

Temps = beau ?

vrai

faux

Devoirs finis ?

Gouter pris ?

vrai

faux

vrai

Maman de bonne humeur ?

vrai

faux

NON

OUI

NON

OUI

méthodes effectives

bons résultats dans la pratique

compréhensibles

Algorithme

Temps=beau

vrai

faux

vrai

vrai

vrai

faux

faux

faux

Décision

OUI

OUI

OUI

OUI

NON

NON

NON

NON

Maman de bonne

humeur

faux

vrai

vrai

faux

vrai

vrai

faux

vrai

Goûter pris

faux

vrai

faux

vrai

vrai

faux

vrai

faux

Devoirs finis

vrai

faux

vrai

vrai

faux

faux

vrai

vrai

E(DF)=5/8 I(DF=vrai)+3/8 I(DF=faux)

I(DF=vrai)= -3/5 log(3/5)-2/5 log(2/5)

I(DF=faux)= -1/3 log(1/5)-2/3 log(2/3)

E(DF)=0.95, E(BH)=0.93, E(TB)=0.8, E(GP)=1

Calcul de l'entropie

--> On choisit l'attribut qui minimise l'entropie.

Choix de Meilleur attribut (attribut de division)

– Il s'agit d'évaluer localement quel attribut apporte « le plus d'information » (ou encore « est le plus corrélé ») au résultat à prédire.

– Différentes mesures introduites:

• L'indice l'entropie,
• L'indice de Gini,
• Le critère du x²,
• L'indice Twoing,
• ...

Température < 37

Non

Malade

Oui

Gorge irritée

Non

Oui

Bien portant

Malade

SI Température < 37 ET gorge irritée ALORS malade

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

SI NON(Température < 37) ALORS malade

Jeux

d’apprentissage

Algorithme de classification

• 1: Construction de l‟arbre
• 2: Simplification de l‟arbre

--> POUR

• plus pures possible (classes homogènes),
• Des branches courtes et les moins nombreuses possibles.

ARBRE DE DECISION

Malade

oui

non

non

non

oui

Gorge irritée

oui

non

non

non

oui

Température

>37

<=37

<=37

>37

>37

1

2

3

4

5

Classificateur

(Modele)

Questions:

– Comment choisir les attributs ?

– Comment isoler les valeurs discriminantes?

• Deux problèmes vont intervenir :

– Le problème du nœud : quelle variable choisit-on à chaque nœud ?

– Le problème de la branche : quelles branches définit-on sous chaque nœud. Autrement dit quelles catégories choisit-on pour les prédicteurs ?

SI Température < 37 ET gorge irritée ALORS malade

C'est quoi ?

et à quoi sert ?

Géneration

Principe

– Pour chaque nœud, on choisit la variable qui sépare le mieux les individus en fonction des catégories de la variable cible.

– On répète l'opération jusqu'à ce qu'elle ne soit plus possible ou plus souhaitable

– Les feuilles ainsi construites sont toutes majoritairement constitués d'individus d'$une seule classe.

– La branche allant de la racine à une feuille constitue une règle de classification.

– L'ensemble des règles constitue le modèle

--> Plus intuitives et populaires du Data Mining :

• Elle fournit des règles explicites de classification.
• Elle supporte les données hétérogènes, manquantes, ….

--> Les arbres de décision:

• Sont à la frontière entre les méthodes prédictives et descriptives.
• C'est une technique de classification :

Hiérarchique,

Descendante.

• C'EST QUOI ? A QUOI SERT ?
• GENERALITES
• GENERATION
• ALGORITHME
• EXEMPLE

Merci pour votre attention

Nora El-Haouirich

Nawfal El Manfaloti