NSI Terminale
class ArbreDecision:
def __init__(self, data: list[dict[str]]):
self.data = data
self.titres = [clef for clef in self.data[0]] # titres = liste des clefs d'un des dictionnaire dans le tableau 'data"
self.attributs = [self.titres[i] for i in range(len(self.titres)-1)] # attributs = liste des titres, sauf le dernier
self.etiquette = self.titres[-1] # étiquette = dernier titre
self.classes = self.valeurs_possibles(self.data, self.etiquette) # classes = valeurs possibles pour l'étiquette
def valeurs_possibles(self, ensemble, titre: str)->list[str]:
"""
Détermine les valeurs possibles dans une colonne de titre donné dans un ensemble d'exemples.
"""
valeurs = []
for dico in ensemble:
if dico[titre] not in valeurs: # on ne stocke que les valeurs uniques
valeurs.append(dico[titre])
return valeurs
def sous_ensemble(self, ensemble: list[dict[str]], attribut: str, valeur: str)->list[dict[str]]:
"""
Renvoie un sous-ensemble d'exemples pour lesquels un attribut donné a une certaine valeur.
"""
s = []
for dico in ensemble:
if dico[attribut] == valeur:
s.append(dico)
return s
def classe_la_plus_frequente(self, ensemble):
max = 0
for valeur in self.valeurs_possibles(ensemble, self.etiquette):
sous_ensemble = self.sous_ensemble(ensemble, self.etiquette, valeur)
if len(sous_ensemble) > max: # max potentiel trouvé ?
max = len(sous_ensemble)
classe = sous_ensemble[0][self.etiquette]
return classe
def meilleur_attribut(self, ensemble: list[dict[str]], liste_attributs):
"""
Dans une liste d'attributs, recherche l'attribut apportant le meilleur gain d'information pour un ensemble d'exemples.
"""
m = ''
maxi = 0
for attribut in liste_attributs:
IG = self.gain_entropie(ensemble, attribut)
if IG > maxi:
maxi = IG
m = attribut
return m
On a bien ici affaire à un algorithme glouton, car à chaque étape, on choisit la meilleure possibilité à cette étape ( = heuristique ), sans étudier tous les choix possibles.
On n'est donc pas certain d'obtenir à la fin la solution optimale au problème posé, mais la détermination de celle-ci prendrait de toute manière un temps énorme : on se contente donc de ce que l'algorithme glouton nous donne, en considérant qu'il fait de son mieux ! 😉...
def creer_arbre(self, ensemble, liste_attributs):
if self.entropie(ensemble) == 0:
classe = ensemble[0][self.etiquette]
return Noeud(classe)
if len(liste_attributs) == 0:
return Noeud(self.classe_la_plus_frequente(ensemble))
attribut_optimal = self.meilleur_attribut(ensemble, liste_attributs)
if attribut_optimal !='':
liste_attributs.remove(attribut_optimal)
else:
return Noeud(self.classe_la_plus_frequente(ensemble))
noeud = Noeud(attribut_optimal, {})
for valeur in self.valeurs_possibles(ensemble, attribut_optimal):
s = self.sous_ensemble(ensemble, attribut_optimal, valeur)
noeud.enfants[valeur] = self.creer_arbre(s , liste_attributs)
return noeud
#self.arbre = self.creer_arbre(self.data, self.attributs)
class ArbreDecision:
def __init__(self, data):
...
self.arbre = self.creer_arbre(self.data, self.attributs) # on rajoute un attribut à la classe pour stocker l'arbre lui-même
... # extraction des données
dt = ArbreDecision(data) # instanciation de l'arbre
def affiche(self, noeud, n = 0):
if noeud.enfants is not None:
for enfant in noeud.enfants:
print("\t"*n + f"{noeud.valeur} {enfant}")
self.affiche(noeud.enfants[enfant], n+1)
else:
print("\t"*n + f"{noeud.valeur}")
dt.affiche(dt.arbre)
def etiqueter(self, exemple:dict[str])->str:
"""
Renvoie la classe à laquelle appartient l'exemple.
"""
noeud = self.arbre
while noeud.enfants is not None:
attribut = noeud.valeur
for cle in exemple:
if cle == attribut:
valeur = exemple[cle]
noeud = noeud.enfants[valeur]
return noeud.valeur
ex1 = {'Emploi': 'Sans emploi', 'Age': '30', 'Résidence': 'Chez parents', 'Enfants': '0', 'Revenu conjoint': '0', 'Revenu': '0', 'Prêt immo.': '0', 'Autre': '0'}
ex2 = {'Emploi': 'Retraité', 'Age': '60', 'Résidence': 'Propriétaire', 'Enfants': '3', 'Revenu conjoint': '0', 'Revenu': '50000', 'Prêt immo.': '1000', 'Autre': '0'}
dt.etiqueter(ex1) # renvoie 'non'
dt.etiqueter(ex2) # renvoie 'oui'