Pattern

recognition
&
Machine Learning
Par : Prof. Amina RADGUI
Département Systèmes de Communication

Pour tout besoin, contactez moi :

Par e-mail. : radgui@[Link].
Au bureau. : Bâtiment D, bureau 110
Par téléphone : 0665651648

1
Objectifs du cours
1. Objectif général:
Apprendre comment la machine apprend

2. Objectifs spécifiques :
1. Découvrir les fondements de l’apprentissage automatique
2. Explorer les principaux algorithmes de l’apprentissage automatique
3. Etudier en pratique des exemples d’applications de l’apprentissage automatique

2
Ressources
Cours :
Diapos et notes du cours

TP:
Séries de Travaux Pratiques (Python)

Référence :
Christopher Bishop, Pattern Recognition and
Machine Learning, Springer, 2007 3
Planification temporelle

?
4
 Plan
I. Introduction

II. Apprentissage supervisé

1. Régression

2. Classification

2.1 Régression logistique

2.2 Machines à support vectoriel SVM

2.3 Plus proches voisins KNN

III. Apprentissage non supervisé

IV. Apprentissage profond

5
Intelligence Artificielle
§ L’intelligence artificielle est développée à la base de l’apprentissage automatique
§ L’IA: Comportements et propriétés particulières à des programmes lui
permettant de défier la réflexion humaine par leur capacité à rendre la machine
capable de :
vApprendre
vDéduire
vRéagir
Devant des états non préalablement programmés.

6
Contexte générale - Motivation
§ L’apprentissage automatique consiste à donner à la machine la capacité d’apprendre
sans la programmer de façon explicite
§ C’est une sous-discipline de l’intelligence artificielle en forte croissance et entrain de
révolutionner tout les domaines
§ Applications
§ Vision par ordinateur
§ Reconnaissance de caractères, de visages, d’objets, mouvements (Kinect)
§ Traitement automatique du langage
§ Système de questions-réponses (IBM Watson), reconnaissance de la voix (Siri),
§ Classification de documents (pourriels), traduction automatique
§ Robotique
§ Conduite automobile automatisée (Google car)
§ Prédiction financière, recommandation de livres, de films (Netflix)
§ ……et bien d’autres
7
Applications de l’apprentissage automatique

8
 Motivation par un exemple
Exemple : Comment reconnaître des caractères manuscrits ?
------------------------------------------------------------------------------------------------
Solution 1 : Par énumération de règles ?
‣ si intensité du pixel à la position (10,3) est plus grand que 50, et le pixel à la position ...
alors c’est un «2»
Inconvénient : Trop fastidieux et il est très difficile de couvrir tous les cas

Solution 2 : Donner à l’ordinateur la capacité d’apprendre à le faire et le laisser faire des essais et
apprendre de ses erreurs
‣ Le domaine de l’apprentissage automatique s’intéressant à l’étude des algorithmes de la solution 2.

9
 Un algorithme d’apprentissage
‣ Entraîne un modèle à partir d’un ensemble d’entraînement, pouvant faire des prédictions sur

de nouvelles données
‣ A des hyper-paramètres qui contrôlent la capacité du modèle entraîné, choisis à l’aide d’une
procédure de sélection de modèle
‣ Mesure sa performance de généralisation sur un ensemble de test (selon une fonction
d’erreur qui peut être différente de la perte d’entraînement)
‣ Aura une meilleure performance de généralisation si la quantité de données d’entraînement
augmente
‣ Peut souffrir de sous-apprentissage (pas assez de capacité) ou sur-apprentissage (trop de
capacité)
10
 Type d’apprentissage
Il existe différents types d’apprentissage
I. Apprentissage supervisé : il y a une cible à prédire
E= {(x1,y1), ... , (xn,yn)}
‣ Classification : la cible est un indice de classe y ∈{1, ... , K}
‣ Régression : la cible est un nombre réel y ∈ ℝ

II. Apprentissage non-supervisé : La cible n’est pas fournie

E= {x1, ... , xn}
‣ Partitionnement de données / clustering

Ou D’autre types d’algorithmes dites d’Apprentissage par renforcement (non couvert dans ce cours)
11
 Techniques d’apprentissage Machine

Apprentissage supervisé : développe un modèle prédictive à la base de données et leurs réponses.

12
Apprentissage non-supervisé : groupe et interprète les données basé seulement sur des données d’entré.
Apprentissage supervisé

1
3
 Techniques d’apprentissage Machine
Les problèmes de prédiction d'une variable
quantitative sont des problèmes de régression
tandis que les problèmes de prédiction d'une
variable qualitative sont des problèmes de
classification.

