CLASSIFICATION

Classification
 Une technique importante de l’apprentissage automatique
 Permet de décrire des tendances dans les relations au sein d’un
ensemble de données
 Les arbres de décisions sont un outil de construction de modèles
 Utilisés pour la classification comme pour la prédiction
 Domaines d’applications
– Diagnostic médical,

– Accord de crédit,

– Détection de fraudes fiscales,

– Techniques de marketing,…

 Classifier les données (construire un modèle) en se basant sur

un ensemble où l’on connaît déjà l’association données-classes
(training set: ensemble d’apprentissage)
2
Classification— Processus à deux étapes

3
 Classification— Processus à deux étapes

 Construction du modèle:
 Chaque tuple (exemple) est supposé appartenir à une classe
comme spécifié par le label de l’attribut “Classe”
 Les données sont partagées en 2 sous ensembles

 Le modèle (construit sur le 1er sous ensemble) est représenté

par des règles de classification, arbres de décisions …
 Utilisation du modèle:
 Estimer la pertinence sur le 2ème sous ensemble

 Comparer les labels de classe de l’ensemble avec ce que

prévoit le modèle
 Le pourcentage de tuples qui sont correctement classifiés par

le modèle donne une mesure de la précision

4
Validation de la Classification

5
 Processus de Classification (1):
Construction du modèle
Algorithmes de
Classification
Training
Data

Nom Grade Années Titulaire Modèle

David Assistant 3 non
Marie Assistant 7 oui
Jean Professeur 2 oui
Jim Prof. Associé 7 oui SI Grade = ‘professeur’
Pierre Assistant 6 non
OU Années > 6
Anne Prof associé 3 non
ALORS Titulaire = ‘oui’
6
 Processus de Classification (2): Utilisation
du modèle

Modèle

Données
Pour test Taux d’erreur
du modèle ?

Tom Assistant 2 non

Elise Assistant 7 non
George Professeur 5 oui
Josephe Assistant 7 oui

7
 Processus de Classification (2):
Prédiction

Modèle

Données
Inconnues
Titulaire? ?
Paul Associate Prof 2 ?
Jeff Professeur 7 ?
?
?

8
 Apprentissage Supervisé vs non supervisé
 Apprentissage Supervisé (classification)
 Supervision: les données d’apprentissage (observations)
sont accompagnés par les labels indiquant leurs classes
 Les nouvelles données sont classifiées en se basant sur le
training set
 Apprentissage non supervisé (regroupement (voir chapitre
clustering))
 Le label de classe des éléments observés (training set)
n’est pas connu
 Le but est de déceler l’existence de classes ou groupes
dans les données

9
 Classification avec arbres de décision

• Une des formes les plus simples d’apprentissage, mais tout

de même une de celles qui connaissent le plus de succès.
• A partir d’exemples, le but est d’apprendre des structures
d’arbres permettant de prendre des décisions.
• Chaque nœud représente un test à faire.
• Chaque branche représente une valeur possible résultant du
test.
• Une feuille correspond à la décision
 Classification avec arbres de décision
 Arbre de Décision
 Les nœuds internes correspondent à des tests

 Un arc correspond au résultat d’un test

 Les nœuds feuilles représentent des classes

 La génération se fait en 2 phases

 Construction de l’arbre

 Au début tous les tuples se trouvent sur la racine

 Partitionner les tuples récursivement en se basant à

chaque fois sur un attribut sélectionné

 Simplification de l’arbre

 Identifier et supprimer les branches qui correspondent à

des exceptions
 Utilisation:
 Tester les attributs du tuple par rapport à l’arbre pour trouver
la branche et qu’il satisfait donc sa classe
11
 Training set
age salaire etudiant crédit achète_ordinateur
<=30 élévé non correct non
<=30 élévé non excellent non
30…40 élévé non correct oui
>40 moyen non correct oui
>40 faible oui correct oui
>40 faible oui excellent non
31…40 faible oui excellent oui
<=30 moyen non correct non
<=30 faible oui correct oui
>40 moyen oui correct oui
<=30 moyen oui excellent oui
31…40 moyen non excellent oui
31…40 élévé oui correct oui
>40 moyen non excellent non

12
Output: Un arbre de décision pour “achète_ordinateur”

age?

<=30 overcast
30..40 >40

étudiant? oui Crédit ?

non oui excellent correct

non oui non oui

