Data Mining
Séance no. 6, 21 Octobre 2013
Prof. Chiraz Ben Abdelkader
ENSI
Plan
• Classification Supervisée par arbres de décision :
1) Introduction & definitions
2) Construction d’un arbre de decision
3) Exemples (TD)
10/27/2013
1
Références
• Notes de cours (Français) : Prof. Philippe Preux, Chapitre 3
• Livre (Anglais): Data Mining, Practical ML tools and techniques,
Chapitre 4 p. 99-112
(Disponibles sur mon Google Drive, sous le dossier « Références &
Publicité
Ressources »)
Introduction
10/27/2013
2
Introduction
• Un arbre a une racine, des nœuds, des branches, et des feuilles
• Un arbre de décision ressemble à un organigramme de
programmation, ou :
• Chaque nœud (y compris la racine) correspond à un test logique sur la valeur
d’un ou plusieurs attributs,
• Chaque branche partant d’un nœud correspond à une ou plusieurs valeurs de
ce test,
• A chaque feuille est associée une valeur de la classe, y Y.
Classification avec un arbre de décision
• Pour classer x, on parcourt l’arbre de décision de la racine à une
feuille, selon les valeurs des attributs xi
Publicité
• La feuille à la fin de ce chemin est la prédiction de la classe qui
correspond à x
• L’exécution du classeur arbre de décision s’agit d’un chemin qui mène
de la racine a une feuille, et dont les branches sont marques avec les
valeurs des attributs xi
10/27/2013
3
Exemple 1
Exemple 1 (suite)
10/27/2013
4
Exemple 2
• On dit qu’une donnée x est couverte par un nœud si ce nœud est
inclut dans le chemin d’exécution qui correspond à x
• Question: dans Exemple 2, la racine de l’arbre couvre quel données?
10/27/2013
Publicité
5
Construction d’un Arbre de Décision
Construction d’un Arbre de Décision
10/27/2013
6
Algorithme ID3
• Les approches d’induction les plus fréquemment utilisées sont ID3,
C4.5, et C5.0, par Ross Quinlan
• ID3 : ne prend en compte que des attributs nominaux
• C4.5 et C5.0: extensions de l’ID3, pour prendre en compte des attributs
quantitatifs (numériques)
• ID3 = Iterative Dichotomiser 3, par Ross Quinlan en 1979.
Algorithme ID3
• Caractéristiques importantes :
• ne prend en compte que les attributs nominaux
• chaque nœud correspond à un test logique sur la valeur d’un seul attribut (et
Publicité
non pas plusieurs attributs, comme dans le cas général).
• Donc, chaque feuille correspond à une combinaison unique des valeurs des p
attributs
10/27/2013
7
10/27/2013
8
ID3 : Choix de l’attribut a*
• Celui qui maximise le gain d’information
• Intuitivement, c’est celui le plus discriminant, qui rend les exemplaires
dans les sou-nœuds de la racine actuelle les plus « homogènes »
• Notion d’entropie
• Notion de gain d’information