Chapitre

Classification et évaluation

1
Plan
 Introduction
 Apprentissage
 Apprentissage automatique
 Types d’apprentissage automatique
 Apprentissage en ligne
 Classification
 Définition
 Ensemble d’apprentissage / Ensemble test
 Approche paramétrique / Approche non paramétrique
 Classification supervisée / Classification non supervisée
 Réduction de multi-classes à deux classes
 Evaluation
 Pourcentage de classification correcte
 Matrice de confusion
 Validation Croisée / Leave one out / Le bootstrap
 Rappel / Précision
 F-mesure
 Sensibilité / Spécificité
 Courbe ROC
 Intelligibilité 2
Introduction

3
Apprentissage

4
 Apprentissage
• Acquérir de nouvelles connaissances.

• Contracter de nouvelles habitudes.

• Avoir une connaissance extraite à partir d’un ensemble d’exemples.

C’est la capacité d’améliorer

l’accomplissement d’une tâche en
interagissant avec un environnement.

5
Apprentissage
automatique

6
 Apprentissage automatique
= Machine learning
• Simuler la cognition humaine.
• Doter la machine d’un mécanisme d’apprentissage.

• Machine learning = Intersection de l’informatique, statistiques et

domaines particuliers

Statistiques Informatique

Domaine
d’application

7
Domaines d’Application

Datamining
Exploiter les données historiques pour
améliorer les décisions (Médecine,
Banque,…)

Applications non classiques

(Reconnaissance de la parole, Conduite
automatique,…)

Programmes auto-adaptatifs
(Lecture des journaux selon le thème,…)

8
 Apprentissage supervisé (1)
 On dispose d’un ensemble de paires d'entrée(s)/sortie(s) de la forme
(xi, yi),
 xi : entrée(s) possible(s) Descriptions ou situations

 yi : sortie(s) associée(s) à xi Actions ou prédictions

 Les paires d'entrée(s)/sortie(s) sont appelées les exemples qui
proviennent d'une fonction inconnue.

 Il s’agit de trouver une bonne approximation d’une fonction f dont on

connaît le résultat que pour un certain nombre d’exemples.

On demande au système de généraliser

9
 Exemples
 Une fonction h aussi proche que possible de f où f(xi) = yi
0 0
1 1
h(x) = x3
4 64
5 125
 Une distribution de probabilité P(xi, yi)
Quelle est la probabilité qu’un client avec tel profil achète tel produit ?
 Dans un jeu de cartes:
 les cartes gagnantes sont: 9♥, Roi ♥ et 7.
 les cartes perdantes sont: 3♠, 4♣ et 6♣.

Les cartes rouges sont gagnantes et les cartes numériques noires sont
perdantes
10
 Apprentissage supervisé (2)

● Apprentissage supervisé avec variable réponse continue.

Régression, Estimation de densité

Prédire une variable Y Exemple de régression :

par les variables Prédire la valeur de la bourse demain,
explicatives X1, étant données les valeurs des jours et mois passés
X2,…Xn

● Apprentissage supervisé avec variable réponse discrète.

Classification ou Analyse discriminante

● Apprentissage supervisé avec variable réponse booléenne.

Apprentissage de concept
 Apprentissage non supervisé
 On ne dispose pas d’un ensemble de paires d'entrée(s)/sortie(s).

On dispose uniquement d’un ensemble d’entrées.

 Regrouper les entrées en un nombre fixe de groupes (clusters):

 Les entrées de chaque groupe sont proches les uns des autres.
 On utilise une certaine métrique dans l’espace des entrées.
 Découvrir de nouvelles relations dans les données (ex: Réseaux
Bayésiens).

12
 Exemples
• Segmentation du marché
• Quelles sont les catégories principales des clients typiques dans
le domaine vestimentaire?
 Enfants, jeunes, adultes, etc.
 Classique, habillé, sport, etc.
• Domaine médical: Découverte de nouveaux liens
• Il y a un lien entre visiter l’Asie et attraper la tuberculose.

13
 Apprentissage semi-supervisé

 L’apprentissage semi-supervisé utilise un ensemble de données

étiquetées et non-étiquetés.

Apprentissage semi-supervisé peut améliorer

les performances en combinant les données
avec labels et sans labels.

