Une première version: ID3 - Les arbres de décisions

9

14

)

× log2

(

9

14

)

−

(

5

14

)

× log2

(

5

14

)

= 0.94

Il faut savoir que, comme on peut le voir sur la Fig. 4,

∀S : 0 ≤ Entropie(S) ≤ 1

Ce qui veut dire que pour tout ensemble S, le désordre de S est toujours compris entre 0 et 1.

Maintenant que nous savons que l’entropie initiale du set est de 0.94, il nous faut savoir quel attribut tester en premier, puis

en second, …, puis en n-ième.

Pour savoir quel attribut tester, il faut connaître la notion de gain d’entropie. Le gain est déni par un set d’exemples et par

un attribut. Cette formule va donc servir à calculer ce que cet attribut apporte au désordre du set. Plus un attribut contribue au

désordre, plus il est important de le tester pour séparer le set en plus petits sets ayant une entropie moins élevée.

Gain(S, A) = Entropie(S) −

∑

v ∈ valeurs ( A )

| Sv |

| S |

× Entropie(Sv)

L’attribut qui va être testé à ce nœud de l’arbre est le nœud qui va le plus réduire l’entropie. C’est logique : quand l’entropie

vaut zéro, c’est qu’il n’y a qu’une seule classe représentée :

− 1 × log2(1) − n × (0 × log2(0)) = 0 − n × 0 = 0

Ici, j’ai mis un n en évidence pour dire qu’il peut y avoir autant de classes que l’on veut. Mais si la probabilité d’une

classe est 1, on a beau avoir 150 classes, leur probabilité sera nulle à chaque fois. On peut donc mettre le nombre de

classes en évidence. Mais attention, si je mets n en évidence, c’est parce qu’il y a n classes de probabilité nulle, mais

il y a aussi une classe de probabilité 1. Il y a donc n+1 classes diérentes.

Toujours dans notre exemple du point 2, en considérant S comme le set initial, pour déterminer l’attribut à tester, il faut

calculer le gain de tous les attributs :

2.1. Calcul de gain dʼentropie

2.1.1. Prévisions

L’attribut Prévisions a trois valeurs possibles : {Ensoleillé, Nuageux, Pluvieux}.

https://zestedesavoir.com/tutoriels/962/les-arbres-de-decisions/premiere-version-id13/#1-10802_lalgorithme-id3

4/24

12/11/21, 5:46 PM

Une première version : ID3 - Les arbres de décisions • Tutoriels • Zeste de Savoir

Gain(S, Prévisions) = Entropie(S)

= 0.94

−

−

−

−

−

−

5

14

4

14

5

14

5

14

4

14

5

14

× Entropie(SEnsoleillé)

× Entropie(SNuageux)

× Entropie(SPluvieux)

× −

× −

× −

(

(

(

3

5

0

4

3

5

× log2

× log2

× log2

3

5

0

( )

( )

( )

3

5

4

−

−

−

2

5

4

4

2

5

× log2

× log2

× log2

5

4

2

( ))

( ))

( ))

5

2

4

= 0.94

= 0.24742

− 0.357 × (0.97)

− 0.286 × (0)

− 0.357 × (0.97)

2.1.2. Vent

L’attribut Vent a quant à lui deux valeurs possibles : {Faible, Fort}.

Gain(S, Vent) = Entropie(S)

−

−

8

14

6

14

× −

(

(

6

8

3

6

× log2

× log2

8

6

( )

( )

6

3

−

−

2

8

3

6

× log2

× log2

2

8

( ))

( ))

3

6

× −

= 0.94

= 0.048

− 0.571 × (0.811)

− 0.428 × 1

2.1.3. Humidité

Humidité a également deux valeurs possibles : {Élevée, Normale}.

Gain(S, Humidité) = Entropie(S)

−

−

7

14

7

14

× −

(

(

4

7

6

7

× log2

× log2

4

7

( )

( )

6

7

−

−

3

7

1

7

× log2

× log2

3

7

( ))

( ))

1

7

× −

= 0.94

= 0.153

− 0.49

− 0.296

2.1.4. Température

Température a trois valeurs diérentes possibles : {Chaud, Chaud, Frais}.

https://zestedesavoir.com/tutoriels/962/les-arbres-de-decisions/premiere-version-id13/#1-10802_lalgorithme-id3

5/24

12/11/21, 5:46 PM