Exemples :
• Prix de l’immobilier
• Prix des actions en bourse
• Météo
• Reconnaissance d’objet
• Recommandation d’amis
• Choix de films, news, produits
• …. 14
 Apprentissage supervisé
èDéveloppe un modèle prédictive à la base de données et leurs réponses.
Hypothèse : Les exemples de la base d’entrainement
(dataset) sont représentatifs du problème général que l’on
Test
souhaite faire apprendre à la machine.

Objectif de l’apprentissage supervisé : Introduire une

fonction qui prédit les réponses associés à de nouvelles
Algo. observations en commettant une erreur de prédiction la plus
Dataset
apprentsg Modèle faible possible.

En pratique : on fournit à l’algorithme des données

Fonction d’erreur
d’entraînement et l’algorithme retourne un «modèle»
capable de généraliser à de nouvelles données
Sortie
prédite Le modèle choisit la fonction qui réalise la plus faible erreur
moyenne de prédiction sur une base d’entrainement.
15
Algorithme d’Apprentissage Supervisé

Consiste à définir quatre éléments :

1. Les données d’entraînement (Dataset)

2. Le modèle d’apprentissage

3. La fonction d’erreur

4. La méthode de minimisation d’erreur

16
1. Données d’entrainement (datasets)
Ensemble d’observations, mesures, exemples retenus du processus qu’on vise à faire apprendre à
la machine.
Cet ensemble est composé des entrés (features, variables, paramètres) et des sorties (cible, target,
label) noté de la même façon dans tout les algorithmes
n Chaque entré est notée :
(𝐢)
𝐱𝐣 avec i=1,…,m et. j=1,…,n
𝟏 𝟏
x1 x2 … xn Y Élément de la matrice : 𝐱𝟏 … 𝐱𝐧
1∗3
𝐗= ⋮ ⋱ ⋮ ∈ ℝ
x(1)1 x(1)2 x(1)n y(1) 𝐦 𝐦
𝐱𝟏 … 𝐱𝐧
…. .. .. .. ..
m … .. .. .. ….
Chaque sortie est notée : (𝐢)
𝐲 𝑎𝑣𝑒𝑐 𝑖 = 1, … , 𝑚.
Élément du vecteur : 𝐲𝟏
x(m)1 x(m)2 x(m)n y(m) ⋮ 1∗?
𝐘= ∈ ℝ
⋮
𝐦 17
𝐲
[Link]èle d’apprentissage
§ Le modèle d’apprentissage est une fonction mathématique notée 𝒉𝜽 𝒙
§ Il est paramétré par des inconnues notées 𝜽
§ Le nombre de paramètres du modèle dépend de l’algorithme d’apprentissage utilisé et la taille des
entrés.

[Link] fonction d’erreur

§ Souvent appelée la fonction cout et notée 𝑱 𝜽

§ Elle quantifie le désaccord entre la prédiction de sortie donnée par la fonction que l’on souhaite
apprendre pour une observation de la base d’apprentissage et sa réponse associée

[Link] de l’erreur
§ Une phase de recherche des paramètres 𝜽 minimisant au mieux la fonction d’erreur 𝑱 𝜽
§ Plusieurs approches sont proposées. 18
Régression

1
9
 Régression linéaire
§ La régression est un ensemble de méthodes statistiques très utilisées pour analyser la relation d'une variable y par

rapport à une x ou plusieurs autres xi.

§ Un modèle de régression linéaire est un modèle de régression qui cherche à établir une relation linéaire entre une

variable, dite expliquée, et une ou plusieurs variables, dites explicatives. On parle aussi de modèle linéaire ou

de modèle de régression linéaire.

§ Le modèle de régression linéaire est souvent estimé par la méthode des moindres carrés, maximum de vraisemblance

ou bien d’autres méthodes.

20
Régression linéaire à une variable
Données d’entrainement
Surface (x) Prix (y)
120 100
112 130
50 60
63 35
70 60
78 64
90 100
92 92
100 120
106 80
125 160
50 25

Problème : A partir des observations disponibles, quel est le modèle d’apprentissage qui permet
d’affecter une cible à une nouvelle entrée (pour chaque entrée (surface) est affectée un prix). 21
 Dans le cas de la régression linéaire, le
modèle est une droite d’équation :
Régression linéaire 𝐲 = 𝐚𝐱 + 𝐛

Best fit line

Q: Quelle est la droite la plus adéquate au sens de la régression?

