Data Mining

CHIII: Apprentissage supervisé

Tableau de données
Statut des variables
Principes de l’apprentissage supervisé
Apprentissage Bayésien
Cas de deux classes

• Classification de deux classes: positive, négative.

Apprentissage en 2 étapes:
• Estimer la probabilité d’affectation 𝑃(𝑌/𝑋)
• Prédire 𝑌 = + 𝑠𝑖 𝑃 𝑌 = +Τ𝑋 > 𝑃(𝑌 = −Τ𝑋)
Généralisation su K classes
Théorème Bayésien
𝑃 𝑋Τ𝑌 𝑃(𝑌)
• Théorème Bayésien: 𝑃(𝑌ൗ𝑋) =
𝑃(𝑋)

Objectif:

X Y

avec:
Exemple
• P(Y/X) reflète la confiance qu’on donne pour que X soit une pomme
sachant qu’elle est rouge et arrondie=> Probabilité à postériori
Y/X
• P(Y) probabilité qu’un exemple donné soit une pomme

• P(X|Y) probabilité que X: rouge et arrondie sachant que c’est une pomme

• P(X) probabilité de l’échantillon

Exemple

• Pour faire la classification d’un nouvel échantillon ( à savoir dans

l’exemple on veut classer un nouveau fruit), que doit-on faire ??
• On calcule le P(Y/X) pour chaque classe Y
• On compare la probabilité et on affecte X à la classe ayant la plus grande
probabilité

Estimation de P(X), P(Y) et P(X/Y) => Phase d’apprentissage

Naïve Bayes Classifier
• On suppose qu’on a n Classes 𝐶1 , 𝐶2 , … , 𝐶𝑛 . Sachant un échantillon X
inconnu, Le classifieur calcule les probabilités à postériori P(𝐶𝑖 /X).

• Maximise => maximise

=> Indépendance entre les descripteurs

Les hypothèses de base pour un algorithme Bayésien:
Utilise tous les descripteurs pour faire une décision
Tous les descripteurs ont la même importance.
Tous les descripteurs sont indépendants les uns des autres.
 Exercice

• On a des nouveaux mesures pour le jour,

on veut savoir si le mache va se jouer ou
non.

• Quelles sont les Y et le X dans cet

exemple?
Jeux de données pour le
matche de tennis
• On calcule 𝑃 𝑦𝑒𝑠Τ𝐸 𝑒𝑡 𝑃 𝑦𝑒𝑠Τ𝐸 où E est l’échantillon suivant:

• Les descripteurs de E sont:

o E1 avec outlook=sunny
o E2 avec temperature =cool
o E3 avec humuidity= true
o E4 avec windy=true

• Les descripteurs sont considérés comme indépendants sachant la classe

=> On peut faire la multiplication des probabilités de chacun des
descripteurs sachant la classe
=>
Pour le nouveau jour la probabilité d’avoir play = no et 4 fois plus
grande.
 Problème du Naïve Bayes
• On suppose que le descripteur (outlook=sunny) est associé (play=no) et
(outlook=sunny) n’a jamais coincide avec (play = yes).
P(play = yes|outlook = sunny) = 0 et P(play = yes|outlook = sunny) =1
𝑃(𝑋1Τ𝑌𝑒𝑠)𝑃(𝑋2Τ𝑌𝑒𝑠)𝑃(𝑋3Τ𝑌𝑒𝑠)𝑃(𝑋4Τ𝑌𝑒𝑠)
 P(yes|X) =
𝑃(𝑋)
P(yes|X) = 0
• Peut arriver dans certains cas d’apprentissage et donne une mauvaise
prédiction pour le nouvel échantillon.
• Solution: On utilise l’estimateur Laplacien pour calculer la probabilité
=> On ajoute 1 pour chaque numérateur et k pour le dénoménateur avec
K le nombre de descripteurs
 Correction de Laplace