Ne pas en laisser de côté des objets et utiliser

toute l’information

14
 Apprentissage par renforcement (1)

 L’algorithme d’apprentissage doit trouver une stratégie d’actions pour

obtenir éventuellement une récompense (ou pénalité).

La récompense ou la pénalité arrive (généralement) suite à un

ensemble d’actions.

Maximiser le gain (ou inversement) à long terme

(apprentissage de réflexes, apprentissage de planification,…)

15
 Exemples

 Jeu d’échecs
 On joue contre un adversaire.
 il y a une stratégie d’actions.
 C’est en fin de partie, qu’on va avoir le résultat de nos actions:
 Victoire
 Nul
 Défaite
Contrôle de robots (Aibo Taibo)
 Aibo réagit à son environnement, il
peut s’adapter en vue d’obtenir plus
de renforcements positifs.
Robot chien-jouet japonais 16
 Apprentissage par renforcement (2)

 L’apprentissage par renforcement se distingue des autres approches

d’apprentissage par plusieurs aspects :

 L’apprentissage se fait sans supervision.

 Il repose sur le principe d’essai/erreur.

17
 Apprentissage en ligne

 L’apprentissage en ligne (on-line learning) dans lequel les

données arrivent en séquences et où l'apprenant doit délibérer
et fournir une réponse après chaque entrée ou groupe
d'entrées.

 L’apprentissage en ligne (aussi incrémental ou séquentiel), est

le processus par lequel une entité accroît ses connaissances
au cours du temps, en même temps qu’elle les utilise.

 Par opposition, il y a l’apprentissage hors ligne (batch

learning) dans lequel toutes les données d'apprentissage sont
fournies d'un seul coup à l'apprenant.

18
N’oubliez pas

Parmi les tâches de l’apprentissage:

La classification

19
Classification

20
 Classifcation

O
Objet

Attributs A1 A2 ……………... Ak
(Variables)
Classifieur

Classes C1, C2, …………………Cn

21
Question ?
Comment savoir si je dois
attribuer un crédit
bancaire à un client ?

22
Réponse
Mais bien sûr : apprendre
à partir d’exemples que la
banque connaît déjà !

23
 Apprentissage par exemples

 On dispose d’un grand ensemble d’exemples (objets).

 On cherche à trouver une structure relative à ces exemples pour

obtenir un modèle.
 Ce modèle permet de:
 Extraire une procédure de classification à partir d’exemples.

 Classer un nouvel exemple.

.
.
 Prévoir une valeur numérique.
 Comprendre la structure des exemples.
24
 Ensemble d’apprentissage
Attributs
Revenu Propriété Crédit non Classes
remboursé
Elevé Supérieur Non C1
Valeurs des attributs

Elevé Supérieur Oui C2

Elevé Supérieur Non C1
Elevé Inférieur Oui C2
Moyen Supérieur Non C1
Moyen Supérieur Oui C2
Moyen Inférieur Non C2
Moyen Inférieur Oui C2
Faible Inférieur Non C3
Faible Inférieur Oui C3
C1: Attribuer tout le crédit.
C2: Attribuer une partie crédit.
C3: Ne pas attribuer le crédit.
25
Ensemble test

Revenu Propriété Crédit non payé Classes

Elevé Supérieur Oui ?
Moyen Inférieur Non ?
Elevé Supérieur Oui ?
Moyen Supérieur Oui ?
Faible Inférieur Oui ?
Nul Inférieur Oui ?
Elevé Supérieur Non ?
Moyen Inférieur Oui ?

On cache les
vraies classes
 Domaines d’application (1)

 Banque: attribution de crédits

 Utiliser un historique de crédits accordés et non accordés avec la
situation personnelle du client.

 Médecine: aide au diagnostic

 Caractériser les symptômes des anciens patients et de leurs
maladies.

 Marketing: établir un profil client

 Faire une segmentation automatique des clients pour le
marketing direct.

27
 Domaines d’application (2)

 Analyse financière: prévision d’évolution des marchés

 Assurance: analyse de risques

 Télécoms: détection de fraudes

 Sécurité: détection d’intrusions

.
.
.
28
 Approche paramétrique
 Proposition d’un modèle dont on estime ses paramètres à partir
