Classification

Introduction à la fouille de données

M. Ledmi
m_ledmi@[Link]
Département d’Informatique Khenchela

2020/2021

M. Ledmi Introduction à la fouille de données

 Classification

Plan

1 Classification
Quelques Notation
Définition
Arbres de décision

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Vous êtes ici

1 Classification
Quelques Notation
Définition
Arbres de décision

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Quelques Notation

On notera X un ensemble de données.

Chaque donnée est décrite par un ensemble A d’attributs.
Chaque attribut a ∈ A prend sa valeur dans un certain ensemble de
valeurs Va
Ainsi, on peut considérer l’ensemble des données x dont les
coordonnées balayent toutes les valeurs possibles des attributs : c’est
l’espace des données que nous noterons D.
Si l’on note a1 , a2 . . . aP les P attributs,D = Va1 × Va2 × . . . × VaP .
Toute donnée appartient à cet ensemble et on a X ⊂ D.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Quelques Notation

On notera X un ensemble de données.

Chaque donnée est décrite par un ensemble A d’attributs.
Chaque attribut a ∈ A prend sa valeur dans un certain ensemble de
valeurs Va
Ainsi, on peut considérer l’ensemble des données x dont les
coordonnées balayent toutes les valeurs possibles des attributs : c’est
l’espace des données que nous noterons D.
Si l’on note a1 , a2 . . . aP les P attributs,D = Va1 × Va2 × . . . × VaP .
Toute donnée appartient à cet ensemble et on a X ⊂ D.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Quelques Notation

On notera X un ensemble de données.

Chaque donnée est décrite par un ensemble A d’attributs.
Chaque attribut a ∈ A prend sa valeur dans un certain ensemble de
valeurs Va
Ainsi, on peut considérer l’ensemble des données x dont les
coordonnées balayent toutes les valeurs possibles des attributs : c’est
l’espace des données que nous noterons D.
Si l’on note a1 , a2 . . . aP les P attributs,D = Va1 × Va2 × . . . × VaP .
Toute donnée appartient à cet ensemble et on a X ⊂ D.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Quelques Notation

On notera X un ensemble de données.

Chaque donnée est décrite par un ensemble A d’attributs.
Chaque attribut a ∈ A prend sa valeur dans un certain ensemble de
valeurs Va
Ainsi, on peut considérer l’ensemble des données x dont les
coordonnées balayent toutes les valeurs possibles des attributs : c’est
l’espace des données que nous noterons D.
Si l’on note a1 , a2 . . . aP les P attributs,D = Va1 × Va2 × . . . × VaP .
Toute donnée appartient à cet ensemble et on a X ⊂ D.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Quelques Notation

On notera X un ensemble de données.

Chaque donnée est décrite par un ensemble A d’attributs.
Chaque attribut a ∈ A prend sa valeur dans un certain ensemble de
valeurs Va
Ainsi, on peut considérer l’ensemble des données x dont les
coordonnées balayent toutes les valeurs possibles des attributs : c’est
l’espace des données que nous noterons D.
Si l’on note a1 , a2 . . . aP les P attributs,D = Va1 × Va2 × . . . × VaP .
Toute donnée appartient à cet ensemble et on a X ⊂ D.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Quelques Notation

On notera X un ensemble de données.

Chaque donnée est décrite par un ensemble A d’attributs.
Chaque attribut a ∈ A prend sa valeur dans un certain ensemble de
valeurs Va
Ainsi, on peut considérer l’ensemble des données x dont les
coordonnées balayent toutes les valeurs possibles des attributs : c’est
l’espace des données que nous noterons D.
Si l’on note a1 , a2 . . . aP les P attributs,D = Va1 × Va2 × . . . × VaP .
Toute donnée appartient à cet ensemble et on a X ⊂ D.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs

Une donnée est un :

Enregistrement au sens des bases de données,
Individu (terminologie issue des statistiques).
Instance (terminologie orientée objet en informatique) .
Tuple (terminologie base de données)

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs

Une donnée est un :

Enregistrement au sens des bases de données,
Individu (terminologie issue des statistiques).
Instance (terminologie orientée objet en informatique) .
Tuple (terminologie base de données)

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs

Une donnée est un :

Enregistrement au sens des bases de données,
Individu (terminologie issue des statistiques).
Instance (terminologie orientée objet en informatique) .
Tuple (terminologie base de données)

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs

Une donnée est un :

Enregistrement au sens des bases de données,
Individu (terminologie issue des statistiques).
Instance (terminologie orientée objet en informatique) .
Tuple (terminologie base de données)

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs

Une donnée est un :

Enregistrement au sens des bases de données,
Individu (terminologie issue des statistiques).
Instance (terminologie orientée objet en informatique) .
Tuple (terminologie base de données)

Une données est caractérisée par un ensemble de champs, de caractères

, ou encore d’attributs.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
Un attribut peut être de nature qualitative ou quantitative en fonction de
l’ensemble des valeurs qu’il peut prendre.
Attribut qualitatif
Si on ne peut pas en faire une moyenne ;
Sa valeur est d’un type défini en extension (une couleur, une
marque de voiture, . . . etc.).

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
Un attribut peut être de nature qualitative ou quantitative en fonction de
l’ensemble des valeurs qu’il peut prendre.
Attribut qualitatif
Si on ne peut pas en faire une moyenne ;
Sa valeur est d’un type défini en extension (une couleur, une
marque de voiture, . . . etc.).

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
Un attribut peut être de nature qualitative ou quantitative en fonction de
l’ensemble des valeurs qu’il peut prendre.
Attribut qualitatif
Si on ne peut pas en faire une moyenne ;
Sa valeur est d’un type défini en extension (une couleur, une
marque de voiture, . . . etc.).

Attribut quantitatif
L’attribut est de nature quantitative : un entier, un réel, . . . etc.
Il peut représenter un salaire, une surface, un nombre d’habitants,
. . . etc.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
Un attribut peut être de nature qualitative ou quantitative en fonction de
l’ensemble des valeurs qu’il peut prendre.
Attribut qualitatif
Si on ne peut pas en faire une moyenne ;
Sa valeur est d’un type défini en extension (une couleur, une
marque de voiture, . . . etc.).

Attribut quantitatif
L’attribut est de nature quantitative : un entier, un réel, . . . etc.
Il peut représenter un salaire, une surface, un nombre d’habitants,
. . . etc.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
Un attribut peut être de nature qualitative ou quantitative en fonction de
l’ensemble des valeurs qu’il peut prendre.
Attribut qualitatif
Si on ne peut pas en faire une moyenne ;
Sa valeur est d’un type défini en extension (une couleur, une
marque de voiture, . . . etc.).

Attribut quantitatif
L’attribut est de nature quantitative : un entier, un réel, . . . etc.
Il peut représenter un salaire, une surface, un nombre d’habitants,
. . . etc.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut nominal
Les valeurs sont des symboles (des noms)
Aucune relation (ordre ou distance) entre les nominaux n’existe.
Seuls des tests d’égalité peuvent être exécutés.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut nominal
Les valeurs sont des symboles (des noms)
Aucune relation (ordre ou distance) entre les nominaux n’existe.
Seuls des tests d’égalité peuvent être exécutés.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut nominal
Les valeurs sont des symboles (des noms)
Aucune relation (ordre ou distance) entre les nominaux n’existe.
Seuls des tests d’égalité peuvent être exécutés.

Exemples
Les valeurs de Temps (Ensoleillé, Pluvieux, Neigeux, Gris)
La couleur (Vert, Bleu, Rouge)
Si T emps = P luvieux alors Jouer = N on
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut nominal
Les valeurs sont des symboles (des noms)
Aucune relation (ordre ou distance) entre les nominaux n’existe.
Seuls des tests d’égalité peuvent être exécutés.

Exemples
Les valeurs de Temps (Ensoleillé, Pluvieux, Neigeux, Gris)
La couleur (Vert, Bleu, Rouge)
Si T emps = P luvieux alors Jouer = N on
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut nominal
Les valeurs sont des symboles (des noms)
Aucune relation (ordre ou distance) entre les nominaux n’existe.
Seuls des tests d’égalité peuvent être exécutés.

