Apprentissage Automatique et Réseaux de Neurones

(AARN)

Chapitre 1 : Introduction
à l’Apprentissage Automatique

BADIÂA DELLAL-HEDJAZI

1
Apprentissage Automatique: Définition

L’apprentissage automatique (Machine Learning) consiste à

construire des programmes informatiques capables d’apprendre
avec de l’expérience acquise via leur environnement ou via un
expert du domaine en question.
Les algorithmes d’apprentissage automatique contiennent en
général deux phases
• Phase d’entrainement : dans cette phase, un modèle est construit à
partir des exemples d’entrainement.
• Phase de test : le modèle construit est utilisé pour étiqueter une
instance de test non-étiquetée.

2
 Domaines d’application de l’AA
• Natural Language Processing (NLP) : RNN, Autoencodeurs
exemples: -Classification articles de presse
- Détection de rumeurs, propos inappropriés
- résumés de texte
- Chatbots
• Détection de fraudes bancaires
• Diagnostic médical.
– Tumeurs bénignes/malines (on utilise généralement :CNN)
– Prédiction de pathologies
• Reconnaissance d’écriture manuscrite
• Véhicules autonomes.
• Reconnaissance vocale.
3
 Processus d’apprentissage

Préparation/ transformation Partitionnement Choix du (ou des)

Acquisition de la base
de données - détection de (entrainement, modèle(s)
d’apprentissage
valeurs aberrantes validation, test) d’apprentissage

Entrainement:
Non
Nouvelles données Optimisation des paramètres
(validation/validation croisée)

Ré-estimation du Comparaison de modèles

Choix final de l’algorithme Base
modèle optimaux /calcul d’erreur de
et du modèle suffisante
(Test sur de nouvelles généralisation sur le jeu de
données) Oui test

4
 Problèmes de l’AA
• Sur-apprentissage (overfitting):
– Problème d’incapacité de généralisation
– Dû à la complexité du modèle par rapport à la quantité de
données et au bruit qu’elles contiennent.
– Algorithmes les plus touchés : arbres de décision et
réseaux de neurones.
– Solutions possibles: Validation croisée, réduire le bruit
dans les données, simplifier modèle (polynomial 
linéaire si possible)

• Sous-apprentissage (underfitting):
– solutions possibles augmenter la
base d’entrainement en évitant le
sur-apprentissage.

5
 Types d’Apprentissage Automatique
Apprentissage
Automatique

Apprentissage Apprentissage Par Apprentissage

Supervisé renforcement Non Supervisé

Classification Régression Exploration de Règles

(valeurs discrètes) (valeurs continues) Clustering
solutions par agents d’association

6
 Apprentissage non supervisé
L’apprentissage non supervisé contrairement à l’apprentissage supervisé,
dispose d’une base d’entrainement dont les données ne sont pas étiquetées
et par conséquent l’algorithme doit regrouper ces dernières dans des classes
les plus homogènes possibles en recherchant des structures naturelles sur
les données.
Autrement dit le but est d’inférer des connaissances sur ces dernières en se
basant sur certaines règles ou critères de regroupement, qui dépendent des
données disponibles à un moment donné et ce sans aucune hypothèse
préalable sur la distribution des données.

7
 Apprentissage non supervisé: Clustering
Exemples:
– Google news : regrouper un ensemble d’articles qui parlent du même sujet.
– Segmentation de marché : découvrir automatiquement les segments du marché puis regrouper les clients
dans les segments adéquats.
– Systèmes de recommandation
Clustering
– Le clustering consiste à étudier les données afin de les regrouper dans des classes de telle sorte à ce que les
données de chaque classe soient les plus semblables possible (exemple : méthode Kmeans).
Algorithme Kmeans

8
Apprentissage non supervisé : Clustering ( Exemple Kmeans)
Exemple: regrouper des individus selon leurs âges. Soit une liste aléatoire d'individus dont les âges sont les suivants :
27 - 51 - 52 - 33 - 45 - 22 - 28 - 44 - 40 - 38 - 20 - 57