des exemples (phase d’apprentissage).

 Les hypothéses que l’on fait sur les lois de probabilité font partie
d’une famille de distributions.

 Si on sait que P est une distribution normale, il suffit d’estimer

ses deux paramètres:
 Sa moyenne
 Son écart type
Avoir une bonne approximation de la distribution P.

Déterminer une procédure de classification.

29
 Approche non paramétrique

 Pas d’hypothèses sur le modèle que suivent les données.

 Les problèmes à résoudre sont plus complexes que ceux

traités par les méthodes paramétriques.

 Méthodes statistiques.

 Méthodes issues de l’intelligence artificielle.

30
 Classification supervisée

 Les classes sont définies a priori.

 Découverte de règles ou formules pour ranger les données

dans des classes prédéfinies.

 Construction d'un modèle sur les données dont la classe est

connue (Ensemble d’apprentissage).

 Utilisation pour classification des nouveaux objets.

31
 Exemples

 Arbres de décision

 Méthodes K plus proches voisins

 Réseaux de neurones

 Machines à vecteurs supports (SVM)

.
.
.
 Classification non supervisée

 Les instances d’apprentissage ne sont pas fournies avec des classes.

L’ensemble d’apprentissage n’est pas étiqueté (on ne connaît

pas les classes a priori).

 Intuitevement les objets de même classe sont “proches” les uns des
autres.
Mesure de similarité ou de distance

Regrouper les exemples similaires:

Segmentation et clustering
 Exemples

 Clustering par partitionnement

 Clustering hiérarchique

.
.
.
 Réduction de multi-classes à deux
classes

 Problème de classification à plusieurs classes.

Plusieurs problèmes de classification binaire.

 OvA (One vs. All) : C’est la méthode un contre tous mais qui n’est
pas forcement la meilleure (classes souvent très déséquilibrées).

 AvA (All vs. All) : Pour chaque paire de classes (C1;C2),

construire un classieur pour discriminer entre C1 et C2 (Classes
équilibrées mais on a  n2/2 classifeurs).

35
Evaluation

36
 Données d’apprentissage

 Ensemble d’apprentissage : ensemble des objets (exemples)

utilisés pour générer le modèle d’apprentissage.

 Ensemble test : ensemble des objets (exemples) sur lequel sera

appliqué le modèle d’apprentissage (pour tester et corriger
l’algorithme).

 Ensemble de validation : peut être utilisé lors de l’apprentissage

(comme sous population de l’ensemble d’apprentissage) afin de
valider (intégrer) le modèle et d’éviter le sur-apprentissage.

36
 Evaluation

 Utilisation d’un ensemble test.

 Pourcentage de classification correcte (PCC).

 Taux d’erreur de classification.

 Utilisation de la validation croisée, leave one out, etc.

38
 Pourcentage de Classifcation
Correcte (PCC) (1)
Nombre d’objets correctement classés
PCC =
Nombre total des objets tests
Ensemble test

Revenu Propriété Crédit Classes Vraies

non payé prédites classes
Elevé Supérieur Oui C1 C1
Moyen Inférieur Non C2 C2
Elevé Supérieur Oui C1 C1
Moyen Supérieur Oui C3 C2
Faible Inférieur Oui C1 C3
Nul Inférieur Oui C2 C3
Elevé Supérieur Non C1 C1
Moyen Inférieur Oui C3 C2
39
 Pourcentage de Classifcation
Correcte (PCC) (2)
Revenu Propriété Crédit Classes Vraies
non payé prédites classes
Elevé Supérieur Oui C1 C1
Moyen Inférieur Non C2 C2
Elevé Supérieur Oui C1 C1
Moyen Supérieur Oui C3 C2
Faible Inférieur Oui C1 C3
Nul Inférieur Oui C3 C3
Elevé Supérieur Non C1 C1
Moyen Inférieur Oui C2 C2

PCC = 6 = 75%
8
Taux d’erreur = 25%

40
 Matrice de confusion

Classifieur
Prédites C1 (4) C2 (2) C3 (2)
Vraies
C1(3) 3 0 0
C2 (3) 0 2 1
C3 (2) 1 0 1
 Bon classifieur: sur les diagonales.

 Identifier les classes mal comprises (apprises).

 Comparer les classifieurs selon la classe.
 Fixer des pénalités.