13
 Création de l’arbre de décision
 L’arbre est construit top-down récursivement
 Au début, tous les tuples sont sur la racine

 Les attributs sont qualitatifs (discrétisation s’il le faut)

 Les tuples sont ensuite partitionnés en fonction de l’attribut

sélectionné

 L’attribut de test est sélectionné en utilisant des heuristiques ex:

gain informationnel (on y reviendra)

 Conditions d’arrêt du partitionnement

 Tous les tuples d’un nœud se trouvent dans la même classe

14
Exemple de définition d’une partition

• Variable binaire X {yes,no} X?

yes no

• Variable quantitative X X < ?

yes no

• Variable qualitative X
– Avec M modalités dans E = {e1,…eM}
X?
X  E’  E
yes e1 e2 … eM
 Choix de l’attribut de partionnement (1)
 Soit le training set suivant

A B Classe Si c’est A qui est choisi en premier

A 1
0 1 C1 0
0 0 C1 C1 C2
1 1 C2
1 0 C2 Si c’est B qui est choisi en premier
B 1
0
A 1
A 1 0
0
C2 C1 C2
C1
16
 Choix de l’attribut de partionnement (2)
 Un arbre de décision représente la suite de questions à poser
pour pouvoir classifier un nouvel exemple.

 Le but consiste à obtenir une classification en posant le moins

possible de questions

 Dans l’exemple précédent, on dira que l’attribut A apporte plus

d’information, respectivement à la classification des exemples,
que B

 Nous avons donc besoin de quantifier l’information apportée par

chaque attribut

17
 Notions sur la théorie de l’information(1)
 Intuitivement : Plus un événement est probable, moins il nous
apporte d’information
 Exemple : Vous êtes dans le désert et on vous annonce que le
lendemain, il fera beau. C’est un événement très probable, ce
message n’apporte donc presque aucune information

 La quantité d’information associée à un événement X sera

considérée comme une fonction croissante sur son improbabilité
 1 
h (X )  f  
 Proba ( X ) 
 

 Un événement certain apporte une quantité d’information nulle,

ainsi f(1) doit être nulle

18
 Notions sur la théorie de l’information(2)
 La réalisation de 2 événements indépendants apporte une quantité
d’information égale à la somme de leurs informations respectives, i.e

   1 
h (X , Y )  f  1   f    h (X )  h (Y )
 Proba ( X , Y )   Proba ( X ) * Proba ( Y ) 

 C’est la fonction log en base 2 qui a été choisie. Ainsi,

h ( X )   log  Proba (X ) 
2

 La fonction h satisfait les 2 conditions: croissante et l’info de deux

événements indépendants est la somme des infos

19
 Notions sur la théorie de l’information(3)
 Supposons maintenant qu’il y a deux classes, P et N
 Soit S un ensemble qui contient p éléments de P et n éléments
de N
 La probabilité qu’un élément soit dans P est p/(p+n)
 La quantité d’information nécessaire pour décider si un
élément quelconque de S se trouve dans P ou dans N est
définie par :

p n
I ( p , n )   p log  n log
2 p  n 2 p  n

20
 Cas particulier
 Supposons que p soit nul. Cela veut dire que I(n,p)=0:

 p=0 et log(p/[n+p])=- le produit donne 0 (pour être

précis, la limite du produit tend vers 0 quand p tend vers
0)

 log(n/[n+p])=0 donc le produit donne 0

 Ce qui est conforme à l’intuition: On n’a pas besoin d’info

pour décider si un élément est dans N ou P; on est sûr qu’il
est dans N
21
 Intuition de l’expression I(n,p)

 Chaque élément apporte une information qui est

 p 
  log 



si il est dans P
n  p
 

 n 
 log   si il est dans N
  n  p 
 

 Si l’on fait le total des infos, on obtient I(n,p)

22
 Gain d’information et arbre de décision
 Supposons qu’en utilisant l’attribut A, S est partitionné en {S1, S2 ,
…, Sv} (ça veut dire que A prend v valeurs)
 Si Si contient pi tuples de P et ni tuples de N, l’entropie, ou la
quantité d’information nécessaire pour classifier les objets de
tous les sous arbres Si est

E (A )   I(p , n )
i 1 i i
 L’entropie mesure la « quantité de désordre » qui reste après le
choix de A
 L’information de codage gagnée en utilisant A sera