Une première version : ID3 - Les arbres de décisions • Tutoriels • Zeste de Savoir

Gain(S, Température) = Entropie(S)

−

−

−

4

14

6

14

4

14

× −

× −

× −

(

(

(

2

4

4

6

3

4

× log2

× log2

× log2

2

4

4

( )

( )

( )

6

4

3

−

−

−

2

4

2

6

1

4

× log2

× log2

× log2

2

4

2

( ))

( ))

( ))

4

6

1

= 0.94

= 0.028

− 0.286

− 0.394

− 0.232

Récapitulons : Gain(S, Température) < Gain(S, Vent) < Gain(S, Humidité) < Gain(S, Prévisions). On peut voir que le plus grand gain est pour

Prévisions. C’est donc Prévisions qui est le premier attribut testé dans l’arbre. Si on regarde chaque nœud ls, on remarque

que pour le nœud Nuageux, tous les résultats sont positifs. Il n’y a donc pas d’attribut à tester ici, on peut directement

étiqueter Oui. Voici à quoi ressemble notre arbre.

arbre à la première itération de sa réalisation (Fig. 5)

Image perdue

J’ai utilisé une notation entre crochets de la forme [n+, m-]. Cette notation veut dire que dans l’ensemble ayant n+m

éléments, n sont positifs et m sont négatifs. Dans notre cas, les positifs sont les exemples étiquetés Oui et les

négatifs sont ceux étiquetés Non bien entendu.

Il faut maintenant continuer à mettre des nœuds après Ensoleillé et Pluvieux car tous les exemples ne donnent pas le même

résultat. Déterminons donc pour Ensoleillé quel est le meilleur attribut à tester en utilisant à nouveau le gain. Cependant il

n’est plus utile de tester le gain de Prévisions étant donné qu’il vient d’être utilisé. Je vous donne juste les résultats, je vous

laisse faire les calculs vous-même pour vous entrainer.

Rappel : pour ceux n’ayant pas de fonctionnalité log2 sur leur calculatrice :

log2(f(x)) =

log(f(x))

log(2)

Voici donc ce que vous devez normalement obtenir :

Gain(SEnsoleillé, Température) = 0.571

Gain(SEnsoleillé, Humidité) = 0.971

Gain(SEnsoleillé, Vent) = 0.019

Donc récapitulons à nouveau :

Gain(SEnsoleillé, Vent) < Gain(SEnsoleillé, Température) < Gain(SEnsoleillé, Humidité)

Le plus grand gain est pour Humidité. D’ailleurs on peut voir que le gain est égal à l’entropie de SEnsoleillé. Ça veut dire que tous

les ls de Humidité donneront une étiquette. Voilà notre arbre jusqu’à présent. Il nous reste à continuer l’arbre du côté de

https://zestedesavoir.com/tutoriels/962/les-arbres-de-decisions/premiere-version-id13/#1-10802_lalgorithme-id3

6/24

12/11/21, 5:46 PM

Une première version : ID3 - Les arbres de décisions • Tutoriels • Zeste de Savoir

Pluvieux. Voici les gains pour les diérents attributs (à nouveau, il n’est pas nécessaire de tester Prévisions qui vient de l’être

mais il faut tester Humidité qui n’a pas été testé de ce côté-là de la branche) :

Gain(SPluvieux, Température) = 0.019

Gain(SPluvieux, Humidité) = 0.019

Gain(SPluvieux, Vent) = 0.971

Récapitulons une fois de plus :

Gain(SPluvieux, Température) ≤ Gain(SPluvieux, Humidité) < Gain(SPluvieux, Vent)

Le plus grand gain est à nouveau de 0.971 et est pour Vent. Il nous faut donc tester Vent et vu que le gain est égal à l’entropie

de SPluvieux, chaque nœud ls de Vent sera une étiquette.

Voici donc notre arbre. Il n’y a plus rien à faire étant donné qu’il ne reste aucun nœud qui n’est pas étiqueté. Le travail est

donc accompli et voilà l’arbre que nous avons généré.

lʼarbre généré par ID3 de lʼexemple playTennis (Fig. 6)

Si vous comparez l’arbre que nous venons de générer avec l’arbre que je vous ai donné en début de tutoriel, vous pouvez

constater que c’est exactement le même. L’arbre est optimisé car il donne une étiquette en maximum deux tests alors qu’il y a

