ESSECT

La Classification et La Prédiction

Niveau : 3ème LIG

Enseignante: Lamia Enneifar
 Classification vs prédiction

Classification
• Classification, classement , discrimination
• Prédit la catégorie d’un objet (discrètes ou nominales)
• Construit un modèle basé sur un échantillon de test (jeu d’apprentissage) et des valeurs (noms
de catégorie) et l’utilise pour classer des données nouvelles
Prédiction
• Modélise des données numériques pour prédire des données inconnue ou manquantes
Applications
• Diagnostic médical, ciblage marketing, credit scoring, détection de fraudes

2
Classification

Quelques méthodes
• Arbre de décision
• Classificateur Bayésien
• Réseau de neurones
• Plus proche voisin

3
Classification : processus à deux étapes

Construction du modèle
• Chaque objet appartient à une classe connue
• jeu de données d’apprentissage : ensemble des objets utilisés pour la construction
du modèle
Utilisation du modèle pour classer des objets nouveaux ou inconnus
• estimation de la précision du modèle à l’aide du jeu de test
• les classes connues du jeu d’apprentissage sont comparées à celles prédites
• précision : pourcentage d’objets de jeu de test correctement classés
• le jeu de test est indépendant du jeu d’apprentissage sinon risque de biais (défaut)

4
 Classification : processus à deux étapes
exemple
Objectif : Division du dataset en deux parties:
expliquer l’attribut tenured en fonction des attributs Rank et Year

• Jeu d’apprentissage pour la

construction du modèle

• Jeu de test pour l’évaluation du

modèle

Une fois le modèle validé, on peut prévoir la valeur d’appartenance de nouvelles instances
Classification : Construction du modèle

Tenured= titulaire

6
Classification : Utilisation du modèle
Estimation de la précsion

Calcul de la précision

7
Classification : Utilisation du modèle

Règles de classification

8
Apprentissage supervisé vs apprentissage
non supervisé

Apprentissage supervisé (classification)

• supervision : le jeu de données d’apprentissage fournit les classes des objets

• les nouveaux objets sont classés en fonction du jeu d’apprentissage

Apprentissage non supervisé (clustering)

• Pas de classes définies

• Étant donné un ensemble de mesures, d’observations, etc., essayer d’établir l’existence de classes
ou de clusters dans les données

9
Considérations pour la classification

Nettoyage des données

pré‐traiter les données pour réduire le bruit et gérer les valeurs manquantes
Analyse de pertinence
supprimer les attributs non pertinents ou redondants
Transformation des données
Généraliser ou normaliser les données
Précision de la prédiction
Capacité à prévoir correctement la valeur de l’attribut (validation croisée, bootstrap)
Efficacité et mise à l’échelle
adaptabilité et robustesse (capacité à construire des classificateurs ou de prédicteurs avec grandes BD)
tolérance au bruit et aux données manquantes
Interprétabilité
compréhension des données via le modèle
Qualité des règles
taille de l’arbre de decision / règles de classification compactes
10
Classification par les arbres de décision

age income student credit_rating buys_computer

<=30 high no fair no Input : données d’apprentissage
Objectif : expliquer buys_computer
<=30 high no excellent no
31…40 high no fair yes
>40 medium no fair yes
>40 low yes fair yes
>40 low yes excellent no
31…40 low yes excellent yes
<=30 medium no fair no
<=30 low yes fair yes
>40 medium yes fair yes
<=30 medium yes excellent yes
31…40 medium no excellent yes
31…40 high yes fair yes
>40 medium no excellent no 11
Classification par les arbres de décision

9 yes
age income student credit_rating buys_computer age? 5 no
<=30 high no fair no
<=30 high no excellent no <=30 31..40 >40
31…40 high no fair yes 4 yes 3 yes
2 yes 2 no
>40 medium no fair yes 3 no 0 no
>40 low yes fair yes
>40 low yes excellent no student? yes credit rating?
31…40 low yes excellent yes
<=30 medium no fair no no yes excellent fair
<=30 low yes fair yes
>40 medium yes fair yes no yes yes
<=30 medium yes excellent yes 0 yes 2 yes 0 yes 3 yes
31…40 medium no excellent yes 3 no 0 no 2 no 0 no
31…40 high yes fair yes
>40 medium no excellent no

