Stages Master 1 (2009) > Stage proposé n°1
Sujet Stage :
Arbre de décisions et discrétisation pour de la classification symbolique
Résumé du travail proposé :
Ce stage s’intègre dans les travaux d’une thèse actuellement en cours au laboratoire. Celle-ci a pour but de développer une méthode de classification symbolique hybride entre les méthodes d’arbre de décision et de Treillis de Galois.
Concernant les arbres de décision, ils existent différents algorithmes de construction des arbres se différenciant par les critères de coupe utilisés.
Ce stage a pour but l’étude des différents critères de coupe nécessaires à la discrétisation dans les arbres de décision ainsi que l’implémentation (programmation java) de ceux-ci et de l’implémentation des algorithmes de construction connus ID3 et C4.5 …
Mots clés :
Arbres de décision, critère de coupe, implémentation java
Informations complémentaires :
Encadrantes: Nathalie Girard, Karell Bertet, Muriel Visani
Projet scientifique : Imédoc
Cadre de coopération :
Date de début du stage : Février 2010
Durée du contrat : 10 semaines (M1)
Contexte de l’étude:
La classification des données se déroule généralement en deux étapes tout d’abord l’acquisition des données et de leurs descripteurs sous forme d’une table de type objet X attributs puis la construction du classifieur (méthode d’analyse).
Il existe différent type de descripteurs :
- Des variables qualitatives ou discrètes : taille de T-Shirt, qualité d’une personne, …
- Des variables quantitatives ou continues : températures, solde de compte, ….
Et il existe différents types de méthodes de classification entre autres les méthodes dites symboliques qui ont pour avantage de pouvoir intégrer des données à la fois qualitatives et quantitatives. Elles offrent ainsi l’avantage de pouvoir choisir et adapter les paramètres du classifieur. Parmi ces méthodes symboliques se trouvent les arbres de décision.
L’arbre de décision [1], très étudié dans les années 90, est une référence autant populaire en statistiques qu’en apprentissage automatique, il manipule des données quantitatives et des données qualitatives : chaque nœud correspond à un test sur un attribut, chaque feuille à une classe, et chaque parcours de la racine vers une feuille à un scenario de classification.
Pour un même jeu de données, ils existent plusieurs arbres de décision. Ils se différencient sur les critères nécessaires à la construction de l’arbre : le critère de sélection d’un attribut à chaque nœud, éventuellement un critère de coupe [2,3] si l’attribut est quantitatif et le critère d’élagage de certains nœuds.
Pour traiter les données quantitatives continues, il est nécessaire, pour cette structure, de discrétiser ces données via le critère de coupe. Pour l’arbre de décision, cette discrétisation se déroule généralement pendant la construction de l’arbre.
Description du sujet :
Ils existent différents algorithmes de construction d’arbres de décision se différenciant selon les différents critères cités précédemment. Le premier objectif de ce stage sera d’implémenter les algorithmes connus ID3 et C4.5.
Le deuxième objectif sera de faire une étude des différents critères de coupe pour la discrétisation et l’implémentation de ceux-ci.
Pré requis et contraintes particulières :
Langages : Java
Références bibliographiques :
[1] R. Rakotomala. Arbres de décision, Tutoriel – Revue MODULAD n°33.
http://eric.univ-lyon2.fr/ ricco/doc/tutoriel_arbre_revue_modulad_33.pdf
[2] S. Kotsiantis D. Kanellopoulos. Discretization Techniques : A recent survey. GESTS International Transactions on Computer Science and Engineering, Vol.32, 2006, pp. 47-58
[3] R. Rakotomala, Graphes d’induction, Thèse de doctorat, Université de Lyon I, 1997 (chapitre 9)
Contacts – liens :
Email : nathalie.girard univ-lr.fr; karell.bertet univ-lr.fr