Exemples
Les valeurs de Temps (Ensoleillé, Pluvieux, Neigeux, Gris)
La couleur (Vert, Bleu, Rouge)
Si T emps = P luvieux alors Jouer = N on
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut nominal
Les valeurs sont des symboles (des noms)
Aucune relation (ordre ou distance) entre les nominaux n’existe.
Seuls des tests d’égalité peuvent être exécutés.

Exemples
Les valeurs de Temps (Ensoleillé, Pluvieux, Neigeux, Gris)
La couleur (Vert, Bleu, Rouge)
Si T emps = P luvieux alors Jouer = N on
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut ordinal
Une notion d’ordre s’impose sur les ordinaux.
Mais il n’est pas possible de calculer directement des distances
entre des valeurs ordinales.
Les opérations d’addition et de soustraction ne sont pas possibles.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut ordinal
Une notion d’ordre s’impose sur les ordinaux.
Mais il n’est pas possible de calculer directement des distances
entre des valeurs ordinales.
Les opérations d’addition et de soustraction ne sont pas possibles.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut ordinal
Une notion d’ordre s’impose sur les ordinaux.
Mais il n’est pas possible de calculer directement des distances
entre des valeurs ordinales.
Les opérations d’addition et de soustraction ne sont pas possibles.

Exemples
La température est décrite par les adjectifs chaud, froid, moyen, et
chaud > moyen > froid
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut ordinal
Une notion d’ordre s’impose sur les ordinaux.
Mais il n’est pas possible de calculer directement des distances
entre des valeurs ordinales.
Les opérations d’addition et de soustraction ne sont pas possibles.

Exemples
La température est décrite par les adjectifs chaud, froid, moyen, et
chaud > moyen > froid
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut ordinal
Une notion d’ordre s’impose sur les ordinaux.
Mais il n’est pas possible de calculer directement des distances
entre des valeurs ordinales.
Les opérations d’addition et de soustraction ne sont pas possibles.

Exemples
La température est décrite par les adjectifs chaud, froid, moyen, et
chaud > moyen > froid
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut de type intervalle
Les intervalles impliquent une notion d’ordre, et les valeurs sont
mesurées dans des unités spécifiques et fixées
La somme, la différence et le produit de deux intervalles ne sont
pas possibles.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut de type intervalle
Les intervalles impliquent une notion d’ordre, et les valeurs sont
mesurées dans des unités spécifiques et fixées
La somme, la différence et le produit de deux intervalles ne sont
pas possibles.

Exemples
La température exprimée en degrés Celsius ou Fahrenheit
L’attribut année : (2000,2010,2014).
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut de type intervalle
Les intervalles impliquent une notion d’ordre, et les valeurs sont
mesurées dans des unités spécifiques et fixées
La somme, la différence et le produit de deux intervalles ne sont
pas possibles.

Exemples
La température exprimée en degrés Celsius ou Fahrenheit
L’attribut année : (2000,2010,2014).
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut de type intervalle
Les intervalles impliquent une notion d’ordre, et les valeurs sont
mesurées dans des unités spécifiques et fixées
La somme, la différence et le produit de deux intervalles ne sont
pas possibles.

Exemples
La température exprimée en degrés Celsius ou Fahrenheit
L’attribut année : (2000,2010,2014).
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut de type rapport (ratio)
Toutes les opérations mathématiques sont autorisées sur les
attributs de ce type.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut de type rapport (ratio)
Toutes les opérations mathématiques sont autorisées sur les
attributs de ce type.

Exemples
L’attribut distance :
On peut comparer deux distances.
On peut additionner deux distances.
La distance entre un objet et lui-même est zéro.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut de type rapport (ratio)
Toutes les opérations mathématiques sont autorisées sur les
attributs de ce type.

Exemples
L’attribut distance :
On peut comparer deux distances.
On peut additionner deux distances.
La distance entre un objet et lui-même est zéro.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Natures d’attributs
La valeur d’un attribut est censée représenter une certaine mesure d’une
quantitée
Attribut de type rapport (ratio)
Toutes les opérations mathématiques sont autorisées sur les
attributs de ce type.

Exemples
L’attribut distance :
On peut comparer deux distances.
On peut additionner deux distances.
La distance entre un objet et lui-même est zéro.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Classification supervisée

On dispose d’un ensemble X de N exemples, i.e. des couples (donnée,

étiquette). Chaque donnée xi ∈ D est caractérisée par P attributs et par
sa classe yi ∈ Y .

Définition
Dans un problème de classification supervisée, la classe prend sa valeur
parmi un ensemble Y fini. Le problème consiste alors, en s’appuyant sur
l’ensemble d’exemples X = (xi , yi ) i ∈ {1 . . . N }, à prédire la classe de
toute nouvelle donnée x ∈ D.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Classification supervisée

Remarque :
On parle de classification binaire quand le nombre de classes yi est
deux .
Il peut naturellement être quelconque. Dans tous les cas, il s’agît
d’un attribut qualitatif pouvant prendre un nombre fini de valeurs.
Dans l’absolu, une donnée peut appartenir à plusieurs classes :
c’est alors un problème multi-classes.
Ici, on considère que chaque donnée appartient à une et une seule
classe.
On utilise le mot étiquette comme synonyme de classe.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Classification supervisée

Remarque :
On parle de classification binaire quand le nombre de classes yi est
deux .
Il peut naturellement être quelconque. Dans tous les cas, il s’agît
d’un attribut qualitatif pouvant prendre un nombre fini de valeurs.
Dans l’absolu, une donnée peut appartenir à plusieurs classes :
c’est alors un problème multi-classes.
Ici, on considère que chaque donnée appartient à une et une seule
classe.
On utilise le mot étiquette comme synonyme de classe.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Classification supervisée

Remarque :
On parle de classification binaire quand le nombre de classes yi est
deux .
Il peut naturellement être quelconque. Dans tous les cas, il s’agît
d’un attribut qualitatif pouvant prendre un nombre fini de valeurs.
Dans l’absolu, une donnée peut appartenir à plusieurs classes :
c’est alors un problème multi-classes.
Ici, on considère que chaque donnée appartient à une et une seule
classe.
On utilise le mot étiquette comme synonyme de classe.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Classification supervisée

Remarque :
On parle de classification binaire quand le nombre de classes yi est
deux .
Il peut naturellement être quelconque. Dans tous les cas, il s’agît
d’un attribut qualitatif pouvant prendre un nombre fini de valeurs.
Dans l’absolu, une donnée peut appartenir à plusieurs classes :
c’est alors un problème multi-classes.
Ici, on considère que chaque donnée appartient à une et une seule
classe.
On utilise le mot étiquette comme synonyme de classe.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Classification supervisée

Remarque :
On parle de classification binaire quand le nombre de classes yi est
deux .
Il peut naturellement être quelconque. Dans tous les cas, il s’agît
d’un attribut qualitatif pouvant prendre un nombre fini de valeurs.
Dans l’absolu, une donnée peut appartenir à plusieurs classes :
c’est alors un problème multi-classes.
Ici, on considère que chaque donnée appartient à une et une seule
classe.
On utilise le mot étiquette comme synonyme de classe.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Classification supervisée
Définition
Un classifieur est une procédure (un algorithme) qui, à partir d’un
ensemble d’exemples, produit une prédiction de la classe de toute donnée.

Remarque :
D’une manière générale, un classifieur procède par induction : à
partir d’exemples (donc de cas particuliers), on construit une
connaissance plus générale.
Parmi les modèles, on distingue ceux qui peuvent être interprétés
par un humain (arbre de décision ) et ceux qui ne le peuvent pas
(réseau de neurones).
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Classification supervisée
Définition
Un classifieur est une procédure (un algorithme) qui, à partir d’un
ensemble d’exemples, produit une prédiction de la classe de toute donnée.