K = 3. Les trois premières graines prennent les trois premières valeurs.

Calculer la distance : Valeur point – Valeur graine / AM AM (Amplitude Maximum): écart maximum entre deux valeurs d’âge.
Ici AM= 37 (écart entre 20 et 57) pour chaque graine (27, 51, 52) et tous les autres points de la liste.
On affecte alors chaque point aux différentes graines. Calcul des distances entre chaque
graine et chaque point

Ex: point 51 avec graine 27: (51-27)/37=0.65

On obtient : Graine 1 (27) : 27 - 33 - 22 - 28 - 38 – 20 Graine 2 (51) : 51 - 45 - 44 – 40 Graine 3 (52) : 52 - 57

Calculer nouveaux centroïdes : moyenne arithmétique de chaque groupe (cluster). graine1 : 28 graine2 : 45 graine3 : 54.5
Réitérer le processus précédent à ces nouvelles valeurs, on obtient alors le tableau suivant :

Calcul des distances entre chaque point et

les nouvelles graines (centroïdes)

Graine1 (28) : 27 - 33 - 22 - 28 - 20 Moy.= 26 Graine2 (45) : 45 - 44 - 40 - 38 Moy.= 41.75 Graine3 (54.5): 51 - 52 - 57 Moy.= 53.33
En réitérant une troisième fois le processus, nous voyons qu'il ne modifie plus les affectations. Les clusters finalisés sont:
Cluster 1: 27 - 33 - 22 - 28 - 20 Jeunes majeurs - Centroïde = 26
Cluster 2: 45 - 44 - 40 - 38 Quadragénaires - Centroïde = 41.75
9
Cluster 3: 51 - 52 - 57 Quinquagénaires - Centroïde = 53.33
 Apprentissage non supervisé: Règles d’association
– L’apprentissage (Extraction) de règles d’association consiste à découvrir des
règles liant les données et qui décrivent de grandes portions de données.
Exemple: des personnes qui achètent le produit X ont aussi tendance à acheter
le produit Y.
(les clients qui achètent des œufs et du fromage, achètent aussi des pain)

{Pain} {Dattes}

10
 Apprentissage par renforcement
Permet d’adapter un agent à un environnement en tenant compte de
récompenses/punitions (les renforcements)

11
 Apprentissage supervisé
• Ensemble de données en entrée pour lesquelles nous connaissons
le résultat.
• Construction d’un modèle pour prédire les résultats de nouvelles
valeurs en entrée. Selon le type de la sortie prédite :
– discrète (classification)
– Continue (régression)

• Construire un programme d’apprentissage automatique qui se base

sur des données étiquetées ave leur vérité-terrain par un expert du
domaine.
12
 Apprentissage supervisé: Formalisation
• B : base d’entrainement du problème d’apprentissage supervisé étudié de
taille N.
– B= 𝑋𝑖 , 𝑌𝑖 𝑜ù 1 ≤ 𝑖 ≤ 𝑁 .
• 𝑋𝑖 , 𝑌𝑖 : exemples d’apprentissage
– 𝑋𝑖 l’entrée (input)
• 𝑋𝑖 ∈ 𝐸 ; 𝐸 ensemble d’inputs
• 𝑋𝑖 défini par m descripteurs (features) 𝑋𝑖 = (𝑎1 , 𝑎2 , … , 𝑎𝑚 ) tels que les 𝑎𝑖 ∈ 𝐴 ; 1 ≤ 𝑖
≤ 𝑚.
• 𝐴 espace des descripteurs (qualitatifs, quantitatifs)
– 𝑌𝑖 sortie (output) associée à 𝑋𝑖 où 𝑌𝑖 ∈ 𝑆 ; 𝑆 ensemble d’outputs
• B est divisée en deux sous-ensembles
2
– Tr (training) ensemble des données d’entrainement préparé par un expert 3 𝑁.
1
– Tst (test) ensemble des données 3 𝑁. Tst données jamais rencontrées.

