| Fievre | Douleur | Toux | Maladie |
| oui | Abdomen | non | Appendicite |
| non | Abdomen | oui | Appendicite |
| oui | gorge | non | rhume |
| oui | gorge | oui | rhume |
| non | gorge | oui | mal de gorge |
| oui | non | non | aucune |
| oui | non | oui | rhume |
| non | non | oui | refroidissement |
| non | non | non | aucune |
| << précédent | index |
L'objectif de ce TD est de comprendre l'algorithme ID3 qui permet la création d'un arbre de décision à partir d'un ensemble de données et de maitriser l'outil DTree qui permet de créer de manière automatique des arbres de décision à partir d'un ensemble de données.
Compétences à acquérir
Les arbres de décision sont des classifieurs pour des données représentées par des ensembles attribut/valeur. Un arbre est constitué :
Voici un exemple d'arbre de décision, créé à partir des données contenu dans le tableau. Les attributs sont "Fievre", "Douleur" et "Toux". La classe est "Maladie".
| |
Le but d'un arbre de décision est de permettre de faire de la prédiction : déterminer la classe d'un nouvel exemple à partir des valeurs de ses attributs. La prédiction est utilisée par la plupart des sites de vente. En effet lorsque vous allez sur ce genre de site, on vous propose souvent des articles susceptibles de vous intéresser. Pour cela les sites effectuent du data mining : ils collectent un grand nombre de données sur les achats et les pages visitées par les clients. À l'aide de ces données, ils peuvent ainsi déterminer quel produit ou quelle catégorie de produit est acheté en fonction des caractéristiques des clients. Lorsqu'un nouveau client lambda surfe sur le site, ce dernier est capable de proposer des articles susceptibles de lui plaire en fonction des pages qu'il visite par exemple et ainsi augmenter les chances d'achats.
La construction d'un arbre de décision ne se fait pas au hasard. Le but est de déterminer les meilleurs attributs à placer à chaque noeud pour que l'arbre construit soit le plus petit possible (plus l'arbre est petit plus la prédiction sera facile à obtenir) et qu'en même temps l'arbre soit capable d'effectuer de bonne prédiction. La construction d'un arbre se fait à partir d'un ensemble de données appelé base d'apprentissage. Ces données sont des exemples de la forme (A_1,...,A_N,C_i) où A_1,..,A_n sont les valeurs de chaque attribut et C_i la valeur de la classe pour l'exemple. Une fois l'arbre construit, on le teste généralement sur un ensemble de données appelé base de test.
La construction de l'arbre de décision se fait à l'aide d'une mesure de désordre de la base d'apprentissage. Le but est donc de sélectionner l'attribut permettant de réduire ce "désordre". Lorsqu'on sélectionne un attribut, on divise pour chaque valeur de cet attribut la base d'apprentissage il est alors possible de calculer sur ces nouveaux sous-ensemble d'exemples la valeur d'apprentissage. On peut ainsi déterminer le gain (en termes de réduction de "désordre") obtenue par l'attribut faisant la différence entre le désordre initial et la somme des désordres pour chaque sous-ensemble d'exemples. Le meilleur attribut sera donc celui ayant un meilleur gain. Le processus est itéré ensuite pour chaque nouveau sous ensemble d'exemple ainsi crée. On arrête de créer de nouveau noeuds soit parce que le sous ensemble d'exemples ne peut plus être divisé (un seul exemple) soit parce que le sous ensemble d'exemple a une valeur de désordre nulle soit parce que l'on a imposé une hauteur maximale de l'arbre.
Pour mesurer le désordre on peut utiliser la fonction d'entropie, qui est ensuite utilisée pour calculer le gain d'un attribut. On choisit alors l'attribut ayant le gain maximal.
1) Déterminez l'arbre de décision des exemples. Vous détaillerez à chaque fois le calcul de l'entropie et du gain. Trouvez vous le même arbre ?
2) Déterminez l'arbre de décision des exemples ci dessous. Vous détaillerez à chaque fois le calcul de l'entropie et du gain.
Le logiciel Dtree est disponible dans outils. Cliquez sur le lien, sauvegardez le dossier dtree.rar sur le bureau puis dézippez l'archive en cliquant dessus. Ouvrez le dossier dtree obtenu en dézippant l'archive et cliquer sur l'icone suivante 
Vous arrivez alors devant l'interface suivante : 
Pour commencer, nous allons apprendre à utiliser Dtree à l'aide des exemples stockés dans sa base.
Les données sont composées d'un ensemble d'exemples qui constituent la base d'apprentissage (training examples). Il est possible de créer une base de test à partir des exemples de la base d'apprentissage.
Pour créer un arbre de décision à partir de votre base d'apprentissage, cliquez sur solve [voir]. La barre d'outils propose des boutons afin de créer, modifier l'arbre de décision :
Il est possible de créer votre propre base d'exemples.
Vérifiez les arbres de décisions obtenus par calcul à l'aide de Dtree.