12
 Classification par les arbres de décision
noeuds internes : test sur un attribut
Output : arbre de décision “buys_computer” branches : résultat d’un test / valeur
attribut
9 yes feuilles : classe
age? 5 no
Modèle:
31..40 R1: si age <=30 et student = no alors
<=30 >40 buys_computer = no
2 yes 4 yes 3 yes
2 no R2: si age <=30 et student = yes alors
3 no 0 no
buys_computer = yes
student? yes credit rating? R3: si age in [31..40] alors buys_computer = yes
R4: si age >40 et credit rating = excellent alors
no yes excellent fair buys_computer = no
R5: si age >40 et credit rating = fair alors
3 yes buys_computer = yes
no 0 yes yes 2 yes 0 yes yes 0 no
3 no 0 no 2 no
13
Classification par les arbres de décision:
généralités

Génération de l’arbre en 2 étapes

1. Construction
au départ, tous les exemples du jeu d’apprentissage sont à la racine
partitionne récursivement les exemples en sélectionnant des attributs

2. Élagage
identification et suppression des branches correspondant à des exceptions ou du
bruit

Utilisation de l’arbre
teste les valeurs des attributs avec l’arbre de décision

14
Algorithme pour l’induction d’arbres de
décision
Algorithme glouton
• approche descendante récursive diviser pour régner
• au départ, tous les objets sont à la racine
• attributs catégoriels (les valeurs continues sont discrétisées à l’avance)
• les exemples sont partitionnés récursivement par la sélection d’attribut
• les attributs sont sélectionnés sur la base d’une heuristique ou d’une mesure
statistique

Conditions d’arrêt
• tous les exemples pour un nœud appartiennent à la même classe
• plus d’attribut pour partitionner, dans ce cas la classe attribuées correspond à celle la
plus représentée

15
Induction d’arbres de décision :
Algorithme générer_arbre_décision

Inputs :
D : partition de données – jeu d’apprentissage et valeurs des classes correspondantes
L : liste des attributs candidats
méthode_sélection_attribute :
procédure pour déterminer le critère de scission qui partitionne le mieux les tuples de
données en classes on parle d’attribut de scission, point de scission

Output : arbre de décision

16
Induction d’arbres de décision :
Algorithme générer_arbre_décision (suite)
Méthode :
1. Créer un nœud N
2. Si les tuples de D sont dans la même classe C alors return N comme feuille avec C comme
classe
3. Si L vide alors return N comme feuille avec la classe majoritaire dans D
4. Appliquer méthode_sélection_attribut(D,L) pour trouver le meilleur critère de scission
5. Donner au nœud N le nom du critère de scission
6. Si attribut_scission discret et rupture multiple permise (arbre non binaire) alors
1. L L – attribut_scission
2. Pour chaque sortie j de attribut_scission
3. Soit Dj l’ensemble des tuples des données de D satisfaisant la sortie j //une partition
4. Attacher le nœud retourné par générer_arbre_décision(Dj, L) au nœud N
5. FinPour
17 17
Mesure pour la sélection d’attributs

Plusieurs mesures possibles:

• Entropie ou gain informationnel (ID3, C4.5)

• Indice de concentration ou indice de GINI (CART)

• Mesure de liaison statistique (CHAID)

18
Mesure pour la sélection d’attributs:
gain d’information (ID3 et c4.5)
• L’entropie est une fonction
mathématique correspondant à la
quantité d’information contenue ou
délivrée par une source d’information.

• Elle permet de mesurer le désordre

dans un ensemble de données.

• Si la source délivre une seule

information l’entropie est nulle.

• Si la source délivre deux informations :

chacune avec une probabilité égale à 0,5
l’entropie est égale à 1.
19
Mesure pour la sélection d’attributs:
gain d’information (ID3 et c4.5)
Entropie de Shannon
Shannon en 1949 a proposé une mesure d’entropie valable pour les distributions discrètes de probabilité. Elle
exprime la quantité d’information, c’est-à-dire le nombre de bits nécessaires pour spécifier la distribution