4 attributs diérents.

Vous ne voyez peut-être pas l’utilité de cet arbre parce qu’ici il y a maximum 36 combinaisons des attributs et 14 nous sont

déjà données. Mais imaginez maintenant que vous voulez faire un arbre qui va déterminer un diagnostic pour des malades.

Comme il existe des milliers de maladies et encore plus de symptômes, l’arbre sera plus dicile à faire à la main. Ceci dit, tant

que tous les exemples possibles n’ont pas été donnés il est possible que l’arbre contienne des erreurs. Mais nous y

reviendrons plus tard.

3. Algorithme et pseudo-code de lʼalgorithme ID3

Voici l’algorithme de génération d’un arbre de décision selon ID3 sous forme de pseudo-code. Ce chapitre est pour les

programmeurs. Si vous êtes uniquement venus pour les maths, ce chapitre ne vous concerne pas directement et vous n’êtes

pas obligés de lire ce qui suit.

Je ne vais pas détailler le pseudo-code, ça devrait sembler relativement clair. Et si vous avez tout de même besoin d’aide à la

compréhension, regardez dans les commentaires, peut-être trouverez-vous votre réponse. Et si vous ne l’y trouvez pas,

posez votre question sur les forums, c’est à ça qu’ils servent.

https://zestedesavoir.com/tutoriels/962/les-arbres-de-decisions/premiere-version-id13/#1-10802_lalgorithme-id3

7/24

12/11/21, 5:46 PM

Une première version : ID3 - Les arbres de décisions • Tutoriels • Zeste de Savoir

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

FONCTION ID3

Entrée :

• exemples = liste d'exemples étiquetés

• questions = liste des attributs non utilisés jusqu'à présent

Retour :

• un nœud

DEBUT

SI exemples est vide, alors

Finir la fonction sans construire de nœud

FIN SI

SI tous les exemples sont la même classe, alors

Retourner une feuille ayant cette classe

FIN SI

SI questions est vide, alors

Retourner une feuille avec la classe la plus fréquente

FIN SI

