Les automates d’arbres

CONTRIBUTION 1. AUTOMATES D’ARBRES POUR LA CLASSIFICATION

Introduction du chapitre

Ce chapitre est consacré à la présentation détaillée de notre première contribution et qui consiste à utiliser les automates d’arbres décrits dans le chapitre précédent pour la génération d’arbres (Taleb et al., 2008a) (Taleb et al., 2008b) ou de graphes (Taleb et al., 2008c). Les étapes de transformation sont décrites en se basant sur deux exemples ; un extrait de l’application MONITDIAB présentée au niveau du chapitre 6 et l’exemple Retard (Bramer, 2007).

Le but de cette transformation est d’atteindre trois objectifs principaux : le premier consiste à mettre ces méthodes dans un cadre formel de représentation, le second permet d’utiliser les propriétés des automates pour la simplification des modèles générés (Taleb et al., 2013) ce qui nous permet d’éviter le recours à un échantillon supplémentaire pour la simplification qui pose souvent problème à cause de l’indisponibilité des données. Le troisième et dernier objectif consiste à utiliser les règles de réécriture pour la génération des règles de décision dont l’extraction se faisait dans les structures arbres ou graphes par un parcours de noeuds de la racine vers les feuilles. De cette contribution résulte une réduction du temps de génération de façon considérable (Taleb et al., 2012) comme nous allons le montrer dans le chapitre 7 (expérimentation).

Nous présentons d’abord les étapes de transcodage ou de transcription d’un arbre de décision dans le formalisme d’automates d’arbres, suit une description du procédé utilisé pour la génération des règles de décision qui repose sur la technique de réécriture propre aux automates. Les algorithmes de simplification reposant sur les propriétés de nettoyage de déterminisation sont ensuite donnés et illustrés sur deux exemples avant de conclure ce chapitre.

Transcodage d’un arbre de décision dans le formalisme d’automates d’arbres

Nous avons proposé et implémenté deux méthodes de transcodage d’arbres de décision dans le formalisme d’automates d’arbres (Taleb et al., 2008a), et nous avons pu démontrer que les deux méthodes sont équivalentes mais l’une d’elles est plus optimale en terme de nombre d’états, et de règles de transition. Dans ce qui suit nous utilisons la méthode de transcodage la plus optimale.

Pour illustrer les étapes de transformation, on considère deux exemples, l’extrait de l’application de surveillance de diabétiques MONITDIAB (chapitre 1 $ 4.5) et l’exemple Retard (Bramer, 2007).

L’opération de base de construction d’un arbre de décision est l’éclatement, la construction de l’automate se fait de façon descendante (Up-Bottom). Pour illustrer de façon claire et détaillée l’approche adoptée, on divise les éclatements en un premier qui représente l’éclatement du noeud racine et un second qui correspond à l’éclatement d’un noeud intermédiaire.

Illustration 1, extrait de l’application MONITDIAB

On considère l’extrait de l’application MONIDIAB présentée en détails au niveau du chapitre 6, l’extrait est composé de 20 instances (patients), 13 variables exogènes et 3 valeurs de classes.

Illustration 2, exemple Retard (Bramer, 2007)

L’exemple est composé de 20 instances décrites par 4 variables exogènes : Jour, Saison,Vent, et Pluie. Les valeurs de classe sont : à Temps (T), en Retard (R), Très en Retard (TR), ne Vient Pas (VP).

Les variables exogènes prennent les valeurs suivantes :
– Jour : {Jour de Semaine (JS), Samedi (S), Dimanche (D), Vacances (V)} ;
– Saison : {Printemps (P), Hiver (H), Automne (A), Eté (E)} ;
– Vent : {Pas de Vent (PV), Elevé (EL), Normal (N)} ;
– Pluie : {Pas de Pluie (PP), Légère (L), Forte (F)}

Extraction des règles de décision

L’extraction des règles de décision ne se fait plus par un parcours de l’arbre de décision mais par l’utilisation de règles de réécriture, ce qui constitue un premier apport de cette contribution, illustrons les règles de réécriture détaillée dans (Taleb et al., 2008c) pour la génération des règles de décision de l’arbre C4.5. A partir de l’arbre C4.5 (Figure 3.6), on peut extraire 4 règles de décision générées en parcourant l’arbre de la racine jusqu’aux feuilles :

Utilisation des propriétés des automates d’arbres pour la simplification des modèles générés

