Tree decison

DATA MINING

TECHNIQUES

PRÉDICTIVES

MOHAMED HENY SELMI

ECOLE SUPÉRIEURE PRIVÉE D'INGÉNIERIE ET DE TECHNOLOGIES

OBJECTIFS DES

TECHNIQUES PRÉDICTIVES

visent à extrapoler de nouvelles informations à partir des informations

présentes : scoring

expliquent les données

il y a une variable cible à prédire.

Mohamed Heny SELMI © ESPRIT 2012-2013

DEUX GRANDES

FAMILLES

CLASSEMENT

la variable à exprimer est qualitative

on parle aussi de discrimination

scoring : classement appliqué à une problématique d’entreprise

PREDICTION

la variable à exprimer est continue

on parle aussi de régression

apprentissage supervisé (Réseaux de Neurones)


CLASSEMENT

consiste à placer chaque individu de la population dans une classe, parmi

plusieurs classes prédéfinies, en fonction des caractéristiques de l’individu

indiquées.

Le résultat du classement est un algorithme permettant d’affecter chaque

individu à la meilleure classe.


PRÉDICTION

La prédiction consiste à estimer

-la valeur d’une variable continue (dite « à expliquer »,

« cible », «dépendante » ou « endogène »)

- en fonction de la valeur d’un certain nombre d’autres

variables (dites « explicatives », «indépendantes » ou

«exogènes »)


MÉTHODES PRÉDICTIVES


MODÈLE À BASE DE RÈGLES LOGIQUES :

ARBRE DE DÉCISION

(TREE DECISION)


PRINCIPE DES ARBRES DE DÉCISION

Réaliser la classification d'un objet par une suite de tests sur les attributs qui le décrivent.

Organiser l'ensemble des tests

possible comme un arbre.

Une feuille de cette arbre désigne

une des classes (mais à chaque

classe peut correspondre plusieurs

feuilles ).

Chaque nœud est associé à un test

portant sur un ou plusieurs attributs.

La classification s‘effectue en

partant de la racine pour poursuivre

récursivement le processus jusqu’à ce

qu'on rencontre une feuille.


EXEMPLE DÉTECTION DE LA

GRIPPE

Apparition soudaine de fièvre élevée

Le patient est fatigué

Rhinorrhée (nez qui coule)

Toux

Douleurs à la gorge

Enrouement, douleurs dorsales, des membres et

céphalées

Grippe


REPRÉSENTATION SOUS FORME

D’ARBRE

fièvre

toux fatigue

Maux de gorge

grippe

Nez qui coule

Courbatures et

maux de tête

angine


EXEMPLE BANCAIRE

Prédire si un client sera un client qui rembourse son prêt avec succès (classe OUI) ou un client qui a des difficultés de remboursement (classe NON)

Client Logement salaire Salaire S. co-emp Succès

E1 locataire A Moyen Elevé NON

E2 locataire A Moyen Faible NON

E3 propriétaireA Moyen Elevé OUI

E4 famille B Moyen Elevé OUI

E5 famille C Elevé Elevé OUI

E6 famille C Elevé Faible NON

E7 propriétaireC Elevé Faible OUI

E8 locataire B Moyen Elevé NON

E9 locataire C Elevé Elevé OUI

E10 famille B Elevé Elevé OUI

E11 locataire B Elevé Faible OUI

E12 propriétaireB Moyen Faible OUI

E13 propriétaireA Elevé Elevé OUI

E14 famille B Moyen Faible NON


REPRÉSENTATION PAR ARBRE DE

DÉCISION

Logement

Salaire Salaire co emp

Locataire Famille Propriétaire

OUI

NON OUI NON OUI

Moyen Elevé Faible Elevé


PROPRIÉTÉ DE L’ARBRE DE

DÉCISION

Chaque nœud interne teste un attribut

Chaque branche correspond à une valeur d’attribut

Chaque feuille correspond à une classe unique (décision OUI ou décision NON) ou une classe majoritaire

On cherche un arbre le plus « simple » possible expliquant l’ensemble des cas


CONSTRUCTION DE

L’ARBRE DE DÉCISION

Comment choisir, parmi l’ensemble des variables disponibles, la variable de segmentation d’un sommet ?

Lorsque la variable est continue, comment déterminer le seuil de coupure lors de la segmentation?

Comment déterminer la bonne taille de l’arbre ? Est-il souhaitable de produire absolument des feuilles pures selon la variable à prédire, même si le groupe correspondant correspond à une fraction très faible des observations ?

Comment affecter la valeur de la variable à prédire dans les feuilles ? Lorsque le groupe est pur la réponse est évidente, dans le cas contraire, nous verrons qu'il nous faut adopter une stratégie


ALGORITHME ARBRE DE DÉCISION

Procédure : construire-arbre(X)

SI tous les points de X appartiennent à la même classe

ALORS créer une feuille portant le nom de cette classe

SINON

choisir le meilleur attribut pour créer un nœud

le test associé à ce nœud sépare X en des parties : Xd………Xg

construire-arbre(Xd)

.

.

.

construire-arbre(Xg)

FIN construire-arbre(X)


DÉROULEMENT DE LA

CONSTRUCTION

Recherche de la variable qui sépare le mieux

Applique la séparation à la population

Obtention de nouveaux nœuds

Arrêt de l’approfondissement de l’arbre lorsque les conditions d’arrêts sont rencontrées


Arrêt de l’approfondissement de l’arbre lorsque les conditions d’arrêts sont rencontrées