q = attribut optimal (avec le plus grand gain d'entropie)

n = nouveau nœud créé qui testera l'attribut q

POUR CHAQUE v = valeur possible de q, FAIRE

e = l'ensemble des éléments de exemples ayant v comme valeur à l'attribut q

chaque nœud fils de n est créé par ID3(e, questions\{q})

FIN POUR CHAQUE

Retourner n

FIN

Notez que si la condition SI questions est vide est remplie, ça veut dire que deux exemples identiques mais étiquetés

diéremment ont été mis dans le set d’exemples de test.

4. Améliorations

Ici sont présentées d’abord les améliorations que l’on peut apporter aux notions vues au (§2.).

5

Commençons par la fonction d’Entropie. Une petite étude mathématique nous montre que la probabilité d’une classe dans un

set n’est autre que la longueur du sous-set de cette classe divisée par la longueur du set initial. Donc

https://zestedesavoir.com/tutoriels/962/les-arbres-de-decisions/premiere-version-id13/#1-10802_lalgorithme-id3

8/24

12/11/21, 5:46 PM

Une première version : ID3 - Les arbres de décisions • Tutoriels • Zeste de Savoir

Entropie(S) = ∑

− pc × log2(pc)

c ∈ classes ( S )

= ∑

c ∈ classes ( S )

−

| c |

| S |

× log2

(

| c |

| S |

)

= −

= −

= −

= −

= −

= −

1

| S |

1

| S |

1

| S |

1

| S |

1

| S |

1

| S |

∑

c ∈ classes ( S )

∑

c ∈ classes ( S )

| c | × log2

(

| c |

| S |

)

| c | × (log2 | c | − log2 | S | )

(

(

(

∑

c ∈ classes ( S )

∑

c ∈ classes ( S )

∑

c ∈ classes ( S )

| c | × log2 | c | − ∑

| c | × log2 | S |

c ∈ classes ( S )

)

| c | × log2 | c | − log2 | S | ∑

c ∈ classes ( S )

| c |

)

| c | × log2 | c | − | S | × log2 | S |

)

∑

c ∈ classes ( S )

| c | × log2 | c | +

| S |

| S |

× log2 | S |

= 1 × log2 | S | −

= log2 | S | −

| c | × log2 | c |

1

| S |

∑

c ∈ classes ( S )

∑c ∈ classes ( S ) | c | × log2 | c |

| S |

Alors cette petite démonstration peut vous paraître rude, mais elle est très bien car elle nous permet de faire beaucoup moins

de calculs. C’est très pratique tant pour programmer (car le programme sera plus rapide) que pour faire les calculs de tête

(vous risquez beaucoup moins de faire des erreurs). On a donc simplié notre splendide fonction d’entropie et on a gardé un

indice sommatoire tout de même. Ouf !

Quid de la fonction de \text{Gain}(S, A) ?

Cette fonction varie entre 0 et \text{Entropie}(S) vu que :

0 < \displaystyle \sum_{v\ \in\ \text{valeurs}(A)}\frac{|S_v|}{|S|} \times \text{Entropie}(S_v) < \text{Entropie}(S)

Quand la somme vaut 0, \text{Gain}(S, A) vaut \text{Entropie}(S) ce qui est son maximum. C’est donc cet attribut qui va être

choisi. Alors que si la somme vaut \text{Entropie}(S), gain vaut 0 et donc cet attribut n’est pas intéressant à tester à ce

moment vu qu’il ne réduit pas l’entropie (qui est, rappelons-le, le désordre des classications du set). La seule chose qui nous

intéresse dans cette fonction est donc la somme qui doit être la plus petite possible (il nous faut avoir le moins de désordre).

On peut donc changer la fonction comme ceci :

\text{Perte}(S, A) = \sum_{v\ \in\ \text{valeurs}(A)}\frac{|S_v|}{|S|} \times \text{Entropie}(S_v) = \frac{1}{|S|} \times \displaystyle

\sum_{v\ \in\ \text{valeurs}(A)}|S_v| \times \text{Entropie}(S_v)

Sauf que je viens de vous montrer comment améliorer la fonction d’entropie. On peut donc encore simplier la fonction de

gain !

\begin{aligned} \text{Perte}(S, A) &= \frac{1}{|S|} \times \sum_{v \, \in \, \text{valeurs}(A)}|S_v| \times Entropie(S_v) \\ &= \frac{1}{|S|}

\times \sum_{v \, \in \, \text{valeurs}(A)}|S_v| \times \le(\log_2|S_v| - \frac{1}{|S_v|} \times \sum_{c \, \in \, \text{classes}(S_v)}|c|

\times \log_2|c|\right) \\ &= \frac{1}{|S|} \times \le(\sum_{v \, \in \, \text{valeurs}(A)}|S_v| \times \log_2|S_v| - \sum_{v \, \in \,

\text{valeurs}(A)}\frac{|S_v|}{|S_v|} \times \sum_{c \, \in \, \text{classes}(S_v)}|c| \times \log_2|c|\right) \\ &= \frac{1}{|S|} \times

https://zestedesavoir.com/tutoriels/962/les-arbres-de-decisions/premiere-version-id13/#1-10802_lalgorithme-id3

9/24

12/11/21, 5:46 PM

Une première version : ID3 - Les arbres de décisions • Tutoriels • Zeste de Savoir

\le(\sum_{v \, \in \, \text{valeurs}(A)} |S_v|\times \log_2|S_v| - \sum_{v \in \text{valeurs}(A)} \sum_{c \, \in \, \text{classes}(S_v)} |c|

\times \log_2|c|\right) \end{aligned}

Je ne pense pas que cette amélioration-ci ait réellement une inuence en termes de performances lors d’un programme mais

c’est plus facile de faire les calculs à la main avec cette formule. La double somme peut faire un petit peu peur, mais ce n’est

pas bien compliqué : ça veut dire qu’on fait la somme sur tous les v, et que pour chaque v, on ajoute la somme sur tous les c.

PS : faites bien attention, ici c’est bien un indice sommatoire sur c dans les classes de S_v et plus juste dans S. La raison est

bien simple, c’est ce qui est expliqué juste au-dessus, c’est lié à la double somme.

Ces améliorations ne changent rien à l’algorithme. Ce sont juste de légères optimisations pour éviter de trop calculer. C’est

pour ceux qui programment leur algorithme mais également pour ceux qui font leurs calculs sur papier et à la calculette (ou

pour les plus balèzes, qui font les calculs de logarithmes avec leurs tables) et qui ne veulent pas tout le temps calculer les

mêmes choses ce qui augmente la probabilité d’erreurs.

Une implémentation

5. Implémentation

Je vais vous proposer une implémentation détaillée en python3. Je vas vous guider étape par étape dans la réalisation de ce

programme. Et pour ceux qui ne savent pas vraiment programmer ce n’est pas grave, le code complet sera mis à la n.

Le code que je vous propose est une implémentation que j’ai choisie et que j’ai développée. Elle n’est pas la plus

performante mais les choix sont avant tout pédagogiques.

Le code qui suit est pseudo-orienté objet (dans la mesures de ce que Python permet), il vous faut être relativement à

l’aise avec cette notion pour pouvoir le comprendre !

5.1. Les types de données nécessaires

Commençons par déterminer de quelles structures de données nous allons avoir besoin. Voici ce que je propose, je vous laisse

le lire, puis j’expliquerai.

1

2

3

classe Nœud:

• enfants: dict

• attribut_testé: str

https://zestedesavoir.com/tutoriels/962/les-arbres-de-decisions/premiere-version-id13/#1-10802_lalgorithme-id3

10/24

1. Pour plus d’informations, c’est ici et plus largement ici ou encore par ici. ↩2. Plus de détails : ici. ↩3. ici, la classication discrète s’oppose à la classication continue. Les mathématiques discrètes concernent les opérationssur des ensembles nis (ex : les possibilités d’un jet de dé : \left\{1, 2, 3, 4, 5, 6\right\}) alors que les mathématiquescontinues concernent les opérations sur des ensembles innis (ex : \mathbb R) ↩4. j’ai tendance à arrondir à la seconde décimale histoire que tout le monde ait une idée de l’ordre de grandeur pour pouvoirfaire des comparaisons. Mais pour une question de lisibilité, je préfère mettre le symbole = que le symbole \simeq. Lavaleur ici n’est donc pas précisément 0.94 mais s’en rapproche assez fort. On peut donc se permettre uneapproximation. ↩5. ce chapitre n’est pas indispensable à la lecture. C’est un développement mathématique sur les logarithmes qui permet desimplier l’écriture et/ou le sens des formules. Vous pouvez soit l’ignorer et passer à la suite, soit regarder à quellesformules on arrive sans regarder le reste, soit suivre toute la pseudo-démonstration (qui s’apparente plus à undéveloppement et à des substitutions). Je vous conseille de faire ce que votre cerveau pourra tolérer en terme de maths, jene vous en voudrai pas si vous ne le lisez même pas ;) ↩12/11/21, 5:46 PM