Remarque :
D’une manière générale, un classifieur procède par induction : à
partir d’exemples (donc de cas particuliers), on construit une
connaissance plus générale.
Parmi les modèles, on distingue ceux qui peuvent être interprétés
par un humain (arbre de décision ) et ceux qui ne le peuvent pas
(réseau de neurones).
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Classification supervisée

Plusieurs problèmes sont à résoudre :

Méthode d’induction du classeur ?
Comment utiliser le classifieur obtenu ?
Comment évaluer la qualité du classeur obtenu : taux d’erreur (ou de
succés) ?
Comment traiter les attributs manquants dans le jeu d’apprentissage ?
Comment traiter les attributs manquants dans une donnée à classer ?

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Classification supervisée

Plusieurs problèmes sont à résoudre :

Méthode d’induction du classeur ?
Comment utiliser le classifieur obtenu ?
Comment évaluer la qualité du classeur obtenu : taux d’erreur (ou de
succés) ?
Comment traiter les attributs manquants dans le jeu d’apprentissage ?
Comment traiter les attributs manquants dans une donnée à classer ?

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Classification supervisée

Plusieurs problèmes sont à résoudre :

Méthode d’induction du classeur ?
Comment utiliser le classifieur obtenu ?
Comment évaluer la qualité du classeur obtenu : taux d’erreur (ou de
succés) ?
Comment traiter les attributs manquants dans le jeu d’apprentissage ?
Comment traiter les attributs manquants dans une donnée à classer ?

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Classification supervisée

Plusieurs problèmes sont à résoudre :

Méthode d’induction du classeur ?
Comment utiliser le classifieur obtenu ?
Comment évaluer la qualité du classeur obtenu : taux d’erreur (ou de
succés) ?
Comment traiter les attributs manquants dans le jeu d’apprentissage ?
Comment traiter les attributs manquants dans une donnée à classer ?

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Classification supervisée

Plusieurs problèmes sont à résoudre :

Méthode d’induction du classeur ?
Comment utiliser le classifieur obtenu ?
Comment évaluer la qualité du classeur obtenu : taux d’erreur (ou de
succés) ?
Comment traiter les attributs manquants dans le jeu d’apprentissage ?
Comment traiter les attributs manquants dans une donnée à classer ?

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Arbres de décision

On se donne :
un ensemble X de N exemples notés xi dont les P attributs sont
quantitatifs ou qualitatifs.
Chaque exemple x est étiqueté, c’est-à-dire qu’il lui est associée une
classe ou un attribut cible que l’on note y ∈ Y.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Arbres de décision

On se donne :
un ensemble X de N exemples notés xi dont les P attributs sont
quantitatifs ou qualitatifs.
Chaque exemple x est étiqueté, c’est-à-dire qu’il lui est associée une
classe ou un attribut cible que l’on note y ∈ Y.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Arbres de décision

Définition
A partir de ces exemples, on construit un arbre dit de décision tel
que :
Chaque noeud correspond à un test sur la valeur d’un ou plusieurs
attributs ;
Chaque branche partant d’un noeud correspond à une ou plusieurs
valeurs de ce test ;
A chaque feuille est associée une valeur de l’attribut cible.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Arbres de décision

Définition
A partir de ces exemples, on construit un arbre dit de décision tel
que :
Chaque noeud correspond à un test sur la valeur d’un ou plusieurs
attributs ;
Chaque branche partant d’un noeud correspond à une ou plusieurs
valeurs de ce test ;
A chaque feuille est associée une valeur de l’attribut cible.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Arbres de décision

Définition
A partir de ces exemples, on construit un arbre dit de décision tel
que :
Chaque noeud correspond à un test sur la valeur d’un ou plusieurs
attributs ;
Chaque branche partant d’un noeud correspond à une ou plusieurs
valeurs de ce test ;
A chaque feuille est associée une valeur de l’attribut cible.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Arbres de décision

Construction de l’arbre
Plusieurs algorithmes ont été proposés, notamment :
CART proposé par Breiman dans les années 1980 .
ID3 de Quinlan proposé en 1986 qui a été raffiné par la suite
(C4.5 puis C5) .

ID3 ne prend en compte que des attributs nominaux.

Son successeur, C4.5, prend également en charge des attributs
quantitatifs.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Arbres de décision

Construction de l’arbre
Plusieurs algorithmes ont été proposés, notamment :
CART proposé par Breiman dans les années 1980 .
ID3 de Quinlan proposé en 1986 qui a été raffiné par la suite
(C4.5 puis C5) .

ID3 ne prend en compte que des attributs nominaux.

Son successeur, C4.5, prend également en charge des attributs
quantitatifs.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Arbres de décision

Construction de l’arbre
Plusieurs algorithmes ont été proposés, notamment :
CART proposé par Breiman dans les années 1980 .
ID3 de Quinlan proposé en 1986 qui a été raffiné par la suite
(C4.5 puis C5) .

ID3 ne prend en compte que des attributs nominaux.

Son successeur, C4.5, prend également en charge des attributs
quantitatifs.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Arbres de décision

Construction de l’arbre
Plusieurs algorithmes ont été proposés, notamment :
CART proposé par Breiman dans les années 1980 .
ID3 de Quinlan proposé en 1986 qui a été raffiné par la suite
(C4.5 puis C5) .

ID3 ne prend en compte que des attributs nominaux.

Son successeur, C4.5, prend également en charge des attributs
quantitatifs.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Les tests placés dans un noeud par l’algorithme ID3 concernent

exclusivement le test de la valeur d’un et seul attribut.
ID3 fonctionne récursivement :
Il détermine un attribut à placer en racine de l’arbre.
Cette racine possède autant de branches que cet attribut prend de valeurs.
A chaque branche est associé un ensemble d’exemples dont l’attribut prend la
valeur qui étiquette cette branche ;
On accroche alors au bout de cette branche l’arbre de décision construit sur ce
sous-ensemble des exemples et en considérant tous les attributs excepté celui qui
vient d’être mis à la racine.
Par cette procédure, l’ensemble des exemples ainsi que l’ensemble des attributs
diminuent petit à petit au long de la descente dans l’arbre.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Les tests placés dans un noeud par l’algorithme ID3 concernent

exclusivement le test de la valeur d’un et seul attribut.
ID3 fonctionne récursivement :
Il détermine un attribut à placer en racine de l’arbre.
Cette racine possède autant de branches que cet attribut prend de valeurs.
A chaque branche est associé un ensemble d’exemples dont l’attribut prend la
valeur qui étiquette cette branche ;
On accroche alors au bout de cette branche l’arbre de décision construit sur ce
sous-ensemble des exemples et en considérant tous les attributs excepté celui qui
vient d’être mis à la racine.
Par cette procédure, l’ensemble des exemples ainsi que l’ensemble des attributs
diminuent petit à petit au long de la descente dans l’arbre.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Les tests placés dans un noeud par l’algorithme ID3 concernent

exclusivement le test de la valeur d’un et seul attribut.
ID3 fonctionne récursivement :
Il détermine un attribut à placer en racine de l’arbre.
Cette racine possède autant de branches que cet attribut prend de valeurs.
A chaque branche est associé un ensemble d’exemples dont l’attribut prend la
valeur qui étiquette cette branche ;
On accroche alors au bout de cette branche l’arbre de décision construit sur ce
sous-ensemble des exemples et en considérant tous les attributs excepté celui qui
vient d’être mis à la racine.
Par cette procédure, l’ensemble des exemples ainsi que l’ensemble des attributs
diminuent petit à petit au long de la descente dans l’arbre.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Les tests placés dans un noeud par l’algorithme ID3 concernent

exclusivement le test de la valeur d’un et seul attribut.
ID3 fonctionne récursivement :
Il détermine un attribut à placer en racine de l’arbre.
Cette racine possède autant de branches que cet attribut prend de valeurs.
A chaque branche est associé un ensemble d’exemples dont l’attribut prend la
valeur qui étiquette cette branche ;
On accroche alors au bout de cette branche l’arbre de décision construit sur ce
sous-ensemble des exemples et en considérant tous les attributs excepté celui qui
vient d’être mis à la racine.
Par cette procédure, l’ensemble des exemples ainsi que l’ensemble des attributs
diminuent petit à petit au long de la descente dans l’arbre.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Les tests placés dans un noeud par l’algorithme ID3 concernent