Nous proposons d’utiliser deux propriétés des automates d’arbres pour la simplification des modèles générés. Un automate émondé ne contient que des états utiles ; qui mènent vers un état final (chapitre 2, § 3.10) et un automate déterministe ne contient pas parmi ses règles de transition deux règles avec mêmes sources et qui transitent vers des états différents (chapitre 2, § 3.9).

Nous présentons dans la section suivante deux algorithmes, un pour le nettoyage et l’autre pour la déterminisation de l’automate d’arbres (Taleb et al., 2013). Le premier algorithme permet d’éliminer les états inutiles et par conséquent réduit la taille de l’automate (nombre de règles de transition et d’états) ainsi que la taille de la base de règles. Le deuxième algorithme permet essentiellement de réduire la taille de l’automate.

Déterminisation de l’automate

Il existe un algorithme permettant de déterminer un automate initialement non déterministe (Comon et al., 2008), l’algorithme conçu initialement pour les automates de séquences est généralisé pour les automates d’arbres. Son principe consiste à utiliser une construction de sous ensembles d’états, sa complexité augmente en fonction du nombre d’états.
L’algorithme de déterminisation que nous proposons (Taleb et al., 2013) est moins complexe que le précédent en terme de temps d’exécution, il est décrit par l’algorithme suivant.
L’algorithme est essentiellement composé de deux boucles principales ; ces dernières permettent de parcourir l’ensemble des règles de transition en testant s’il y a des règles qui causent le non déterminisme. Le non déterminisme est essentiellement causé par les symboles d’arité 0 (modalités des variables exogènes).

Nettoyage de l’automate

Le nettoyage consiste à éliminer les états inutiles de l’automate ; un état inutile est un état qui n’est pas relié à un état final donc ne participe pas à une décision. Ce nettoyage a pour conséquences la réduction de la taille de l’automate ainsi que la taille de la base de règles avec une amélioration des performances en prédiction. Nous présentons l’algorithme permettant de nettoyer un automate déterministe en entrée :

Conclusion du chapitre

Dans ce chapitre nous avons présenté la première contribution de cette thèse qui concerne l’utilisation des automates d’arbres pour la génération et la simplification d’arbres de décision (Taleb et al., 2013). Nous avons donné en détails trois algorithmes : le premier décrit le processus de réécriture pour la génération de règles de décision, le second est dédié à la déterminisation d’un automate, enfin un troisième algorithme décrit le nettoyage. Les deux derniers algorithmes permettent de réduire le nombre d’états et de règles de transition de l’automate et parfois même la taille de la base de règles de décision.
L’utilisation des automates d’arbres pour la génération de modèles de classification à base d’arbres de décision nous a permis de simplifier les modèles sans avoir recours à un échantillon pour le pruning comme c’est le cas des méthodes usuelles d’élagage d’arbres, l’échantillon de pruning n’étant généralement pas disponible. De plus, l’utilisation du procédé de réécriture pour la génération des règles de décision à partir de l’automate permet de réduire le temps de génération qui se faisait sur des structures complexes d’arbres ou de graphes avec un parcourt racine-feuille.

Les apports de la contribution sont montrés au chapitre 7 avec des études expérimentales sur l’application MONITDIAB et des benchmarks de l’UCI Repository (Asuncion et al., 2007).

Etat de l’art, méthodes d’ensemble

Plusieurs méthodes d’ensemble d’arbres de décision ont vu le jour, elles ont été appliquées avec succès à diverses applications, les premiers travaux abordant des problèmes liés à la synthèse des résultats d’arbres multiples (Shlien, 1990) (Shlien, 1992) démontre qu’une grande amélioration de la précision peut être obtenue en utilisant le même échantillon d’apprentissage pour générer une combinaison d’arbres de décision binaires (générées par des critères de sélection de variables différents) et les combinant en utilisant le modèle de Dempster et Shafer (Buchanan, 1984) (Bogler, 1987), Shlien (1992) applique son approche dans le domaine de reconnaissance de caractères.
(Kwok et al., 1990) proposent la génération d’arbres multiples en changeant les paramètres d’apprentissage, la génération de comités d’arbres de décision par une sélection stochastique d’attributs a été proposée dans (Dietterich et al., 1995) (Ali, 1996) (Zheng et al., 1998).