• Exemple sur les données après modification (P(play = yes|outlook = sunny) = 0

• La correction de Laplace ajoute 1 au numérateur et 3 au dénominateur

• On s’assure que même si le descripteur

(variable) n’est pas arrivé dans l’ensemble
d’apprentissage, il aura une faible probabilité
mais, pas nulle.
 Correction de Laplace
• Correction de Laplace sur les données originaux (P(play = yes|outlook = sunny) = 0
Traitement des valeurs manquantes
• Que faire lorsqu’on a une donnée à classer avec une variable ayant
valeur manquante?
On doit omettre la variable et ne pas l’intégrer dans le calcul.

333 9
9 9 9 14 0,0238
𝑃 𝑦𝑒𝑠 𝑋 = =
𝑃 𝑋 𝑃(𝑋)
143 5
5 5 5 14 0,0343
𝑃 𝑛𝑜 𝑋 = =
𝑃 𝑋 𝑃(𝑋)
Que pensez-vous de ces résultats par rapport à ceux retrouver lorsque la
valeur de la variable outlook existe?
Les probabilités dans ce cas sont plus grandes puisqu’il y a une valeur manquante, mais les résultats
de la comparaison ne changent pas puisqu’elle ne rentre pas dans le calcul dans la probabilité à
postériori des deux classes
Traiter les variables numériques

• On veux classer l’échantillon suivant:

 • Comment on peut calculer les probabilités??
P(temperature=66|yes) ?? P(temperature=66|no)??
Problème dans ce cas P(temperature=66|yes) =0

On assume que chaque variable numérique a une distribution de probabilité normal

(Suit la loi Gaussienne)

Alors la probabilité de la température prend une valeur dans une

région entre 64 et 68.
 X
X X

X
X X
Donc P(yes|X) <P(no|X) alors play = no
Réseau de neurones
Réseau de neurones (NN)

• Le réseau de neurones est composé de couches de neurones

interconnectés.
• Le message passe par les connexions entre les neurones
Réseau de neurones (NN)
• Chaque connexion entre les neurones présente un poids (weight).
• L’entrée de chaque neurone provient des sorties des neurones qui lui
sont connectés.
• La sortie de chaque neurone présente son entrée et le poids de la
connexion.
Réseau de neurones (NN): Apprentissage

• Apprentissage: La procédure de modifier les poids pour effectuer une

tache donnée.
• L’apprentissage peut également se faire par le changement de
quelques connexions. => Ajout et élimination des connexions entre
les neurones.
Réseau de neurones (NN): Model

• La connexion entre deux neurones 𝑖 et 𝑗 est définie par le poids 𝑤𝑖𝑗

• 𝑤𝑖𝑗 => La force de la connexion entre les deux neurones
• Chaque neurone calcule la somme des entrées des différents
neurones pondérée par le poids de leurs connexions.
• Un poids spécial est également ajouté à cette somme pondérée.
Fonction d’activation
𝑦𝑖 = 𝑓(𝑤11 𝑥11 + ⋯ + 𝑤1𝑛 𝑥1𝑛 + 𝑏1 )
• Dans le cas de classification : une classe 1 et une classe -1:
➢La fonction la plus basique est 𝑓 𝑦𝑖 = 𝑠𝑖𝑔𝑛(𝑦𝑖 ) => Aucune idée sur le degré
de confiance

1
➢La fonction 𝑠𝑖𝑔𝑚𝑜𝑖𝑑(𝑦𝑖 ) = => traduit la sortie en probabilité
1+𝑒 −𝑦𝑖

➢La fonction Relu = max(𝑦𝑖 , 0)

Les étapes d’apprentissage du réseau de
neurones
1. Construction du réseau de neurone (nombre de neurones, nombre
de couches)
2. Apprentissage du réseau
3. « Purning » le réseau
4. Interprète le résultat
Apprentissage du réseau

• L’objectif de l’apprentissage est d’avoir des poids qui font que la

prédiction des échantillons d’apprentissage seront bien classés.
• Les étapes:
• Les poids sont fixés au début de façon aléatoire
• Les échantillons d’apprentissage sont donnés un par un.
• Calcul des fonctions d’activation des nœuds.
• Calcul du vecteur de sortie.
• Ajustement des poids suivant le calcul d’erreur (label – vecteur_obtenu).
Network Pruning
• La connexion de tous les neurones augmente le nombre de poids à
gérer.
• n neurones en entrée, h neurones dans la couche cachée et m
neurones dans la couche de sortie représente un nombre de h(n+m)
liens [poids].

Solution:
Pruning : éliminer des liens entre les neurones sans affecter la
classification.
 Exemple
Base d’apprentissage
Comment on définit l’architecture du
réseau de neurones??

Un neurone pour chaque

classe
Neurones en sorties

Couche cachée

Neurones en entrées
Un neurone
Un neurone pourpour
chaque
descripteur
• FeedForward : chaque neurone reçoie en entrée les sorties des
neurones de la couche précédente => Dans le cas d’un réseau
entièrement connectée, chaque neurone sera connecté avec les
neurones de la couche précédente.
• Initialisation des poids se fait de façon aléatoire avec des valeurs
entre [-1,1]
• Modèle : somme pondérée des entrées + biais sur laquelle est
appliquée une fonction de transfert différentiable
Architecture: nombre de neurones
• Données numérique : un neurone pour chaque entrée
• Données catégorique:
• Nominal: un neurone pour chaque valeur de l’entrée (one-hot encoding)
Exemple: color ==> « red », « green », « blue »
Red Green Blue
1 0 0
0 1 0
0 0 1

• Ordinal : un neurone pour la variable et la valeur code les différents rangs

Exemple: place ➔ « first », « second », « third »
First : 1, second: 2, third :3

➢Combien de neurones doit-on avoir pour le vecteur weather ?

Exemple: vecteur1: sunny, hot, high, false => 100 100 10 10

On peut coder autrement, par exemple la variable Windy peut être représenter par un seule
neurone et prend comme valeur 0 ou 1.
Architecture: nombre de neurones

On peut coder autrement, on peut avoir un seule neurone pour coder la sortie Yes or No (1 ou 0)
Architecture: nombre de neurones
• Nombre de neurone dans la couche cachée ???
=> la réponse n’est pas évidente, il faut tester et affiner selon le
taux d’erreur obtenu
➢Un taux élever de couches et de neurones => beaucoup de poids
Overfitting
Le réseau n’arrive pas à généraliser
➢ Un taux bas de neurones => peu de poids
Underfitting
 Le réseau n’arrive pas à apprendre la relation entre l’entrée et la sortie.

Idée: On peut commencer par une couche cachée avec n neurones

𝑒𝑛𝑡𝑟é𝑒𝑠𝑛𝑒𝑢𝑟𝑜𝑛𝑒 +𝑠𝑜𝑟𝑡𝑖𝑒𝑛𝑒𝑢𝑟𝑜𝑛𝑒𝑠
𝑛=
2
Apprentissage par Backpropagation
Apprentissage par backpropagation:
Pour chaque exemple d’apprentissage p:
• On calcule la sortie a et on calcule l’erreur par rapport au label d.
• On met à jour les poids du réseau pour minimiser l’erreur
Jusqu’à erreur de tous les échantillons < Seuil
• Backpropagation ?? Ajustement des poids par un retour en arrière
(des neurones de sorties vers les neurones d’entrées) en ajoutant le
changement des poids ∆𝑤

• Une fonction classique pour calculer l’erreur E est la somme au carré

de l’erreur.
• E : erreur pour un échantillon d’apprentissage
• di: la sortie désirée par le neurone i
• ai: la valeur obtenue par le neurone i

Comment peut-on calculer le changement des poids???

• On peut considérer la backpropagation comme une optimisation de la
recherche dans l’espace des poids.
• Objectif: retrouver l’ensemble des poids pour lesquels l’erreur est minimal
• Méthode de recherche : réduit l’erreur pour chaque exemple d’apprentissage.

𝜕𝐸
• Réduire la fonction d’erreur => Faire des petits pas (gradient )
𝜕𝑤
• Une fonction décroit rapidement lorsque la direction du mouvement est
dans la direction du négatif du gradient.
=> Pour ajuster les poids, on effectue des petits pas dans le sens inverse du
sens du gradient jusqu’à trouver un minimum local de la fonction de l’erreur E
 • L’algorithme de « backpropagation » ajuste les poids en projetant vers
l’arrière l’erreur, d’une couche à une autre en partant de la couche de
sortie vers la couche d’entrée.
• Trois approches sont utilisées:
• Approche descente de gradient classique (batch): Les poids sont calculés
après le passage de tous les exemples d’apprentissage. Une moyenne des
gradients sur tous les échantillons d’apprentissage est effectuée pour faire la
mise à jours des poids, au bout d’une « epoch ». Plusieurs « epochs » sont
nécessaires pour améliorer les résultats. ➔ epoch ???
-> On suppose que dataset = 1000 exemples
epoch1

epoch2 Après la 1ERE epoch, on fait une mise à jour des poids

L’application de plusieurs epochs améliore les poids

epoch3
 • Approche incrémentale (online) : Les poids sont ajustés après chaque
exemple d’apprentissage.
• Approche descente de gradient par lot (Mini-batch) : Les poids sont calculés
après le passage d’un ensemble des exemples d’apprentissage. Une moyenne
des gradients sur l’ensemble des échantillons du lot est effectuée pour la mise
à jour des poids.

Le traitement par lots:

➢ Améliore les problèmes de mémoire qu’on peut rencontrer dans l’approche classique. Il permet de se
contenter de charger partiellement les données en mémoire au fur et à mesure.
➢ Améliorer la convergence en réduisant le nombre de passage sur la base entière.
➢ Le plus utilisé dans les problèmes d’apprentissage
➢ Le choix de la taille de batch est purement expérimental.
Mise à jour des poids
• : Poids du neurone p vers le neurone q à l’instant t
• Mise à jour du poids

le pas de changement avec :

𝑜𝑝 𝑠𝑜𝑟𝑡𝑖𝑒 𝑑𝑒 𝑙𝑎 𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛 𝑑′ 𝑎𝑐𝑡𝑖𝑣𝑎𝑡𝑖𝑜𝑛 𝑑𝑢 𝑛𝑒𝑢𝑟𝑜𝑛𝑒 𝑝 et
𝛿𝑞 (𝑒𝑟𝑟𝑒𝑢𝑟 𝑑𝑢 𝑛𝑒𝑢𝑟𝑜𝑛𝑒 𝑞)
• 𝛿 est calculé de deux façon différentes:
Mise à jour des poids
• La fonction sigmoid :
• Dérivée de la fonction sigmoid :

• Donc l’erreur de la backpropagation avec sigmoid comme fonction

d’activation
KNN
KNN
• Dans la classification K-NN, la base d’apprentissage est utilisée pour
classer chaque nouvel échantillon.
• Il n’y a pas de model créer au cours de l’apprentissage => Lazy
Learning
Simple Nearest Neighbour
• La phase d’apprentissage consiste à trier les échantillons
d’apprentissage dans une liste.
• Pour classer un nouvel échantillon, une comparaison entre ce dernier
et la liste des échantillons d’apprentissage est effectuée. Le label de
l’échantillon le plus proche (similaire) sera affecté au nouvel
échantillon.

=> Différentes mesures de similarités et de distances peuvent être

utilisées.
K- nearest neighbour
• Le KNN est une variante du simple Nearest Neighbour. Au lieu de voir
l’échantillon d’apprentissage le plus proche, on cherche les k
échantillons les plus proches au nouvel échantillon.
• Pour affecter un label, au nouvel échantillon on lui donne le label de
la majorité des k voisins.
Agglomerative Nearset Neighbour
• Les échantillons d’apprentissage sont mis ensembles dans des
groupes, tout au long de l’apprentissage.
• Les étapes de l’Apprentissage:
• Chaque groupe a un centre c et un rayon r et un label qui correspond aux
échantillons du groupe. Initialement chaque échantillon forme à lui tout seul
un groupe.
• Chaque deux groupes ayant le même label et une distance inférieur à certain
seuil sont mergés ensemble pour former un nouveau groupe➔ Donc, un
nouveau rayon r et un nouveau centre c.
Agglomerative Nearset Neighbour
➢L’affectation d’un nouvel échantillon se résume à trouver le groupe
d’échantillons le plus proche.
➢La phase d’apprentissage de l’agglomerative Nearset Neighbour est
plus lente par rapport au KNN.
➢Pas besoin de stocker tous les échantillons, il suffit seulement
d’enregistrer le centre et le rayon de chaque groupe.
➢Dans le cas où tous les échantillons sont distants les uns des autres,
nous revenons au cas du Nearest Neighbour
➢Dans le cas où tous les échantillons sont proches, nous obtenons un
nombres de groupes égale au nombre de classes.
Problème de chevauchement
• Un problème de chevauchement peut survenir dans certains cas.
=> Un groupe qui s’agrandit et fait un chevauchement avec un
groupe ayant un label différent diminue la précision de la prédiction.

Solution:
=> Arrêter la croissance d’un groupe si elle entraine un chevauchement
avec un groupe ayant un label différent.
Mesure des distances
Données catégoriques
• Les mesures de similarité est l’inverse des mesures des distances.

• Les mesures de similarité pour les données catégoriques: