Une amélioration : C 4.5

"""
   écrit par poupou9779 pour Zeste de Savoir
"""

from math import log
from operator import itemgetter

class Exemple:
   """
       Un exemple contient 2 valeurs :
           - un dictionnaire d'attributs (dict)
           - une étiquette (str)
   """

   def __init__(self, noms_attributs, valeurs_attributs, etiquette=""):
       """
           etiquette peut être non précisée en quel cas on aurait
           un exemple non étiqueté
       """
       #si on a un problème de types
       if not isinstance(noms_attributs, list) \
       or not isinstance(valeurs_attributs, list):
           raise TypeError("noms_attributs et valeurs_attributs doivent être" \
                           " des listes et pas des {0} et {1}" \
                           .format(type(noms_attributs),
                                   type(valeurs_attributs)))
       if not isinstance(etiquette, str):
           raise TypeError("etiquette doit être un str et pas un {}" \
                           .format(type(etiquette)))
       #si les deux listes n'ont pas le même nombre d'éléments
       if len(valeurs_attributs) != len(noms_attributs):
           raise ValueError("noms_attributs et valeurs_attributs doivent " \
                            "avoir le même nombre d'éléments")
       self.etiquette = etiquette
       self.dict_attributs = dict()
       #on ajoute chaque attribut au dictionnaire
       for i in range(len(noms_attributs)):
           self.dict_attributs[noms_attributs[i]] = valeurs_attributs[i]

class Ensemble:
   """
       Un ensemble contient deux valeurs :
           - les noms des attributs (list)
           - les exemples (list)
   """

   def __init__(self, chemin=""):
       """
           chemin est l'emplacement du fichier contenant les données.
           Cette variable peut être non précisée en quel cas les variables
               seront initialisées comme des listes vides.
       """
       #Python est un langage à typage dynamique fort,
       #il faut donc vérifier que l'utilisateur ne fait pas n'importe quoi
       #en passant autre chose qu'un str
       if not isinstance(chemin, str):
           raise TypeError("chemin doit être un str et non {}" \
                           .format(type(chemin)))
       if chemin == "":
           #initialisation en listes vides
           self.liste_attributs = list()
           self.liste_exemples = list()
       else:
           with open(chemin, 'r') as fichier:
               #on stocke chaque mot de la première ligne dans liste_attributs
               self.liste_attributs = \
                               fichier.readline().lower().strip().split(' ')
               #ensuite on stocke la liste d'exemples dans liste_exemples
               self.liste_exemples = self.liste_en_exemples(
                                       fichier.read().strip().lower().split('\n'),
                                       self.liste_attributs
                                     )

   def __len__(self):
       """
           retourne la longueur de l'ensemble
       """
       return len(self.liste_exemples)

   @staticmethod
   def liste_en_exemples(exemples, noms_attributs):
       """
           retourne une liste d'exemples sur base d'une liste de str contenant
           les valeurs et d'une liste de str contenant les noms des attributs
       """
       #on initialise la liste à retourner
       ret = list()
       for ligne in exemples:
           #on stocke chaque mot de la ligne dans une liste attributs
           attributs = ligne.lower().strip().split(' ')
           #met l'étiquette par défaut si elle n'est pas dans la ligne
           etiquette = attributs[-1] if len(attributs) != len(noms_attributs) \
                                     else ""
           #on ajoute un objet de type Exemple contenant la ligne
           ret.append(Exemple(noms_attributs,
                              attributs[:len(noms_attributs)],
                              etiquette))
       return ret

   def etiquettes_possibles(self):
       """
           retourne une liste contenant les étiquettes de l'ensemble
       """
       #on initialise la valeur de retour
       ret = list()
       #pour chaque exemple de l'ensemble
       for exemple in self.liste_exemples:
           #si l'étiquette n'est pas déjà dans la liste
           if not exemple.etiquette in ret:
               #on l'ajoute
               ret.append(exemple.etiquette)
       return ret

   def sous_ensemble_etiquette(self, etiquette):
       """
           retourne un ensemble contenant uniquement les exemples ayant
           etiquette comme étiquette
       """
       #initialisation de la valeur de retour
       ret = Ensemble()
       #on copie la liste d'attributs
       ret.liste_attributs = self.liste_attributs[:]
       #pour chaque exemple de l'ensemble initial
       for exemple in self.liste_exemples:
           #si l'étiquette est bonne
           if exemple.etiquette == etiquette:
               #on l'ajoute au sous-ensemble
               ret.liste_exemples.append(exemple)
       return ret

   def sous_ensemble_attribut(self, nom_attribut, valeur):
       """
           retourne un sous-ensemble contenant uniquement les exemples ayant
           la bonne valeur pour l'attribut
       """
       ret = Ensemble()
       #on prend tous les attributs sauf celui passé en paramètre
       ret.liste_attributs = self.liste_attributs[:]
       ret.liste_attributs.remove(nom_attribut)
       #pour chaque exemple de l'ensemble
       for exemple in self.liste_exemples:
           #s'il a la bonne valeur
           if exemple.dict_attributs[nom_attribut] == valeur:
               #on l'ajoute
               ret.liste_exemples.append(exemple)
       #et on retourne la liste
       return ret

   def entropie(self):
       """
           retourne l'entropie de Shannon de l'ensemble
       """
       #initialisation de la variable retournée
       ret = 0
       #pour chaque étiquette de l'ensemble
       for etiquette in self.etiquettes_possibles():
           #on crée un sous-ensemble qui ne contient que les éléments de
           #self ayant etiquette comme étiquette
           sous_ensemble = self.sous_ensemble_etiquette(etiquette)
           #on ajoute |c| * log_2(|c|) à ret
           longueur_sous_ensemble = len(sous_ensemble)
           ret += longueur_sous_ensemble * log(longueur_sous_ensemble, 2)
       #on retourne log_2(|S|) - ret/|S|
       return log(len(self), 2) - ret/len(self)

   def attribut_optimal(self, ID3=True):
       """
           retourne un str avec le nom de l'attribut à tester
       """
       max, ret = float("-inf"), ""
       #pour chaque attribut
       for attribut in self.liste_attributs:
           if ID3:
               gain = self.gain_entropie(attribut)
           else:
               gain = self.ratio_gain(attribut)
           #si le gain d'entropie est le plus grande
           if gain >= max:
               #on le garde en mémoire
               max, ret = gain, attribut
       #et on le retourne
       return ret

   def valeurs_possibles_attribut(self, nom_attribut):
       """
           retourne une liste contenant toutes les
           valeurs possibles de l'attribut
       """
       ret = list()
       #pour chaque exemple
       for exemple in self.liste_exemples:
           #si cette valeur n'est pas encore dans la liste
           if not exemple.dict_attributs[nom_attribut] in ret:
               #on l'ajoute
               ret.append(exemple.dict_attributs[nom_attribut])
       #et on retourne la liste
       return ret

   def gain_entropie(self, nom_attribut):
       """
           retourne la perte d'entropie selon la définition de Ross Quinlan
       """
       somme = 0
       #pour chaque valeur de l'attribut en question
       for valeur in self.valeurs_possibles_attribut(nom_attribut):
           #déclaration de Sv
           sous_ensemble = self.sous_ensemble_attribut(nom_attribut, valeur)
           #somme = somme sur v de |Sv| * Entropie(Sv)
           somme += len(sous_ensemble) * sous_ensemble.entropie()
       #Gain(S, A) = Entropie(S) - 1/|S| * somme
       return self.entropie() - somme/len(self)

   def ratio_gain(self, nom_attribut):
       """
           retourne le ratio de gain (C4.5) de l'ensemble
       """
       split = self.split_entropie(nom_attribut)
       gain = self.gain_entropie(nom_attribut)
       return gain/split if split != 0 else float("inf")

   def split_entropie(self, nom_attribut):
       """
           retourne le split d'entropie du set selon l'attribut en question
       """
       ret = 0
       for valeur in self.valeurs_possibles_attribut(nom_attribut):
           sous_ensemble = self.sous_ensemble_attribut(nom_attribut, valeur)
           ret += len(sous_ensemble) * log(len(sous_ensemble), 2)
       return log(len(self), 2) - ret/len(self)

   def est_discretisable(self, nom_attribut):
       """
           renvoie True si l'attribut en question est un attribut continu
       """
       #pour chaque exemple
       for exemple in self.liste_exemples:
           #si la valeur de l'attribut n'est pas un nombre
           try:
               float(exemple.dict_attributs[nom_attribut])
           #alors l'attribut n'est pas discrétisable
           except ValueError:
               return False
       #si tous les exemples sont discrétisables pour cet attribut,
       #l'attribut est  discrétisable
       return True

   def sauvegarder_valeurs_discretes(self):
       """
           renvoie une liste de tuples contenant :
               + le nom de l'attribut
               + la liste de toutes les valeurs de cet attribut
       """
       ret = list()
       #pour chaque attribut
       for attribut in self.liste_attributs:
           #s'il est discrétisable
           if self.est_discretisable(attribut):
               #on sauvegarde les valeurs de chaque exemple
               valeurs_attribut = [exemple.dict_attributs[attribut] \
                                   for exemple in self.liste_exemples]
               ret.append((attribut, valeurs_attribut))
       return ret

   def discretiser(self, nom_attribut):
       """
           remplace chaque valeur de l'attribut en question par l'ensemble
           auquel il appartient
       """
       #liste_intervalles va contenir la liste des intervalles résultant
       #de la discrétisation
       liste_intervalles = list()
       #valeurs_triees est initialisée avec les valeurs de
       #l'attribut de chaque exemple
       valeurs_triees = \
               [(i, self.liste_exemples[i].dict_attributs[nom_attribut]) \
                               for i in range(len(self))]
       #et ensuite est triée selon ces valeurs
       valeurs_triees.sort(key=itemgetter(1))
       indice_borne_inf = 0
       #on parcourt la liste triée
       for i in range(1, len(valeurs_triees)):
           #s'il y a un changement d'étiquette
           if self.liste_exemples[valeurs_triees[i][0]].etiquette !=  \
           self.liste_exemples[valeurs_triees[indice_borne_inf][0]].etiquette:
               #les bornes (inf et sup) sont une moyenne de
               #l'élément courant et du précédent
               #ATTENTION : le premier intervalle commence à -8 car il faut
               #pouvoir gérer toutes les valeurs
               if len(liste_intervalles) == 0:
                   borne_inf = float("-inf")
               else:
                   borne_inf = (float(valeurs_triees[indice_borne_inf][1]) + \
                                float(valeurs_triees[indice_borne_inf-1][1]))/2
               borne_sup = (float(valeurs_triees[i][1]) + \
                            float(valeurs_triees[i-1][1])) / 2
               #une fois les bornes trouvées, on ajoute l'intervalle à la liste
               liste_intervalles.append((borne_inf, borne_sup))
               indice_borne_inf = i
       #il ne faut pas oublier le dernier intervalle qui va jusqu'à +8 !
       liste_intervalles.append((liste_intervalles[-1][1], float("+inf")))

       #pour chaque exemple
       for exemple in self.liste_exemples:
           for intervalle in liste_intervalles:
               #on trouve le bon intervalle
               if float(exemple.dict_attributs[nom_attribut]) < intervalle[1]:
                   #en on discrétise
                   exemple.dict_attributs[nom_attribut] = intervalle
                   break

   def valeur_plus_frequente_attribut(self, nom_attribut):
       """
           renvoie un str avec la valeur la plus fréquente de
           l'attribut en question dans l'ensemble
       """
       dict_frequences = dict()
       #pour chaque exemple de l'ensemble
       for exemple in self.liste_exemples:
           #on regarde quelle est sa valeur pour l'attribut en question
           #si elle n'a pas encore été rencontrée
           if exemple.dict_attributs[nom_attribut] not in dict_frequences:
               #on l'ajoute au dictionnaire
               dict_frequences[exemple.dict_attributs[nom_attribut]] = 0
           dict_frequences[exemple.dict_attributs[nom_attribut]] += 1
       #on retourne la clef pour laquelle la valeur est la plus élevée
       return max(dict_frequences, key=dict_frequences.get)

   def restaurer_valeurs_manquantes(self):
       """
           change chaque '?' dans les attributs, le remplacer par
           la valeur de l'attribut la plus fréquente dans le set
           (pour les exemples ayant la même étiquette)
       """
       #pour chaque exemple
       for i in range(len(self.liste_exemples)):
           #on check chaque chaque attribut
           for nom_attribut in self.liste_exemples[i].dict_attributs:
               #si l'attribut en question vaut '?'
               if self.liste_exemples[i].dict_attributs[nom_attribut] == '?':
                   #on isole les éléments ayant la même étiquette
                   sous_ensemble = self.sous_ensemble_etiquette(
                                       self.liste_exemples[i].etiquette)
                   #et on récupère la valeur de ce même attribut la plus
                   #fréquente pour l'assigner à la place du '?'
                   self.liste_exemples[i].dict_attributs[nom_attribut] = \
                     sous_ensemble.valeur_plus_frequente_attribut(nom_attribut)

class Feuille:
   """
       Une feuille contient uniquement une valeur:
           - l'étiquette (str)
   """

   def __init__(self, etiquette):
       """
           etiquette doit obligatoirement être un str
       """
       if not isinstance(etiquette, str):
           raise TypeError("etiquette doit être un str et pas un {}" \
                           .format(type(etiquette)))
       self.etiquette = etiquette

class Noeud:
   """
       Un noeud a deux valeurs :
           - un dictionnaire d'enfants (dict)
           - l'attribut testé (str)
   """

   def __init__(self, attribut):
       """
           attribut_teste est le nom de l'attribut stocké dans un str
       """
       if not isinstance(attribut, str):
           raise TypeError("attribute_teste doit être un str et pas un {}" \
                           .format(type(attribut)))
       #initialisation des valeurs de l'objet
       self.enfants = dict()
       self.attribut_teste = attribut

class Arbre_ID3:
   """
       Un arbre ID3 contient deux valeurs :
           - un ensemble d'exemples (Ensemble)
           - un arbre (Noeud)
   """

   def __init__(self, chemin=""):
       """
           chemin est l'emplacement du fichier contenant les données
       """
       #initialisation de l'ensemble avec le fichier dans chemin
       self.ensemble = Ensemble(chemin)
       #initialisation du noeud principal de l'arbre
       self.arbre = None

   def construire(self):
       """
           génère l'arbre sur base de l'ensemble pré-chargé
       """
       self.arbre = self.__construire_arbre(self.ensemble)

   def __construire_arbre(self, ensemble):
       """
           fonction privée et récursive pour a génération de l'arbre
       """
       if not isinstance(ensemble, Ensemble):
           raise TypeError("ensemble doit être un Ensemble et non un {}" \
                           .format(type(ensemble)))
       #si la liste est vide
       if len(ensemble) == 0:
           raise ValueError("la liste d'exemples ne peut être vide !")
       #testons si tous les exemples ont la même étiquette
       if ensemble.entropie() == 0:
           #on retourne l'étiquette en question
           return Feuille(ensemble.liste_exemples[0].etiquette)
       #s'il ne reste d'attribut à tester
       if len(ensemble.liste_attributs) == 0:
           max, etiquette_finale = 0, ""
           #on teste toutes les étiquettes possibles de l'ensemble
           for etiquette in ensemble.etiquettes_possibles():
               sous_ensemble = ensemble.sous_ensemble_etiquette(etiquette)
               #si c'est la plus fréquente, c'est celle qu'on choisit
               if len(sous_ensemble) > max:
                   max, etiquette_finale = len(sous_ensemble), etiquette
           #et on la retourne dans une feuille
           return Feuille(etiquette_finale)

       a_tester = ensemble.attribut_optimal()
       #si on arrive ici, on retourne d'office un nœud et pas une feuille
       noeud = Noeud(a_tester)
       #pour chaque valeur que peut prendre l'attribut à tester
       for valeur in ensemble.valeurs_possibles_attribut(a_tester):
           #on crée un sous-ensemble
           sous_ensemble = ensemble.sous_ensemble_attribut(a_tester, valeur)
           #et on en crée un nouveau nœud
           noeud.enfants[valeur] = self.__construire_arbre(sous_ensemble)
       #on retourne le nœud que l'on vient de créer
       return noeud

   def afficher(self):
       """
           affiche l'entièreté de l'arbre à l'écran
       """
       self.__afficher_arbre(self.arbre)

   def __afficher_arbre(self, noeud, nb_tabs=0):
       """
           selon la convention :
               <texte> <-> nom de l'attribut
               -<texte> <-> valeur de l'attribut
               .<texte> <-> feuille
       """
       #si on a affaire à un nœud
       if isinstance(noeud, Noeud):
           #on affiche le nom de l'attribut testé
           print('\t' * nb_tabs + noeud.attribut_teste)
           #on parcourt ses enfants
           for enfant in noeud.enfants:
               #on affiche la valeur de l'attribut
               print('\t' * nb_tabs + '-' + str(enfant))
               self.__afficher_arbre(noeud.enfants[enfant], nb_tabs+1)
       #si c'est une feuille
       elif isinstance(noeud, Feuille):
           #on affiche l'étiquette
           print('\t' * nb_tabs + '.' + noeud.etiquette)
       else:
           raise TypeError("noeud doit être un Noeud/Feuille et pas un {}" \
                           .format(type(noeud)))

   def etiqueter(self, exemple):
       """
           assigne la bonne étiquette à l'exemple passé en paramètre
       """
       #on initialise le nœud actuel avec le haut de l'arbre
       noeud_actuel = self.arbre
       #tant que l'on est sur un nœud et pas sur une feuille,
       #on continue d'explorer
       while not isinstance(noeud_actuel, Feuille):
           #pour savoir quel est le prochain nœud, on récupère d'abord
           #l'attribut testé avec noeud_actuel.attribut_teste puis on récupère
           #la valeur de l'exemple pour cet attribut avec
           #exemple.dict_attributs[noeud_actuel.attribut_teste]
           #puis on prend l'enfant de noeud_actuel ayant cette valeur.
           valeur = exemple.dict_attributs[noeud_actuel.attribut_teste]
           noeud_actuel = noeud_actuel.enfants[valeur]
       #on finit en donnant comme étiquette l'étiquette
       #contenue dans la feuille finale
       exemple.etiquette = noeud_actuel.etiquette