Gain ( A )  I(p , n )  E (A )
23
 Intuition derrière Gain(A)
 Pour classer les éléments dans Si, nous avons besoin d’une quantité
d’info égale à I(ni,pi)

 Pour classer les éléments dans tous les Si, on fait la somme des
I(ni,pi) ce qui donne E(A)

 On sait que pour classifier les éléments, nous avons besoin d’une
quantité d’info égale à I(n,p)

 Suite au partionnement des n+p éléments selon les valeurs de A,

nous aurons besoin d’une quantité d’info égale à E(A)

 Donc, il nous manquera que I(n,p)-E(A) pour pouvoir classer

24
 Application à l’exemple
 Il y a 2 classes C1 (P) et C2 (N)
 En choisissant A, S est partitionné en S1
et S2
 p1=2, n1=0, p2=0 et n2=2 A B Classe
0 1 C1
 E(A)=(I(2,0)+I(0,2)) 0 0 C1
 I(2,0)=-2*log(1)-0*log(0)=0
1 1 C2
 I(0,2)=0
1 0 C2
 E(A)=0

 Gain(A)=I(2,2)-E(A)
 I(2,2)=-2*log(2/4)-2*log(2/4)=4

 Gain(A)=4
25
 Application à l’exemple
 En choisissant B, S est partitionné en S1
et S2
 p1=1, n1=1, p2=1 et n2=1
A B Classe
 E(B)=(I(1,1)+I(1,1)) 0 1 C1
 I(1,1)=-log(1/2)-log(1/2)=2
0 0 C1 S1
 E(B)=4
S2 1 1 C2
1 0 C2
 Gain(B)=I(2,2)-E(B)=0

 Il vaut mieux choisir A!!

26
 Gain d’information: Exemple

 Classe P: achète_ordinateur = “oui”

 Classe N: achète_ordinateur = “non”
 I(p, n) = I(9, 5) =13,16
 L’entropie de l’attribut age:
E ( age )  I(2 ,3 )  I(4 ,0 )

 I(3 ,2 )  9 , 71

age pi ni I(pi, ni)

<=30 2 3 4,855
30…40 4 0 0
>40 3 2 4,855
Gain(age)=I(p,n)-E(age)=3,45
C’est l’attribut qui maximise le gain 27
 Extraction de règles de classification

 De la forme SI-ALORS
 Chaque chemin partant de la racine et atteignant une feuille
donne lieu à une règle
 Chaque paire attribut-value le long d’un chemin forme une
conjonction
 Les feuilles constituent la classe
 Exemple
SI age = “<=30” ET étudiant = “non” ALORS
achète_ordinateur = “non”
SI age = “<=30” ET étudiant = “oui” ALORS
achète_ordinateur = “oui”

28
Output: Un arbre de décision pour “achète_ordinateur”

age?

<=30 overcast
30..40 >40

étudiant? oui Crédit ?

non oui excellent correct

non oui non oui

29
 Exemple
• Est-ce une bonne journée pour jouer au tennis?
Journée Ciel Température Humidité Vent JouerTennis
J1 Ensoleillé Chaude Élevée Faible Non
J2 Ensoleillé Chaude Élevée Fort Non
J3 Nuageux Chaude Élevée Faible Oui
J4 Pluvieux Tempérée Élevée Faible Oui
J5 Pluvieux Froide Normal Faible Oui
J6 Pluvieux Froide Normal Fort Non
J7 Nuageux Froide Normal Fort Oui
J8 Ensoleillé Tempérée Élevée Faible Non
 Exemple
Journée Ciel Température Humidité Vent JouerTennis

J9 Ensoleillé Froide Normal Faible Oui

J10 Pluvieux Tempérée Normal Faible Oui

J11 Ensoleillé Tempérée Normal Fort Oui

J12 Nuageux Tempérée Élevée Fort Oui

J13 Nuageux Chaude Normal Faible Oui

J14 Pluvieux Tempérée Élevée Fort Non

 Exemple
• Premièrement, il faut choisir la racine de l’arbre.
• Pour cela, choisir l’attribut qui a le plus grand gain
d’information.
– Pour calculer le gain d’information, il faut d’abord calculer
l’entropie des exemples d’entraînement.
– Il y a 9 exemples positifs et 5 exemples négatifs, donc on obtient
une entropie de :

Entropie(S) = i=1..c (-pi) log2 (pi)