Une première version : ID3 - Les arbres de décisions • Tutoriels • Zeste de Savoir

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

classe Feuille:

• étiquette: str

classe Exemple:

• étiquette: str

• attributs: dict

classe Ensemble:

• noms_attributs: list de str

• liste_exemples: list de Exemple

classe Arbre_ID3:

• arbre: Nœud/Feuille

• ensemble: Ensemble

Voilà le moment où je dois vous l’expliquer. J’ai donc fait un découpage en classes. Peut-être auriez-vous fait autrement mais

voilà, c’est ce que j’ai choisi.

Pourquoi ces classes là ?

Bon pour commencer, laissez-moi expliquer la classe Arbre_ID3. Cette classe contient deux informations importantes :

l’arbre en lui-même ;

et l’ensemble de données sur lequel il est construit.

Cet ensemble, il est de classe Ensemble (oui je sais c’est pas très imaginatif mais au moins, c’est clair

). La classe Ensemble

quant à elle contient également deux informations mais ce ne sont pas du tout les mêmes :

le nom des attributs qui sont à utiliser ;

et les exemples.

Le nom des attributs est stocké dans une liste (qui est un type interne à Python ) et les exemples sont également stockés dans

1

une liste. Mais que contiennent ces listes me direz-vous !

… Mais que contiennent ces listes ?

Merci de poser la question, ça me permet de vous expliquer la classe Exemple ! La première liste, le nom des attributs ne

contient que des chaines de caractères, ou des Strings. Ce type s’appelle str en Python. Par contre, la seconde liste, celle qui

contient les exemples contient des… Exemples ! donc des objets de la classe Exemple.

Cette classe Exemple contient deux informations importantes :

l’étiquette de l’exemple ;

et ses attributs.

L’étiquette est une str alors que les attributs sont un dictionnaire ayant pour clef le nom de l’attribut et comme valeur la

valeur de l’attribut. Logique, non ?