class Arbre_C45(Arbre_ID3):
   """
       Un arbre C4.5 hérite d'un arbre ID3 mais se construit différemment
   """

   def __init__(self, chemin_données="", chemin_elagage=""):
       """
           chemin_données est l'emplacement du fichier contenant les données
           chemin_elagage est l'emplacement d'un autre set permettant
           d'élaguer l'arbre
       """
       #initialisation de l'ensemble avec le fichier dans chemin_données
       self.ensemble = Ensemble(chemin_données)
       #initialisation du nœud principal de l'arbre
       self.arbre = None
       self.chemin_elagage = chemin_elagage

   def construire(self):
       """
           retourne l'arbre au complet
       """
       #si le set est corrompu (attributs manquants), on le restaure
       self.ensemble.restaurer_valeurs_manquantes()
       self.arbre = self.__construire_arbre(self.ensemble)

   def __construire_arbre(self, ensemble):
       if not isinstance(ensemble, Ensemble):
           raise TypeError("ensemble doit être un Ensemble et non un {}" \
                           .format(type(ensemble)))
       #si la liste est vide
       if len(ensemble) == 0:
           raise ValueError("la liste d'exemples ne peut être vide !")
       #testons si tous les exemples ont la même étiquette
       if ensemble.entropie() == 0:
           #on retourne l'étiquette en question
           return Feuille(ensemble.liste_exemples[0].etiquette)
       #s'il ne reste d'attribut à tester 
       if len(ensemble.liste_attributs) == 0:
           max, etiquette_finale = 0, ""
           #on teste toutes les étiquettes possibles de l'ensemble
           for etiquette in ensemble.etiquettes_possibles():
               sous_ensemble = ensemble.sous_ensemble_etiquette(etiquette)
               #si c'est la plus fréquente, c'est celle qu'on choisit
               if len(sous_ensemble) > max:
                   max, etiquette_finale = len(sous_ensemble), etiquette
           #et on la retourne dans une feuille
           return Feuille(etiquette_finale)

       #ne pas oublier de sauver les valeurs pour pouvoir les restituer au cas
       #où l'attribut discrétisé n'est pas choisi
       sauvegarde_valeurs = ensemble.sauvegarder_valeurs_discretes()
       #pour chaque valeur à discrétiser
       for attribut, valeurs in sauvegarde_valeurs:
           #on discrétise
           ensemble.discretiser(attribut)
       #on récupère l'attribut optimal
       #ATTENTION : préciser ID3=False pour utiliser le ratio de gain
       a_tester = ensemble.attribut_optimal(ID3=False)
       #pour chaque attribut sauvegardé
       for attribut, valeurs in sauvegarde_valeurs:
           #si ce n'est pas l'attribut choisi
           if attribut != a_tester:
               #on remet les anciennes valeurs continues
               for i in range(len(valeurs)):
                   ensemble.liste_exemples[i].dict_attributs[attribut] = \
                                                                   valeurs[i]
       #si on arrive ici, on retourne d'office un nœud et pas une feuille
       noeud = Noeud(a_tester)
       #pour chaque valeur que peut prendre l'attribut à tester
       for valeur in ensemble.valeurs_possibles_attribut(a_tester):
           #on crée un sous-ensemble
           sous_ensemble = ensemble.sous_ensemble_attribut(a_tester, valeur)
           #et on en crée un nouveau nœud
           noeud.enfants[valeur] = self.__construire_arbre(sous_ensemble)
       #on retourne le nœud que l'on vient de créer
       return noeud

   def etiqueter(self, exemple):
       #on initialise le nœud actuel avec le haut de l'arbre
       noeud_actuel = self.arbre
       #tant que l'on est sur un nœud et pas sur une feuille
       while isinstance(noeud_actuel, Noeud):
           #valeur == valeur de l'exemple à étiqueter pour l'attribut du nœud
           valeur = exemple.dict_attributs[noeud_actuel.attribut_teste]
           #si valeur représente un nombre
           try:
               valeur = float(valeur)
           #si ça ne marche pas, tout va bien : c'est une valeur discrète
           except:
               pass
           #si c'est une valeur continue, on la transforme en intervalle
           else:
               for intervalle in noeud_actuel.enfants:
                   if valeur < intervalle[1] and valeur >= intervalle[0]:
                       valeur = intervalle
                       break
           finally:
               #mais il faut bien faire avancer le nœud
               noeud_actuel = noeud_actuel.enfants[valeur]
       #une fois l'exploration terminée, on étiquette l'exemple
       exemple.etiquette = noeud_actuel.etiquette

   def taux_erreur(self, ensemble):
       """
           renvoie un nombre dans [0, 1] correspondant à la proportion
           d'exemples dans ensemble qui se font étiqueter correctement
           avec l'arbre tel quel
       """
       compteur_etiquetages_incorrects = 0
       #pour chaque exemple
       for exemple in ensemble.liste_exemples:
           #on garde son étiquette
           etiquette = exemple.etiquette
           self.etiqueter(exemple)
           #et on la compare à l'étiquette donnée par l'arbre
           if etiquette != exemple.etiquette:
               #si elles sont différentes, on augmente la proportion
               #d'étiquetages incorrects et on rétablit la bonne étiquette
               compteur_etiquetages_incorrects += 1
               exemple.etiquette = etiquette
       return compteur_etiquetages_incorrects/len(ensemble)

   def elaguer(self):
       """
           modifie l'arbre en élaguant suivant l'ensemble de travail
           d'élagage donné dans self.chemin_elagage
       """
       #ATTENTION : si le chemin n'a pas été donné, on n'élague pas !
       if self.chemin_elagage != "":
           self.arbre = self.__elaguer_noeud(self.arbre,
                                             Ensemble(self.chemin_elagage))

   def __elaguer_noeud(self, noeud, ensemble_elagage):
       """
           élague le noeud passé en paramètre et le retourne
       """
       #si on est sur une feuille, on ne va pas plus loin
       if isinstance(noeud, Feuille):
           return noeud
       min_erreur, etiquette_gardee = 1.0, ""
       proportion_initiale = self.taux_erreur(ensemble_elagage)
       sauvegarde = self.arbre
       #pour chaque étiquette
       for etiquette in ensemble_elagage.etiquettes_possibles():
           self.arbre = Feuille(etiquette)
           #on calcule le taux d'erreur si on remplace le nœud par
           #l'étiquette en question
           taux_erreur_actuel = self.taux_erreur(ensemble_elagage)
           #on sauvegarde le meilleur taux
           if taux_erreur_actuel < min_erreur:
               min_erreur, etiquette_gardee = taux_erreur_actuel, etiquette
       #s'il existe un taux avantageux on élague à cet endroit
       if min_erreur <= proportion_initiale:
           return Feuille(etiquette_gardee)
       else:
           self.arbre = sauvegarde
       #on n'oublie pas de restaurer la valeur du sommet de l'arbre !
       sauvegarde, self.arbre = self.arbre, sauvegarde
       #on teste chaque enfant pour voir s'il est élagable
       for enfant in noeud.enfants:
           sous_ensemble = ensemble_elagage.sous_ensemble_attribut(
                                                   noeud.attribut_teste,
                                                   enfant)
           #s'il l'est, on l'élague
           if len(sous_ensemble) != 0:
               noeud.enfants[enfant] = self.__elaguer_noeud(
                                                   noeud.enfants[enfant],
                                                   sous_ensemble)
       #et au final, on renvoie le nœud aux enfants peut-être élagués 
       return noeud