L’entropie d'information est:

I = -  pi  log2 (pi )
i=1..k
où pi est la probabilité de la classe Ci.

Entropie d’information de S
C
I ( S ) = −  p (ci )  log 2 p (ci )
i =1

Nulle quand il n’y a qu’une classe

D’autant plus grande que les classes sont équiprobables
20
Vaut log2(k) quand les k classes sont équiprobables
Mesure pour la sélection d’attributs:
gain d’information (ID3 et c4.5)

Gain d’information : Gain(S,A)=Réduction d’entropie due à un tri suivant les valeurs de A

Objectif→ trouver un attribut permettant d’avoir des feuilles pures cad dont
l’information est la plus petite
Mesure pour la sélection d’attributs :
gain d’information (ID3 et c4.5)
◼ But: sélectionner l’attribut ayant le plus grand gain d’information

◼ Soit pi la probabilité qu’un tuple arbitraire dans D appartienne à la classe Ci, estimé par
|Ci, D|/|D| (nombre de tuples de D appartenant à Ci divisé par le nombre de tuples de D)
m
Info( D ) = − pi log2 ( pi )
i =1

◼ L’information nécessaire (en utilisant l’attribut A pour scinder D en v partitions) pour classifier D selon A:
v | Dj |
j= nombre de valeurs dans A Info A ( D) =   Info ( D j )
j =1 | D |
Le gain d’information en partitonnant selon l’attibut A

Gain(A) = Info(D) − InfoA(D)

22
Sélection d’attribut: Gain d’information
 Classe P: buys_computer = “yes” 5 4
Infoage ( D ) = I ( 2,3) + I ( 4,0)
 Classe N: buys_computer = “no” 14 14
9 9 5 5 5
Info( D) = I (9,5) = − log2 ( ) − log2 ( ) =0.940 + I (3,2) = 0.694
14 14 14 14
14
5
age pi ni I(pi, ni) I (2,3) → “age <=30” a 5 parmi 14 exemples, avec
<=30 2 3 0.971 14
2 yes et 3 no. Ainsi
31…40 4 0 0
>40 3 2 0.971
age income student credit_rating buys_computer Gain(age) = Info( D) − Infoage ( D) = 0.246
<=30 high no fair no On a aussi,
<=30 high no excellent no
31…40 high no fair yes
>40 medium no fair yes
>40
>40
low
low
yes fair
yes excellent
yes
no Gain(income) = 0.029
31…40 low yes excellent yes
<=30
<=30
medium
low
no fair
yes fair
no
yes
Gain( student ) = 0.151
>40
<=30
medium
medium
yes fair
yes excellent
yes
yes Gain
Donc on(choisit
creditl’attribut ) = 0.048
_ ratingAGE
31…40 medium no excellent yes
31…40 high yes fair yes 23
October 25, 2022
>40 medium no excellent no
Mesure pour la sélection d’attributs:
Ratio du gain pour la sélection d’attributs
(C4.5)
• La mesure du gain d’information est biaisée vers les attributs ayant le plus grand nombre de valeurs
• C4.5 (successeur de ID3) utilise un ratio de gain pour pallier à ce problème (normalisation du gain
d’information)
v | Dj | | Dj |
SplitInfoA ( D) = −  log2 ( )
j =1 |D| |D|
– GainRatio(A) = Gain(A)/SplitInfo(A)
• Ex.
– gain_ratio(income) = 0.029/0.926 = 0.031
• L’attribut ayant le gain maximum est sélectionné comme attribut de coupure

4 4 6 6 4 4
SplitInfoA ( D) = −  log2 ( ) −  log2 ( ) −  log2 ( ) = 0.926
14 14 14 14 14 14
24
Mesure pour la sélection d’attributs:
Indice de Gini (CART, IB IntelligentMiner)
• Génération d’un arbre binaire
• Si D est un ensemble contenant des exemples de n classes, l’indice de gini de D, gini(D) mesure
l’impureté de D est définie comme n
gini( D) =1−  p 2j
j =1
où pj est la fréquence relative de la classe j dans D
• Si l’ensemble de données D est divisé selon l’attribut A en deux sous ensembles D1 et D2, l’indice
gini(D) est défini par |D | |D |
giniA (D) = 1 gini( D1) + 2 gini( D2)
|D| |D|
•
gini( A) = gini( D) − giniA ( D)
Réduction de l’impureté :