CONDITIONS

D’ARRÊTS EXISTANTES

Profondeur de l’arbre atteint une limite fixée

(=nombre de variables utilisées)

Nombre de feuilles atteint un maximum fixé

L’effectif de chaque nœud est inférieur à un seuil fixé

La qualité de l’arbre est suffisante

La qualité de l’arbre n’augmente plus de façon sensible


CHOIX DU MEILLEUR ATTRIBUT

Comment trouver les variables qui séparent le mieux les individus

de chaque classe ?

… Plusieurs critères de choix de variables correspondant à

différents types d’arbres :

- CART (Classification And Regression Tree : Indice de Gini)

- CHAID (Chi square Automatic Interaction Detection)

- C5.0 (Entropie de Shannon)


ALGORITHME CART

Parmi les plus performants et plus répandus

…Accepte tout type de variables

…Critère de séparation : Indice de Gini

Avec n : nombre de classes à prédire

fi : fréquence de la classe dans le nœud

Plus l’indice de Gini est bas, plus le nœud est pure


ALGORITHME CART

Exemple :


ALGORITHME CART

Ainsi,

En séparant 1 nœud en 2 nœuds fils on cherche la plus

grande hausse de la pureté

La variable la plus discriminante doit maximiser

IG(avant sep.)-[IG(fils1)+……+IG(filsn)]


ALGORITHME CART

Répartition des individus dans les nœuds

- Quand l’arbre est construit : critères de division connus

-On affecte chaque individu selon les règles obtenues

remplissage des feuilles

Pour chaque feuille : plusieurs classes C

- Pc = Proportion d’individus de la feuille appartenant à la

classe c

- On affecte à la feuille la classe pour laquelle Pc est la

plus grande Mohamed Heny SELMI © ESPRIT 2012-2013

ALGORITHME CART

Taux d’erreur global de l’arbre

=

somme pondérée des taux d’erreur des feuilles

Exemple :


AVANTAGES

Résultats explicites

• Arbre

• Règles de décisions simples

• Modèle facilement programmable pour affecter

de nouveaux individus

Peu de perturbation des individus extrêmes

• Isolés dans des petites feuilles

Peu sensible au bruit des variables non

discriminantes

• Non introduites dans le modèle


AVANTAGES

CART permet l’utilisation de variables de tous types

• Continues, discrètes, catégoriques

Traitement d’un grand nombre de variables explicatives

Peu d’hypothèses préalables


INCONVÉNIENTS

Arbre non optimaux

• Utilisation de règles heuristiques

• Utilisation des variables non simultanée mais

séquentielle

• « Effet papillon » On change une variable dans

l’arbre, tout l’arbre change

Nécessité d’un grand nombre d’individus

• Pour avoir 20-30 individus minimum par nœud pour

que les règles aient une valeur


INCONVÉNIENTS

Temps de calculs importants

• Recherche des critères de division

• Élagage


EXERCICE Une banque dispose des informations suivantes sur un ensemble de clients:

-M : moyenne des montants sur le compte client.

-A : tranche d'âge du client.

-R : localité de résidence du client.

-E : valeur oui si le client a un niveau d'études supérieures.

- I : classe oui correspond à un client qui effectue une consultation de ses comptes bancaires en utilisant Internet

Question : trouver un

arbre de décision

capable de dire si un

client effectue des

consultations de ses

comptes par Internet Mohamed Heny SELMI © ESPRIT 2012-2013

INDICATION

Indice de Gini : quantifie la pureté du nœud

Plus qu’un nœud est pure, plus qu’il existe une classe majoritaire dans ce nœud

Sachant que la variable cible est I, on commence à calculer l’indice de Gini de la racine avant la première séparation

Calculer Indice de Gini : variable par variable

Calculer les gains de chaque valeur calculée : c’est l’écart entre l’indice de Gini de la racine et toute valeur de nœud fils

On applique toujours la règle : plus le gain G est important, plus la variable génère des nœuds pures


APPLICATION

TRAVAUX PRATIQUES

1.

On reprend le fichier « faillite_etreprise.txt »

Bibliothèque nécessaire « rpart »

2.

Télécharger le fichier « Decisions_entrep »

On considère les deux variables cibles : « Type_Action » « Discipline_Action »

On génère deux arbres de décisions

Essayer la donnée ( information) suivante : arbre_TA(c(1,2,3,2,1,3,3,2,1,3,2,1,2,1,4))

3. Reprendre le même travail avec le fichier « Don_osteo »


INDICATION TP

library(rpart)

? rpart

don_entrep=read.table("Faillite_entrep.txt", header=TRUE)

don_entrep

res.tree=rpart(ET ~ FD + RA + AD + AV, data=don_entrep)

res.tree

don_decision=read.table("Decisions_entrep.txt", header=TRUE)

names(don_decision)

don_TA=don_decision[,c(1:16)]

don_TA

res.tree1=rpart(Type_Action ~ Type_projet + Phase_projet + Discipline + Pays + Priorité + Type_Impact + Degré_Impact + Probabilité_apparition + Stratégie_réponse + Catégorie_risque + Cause_Materiel + Cause_Personnel + Cause_Méthode + Cause_Milieu + Cause_Matière, data=don_TA)

res.tree1

? rapa

? rpart

source("arbre_TA.txt")

arbre_TA(c(1,2,3,2,1,3,3,2,1,3,2,1,2,1,4))


Documents

Tree decison