22
Régression linéaire
Etant donné :
Les entrés : x=[120, 112, 50, 63, 70, 78, 90, 92, 100, 106, 125, 50]
Les Sortie y=[100, 130, 60, 35, 60, 64, 100, 92, 120, 80, 160, 25]
Le nombre de features n=1
Le nombre de mesures m=12
Le modèle de régression linéaire est supposé correspondre à :
𝒉𝜽 𝒙 = 𝜽𝟏 𝐱 + 𝜽𝟎
Tel que l𝐞𝐬 𝐩𝐚𝐫𝐚𝐦è𝐭𝐫𝐞𝐬 (𝜃O , 𝜃? ) minimise la fonction d’erreur :
x 𝐦
𝟏 𝐢 𝐢 𝟐
𝐉 𝛉𝟎 , 𝛉𝟏 = V 𝐡𝛉 𝐱 −𝐲
𝟐𝒎
𝐢Y𝟏

è Q : Comment minimiser J 𝜽𝟎 , 𝜽𝟏 ? 23
Minimisation de la fonction d’erreur
En 1d :

𝛉𝟒
𝐽(𝜃)
𝐽(𝜃? )=0.25
𝐡𝛉 𝐱
𝛉𝟏 𝐽(𝜃[ )=5.93
𝐽(𝜃\ )=22.5
𝐽(𝜃] )=5.43
𝛉𝟐

𝛉𝟑 𝛉𝟑 𝛉𝟐 𝛉𝟏 𝛉𝟒 𝜃

24
 Première solution : Descente du gradient
Partant d’un vecteur (𝛉𝟎 , 𝛉𝟏 ) initial, on cherche la fonction ‘ h’ tel que l’erreur quadratique ‘ J ’
soit minimale par l’idée de la descente du gradient.
En 1d :