Tin Kam Ho propose dans (Ho, 1994) (Ho, 1995) (Ho, 1998) de créer un ensemble d’apprentissage composé d’un ensemble d’arbres de décision « decision forest » construits de façon systématique en sélectionnant pseudo aléatoirement des composants du vecteur des variables, de cette façon les arbres sont construits dans des sous espaces choisit aléatoirement.
Le tirage aléatoire de variables pour découper un noeud avait aussi été utilisé par (Amit et al., 1997) dans des problèmes de reconnaissance d’image pour les random feature selection ou random trees. Pour leur problème, les auteurs introduisent une perturbation non pas au niveau de l’échantillon d’apprentissage, mais directement dans le choix des partitions internes, eninstaurant à chaque noeud une présélection aléatoire préalable au choix de la partition optimale. Freund et Schapire (Freund et al., 1995) introduisent un nouvel algorithme de boosting appelé « Adaboost » qui, théoriquement, est capable de réduire significativement l’erreur d’un algorithme engendrée par un classifieur qui possède une performance pas significative par rapport à un classifieur construit de façon aléatoire, ils introduisent aussi la notion de« pseudo-perte » qui force un algorithme d’apprentissage à se concentrer sur les étiquettes les plus difficiles à discriminer.

Table des matières

INTRODUCTION GENERALE
CHAPITRE 1 : EXTRACTION DE CONNAISSANCES A PARTIR DE DONNEES
1 Introduction du chapitre
2 Généralités ECD
2.1 Processus ECD
3 Apprentissage automatique
3.1 Les méthodes de l’apprentissage automatique
3.1.1 Méthodes d’Apprentissage Empirique
3.1.1.1 Apprentissage par analogie
3.1.1.2 Apprentissage par induction
3.1.2 Méthodes d’Apprentissage par Explication
3.2 Apprentissage supervisé
3.3 Apprentissage non-supervisé
3.4 Les approches de l’apprentissage automatique
3.4.1 Apprentissage numérique
3.4.2 Apprentissage symbolique
3.5 Fouille de données (Datamining)
3.6 Principales méthodes de classification
3.6.1 Analyse factorielle discriminante
3.6.2 Méthodes du noyau et plus proches voisins
3.6.3 Les réseaux de neurones
3.6.4 Les arbres de décision
4 Méthodes de classification à base d’arbres
4.1 Arbres de décision, historique
4.2 Stratégies de construction d’arbres de décision
4.3 Schéma TDIDT
CHAPITRE 2 : LES AUTOMATES D’ARBRES
1 Introduction du chapitre
2 Automates pour les séquences
3 Automates pour les arbres
3.1 Automates d’arbres pour la
manipulation de documents XML
3.2 Automates d’arbres pour la sécurité informatique
3.3 Automates d’arbres & apprentissage
3.4 Applications des automates d’arbres
3.5 Quelques définitions sur les arbres
3.6 Automates d’arbres finis, définition
4.4 Qualité d’une partition
4.4.1 Critères de partition
4.4.1.1 Théorie de l’information
4.4.1.2 Distances entre distributions de probabilités
4.5 Algorithmes ID3 & C4.5
4.5.1 La méthode ID3
4.5.2 La méthode C4.5
4.6 Taille d’un arbre de décision
4.6.1 Pré-élagage
4.6.2 Post-élagage
4.6.2.1 Minimal Cost Complexity Pruning
4.6.2.2 Reduced Error Pruning
4.6.2.3 Pessimistic Error Pruning
4.6.2.4 Error Based Pruning
4.6.3 Simplification des arbres de décision
4.7 Inconvénients des méthodes de segmentation par arbres
5 Conclusion du chapitre
3.7 Types d’automates d’arbres
3.7.1 Les automates d’arbres finis ascendants
3.7.2 Les automates d’arbres finis descendants
3.8 Automates d’arbres avec règles-ε
3.9 Automates d’arbres déterministes
3.9.1 Déterminisation d’un automate d’arbres
3.10 Réduction des automates d’arbres
3.11 Minimisation des automates
3.11.1 Méthodes de simplification d’automates
3.11.1.1 Equivalence de Nerode
3.11.1.2 Algorithme de Hopcroft
4 Conclusion du chapitre
CHAPITRE 3 : CONTRIBUTION 1 : AUTOMATES D’ARBRES POUR LA CLASSIFICATION.
1 Introduction du chapitre
2 Transcodage d’un arbre de décision dans le formalisme d’automates d’arbres
2.1 Illustration 1, extrait application MONITDIAB
2.1.1 Eclatement du noeud racine
2.1.2 Eclatement d’un noeud intermédiaire
2.2 Illustration 2, exemple Retard
3 Extraction des règles de décision
4 Utilisation des propriétés des automates d’arbres pour la simplification des modèles générés
4.1 Déterminisation de l’automate
4.2 Nettoyage de l’automate
4.3 Déroulement des algorithmes
4.3.1 Déroulement exemple 1
4.3.2 Déroulement exemple 2
5 Conclusion du chapitre
CHAPITRE 4 : METHODES D’ENSEMBLES ET SIMPLIFICATION D’ENSEMBLES
1 Introduction du chapitre
2 Etat de l’art, méthodes d’ensemble
3 Agrégation de modèles
3.1 Techniques de diversification
3.1.1 Diversification par rééchantillonnage
3.1.1.1 Bagging
3.1.1.2 Boosting
3.1.1.3 Randomizing outputs
3.1.1.4 Random subspace
3.1.2 Diversification par Hybridation
3.1.2.1 Stacking
3.1.2.2 Méthodes multi-stratégies
4 Pruning d’ensemble
4.1 Pourquoi le pruning d’ensemble ?
4.2 Méthodes de pruning d’ensembles
4.2.1 Pruning d’ensemble, état de l’art
4.2.2 Méthodes Hill Climbing
4.2.2.1 Direction de recherche
4.2.2.2 Fonction d’évaluation
4.2.2.3 Ensemble de validation
5 Conclusion du chapitre
CHAPITRE 5 : FONCTION MULTI OBJECTIFS ET MESURE DE SEGMENTATION POUR LA SELECTION
1 Introduction du chapitre
2 Mesure de segmentation pour la sélection des variables
2.1 Motivations
2.2 Principe de la mesure NIM
2.3 Présentation détaillée de la mesure
2.4 Critiques des méthodes arborescentes
2.4.1 Insensibilité à l’effectif
2.4.2 Non décroissance du critère
2.4.3 Préférence à la complexité
2.5 Etapes de génération d’un arbre
2.6 Génération d’un arbre sur l’application de surveillance des diabétiques
3 Fonction multi objectifs pour la sélection d’ensembles
3.1 Motivations
3.2 Contribution
3.3 Présentation détaillée de la fonction multi objectifs
3.3.1 Normalisation des composantes C et E de S
3.3.2 Algorithme de simplification
3.3.3 Initialisation et parcours
4 Conclusion du chapitre
CHAPITRE 7 : EXPERIMENTATIONS
1 Introduction du chapitre
2 Description des bases d’apprentissage
3 Environnements de développement
3.1 Présentation de la plate forme Weka
3.1.1 Structure de données
3.1.2 Outils de programmation
3.2 Plate forme méthodes d’ensembles
4 Architecture générale
5 Automates d’arbres pour la classification
5.1 Démarche des expérimentations
5.2 Etudes comparatives et résultats
5.2.1 Première étude comparative
5.2.2 Deuxième étude comparative
5.2.3 Troisième étude comparative
5.3 Analyse des résultats des résultats
CHAPITRE 6 : PRESENTATION DU DOMAINE D’APPLICATION : SURVEILLANCE DES DIABETIQUES
1 Introduction du chapitre
2 Le diabète
2.1 Types du diabète
2.1.1 Diabète Type 1
2.1.2 Diabète Type 2
3 Complications du diabète : qu’est-ce que c’est?
4 La surveillance du Diabète
5 Le diabète & l’informatique
6 Contribution, élaboration du modèle de classification
6.1 Les variables exogènes
6.2 Les valeurs de la classe
7 Conclusion du chapitre
6 Mesure de segmentation pour la sélection de variables
6.1 Démarche des expérimentations
6.2 Etudes comparatives et résultats
6.2.1 Première étude comparative
6.2.1.1 Analyse des résultats de la première étude comparative
6.2.2 Deuxième étude comparative
6.2.2.1 Analyse des résultats de la deuxième étude comparative
7 Fonction multi objectifs pour la sélection d’ensembles
7.1 Etudes comparatives
7.2 Démarche des expérimentations
7.2.1 Comparaison des taux de succès
7.2.2 Comparaison des tailles des sous ensembles
8 Conclusion du chapitre
CONCLUSION GENERALE
BIBLIOGRAPHIE
ANNEXE A
ANNEXE B

Télécharger le rapport complet