def exemple_utilisation():
   """
       exemples d'utilisation
   """
   with open("datas PlayTennis.txt") as tmp:
       print("Exemple d'arbre avec ID3 sur le fichier datas PlayTennis.txt :"
             "\n\n{}\n\n" .format("".join(tmp.readlines())))
   arbre = Arbre_ID3("datas PlayTennis.txt")
   arbre.construire()
   arbre.afficher()
   exemple = Exemple(["outlook", "temperature", "humidity", "wind"],
                     ["sunny",   "cool",        "normal",   "strong"])
   print("etiquette : '{}'".format(exemple.etiquette))
   arbre.etiqueter(exemple)
   print("etiquette : '{}'\n\n".format(exemple.etiquette))

   print('-' * 35)

   with open("datas continues.txt") as tmp:
       print("\n\nExemple d'arbre avec C4.5 sur le fichier "
             "'datas continues.txt' :\n\n{}\n\n" \
             .format("".join(tmp.readlines())))
   arbre = Arbre_C45("datas continues.txt")
   arbre.construire()
   arbre.afficher()
   exemple = Exemple(["outlook", "temperature", "humidity", "wind"],
                     ["sunny",   "cool",        "60",   "strong"])
   print("etiquette : '{}'".format(exemple.etiquette))
   arbre.etiqueter(exemple)
   print("etiquette : '{}'".format(exemple.etiquette))

   print('-' * 35)

   with open("datas manquantes.txt") as tmp:
       print("\n\nExemple d'arbre avec C4.5 sur le fichier " \
             "datas manquantes.txt :\n\n{}\n\n" \
             .format("".join(tmp.readlines())))
   arbre = Arbre_C45("datas manquantes.txt")
   arbre.construire()
   arbre.afficher()
   exemple = Exemple(["outlook", "temperature", "humidity", "wind"],
                     ["sunny",   "cool",        "normal",   "strong"])
   print("etiquette : '{}'".format(exemple.etiquette))
   arbre.etiqueter(exemple)
   print("etiquette : '{}'".format(exemple.etiquette))

   with open("datas PlayTennis.txt") as tmp:
       print("\n\nExemple d'arbre avec C4.5 sur le fichier " \
             "datas PlayTennis.txt :\n\n{}\n\n" \
             .format("".join(tmp.readlines())))
   arbre = Arbre_C45("datas PlayTennis.txt", "datas élagage.txt")
   arbre.construire()
   arbre.afficher()
   print("\n\nÉlagage de l'arbre\n\n")
   arbre.elaguer()
   arbre.afficher()
   exemple = Exemple(["outlook", "temperature", "humidity", "wind"],
                     ["sunny",   "cool",        "normal",   "strong"])
   print("etiquette : '{}'".format(exemple.etiquette))
   arbre.etiqueter(exemple)
   print("etiquette : '{}'".format(exemple.etiquette))

if __name__ == "__main__":
   exemple_utilisation()