Je crois qu’on en a ni pour vous expliquer ce qui était contenu dans la variable ensemble de la classe Arbre_ID3… Mais il

nous reste la variable arbre !

Cette variable arbre est soit un objet de type Feuille soit un objet de type Nœud. Étant donné que la notion d’arbre est un

prérequis pour ce cours, je considère que vous connaissez ces deux termes et je ne m’attarderai pas dessus.

https://zestedesavoir.com/tutoriels/962/les-arbres-de-decisions/premiere-version-id13/#1-10802_lalgorithme-id3

11/24

12/11/21, 5:46 PM

Une première version : ID3 - Les arbres de décisions • Tutoriels • Zeste de Savoir

La classe Feuille ne contient qu’un élément de type str . C’est vrai que ce n’était pas obligatoire d’en faire une classe, mais je

préférais pour une raison de clarté.

La classe Nœud quant à elle contient la valeur de l’attribut testé dans un str et un dictionnaire de Nœuds. Eectivement,

c’est bien le principe : pour faire un arbre n-aire, il nous faut pouvoir mettre autant de ls que possible à chaque nœud.

Nous avons maintenant fait le tour des variables, nous pouvons passer à la phase de développement du code, du vrai !

5.2. Le code le vrai

La première chose que doit faire notre code, c’est savoir sur quelles données il va travailler. On pourrait soit rentrer toutes nos

données de la classe Ensemble à la main, mais j’ai le sentiment que ça va être long, fastidieux et inutile… Je vous propose donc

de créer une fonction qui va récupérer des données dans un chier !

5.2.1. implémentation des types de données basiques

Cette fonction est une méthode de la classe Ensemble. Pourquoi ? C’est simple : on veut faire une fonction qui va remplir notre

classe Ensemble et donc créer et modier ses éléments. Cette méthode est donc dans notre classe Ensemble. Je propose même

que ça fasse partie de notre constructeur ! je vais tout de même laisser la possibilité de créer un Ensemble simple, vous

comprendrez plus tard pourquoi.

Voici donc le début de notre classe Ensemble qui contient un constructeur et une fonction qui nous permet d’alléger le code

du constructeur.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

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

https://zestedesavoir.com/tutoriels/962/les-arbres-de-decisions/premiere-version-id13/#1-10802_lalgorithme-id3

12/24

12/11/21, 5:46 PM

Une première version : ID3 - Les arbres de décisions • Tutoriels • Zeste de Savoir

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

)

@staticmethod #fonction statique car ne dépend pas de l'objet mais est commune à toute instan

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) \

#on ajoute un objet de type Exemple contenant la ligne

ret.append(Exemple(noms_attributs,

else ""

attributs[:len(noms_attributs)],

etiquette))

return ret

Voici comment nous allons coder le constructeur d’Exemple : cette fonction doit prendre en paramètres la liste contenant le

nom des attributs, puis la liste contenant la valeur de chaque attribut, puis l’étiquette.

Voilà donc le début de notre classe Exemple :

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

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

https://zestedesavoir.com/tutoriels/962/les-arbres-de-decisions/premiere-version-id13/#1-10802_lalgorithme-id3

13/24

12/11/21, 5:46 PM

Une première version : ID3 - Les arbres de décisions • Tutoriels • Zeste de Savoir

28

29

30

31

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]

Lançons-nous maintenant dans la création de l’arbre en lui-même. Il nous faut donc manipuler la classe Arbre_ID3, et donc,

la créer ! Le constructeur doit prendre une variable, à savoir le chemin vers le chier de données à envoyer au constructeur de

sa variable ensemble :

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Voilà la base de notre classe. Sauf que jusqu’ici, on ne sait qu’initialiser les données, nous ce qu’on veut faire, c’est bien plus !

Il nous faut donc pouvoir créer l’arbre. Voici la méthode de Arbre_ID3 que je vous propose :

1

2

3

4

5

def construire(self):

"""

génère l'arbre sur base de l'ensemble pré-chargé

"""

self.arbre = self.__construire_arbre(self.ensemble)

Alors, vous aimez ?

Bon d’accord, je le reconnais, je n’ai pas codé la réalisation de l’arbre… Mais c’est fait exprès ! J’ai créé une petite fonction

toute simple à appeler par l’utilisateur pour que l’arbre se crée. Cette fonction appelle la fonction privée

__construi...