exclusivement le test de la valeur d’un et seul attribut.
ID3 fonctionne récursivement :
Il détermine un attribut à placer en racine de l’arbre.
Cette racine possède autant de branches que cet attribut prend de valeurs.
A chaque branche est associé un ensemble d’exemples dont l’attribut prend la
valeur qui étiquette cette branche ;
On accroche alors au bout de cette branche l’arbre de décision construit sur ce
sous-ensemble des exemples et en considérant tous les attributs excepté celui qui
vient d’être mis à la racine.
Par cette procédure, l’ensemble des exemples ainsi que l’ensemble des attributs
diminuent petit à petit au long de la descente dans l’arbre.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Les tests placés dans un noeud par l’algorithme ID3 concernent

exclusivement le test de la valeur d’un et seul attribut.
ID3 fonctionne récursivement :
Il détermine un attribut à placer en racine de l’arbre.
Cette racine possède autant de branches que cet attribut prend de valeurs.
A chaque branche est associé un ensemble d’exemples dont l’attribut prend la
valeur qui étiquette cette branche ;
On accroche alors au bout de cette branche l’arbre de décision construit sur ce
sous-ensemble des exemples et en considérant tous les attributs excepté celui qui
vient d’être mis à la racine.
Par cette procédure, l’ensemble des exemples ainsi que l’ensemble des attributs
diminuent petit à petit au long de la descente dans l’arbre.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Les tests placés dans un noeud par l’algorithme ID3 concernent

exclusivement le test de la valeur d’un et seul attribut.
ID3 fonctionne récursivement :
Il détermine un attribut à placer en racine de l’arbre.
Cette racine possède autant de branches que cet attribut prend de valeurs.
A chaque branche est associé un ensemble d’exemples dont l’attribut prend la
valeur qui étiquette cette branche ;
On accroche alors au bout de cette branche l’arbre de décision construit sur ce
sous-ensemble des exemples et en considérant tous les attributs excepté celui qui
vient d’être mis à la racine.
Par cette procédure, l’ensemble des exemples ainsi que l’ensemble des attributs
diminuent petit à petit au long de la descente dans l’arbre.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Ayant l’idée de l’algorithme, il reste à résoudre une question centrale :

quel attribut placer en racine ?
Une fois cette question résolue, on itérera le raisonnement pour les
sous-arbres.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Ayant l’idée de l’algorithme, il reste à résoudre une question centrale :

quel attribut placer en racine ?
Une fois cette question résolue, on itérera le raisonnement pour les
sous-arbres.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Ayant l’idée de l’algorithme, il reste à résoudre une question centrale :

quel attribut placer en racine ?
Une fois cette question résolue, on itérera le raisonnement pour les
sous-arbres.
On tente de réduire l’hétérogénéïté à chaque noeud :
Les données qui atteignent un certain noeud de l’arbre de décision
doivent être plus homogènes que les données atteignant un noeud
ancêtre.
Pour cela, on a besoin de pouvoir mesurer l’homogénéïté d’un
ensemble de données.
En physique, on mesure l’homogénéïté par l’entropie.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Ayant l’idée de l’algorithme, il reste à résoudre une question centrale :

quel attribut placer en racine ?
Une fois cette question résolue, on itérera le raisonnement pour les
sous-arbres.
On tente de réduire l’hétérogénéïté à chaque noeud :
Les données qui atteignent un certain noeud de l’arbre de décision
doivent être plus homogènes que les données atteignant un noeud
ancêtre.
Pour cela, on a besoin de pouvoir mesurer l’homogénéïté d’un
ensemble de données.
En physique, on mesure l’homogénéïté par l’entropie.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Ayant l’idée de l’algorithme, il reste à résoudre une question centrale :

quel attribut placer en racine ?
Une fois cette question résolue, on itérera le raisonnement pour les
sous-arbres.
On tente de réduire l’hétérogénéïté à chaque noeud :
Les données qui atteignent un certain noeud de l’arbre de décision
doivent être plus homogènes que les données atteignant un noeud
ancêtre.
Pour cela, on a besoin de pouvoir mesurer l’homogénéïté d’un
ensemble de données.
En physique, on mesure l’homogénéïté par l’entropie.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3
Entropie
Soit un ensemble X d’exemples dont une proportion p+ sont positifs et
une proportion p− sont négatifs. (Bien entendu, p+ + p− = 1.) L’entropie
de X est :
H(X ) = −p+ log2 (p+ ) − p− log2 (p− )
 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3
Entropie
Soit un ensemble X d’exemples dont une proportion p+ sont positifs et
une proportion p− sont négatifs. (Bien entendu, p+ + p− = 1.) L’entropie
de X est :
H(X ) = −p+ log2 (p+ ) − p− log2 (p− )

Remarque :
1 0 ≤ H(X ) ≤ 1 ;
2 Si p+ = 0 ou p− = 0, alors H(X ) = 0 : ainsi, si tous exemples sont
soit tous positifs, soit tous négatifs, l’entropie est nulle ;
3 Si p+ = p− = 0.5, alors H(X ) = 1 : ainsi, s’il y a autant de positifs
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3
Entropie
Soit un ensemble X d’exemples dont une proportion p+ sont positifs et
une proportion p− sont négatifs. (Bien entendu, p+ + p− = 1.) L’entropie
de X est :
H(X ) = −p+ log2 (p+ ) − p− log2 (p− )

Remarque :
1 0 ≤ H(X ) ≤ 1 ;
2 Si p+ = 0 ou p− = 0, alors H(X ) = 0 : ainsi, si tous exemples sont
soit tous positifs, soit tous négatifs, l’entropie est nulle ;
3 Si p+ = p− = 0.5, alors H(X ) = 1 : ainsi, s’il y a autant de positifs
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3
Entropie
Soit un ensemble X d’exemples dont une proportion p+ sont positifs et
une proportion p− sont négatifs. (Bien entendu, p+ + p− = 1.) L’entropie
de X est :
H(X ) = −p+ log2 (p+ ) − p− log2 (p− )

Remarque :
1 0 ≤ H(X ) ≤ 1 ;
2 Si p+ = 0 ou p− = 0, alors H(X ) = 0 : ainsi, si tous exemples sont
soit tous positifs, soit tous négatifs, l’entropie est nulle ;
3 Si p+ = p− = 0.5, alors H(X ) = 1 : ainsi, s’il y a autant de positifs
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

La définition précédente de l’entropie se généralise aisément à un attribut

pouvant prendre plus de deux valeurs distinctes :

Définition
Pour une classe prenant n valeurs distinctes (numérotées de 1 à n) , no-
tons pi la proportion d’exemples dont la valeur de cet attribut est i dans
l’ensemble d’exemples considéré X . L’entropie de l’ensemble d’exemples
X est : n X
H(X ) = − pi log2 (pi )
i=1

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Remarque :
Avoir des sous-sensembles dont l’entropie est minimale est
intéressant : cela signifie que l’attribut placer à la racine discrimine
les exemples en fonction de leur classe.
Il est naturel de sommer ces entropies en les pondérant en fonction
de la proportion d’exemples dans chacun des sous-ensembles.
Voulant sélectionner l’attribut discriminant au mieux, on peut
utiliser la différence entre l’entropie de l’ensemble d’exemples initial
(utilisé pour déterminer la racine) et cette somme pondérée pour
trouver l’attribut le plus intéressant à placer dans la racine.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Remarque :
Avoir des sous-sensembles dont l’entropie est minimale est
intéressant : cela signifie que l’attribut placer à la racine discrimine
les exemples en fonction de leur classe.
Il est naturel de sommer ces entropies en les pondérant en fonction
de la proportion d’exemples dans chacun des sous-ensembles.
Voulant sélectionner l’attribut discriminant au mieux, on peut
utiliser la différence entre l’entropie de l’ensemble d’exemples initial
(utilisé pour déterminer la racine) et cette somme pondérée pour
trouver l’attribut le plus intéressant à placer dans la racine.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Remarque :
Avoir des sous-sensembles dont l’entropie est minimale est
intéressant : cela signifie que l’attribut placer à la racine discrimine
les exemples en fonction de leur classe.
Il est naturel de sommer ces entropies en les pondérant en fonction
de la proportion d’exemples dans chacun des sous-ensembles.
Voulant sélectionner l’attribut discriminant au mieux, on peut
utiliser la différence entre l’entropie de l’ensemble d’exemples initial
(utilisé pour déterminer la racine) et cette somme pondérée pour
trouver l’attribut le plus intéressant à placer dans la racine.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Remarque :
L’attribut qui maximise cette différence est l’attribut qui
discrimine le mieux les exemples en fonction de leur classe.
Cette différence porte le nom de gain d’information.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3
Gain d’information
Soit une population d’exemples X . Le gain d’information de X par
rapport à un attribut aj donné est la variation d’entropie causée par la
partition de X selon aj :
 