𝛛
𝜽𝒋 : = 𝜽𝒋 − 𝛂 𝐉(𝜽d
𝛛𝜽𝒋

𝛼 : Valeur du pas de l’apprentissage >0

25
Minimisation de la fonction d’erreur
J 𝜽𝟎 , 𝜽𝟏

θ0 θ1

26
 Première solution : Descente du gradient

𝐦
𝟏 𝐢 𝐢
𝛉𝟎 : = 𝛉𝟎 − 𝛂 V 𝐡𝛉 𝐱 −𝐲
𝐦
𝐢Y𝟏

𝐦
𝛼 : Valeur du pas d’apprentissage (Learning Rate) 𝟏 𝐢 𝐢 𝐢
𝛉𝟏 : = 𝛉𝟏 − 𝛂 V 𝐡𝛉 𝐱 −𝐲 𝐱
𝐦 27
𝐢Y𝟏
Algorithme de descente de gradient
Require 𝛼 ≥ 0
1: repeat
k
2: 𝜃j : = 𝜃j − 𝛼 𝐽(𝜃O , 𝜃? ) pour j=0 et j=1
klm

3: until convergence

Remarque
Mise à jour correcte Mise à jour fausse
𝜕 𝜕
𝑡𝑒𝑚𝑝0: = 𝜃O − 𝛼 𝐽(𝜃O , 𝜃? ) 𝜃O : = 𝜃O − 𝛼 𝐽 𝜃O , 𝜃?
𝜕𝜃O 𝜕𝜃O
𝜕 𝜕
𝑡𝑒𝑚𝑝1: = 𝜃? − 𝛼 𝐽 𝜃O , 𝜃? 𝜃? : = 𝜃? − 𝛼 𝐽 𝜃O , 𝜃?
𝜕𝜃? 𝜕𝜃?
𝑡𝑒𝑚𝑝0 = 𝜃O
𝑡𝑒𝑚𝑝1 = 𝜃?
28
 Algorithme de descente de gradient
Choix de 𝜶 :
§ Si la valeur de 𝛼 est trop petite, la convergence est très lente
§ Si la valeur de 𝛼 est assez grande, on risque de ne pas trouver les minimum global de J
§ Si la valeur de 𝛼 est suffisamment petite, 𝐽 𝜃O , 𝜃? décroit après chaque itération
§ Si l’algorithme ne converge pas, choisir une valeur plus petite de 𝛼
§ En général, l’algorithme converge si 𝐽 𝜃O , 𝜃? décroit à 10 après une itération
-3

§ En pratique : Le nombre des idéations est fixé et le cout de la convergence peut être
étudié (voir en TP) 29
Deuxième solution : Equation Normale

§ Méthode pour calculer, analytiquement, le minimum de l’erreur

quadratique J() ;
k
§ J est minimum si ∀𝑗 = 0, … . 𝑛, 𝐽 𝜃 =0
klm
§ L’objectif est de trouver le vecteur 𝜃 pour qui :

k
𝐽 𝜃 =0
klm

30
Deuxième solution : Equation Normale

§ Notons :
𝐣
𝐗= 𝐱𝐢 𝑒𝑡 𝐲 = 𝐲𝐣 𝑒𝑡 𝛉 = 𝛉𝐣 𝑎𝑣𝑒𝑐 𝑖 = 1, … 𝑚 𝑒𝑡 𝑗 = 1, … 𝑛

§ La fonction d’erreur : 𝐉(𝛉) = 𝟏⁄𝟐 𝐦 V 𝐗. 𝛉 − 𝐲 𝟐

§ Sa dérivé : 𝛛 𝟏
𝐉 𝛉 = (−𝐗 𝐓 𝐲 + 𝐗 𝐓 𝐗 𝛉}
𝛛𝛉 𝐦
𝐓 |𝟏 𝐓
§ La solution est l’équation normale suivante : 𝛉= 𝐗 𝐗 𝐗 𝐲
§ A l’avantage que aucun paramètre 𝛼 n’est nécessaire mais le calcul est lent
quand n est grand
§ Les paramètres doivent être indépendants pour assurer le calcul de la matrice
inverse.
31
Résumé : régression linéaire à une seule variable
Modèle de Régression Linéaire:
ℎl x = 𝜃O + 𝜃? x

Fonction d’erreur:
? 1 ‚ (‚) [
𝐽 𝜃O , 𝜃? = ∑‚Y?(ℎl x − 𝑦 )
[1

Algorithme de descente du gradient :

Require 𝛼 ≥ 0
1: repeat
k
2: 𝜃j : = 𝜃j − 𝛼 kl 𝐽(𝜃O , 𝜃? ) pour j=0 et j=1
m
3: until convergence
Ou Equation normale : 𝜃= … |? …
𝑋 𝑋 𝑋 𝑦
32
 Régression multi-variables
Surface (x1) [Link] (x2) Étage (x3) …….. Prix (y) Plusieurs paramètres (features)
120 3 1  00
1
112 4 5 130 • n : nombre de paramètres
50 1 0 60
63 2 0 35
• x : i entré de la base d’entrainement
(i) eme

70
78
2
2
2
2
60
64
• xj : valeur du j paramètre de la i
(i) eme eme

90 2 1 100 entrée
92 2 2 92
100 3 3 120 • Le modèle linéaire multi-variable :
106 2 4 80
125 4 5 160
𝐡𝛉 𝐱 = 𝛉𝟎 + 𝛉𝟏 𝐱𝟏 + 𝛉𝟐 𝐱𝟐 + 𝛉𝟑 𝐱𝟑 + ⋯ … + 𝛉𝐧 𝐱𝐧
50 1 0 25 Ou pour x0 =1 et x= x(i)

𝐡𝛉 𝐱 = 𝛉𝟎 𝐱 𝟎 + 𝛉𝟏 𝐱 𝟏 + 𝛉𝟐 𝐱 𝟐 + 𝛉𝟑 𝐱 𝟑 + ⋯ … + 𝛉𝐧 𝐱 𝐧

33
Régression multi-variables
Modèle de Régression Linéaire multi-variables: (avec x0=1)
3

ℎl 𝑥 = 𝜃O 𝑥O + 𝜃? 𝑥? + 𝜃[ 𝑥[ + 𝜃\ 𝑥\ + ⋯ … + 𝜃3 𝑥3 = V 𝜃‚ 𝑥‚
Inconnu : ‚YO
𝛉 = 𝛉𝒊
Fonction d’erreur:
1
1 ‚ ‚ [
𝐽 𝜃 = V ℎl x −𝑦
2𝑚
‚Y?

Algorithme de descente du gradient :

Require 𝛼 ≥ 0
1: repeat
k
2: 𝜃j : = 𝜃j − 𝛼 𝐽(𝜃) , pour j= 0, …., n
klm
3: until convergence
Dérivés partielles de J :
1
𝜕 1 ‚ ‚ ‚
𝐽(𝜃) = V ℎl x −𝑦 x 34
𝜕𝜃j 𝑚
‚Y?
Généralisation

§ La droite est elle toujours le meilleur modèle ?

35
 Généralisation
Introduire des fonctions de base permet de généraliser la régression
𝐓
𝐡𝛉 (𝐱) = 𝚽(𝐱). 𝛉

Avec : 𝑥 = (𝑥O , 𝑥? , … , 𝑥3 ) et 𝜃 = (𝜃O , 𝜃? , … 𝜃3 ) et Φ 𝑥O = 1

Fonction de base:
§ 𝛷 𝑥 = x => Regréssion linéaire
§ 𝛷𝑗(𝑥)= x => Régression polynomiale
j

?
§𝛷 𝑥 = ou 𝛷 𝑥 = ex …. Best fit curve
“

[
§ Exemple d’une régression polynomiale (degré 2) ∶ ℎl 𝑥 = 𝜃O + 𝜃? 𝑥 + 𝜃[ 𝑥
36
 Classification
Régression logistique

3
7
 Classification
q La classification concerne l’apprentissage supervisé quand la cible est 0 ou 1 ou un indice de classe.
q Exemple d’application :
• En médecine, elle permet par exemple de trouver les facteurs qui caractérisent un groupe de sujets
malades par rapport à des sujets sains. Exemple : Tumeur : Bénigne (non cancéreuse)/Maligne
(cancéreuse)
• Dans le domaine des assurances, elle permet de cibler une fraction de la clientèle qui sera sensible à une
police d’assurance sur tel ou tel risque particulier.
• En économétrie, pour expliquer une variable discrète. Par exemple, les intentions de vote aux élections
• Email : Spam/Non-spam ?
q On va étudier trois approches de classification : Régression logistique et SVM (Support Vector Machine)
et KNN (k nearest neighbors)

38
Régression linéaire vs Régression logistique

𝟎 ∶ 𝐂𝐥𝐚𝐬𝐬𝐞 𝐧é𝐠𝐚𝐭𝐢𝐯𝐞 (𝐓𝐮𝐦𝐞𝐮𝐫 𝐁𝐞𝐧𝐢𝐠𝐧𝐞 )

𝐲 ∈ 𝟎, 𝟏 –
𝟏 ∶ 𝐂𝐥𝐚𝐬𝐬𝐞 𝐩𝐨𝐬𝐢𝐭𝐢𝐯𝐞 (𝐓𝐮𝐦𝐞𝐮𝐫 𝐌𝐚𝐥𝐢𝐠𝐧𝐞 )

39
 Classification
La Régression logistique utilise une fonction logistique ou sigmoïdale g entre 0 et 1,

𝐓
𝟏
𝐡𝛉 𝐱 = 𝐠 𝛉 𝐱 = 𝐓𝐱
𝟏+ 𝐞 |𝛉

Interprétation : Représente P( y=1 /x ; θ) la probabilité que y=1 sachant x paramétrée par θ

Exemple : si h x =0.8 => 80% de chance que la tumeur soit maligne. 40
 La fonction d’erreur

1
1 ‚ ‚
𝐽 𝜃 = V𝐶𝑜𝑠𝑡(ℎl 𝑥 ,𝑦 ¤
𝑚
‚Y?

− log ℎl 𝑥 𝑠𝑖 𝑦 = 1
𝐶𝑜𝑠𝑡 ℎl 𝑥 , 𝑦 = ¥
− log 1 − ℎl 𝑥 𝑠𝑖 𝑦 = 0

𝐂𝐨𝐬𝐭 𝐡𝛉 𝐱 , 𝐲 = −𝐲 𝐥𝐨𝐠 𝐡𝛉 𝐱 − (𝟏 − 𝐲) 𝐥𝐨𝐠 𝟏 − 𝐡𝛉 𝐱

41
 Minimisation de la fonction d’erreur
Fonction d’erreur :
1
1 ‚ ‚ ‚ ‚
𝐽 𝜃 = V −𝑦 𝐥𝐨𝐠 𝐡𝛉 𝑥 − (𝟏 − 𝑦 ) 𝐥𝐨𝐠 𝟏 − 𝐡𝛉 𝑥
𝑚
‚Y?

Algorithme de descente de gradient :

Require 𝛼 ≥ 0
1: repeat
k
2: 𝜃j : = 𝜃j − 𝛼 𝐽(𝜃) pour j= 0, …., n
klm

3: until convergence

1
𝜕 1 1
Avec : 𝐽(𝜃) = V ℎl x ‚
−𝑦 ‚
x ‚ et ℎl 𝑥 = ¦§
𝜕𝜃j 𝑚 1+ 𝑒 |l
‚Y?

42
 Classification
𝐓
La frontière de décision est la solution de l’inéquation : 𝛉 𝐱 >=0 (y=1)

Exemple : Classification linéaire Exemple : Classification Non-Linéaire

Une droite : 𝜃O + 𝜃? 𝑥1 + 𝜃[ 𝑥[ ≥ 0 Un cercle : 𝜃O + 𝜃? 𝑥1 + 𝜃[ 𝑥[ + 𝜃\ 𝑥?[ + 𝜃] 𝑥[[ ≥ 0

43
 Classification multi-classes
• Classification de chiffres manuscrits : 10 classes, Classification de caractères manuscrits : 26
classes, Météo : ensoleillé, nuageux, pluie, neige
• Soit k le nombre de classe, il existe deux stratégies pour la classification multi-classes :
1. Un-contre-un (One-vs-one OVO) : création d’un classifieur pour chaque deux classes
2. Un-contre-tous (One-vs-all ou One-vs-rest OVA) : création d’un classifieur pour chaque classe

44
Résumé : Classification par Régression logistique
Modèle de Régression logistique :
𝟏
𝐡𝛉 𝐱 = 𝐓𝐱
𝟏+ 𝐞 |𝛉

Fonction d’erreur :
𝒎
𝟏 𝒊 𝒊
𝐉 𝜽 = V −𝒚 𝐥𝐨𝐠 𝐡𝛉 𝒙 − (𝟏 − 𝒚 𝒊 ) 𝐥𝐨𝐠 𝟏 − 𝐡𝛉 𝒙 𝒊
𝒎
𝐢Y𝟏
Gradient :
𝒎
𝝏 𝟏 𝒊 𝒊 𝒊
𝐉(𝛉) = V 𝒉𝜽 𝐱 −𝒚 𝐱
𝛛𝜽𝒋 𝒎
𝐢Y𝟏
Descente du gradient :
𝝏
𝜽𝒋 : = 𝜽𝒋 − 𝛂 𝐉(𝜽𝟎 , 𝜽𝟏 )
𝛛𝜽𝒋

45
Application des algorithmes en Python avec sklearn
1. Importer les données :
from sklearn import datasets
Example = datasets.load_***()
X= [Link]
y= [Link]

2. Organiser les données

from sklearn.model_selection import train_test_split
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2)

3. Importer le module scikit-lean souhaité :

from sklearn.linear_model import LinearRegression
Ou from sklearn.linear_model import LogisticRegression
Ou from [Link] import SVC
Ou from [Link] import KNeighborsClassifier
Ou from [Link] import KMeans
46
Application des algorithmes en Python avec sklearn
4. Sélectionner l’estimateur et préciser ses hyper-parametres
model = LinearRegression (……)
Ou model=LogisticRegression (……)
Ou model = KNeighborsClassifier (…..)
Ou model = SVC (…….)
Ou model = Kmeans (……)

5. Entrainer le modèle sur les données d’entrainement

[Link](X_train,y_train)

47
Application des algorithmes en Python avec sklearn
6. Utiliser le modèle sur des données test
y_pred = [Link](X_test)

7. Evaluer le modèle
# Score de performance (proche de 1)
from [Link] import accuracy_score
score = accuracy_score(y_test, y_pred)
#Matrice de confusion (diagonale)
from [Link] import confusion_matrix
cm = confusion_matrix(y_test, y_pred)
# courbe ROC (Aire sous courbe proche de 1)
from [Link] import roc_curve
fpr,tpr,thresholds=roc_curve(y_test,y_pred)
48
KNN : plus proches voisins

49
Classification KNN
§ Classification à l’aide des plus proches voisins
§ L'algorithme k-NN est parmi les plus simples des algorithmes de machines learning.
§ La méthode k-NN est basée sur l'apprentissage préalable, ou l'apprentissage faible, où la fonction est évaluée
localement, le calcul définitif étant effectué à l'issue de la classification.
§ A partir d’un nuage de points pour lesquels la classe d’appartenance est connue, comment classer un nouveau point
pour lequel cette classe est inconnue ?
§ Une méthode simple consiste à attribuer à ce nouveau point la même classe que le plus proche des points
appartenant au nuage initial. C’est la méthode des plus proches voisins (Nearest Neighbours). Elle est facile à
implémenter mais peu utilisée car souvent très gourmande en temps de calcul lorsque le nuage de points est
conséquent.

50
 Classification KNN
§ L'algorithme nécessite de connaître le nombre de voisins à considérer K.
§ Exemple de classification k-NN . L'échantillon de test (cercle vert) pourrait être classé soit dans la
première classe de carré bleu ou la seconde classe de triangles rouges. Si k= 3 (cercle en ligne
pleine) il est affecté à la seconde classe car il y a deux triangles et seulement un carré dans le cercle
considéré.
§ Si k = 5 (cercle en ligne pointillée) il est affecté à la première classe (3 carrés face à deux triangles
dans le cercle externe)

51
SVM : Support vector Machine

52
Classification : SVM
§ Le SVM appartient à la catégorie des classificateurs linéaires (qui utilisent une séparation linéaire
des données), et qui dispose de sa méthode à lui pour trouver la frontière entre les classes.
§ Les SVM sont très efficaces quand on ne dispose que de peu de données d’entraînement. Ils ont
une capacité de généralisation intéressante même à partir de données minimales.
§ Etant donné deux classes (+1 et -1), Comment séparer entre ses deux classes ?
§ Si on opte pour un classifieur linéaire : 𝑦 𝑥 = 𝑠𝑖𝑔𝑛 𝜃t. 𝑥 + 𝑏 , Il existe de nombreux choix
possibles pour 𝜃 et b, Quelle hyperplan choisir ?
§ Intuitivement, on se dit que si on nous donne un nouveau point, très proche des points vert, alors
ce point a de fortes chances d’être dans la classe des points vert lui aussi. Inversement, plus un
point est près des points bleus, plus il a de chances d’être lui-même un point bleu.
§ Pour cette raison, un SVM va placer la frontière aussi loin que possible des points bleus, mais
également aussi loin que possible des points vert.

53
Classification : SVM

54
 Classification : SVM
§ Le but d’un SVM est de trouver une frontière optimale, en maximisant la distance entre les
points d’entraînement et cette frontière.
§ Les points d’entraînement les plus proches de la frontière sont appelés vecteurs support
(Support, parce que ce sont ces points qui « supportent » la frontière).
§ La marge est la distance d entre les deux classes et SVM cherche à maximiser cette marge
§ On supposant que les données peuvent être séparées par un hyperplan, affin de limiter l’espace
des hyperplans possibles, on considère que les points les plus proches sont situés sur les
hyperplans canoniques définis par : 𝜃 . 𝑥 + 𝑏 = ±1
t
[
§ Dans ce cas la marge d est donné par 𝑑 = l
§ Les données x de la classe +1 (resp. -1) vérifient : 𝜃t. 𝑥 + 𝑏 >=1 (resp. < -1).
§ Maximiser la marge revient à trouver 𝜃 et b tels que d est maximale, ∀ 𝑥‚ , 𝑦‚ de la base
d’apprentissage, sous les contraintes :
𝜃t. 𝑥 + 𝑏 ≥ +1 𝑠𝑖 𝑦‚ = +1
– t
𝜃 . 𝑥 + 𝑏 < −1 𝑠𝑖 𝑦‚ = −1

55
Classification : SVM

56
Cas linéairement séparable
vLe problème revient donc à chercher la solution au problème :
? [
min [ 𝜃
¥ . (1)
𝑦‚ 𝜃. 𝑥 + 𝑏 ≥ 1 ∀ 𝑖 ∈ 1, 𝑚
vSolution (Lagrangien) : Trouver la solution du problème (1) revient à trouver
∗ ∗ ∗
le point selle (𝜃 , 𝑏 , 𝛼 ) du Lagrangien associé :
1 [
1
ℒ 𝜃, 𝑏, 𝛼 = 𝜃 − V 𝛼‚ 𝑦‚ 𝜃. 𝑥 + 𝑏 − 1
° 2 ‚Y?
𝛼‚ ≥ 0 ∀ 𝑖 ∈ 1, 𝑚
∗ 1 ∗
vLes calculs vont permettre de noter : 𝜃 = ∑‚Y? 𝛼‚ 𝑦‚ 𝑥‚
vPour calculer la classe d’un nouvel exemple x0, on étudie le signe de la
quantité :
∗ ∗ 1 ∗ ∗
𝜃 𝑥O + 𝑏 = ∑‚Y? 𝛼‚ 𝑦‚ 𝒙𝟎 . 𝒙𝒊 +𝑏 57
 Cas non-linéairement séparable : Tolérance aux erreurs
vSi les données ne sont pas linéairement séparables : L’idée est d’ajouter des
variables d’ajustement 𝜉‚ dans la formulation précédente pour tenir compte
des erreurs de classification
vCe qui revient à chercher la solution à :
? [ 1
𝑚𝑖𝑛 [ 𝜃 +𝐶 ∑‚Y? 𝜉‚
𝑦‚ 𝜃 .𝑥
𝑡 + 𝑏 ≥ 1 − 𝜉‚ ∀ 𝑖 ∈ 1, 𝑚
𝜉‚ ≥ 0 ∀ 𝑖
vC (dénommée capacité) est une constante choisie par l’utilisateur qui
permet de donner plus ou moins d’importance aux erreurs : Une grande
valeur de C correspond à une grande pénalité aux erreurs.

58
Cas non-linéairement séparable : Astuce de noyau
§ Prenons l’exemple suivant de deux classes non linéairement séparable, nous
pouvons utiliser la solution précédente en acceptant quelques erreurs ou
bien projeter les données dans un espace de grande dimension ?

§ L’espace des données peut toujours être projeté dans un espace de plus
grande dimension dans lequel les données peuvent être séparées
linéairement
§ Si les données d’apprentissage sont projetées dans un espace de grande
dimension via la transformation 𝜙: 𝑥 → 𝜙(𝑥) le produit scalaire devient
𝐾 𝑥‚ , 𝑥j =< 𝜙 𝑥‚ , 𝜙 𝑥j > ∶ K est appelée fonction noyau

59
Astuce de noyau
§ Exemples de noyaux
§ Noyau linéaire : K(xi, xj) = [Link]
§ Noyau polynomial de degré p : K(xi; xj) = (1 + [Link])p
¼
¹º »¹m
|
§ Noyau gaussien : 𝐾 𝑥‚ , 𝑥j = 𝑒 ¼½¼

§ Remarque : Lors de l’apprentissage des SVM, seul l’utilisation du noyau est

importante
§ Formulation :
? [ 1
𝑚𝑖𝑛 𝜃 +𝐶 ∑‚Y? 𝜉‚
¥ [
𝑦‚ 𝜃 . 𝜙(𝑥‚ ) + 𝑏 ≥ 1 − 𝜉‚ ∀ 𝑖 ∈ 1, 𝑚 𝑒𝑡 𝜉‚ ≥ 0 ∀ 𝑖
𝑡

60
Apprentissage non supervisé
K-means: clustering

61
 Le clustering
q Le clustering est une méthode d’apprentissage non-supervisé.
q L’apprentissage non supervisé consiste à trouver des patterns dans les données. Notamment,
en regroupant les choses qui se ressemblent : Clustring.
q Le clustering va regrouper en plusieurs familles (clusters) les individus/objets en fonction de leurs
caractéristiques.
q Il a plusieurs applications :
q La segmentation de la clientèle en fonction d’un certain critère (démographique, habitude d’achat
etc….)
q Le Clustering de documents (regroupement de documents en fonction de leurs contenus. (Google
Actualités)

62
 K-means:
qK-means est un algorithme non supervisé de clustring. Il permet de regrouper
en clusters distincts les observations des données d’entrainement.
qPar ailleurs, une observation ne peut se retrouver que dans un cluster à la fois
(exclusivité d’appartenance).
qPour pouvoir regrouper un jeu de données en cluster distincts, l’algorithme
Kmeans a besoin d’un moyen de comparer le degré de similarité entre les
différentes observations.
qAinsi, deux données qui se ressemblent, auront une distance de
dissimilarité réduite, alors que deux objets différents auront une distance de
séparation plus grande.
qLa distance la plus connue pour les cas de clustering est La distance
Euclidienne: ? [
3

𝑑 𝑥 ,𝑥 = V 𝑥 −𝑥
?j [j
[

jY? 63
 Choisir K : le nombre de clusters
q Choisir un nombre de cluster K n’est pas forcément intuitif. Spécialement quand le jeu de données est grand et quand
on ne dispose pas d’hypothèses sur les données.
q Un nombre grand peut conduire à un partitionnement trop fragmenté des données. Ce qui empêchera de découvrir des
patterns intéressants dans les données. Par contre, un nombre de clusters trop petit, conduira à avoir, potentiellement,
des cluster trop généralistes contenant beaucoup de données. Dans ce cas, on n’aura pas de patterns “fins” à découvrir.
q Il n’existe pas de procédé automatisé pour trouver le bon nombre de clusters.
q La méthode la plus usuelle pour choisir le nombre de clusters est de lancer K-Means avec différentes valeurs de K et de
calculer la variance des différents clusters.
q La variance est la somme des distances entre chaque centroid d’un cluster et les différentes observations inclues dans
le même cluster. Ainsi, on cherche à trouver un nombre de clusters de telle sorte que les clusters retenus minimisent la
distance entre leurs centres (centroids) et les observations dans le même cluster. On parle de minimisation de la
distance intra-classe.
q La variance des clusters se calcule comme suit :
𝐕 = ∑𝐣 ∑𝐱 𝐢→𝐜𝐣 𝐃(𝐜𝐣 , 𝐱 𝐢 )𝟐
Avec :
§ 𝑐j : Le centre du cluster (le centroïd)
§ 𝑥‚ : la ième observation dans le cluster ayant pour centroïd 𝑐j
§ 𝐷(𝑐j , 𝑥‚ ) : La distance (euclidienne ou autre) entre le centre du cluster et le point
64
K-means: Algorithme

65
 K-means: Algorithme

• Note : La convergence de l’algorithme K-Means peut être l’une des conditions suivantes :
1. Un nombre d’itérations fixé à l’avance, dans ce cas, K-means effectuera les itérations et s’arrêtera peu
importe la forme de clusters composés.
2. Stabilisation des centres de clusters (les centroids ne bougent plus lors des itérations). 66