• L’attribut offrant le plus petit ginisplit(D) (ou la plus grande réduction d’impureté) est choisi pour
diviser le noeud (nécessité de considérer pour chaque attribut toutes les divisions binaires possibles) 25
Indice de Gini (CART, IBM
IntelligentMiner)
• Ex. D a 9 tuples avec buys_computer = “yes” et 5 avec “no”
2 2
9 5
gini( D) = 1 −   −   = 0.459
 14   14 
• Supposons que l’attribut income partitionne D en 10 dans D1: {low, medium} et 4
dans D2
 10   4
giniincome{low,medium} ( D ) =  Gini( D1 ) +  Gini( D1 )
 14   14 

Mais gini{medium,high} = 0.30 est le meilleur puisque c’est le plus petit 26

 Exemple : utilisation de l’indicde de GINI
2 2
9 5
gini( D) = 1 −   −   = 0.459
age income student credit_rating buys_computer  14   14 
<=30 high no fair no
<=30 high no excellent no income → trois possibilités de partionnement
31…40 high no fair yes {low, medium} {high}
>40 medium no fair yes {high, low} {medium}
>40 low yes fair yes
>40 low yes excellent no {high, medim} {low}
31…40 low yes excellent yes
{low, medium} {high}
<=30 medium no fair no
<=30 low yes fair yes  10   4
>40 medium yes fair yes giniincome{low,medium} ( D ) =  Gini( D1 ) +  Gini( D1 )
<=30 medium yes excellent yes  14   14 
31…40 medium no excellent yes
31…40 high yes fair yes
>40 medium no excellent no

gini{medium,high} = 0.30 est le meilleur puisque c’est le plus petit27

Eviter de trop modéliser le jeu d’apprentissage
(overfitting)

L’arbre généré risque de trop refléter le jeu d’apprentissage:

Trop de branches, certaines peuvent représenter des anomalies
Précision faible pour les données nouvelles

2 approches :
pré‐élagage : arrêter la construction de l’arbre tôt = ne pas partitionner un noeud si la
mesure de qualité dépasse un seuil
→ difficulté de fixer le seuil
post‐élagage : supprimer des branches d’un arbre totalement construit
= obtenir une séquence d’arbres progressivement élagués
→ utiliser un jeu de données différents pour décider du meilleur arbre Élagué

28
29
Classifieurs bayésiens: pourquoi?

• Apprentissage probabiliste : calcule explicitement les probabilités des hypothèses, une

des approches les plus pragmatiques pour certains types d’apprentissage

• Incrémental : chaque exemple met à jour la probabilité qu’une hypothèse est correcte.
Des connaissances a priori peuvent être combinées avec des données d’observation.

• Prédiction : probabiliste : prédit plusieurs hypothèses, pondérées par leur probabilité

30
 Théorème de Bayes: concepts de base

Méthode simple et intuitive basée sur le théorème de Bayes

P(H/E) = (P(E/H)P(H)) /P(E)

Où H est l’hypothèse à tester et E l’évidence associée à H, P(H) est une probabilité a priori

Calcul des probabilités conditionnelles à partir des instances du dataset

Exemple : on veut savoir si on peut jouer au golf (H) sachant l’evidence (E) outlook = sunny, temperature =
cool, humidity = high et windy= true
Hypothèse pour pouvoir utiliser le théorême de Bayes : évènements indépendants
cela veut dire que les attributs outlook, temperature, humidity et windy sont indépendants

P(E/H) = P(outlook =sunny/yes)* P(temperature =COOL/yes)* P(humidity=high/yes)* P(windy=TRUE/yes)

31
P(H) → P(play= yes), P(play=no)
Classifieurs
bayésiens:
exemple

modèle
Classification naïve Bayésienne : avantages &
inconvénents

… rend le calcul possible

… mène à des classificateurs optimaux si elle est vérifiée
… mais c’est rarement le cas, car les attributs sont souvent Corrélés

tentative de pallier cette difficulté :

réseaux Bayésiens : combinent le raisonnement Bayésien avec la relation causale entre

les attributs

arbres de décision : considère un seul attribut à la fois, en commençant par le plus

important

Problème des probabilités nulles

33 33
Classifieurs bayésiens: exemple

Calculer aussi P(no|E)

Classifieurs bayésiens: exemple

Play= no pour le nouvel

exemple
Méthodes de classification basées sur les instances

• Apprentissage basé sur des instances :

Stocke le jeu d'apprentissage et effectue le traitement quand une nouvelle instance doit être
classée

• Approches typiques
k plus proches voisins (k nearest neighbors) chaque objet représente un point dans l’espace
régression
loess, approximation locale
Raisonnement à base de cas

36
Algorithme des K plus proches voisins
(KNN)

• Chaque objet est représenté par un point dans un espace à n dimensions

• Les plus proches voisins sont définis en terme de distance (euclidienne, manhattan, …) ou
dissimilarité

• La fonction de prédiction peut être discrète/nominale ou continue

•discrète : valeur la plus fréquente
•continue : moyenne

37 37
 Objectif : classer le nouveau
point test (cercle vert)
Ce point peut être classé à la
première classe des carrés bleus
ou à celle des triangles rouges
Exemple
Deux cas :
Algorithme Si k = 3 (cercle ligne continue) le
KNN point est affecté à la seconde
classe parce qu’il y a 2 triangles
et 1 carré dans le voisinage du
cercle vert.
Si k = 5 (cercle ligne discontinue)
le point est affecté à la première
classe parce qu’il y a 2 triangles
et 3 carrés dans le voisinage du
cercle vert.

38
Algorithme KNN

Input:

D : partition de données – jeu d’apprentissage et valeurs des classes correspondantes

K : le nombre de voisins

d : Une fonction de distance

Méthode :

Pour une nouvelle observation X dont on veut prédire sa variable de sortie y

Faire :
1. Calculer toutes les distances de cette observation X avec les autres observations du jeu de données D
2. Retenir les K observations du jeu de données D les proches de X en utilisation le fonction de calcul de
distance
3. Rendre les valeurs de y des K observations en calculant le mode des y retenues (classe majoritaire)
4. Retourner la valeur calculée dans l’étape 3 comme étant la valeur qui a été prédite par K-NN pour
l’observation X.
Discussion autour de la méthode KNN

• Pondération en fonction de la distance

pondère la contribution de chacun des k voisins en fonction de sa distance à
l’objet à classer plus on est proche

Plus on est proche, plus on a de poids

• Robuste dans le cas de données bruitées

• Problème de dimensionnalité : la distance peut être dominée par des attributs non
pertinents
solution : normalisation des dimensions ou élimination des attributs non
pertinents
40
Critères d’évaluation des classificateurs

Construire la table de contingence ou matrice de confusion

classe prédite
C1 C2

classe C1 a (True positive) c (False negative)

réelle C2 b (False positive) d (True negative)

Précision: a/(a+b) nombre d’assignations correctes sur le nombre total d’assignations (true
positive/(true positive +false positive))
Rappel/ Recall: a/(a+c) nombre d’assignations correctes sur le nombre d’assignations qui
auraient dues être faites (true positive/(true positive+ false negative))
Exactitude /accuracy: (a+d)/(a+b+c+d) (accuracy) validité
Erreur: (b+c)/(a+b+c+d) (error) 41 41
 Estimation des taux d’erreur

• partitionnement
utilisation de jeux indépendants : apprentissage (2/3), test (1/3)
• validation croisée :
diviser les données en k partitions
utiliser k‐1 partitions pour l’apprentissage et la dernière pour le test
précision = nombre d’objets bien classés lors des k itérations / nombre d’objets

• bootstrapping
tirage aléatoire avec remise des objets constituant le jeu d’apprentissage

42