Xaj =v 
 
X
Gain(X , aj ) = H(X ) − H(Xaj =v )
v∈valeurs(aj )
|X |

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3
Gain d’information
Soit une population d’exemples X . Le gain d’information de X par
rapport à un attribut aj donné est la variation d’entropie causée par la
partition de X selon aj :
 
Xaj =v 
 
X
Gain(X , aj ) = H(X ) − H(Xaj =v )
v∈valeurs(aj )
|X |

où
Xaj =v ⊂ X est l’ensemble des exemples dont l’attribut considéré aj
prend la valeur v,
La notation |X | indique le cardinal de l’ensemble X .
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3
Gain d’information
Soit une population d’exemples X . Le gain d’information de X par
rapport à un attribut aj donné est la variation d’entropie causée par la
partition de X selon aj :
 
Xaj =v 
 
X
Gain(X , aj ) = H(X ) − H(Xaj =v )
v∈valeurs(aj )
|X |

où
Xaj =v ⊂ X est l’ensemble des exemples dont l’attribut considéré aj
prend la valeur v,
La notation |X | indique le cardinal de l’ensemble X .
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Exemple :
Supposons que X soit constitué de 14 exemples, 9 positifs et 5 négatifs.
Parmi ces exemples, 6 positifs et 2 négatifs prennent la valeur oui
pour l’attribut a, tandis que les autres exemples prennent la valeur
non pour cet attribut.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Exemple :
Supposons que X soit constitué de 14 exemples, 9 positifs et 5 négatifs.
Parmi ces exemples, 6 positifs et 2 négatifs prennent la valeur oui
pour l’attribut a, tandis que les autres exemples prennent la valeur
non pour cet attribut.
X |Xa=v |
Gain(X , a) = H(X ) − H(Xa=v )
v∈{oui,non}
|X |

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Exemple :
Supposons que X soit constitué de 14 exemples, 9 positifs et 5 négatifs.
Parmi ces exemples, 6 positifs et 2 négatifs prennent la valeur oui
pour l’attribut a, tandis que les autres exemples prennent la valeur
non pour cet attribut.
8 6
Gain(X , a) = H(X ) − H(Xa=oui ) − H(Xa=non )
14 14

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Exemple :
Supposons que X soit constitué de 14 exemples, 9 positifs et 5 négatifs.
Parmi ces exemples, 6 positifs et 2 négatifs prennent la valeur oui
pour l’attribut a, tandis que les autres exemples prennent la valeur
non pour cet attribut.
8 6
Gain(X , a) = H(X ) − H(Xa=oui ) − H(Xa=non )
14 14
6 6 2 2
 
H(Xa=oui ) = − log2 + log2 ≈ 0.811
8 8 8 8

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Exemple :
Supposons que X soit constitué de 14 exemples, 9 positifs et 5 négatifs.
Parmi ces exemples, 6 positifs et 2 négatifs prennent la valeur oui
pour l’attribut a, tandis que les autres exemples prennent la valeur
non pour cet attribut.
8 6
Gain(X , a) = H(X ) − H(Xa=oui ) − H(Xa=non )
14 14
6 6 2 2
 
H(Xa=oui ) = − log2 + log2 ≈ 0.811
8 8 8 8
3 3 3 3
 
H(Xa=non ) = − log2 + log2 = 1.0
6 6 6 6

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Exemple :
Supposons que X soit constitué de 14 exemples, 9 positifs et 5 négatifs.
Parmi ces exemples, 6 positifs et 2 négatifs prennent la valeur oui
pour l’attribut a, tandis que les autres exemples prennent la valeur
non pour cet attribut.
8 6
Gain(X , a) = H(X ) − H(Xa=oui ) − H(Xa=non )
14 14
8 6
Gain(X , a) ≈ 0.940 − 0.811 − ≈ 0.048
14 14

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Entrées : ensemble d’exemples X , ensemble d’attributs A

Sorties : racine d’un noeud de l’arbre de décision
1 Créer un noeud racine;
2 si tous les élements de X sont positifs alors
3 racine. étiquette ← ⊕;
4 retourner racine;
5 si tous les élements de X sont négatifs alors
6 racine. étiquette ← ;
7 retourner racine;
8 si A = ∅ alors
9 racine. étiquette ← valeur la plus présente de la classe parmi les X ;
10 retourner racine;
..
11 .

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Entrées : ensemble d’exemples X , ensemble d’attributs A

Sorties : racine d’un noeud de l’arbre de décision
1 Créer un noeud racine;
2 si tous les élements de X sont positifs alors
3 racine. étiquette ← ⊕;
4 retourner racine;
5 si tous les élements de X sont négatifs alors
6 racine. étiquette ← ;
7 retourner racine;
8 si A = ∅ alors
9 racine. étiquette ← valeur la plus présente de la classe parmi les X ;
10 retourner racine;
..
11 .

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Entrées : ensemble d’exemples X , ensemble d’attributs A

Sorties : racine d’un noeud de l’arbre de décision
1 Créer un noeud racine;
2 si tous les élements de X sont positifs alors
3 racine. étiquette ← ⊕;
4 retourner racine;
5 si tous les élements de X sont négatifs alors
6 racine. étiquette ← ;
7 retourner racine;
8 si A = ∅ alors
9 racine. étiquette ← valeur la plus présente de la classe parmi les X ;
10 retourner racine;
..
11 .

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Entrées : ensemble d’exemples X , ensemble d’attributs A

Sorties : racine d’un noeud de l’arbre de décision
1 Créer un noeud racine;
2 si tous les élements de X sont positifs alors
3 racine. étiquette ← ⊕;
4 retourner racine;
5 si tous les élements de X sont négatifs alors
6 racine. étiquette ← ;
7 retourner racine;
8 si A = ∅ alors
9 racine. étiquette ← valeur la plus présente de la classe parmi les X ;
10 retourner racine;
..
11 .

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Entrées : ensemble d’exemples X , ensemble d’attributs A

Sorties : racine d’un noeud de l’arbre de décision
1 Créer un noeud racine;
2 si tous les élements de X sont positifs alors
3 racine. étiquette ← ⊕;
4 retourner racine;
5 si tous les élements de X sont négatifs alors
6 racine. étiquette ← ;
7 retourner racine;
8 si A = ∅ alors
9 racine. étiquette ← valeur la plus présente de la classe parmi les X ;
10 retourner racine;
..
11 .

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Entrées : ensemble d’exemples X , ensemble d’attributs A

Sorties : racine d’un noeud de l’arbre de décision
1 Créer un noeud racine;
2 si tous les élements de X sont positifs alors
3 racine. étiquette ← ⊕;
4 retourner racine;
5 si tous les élements de X sont négatifs alors
6 racine. étiquette ← ;
7 retourner racine;
8 si A = ∅ alors
9 racine. étiquette ← valeur la plus présente de la classe parmi les X ;
10 retourner racine;
..
11 .

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Entrées : ensemble d’exemples X , ensemble d’attributs A

Sorties : racine d’un noeud de l’arbre de décision
..
1 .
2 a∗ ← arg maxa∈A Gain(X , a) ;
3 racine. étiquette ← a∗ ;
4 pour toutes les valeurs vi de a∗ faire
5 ajouter une branche à racine correspondant à la valeur vi ;
6 former Xa∗ =vi ⊆ X dont l’attribut a∗ vaut vi ;
7 si Xa∗ =vi = ∅ alors
8 a l’extrémité de cette branche, mettre une feuille étiquetée avec la
valeur la plus présente de la classe parmi les X ;
9 sinon
10 a l’extrémité de cette branche, mettre ID3(Xa∗ =vi , A − a∗ );
11 retourner racine;

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Entrées : ensemble d’exemples X , ensemble d’attributs A

Sorties : racine d’un noeud de l’arbre de décision
..
1 .
2 a∗ ← arg maxa∈A Gain(X , a) ;
3 racine. étiquette ← a∗ ;
4 pour toutes les valeurs vi de a∗ faire
5 ajouter une branche à racine correspondant à la valeur vi ;
6 former Xa∗ =vi ⊆ X dont l’attribut a∗ vaut vi ;
7 si Xa∗ =vi = ∅ alors
8 a l’extrémité de cette branche, mettre une feuille étiquetée avec la
valeur la plus présente de la classe parmi les X ;
9 sinon
10 a l’extrémité de cette branche, mettre ID3(Xa∗ =vi , A − a∗ );
11 retourner racine;

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Entrées : ensemble d’exemples X , ensemble d’attributs A

Sorties : racine d’un noeud de l’arbre de décision
..
1 .
2 a∗ ← arg maxa∈A Gain(X , a) ;
3 racine. étiquette ← a∗ ;
4 pour toutes les valeurs vi de a∗ faire
5 ajouter une branche à racine correspondant à la valeur vi ;
6 former Xa∗ =vi ⊆ X dont l’attribut a∗ vaut vi ;
7 si Xa∗ =vi = ∅ alors
8 a l’extrémité de cette branche, mettre une feuille étiquetée avec la
valeur la plus présente de la classe parmi les X ;
9 sinon
10 a l’extrémité de cette branche, mettre ID3(Xa∗ =vi , A − a∗ );
11 retourner racine;

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Entrées : ensemble d’exemples X , ensemble d’attributs A

Sorties : racine d’un noeud de l’arbre de décision
..
1 .
2 a∗ ← arg maxa∈A Gain(X , a) ;
3 racine. étiquette ← a∗ ;
4 pour toutes les valeurs vi de a∗ faire
5 ajouter une branche à racine correspondant à la valeur vi ;
6 former Xa∗ =vi ⊆ X dont l’attribut a∗ vaut vi ;
7 si Xa∗ =vi = ∅ alors
8 a l’extrémité de cette branche, mettre une feuille étiquetée avec la
valeur la plus présente de la classe parmi les X ;
9 sinon
10 a l’extrémité de cette branche, mettre ID3(Xa∗ =vi , A − a∗ );
11 retourner racine;

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Entrées : ensemble d’exemples X , ensemble d’attributs A

Sorties : racine d’un noeud de l’arbre de décision
..
1 .
2 a∗ ← arg maxa∈A Gain(X , a) ;
3 racine. étiquette ← a∗ ;
4 pour toutes les valeurs vi de a∗ faire
5 ajouter une branche à racine correspondant à la valeur vi ;
6 former Xa∗ =vi ⊆ X dont l’attribut a∗ vaut vi ;
7 si Xa∗ =vi = ∅ alors
8 a l’extrémité de cette branche, mettre une feuille étiquetée avec la
valeur la plus présente de la classe parmi les X ;
9 sinon
10 a l’extrémité de cette branche, mettre ID3(Xa∗ =vi , A − a∗ );
11 retourner racine;

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Entrées : ensemble d’exemples X , ensemble d’attributs A

Sorties : racine d’un noeud de l’arbre de décision
..
1 .
2 a∗ ← arg maxa∈A Gain(X , a) ;
3 racine. étiquette ← a∗ ;
4 pour toutes les valeurs vi de a∗ faire
5 ajouter une branche à racine correspondant à la valeur vi ;
6 former Xa∗ =vi ⊆ X dont l’attribut a∗ vaut vi ;
7 si Xa∗ =vi = ∅ alors
8 a l’extrémité de cette branche, mettre une feuille étiquetée avec la
valeur la plus présente de la classe parmi les X ;
9 sinon
10 a l’extrémité de cette branche, mettre ID3(Xa∗ =vi , A − a∗ );
11 retourner racine;

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3

Entrées : ensemble d’exemples X , ensemble d’attributs A

Sorties : racine d’un noeud de l’arbre de décision
..
1 .
2 a∗ ← arg maxa∈A Gain(X , a) ;
3 racine. étiquette ← a∗ ;
4 pour toutes les valeurs vi de a∗ faire
5 ajouter une branche à racine correspondant à la valeur vi ;
6 former Xa∗ =vi ⊆ X dont l’attribut a∗ vaut vi ;
7 si Xa∗ =vi = ∅ alors
8 a l’extrémité de cette branche, mettre une feuille étiquetée avec la
valeur la plus présente de la classe parmi les X ;
9 sinon
10 a l’extrémité de cette branche, mettre ID3(Xa∗ =vi , A − a∗ );
11 retourner racine;

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

On considère l’ensemble exemplees suivant. L’attribut cible est donc
“Jouer au tennis ?”
Jour Ciel Température Humidité Vent Jouer au tennis ?
1 Ensoleillé Chaude Elevée Faible Non
2 Ensoleillé Chaude Elevée Fort Non
3 Couvert Chaude Elevée Faible Oui
4 Pluie Tiède Elevée Faible Oui
5 Pluie Fraîche Normale Faible Oui
6 Pluie Fraîche Normale Fort Non
7 Couvert Fraîche Normale Fort Oui
8 Ensoleillé Tiède Elevée Faible Non
9 Ensoleillé Fraîche Normale Faible Oui
10 Pluie Tiède Normale Faible Oui
11 Ensoleillé Tiède Normale Fort Oui
12 Couvert Tiède Elevée Fort Oui
13 Couvert Chaude Normale Faible Oui
14 Pluie Tiède Elevée Fort Non

Table – Jeu de données jouer au tennis ?

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Attribut Gain
Ciel 0.246

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Attribut Gain
Ciel 0.246
Humidité 0.151

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Attribut Gain
Ciel 0.246
Humidité 0.151
Vent 0.048

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Attribut Gain
Ciel 0.246
Humidité 0.151
Vent 0.048
Tempétarure 0.029

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?
Attribut Gain
Ciel 0.246
Humidité 0.151
Vent 0.048
Tempétarure 0.029

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?

Attribut Gain
Humidité 0.970

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?

Attribut Gain
Humidité 0.970
Tempétarure 0.570

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?

Attribut Gain
Humidité 0.970
Tempétarure 0.570
Vent 0.019

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?

Attribut Gain Ensoleillé

Humidité 0.970
Tempétarure 0.570 Humidité ?
Vent 0.019

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?

Ensoleillé

Humidité ?

Elevée

Non

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?

Ensoleillé

Humidité ?

Elevée Normale

Non oui

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?

Ensoleillé Couvert

Humidité ?
Oui
Elevée Normale

Non oui

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?

Attribut Gain Ensoleillé Couvert

Vent 0.970
Humidité ?
Oui
Elevée Normale

Non oui

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?

Attribut Gain Ensoleillé Couvert

Vent 0.970
Humidité 0.0.019 Humidité ?
Oui
Elevée Normale

Non oui

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?

Attribut Gain Ensoleillé Couvert

Vent 0.970
Humidité 0.0.019 Humidité ?
Tempétarure 0.019 Oui
Elevée Normale

Non oui

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?

Attribut Gain Ensoleillé Pluie

Couvert
Vent 0.970
Humidité 0.0.019 Humidité ? Vent ?
Tempétarure 0.019 Oui
Elevée Normale

Non oui

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?

Ensoleillé Couvert Pluie

Humidité ? Vent ?
Oui
Elevée Normale Fort

Non oui Non

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Algorithme ID3 : Déroulement

Ciel ?

Ensoleillé Couvert Pluie

Humidité ? Vent ?
Oui
Elevée Normale Fort Faible

Non oui Non oui

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Ensemble d’Apprentissage, de Test et de Validation

La tâche de classification repose sur la disponibilité d’un corpus initial
Ω = d1 , . . . , d|Ω| ⊂ D
de exemples pré-classifiés sous
C = {c1 , . . . , c|C| }
Les valeurs de la fonction Φ : D × C → {T, F } sont connues pour
chaque paire hdj , ci i.
Un exemples dj est un exemple positif de ci si
Φ (dj , ci ) = T
,
Un exemple négatif de ci si
Φ (dj , ci ) = F
. M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Ensemble d’Apprentissage, de Test et de Validation

La tâche de classification repose sur la disponibilité d’un corpus initial
Ω = d1 , . . . , d|Ω| ⊂ D
de exemples pré-classifiés sous
C = {c1 , . . . , c|C| }
Les valeurs de la fonction Φ : D × C → {T, F } sont connues pour
chaque paire hdj , ci i.
Un exemples dj est un exemple positif de ci si
Φ (dj , ci ) = T
,
Un exemple négatif de ci si
Φ (dj , ci ) = F
. M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Ensemble d’Apprentissage, de Test et de Validation

La tâche de classification repose sur la disponibilité d’un corpus initial
Ω = d1 , . . . , d|Ω| ⊂ D
de exemples pré-classifiés sous
C = {c1 , . . . , c|C| }
Les valeurs de la fonction Φ : D × C → {T, F } sont connues pour
chaque paire hdj , ci i.
Un exemples dj est un exemple positif de ci si
Φ (dj , ci ) = T
,
Un exemple négatif de ci si
Φ (dj , ci ) = F
. M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Ensemble d’Apprentissage, de Test et de Validation

La tâche de classification repose sur la disponibilité d’un corpus initial
Ω = d1 , . . . , d|Ω| ⊂ D
de exemples pré-classifiés sous
C = {c1 , . . . , c|C| }
Les valeurs de la fonction Φ : D × C → {T, F } sont connues pour
chaque paire hdj , ci i.
Un exemples dj est un exemple positif de ci si
Φ (dj , ci ) = T
,
Un exemple négatif de ci si
Φ (dj , ci ) = F
. M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Ensemble d’Apprentissage, de Test

Une fois qu’un classifieur Φ a été construit il est souhaitable d’évaluer

son efficacité.
Avant la construction du classifieur, le corpus initial est divisé en deux
séries, pas nécessairement de taille égale : un ensemble d’apprentissage
et un ensemble de test.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Ensemble d’Apprentissage, de Test

Une fois qu’un classifieur Φ a été construit il est souhaitable d’évaluer

son efficacité.
Avant la construction du classifieur, le corpus initial est divisé en deux
séries, pas nécessairement de taille égale : un ensemble d’apprentissage
et un ensemble de test.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Ensemble d’Apprentissage, de Test

Une fois qu’un classifieur Φ a été construit il est souhaitable d’évaluer

son efficacité.
Avant la construction du classifieur, le corpus initial est divisé en deux
séries, pas nécessairement de taille égale : un ensemble d’apprentissage
et un ensemble de test.

Ensemble d’apprentissage

EA = {d1 , . . . , d|EA| }
Le classifieur Φ pour les catégories C = {c1 , . . . , c|C| } est construit en
observant les caractéristiques de ces exemples.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Ensemble d’Apprentissage, de Test

Une fois qu’un classifieur Φ a été construit il est souhaitable d’évaluer
son efficacité.
Avant la construction du classifieur, le corpus initial est divisé en deux
séries, pas nécessairement de taille égale : un ensemble d’apprentissage
et un ensemble de test.

Ensemble de Test

ET = {d|EA+1| , . . . , d|Ω| }
Il est utilisé pour tester l’efficacité des classifieurs. Chaque dj ∈ ET est
donné au classifieur, et les décisions du classifieur Φ (dj , ci ) sont compa-
rées avec les décisions d’expert.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Ensemble d’Apprentissage, de Test

Remarque :
Les documents de ET ne peuvent pas participer d’une façon
quelconque à la construction d’induction du classement.
Si cette condition n’était satisfaite, les résultats expérimentaux
obtenus seraient probablement trop bons, et l’évaluation n’aurait
donc pas de caractère scientifique.
La validation est une phase indispensable à tout processus
d’apprentissage.
Elle consiste à vérifier que le modèle construit sur l’ensemble
d’apprentissage permet de classer tout individu avec le minimum
d’erreurs possible.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Ensemble d’Apprentissage, de Test

Remarque :
Les documents de ET ne peuvent pas participer d’une façon
quelconque à la construction d’induction du classement.
Si cette condition n’était satisfaite, les résultats expérimentaux
obtenus seraient probablement trop bons, et l’évaluation n’aurait
donc pas de caractère scientifique.
La validation est une phase indispensable à tout processus
d’apprentissage.
Elle consiste à vérifier que le modèle construit sur l’ensemble
d’apprentissage permet de classer tout individu avec le minimum
d’erreurs possible.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Ensemble d’Apprentissage, de Test

Remarque :
Les documents de ET ne peuvent pas participer d’une façon
quelconque à la construction d’induction du classement.
Si cette condition n’était satisfaite, les résultats expérimentaux
obtenus seraient probablement trop bons, et l’évaluation n’aurait
donc pas de caractère scientifique.
La validation est une phase indispensable à tout processus
d’apprentissage.
Elle consiste à vérifier que le modèle construit sur l’ensemble
d’apprentissage permet de classer tout individu avec le minimum
d’erreurs possible.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Ensemble d’Apprentissage, de Test

Remarque :
Les documents de ET ne peuvent pas participer d’une façon
quelconque à la construction d’induction du classement.
Si cette condition n’était satisfaite, les résultats expérimentaux
obtenus seraient probablement trop bons, et l’évaluation n’aurait
donc pas de caractère scientifique.
La validation est une phase indispensable à tout processus
d’apprentissage.
Elle consiste à vérifier que le modèle construit sur l’ensemble
d’apprentissage permet de classer tout individu avec le minimum
d’erreurs possible.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Ensemble de validation

Validation par test

les résultats de l’évaluation seraient une estimation pessimiste de la
performance réelle,
L’ensemble d’apprentissage permet de générer le modèle,
l’ensemble de test permet d’évaluer l’erreur réelle du modèle sur un
ensemble indépendant évitant ainsi un biais d’apprentissage.
S’il s’agit de tester plusieurs modèles et de les comparer, on peut
sélectionner le meilleur modèle selon ses performances sur
l’ensemble de validation et ensuite évaluer l’erreur réelle sur
l’ensemble de test.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Ensemble de validation

Validation par test

les résultats de l’évaluation seraient une estimation pessimiste de la
performance réelle,
L’ensemble d’apprentissage permet de générer le modèle,
l’ensemble de test permet d’évaluer l’erreur réelle du modèle sur un
ensemble indépendant évitant ainsi un biais d’apprentissage.
S’il s’agit de tester plusieurs modèles et de les comparer, on peut
sélectionner le meilleur modèle selon ses performances sur
l’ensemble de validation et ensuite évaluer l’erreur réelle sur
l’ensemble de test.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Ensemble de validation

Validation par test