13
 Apprentissage supervisé : Formalisation
• B donc ensemble de couples (entrée-sortie) construits selon une loi sur 𝐸 × 𝑆 à priori
inconnue : 𝑋𝑖 suit une loi L.
• Prédire les classes des entrées en construisant une fonction qui met en lien entre
entrées et sorties
• Fonction f = construction fastidieuse ⇒ f est approchée par un modèle (fonction
d’approximation ou hypothèse)
– 𝐸×𝑆F
– (X,Y) 𝑓መ
• Un algorithme d’apprentissage est élaboré afin de déterminer 𝑓መ en utilisant les
couples de (X,Y) ∈ Tr
መ 𝑁+𝑘 ).
– attribuer à chaque nouvelle entrée 𝑋𝑁+𝑘 ; 𝑘 ∈ ℕ appartenant à Tst son output 𝑓(𝑋
• Ajuster les paramètres de f ⇒ calculer fonction coût
– Exemple |𝑓መ − 𝑌|
– Minimiser le coût

14
Apprentissage supervisé

15
 Apprentissage supervisé
• deux types d’apprentissage supervisé
– régression lorsque 𝑆 ⊂ ℝ,
• Sorties continues
– classification 𝑆 ⊂ 𝐶1 , … , 𝐶𝑙 ; 𝑙 ∈ ℕ.
• Sorties discrètes

16
 Apprentissage supervisé: Classification
• « Soit un ensemble de données d’entrainement avec leur
étiquettes associées (vérité terrain), on veut déterminer la
classe de l’étiquette d’une instance de test non-étiquetée en
apprenant les relations entre les données et les sorties »
• Une classification parfaite est en général impossible, par
conséquent, un classifieur détermine des probabilités pour
chacune des classes possibles.

17
 Apprentissage supervisé: Classification
• Un classifieur est un système d’apprentissage supervisé qui prédit des
valeurs discriminantes, binaires ou qualitatives
• En général, le classifieur renvoie une probabilité qui est comparée à un
certain seuil pour pouvoir affecter l’entrée à une classe donnée.
• Pour une classification binaire :
– la classe 0 aura pour valeur représentative le chiffre 0 et la classe 1 le chiffre 1.
– Le classifieur renvoie des valeurs comprises entre 0 et 1
– Nécessité de définir un seuil pour affecter les valeurs à la classe adéquate ;
– Exemple 0,5
• Pour tout output ≤ 0.5, Xi affecté à la classe 0
• Pour tout output > 0.5 Xi affecté à la classe 1

18
Classification

19
 Vérité terrain

• Une donnée étant étiquetée par le nom de la classe à

laquelle elle appartient,
• La donnée est accompagnée de sa vérité terrain, car
l’étiquetage est fait par un expert du domaine.

20
 Evaluation de classifieur: Matrice de confusion
Métriques de base:
Classe Prédite
 Vrais Positifs VP : éléments de la classe 1
Classe 0 Classe 1 correctement prédits.
 Vrais Négatifs VN : éléments de la classe 0
Classe 0 VN FP correctement prédits.

Observée

Faux Positifs FP : éléments de la classe 0 mal

Classe

prédits.
Classe 1 FN VP
 Faux négatifs FN : éléments de la classe 1 mal
prédits.

21
 Evaluation de classifieur: Métriques avancées
𝑉𝑃
• Exactitude (Accuracy):  Vrais Positifs VP : éléments de la classe 1
𝑡𝑜𝑢𝑠 𝑙𝑒𝑠 𝑒𝑥𝑒𝑚𝑝𝑙𝑒𝑠 correctement prédits.
• Rappel ou Sensibilité ou Taux de VP : proportion  Vrais Négatifs VN : éléments de la classe 0
d’éléments bien classés par rapport au nombre correctement prédits.
d’éléments de la classe à prédire  Faux Positifs FP : éléments de la classe 1 mal prédits.
𝑉𝑃  Faux négatifs FN : éléments de la classe 0 mal prédits.
– 𝑅𝑎𝑝𝑝𝑒𝑙𝑐𝑙𝑎𝑠𝑠𝑒𝑖 =
𝑉𝑃+𝐹𝑁
• Précision : proportion d’éléments bien classés
pour une classe donnée ; Classe Prédite
𝑉𝑃
– 𝑃𝑟é𝑐𝑖𝑠𝑖𝑜𝑛𝑐𝑙𝑎𝑠𝑠𝑒𝑖 = Classe 0 Classe 1
𝑉𝑃+𝐹𝑃
𝐹𝑃
• Taux de FP : 𝑇𝑎𝑢𝑥 𝑑𝑒 𝐹𝑃𝐶𝑙𝑎𝑠𝑠𝑒𝑖
𝐹𝑃+𝑉𝑁
Classe 0 VN FP
• Spécificité :

Observée
𝑉𝑁

Classe
– 𝑆𝑝é𝑐𝑖𝑓𝑖𝑐𝑖𝑡é𝑐𝑙𝑎𝑠𝑠𝑒i = 1 – Taux de FP
𝑉𝑁+𝐹𝑃
𝑉𝑁 Classe 1 FN VP
– Taux de FP = 1− 𝑆𝑝é𝑐𝑖𝑓𝑖𝑐𝑖𝑡é𝑐𝑙𝑎𝑠𝑠𝑒i
𝑉𝑁+𝐹𝑃

𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 𝑥 𝑅𝑎𝑝𝑝𝑒𝑙
• Mesure F = 2
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛+ 𝑅𝑎𝑝𝑝𝑒𝑙

22
 Evaluation de classifieur

• Il est possible de calculer les indicateurs globaux du

système, en calculant les indicateurs de chaque classe puis
la moyenne de toutes les classes :
𝑙
1 𝑉𝑃𝑖
𝑃𝑟é𝑐𝑖𝑠𝑖𝑜𝑛 = ෍
𝑙 𝑉𝑃𝑖 + 𝐹𝑃𝑖
𝑖=1
𝑙
1 𝑉𝑃𝑖
𝑅𝑎𝑝𝑝𝑒𝑙 = ෍
𝑙 𝑉𝑃𝑖 + 𝐹𝑁𝑖
𝑖=1
l nombre de classes :
23
 Evaluation de classifieur: Courbe ROC

• Courbe ROC : Receiver Operating Characteristic curve

• La courbe ROC représente un tracé des vrais positifs en fonction des faux positifs dans le cadre d’une
classification binaire.
• Cette courbe trace les couples (VF, FP) pour chaque valeur du seuil.
• L’aire définie sous la courbe permet d’évaluer la qualité du classifieur. (AUC: Area Under the Curve)
– Plus l’aire s’approche de 1 plus le classifieur est bon .
– Inconvénient majeur:
• Les indicateurs sont calculés sur les données d’entrainement et fournissent par conséquent une évaluation optimiste du modèle.
• Solution possible: utiliser la validation croisée.
• La courbe ROC trace la sensibilité (taux de vrai positif axe abscisses) en fonction du taux de faux négatif (axe des
ordonnées) pour un ensemble de seuils entre 0 et 1.
• La courbe précision/rappel:
– Trace la précision en fonction du rappel. 24
Courbe ROC: Exemple

25
 Evaluation de classifieur: Validation

– Division entrainement / test :

2
• les données du problème sont divisées en deux groupes : entrainement (3 des
1
données) sur lequel le modèle est entrainé et test (3 restant des données).
• Les mesures de performances sont calculées dans les deux phases puis
comparées. Si celles de la phase d’entrainement sont significativement
supérieures à celles de la phase test, alors il y a sur-apprentissage.
• Cette technique est efficace, sauf si les données sont limitées. Il peut alors
manquer certaines informations sur les données qui n’ont pas été utilisées pour
l’entraînement, et les résultats peuvent donc être hautement biaisés.

26
 Evaluation de classifieur: Validation croisée
– Validation croisées à k-plis (k-fold) : appelée aussi LOO (en anglais Leave One Out):
• Les données sont divisées en k sous-groupes appelés plis.
• Un pli choisi aléatoirement sur les k est laissé comme ensemble de test et le modèle est
entrainé sur les k-1 restants.
• Le processus est répété k fois.
• Les moyennes des mesures de performances d’entrainement sont comparées à celle des tests
pour détecter un éventuel sur-apprentissage.
• Elle permet d’assurer que toutes les observations de l’ensemble de données original aient la
chance d’apparaître dans l’ensemble d’entraînement et dans l’ensemble de test

27
Quelques algorithmes: KPP ( k-plus proches voisins)
 En anglais K Nearest Neighbors (KNN), est un des algorithmes d’apprentissage supervisé les plus
simples cependant très performant. Il est utilisé pour la classification et en régression.
 KNN est un algorithme d’apprentissage paresseux et non paramétrique :
- non paramétrique : ne fait aucune hypothèse sur la distribution des données
- paresseux : l’algorithme ne passe pas par une phase d’apprentissage explicite et donc manque de
généralisation autrement dit toutes les données d’apprentissage sont utilisées durant la phase de test.
 Les données d’entrainement étant étiquetées par leur classe, l’idée de base des KNN est de trouver
un groupe d’objets, de « voisins », parmi ces derniers qui sont les plus proches de l’objet test. Ce
dernier se voit assigné la classe majoritaire parmi celles de ses voisins.
 Trois éléments clés : la base de données d’entrainement étiquetées, une distance ou une métrique de
similarité entre les objets et la valeur de K le nombre des plus proches voisins.
 Le calcul de la similarité se fait via plusieurs distances entre autres l’euclidienne, la distance de
Hamming, Minkowski.
 Le choix du nombre K est crucial et dépend fortement des données. En effet, la valeur de K (KϵN) est
choisie de sorte à minimiser l’erreur de classification. Plusieurs techniques peuvent être utilisées (de
validation croisée par exemple) pour choisir un bon K.

28
 Quelques algorithmes: KNN (K-Nearest Neighbors)
Algorithme KNN D={(x’,c)} : dataset
Soit x l’exemple : qu’on souhaite classer
Début
Pour chaque ((x’,c) ∈ 𝑫) 𝒇𝒂𝒊𝒓𝒆
Calculer la distance dist(x,x’) # trier liste distances et prendre les k 1eres
Fait
Pour chaque {x’ ∈ kppv(x) } faire
compter le nombre d’occurrences de chaque classe
Fait
Attribuer à x la classe majoritaire (Si régression renvoyer la moyenne des étiquettes)
FIN

29
 Quelques algorithmes: KNN (K-Nearest Neighbors)
Exemple : KNN avec K=3 (3-Nearest Neighbors) Distance Euclidienne:

Les 3 plus proches au client David sont :

John  No
Rachel  Yes
(35 − 37)2 +(35 − 50)2 +(3 − 2)2 = 15,16 Nellie  Yes
(22 − 37)2 +(50 − 50)2 +(2 − 2)2 = 15
Classe majoritaire : Yes
(63 − 37)2 +(200 − 50)2 +(1 − 2)2 = 152,23
D’où prédiction de la classe de David est: Yes
(59 − 37)2 +(170 − 50)2 +(1 − 2)2 = 122
Response = Yes d’où client David est Loyal
(25 − 37)2 +(40 − 50)2 +(4 − 2)2 = 15,74
30
 Quelques algorithmes: Arbres de décision
• « Un arbre de décision (en anglais DT pour Decision Tree)
modélise une hiérarchie de tests sur les valeurs d’un ensemble
de variables : des descripteurs. À l’issue de ces tests, le
prédicteur produit une valeur numérique ou choisit un
élément dans un ensemble discret de conclusions. »
• Pourquoi les arbres de décision:
- Faciles à comprendre
- Etroitement liée à l’approche « diviser pour régner »

31
 Quelques algorithmes: Arbres de décision

• Pour un problème donné, nous disposons d’un échantillon dont X est une donnée
quelconque définie par n descripteurs ; X = (x1, x2, …, xn ).
• Et soit Y la variable à prédire qui peut être soit qualitative et donc définie par un
ensemble de classes Y = (C1, C2, …, Cn), soit quantitative et donc définie par un
ensemble de valeurs possibles (ℝ par exemple).
• Un arbre de décision est un classifieur représenté sous forme d’arbre tel que :
• Le nœud racine et chaque nœud intermédiaire représentent un test sur les
descripteurs (attributs): les xi définis précédemment.
• Chaque valeur possible du descripteur testé (le nœud) est associée à une branche qui
est étiquetée par cette valeur.
• A chaque classe ou valeur prédite est associée une feuille cette valeur en question ; les
Ci ou les valeurs possibles de Y.

32
 Quelques algorithmes: Arbres de décision
Exemple:

33
 Quelques algorithmes: Arbres de décision
Algorithme ID3
Algorithme DT (T: arbre, E: Dataset)
{
E T
SI tous les exemples de E sont dans la même classe (Data pure)
ALORS Affecter l’étiquette Ci au nœud courant. FIN.
SINON (Data non pure) V1 V2 Vn
Sélectionner le meilleur attribut A avec les valeurs v1,…, vn
Partitionner E selon v1,…, vn en E1, E2, …, En
E1 E2 T2 En Tn
Pour j=1 à n DT(Tj,Ej) T1

34
 Arbre de décision : Algorithme ID3
9 9 5 5
Jour Ciel Températur Humidité Vent Jouer E(S)= −( ∗ 𝑙𝑜𝑔2 + ∗ 𝑙𝑜𝑔2 ) = 0,94
14 14 14 14
e tennis ?
1 Soleil Chaud Elevée Faible Non
1) G(S,Ciel)=?
2 Soleil Chaud Elevée Fort Non 2 3 4 0 3 2
Ciel: Soleil { :O, :N} ; Couvert { :O, :N} ; Pluie { :O, :N}
3 Couvert Chaud Elevée Faible Oui 5 5 4 4 5 5
5 2 2 3 3 5 3 3 2 2
4 Pluie Moyen Elevée Faible Oui G(S,Ciel)= 0,94-[ (- log 2 - log 2 ) + (- log 2 - log 2 )=0,247
14 5 5 5 5 14 5 5 5 5
5 Pluie Frais Normale Faible Oui 2) G(S,Température) = 0,029
6 Pluie Frais Normale Fort Non 3) G(S,Humidité) = 0,152
7 Couvert Frais Normale Fort Oui 4) G(S, Vent) = 0,048
8 Soleil Moyen Elevée Faible Non
L’attribut Ciel est le plus discriminant (le plus grand Gain)
9 Soleil Frais Normale Faible Oui
10 Pluie Moyen Normale Faible Oui On continue le traitement de façon récursive pour les sous-ensembles
11 Soleil Moyen Normale Fort Oui obtenus à partir de Ciel et on obtient l’arbre final suivant:
12 Couvert Moyen Elevée Fort Oui
13 Couvert Chaud Normale Faible Oui
14 Pluie Moyen Normale Fort Non

Entropie : E(S) = -σ𝒄𝒊=𝟏 𝒑𝒊 ∗ 𝐥𝐨𝐠 𝟐 𝒑𝒊

𝑺
Gain : G(S, A) = E(S) - σ𝒗 ∈𝒗𝒂𝒍𝒆𝒖𝒓(𝑨) 𝒗 ∗ 𝑬(𝑺𝒗 )
𝑺
35
 Arbre de décision
Ciel

Soleil Couvert Pluie

Humidité Oui Vent

Elevée Normale Fort Faible

Non Oui Non Oui

36