41
 Validation croisée

 Partition de l’ensemble d’apprentissage T en k ensembles

disjoints (T1, T2,…, Tk) de même taille |Ti|.

 Pour chaque i = 1, 2, …, k
1- On fait l’apprentissage sur T – {Ti}

2- On teste sur Ti

3- On calcule le PCC sur Ti

● On fait la moyenne des PCC.

42
 Leave one out

 Cette méthode est dérivée de la méthode de validation croisée, en

prenant 𝒌=𝒏, 𝒏 étant le nombre d'exemples.

 A chaque itération, on va donc faire l'apprentissage sur tous les

exemples moins un, et tester sur un seul exemple, afin de vérifier s'il
est prédit correctement.

43
 Le bootstrap

 Le bootstrap diffère des techniques précédentes qu’il utilise des

tirages avec remise pour l’ensemble des exemples: on tire
aléatoirement un exemple, pour le placer dans un ensemble appelé
boostrap, le procédé est répété n fois.

 Le bootstrap est très souvent utilisé dans le cadre de jeux de

données contenant peu d'exemples.

44
 Matrice de confusion
Classifieur
Prédites Oui Non
Vraies
Oui VP FN
Non FP VN
VP (Vrai Positif) = Nombre d’individus prédits positifs par le test et qui le sont effectivement.

FP (Faux Positif) = Nombre d’individus prédits positifs par le test mais qui sont en réalité négatifs.

VN (Vrai Négatif) = Nombre d’individus prédits négatifs par le test et qui le sont effectivement.

FN (Faux Négatif) = nombre d’individus prédits négatifs par le test mais qui sont en réalité positifs.

TP = VP, TN = VN
45
 Rappel / Précision
Classifieur
Prédites Oui Non
Vraies PCC (Accuracy) =
VP + VN
Oui VP FN VP + FN + FN + VN

Non FP VN
 Parmi toutes les étiquettes positives possibles, combien d'entre elles
le modèle a-t-il correctement identifiées.
VP
Rappel (Recall) =
VP + FN
 Quelle est la fréquence à laquelle le modèle prédit correctement la
classe positive.
VP
Précision (Precision) =
VP + FP 46
 F-mesure (F-measure)

 Moyenne harmonique entre la précision et le rappel

2*Précision *Rappel 2VP

F-measure = =
Précision + Rappel 2VP + FP + FN

 Si Précission = Rappel alors F-mesure = Précision = Rappel

47
 Sensibilité / spécificité

 Taux de vrais positifs : proportion d'individus positifs effectivement

bien détectés par le test.
VP
Sensibilité (Sensibility) =
VP + FN

 Taux de vrais négatifs : proportion d'individus négatifs effectivement

bien détectés par le test.

VN
Spécificité (Specificity) =
VN + FP

48
 Courbe ROC (1)
- Receiver Operating Charateristic -
 Courbe ROC est une représentation graphique de la relation
existante entre la sensibilité et la spécificité d’un test pour chaque
valeur seuil considérée.

 L’ordonnée représente la sensibilité et l’abscisse correspond à la

quantité (1 - spécificité). Cette représentation fait varier le seuil de la
probabilité qu’un exemple soit dans la classe positive.

49
 Courbe ROC (2)
- Receiver Operating Charateristic -
 Principe de la courbe ROC :
Soit xi positif, si p(y = 1|xi) > seuil , sinon il est négatif (y = 0).

=1 p(y = 1|xi) > seuil

 Si on prend seuil = 0,5, alors on aura une matrice de confusion, et
donc on peut calculer la sensibilité et (1 – spécificité).

 Si on choisit un autre seuil (par exemple 0,6), on aura une autre

matrice de confusion, et par conséquent de nouvelles valeurs de
sensibilité et de (1 – spécificité).

L’idée de la courbe ROC est de faire varier les seuils pour obtenir
à chaque seuil, la sensibilité et (1 – spécificité).

50
 Autre critère : Intelligibilité

 Améliorer la compréhension des résultats d’apprentissage.

Permettre au modèle de fournir une connaissance claire et

compréhensible, au sens interprétable.

51
 A suivre…

 Une technique de classification en apprentissage supervisé.

Arbres de décision

52