les résultats de l’évaluation seraient une estimation pessimiste de la
performance réelle,
L’ensemble d’apprentissage permet de générer le modèle,
l’ensemble de test permet d’évaluer l’erreur réelle du modèle sur un
ensemble indépendant évitant ainsi un biais d’apprentissage.
S’il s’agit de tester plusieurs modèles et de les comparer, on peut
sélectionner le meilleur modèle selon ses performances sur
l’ensemble de validation et ensuite évaluer l’erreur réelle sur
l’ensemble de test.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Ensemble de validation
Validation Croisée
Les k différents classifieurs Φ1 , · · · , Φk sont construits par le
partitionnement initial du corpus en k ensembles disjoints
ET1 , · · · , ETk .
La validation par test est ensuite appliquée de façon itérative sur
les paires hEAi = Ω − ETi , ETi i .
L’efficacité finale est obtenue par le calcul individuel de l’efficacité
de Φ1 , · · · , Φk .
La validation croisée ne construit pas de modèle utilisable, elle
estime juste l’erreur réelle.
En général le nombre k de parties est fixé à 10.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Ensemble de validation
Validation Croisée
Les k différents classifieurs Φ1 , · · · , Φk sont construits par le
partitionnement initial du corpus en k ensembles disjoints
ET1 , · · · , ETk .
La validation par test est ensuite appliquée de façon itérative sur
les paires hEAi = Ω − ETi , ETi i .
L’efficacité finale est obtenue par le calcul individuel de l’efficacité
de Φ1 , · · · , Φk .
La validation croisée ne construit pas de modèle utilisable, elle
estime juste l’erreur réelle.
En général le nombre k de parties est fixé à 10.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité
L’efficacité de classification se mesure généralement par les paramètres
classiques du domaine de la recherche d’information :
La précision,
Le rappel.

Précision
La précision c’est un ratio entre le nombre de documents pertinents
trouvés et le nombre total de documents trouvés.
Elle mesure le bruit, et plus elle est proche de 100%, moins il y a
de bruit, et donc meilleure est la réponse.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité
L’efficacité de classification se mesure généralement par les paramètres
classiques du domaine de la recherche d’information :
La précision,
Le rappel.

Précision
La précision c’est un ratio entre le nombre de documents pertinents
trouvés et le nombre total de documents trouvés.
Elle mesure le bruit, et plus elle est proche de 100%, moins il y a
de bruit, et donc meilleure est la réponse.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité
L’efficacité de classification se mesure généralement par les paramètres
classiques du domaine de la recherche d’information :
La précision,
Le rappel.

Rappel
Le rappel est un ratio entre le nombre de documents pertinents
trouvés et le nombre de documents pertinents présents dans la base.
Plus il est proche de 100%, moins il y a de silence, et meilleure est
la réponse.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité
L’efficacité de classification se mesure généralement par les paramètres
classiques du domaine de la recherche d’information :
La précision,
Le rappel.

Rappel
Le rappel est un ratio entre le nombre de documents pertinents
trouvés et le nombre de documents pertinents présents dans la base.
Plus il est proche de 100%, moins il y a de silence, et meilleure est
la réponse.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité
Ces mésures peuvent être estimées par un tableau qui montre toutes les
possibilités d’un classifieur
Catégorie Classement de l’Expert
ci Vrai Faux
Jugement du Positif T Pi F Pi
Classifieur Négatif F Ni T Ni
F Pi : le nombre de documents de test mal classés dans la catégorie ci ,
T Ni : le nombre de documents bien classés qui n’appartiennent pas à
la catégorie ci ,
T Pi : le nombre de documents bien classés qui appartiennent à la
catégorie ci ,et
F Ni : le nombre de documents de catégorie ci non classés par le
classifieur.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité
Ces mésures peuvent être estimées par un tableau qui montre toutes les
possibilités d’un classifieur
Catégorie Classement de l’Expert
ci Vrai Faux
Jugement du Positif T Pi F Pi
Classifieur Négatif F Ni T Ni
F Pi : le nombre de documents de test mal classés dans la catégorie ci ,
T Ni : le nombre de documents bien classés qui n’appartiennent pas à
la catégorie ci ,
T Pi : le nombre de documents bien classés qui appartiennent à la
catégorie ci ,et
F Ni : le nombre de documents de catégorie ci non classés par le
classifieur.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité
Ces mésures peuvent être estimées par un tableau qui montre toutes les
possibilités d’un classifieur
Catégorie Classement de l’Expert
ci Vrai Faux
Jugement du Positif T Pi F Pi
Classifieur Négatif F Ni T Ni
F Pi : le nombre de documents de test mal classés dans la catégorie ci ,
T Ni : le nombre de documents bien classés qui n’appartiennent pas à
la catégorie ci ,
T Pi : le nombre de documents bien classés qui appartiennent à la
catégorie ci ,et
F Ni : le nombre de documents de catégorie ci non classés par le
classifieur.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité
Ces mésures peuvent être estimées par un tableau qui montre toutes les
possibilités d’un classifieur
Catégorie Classement de l’Expert
ci Vrai Faux
Jugement du Positif T Pi F Pi
Classifieur Négatif F Ni T Ni
F Pi : le nombre de documents de test mal classés dans la catégorie ci ,
T Ni : le nombre de documents bien classés qui n’appartiennent pas à
la catégorie ci ,
T Pi : le nombre de documents bien classés qui appartiennent à la
catégorie ci ,et
F Ni : le nombre de documents de catégorie ci non classés par le
classifieur.
M. Ledmi Introduction à la fouille de données
 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité
La précision et le rappel peuvent être exprimés localement de la façon
suivante :
T Pi
πi =
T Pi + F Pi
T Pi
ρi =
T Pi + F Ni
Deux approches sont adoptées pour exprimer globalement la précision et le
rappel :
Macro-moyenne : donner un poids égal à toutes les classes.
Micro-moyenne : Donner un poids proportionnel à la fréquence de
chaque classe.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité
La précision et le rappel peuvent être exprimés localement de la façon
suivante :
T Pi
πi =
T Pi + F Pi
T Pi
ρi =
T Pi + F Ni
Deux approches sont adoptées pour exprimer globalement la précision et le
rappel :
Macro-moyenne : donner un poids égal à toutes les classes.
Micro-moyenne : Donner un poids proportionnel à la fréquence de
chaque classe.

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité

Catégories
n o Classement de l’Expert
C = ci , · · · , c|C| Vrai Faux
P|C| P|C|
Jugement du Positif T P = i=1 T Pi F P = i=1 F Pi
P|C| P|C|
Classifieur Négatif F N = i=1 F Ni T N = i=1 T Ni
Table – Table de contingence globale

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité
La micro-moyenne (ang : micro-averaging) calcule les mesures rappel et
précision de façon globale : si l’on considère les tables de contingences
associées à chaque catégorie, cela revient à sommer les cases TP et FP de
chaque catégorie pour obtenir la table de contingence globale. Les
différentes mesures comme le π et ρ sont ensuite calculées à partir des
valeurs cumulées.
P|C|
TP T Pi
µ
π = = P|C| i=1
TP + FP i=1 (T Pi + F Pi )
P|C|
TP T Pi
µ
ρ = = P|C| i=1
TP + FN i=1 (T Pi + F Ni )

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité

La macro-moyenne (ang : macro-averaging) évalue d’abord

indépendamment chaque catégorie. Ensuite, la performance globale du
classifieur est calculée en faisant la moyenne des mesures individuelles. Les
différentes catégorie sont alors la même importance. La précision et le
rappel macro-moyenne sont calculés comme suit :
P|C|
M i=1 πi
π =
|C|
P|C|
M i=1 ρi
ρ =
|C|

M. Ledmi Introduction à la fouille de données

 Quelques Notation
Classification Définition
Arbres de décision

Mesures de d’éfficacité
F1 peut être considéré comme le degré relatif d’importance attribué à la
précision et au rappel :
2πρ
F1 =
π+ρ
Le taux de succès (ang : accuracy rate) désigne le pourcentage d’exemples
bien classés par le classifieur :
TP + TN
A=
TP + TN + FP + FN
Taux d’erreur (ang : error rate) désigne le pourcentage d’exemples mal
classés.
FP + FN
E= =1−A
TP + TN + FP + FN
M. Ledmi Introduction à la fouille de données