= (-9/14) log2 (9/14) + (-5/14) log2 (5/14)
= 0.94
 Exemple
• Maintenant, calculer le gain d’information pour le premier
attribut, l’attribut Ciel.
– Cet attribut a 3 valeurs possibles, donc les exemples
d’entraînement seront regroupés en 3 sous-ensembles.
– Commençons par calculer l’entropie des 3 sous-ensembles :

Entropie(SEnsoleillé) = 0.971
Entropie(Snuageux) = 0
Entropie(Spluvieux) = 0.971
 Exemple
• On calcule le gain d’information pour les attributs :
Gain(S,Ciel) = 0.246
Gain(S,Humidité) = 0.151
Gain(S,Vent) = 0.048
Gain(S,Température) = 0.029
• L’attribut qui a le plus grand gain d’information est
l’attribut Ciel, donc ce sera la racine de l’arbre de décision.
 Exemple
En séparant les exemples selon les valeurs de l’attribut
Ciel, on obtient l’arbre partiel :
[9+,5-]
Ciel
Ensoleillé Pluvieux
Nuageux [3+,2-]
[2+,3-] [4+,0-]
??? ???
Oui

• On peut voir que lorsque le ciel est nuageux, il reste uniquement des
exemples positifs, donc ce nœud devient une feuille avec une valeur de
Oui pour la fonction visée.
• Pour les deux autres nœuds, il y a encore des exemples positifs et
négatifs, alors il faut recommencer le même calcul du gain
d’information, mais avec les sous-ensembles restants
 Exemple
En effectuant les calculs restants, on obtient :
[9+,5-]
Ciel
Pluvieux
Ensoleillé Nuageux
[2+,3-] [4+,0-] [3+,2-]
Oui
Humidité Vent

Élevée Normale Fort Faible

[0+,2-] [3+,0-]
[0+,3-] [2+,0-]
Non Oui
Non Oui
 Problème de l’overfitting
 En appliquant la méthode décrite jusque là, on obtient des arbres qui
classent correctement les exemples du training set
 Aucune erreur (normalement)

 Mais rien ne dit qu’ils seront efficaces pour l’autre partie des
exemples

 Lorsque l’arbre « colle trop au training set » on parle d’overfitting

 Pour résoudre le problème, on va autoriser des erreurs sur le training

set pour obtenir des arbres assez généraux

37
 Généraliser l’arbre induit
 2 Approches

 Prepruning: ne pas découper un nœud si le partage fait basculer la

mesure de pertinence en dessous d’un certain seuil.
 Par exemple si le gain est inférieur à un certain seuil

 Difficile de choisir un seuil approprié

 Postpruning: supprimer des banches d’un arbre déjà construit.

Obtenir un ensemble d’arbres réduits
 Utiliser un ensemble de données différent du training set pour

choisir le meilleur arbre réduit

38
 Procédure générale d’apprentissage
1. Faire la collecte d’un grand ensemble d’exemples.
2. Diviser les exemples en deux ensembles : un
d’entraînement et l’autre de test.
3. Utiliser l’ensemble d’entraînement comme exemples et
générer l’hypothèse h.
4. Mesurer le pourcentage d’exemples de l’ensemble de
test qui sont correctement identifiés par h.
5. Répéter les étapes 1 à 4 pour différentes tailles
d’ensembles d’entraînement et différentes sélections
aléatoires d’exemples pour chacune des grandeurs.
 Gérer les erreurs dans les exemples

• Si les exemples d’entraînement contiennent des erreurs, il se

peut qu’on trouve un arbre plus grand, mais qui ne classifiera
pas bien les instances autres que celles utilisées dans les
exemples d’entraînement
• Pour vérifier notre arbre, on utilise un ensemble de validation
(ou de test).
– L’ensemble de validation est généralement le tiers des exemples
disponibles pour l’apprentissage
 Principaux algorithmes
• Arbre de décision
• ID3 (Quinlan, 1979)
• C4.5 (Quinlan, 1986), amélioration de ID3
• CART (Breiman, Friedmen, Ohlson, Stone, 1984)
• C4.5 est l’un des algorithmes les plus connus et les
plus utilisés
• Autres méthodes de classification
• Classification Bayésienne : Naïve Bayes
• k plus proches voisins (k-Nearest Neighbor : K-NN)
• Support Vector Machines : SVM