UNIVERSITE PROTESTANTE AU CONGO

FACULTE DES SCIENCES

INFORMATIQUES (FASI)
B.P. 4745 KINSHASA II

MACHINE LEARNING

Cours préparé et dispensé par :

Dr. Patrick B. Mande, Ph.D.
Professeur

Année académique: 2023-2024

1|Page
 MACHINE LEARNING

Volume horaire : 45 Heures dont 30 heures théoriques et 15 heures pratiques

Enseignant : Dr. Patrick B. Mande, Ph.D.
Email : [email protected]
Jours des cours : Chaque Lundi de 8h à 13h.
Local : Voir Campus du Centenaire.
Année académique : 2024 - 2025
Semestre : Premier semestre.
Langue d’enseignement : Français.

Description

Une machine peut apprendre à partir des données qui lui sont fournies et améliorer ses
performances dans une tâche donnée. En plus, une machine peut atteindre des niveaux de
performance qui peuvent bien se généraliser à de nouvelles situations. Le Machine Learning
s’intéresse à ces thématiques. Il est un domaine qui combine des techniques qui tirent leurs
origines aussi bien de l’informatique, de l’optimisation et des statistiques. Il est une discipline
en pleine expansion.

Ce cours va s’intéresser à l’apprentissage supervisé et à l’apprentissage non-supervisé. D’une

part, à partir d’un ensemble des données labelisées relatives à une tâche donnée, comment
pouvons-nous faire des prédictions précises des résultats qui se généralisent à des nouvelles
données. C’est ce qu’explorera l’aperçu adopté pour l’apprentissage automatique supervisé.
D’autre part, l’apprentissage non-supervisé s’intéresse au regroupement des données et à la
réduction des dimensions.

Objectifs et Résultats attendus

L’objectif de ce cours est de préparer les étudiants à appliquer efficacement les méthodes du
Machine Learning à des problèmes du "monde réel" - dans l'industrie, la médecine, l'éducation,
etc. Il cherche à familiariser les étudiants avec les algorithmes de l’apprentissage automatique
et créer de la confiance et de l’indépendance dans l’utilisation de ces outils puissants.
À la fin du cours, les étudiants devraient être capables de :
- Identifier des problèmes du monde réel comme des possibilités d’application des
algorithmes du Machine Learning (régression, clustering, etc.)
- Concevoir et implémenter une solution efficace aux problèmes de régression, de
classification, etc. au moyen des codes écrits en Python, à partir de zéro si nécessaire.
- Utiliser efficacement des bibliothèques de programmation pour effectuer des tâches de
Machine Learning.
- Mettre en œuvre les techniques de prétraitement des données et procéder à la partition des
données en ensembles d’entrainement, de validation et de test.
- Comparer les mesures appropriées d’évaluation des tâches de prédiction d’apprentissage
supervisé telles que la matrice de confusion, les courbes ROC, les courbes de précision,
etc.

2|Page
Ouvrages de référence
Le crédit des notes du cours vont aux auteurs dont les ouvrages sont repris ci-dessous.

1. Géron, A. (2019). Hands-On Machine Learning with Scikit-Learn, Keras and

TensorFlow: Concepts, Tools and Techniques to Build Intelligent Systems, Second
Edition. O’Reilly Media.
2. Géron, A. (2019). Machine Learning avec Scikit-Learn: Mise en oeuvre et cas concrets,
Troisième Edition. Dunod.
3. Azencott, C.-A., Introduction au Machine Learning. Deuxième Edition. Dunod.

Méthodologie d’enseignement

- Le cours est donné en utilisant les notes des cours tirés des livres de référence identifié
ci-dessus et toute autre documentation (nécessaire à atteindre les objectifs assignés à ce
cours).
- La partie théorique du cours sera immédiatement enrichi par le côté dans
l’environnement Python.
- Le cours adoptera une méthode interactive qui engage la participation de l’étudiant et
développe les compétences identifiées dans les objectifs ci-dessus.
- Les étudiants seront soumis à des travaux dirigés et à des projets, personnels ou en
groupes pour les aider à pratiquer les concepts étudiés et à développer les compétences.

Contenu

- Chapitre 1. Présentation du Machine Learning

- Chapitre 2. Apprentissage supervisé.
- Chapitre 3. Sélection et Evaluation
- Chapitre 4. Régression paramétrique
- Chapitre 5. Régularisation.
- Chapitre 6. Méthode des plus proches voisions
- Chapitre 7. Arbre et Forêts
- Chapitre 8. Machines à vecteurs de support
- Chapitre 9. Réduction de dimension
- Chapitre 10. Clustering

Modes d’Evaluation
- Présence et Participation au cours (10%)
Les étudiants sont récompensés pour leur présence au cours et surtout pour la participation en
répondant aux questions ou pour des commentaires pertinents. Pour juger de l’assimilation du
cours, les étudiants peuvent être évalués séance tenante.

- Exercices à domicile (20%) et Projets (20%) en groupes

Les étudiants formeront des groupes (taille à convenir) auxquels des exercices d’applications
seront assignés et une date de remise convenue. Tout travail remis en dehors du délai sera
sanctionné par des points en moins.

3|Page
 - Examen (50%).
L’examen est à notes et livres fermés. Il portera sur toute la matière étudiée pendant le cours
et les travaux pratiques. Les questions seront intelligentes et pousseront à réfléchir et à faire
preuve d’un esprit critique. Les séances des cours et les travaux pratiques prépareront
l’étudiant à aborder l’examen avec succès

Règles à observer
1. Être présent à chaque séance de cours et des travaux pratiques. La présence au cours et
aux séances pratiques sera prélevée et elle comptera pour la note finale.
2. Eviter de se présenter au cours avec un retard de plus de 10 minutes car l’accès ne sera
pas autorisé et l’étudiant sera considéré comme absent.
3. Mettre les téléphones en mode silencieux, éviter le bavardage et les déplacements
inutiles car toute indiscipline sera punie sévèrement.
4. Pas de déplacement inutile pendant le cours. Tout étudiant qui veut sortir, pour une
raison légitime, demande la permission au Professeur.
5. Une pause de 10 minutes sera accordée pour permettre de souffler.
6. La tricherie et le non-respect des règles académiques, reconnues universellement et
spécifiques à l’Université Protestante au Congo, seront punies de façon exemplaire

4|Page
 CHAPITRE 1.
PRÉSENTATION DU MACHINE LEARNING
1.1 Qu’est-ce que le Machine Learning

• Apprendre : c’est acquérir une compétence basée sur l’expérience.

o Fabien Benureau (2015) : « L’apprentissage est une modification d’un
comportement sur la base d’une expérience ».
o Arthur Samuel (1959) : On parle de Machine learning, quand un programme
informatique a la capacité d’apprendre sans que cette modification ne soit
explicitement programmée.
▪ Un programme classique utilise une procédure et les données qu’il
reçoit en entrées pour produire des réponses.
▪ Un programme d’apprentissage automatique utilise les données et les
réponses afin de produire la procédure qui permet d’obtenir les secondes
à partir des premières
Exemple

Supposons qu’une entreprise veuille connaître le montant total dépensé par un client ou une
cliente à partir de ses factures. Il suffit d’appliquer un algorithme classique, à savoir une simple
addition : un algorithme d’apprentissage n’est pas nécessaire.

Supposons maintenant que l’on veuille utiliser ces factures pour déterminer quels produits le
client est le plus susceptible d’acheter dans un mois. Bien que cela soit vraisemblablement lié,
nous n’avons manifestement pas toutes les informations nécessaires pour ce faire. Cependant,
si nous disposons de l’historique d’achat d’un grand nombre d’individus, il devient possible
d’utiliser un algorithme de machine learning pour qu’il en tire un modèle prédictif nous
permettant d’apporter une réponse à notre question.

Algorithme classique

Algorithme de Machine
Learning

5|Page
Pourquoi utiliser le Machine Learning

• Utiliser le Machine Learning quand

o Les données sont abondantes mais les connaissances sont peu développées ou
peu accessibles.
o En particulier quand
▪ L’expertise humaine n’existe pas (en d’autres termes pour des
problèmes que l’on ne sait pas résoudre (cas de prédiction d’achat ci-
dessus)
▪ Les humains sont incapables d’expliquer leur expertise (en d’autres
termes pour des problèmes que l’on sait résoudre mais on ne sait
formaliser en termes algorithmiques comment nous les résolvons.
Exemples : reconnaissance d’images ou de la compréhension du langage
naturel).
▪ Les solutions existantes sont coûteuses (en d’autres termes pour des
problèmes que l’on sait résoudre mais avec des procédures gourmandes
en ressources informatiques. Exemples : prédiction d’intéractions entre
molécules de grande taille pour lesquelles les simulations sont très
lourdes).

• Ainsi, le Machine learning peut aussi aider les humains à apprendre

o Dans l’exemple de la prédiction d’achats, comprendre le modèle peut nous
permettre d’analyser quelles caractéristiques des achats passés permettent de
prédire ceux à venir.
o Cet aspect du Machine learning est très utilisé dans la recherche scientifique :
▪ Quels gènes sont impliqués dans le développement d’un certain type de
tumeur, et comment ?
▪ Quelles régions d’une image cérébrale permettent de prédire un
comportement ?
▪ Quelles caractéristiques d’une molécule en font un bon médicament
pour une indication particulière ?
▪ Quels aspects d’une image de télescope permettent d’y identifier un
objet astronomique particulier ?

Ingrédients du Machine Learning

• Le Machine Learning repose sur deux piliers fondamentaux :

o Les données : il s’agit des exemples à partir duquel l’algorithme va apprendre ;
o L’algorithme d’apprentissage : c’est la procédure que l’on fait tourner sur ces
données pour produire un modèle.
▪ Retenons qu’une part importante du travail de machine learner ou de data
scientist consiste à préparer les données afin d’éliminer les données
aberrantes, gérer les données manquantes, choisir une représentation
pertinente, etc.

6|Page
 o On appelle entraînement le fait de faire tourner un algorithme d’apprentissage
sur un jeu de données.
• Note :
o Aucun algorithme d’apprentissage ne pourra créer un bon modèle à partir de
données qui ne sont pas pertinentes.
▪ Un algorithme d’apprentissage auquel on fournit des données de
mauvaise qualité ne pourra rien en faire d’autre que des prédictions de
mauvaise qualité.
o Un modèle appris avec un algorithme inadapté sur des données pertinentes ne pourra
pas être de bonne qualité.

• Le Machine Learning permet de

o Développer un algorithme (un modèle) c’est-à-dire modéliser un phénomène
o A partir des exemples des données
o Pour ce faire, il faut définir et optimiser une fonction objectif.

• Voici quelques exemples de reformulation de problèmes de Machine learning sous la

forme d’un problème d’optimisation.
o Un vendeur en ligne peut chercher à modéliser des types représentatifs de
clientèle, à partir des transactions passées, en maximisant la proximité entre
clients et clientes affectés à un même type.
o Une compagnie automobile peut chercher à modéliser la trajectoire d’un
véhicule dans son environnement, à partir d’enregistrements vidéo de voitures,
en minimisant le nombre d’accidents.
o Des chercheurs en génétique peuvent vouloir modéliser l’impact d’une mutation
sur une maladie, à partir de données patient, en maximisant la cohérence de leur
modèle avec les connaissances de l’état de l’art.
o Une banque peut vouloir modéliser les comportements à risque, à partir de son
historique, en maximisant le taux de détection de non-solvabilité.

Machine Learning et les autres disciplines

• Le Machine learning repose sur

o Les Mathématiques, et en particulier les Statistiques, pour ce qui est de la
construction de modèles et de leur inférence à partir de données.
o L’Informatique, pour ce qui est de la représentation des données et de
l’implémentation efficace d’algorithmes d’optimisation.
• Le Machine Learning est une branche de l’Intelligence Artificielle.
o L’intelligence artificielle est définie comme l’ensemble des techniques mises en
œuvre afin de construire des machines capables de faire preuve d’un
comportement que l’on peut qualifier d’intelligent.
o Elle fait aussi appel aux sciences cognitives, à la neurobiologie, à la logique, à
l’électronique, à l’ingénierie et bien plus encore.

7|Page
1.2 Types des problèmes de Machine Learning

Apprentissage supervisé
• Branche du Machine learning qui s’intéresse aux problèmes pouvant être formalisés
de la façon suivante
𝑖
o Etant donné n observations {x⃗} 𝑖 = 1, … , 𝑛 décrites dans un espace 𝜒, et leurs
𝑖
étiquettes {y⃗ } 𝑖 = 1, … , 𝑛 décrites dans un espace 𝕪
o On suppose que les étiquettes peuvent être obtenues à partir des observations
grâce à une fonction 𝜗: 𝜒 → 𝕪 fixe et inconnue : 𝑦 𝑖 = 𝜗(x⃗)𝑖 + 𝜖𝑖 , où 𝜖𝑖 est un
bruit aléatoire.
o Il s’agit donc d’utiliser les données pour déterminer une fonction f : 𝜒 → 𝕪 tel
que pour tout couple (x⃗, 𝜗(x⃗)) ∈ 𝜒 × 𝕪 , 𝑓(x⃗) ≈ 𝜗(x⃗)

• But : Apprendre à faire des prédictions, à partir d’une liste d’exemples étiquetés, c’est-
à-dire accompagnés de la valeur à prédire.

o Dans le cas où les étiquettes sont binaires, (autrement dit 𝕪 = {0,1}), elles indiquent
l’appartenance à une classe.
▪ On parle alors de classification binaire.
▪ Exemples de classification binaire
• Identifier si un email est un spam ou non.
• Identifier si un tableau a été peint par Picasso ou non.
• Identifier si une image contient ou non une girafe.
• Identifier si une molécule peut ou non traiter la dépression.
• Identifier si une transaction financière est frauduleuse ou non.
o Dans le cas où les étiquettes sont discrètes, et correspondent donc à plusieurs
classes (𝕪 = {1, 2, … , 𝐶}), on parle de classification multi-classe.
▪ C est le nombre des classes.
▪ Exemples des problèmes de classification multi-classes :
• Identifier en quelle langue un texte est écrit.
• Identifier lequel des 10 chiffres arabes est un chiffre manuscrit.

8|Page
 •
Identifier l’expression d’un visage parmi une liste prédéfinie de
possibilités (colère, tristesse, joie, etc.).
• Identifier à quelle espèce appartient une plante.
• Identifier les objets présents sur une photographie.
o Dans le cas où les étiquettes sont à valeurs réelles (𝕪 = ℝ), on parle de
régression.
▪ Exemples des problèmes de régression
• Prédire le nombre de clics sur un lien.
• Prédire le nombre d’utilisateurs et utilisatrices d’un service en
ligne à un moment donné.
• Prédire le prix d’une action en bourse.
• Prédire l’affinité de liaison entre deux molécules.
• Prédire le rendement d’un plant de maïs.

Apprendre non-supervisé

• Dans le cadre de l’apprentissage non supervisé, les données ne sont pas étiquetées.
o C’est la branche du Machine Learning qui s’intéresse aux problèmes pouvant
être formalisés comme suit :
𝑖
o Etant donné n observations {x⃗} 𝑖 = 1, … , 𝑛 décrites dans un espace 𝜒, il s’agit
d’apprendre une fonction sur 𝜒 qui vérifie certaines propriétés.
• Le clustering, ou partitionnement, consiste à identifier des groupes dans les données
(voir figure 1.3).
o Cela permet de comprendre leurs caractéristiques générales, et éventuellement
d’inférer les propriétés d’une observation en fonction du groupe auquel elle
appartient.

o Exemples des problèmes de partitionnement

▪ La segmentation de marché consiste à identifier des groupes d’usagers
ou de clients ayant un comportement similaire.
• Cela permet de mieux comprendre leur profil, et cibler une
campagne de publicité, des contenus ou des actions
spécifiquement vers certains groupes.

9|Page
 ▪ Identifier des groupes de documents ayant un sujet similaire, sans les
avoir au préalable étiquetés par sujet.
• Cela permet d’organiser de larges banques de textes.
▪ La compression d’image peut être formulée comme un problème de
partitionnement consistant à regrouper des pixels similaires pour ensuite
les représenter plus efficacement.
▪ La segmentation d’image consiste à identifier les pixels d’une image
appartenant à la même région.
▪ Identifier des groupes parmi les patients présentant les mêmes
symptômes permet d’identifier des sous-types d’une maladie, qui
pourront être traités différemment.
• La réduction de dimension est une autre famille importante de problèmes
d’apprentissage non supervisé.
o Il s’agit de trouver une représentation des données dans un espace de dimension
plus faible que celle de l’espace dans lequel elles sont représentées à l’origine
(voir figure 1.4).

o Cela permet de réduire les temps de calcul et l’espace mémoire nécessaire au

stockage les données, mais aussi souvent d’améliorer les performances d’un
algorithme d’apprentissage supervisé entraîné par la suite sur ces données.
• Certaines méthodes de réduction de dimension sont supervisées : il s’agit alors de
trouver la représentation la plus pertinente pour prédire une étiquette donnée.

Apprentissage par renforcement

• Dans le cadre de l’apprentissage par renforcement, le système d’apprentissage peut

interagir avec son environnement et accomplir des actions.
o En retour de ces actions, il obtient une récompense, qui peut être positive si
l’action était un bon choix, ou négative dans le cas contraire.
o La récompense peut parfois venir après une longue suite d’actions ; c’est le cas
par exemple pour un système apprenant à jouer au go ou aux échecs.
o Ainsi, l’apprentissage consiste dans ce cas à définir une politique, c’est-à-dire
une stratégie permettant d’obtenir systématiquement la meilleure récompense
possible.

10 | P a g e
 • Les applications principales de l’apprentissage par renforcement se trouvent dans les
jeux (échecs, go, etc) et la robotique.
o Ce sujet dépasse largement le cadre de ce cours.

1.3 Résumé
• But du Machine Learning : Trouver une approximation des données qui soit, à la fois,
bonne et utile.
o C’est facile de construire un modèle dont la performance est bonne sur le
training data.
o Cependant, comment va-t-il fonctionner sue des nouvelles données ?
• Défis :
o Apprendre les modèles qui se généralisent bien.
o Evaluer si les modèles se généralisent bien.
• Boîtes à outils (Toolboxes) :
o Python, Pandas, Numpy, Scikit-learn

11 | P a g e
 CHAPITRE 2.
APPRENTISSAGE SUPERVISE
2.1 Formalisation d’un problème d’apprentissage supervisé

• L’apprentissage supervisé peut être formalisés de la façon suivante

o Etant donné n observations {x⃗1 , x⃗ 2 , … , x⃗ 𝑛 }, où chaque observation x⃗ 𝑖 est un
élément des observations 𝜒, et leurs étiquettes {𝑦1 , 𝑦 2 , … , 𝑦 𝑛 }, où chaque
étiquette 𝑦 𝑖 appartient à l’espace des étiquettes 𝕪
o Le but de l’apprentissage supervisé est de trouver une fonction 𝑓: 𝜒 → 𝕪 tel que
𝑓(x⃗) ≈ 𝑦, pour toutes les paires (𝑥, 𝑦) 𝜖 𝜒 × 𝕪 ayant la même relation que les
paires observées.
o L’ensemble 𝒟 = {(𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,2,…,𝑛 forme le jeu d’apprentissage.
• Trois cas particuliers sont possibles pour 𝕪.
o 𝕪 = ℝ, on parle des problèmes de régression.
o 𝕪 = {0,1}, on parle d’un problème de classification binaire.
▪ Les observations dont l’étiquette vaut 0 sont appelées négatives tandis que
celles dont l’étiquette vaut 1 sont appelées positives.
▪ Dans certains cas, il sera mathématiquement plus simple d’utiliser 𝕪 =
{−1,1}
o 𝕪 = {1,2, … , 𝐶}, 𝐶 > 2, on parle d’un problème de classification multi-classe.
• Dans de nombreux cas, on se ramènera au cas où 𝕪 = ℝ𝑝 .
o On dira alors que les observations sont représentées par p variables.
o Les variables sont aussi appelées descripteurs, attributs, prédicteurs, ou
caractéristiques (en anglais, variables, descriptors, attributes, predictors ou
encore features).
o Les observations sont aussi appelées exemples, échantillons ou points du jeu
de donnée (en anglais, samples ou data points).
o Les étiquettes sont aussi appelées variables cibles (en anglais, labels, targets ou
outcomes).
▪ La figure 2.1 illustre ces différents concepts.

12 | P a g e
 • La matrice 𝑋 𝜖 ℝ𝑛×𝑝 telle que 𝑋𝑖𝑗 = 𝑥𝑗𝑖 soit la j-ème variable de la i-ème observation
est appelée matrice de données ou matrice de design.

2.2 Espace des hypothèses.

• Pour poser un problème d’apprentissage supervisé, il nous faut décider du type de

fonctions de modélisation que nous allons considérer.
o On appelle espace des hypothèses l’espace de fonctions ℱ ⊆ 𝕪 𝜒 décrivant les
fonctions de modélisation que nous allons considérer.
o Cet espace est choisi en fonction de nos convictions par rapport au problème.
• Etant donné un jeu de n observations étiquetées 𝒟 = {(𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,2,…,𝑛 et un espace
d’hypothèses ℱ.
o La tâche d’apprentissage supervisé consiste à supposer que les étiquettes 𝑦 𝑖 ont
été calculées grâce à une fonction 𝜗: 𝜒 → 𝕪, et à trouver une hypothèse 𝑓 ∈ 𝐹
qui approche au mieux la fonction cible 𝜗.
o Pour réaliser une telle tâche, nous allons voir besoin de deux outils
supplémentaires :
▪ Une façon de quantifier la qualité d’une hypothèse, afin de pouvoir
déterminer si une hypothèse satisfaisante (voire optimale) a été trouvée.
• Pour cela, nous allons définir ci-dessous la notion de fonction de
coût.
▪ Une façon de chercher une hypothèse optimale dans ℱ.
• Nous allons nous concentrer sur les méthodes d’apprentissage
par optimisation.

2.3 Minimisation du risque empirique

• Résoudre un problème d’apprentissage supervisé revient à trouver une fonction 𝑓 ∈ ℱ

dont les prédictions soient les plus proches possibles des véritables étiquettes, sur tout
l’espace 𝜒.
o On utilise pour formaliser cela la notion de fonction de coût.
o Une fonction de coût L : 𝕪 × 𝕪 → ℝ, aussi appelée fonction de perte ou
fonction d’erreur (en anglais : cost function ou loss function) est une fonction
utilisée pour quantifier la qualité d’une prédiction : 𝐿(𝑦, 𝑓(x⃗)) est d’autant plus
grande que l’étiquette 𝑓(x⃗) est éloignée de la vraie valeur de 𝑦.
• Étant donnée une fonction de coût L, nous cherchons donc f qui minimise ce coût sur
l’ensemble des valeurs possibles de x⃗ ∈ 𝜒 , ce qui est formalisé par la notion de risque.
o Dans le cadre d’un problème d’apprentissage supervisé, on appelle risque
l’espérance d’une fonction de coût : ℜ(ℎ) = 𝔼 𝜒 [𝐿(ℎ(x⃗), 𝑦].
o La fonction 𝑓 que nous cherchons vérifie donc 𝑓 = argminℎ 𝜖 𝐹 𝔼[𝐿(ℎ(x⃗), 𝑦].
o Etant donné n observations étiquetées {(𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,2,…,𝑛 , on approchera le
risque par son estimation sur ces données observées.
1
o Cet estimateur est appelé le risque empirique : 𝑅𝑛 (ℎ) = 𝑛 ∑𝑛𝑖=1 𝐿(ℎ(x⃗ 𝑖 ), 𝑦 𝑖 )

13 | P a g e
 • Le prédicteur par minimisation du risque empirique est donc :
𝑛
1
𝑓 = argminℎ 𝜖 𝐹 ∑ 𝐿(ℎ(x⃗ 𝑖 ), 𝑦 𝑖 )
𝑛
𝑖=1
• Selon le choix de ℱ, l’équation ci-dessus peut avoir une solution analytique explicite.
o Cela ne sera pas souvent le cas.
o Cependant on choisira souvent une fonction de coût convexe afin de résoudre
plus facilement ce problème d’optimisation.

2.4 Fonctions des coûts

• Il existe de nombreuses fonctions des coûts.

o Le choix d’une fonction de coût dépend
▪ Du problème en lui-même, autrement dit de ce que l’on trouve pertinent
pour le cas pratique considéré, et
▪ De considérations pratiques : peut-on ensuite résoudre le problème
d’optimisation qui résulte de ce choix de façon suffisamment exacte et
rapide ?

Fonction des coûts pour la classification

• Dans le cadre d’un problème de classification binaire, on appelle coût quadratique, ou

square loss, la fonction suivante :

𝐿𝑠𝑞𝑢𝑎𝑟𝑒 : {−1,1} × ℝ → ℝ

𝑦, 𝑓(x⃗) → (1 − 𝑦𝑓(x⃗))2

• On peut chercher à définir une fonction de décision dont la valeur absolue quantifie
notre confiance en sa prédiction.
o On cherche alors à ce que 𝑦, 𝑓(x⃗) soit la plus grande possible, et on utilise le
coût logistique.
o On appelle fonction de coût logistique, ou logistic loss, la fonction suivante :
𝐿𝑙𝑜𝑔 : {−1,1} × ℝ → ℝ
𝑦, 𝑓(x⃗) → 𝑙𝑜𝑔(1 + exp (−𝑦𝑓(x⃗))
• Si l’on préfère utiliser Y = {0, 1}, le coût logistique est équivalent à l’entropie croisée.
o Dans le cas binaire, on appelle entropie croisée, ou cross-entropy, la fonction
suivante :
𝐿𝐻 : {0,1} × ]0,1[ → ℝ
𝑦, 𝑓(x⃗) → −𝑦𝑙𝑜𝑔(𝑓(x⃗) − (1 − 𝑦)log (1 − 𝑓(x⃗))
o Dans le cas multi-classe, on appelle entropie croisée, ou cross-entropy, la
fonction suivante :
𝐿𝐻 : {1,2, … , 𝐶} × ℝ → ℝ

14 | P a g e
 𝐶

𝑦, 𝑓(x⃗) → − ∑ 𝛿( 𝑦, 𝑐)𝑙𝑜𝑔𝑓𝑐 (x⃗) = −log 𝑓𝑦 (x⃗)

𝑐=1

Fonction des coûts pour la régression

• Dans le cas d’un problème de régression, nous considérons maintenant 𝕪 = ℝ.

o Le but de notre fonction de coût est de pénaliser les fonctions de prédiction f
dont la valeur est éloignée de la valeur cible x⃗.
o On appelle fonction de coût quadratique ou quadratic loss ou encore squared
error, la fonction suivante :
𝐿𝑆𝐸 : ℝ × ℝ → ℝ
1
𝑦, 𝑓(x⃗) → (𝑦 − 𝑓(x⃗))2
2
1
• Le coefficient 2 permet d’éviter d’avoir des coefficients multiplicateurs quand on dérive
le risque empirique pour le minimiser.

2.5 Généralisation et Surapprentissage

• Imaginons un algorithme qui, pour prédire l’étiquette d’une observation x⃗, retourne son
étiquette si x⃗ appartient aux données dont l’étiquette est connue, et une valeur aléatoire
sinon.
o Cet algorithme aura une erreur empirique minimale quelle que soit la fonction
de coût choisie, mais fera de très mauvaises prédictions pour toute nouvelle
observation.
o Ce n’est pas vraiment ce que l’on a en tête quand on parle d’apprentissage.
o On appelle généralisation la capacité d’un modèle à faire des prédictions
correctes sur de nouvelles données, qui n’ont pas été utilisées pour le construire.
• Dans tout problème d’apprentissage automatique, les données sont inévitablement
bruitées
o Par des erreurs de mesure dues à la faillibilité des capteurs utilisés pour mesurer
les variables par lesquelles on représente nos données, ou à la faillibilité des
opérateurs humains qui ont entré ces mesures dans une base de données ;
o par des erreurs d’étiquetage (souvent appelées teacher’s noise en anglais) dues
à la faillibilité des opérateurs humains qui ont étiqueté nos données ;
o enfin, parce que les variables mesurées ne suffisent pas à modéliser le
phénomène qui nous intéresse, soit qu’on ne les connaisse pas, soit qu’elles
soient coûteuses à mesurer.
• On dit d’un modèle qui, plutôt que de capturer la nature des objets à étiqueter, modélise
aussi le bruit et ne sera pas en mesure de généraliser qu’il sur-apprend.
o En anglais, on parle d’overfitting.
o Un modèle qui sur-apprend est généralement un modèle trop complexe, qui
«colle» trop aux données et capture donc aussi leur bruit.

15 | P a g e
• À l’inverse, il est aussi possible de construire un modèle trop simple, dont les
performances ne soient bonnes ni sur les données utilisées pour le construire, ni en
généralisation.
o On dit d’un modèle qui est trop simple pour avoir de bonnes performances
même sur les données utilisées pour le construire qu’il sous-apprend.
o En anglais, on parle d’underfitting.
• Ces concepts sont illustrés sur la figure 2.6a pour un problème de classification binaire
et la figure 2.6b pour un problème de régression.

• Plus un modèle est simple, et moins il a de risques de sur-apprendre.

o Pour limiter le risque de sur-apprentissage, il est donc souhaitable de limiter la
complexité d’un modèle.
o C’est ce que permet de faire la régularisation, une technique qui consiste à
ajouter au terme d’erreur que l’on cherche à minimiser un terme qui mesure la
complexité du problème.
o Ainsi, un modèle complexe qui a une erreur empirique faible peut être
défavorisé face à une modèle plus simple, même si celui-ci présente une erreur
empirique plus élevée.

16 | P a g e
 CHAPITRE 3.
SELECTION DE MODELE ET EVALUATION
• Nous avons formalisé au chapitre 2 l’apprentissage supervisé comme la recherche d’un
modèle dont l’erreur empirique est minimale sur un ensemble donné d’observations.
o Cependant, minimiser cette erreur empirique ne garantit pas de minimiser
l’erreur du modèle sur la totalité de l’espace des données.
o En effet, dans une situation de surapprentissage, l’erreur du modèle sera sous-
estimée.
o C’est cependant cette erreur, ou, en d’autres mots, notre capacité à faire des
prédictions sur des choses qui ne sont pas connues, qui nous intéresse.
• Ce chapitre présente comment mettre en place un cadre expérimental qui permette
d’évaluer un modèle en évitant le biais du sur-apprentissage.
o Dans cette optique, nous veillerons à distinguer l’évaluation d’un modèle, qui
consiste à déterminer sa performance sur l’espace des données dans sa totalité,
de sa sélection, qui consiste à choisir le meilleur modèle parmi plusieurs.

3.1 Estimation empirique de l’erreur de généralisation

• L’erreur empirique mesurée sur les observations qui ont permis de construire le modèle
est un mauvais estimateur de l’erreur du modèle sur l’ensemble des données possibles,
ou erreur de généralisation :
o Si le modèle sur-apprend, cette erreur empirique peut être proche de zéro voire
nulle, tandis que l’erreur de généralisation peut être arbitrairement grande.
o Pour évaluer un modèle, il est donc indispensable d’utiliser des données
étiquetées qui n’ont pas servi à le construire.
• Etant donné un jeu des données 𝒟 = {(𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,2,…,𝑛 partitionné en deux jeux 𝒟𝑡𝑟 et
𝒟𝑡𝑒 , on appelle :
o Jeu d’entrainement (training set en anglais) l’ensemble 𝒟𝑡𝑟 utilisé pour
entraîner un modèle prédictif ;
o Jeu de test (test set) l’ensemble 𝒟𝑡𝑒 utilisé pour son évaluation.
• Comme nous n’avons pas utilisé le jeu de test pour entraîner notre modèle, il peut être
considéré comme un jeu de données « nouvelles ».
o La perte calculée sur ce jeu de test est un estimateur de l’erreur de
généralisation.

• Supposons maintenant que nous voulons choisir entre K modèles.

o Nous pouvons alors entraîner chacun des modèles sur le jeu de données
d’entraînement,
o Obtenir ainsi K fonctions de décision 𝑓1 , 𝑓2 , … , 𝑓𝑘 ,
o Calculer l’erreur de chacun de ces modèles sur le jeu de test.
o Choisir, ensuite, comme modèle celui qui a la plus petite erreur sur le jeu de test
:

17 | P a g e
 1
𝑓̂ = arg min ∑ 𝐿(𝑦, 𝑓𝑘 (x⃗))
𝑘=1,…,𝐾 |𝒟𝑡𝑒 |
⃗ ,𝑦 𝜖 𝒟𝑡𝑒
x

o Mais quelle est son erreur de généralisation ? Comme nous avons utilisé 𝒟𝑡𝑒
pour sélectionner le modèle, il ne représente plus un jeu indépendant composé
de données nouvelles, inutilisées pour déterminer le modèle.

• La solution est alors de découper notre jeu de données en trois parties :

o Un jeu d’entraînement 𝒟𝑡𝑟 sur lequel nous pourrons entraîner nos K
algorithmes d’apprentissage ;
o Un jeu de validation (validation set en anglais) 𝒟𝑣𝑎𝑙 sur lequel nous évaluerons
les K modèles ainsi obtenus, afin de sélectionner un modèle définitif ;
o Un jeu de test 𝒟𝑡𝑒 sur lequel nous évaluerons enfin l’erreur de généralisation du
modèle choisi.
• Combien de données devraient être incluses dans chacun des jeux d'entraînement, de
validation et de test ?
o Comment savoir si nous avons suffisamment de données pour évaluer les
erreurs de prédiction et de généralisation ?
o Le cadre le plus classique pour ce faire est celui de la validation croisée, illustré
sur la figure 3.1.

• Étant donnés un jeu 𝒟 de n observations et un nombre K, on appelle validation croisée

(cross-validation, en anglais) la procédure qui consiste à :
o 1. partitionner 𝒟 en K parties de tailles sensiblement similaires, 𝒟1 , 𝒟2 , … , 𝒟𝑘
;
o 2. pour chaque valeur de k = 1, . . . , K :
▪ Entraîner un modèle sur ⋃𝑙≠𝑘 𝒟𝑙
▪ Évaluer ce modèle sur 𝒟𝑘 .
o Chaque partition de 𝒟 en deux ensembles 𝒟𝑘 et ⋃𝑙≠𝑘 𝒟𝑙 est appelée un fold de
la validation croisée.

18 | P a g e
 • Chaque observation étiquetée du jeu 𝒟 appartient à un unique jeu de test, et à (K −1)
jeux d’entraînement.
o Ainsi, cette procédure génère une prédiction par observation de 𝒟.
o Pour conclure sur la performance du modèle, on peut :
▪ Soit évaluer la qualité des prédictions sur 𝒟;
▪ Soit évaluer la qualité de chacun des K prédicteurs sur le jeu de test 𝒟𝑘
correspondant, et faire la moyenne de leurs performances.
• Cette deuxième approche permet aussi de rapporter l’écart-type
de ces performances, ce qui permet de se faire une meilleure idée
de la variabilité de la qualité des prédictions en fonction des
données d’entraînement.
• Une validation croisée dont le nombre de folds est égal au nombre d’observations dans
le jeu d’entraînement, et dont chaque fold est donc composé d’un jeu d’entraînement
de taille n − 1 et d’un jeu de test de taille 1, est appelée leave one out (on met de côté,
pour chaque fold, un unique exemple).
o L’évaluation par leave-one-out présente deux inconvénients.
▪ Elle requiert un grand temps de calcul ;
▪ Les jeux d’entrainement ainsi formés sont très similaires entre eux.
▪ Les jeux de test seront disjoints et les performances pourront ainsi avoir
une grande variabilité. Ce qui compliquera leur interprétation.

3.2 Critères de performance

• Il existe de nombreuses façons d’évaluer la performance prédictive d’un modèle

d’apprentissage supervisé.

Matrice de confusion et critères dérivés

• Les performances d’un modèle de classification, binaire comme multiclasse, peuvent

être résumée dans une matrice de confusion.
o Étant donné un problème de classification, on appelle matrice de confusion une
matrice M contenant autant de lignes que de colonnes que de classes, et dont
l’entrée 𝑀𝑐𝑘 est le nombre d’exemples de la classe c pour laquelle l’étiquette k
a été prédite.
o Dans le cas de la classification binaire, la matrice de confusion prend la forme
suivante :

19 | P a g e
• On appelle :
o Vrais positifs (en anglais true positives) les exemples positifs correctement
classifiés ;
o Faux positifs (en anglais false positives) les exemples négatifs étiquetés positifs
par le modèle ;
o et réciproquement pour les vrais négatifs (true negatives) et les faux négatifs (
false negatives).
• On note généralement TP le nombre de vrais positifs, FP le nombre de faux positifs,
TN le nombre de vrais négatifs et FN le nombre de faux négatifs.
o Les faux positifs sont aussi appelés fausses alarmes ou erreurs de type I, par
opposition aux erreurs de type II qui sont les faux négatifs.

• Il est possible de dériver de nombreux critères d’évaluation à partir de la matrice de

confusion.
o On appelle rappel (recall en anglais), ou sensibilité (sensitivity en anglais), le
taux de vrais positifs, c’est-à-dire la proportion d’exemples positifs
correctement identifiés comme tels :
TP
Rappel =
TP + FN

• Il est cependant très facile d’avoir un bon rappel en prédisant que tous les exemples
sont positifs.
o Ainsi, ce critère ne peut pas être utilisé seul.
o On lui adjoint ainsi souvent la précision : On appelle précision, ou valeur
positive prédictive (positive predictive value, PPV) la proportion de prédictions
correctes parmi les prédictions positives :
TP
Precision =
TP + FP

o Note : L’anglais distingue precision (la précision ci-dessus) et accuracy, qui est
la proportion d’exemples correctement étiquetés, soit le complémentaire à 1 du
taux d’erreur, aussi traduit par précision en français.
o On utilisera donc ces termes avec précaution.
• Pour résumer rappel et précision en un seul nombre, on calculera la F-mesure :
o On appelle F-mesure (F-score ou F1-score en anglais), notée F, la moyenne
harmonique de la précision et du rappel :

Précision . Rappel 2 TP
F=2 =
Précision + Rappel 2TP + FP + FN

o On appelle spécificité le taux de vrais négatifs, autrement dit la proportion

d’exemples négatifs correctement identifiés comme tels :
TN
Spécificité =
FP + TN

20 | P a g e
Exemple

Prenons l’exemple d’un test clinique pour illustrer ces différents critères. Il ne s’agit pas ici
d’un modèle d’apprentissage automatique, mais d’un frottis de dépistage du cancer du col de
l’utérus : il s’agit d’un examen beaucoup plus simple et moins invasif qu’un examen
histologique, qui doit être interprété par un expert, et servira de vérité terrain.

Les résultats d’une expérience menée sur 4 000 femmes âgées de 40 ans et plus sont présentés
sur le tableau 3.1.

Le rappel est de 95 %, la spécificité de 94,5 %, mais la précision ne vaut que 47,5 %. En effet,
ce test est un bon outil de dépistage : la probabilité de n’avoir effectivement pas de cancer
quand le frottis est négatif est élevée (3590/3600 ≈ 99,7 %).

Cependant, c’est un mauvais outil diagnostique, au sens où la probabilité de fausse alarme est
très élevée.

Evaluation des méthodes de classification binaire retournant un score

• De nombreux algorithmes de classification ne retournent pas directement une étiquette

de classe, mais utilisent une fonction de décision qui doit ensuite être seuillée pour
devenir une étiquette.
o Cette fonction de décision peut être un score arbitraire (par exemple, la
proportion d’exemples positifs parmi les k plus proches voisins du point à
étiqueter – nous verrons l’algorithme des k plus proches voisins en détails plus
loin) ou la probabilité d’appartenir à la classe positive (comme c’est par
exemple le cas pour la régression logistique).
o Plusieurs critères permettent d’évaluer la qualité de la fonction de décision avant
seuillage.

Courbe ROC

• On appelle courbe ROC, de l’anglais Receiver-Operator Characteristic la courbe

décrivant l’évolution de la sensibilité en fonction du complémentaire à 1 de la
spécificité, parfois appelé antispécificité, lorsque le seuil de décision change.
o Le terme vient des télécommunications, où ces courbes servent à étudier si un
système arrive à séparer le signal du bruit de fond.

21 | P a g e
 o On peut synthétiser une courbe ROC par l’aire sous cette courbe, souvent
abrégée AUROC pour Area Under the ROC.

Pour illustrer la construction d’une courbe ROC, prenons l’exemple décrit sur le tableau 3.2.

Pour un seuil supérieur à 0,9, les 6 exemples sont étiquetés négatifs. On commence donc par
le point (0,0). Pour un seuil entre 0,95 et 0,9, seule la première observation est étiquetée
positive. La sensibilité est donc de 1/3 tandis que l’antispécificité reste nulle. On peut continuer
ainsi jusqu’à utiliser un seuil inférieur à 0,1 :

La courbe ROC correspondante est visible sur la figure 3.3.

22 | P a g e
 • On peut enfin utiliser la courbe ROC pour choisir un seuil de décision, à partir de la
sensibilité (ou de la spécificité) que l’on souhaite garantir.

Courbe précision-rappel (PR)

• La courbe précision-rappel vient souvent complémenter la courbe ROC.

o On appelle courbe précision-rappel, ou courbe PR, ou Precision-Recall curve
en anglais, la courbe décrivant l’évolution de la précision en fonction du rappel,
lorsque le seuil de décision change.
o Pour synthétiser cette courbe, on peut utiliser l’aire sous celle-ci, souvent
abrégée AUPR pour Area Under the Precision-Recall curve.

Reprenons l’exemple précédent pour construire une courbe précision-rappel. Les valeurs de la
précision et du rappel sont les suivantes :

23 | P a g e
On obtient donc la courbe précision-rappel visible sur la figure 3.5.

Erreurs de régression

• Dans le cas d’un problème de régression, le nombre d’erreurs n’est pas un critère
approprié pour évaluer la performance.
o On préférera quantifier la performance d’un modèle de régression en fonction
de l’écart entre les prédictions et les valeurs réelles.
• Un premier critère est donc l’erreur quadratique moyenne :
o Etant donné n étiquettes réelles 𝑦1 , 𝑦 2 , … , 𝑦 3 et n prédictions
𝑓(x⃗1 ), 𝑓(x⃗ 2 ), … , 𝑓(x⃗ 𝑛 ), on appelle erreur quadratique moyenne, ou MSE de
l’anglais mean squared error, la valeur :
𝑛
1
𝑀𝑆𝐸 = ∑(𝑓(x⃗ 𝑖 ) − 𝑦 𝑖 )2
𝑛
𝑖=1
• Pour mesurer l’erreur dans la même unité que la cible, on lui préfère souvent sa racine :
o Etant donné n étiquettes réelles 𝑦1 , 𝑦 2 , … , 𝑦 3 et n prédictions
𝑓(x⃗1 ), 𝑓(x⃗ 2 ), … , 𝑓(x⃗ 𝑛 ), on appelle racine de l’erreur quadratique moyenne,
ou RMSE de l’anglais root mean squared error, la valeur :
𝑛
1
𝑅𝑀𝑆𝐸 = √ ∑(𝑓(x⃗ 𝑖 ) − 𝑦 𝑖 )2
𝑛
𝑖=1

• L’interprétation de ces erreurs requiert néanmoins de connaître la distribution des

valeurs cibles.
o Pour répondre à cela, il est possible de normaliser la somme des carrés des
résidus non pas en en faisant la moyenne, mais en la comparant à la somme des
distances des valeurs cibles à leur moyenne.

24 | P a g e
o Etant donné n étiquettes réelles 𝑦1 , 𝑦 2 , … , 𝑦 3 et n prédictions
𝑓(x⃗1 ), 𝑓(x⃗ 2 ), … , 𝑓(x⃗ 𝑛 ), on appelle erreur carrée relative, ou RSE de l’anglais
relative squared error, la valeur :
∑𝑛𝑖=1(𝑓(x⃗ 𝑖 ) − 𝑦 𝑖 )2
𝑅𝑆𝐸 =
1
∑𝑛𝑖=1(𝑦 𝑖 − ∑𝑛𝑙 𝑦 𝑙 )2
𝑛
o Le complémentaire à 1 de la RSE est le coefficient de détermination, noté 𝑅 2 .
▪ On note le coefficient de détermination 𝑅 2 car il s’agit du carré du
coefficient de corrélation entre y ⃗ et (𝑓(x⃗1 ), 𝑓(x⃗ 2 ), … , 𝑓(x⃗ 𝑛 ) donné par :

o R est compris entre -1 et 1.

o Le coefficient 𝑅 2 indique à quel point les valeurs prédites sont corrélées aux
valeurs réelles.
o Attention, il sera élevé aussi si elles leur sont anti corrélées.

25 | P a g e
 CHAPITRE 4.
REGRESSION PARAMETRIQUE
• Un modèle de régression paramétrique suppose que la forme analytique de la fonction
de décision est connue.
o Dans ce contexte, ce chapitre se concentre principalement sur des problèmes de
régression linéaire, c’est-à-dire ceux pour lesquels la fonction de décision est
une fonction linéaire des descripteurs.

4.1 Apprentissage supervisé d’un modèle paramétrique

• On parle de modèle paramétrique quand on utilise un algorithme d’apprentissage dont

le but est de trouver les valeurs optimales des paramètres d’un modèle dont on a défini
la forme analytique en fonction des descripteurs.
o Exemple :

Un algorithme d’apprentissage qui permet d’apprendre les coefficient α, β, γ dans la fonction

de décision suivante : 𝑓 ∶ x⃗ → 𝛼x1 + 𝛽x2 x42 + 𝛾𝑒 x3 −x5 apprend un modèle paramétrique.
Quel que soit le nombre d’observations, ce modèle ne change pas.

À l’inverse, la méthode du plus proche voisin, qui associe à x⃗ l’étiquette du point du jeu
d’entraînement dont il est le plus proche en distance euclidienne, apprend un modèle non
paramétrique : on ne sait pas écrire la fonction de décision comme une fonction des variables
prédictives. Plus il y a d’observations, plus le modèle pourra apprendre une frontière de
décision complexe

o La complexité d’un modèle paramétrique grandit avec le nombre de paramètres

à apprendre, autrement dit avec le nombre de variables.
• Étant donné un jeu 𝒟 = {(𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,2,…,𝑛 de n observations en p dimensions et leurs
étiquettes réelles, nous supposons ici que la fonction de décision f est paramétrée par le
⃗ ∈ ℝ𝑚 .
vecteur β
o Nous allons faire l’hypothèse que les erreurs, c’est-à-dire la différence entre les
étiquettes réelles et les valeurs correspondantes de f , sont normalement
distribuées, centrées en 0 : 𝑦 = 𝑓(x⃗) ∕ ⃗β) + 𝜀 𝜀 ∼ ℕ(0, 𝜎 2 )
o Selon cette hypothèse, les observations x⃗ sont la réalisation de p variables
aléatoires 𝑋1, 𝑋2, . . . , 𝑋𝑝 à valeurs réelles, leurs étiquettes 𝑦 sont la réalisation
d’une variable aléatoire 𝑌 à valeurs réelles, et ces variables aléatoires vérifient
: ℙ(𝑌 = 𝑦⁄𝑋 = x⃗ ∼ ℕ(𝑓(x⃗)⁄β ⃗ , 𝜎2)
o On note ici ℙ(𝑋 = x⃗) pour ℙ(𝑋1 = x1 , 𝑋2 = x2 , . . . , 𝑋𝑝 = xp ).

26 | P a g e
4.2 Régression linéaire

• Dans les modèles linéaires, nous cherchons à expliquer la variable cible 𝑦 par une
combinaison linéaire des descripteurs.
o Nous choisissons une fonction de décision 𝑓 de la forme : 𝑓: x⃗ ⇀ 𝛽0 +
∑𝑝𝑗=1 𝛽𝑗 xj
o Ici ⃗β ∈ ℝ𝑝+1 et donc m = p + 1
• On appelle régression linéaire le modèle de la forme 𝑓: x⃗ ⇀ 𝛽0 + ∑𝑝𝑗=1 𝛽𝑗 xj dont les
coefficients sont obtenus par minimisation de la somme des moindres carrés, à savoir :
𝑝 2
𝑛

arg min ∑ (𝑦 𝑗 − 𝛽0 − ∑ 𝛽𝑗 x𝑗 )
⃗β ∈ ℝ𝑝+1
𝑖=1 𝑗=1
o Cette minimisation peut être réécrite sous forme matricielle, en ajoutant une
colonne de 1 sur la gauche de la matrice d’observations 𝑋 ∈ ℝ𝑝 :

o La somme des moindres carrés s’écrit alors :

o Il s’agit d’une forme quadratique convexe en ⃗β, que l’on peut donc minimiser
en annulant son gradient △⃗ 𝑅𝑆𝑆 = −2𝑋 Τ (𝑦 − 𝑋β ⃗ ).
β
⃗ ∗ = 𝑋Τ𝑦
o On obtient alors : 𝑋 ⊺ 𝑋β
• Si le rang de la matrice X est égal à son nombre de colonnes, alors la somme des
moindres carrés RSS est minimisée pour : 𝛽 ∗ = (𝑋 Τ 𝑋)−1 𝑋 Τ 𝑦
o On peut aussi (et ce sera préférable quand p est grand et que l’inversion de la
matrice 𝑋 Τ 𝑋 ∈ ℝp×p est donc coûteuse) obtenir une estimation de ⃗β par un
algorithme à directions de descente.
• La régression linéaire produit un modèle interprétable, au sens où les 𝛽𝑗 permettent de
comprendre l’importance relative des variables sur la prédiction.
o En effet, plus |𝛽𝑗 | est grande, plus la j-ème variable a un effet important sur la
prédiction, et le signe de 𝛽𝑗 nous indique la direction de cet effet.
• Étant donnés un vecteur de paramètres 𝜔 en 𝑞 dimensions, et un vecteur 𝑦 à partir
duquel l’estimer, on dit que l’estimateur 𝜔∗ est le meilleur estimateur non biaisé de 𝜔,
ou BLUE pour Best Linear Unbiased Estimator, de 𝜔, si :
o 1. 𝜔∗ est un estimateur linéaire de 𝜔, autrement dit il existe une matrice A telle
que 𝜔∗ = 𝐴𝑦
o 2. 𝜔∗ est non biaisé, autrement dit, 𝐸[𝜔∗ ] = 𝜔.

27 | P a g e
 o 3. Quel que soit l’estimateur linéaire non biaisé 𝜔 ̃ de 𝜔, la variance de cet
∗
estimateur est supérieure ou égale à celle de 𝜔 .
• Soient n observations x⃗1 , x⃗ 2,…, x⃗ n ∈ ℝp et leurs étiquettes 𝑦1 , 𝑦 2 , … , 𝑦 𝑛 ∈ R. Sous
l’hypothèse que, pour tout i, 𝑦𝑖 = 𝛽0 + ∑𝑝𝑗=1 𝛽𝑗 x𝑗𝑖 + 𝜀 𝑖 et que les 𝜀 𝑖 sont normalement
distribuées et centrées en 0, alors l’estimateur de 𝛽 par la méthode des moindres carrés
en est l’unique BLUE.
o L’hypothèse de normalité sur 𝜀 n’est pas nécessaire : il suffit que les erreurs
{𝜀𝑖 }𝑖=1,…,𝑛 aient une espérance nulle, aient la même variance finie 𝜎 2 (on parle
d’homoscédasticité), et ne soient pas corrélées entre elles (𝑐𝑜𝑣(𝜀𝑖 , 𝜀𝑙 ) = 0 pour
𝑖 ≠ 𝑙).

4.3 Régression logistique

• Supposons maintenant que nous voulions résoudre un problème de classification

binaire de manière linéaire, c’est-à-dire modéliser 𝑦 ∈ {0, 1} à l’aide d’une
combinaison linéaire de variables.
o Nous pourrions alors envisager un modèle probabiliste, dans lequel 𝑃(𝑌 =
𝑦|𝑋 = x⃗) soit modélisé par une combinaison linéaire des variables de x⃗.
o Cependant, 𝑃(𝑌 = 𝑦|𝑋 = x⃗) doit être comprise entre 0 et 1, et intuitivement,
cette fonction n’est pas linéaire :
▪ si 𝑃(𝑌 = 0|𝑋 = x⃗ ) est très proche de 1, autrement dit qu’il est très
probable que x⃗ est négative, une petite perturbation de x⃗ ne doit pas
beaucoup affecter cette probabilité ;
▪ mais à l’inverse, si 𝑃(𝑌 = 0|𝑋 = x⃗ ) est très proche de 0,5, autrement
dit que l’on est très peu certain de l’étiquette de x⃗, rien ne s’oppose à ce
qu’une petite perturbation de x⃗ n’affecte cette probabilité.
o C’est pour cela qu’il est classique de modéliser une transformation logit de
𝑃(𝑌 = 0|𝑋 = x⃗ ) comme une combinaison linéaire des variables.
o On appelle fonction logit la fonction :
logit: [0,1] → ℝ
p
p → log
1−p

o On appelle fonction logistique la fonction :

σ: ℝ → [0,1]
1 𝑒𝜇
μ→ =
1 + 𝑒 −𝜇 1 + 𝑒𝜇
o La fonction logit (figure 5.2a) est la réciproque de la fonction logistique (figure
5.2b).

28 | P a g e
 ⃗)
P(Y=1|x
• Ainsi, nous cherchons donc à modéliser log ⃗)
comme la combinaison linéaire
1−P(Y=1|x
⃗ Τ x⃗, où, de manière équivalente, ℙ(𝑌 = 1|x⃗) comme 𝜎(β
β ⃗ ⊺ x⃗).

• Étant donné n observations 𝒟 = {(𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,2,…,𝑛 que l’on suppose iid, le log de la
⃗ est :
vraisemblance de β

où C est une constante par rapport à ⃗β. Nous cherchons à maximiser cette
vraisemblance.

• ⃗ Τ x⃗) dont les coefficients sont

On appelle régression logistique le modèle 𝑓 : x → 𝜎(β
obtenus par :
𝑛
⃗ Τ x⃗ 𝑖 ) + (1 − 𝑦 𝑖 ) log (1 − 𝜎(β
arg max ∑ 𝑦 𝑖 log 𝜎(β ⃗ Τ x⃗ 𝑖 ))
⃗β ∈ ℝ𝑝+1
𝑖=1
o Maximiser la vraisemblance de 𝛽 sous ce modèle est équivalent à minimiser le
risque empirique défini en utilisant la fonction de coût logistique.
o La vraisemblance de la régression logistique est une fonction concave.
o Le gradient en ⃗β du maximum de vraisemblance de la régression logistique
vaut :

29 | P a g e
 o Ce gradient ne peut pas être annulé de manière analytique et la régression
logistique n’admet donc pas de solution explicite.
▪ On trouvera généralement sa solution par l’algorithme du gradient ou
une de ses variantes.
▪ Ces algorithmes convergent vers la solution optimale car la
vraisemblance est concave et n’admet donc pas de maximum local.

4.3 Régression polynomiale

• Dans le cas de la régression polynomiale de degré d, on cherche maintenant une

fonction de décision de la forme suivante :

o Il s’agit en fait d’une régression linéaire sur p×d variables :

x1 , x2 , … , x𝑝 , x12 , x22 , … , x𝑝2 , … , x1𝑑 , x2𝑑 , … , x𝑝𝑑

30 | P a g e
 CHAPITRE 5.
REGULARISATION
• Lorsque les variables explicatives sont corrélées, ou trop nombreuses, la complexité
d’un modèle de régression linéaire est bien souvent trop élevée.
o Ce qui conduit à une situation de sur-apprentissage.
o Dans ce chapitre, nous verrons comment régulariser ces modèles en contrôlant
les coefficients de régression, c’est-à-dire les poids affectés à chacune des
variables dans leur combinaison linéaire.

5.1 Qu’est-ce que la régularisation

• On appelle régularisation le fait d’apprendre un modèle en minimisant la somme du

risque empirique sur le jeu d’entraînement et d’un terme de contrainte Ω sur les
solutions possibles:
𝑛
1
𝑓 = arg min ∑ 𝐿(ℎ( x⃗ 𝑖 , 𝑦 𝑖 ) + 𝜆Ω(ℎ)
h∈𝐹 𝑛
𝑖=1

où le coefficient de régularisation 𝜆 ∈ 𝑅+ contrôle l’importance relative de chacun des

termes.

• Dans le cas d’un modèle de régression linéaire, nous allons utiliser comme fonction de
perte la somme des moindres carrés.
o Les régulariseurs que nous allons voir sont fonction du vecteur de coefficients
de régression ⃗β :

o Ou, de manière équivalente

support

• Le coefficient de régularisation 𝜆 est un hyperparamètre de la régression linéaire

régularisée.
o Quand 𝜆 tend vers +∞, le terme de régularisation prend de plus en plus
d’importance, jusqu’à ce qu’il domine le terme d’erreur et que seule compte la
minimisation du régulariseur.
o Dans la plupart des cas, le régulariseur est minimisé quand β ⃗ = ⃗0 , et il n’y a
plus d’apprentissage.

31 | P a g e
 o À l’inverse, quand 𝜆 tend vers 0, le terme de régularisation devient négligeable
devant le terme d’erreur, et ⃗β prendra comme valeur une solution de la
régression linéaire non régularisée.
o Comme tout hyperparamètre, 𝜆 peut être choisi par validation croisée.
o On utilisera généralement une grille de valeurs logarithmique.

5.1 La régression Ridge

• Une des formes les plus courantes de régularisation, utilisée dans de nombreux
domaines faisant intervenir des problèmes inverses mal posés, consiste à utiliser comme
régulariseur la norme 𝑙2 du vecteur ⃗β :

• On appelle régression ridge le modèle 𝑓: x ⇀ ⃗β⊺ x⃗ 𝑖 dont les coefficients sont obtenus par
:

o Ce problème est un problème d’optimisation convexe : il s’agit de minimiser

une fonction quadratique.
o Il se résout en annulant la gradient en ⃗β de la fonction objective :

o En notant 𝐼𝑝 ∈ ℝp×p la matrice identité en dimension p, on obtient :

o Comme 𝜆 > 0, la matrice 𝜆𝐼𝑝 + 𝑋 Τ 𝑋 est toujours inversible.

o Notre problème admet donc toujours une unique solution explicite.
o La régularisation par la norme 𝑙2 a permis de transformer un problème potentiellement
mal posé en un problème bien posé, dont la solution est :

• Note :
o Si l’on multiplie la variable x𝑗 par une constante α, le coefficient correspondant
dans la régression linéaire non régularisée est divisé par α.

32 | P a g e
 ▪ En effet, si on appelle 𝑋 ∗ la matrice obtenue en remplaçant x𝑗 par αx𝑗
dans X, la solution β ⃗ ∗ de la régression linéaire correspondante vérifie
⃗ − 𝑋 ∗ ⃗β∗ ) = 0, tandis que la solution ⃗β de la régression linéaire sur
𝑋 ∗ (y
X vérifie 𝑋(y ⃗ − 𝑋β⃗)=0
▪ Ainsi, changer l’échelle d’une variable a comme seul impact sur la
régression linéaire non régularisée d’ajuster le coefficient correspondant
de manière inversement proportionnelle.
o À l’inverse, dans le cas de la régression ridge, remplacer x𝑗 par αx𝑗 affecte aussi
le terme de régularisation, et a un effet plus complexe.
▪ L’échelle relative des différentes variables peut donc fortement affecter
la régression ridge.
▪ Il est ainsi recommandé de standardiser les variables avant
l’apprentissage, c’est-à-dire de toutes les ramener à avoir un écart-type
de 1 en les divisant par leur écart-type :

o Attention : pour éviter le sur-apprentissage, il est important que cet écart-type

soit calculé sur le jeu d’entraînement uniquement, puis appliqué ensuite aux
jeux de test ou validation.
• On appelle chemin de régularisation l’évolution de la valeur du coefficient de
régression d’une variable en fonction du coefficient de régularisation 𝜆.
o Le chemin de régularisation permet de comprendre l’effet de la régularisation
sur les valeurs de ⃗β.

5.2 Le Lasso

• Dans certaines applications, il peut être raisonnable de supposer que l’étiquette que l’on
cherche à prédire n’est expliquée que par un nombre restreint de variables.

33 | P a g e
 o Il est dans ce cas souhaitable d’avoir un modèle parcimonieux, ou sparse, c’est-
à-dire dans lequel un certain nombre de coefficients sont nuls : les variables
correspondantes peuvent être retirées du modèle.
o Pour ce faire, on peut utiliser, comme régulateur, la norme 𝑙1 du coefficient ⃗β :

• On appelle lasso le modèle 𝑓: x ⇀ ⃗βΤ x⃗ 𝑖 dont les coefficients sont obtenus par :

• Le nom de lasso est en fait un acronyme, pour Least Absolute Shrinkage and Selection
Operator.
o Il s’agit d’une méthode qui utilise les valeurs absolues des coefficients (la
norme 𝑙1) pour réduire (shrink) ces coefficients.
o Ce qui permet de sélectionner les variables qui n’auront pas un coefficient nul.
o En traitement du signal, le lasso est aussi connu sous le nom de poursuite de
base (basis pursuit en anglais).
• En créant un modèle parcimonieux et en permettant d’éliminer les variables ayant un
coefficient nul, le lasso est une méthode de sélection de variable supervisée.
o Il s’agit donc aussi d’une méthode de réduction de dimension.
• Le lasso n’admet pas de solution explicite.
o On pourra utiliser un algorithme à directions de descente pour le résoudre.
o De plus, il ne s’agit pas toujours d’un problème strictement convexe (en
particulier, quand p > n) et il n’admet donc pas nécessairement une unique
solution.
• Sur le chemin de régularisation du lasso (par exemple figure 6.4), on observe que les
variables sortent du modèle les unes après les autres, jusqu’à ce que tous les coefficients
soient nuls.
o On remarquera aussi que le chemin de régularisation pour n’importe quelle
variable est linéaire par morceaux ; c’est une propriété du lasso.

34 | P a g e
5.3 Elastic Net

• La régularisation par la norme 𝑙1 permet d’obtenir un modèle parcimonieux et donc

plus facilement interprétable.
o La régularisation par la norme 𝑙2 permet d’éviter le sur-apprentissage et de
grouper les variables corrélées.
o Il est assez naturel de souhaiter combiner les deux normes dans le régulariseur
suivant :

• Ce régulariseur est paramétré par α ∈ [0, 1].

o Quand α = 0, on retrouve la régularisation 𝑙1.
o Quand α = 1, la régularisation 𝑙2 .
• On appelle lasso le modèle 𝑓: x ⇀ ⃗βΤ x⃗ 𝑖 dont les coefficients sont obtenus par :

• On obtient la solution de l’Elastic net par un algorithme à directions de descente.

o Cette solution est parcimonieuse, mais moins que celle du lasso.

35 | P a g e
▪ En effet, quand plusieurs variables fortement corrélées sont pertinentes,
le lasso sélectionnera une seule d’entre elles, tandis que, par effet de la
norme 𝑙2 , l’Elastic net les sélectionnera toutes et leur affectera le même
coefficient.

36 | P a g e
 CHAPITRE 6.
METHODE DES PLUS PROCHES VOISINS
• Ce chapitre présente un algorithme de prédiction non paramétrique conceptuellement
très simple mais néanmoins puissant.
o Il permet de construire des frontières de décision complexes sans faire aucune
hypothèse sur la distribution des données.
o Cet algorithme, dit des plus proches voisins, se base sur le principe de « qui se
ressemble s’assemble ».
o Il utilise les étiquettes des exemples les plus proches pour prendre une décision.
• Cet algorithme s’applique aussi bien à un problème de classification qu’à un problème
de régression.

6.1 Méthode des k plus proches voisins

• Étant donné un jeu 𝒟 = {(𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,2,…,𝑛 de n observations étiquetées, une distance d

sur 𝜒 et un hyperparamètre 𝑘 ∈ ℕ∗ , on appelle algorithme des k plus proches voisins,
ou kNN pour k nearest neighbors en anglais, l’algorithme consistant à étiqueter une
nouvelle observation x⃗ en fonction des étiquettes des k points du jeu d’entraînement
dont elle est la plus proche.
o En notant ℕ𝑘 (x⃗) l’ensemble des k plus proches voisins de x⃗ dans 𝒟 :
▪ Pour un problème de classification, on appelle le vote de la majorité, et
x⃗ prend l’étiquette majoritaire parmi celles de ses k plus proches
voisins :

▪ Pour un problème de régression, x⃗ prend comme étiquette la moyenne

des étiquettes de ses k plus proches voisins :

▪ Dans le cas où k = 1, on retrouve l’algorithme du plus proche voisin.

o L’algorithme des k plus proches voisins est un exemple d’apprentissage non
paramétrique : la fonction de décision s’exprime en fonction des données
observées et non pas comme une formule analytique fonction des variables.

37 | P a g e
• La frontière de décision de l’algorithme des k plus proches voisins est linéaire par
morceaux ;
o quand k augmente, elle devient plus « simple », car le vote de la majorité permet
de lisser les aspérités créées par les exemples individuels, comme on le voit sur
la figure 8.3.

• On parle parfois d’apprentissage paresseux, ou lazy learning en anglais, pour qualifier

l’algorithme des k plus proches voisins.
o En effet, la procédure d’apprentissage consiste uniquement à stocker les
données du jeu d’entraînement et ne comporte aucun calcul.
o Attention, cela peut être un facteur limitant, au niveau de la mémoire, si le jeu
d’entraînement est très grand.
• À l’inverse, la procédure de prédiction requiert de calculer la distance de l’observation
à étiqueter à chaque observation du jeu d’entraînement, ce qui peut être intensif en
temps de calcul si ce jeu d’entraînement est très grand.
o Une prédiction requiert en effet de calculer n distances, une opération d’une
complexité de l’ordre 𝒪(np) de 𝑝 dimensions, puis de trouver les k plus petites
de ces distances, une opération d’une complexité en 𝒪(n log k).
• Comme nous l’avons décrit ci-dessus, nous proposons d’utiliser k > 1 pour rendre
l’algorithme des k plus proches voisins plus robuste au bruit.
o Cependant, à l’inverse, si k = n, l’algorithme prédira,
▪Dans le cas d’un problème de classification, la classe majoritaire dans
𝒟,
▪ Dans le cas d’un problème de régression, la moyenne des étiquettes de
𝒟,
▪ Ce qui paraît tout aussi peu satisfaisant.
o Il faudra donc choisir une valeur de k intermédiaire, ce que l’on fera
généralement en utilisant une validation croisée.
▪ L’heuristique 𝑘 ≈ √𝑛 est aussi parfois utilisée.

38 | P a g e
6.2 Distances et Similarités

Distances

• L’ingrédient essentiel de l’algorithme des k plus proches voisin est la distance

permettant de déterminer quelles sont les observations du jeu d’entraînement les plus
proches du point à étiqueter.
o Étant donné un ensemble 𝜒, on appelle distance sur 𝜒 toute fonction d :𝜒 × 𝜒
→ ℝ vérifiant les trois propriétés suivantes :
▪ 1. Séparation : ∀ u ⃗, v
⃗ ∈ 𝜒 × 𝜒, 𝑑(u ⃗ ,v
⃗ ) = 0 ⇔ u ⃗ = v ⃗ .
▪ 2. Symétrie : ∀ u ⃗ ,v
⃗ ∈ 𝜒 × 𝜒, d(u ⃗ ,v
⃗ ) = d(v ⃗ ,u
⃗ ).
3
▪ 3. Inégalité triangulaire : ∀ t, u
⃗ ⃗ ,v
⃗ ∈ 𝜒 , d(u ⃗ ,v
⃗ ) ≤ d(u ⃗ , t) + d(t , v
⃗ ).
• 𝑝
Dans le cas où 𝜒 = ℝ , on utilisera le plus souvent une distance de Minkowski.
o Étant donné q fixé, q ≥ 1, on appelle distance de Minkowski la distance définie
par:

o La distance euclidienne est le cas particulier q = 2 : 𝑑2 (u ⃗) =

⃗ ,v
2
√∑𝑝𝑗=1(𝑢𝑗 − 𝑣𝑗 )
• Quand q = 1, on parle de distance de Manhattan, ou distance du chauffeur de taxi,
car dans le plan elle consiste à calculer la distance parcourue entre u
⃗ et v
⃗ en se déplaçant
uniquement parallèlement aux axes, comme ce serait le cas d’un taxi dans Manhattan,
où les rues forment un quadrillage : 𝑑1 (𝑢 ⃗ , 𝑣 ) = ∑𝑝𝑗=1|𝑢𝑗 − 𝑣𝑗 |
o Enfin, la distance 𝑙∞ , ainsi nommée en référence à l’espace de suites 𝑙 ∞ , et notée
𝑑∞ , est la différence maximale entre 𝑢
⃗ et 𝑣 sur une dimension :

𝑑∞ (𝑢
⃗ , 𝑣) = max |𝑢𝑗 − 𝑣𝑗 |
𝑗=1,…,𝑝

o On l’appelle aussi distance de Tchebychev.

o La distance 𝑙∞ est la limite quand q→∞ de la distance de Minkowski.

Similarités entre vecteurs réels

• Cependant, il n’est pas nécessaire pour appliquer l’algorithme des k plus proches
voisins d’utiliser une distance : une notion de similarité est suffisante.
• On appelle similarité sur 𝜒 toute fonction s : 𝜒 × 𝜒 → ℝ+ qui est d’autant plus grande
que les deux éléments de 𝜒 qu’elle compare sont semblables.
o Contrairement à une distance, une similarité n’a pas de propriétés
mathématiques particulières.

39 | P a g e
 o Il est possible de transformer n’importe quelle distance en similarité, en
utilisant par exemple la transformation s(u
⃗,v
⃗ ) = −d(u
⃗,v⃗ ), ou 𝑠(u
⃗,v
⃗) =
1
⃗ ,v
).
⃗)
1+𝑑(u
• Une notion de similarité fréquemment utilisée lorsque 𝜒 = ℝ𝑝 est celle du coefficient
de corrélation.
o Étant donnés u⃗,v⃗ ∈ ℝ𝑝 , on appelle coefficient de corrélation ou corrélation de
Pearson entre u
⃗ et v⃗ la valeur :

o Remarquons que si l’on appelle u ⃗ ′ (resp. v

⃗ ′ ) la version centrée de u
⃗ (resp. v
⃗ ),
c’est-à-dire le vecteur obtenu en lui retranchant la moyenne de ses coordonnées
1
⃗ − 𝑝 ∑𝑝𝑗=1 𝑢𝑗 , ce coefficient se simplifie en :
⃗′=u
:u

o Et vaut donc le cosinus de l’angle entre u ⃗ ′ et v

⃗ ′.
▪ C’est pour cette raison qu’on appelle parfois ρ la similarité cosinus.
o Si en plus d’être centrés, les vecteurs u ⃗ et v⃗ sont normalisés, la similarité cosinus se
réduit au produit scalaire entre u
⃗ et v
⃗.
o La valeur absolue de ce produit scalaire est d’autant plus grande que les vecteurs u ⃗ et
⃗ sont colinéaires, et vaut 0 quand les vecteurs sont orthogonaux.
v
• Note : En général, la similarité cosinus et la distance euclidienne ne définissent pas les
mêmes voisinages.

Similarités entre ensembles

• Jusqu’à présent, nous avons uniquement traité de données qui peuvent être représentées
par un vecteur réel.
o Cependant, il arrive souvent que nos observations soient plus aisément
représentées comme des sous-ensembles d’un même ensemble fini d’éléments.
▪ Par exemple, une chaîne de caractères peut être représentée par
l’ensemble des lettres qu’elle contient, ou un document texte par
l’ensemble des mots qu’il contient.
o Ces représentations peuvent être transformées en vecteurs binaires : un sous
ensemble 𝒮 de ℰ peut être représenté comme un vecteur binaire de taille | ℰ |
dont chaque bit correspond à un élément e de ℰ et vaut 1 si e ∈ 𝒮 et 0 sinon.

40 | P a g e
 o On peut alors appliquer les distances ou similarités précédentes à ces
représentations vectorielles.
• On peut aussi définir des distances ou des similarités directement sur ces ensembles,
sans passer par une représentation vectorielle dont la dimension pourrait être très grande
(autant que le nombre de mots dans le dictionnaire, dans le cas de la représentation d’un
document par les mots qu’il contient), bien que potentiellement parcimonieuse (la
plupart des documents contiendront peu de mots, relativement au dictionnaire).
o On peut choisir de comparer deux ensembles en fonction du nombre d’éléments
qui apparaissent dans un seul d’entre eux.
o La distance de Hamming entre deux sous-ensembles 𝒮 et 𝒯 de ℰ est définie
comme:

𝐻(𝒮 , 𝒯 ) = |𝒮 − 𝒯 |,

Où 𝒮 Δ 𝒯 = {𝑒 ∈ 𝒮 ∖ 𝒯} ⋃{𝑒 ∈ 𝒯 ∖ 𝒮} est la différence symétrique entre 𝒮 et 𝒯.

o En utilisant une représentation binaire de 𝒮 et 𝒯, la distance de Hamming est le

nombre de bits différents entre ces deux vecteurs, et est équivalente à leur
distance de Manhattan.
• Deux ensembles sont considérés être d’autant plus semblables qu’ils ont d’éléments en
commun.
o Attention, si l’on compare des ensembles susceptibles d’être de tailles très
différentes, cela doit être comparé au nombre d’éléments qu’ils pourraient avoir
en commun : deux ensembles de grande taille auront naturellement plus
d’éléments communs que deux ensembles de petite taille.
o On utilisera pour cela la similarité de Jaccard.
• Étant donné un ensemble ℰ d’éléments, on appelle similarité de Jaccard, similarité de
Tanimoto, ou encore index de Jaccard la fonction :

o Ici 2ℰ désigne l’ensemble des parties de ℰ, autrement dit l’ensemble de ses sous-
ensembles.
o Cette notation est choisie car, du moins dans le cas fini, un sous-ensemble 𝒮 ⊆
ℰ peut être représenté comme une fonction binaire de ℰ vers {0, 1} qui associe
1 à un élément de ℰ présent dans 𝒮, et 0 aux autres.
• Si les éléments sont susceptibles d’apparaître plusieurs fois dans chaque « ensemble »
(il ne s’agira alors plus d’ensembles, mais de multi-ensembles), on peut prendre en
compte la multiplicité des éléments en utilisant la similarité MinMax.
o Étant donné un multi-ensemble 𝒮 de ℰ, et un élément e ∈ ℰ, on note 𝑚𝒮 (e) la
multiplicité de e dans 𝒮, autrement dit son nombre d’occurrences dans 𝒮.

41 | P a g e
 o Étant donné un ensemble E d’éléments, on appelle similarité MinMax entre
deux multiensembles 𝒮 et 𝒯 de ℰ la fonction qui retourne :

6.3 Filtrage collaboratif

• Le filtrage collaboratif, ou collaborative filtering en anglais, est à la base des systèmes

de recommandation, tels que ceux utilisés par Netflix ou Amazon, qui utilisent les
évaluations d’un groupe pour proposer des recommandations à un individu.
o L’hypothèse qui est faite est telle que des utilisateurs aux goûts similaires vont
continuer à aimer les mêmes choses.
o Plus précisément, étant donnés un ensemble 𝒮 d’objets (films, livres, achats,
etc.), un ensemble 𝒳 d’utilisateurs, nous supposons l’existence d’une fonction
𝑟 ∶ 𝒳 × 𝒮 → ℝ telle que 𝑟(𝑢, 𝑎) est la note donnée par l’utilisateur u à l’objet
a.
o Cette fonction est partiellement connue, au sens où tous les utilisateurs n’ont
pas noté tous les objets.
o En notant, pour tout (a, b) ∈ 𝒮 × 𝒮, 𝒰(𝑎, 𝑏) le sous-ensemble de 𝒳 contenant
uniquement les utilisateurs qui ont noté à la fois a et b, et pour tout 𝑢 ∈ 𝒳, r(u)
la note moyenne donnée par u, on peut alors définir une similarité entre objets
sur la base de la similarité cosinus :

• Appelons maintenant 𝒩𝑢𝑘 (𝑎) les k plus proches voisins de a parmi les objets notés par
u.
o On peut recommander l’objet a pour l’utilisateur u par :

42 | P a g e
 CHAPITRE 7.
ARBRE ET FORETS
• L’algorithme des plus proches voisins permet de construire des modèles non
paramétriques métriques, c’est-à-dire qu’ils reposent sur la définition d’une distance ou
similarité pertinente entre les observations.
o Cela n’est pas toujours chose aisée, et les arbres de décision approchent le
problème différemment.
o Non métriques, hiérarchiques, et non paramétriques, ils présentent
d’intéressantes propriétés, en particulier en ce qui concerne les attributs discrets.
o Cependant, ils ont tendance à mal apprendre, et à avoir de faibles propriétés de
généralisation.

7.1 Arbres de décision

Apprentissage hiérarchique

• Les arbres de décision sont des modèles hiérarchiques, qui se comportent comme une
série successive de tests conditionnels, dans laquelle chaque test dépend de ses
antécédents.
o Ils sont couramment utilisés en dehors du monde du machine learning, par
exemple pour décrire les étapes d’un diagnostic ou d’un choix de traitement
pour un médecin, ou les chemins possibles dans un « livre dont vous êtes le
héros ».
o La figure 9.1 présente un tel arbre de décision.

• La figure 9.1 nous permet d’illustrer trois propriétés des arbres de décision :
o Ils permettent de traiter des attributs discrets (comme ici la forme, la taille et la
couleur), sans nécessiter une notion de similarité ou d’ordre sur ces attributs (on
parle d’apprentissage non métrique).
o Ils permettent de traiter un problème de classification multi-classe sans passer
par des classifications binaires.

43 | P a g e
 o Ils permettent de traiter des classes multi-modales (comme ici pour l’étiquette
« pomme », qui est affectée à un fruit grand et rouge ou à un fruit jaune et rond).
• On appelle arbre de décision un modèle de prédiction qui peut être représenté sous la
forme d’un arbre.
o Chaque nœud de l’arbre teste une condition sur une variable et chacun de ses
enfants correspond à une réponse possible à cette condition.
o Les feuilles de l’arbre correspondent à une étiquette.
o Pour prédire l’étiquette d’une observation, on « suit » les réponses aux tests
depuis la racine de l’arbre, et on retourne l’étiquette de la feuille à laquelle on
arrive.

Partition de l’espace par un arbre de décision

• Un arbre de décision partitionne l’espace 𝜒 des observations en autant de régions qu’il
a de feuilles ; au sein d’une même région, toutes les observations reçoivent alors la
même étiquette.
o Dans le cas d’un problème de classification, cette étiquette est l’étiquette
majoritaire dans la région.
o En supposant n observations x⃗1 , x⃗2 , . . . , x⃗𝑛 de 𝜒 étiquetées par 𝑦1 , 𝑦2 , . . . , 𝑦𝑛 ,
et R régions 𝑅1 , 𝑅2 , . . . , 𝑅𝑅 , on peut écrire :

o Pour un problème de régression, cette étiquette est l’étiquette moyenne des

observations dans cette région :

• Ces notations sont lourdes et on préférera éviter d’essayer d’écrire la fonction de

décision d’un arbre de décision sous forme analytique.
o Cependant, il est important de retenir qu’un arbre de décision partitionne le jeu
d’entraînement de manière récursive en des sous-ensembles de plus en plus
petits.
o Une telle partition est illustrée sur la figure 9.2 pour des variables réelles.

44 | P a g e
7.2 Comment faire pousser un arbre

CART

• L’algorithme utilisé pour entraîner un arbre de décision est appelé CART, pour
Classification And Regression Tree (Breiman et al., 1984).
o Il s’agit d’un algorithme de partitionnement de l’espace par une approche
gloutonne, récursive et divisive.
o CART peut être utilisé pour entraîner un arbre de décision binaire, c’est-à-dire
dans lequel chaque nœud a exactement deux enfants, sans perte de généralité.
o En effet, tout arbre peut être réexprimé sous la forme d’un arbre binaire, comme
l’illustre la figure 9.3.

• Comme illustré sur la figure 9.2, CART partitionne les données une variable à la fois,
ce qui produit une frontière de décision orthogonale aux axes.

45 | P a g e
 o Nous supposons par la suite que les données sont définies dans un espace 𝜒 de
dimension p.
• À chaque nœud d’un arbre de décision construit par CART correspond une variable
séparatrice (splitting variable) j ∈ {1, . . . , p} selon laquelle vont être partitionnées les
données.
o Cette variable séparatrice définit deux régions, correspondant aux enfants du
nœud considéré.
o Dans le cas où la variable de séparation est binaire, ces deux régions sont :

𝑅𝑙 (𝑗, 𝑠) = {x⃗: x𝑗 = 0} ; 𝑅𝑟 (𝑗, 𝑠) = {x⃗: x𝑗 = 1}

o Dans le cas où la variable de séparation est une variable discrète pouvant

prendre plus de deux valeurs (ou modalités), elle s’accompagne alors d’un sous-
ensemble de ces valeurs 𝒮 ⊂ dom(x𝑗 ).
o Les deux régions sont :

𝑅𝑙 (𝑗, 𝑠) = {x⃗: x𝑗 ∈ 𝒮} ; 𝑅𝑟 (𝑗, 𝑠) = {x⃗: x𝑗 ∉ 𝒮}

• Enfin, dans le cas où la variable de séparation est une variable réelle, elle s’accompagne
alors d’un point de séparation (splitting point) s qui est la valeur de l’attribut par rapport
à laquelle va se faire la décision.
o Les deux régions sont alors :

𝑅𝑙 (𝑗, 𝑠) = {x⃗: x𝑗 < 𝑠} ; 𝑅𝑟 (𝑗, 𝑠) = {x⃗: x𝑗 ≥ 𝑠}

o À chaque itération de l’algorithme CART, on itère sur toutes les valeurs

possibles de j et, le cas échéant, toutes les valeurs possibles de s ou 𝒮 pour
déterminer le couple (j, s) qui minimise un critère prédéfini.
• Dans le cas d’un problème de régression, ce critère est généralement l’erreur
quadratique moyenne :
o à quel point la partition en (j, s) permet-elle de regrouper des observations
d’étiquettes proches ?
o On choisit donc la variable et le point de séparation comme :

où 𝑦𝑙 (𝑗, 𝑠) (resp. 𝑦𝑟 (𝑗, 𝑠)) est l’étiquette associée à la région 𝑅𝑙 (𝑗, 𝑠) (resp. 𝑅𝑟 (𝑗, 𝑠)) à ce stade,
soit donc la moyenne des étiquettes de cette région.

• Dans le cas d’un problème de classification, on utilise plutôt que l’erreur quadratique
moyenne un critère d’impureté, ainsi appelé car il quantifie à quel point la région
considérée est « polluée » par des éléments des classes qui n’y sont pas majoritaires.

46 | P a g e
 o En notant Imp ce critère, on choisit donc la variable et le point de séparation
comme:

Critères d’impureté

• Il existe plusieurs critères d’impureté, que nous détaillons dans cette section : l’erreur
de classification, l’entropie croisée et l’impureté de Gini.
o Pour les définir, nous allons utiliser la notation pc (R) pour indiquer la
proportion d’exemples d’entraînement de la région R qui appartiennent à la
classe c :

o Tout d’abord, l’erreur de classification permet de définir l’impureté d’une

région R comme la proportion d’exemples de cette région qui n’appartiennent
pas à la classe majoritaire :

▪ Si tous les exemples d’une région appartiennent à la même classe,

l’erreur de classification de cette région vaut 0 ;
▪ A l’inverse, si une région contient autant d’exemples de chacune des C
1
classes, pc (R) ≈ quelle que soit la classe c, et l’erreur de
𝐶
1 1
classification vaut 1 − 𝐶, soit 2 dans le cas d’une classification binaire.
o Ensuite, l’entropie croisée permet de définir l’impureté d’une région R de sorte
à choisir la séparation qui maximise le gain d’information.
▪ Le but de la construction est alors de minimiser la quantité d’information
supplémentaire nécessaire pour étiqueter correctement les exemples
d’entraînement de R :

▪ Si tous les exemples d’une région appartiennent à la même classe,

l’entropie croisée de cette région vaut 0 ;
▪ A l’inverse, si une région contient autant d’exemples de chacune des C
classes, l’entropie croisée vaut log 2 (C), soit 1 dans le cas d’une
classification binaire.

47 | P a g e
 o Enfin, la définition la plus utilisée de l’impureté est l’impureté de Gini, qui
permet de quantifier la probabilité qu’un exemple du jeu d’entraînement soit
mal étiqueté s’il était étiqueté aléatoirement en fonction de la distribution des
étiquettes dans R.
▪ L’impureté de Gini d’une région R est définie comme :

▪ Si tous les exemples d’une région appartiennent à la même classe,

l’impureté de Gini de cette région vaut 0 ;
▪ A l’inverse, si une région contient autant d’exemples de chacune des C
1 1
classes, l’impureté de Gini vaut 1 − 𝐶, soit dans le cas d’une
2
classification binaire.

Elaguer un arbre
• Nous avons établi une stratégie pour construire un arbre.
o Il nous faut maintenant pouvoir décider quand l’arrêter.
o En effet, si un arbre peu profond risque de mal modéliser le problème, un arbre
trop profond est susceptible de sur-apprendre.
• Une approche classique du problème est d’arrêter de diviser une région quand celle-ci
contient un nombre minimum d’exemples d’entraînement fixé par avance.
o Cela évite de construire des feuilles trop spécifiques ne contenant qu’un seul
point.
o On peut aussi choisir de limiter la profondeur de l’arbre.
• Il est également possible d’utiliser une méthode de régularisation pour contrôler la
complexité de l’arbre, mesurée par le nombre de régions qu’il définit.
o C’est ce qu’on appelle l’élagage par coût en complexité, ou cost-complexity
pruning : le coût en complexité d’un arbre T est donné par :

o où |T| est le nombre de régions définies par T, 𝑅𝑟 la r-ième de ces régions, et 𝑛𝑟

le nombre d’exemples d’entraînement qu’elle contient.
o λ > 0 est un hyperparamètre permettant de contrôler l’importance relative de la
mesure d’erreur et de la complexité.
o Cette procédure requiert de développer complètement l’arbre, puis de l’élaguer
en regroupant séquentiellement certaines régions jusqu’à ce que le critère soit
optimal.

48 | P a g e
 • Malheureusement, les arbres de décision ont tendance à donner des modèles trop
simples.
o Leurs performances de prédiction sont souvent à peine supérieures à des
modèles aléatoires et sont très sensibles aux variations dans les données.
o On les qualifie d’apprenants faibles (weak learners en anglais).
o Heureusement, il est possible d’y remédier grâce aux méthodes ensemblistes.

7.3 Méthodes ensemblistes

• Les méthodes ensemblistes sont des méthodes très puissantes en pratique, qui reposent
sur l’idée que combiner de nombreux apprenants faibles permet d’obtenir une
performance largement supérieure aux performances individuelles de ces apprenants
faibles, car leurs erreurs se compensent les unes les autres.
o Deux grandes familles d’approches permettent de créer plusieurs modèles
faibles à partir d’un unique jeu de données.
o Elles sont toutes deux basées sur un rééchantillonage du jeu de données, mais
sont conceptuellement très différentes.
▪ Le bagging, est une méthode parallèle dans laquelle les apprenants
faibles sont indépendants les uns des autres.
▪ Le boosting, est une méthode séquentielle dans laquelle chaque nouvel
apprenant est construit en fonction des performances du précédent.

Méthodes parallèles : le bagging

• Supposons un jeu de données 𝒟 de n observations ⃗⃗⃗ x1 , ⃗⃗⃗

x2 , . . . , ⃗⃗⃗⃗
x𝑛 de 𝜒 étiquetées par
𝑦1 , 𝑦2 ,…, 𝑦𝑛 .
o Le bagging, proposé par Leo Breiman (1996), consiste à former B versions de
𝒟 par échantillonage bootstrap.
o Chaque modèle faible est entraîné sur un des échantillons, ce qui peut être fait
en parallèle.
o Les B prédictions sont ensuite combinées :
▪ par vote de la majorité dans le cas d’un problème de classification ;
▪ en prenant la moyenne dans le cas d’un problème de régression.
• Le bagging permet de réduire la variance des estimateurs individuels.
o C’est ce qui lui permet d’atteindre une plus grande stabilité et une meilleure
prédiction qu’eux.
o La figure 9.5 illustre ce principe : les 5 premiers arbres qui composent le
classifieur entraîné par bagging séparent nettement moins bien le jeu de données
que le bagging,

49 | P a g e
 Forêts aléatoires

• La puissance des méthodes ensemblistes se révèle lorsque les apprenants faibles sont
indépendants conditionnellement aux données,
o Autrement dit aussi différents les uns des autres que possible, afin que leurs
erreurs puissent se compenser les unes les autres.
o Pour atteindre cet objectif, l’idée des forêts aléatoires, proposée toujours par
Leo Breiman, est de construire les arbres individuels non seulement sur des
échantillons différents (comme pour le bagging), mais aussi en utilisant des
variables différentes (Breiman, 2001).
• Plus précisément, les arbres construits pour former une forêt aléatoire diffèrent de ceux
appris par CART en ce que, à chaque nœud, on commence par sélectionner q < p
variables aléatoirement, avant de choisir la variable séparatrice parmi celles-ci.
o En classification, on utilise typiquement 𝑞 ≈ √𝑝, ce qui permet aussi de réduire
considérablement les temps de calculs puisqu’on ne considère que peu de
variables à chaque nœud (5 pour un problème à 30 variables, 31 pour un
problème avec 1000 variables).
𝑝
o Pour la régression, le choix par défaut est plutôt de 𝑞 ≈ 3
• En pratique, les forêts aléatoires sont un des algorithmes les plus performants et les plus
simples à mettre en place.
o Elles ont aussi l’avantage de peu dépendre de leurs hyperparamètres, à savoir
du nombre q de variables considérées à chaque nœud, du nombre d’observations
utilisées pour chaque arbre (n dans la procédure que nous avons décrite, mais
que l’on pourrait réduire), du nombre maximum d’observations dans les feuilles
de l’arbre (généralement fixé à 1 en classification et 5 en régression), et du
nombre d’arbres, à partir du moment où celui-ci est suffisamment grand.

50 | P a g e
 Méthodes séquentielles : le boosting

• Le bagging repose sur l’hypothèse que des apprenants ayant de bonnes performances
sur des régions différentes de l’espace 𝜒 des observations auront des erreurs
décorrélées.
o Il est donc possible de faire confiance à la majorité d’entre eux pour ne pas faire
d’erreur pour une prédiction donnée.
o L’approche séquentielle de la construction d’un ensemble cherche à créer des
modèles faibles qui se concentreront sur les erreurs du modèle.
▪ On parle alors de boosting : par itérations successives, des apprenants
faibles viennent exalter (« booster ») les performances du modèle final
qui les combine.

AdaBoost

• AdaBoost, dont le nom vient de Adaptive Boosting, est un algorithme qui permet de
construire un classifieur de manière itérative, en forçant un classifieur faible à se
concentrer sur les erreurs du modèle grâce à un système de pondération des exemples
d’entraînement.
• Supposons un jeu de données de classification binaire 𝒟 = {(𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,…,𝑛 , un nombre
d’itérations M et un algorithme d’apprentissage.
o Étant donné un jeu de données 𝒮, on note 𝑓𝒮 la fonction de décision retournée
par cet algorithme.
o Nous supposons 𝕐 = {−1, 1} et que 𝑓𝒮 est à valeur dans 𝕐.
o Nous appelons jeu de données pondérées 𝒟 ′ = {(𝑤𝑖 , 𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,…,𝑛 ∈ ℝ𝑛 ×
𝜒 𝑛 × 𝕐𝑛 un jeu de données {(𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,…,𝑛 dans lequel un poids 𝑤𝑖 a été affecté
à la ième observation.
o Nous supposons ici que l’algorithme d’apprentissage que nous utilisons est
capable d’intégrer ces pondérations.
o Dans le cas des arbres de décision, la pondération des exemples d’apprentissage
se reflète par leur pondération dans le critère d’impureté ; la décision est
également prise par vote majoritaire pondéré.
• On appelle AdaBoost la procédure de construction d’un ensemble d’apprenants
suivante :
1
o 1. Initialiser les pondérations 𝑤11 , 𝑤21 , … , 𝑤𝑛1 à 𝑛
o 2. Pour 𝑚 = 1,2, … , 𝑀 :
a. Apprendre sur le jeu des données pondéré 𝒟𝑚 =
{(w𝑖𝑚 , 𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,…,𝑛 la fonction de décision 𝑓𝑚 = 𝑓𝒟𝑚
b. Calculer l’erreur pondérée de ce modèle :

51 | P a g e
 c. En déduire la confiance que l’on peut lui associer :

𝛼𝑚 est d’autant plus élevé que l’erreur globale du modèle est faible : on pourra alors lui faire
plus confiance.

d. Actualiser les poids, de sorte à donner plus d’importance à un

exemple
d’entraînement sur lequel 𝑓𝑚 se trompe :

▪ Le rôle de Zm est d’assurer que la somme des coefficients 𝑤𝑖𝑚+1 vaut 1.

o 3. Retourner la fonction de décision finale

o Il est classique de considérer comme apprenants faibles pour AdaBoost un type

bien particulier d’arbres de décision : les arbres de décision de profondeur 1,
appelés stumps (qui signifie souche en anglais).

Boosting du gradient

• AdaBoost se trouve en fait être un cas particulier d’une famille de techniques appelées
boosting du gradient (gradient boosting, ou GBOOST).
o Ce cadre permet tout d’abord de mieux comprendre le fonctionnement
d’AdaBoost, en considérant la minimisation du risque empirique sur 𝒟 et la
fonction d’erreur exponentielle comme fonction de coût.
• Étant donné un problème de classification, on appelle fonction d’erreur exponentielle,
ou exponential loss, la fonction de coût suivante :

52 | P a g e
 o Reprenons l’algorithme AdaBoost, et appelons 𝐹𝑚 la fonction de décision
cumulative 𝐹𝑚 : x⃗ → ∑𝑚 𝑘=1 𝛼𝑘 𝑓𝑘 (x
⃗ ).
o A l’étape m, l’erreur exponentielle de 𝐹𝑚 sur le jeu d’entraînement vaut :

𝑖
o Définissons maintenant 𝑤𝑚 = exp (−𝑦 𝑖 𝐹𝑚−1 (x⃗ 𝑖 ) ; alors :

o Cette erreur est minimale quand 𝛼𝑚 a la forme donnée dans c ci-dessus (voir
Adaboost).
o Ainsi, AdaBoost combine les apprenants faibles de sorte à minimiser, à chaque
étape, l’erreur exponentielle du classifieur global.
• L’erreur exponentielle peut être remplacée par une autre fonction de coût, telle que
l’entropie croisée ou l’erreur quadratique.
o C’est ce que l’on appelle le boosting du gradient.
o GBOOST est aujourd’hui un des algorithmes les plus populaires en machine
learning.

53 | P a g e
 CHAPITRE 8.
MACHINES A VECTEURS DE SUPPORT ET METHODES A
NOYAUX
• Les machines à vecteurs de support (aussi appelées machines à vecteurs supports), ou
SVM de l’anglais support vector machines, sont de puissants algorithmes
d’apprentissage automatique.
o Elles se basent sur un algorithme linéaire mais permettent d’apprendre bien plus
que des modèles linéaires.
o En effet, grâce à l’astuce du noyau, elles peuvent être étendus efficacement à
l’apprentissage de modèles non linéaires.
o Ce chapitre présente cette approche dans ses différentes versions pour un
problème de classification, et introduit ainsi la famille des méthodes à noyaux.

8.1 Le cas linéairement séparable.

• Nous nous plaçons dans ce chapitre dans le cas d’un problème de classification binaire.
o Dans cette section, nous allons supposer qu’il est possible de trouver un modèle
linéaire qui ne fasse pas d’erreur sur nos données : c’est ce qu’on appelle un
scénario linéairement séparable.
• Soit 𝒟 = {(𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,…,𝑛 un jeu de données de n observations.
o Nous supposons que 𝑥 𝑖 ∈ ℝ𝑝 et 𝑦 𝑖 ∈ {−1,1}.
o On dit que 𝒟 est linéairement séparable s’il existe au moins un hyperplan
dans ℝ𝑝 tel que tous les points positifs (étiquetés +1) soient d’un côté de cet
hyperplan et tous les points négatifs (étiquetés −1) de l’autre.
• Dans ce cas, il existe en fait une infinité d’hyperplans séparateurs qui ne font aucune
erreur de classification (voir figure 10.1).
o Ces hyperplans sont des modèles équivalents du point de vue de la minimisation
du risque empirique.

54 | P a g e
 Marges d’un hyperplan séparateur
• En l’absence d’information supplémentaire, l’hyperplan séparateur en pointillés sur la
figure 10.1 semble préférable.
o En effet, celui-ci, étant équidistant de l’observation positive la plus proche et de
l’observation négative la plus proche, coupe en quelque sorte la poire en deux
pour la région située « entre » les points positifs et les points négatifs.
o La marge d’un hyperplan séparateur permet de formaliser cette intuition.
• La marge γ d’un hyperplan séparateur est la distance de cet hyperplan à l’observation
du jeu d’entraînement la plus proche.
o L’hyperplan séparateur que nous cherchons est donc celui qui maximise la
marge.
▪ Il y a alors au moins une observation négative et une observation
positive qui sont à une distance γ de l’hyperplan séparateur.
▪ Dans le cas contraire, si par exemple toutes les observations négatives
étaient à une distance supérieure à γ de l’hyperplan séparateur, on
pourrait rapprocher cet hyperplan des observations négatives et
augmenter la marge.
• Nous pouvons alors définir, en plus de l’hyperplan séparateur H, les hyperplans 𝐻+ et 𝐻− qui
lui sont parallèles et situés à une distance 𝛾 de part et d’autre.
o 𝐻+ contient au moins une observation positive, tandis que 𝐻− contient au
moins une observation négative.
o On appelle vecteurs de support les observations du jeu d’entraînement situés à
une distance 𝛾 de l’hyperplan séparateur.
▪ Elles « soutiennent » les hyperplans 𝐻+ et 𝐻− .
o C’est de là que vient le nom de la méthode, appelée Support Vector Machine
ou SVM en anglais, et machine à vecteurs de support en français.
▪ On rencontre aussi parfois le nom de « séparatrice à vaste marge », qui
respecte les initiales SVM.
o Toutes les observations positives sont situées à l’extérieur de 𝐻+ , tandis que
toutes les observations négatives sont situées à l’extérieur de 𝐻− .
▪ On appelle zone d’indécision la zone située entre H− et H+. Cette zone
ne contient aucune observation.
▪ La figure 10.2 illustre ces différents concepts.

55 | P a g e
 Formulation de la SVM à marge rigide
• L’équation de l’hyperplan séparateur 𝐻 que nous cherchons est de la forme (𝑤 ⃗⃗ , x⃗) + 𝑏 = 0 où
𝑝
(,) représente le produit scalaire sur ℝ .
o L’hyperplan 𝐻+ lui est parallèle, et a donc pour équation (𝑤 ⃗⃗ , x⃗) + 𝑏 = constante.
o Nous pouvons fixer cette constante à 1 sans perdre en généralité : en effet, si nous
multiplions 𝑤⃗⃗ , et 𝑏 par une constante, cela n’affectera pas l’équation de 𝐻.
o 𝐻− étant symétrique de H par rapport à 𝐻+ , son équation est alors (𝑤 ⃗⃗ , x⃗) + 𝑏 = −1.
1
o Enfin, la marge qui est la distance de 𝐻 à 𝐻+ vaut 𝛾 = ⟦𝑤
⃗⃗ ⟧
.
2

• Les observations positives vérifient donc toutes (𝑤

⃗⃗ , x⃗) + 𝑏 ≥ 1.
o De même, les points négatifs vérifient tous (𝑤 ⃗⃗ , x⃗) + 𝑏 ≤ 1.
o Ainsi, pour chacun des points de notre jeu d’entraînement, 𝑦 𝑖 (𝑤 ⃗⃗ , x⃗) + 𝑏 ≥ 1.
o L’égalité est vérifiée pour les vecteurs de support.
1
o Nous cherchons donc ici à maximiser ⟦𝑤
⃗⃗ ⟧
sous les 𝑛 contraintes 𝑦 𝑖 (𝑤
⃗⃗ , x⃗) + 𝑏 ≥ 1.
2
• On appelle SVM à marge rigide le problème d’optimisation suivant :

o Supposons 𝑤 ⃗⃗ ∗, 𝑏 ∗ solutions de l’équation ci-avant.

o La fonction de décision est alors donnée par : 𝑓(x⃗) = (𝑤⃗⃗ ∗ , x⃗) + 𝑏 ∗.
• Le problème défini par l’équation (10.1) ci-dessus est équivalent à :

o Cette équation est appelée formulation duale.

• Pour trouver 𝑏 ∗, on peut revenir à la formulation initiale de la SVM : les vecteurs de support
⃗⃗ ∗ , x⃗ 𝑖 ) + 𝑏 ∗ = 1.
positifs sont situés sur l’hyperplan 𝐻+ et vérifient (𝑤
o De plus, étant les observations positives les plus proches de l’hyperplan séparateur 𝐻,
les vecteurs de support positifs minimisent (𝑤 ⃗⃗ ∗ , x⃗ 𝑖 ).
o Ainsi : 𝑏 ∗ = 1 − min
𝑖
⃗⃗ ∗ , x⃗ 𝑖 ).
(𝑤
𝑖:𝑦 =+1
o Enfin, la fonction de décision est donnée par :

8.2 Le cas linéairement non-séparable : SVM à marge souple

• Nos données ne sont généralement pas linéairement séparables.

o Dans ce cas, quel que soit l’hyperplan séparateur que l’on choisisse, certains des points
seront mal classifiés ;
o D’autres seront correctement classifiés, mais à l’intérieur de la zone d’indécision.
o Ces concepts sont illustrés sur la figure 10.3.

56 | P a g e
• Notre but est maintenant de trouver un compromis entre les erreurs de classification et
la taille de la marge.
o Comme dans la SVM à marge rigide (équation 10.1), nous cherchons à
1
⃗⃗ ⟧22 , auquel nous rajoutons un terme
minimiser l’inverse du carré de la marge 2 ⟦𝑤
d’erreur 𝐶 × ∑𝑛𝑖=1 𝑙(𝑓(x⃗ 𝑖 ), 𝑦 𝑖 ).
o Ici, 𝐶 ∈ ℝ+ est un hyperparamètre de la SVM, et L représente une fonction de coût :

• L’hyperparamètre de coût 𝐶 permet de contrôler l’importance relative de la marge et des erreurs

du modèle sur le jeu d’entraînement.
o Il confère ainsi une certaine souplesse à la marge ; on parle alors de SVM à marge
souple.
o Nous souhaitons, autant que possible, que toute observation x⃗ d’étiquette 𝑦 soit située
à l’extérieur de la zone d’indécision, autrement dit vérifie 𝑦𝑓 (x⃗ ) ≥ 1.
o Nous allons donc utiliser l’erreur hinge (cf. définition 2.12) comme fonction de coût.
• On appelle SVM à marge souple la solution du problème d’optimisation suivant :

• Cette formulation est celle d’une régularisation de la minimisation d’un risque

empirique par un terme de norme 𝑙2 .
o Elle est similaire à la régression ridge, C étant inversement proportionnel à 𝜆,
mais la fonction d’erreur est différente.

57 | P a g e
 • En introduisant une variable d’ajustement (ou variable d’écart ; on parlera de slack
variable en anglais) 𝜉𝑖 = [1 − 𝑦 𝑗 𝑓(x⃗ 𝑖 )]+ pour chaque observation du jeu
d’entraînement, le problème d’optimisation 10.11 est équivalent à :

o Le problème 10.12 est équivalent à :

o La seule différence avec la formulation duale de la SVM à marge rigide

(équation 10.3) est la contrainte 𝛼𝑖 ≤ 𝐶, 𝑖 = 1, . . . , 𝑛.

8.3 Le cas non-linéaire : SVM à noyau.

• Il est fréquent qu’une fonction linéaire ne soit pas appropriée pour séparer nos
données (voir par exemple la figure 10.4a).
o Que faire dans ce cas ?

• Dans le cas des données représentées sur la figure 10.4a, un cercle d’équation x12 + x22 =
𝑅 2 semble bien mieux indiqué qu’une droite pour séparer les deux classes.
o Or si la fonction 𝑓 ∶ ℝ2 → ℝ, x⃗ → x12 + x22 − 𝑅 2 n’est pas linéaire en x⃗ = (x1, x2), elle
est linéaire en (x12 , x22 ).

58 | P a g e
 o Définissons donc l’application 𝜑 ∶ 𝑅 2 → 𝑅 2 , (x1 , x2 ) → (x12 , x22 )
o La fonction de décision 𝑓 est linéaire en 𝜑(x⃗ ) ∶ 𝑓(x⃗ ) = 𝜑(x⃗ )1 + 𝜑(x⃗ )2 −
𝑅2.
• Nous pouvons donc l’apprendre en utilisant une SVM sur les images des données par
l’application φ.
o Plus généralement, nous allons maintenant supposer que les observations sont
définies sur un espace quelconque 𝒳, qui peut être ℝ𝑝 mais aussi par exemple
l’ensemble des chaînes de caractères sur un alphabet donné, l’espace de tous les
graphes, ou un espace de fonctions.
o On appelle espace de redescription l’espace de Hilbert H dans lequel il est
souhaitable de redécrire les données, au moyen d’une application 𝜑 ∶ 𝒳 → ℋ,
pour 𝑦 entraîner une SVM sur les images des observations du jeu
d’entraînement.
o La redescription des données dans un espace de Hilbert nous permet d’utiliser
un algorithme linéaire, comme la SVM à marge souple, pour résoudre un
problème non linéaire.
• Pour entraîner une SVM sur les images de nos observations dans l’espace de
redescription ℋ, il nous faut donc résoudre, d’après l’équation 10.13, le problème
suivant :

o La fonction de décision sera ensuite donnée par (équation 10.9) :

• Dans les équations 10.20 et 10.21, les images des observations dans ℋ apparaissent
uniquement dans des produits scalaires sur ℋ.
o Nous pouvons donc, plutôt que la fonction φ : 𝒳 → ℋ, utiliser la fonction
suivante, appelée noyau :

59 | P a g e
• On appelle SVM à noyau la solution du problème d’optimisation suivant :

• La fonction de décision sera ensuite donnée par (équation 10.9) :

• Que ce soit pour entraîner la SVM ou pour l’appliquer, nous n’avons pas besoin de
connaître 𝜑 explicitement, mais il nous suffit de connaître le noyau 𝑘.
o Cela signifie que nous n’avons pas besoin de faire de calcul dans ℋ, qui est
généralement de très grande dimension : c’est ce que l’on appelle l’astuce du
noyau.
o L’astuce du noyau s’applique de manière générale à d’autres algorithmes
d’apprentissage linéaires, comme la régression ridge (cf. section 6.2), l’ACP
(cf. section 11.3.1) ou encore la méthode des K-moyennes (cf. section 12.4).
• Nous appelons noyau toute fonction k de deux variables s’écrivant sous la forme d’un
produit scalaire des images dans un espace de Hilbert de ses variables.
o Ainsi, un noyau est une fonction continue, symétrique, et semi-définie positive
:

• Étant donnés 𝑛 observations x⃗1 , x⃗ 2, . . . , x⃗ 𝑛 ∈ 𝒳 𝑛 , et un noyau 𝑘 sur 𝒳, on appelle

matrice de Gram de ces observations la matrice 𝐾 ∈ ℝ𝑛×𝑛 telle que 𝐾𝑖𝑙 = 𝑘(x⃗ 𝑖 , x⃗ 𝑙 ).
o Cette matrice est semi-définie positive.
o Pour toute fonction symétrique semi-définie positive 𝜅 ∶ 𝒳 × 𝒳 → ℝ, il existe
un espace de Hilbert ℱ et une application 𝜓 ∶ 𝒳 → ℱ telle que pour tout x⃗, x⃗ 𝑙 ∈
𝒳 × 𝒳, 𝜅(x⃗, x⃗ 𝑙 ) = (𝜓(x⃗), 𝜓(x⃗ 𝑙 ))ℱ .

60 | P a g e
 CHAPITRE 9.
REDUCTION DE DIMENSION
• Dans certaines applications, le nombre de variables p utilisé pour représenter les
données est très élevé.
o C’est le cas par exemple du traitement d’images haute-résolution, dans lequel
chaque pixel peut être représenté par plusieurs variables, ou de l’analyse de
données génomiques, où des centaines de milliers de positions du génome
peuvent être caractérisées.
o Bien qu’une représentation des données contenant plus de variables soit
intuitivement plus riches, il est plus difficile d’apprendre un modèle performant
dans ces circonstances. Dans ce chapitre, nous en détaillerons les raisons avant
d’explorer une série de méthodes, supervisées ou non, pour réduire ce nombre
de variables afin d’obtenir des représentations plus compactes et des modèles
plus robustes.

9.1 Motivation

• Le but de la réduction de dimension est de transformer une représentation 𝑋 ∈ ℝ𝑛×𝑝

des données en une représentation 𝑋 ∗ ∈ ℝ𝑛×𝑚 où 𝑚 ≪ 𝑝.
o Les raisons de cette démarche sont détaillées ci-dessous.

1. Visualiser les données

• Bien que le but de l’apprentissage automatique soit justement d’automatiser le

traitement des données, il est essentiel pour appliquer les méthodes présentées dans ce
cours à bon escient de bien comprendre le problème particulier que l’on cherche à
résoudre et les données dont on dispose.
o Cela permet de mieux définir les variables à utiliser, d’éliminer éventuellement
les données aberrantes, et de guider le choix des algorithmes.
o Dans ce but, il est très utile de pouvoir visualiser les données ; mais ce n’est pas
tâche aisée avec p variables.
o Ainsi, limiter les variables à un faible nombre de dimensions permet de
visualiser les données plus facilement, quitte à perdre un peu d’information lors
de la transformation.

2. Réduire les coûts algorithmiques

• Réduire la dimension des données permet de réduire, d’une part, l’espace qu’elles
prennent en mémoire et, d’autre part, les temps de calcul.
o De plus, si certaines variables sont inutiles, ou redondantes, il n’est pas
nécessaire de les obtenir pour de nouvelles observations : cela permet de réduire
le coût d’acquisition des données.

61 | P a g e
 3. Améliorer la qualité des modèles
• Notre motivation principale pour réduire la dimension des données est de pouvoir
construire de meilleurs modèles d’apprentissage supervisé.
o Par exemple, un modèle paramétrique construit sur un plus faible nombre de
variables est moins susceptible de sur-apprendre, comme nous l’avons vu avec
le lasso.
o De plus, si certaines des variables mesurées ne sont pas pertinentes pour le
problème d’apprentissage qui nous intéresse, elles peuvent induire l’algorithme
d’apprentissage en erreur.
o Enfin, nous faisons face en haute dimension à un phénomène connu sous le nom
de fléau de la dimension, ou curse of dimensionality en anglais.
o Ce terme qualifie le fait que les intuitions développées en faible dimension ne
s’appliquent pas nécessairement en haute dimension.
▪ Cela implique que les algorithmes développés en utilisant une notion de
similarité, comme les plus proches voisins, les arbres de décision ou les
SVM, ne fonctionnent pas nécessairement en grande dimension.
▪ Ainsi, réduire la dimension peut être nécessaire à la construction de bons
modèles.
• Deux possibilités s’offrent à nous pour réduire la dimension de nos données :
o La sélection de variables, qui consiste à éliminer un nombre p − m de variables
de nos données ;
o L’extraction de variables, qui consiste à créer m nouvelles variables à partir
des p variables dont nous disposons initialement.

9.2 Sélection des variables

• Les approches de sélection de variables consistent à choisir m variables à conserver

parmi les p existantes, et à ignorer les p − m autres.
o On peut les séparer en trois catégories : les méthodes de filtrage, les méthodes
de conteneur, et les méthodes embarquées.
o Les méthodes que nous allons voir ici sont des méthodes supervisées : nous
supposons disposer d’un jeu de données étiqueté 𝒟 = {(𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,…,𝑛 où 𝑥 𝑖 ∈
ℝ𝑝 .

Méthodes de filtrage
• La sélection de variable par filtrage consiste à appliquer un critère de sélection
indépendamment à chacune des 𝑝 variables ;
o Il s’agit de quantifier la pertinence de la p-ième variable du jeu de donnée par
rapport à 𝑦.
o Quelques exemples d’un tel critère sont la corrélation avec l’étiquette, un test
statistique comme celui du 𝜒 2 dans le cas d’un problème de classification, ou
l’information mutuelle.

62 | P a g e
• La corrélation entre la variable j et l’étiquette y se calcule comme celle entre une
étiquette prédite et une étiquette réelle (cf. équation 3.2) :

Méthodes de conteneur
• Les méthodes de conteneur, ou wrapper methods en anglais, consistent à essayer de
déterminer le meilleur sous-ensemble de variables pour un algorithme d’apprentissage
donné.
o On parle alors souvent non pas de sélection de variables mais de sélection de
sous-ensemble de variables, ou subset selection en anglais.
o Quelques exemples de ces approches sont la recherche ascendante, la
recherche descendante, et la recherche flottante.
• La recherche ascendante consiste à partir d’un ensemble de variables vide, et à lui
ajouter variable par variable celle qui améliore au mieux sa performance, jusqu’à ne
plus pouvoir l’améliorer.
o On appelle recherche ascendante, ou forward search en anglais, la procédure
gloutonne de sélection de variables suivante :
▪ 1. Initialiser ℱ = ∅.
▪ 2. Trouver la meilleure variable à ajouter à ℱ :

▪ 3. Si E𝒟 = (ℱ⋃{𝑗}) > E𝒟 (ℱ) : s’arrêter

sinon : ℱ ← ℱ⋃{𝑗}; recommencer 2-3

• À l’inverse, la recherche descendante consiste à partir de l’ensemble de toutes les variables, et

à lui retirer variable par variable celle qui améliore au mieux sa performance, jusqu’à ne plus
pouvoir l’améliorer.
o On appelle recherche descendante, ou backward search en anglais, la
procédure gloutonne de sélection de variables suivante :
▪ 1. Initialiser ℱ = {1,2, … , 𝑝}.
▪ 2. Trouver la meilleure variable à retirer à ℱ :

▪ 3. Si E𝒟 = (ℱ ∖ {𝑗}) > E𝒟 (ℱ) : s’arrêter

sinon : ℱ ← ℱ ∖ {𝑗}; recommencer 2-3

63 | P a g e
 o L’avantage de l’approche descendante sur l’approche ascendante est qu’elle
fournit nécessairement un sous-ensemble de variables meilleur que l’intégralité
des variables.
• La recherche flottante permet d’explorer un peu différemment l’espace des possibles
en combinant les deux approches.
o Étant donnés deux paramètres entiers strictement positifs q et r, on appelle
recherche flottante, ou floating search en anglais, la procédure gloutonne de
sélection de variables suivante :
▪ 1. Initialiser ℱ = ∅.
▪ 2. Trouver les q meilleures variables à ajouter à ℱ :

▪ 3. Si E𝒟 (ℱ ∪ 𝒮) < E𝒟 (ℱ). ℱ ← ℱ ∪ 𝒮.
▪ 4. Trouver les r meilleures variables à retirer de ℱ.

sinon : ℱ ← ℱ ∖ {𝑗}; recommencer 2-5.

Méthodes embarquées

• Enfin, les méthodes embarquées, ou embedded approaches en anglais, apprennent en

même temps que le modèle les variables à y inclure.
o Il s’agit généralement de modèles paramétriques parcimonieux tels que les
coefficients affectés à certaines variables soient nuls.
o Ces variables sont alors éliminées du modèle.
o L’exemple le plus prégnant de ces techniques est le lasso.
• Dans le même ordre d’idée, la mesure d’importance des variables dans les forêts
aléatoires peut être utilisée pour décider quelles variables éliminer.

9.3 Extraction des variables

• La méthode la plus classique pour réduire la dimension d’un jeu de données par
extraction de variables est l’analyse en composantes principales, ou ACP.
o On parle aussi souvent de PCA, de son nom anglais Principal Component
Analysis.
▪ L’idée centrale d’une ACP est de représenter les données de sorte à
maximiser leur variance selon les nouvelles dimensions, afin de pouvoir
continuer à distinguer les exemples les uns des autres dans leur nouvelle
représentation (cf. figure 11.3).

64 | P a g e
• Une analyse en composantes principales, ou ACP, de la matrice 𝑋 ∈ ℝ𝑛×𝑝 est une
transformation linéaire orthogonale qui permet d’exprimer X dans une nouvelle base
orthonormée, de sorte que la plus grande variance de X par projection s’aligne sur le
premier axe de cette nouvelle base, la seconde plus grande variance sur le deuxième
axe, et ainsi de suite.
o Les axes de cette nouvelle base sont appelés les composantes principales,
abrégées en PC pour Principal Components.
• La standardisation des variables est un prérequis pour l’application de l’ACP.
o Les variables sont standardisées de sorte à toutes avoir une moyenne de 0 et une
variance de 1.
o Elle évite que les variables qui prennent de grandes valeurs aient plus
d’importance que celles qui prennent des faibles valeurs.
o Cette standardisation s’effectue en centrant la moyenne et en réduisant la
variance de chaque variable :

1
où x𝑗 = 𝑛 ∑𝑛𝑙=1 x𝑗𝑙
o On dira alors que X est centrée : chacune de ses colonnes a pour moyenne 0.
• Réduire la dimension des données par une ACP implique de choisir un nombre de
composantes principales à conserver.
o Pour ce faire, on utilise la proportion de variance expliquée par ces composantes
: la variance de X s’exprime comme la trace de ∑, qui est elle-même la somme
de ses valeurs propres.
o Ainsi, si l’on décide de conserver les m premières composantes principales de
X, la proportion de variance qu’elles expliquent est :

𝛼1 + 𝛼2 … 𝛼𝑚
Tr(∑)

où 𝛼1 ≥ 𝛼2 ≥ ⋯ ≥ 𝛼𝑝 sont les valeurs propres de ∑ par ordre décroissant.

65 | P a g e
• Il est classique de s’intéresser à l’évolution, avec le nombre de composantes,
o soit de la proportion de variance expliquée par chacune d’entre elles,
o soit à cette proportion cumulée, que l’on peut représenter visuellement sur un
scree plot (figure 11.4a).
o Ce graphe peut nous servir à déterminer :
▪ soit le nombre de composantes principales qui explique un pourcentage
de la variance que l’on s’est initialement fixé (par exemple, sur la figure
11.4b, 95 %) ;
▪ soit le nombre de composantes principales correspondant au « coude »
du graphe, à partir duquel ajouter une nouvelle composante principale
ne semble plus informatif.

66 | P a g e
 CHAPITRE 10.
CLUSTERING
• Comment étudier des données non étiquetées ?
o La dimension de réduction nous permet de les visualiser.
o Les méthodes dites de partitionnement de données, ou clustering, nous
permettent d’aller beaucoup plus loin.
▪ Il s’agit de séparer les données en sous-groupes homogènes, appelés
clusters, qui partagent des caractéristiques communes.
o Dans ce chapitre, nous détaillerons l’intérêt de ces techniques et verrons trois
types d’approches de clustering : le clustering hiérarchique, le clustering par
centroïdes, et le clustering par densité.

10.1 Pourquoi partitionner ses données ?

• Les algorithmes de partitionnement de données permettent d’effectuer une analyse

exploratoire sur des données non étiquetées.
o Ils permettent par exemple d’identifier
▪ des utilisateurs qui ont des comportements similaires (ce que l’on
appelle la segmentation de marché),
▪ des communautés sur un réseau social,
▪ des motifs récurrents dans des transactions financières,
▪ des pixels d’un même objet dans une image (segmentation d’image) ou
▪ des patients dont la maladie s’explique par un même profil génétique.
o Ils permettent aussi de visualiser les données, en se contentant de regarder un
exemple représentatif par cluster.
o Ils permettent de transférer à toutes les observations du même cluster les
propriétés que l’on sait vraies de l’un des éléments de ce cluster. Cela est
particulièrement utile dans le cas où l’étiquetage des données est difficile ou
coûteux.
• Prenons l’exemple de l’annotation d’un corpus de documents texte.
o Annoter manuellement chacun de ces documents par le ou les sujets qu’il couvre
est un travail fastidieux.
o Les personnes qui l’effectuent sont d’ailleurs susceptibles de commettre
involontairement des erreurs d’inattention.
o Il est ainsi moins coûteux, voire plus efficace, d’utiliser un algorithme de
clustering pour regrouper automatiquement ces documents par sujet.
o Il suffira alors d’avoir recours à un intervenant humain pour assigner un sujet à
chaque cluster en lisant uniquement un ou deux des documents qu’il contient.

67 | P a g e
10.2 Evaluer la qualité d’un algorithme de clustering

• Le clustering n’étant pas supervisé, il nous faut mettre au point des critères d’évaluation
qui ne dépendent pas d’une vérité terrain (c’est-à-dire d’étiquettes connues).
o Nous supposons avoir partitionné un jeu de données non étiqueté 𝒟 =
{(𝑥 𝑖 , 𝑦 𝑖 )}𝑖=1,…,𝑛 de n points d’un espace 𝜒 en K clusters 𝒞1 , 𝒞2 , . . . , 𝒞𝐾 .
o d est une distance sur 𝜒 et 𝑘(x⃗) est l’indice du cluster auquel x⃗ a été assigné.

La forme de clusters
• Pour évaluer la qualité des clusters obtenus par un algorithme de partitionnement, il est
possible de s’appuyer sur le souhait formulé de regrouper entre elles les observations
similaires.
o Ainsi, les observations appartenant à un même cluster doivent être proches,
tandis que les observations dissimilaires doivent appartenir à des clusters
différents.
• Pour quantifier ces notions, nous allons avoir besoin de celle de centroïde, qui est le
barycentre d’un cluster.
o On appelle centroïde du cluster 𝒞 le point défini par :

1
⃗𝒞 =
𝜇 ∑x
|𝒞|
x∈𝒞

o Le médoïde est le point du cluster le plus proche du centroïde (il peut ne pas
être unique, auquel cas il sera choisi arbitrairement).
▪ Il sert de représentant du cluster :

• Que des observations proches appartiennent au même cluster peut se traduire par la
notion d’homogénéité, illustrée sur la figure 12.1.
o On appelle homogénéité du cluster 𝒞𝑘 , ou tightness en anglais, la moyenne des
distances des observations de ce cluster à son centroïde :

▪ ici 𝑢
⃗ 𝑘 est le centroide de 𝒞𝑘

o L’homogénéité globale d’un clustering de 𝒟 se calcule comme la moyenne des

homogénéités des clusters :

68 | P a g e
 𝐾
1
𝑇 = ∑ 𝑇𝑘
𝐾
𝑘=1

• Pour quantifier à quel point les clusters sont distants les uns des autres, nous pouvons
utiliser le critère de séparabilité, illustré sur la figure 12.2.

• On appelle séparabilité des clusters 𝒞𝑘 et 𝒞𝑙 la distance entre leurs centroïdes :

o La séparabilité globale d’un clustering de 𝒟 se calcule comme la moyenne des

séparabilités des clusters deux à deux :

69 | P a g e
• Plutôt que de considérer les deux critères de séparabilité (que l’on souhaite élevée) et
d’homogénéité (que l’on souhaite faible) séparément, il est possible de les comparer
l’un à l’autre grâce à l’indice de Davies-Bouldin.
o On appelle indice de Davies-Bouldin du cluster 𝒞𝑘 la valeur :

o L’indice de Davies-Bouldin global d’un clustering de 𝒟 se calcule comme la

moyenne des indices de Davies-Bouldin des clusters :

• Une autre façon de prendre en compte séparabilité et homogénéité est de calculer le

coefficient de silhouette, qui permet de quantifier pour chacune des observations si elle
appartient ou non au bon cluster.
o On appelle coefficient de silhouette de l’observation x⃗ ∈ 𝒟 la valeur :

où 𝑎⃗⃗⃗
(x) est la distance moyenne de x⃗ à tous les autres éléments du cluster auquel il appartient
⃗⃗⃗ ) est la plus petite valeur que pourrait prendre 𝑎⃗⃗⃗
et 𝑏(x (x), si a appartenait à un autre cluster :

o Le coefficient de silhouette global du clustering est son coefficient de silhouette

moyen :

o Le coefficient de silhouette de x⃗ est d’autant plus proche de 1 que son

assignation au cluster 𝒞𝑘(x⃗) est satisfaisante.

70 | P a g e
10.3 Le clustering hiérarchique
• Le clustering hiérarchique forme des clusters séparés par récurrence : il s’agit de
partitionner les données pour toutes les échelles possibles de taille de partition, dans
une hiérarchie à plusieurs niveaux.
o Le résultat d’un clustering hiérarchique peut se visualiser sous la forme d’un
dendrogramme.
▪ Il s’agit d’un arbre dont les n feuilles correspondent chacune à une
observation.
▪ Chaque nœud de l’arbre correspond à un cluster :
• La racine est un cluster contenant toutes les observations ;
• Chaque feuille est un cluster contenant une observation ;
• Les clusters ayant le même parent sont agglomérés en un seul cluster
au niveau au-dessus ;
• Un cluster est subdivisé en ses enfants au niveau au-dessous.
o Ce sont donc les nœuds intermédiaires qui nous intéresseront le plus.
o Enfin, la longueur d’une branche de l’arbre est proportionnelle à la distance entre les
deux clusters qu’elle connecte.
• La figure 12.3 représente un exemple de dendrogramme.
o Dans le cas où n est trop grand pour représenter l’intégralité de l’arbre, il est
classique de le couper et de n’en représenter que la partie de la racine à un niveau
que l’on choisit.
o Cette facilité à représenter visuellement le résultat d’un algorithme de clustering
hiérarchique fait qu’il est très utilisé dans des domaines comme la bio-
informatique.

• Un clustering hiérarchique peut se construire de manière agglomérative ou divisive.

o Le clustering agglomératif, ou bottom-up clustering, commence par considérer
les feuilles du dendrogramme : initialement, chaque observation forme un
cluster de taille 1.
71 | P a g e
 ▪ À chaque itération de l’algorithme, on trouve les deux clusters les plus
proches, et on les agglomère en un seul cluster, et ce jusqu’à ne plus
avoir qu’un unique cluster contenant les n observations.
o Le clustering divisif, ou top-down clustering, est l’approche inverse.
▪ On l’initialise en considérant un seul cluster, la racine du
dendrogramme, contenant toutes les observations.
▪ À chaque itération, on sépare un cluster en deux, jusqu’à ce que chaque
cluster ne contienne plus qu’une seule observation.
• Déterminer les deux clusters les plus proches afin de les agglomérer requiert de définir
une distance entre clusters.
o C’est ce qu’on appelle dans le cadre du clustering une fonction de lien, ou
linkage en anglais.
o Plusieurs approches sont possibles, qui reposent toutes sur une distance d sur
𝒳.
• Tout d’abord, on peut choisir d’agglomérer deux clusters si deux de leurs éléments sont
proches. On utilise alors le lien simple.
o On appelle lien simple, ou single linkage, la distance entre deux clusters définie
par :

• On peut aussi choisir d’agglomérer deux clusters si tous leurs éléments sont proches.
o On utilise alors le lien complet, qui est la distance maximale entre un élément
du premier cluster et un élément du deuxième.
o On appelle lien complet, ou complete linkage, la distance entre deux clusters
définie par :

• Une approche intermédiaire consiste à considérer la distance moyenne entre un élément

du premier cluster et un élément du deuxième. C’est le lien moyen.
o On appelle lien moyen, ou average linkage, la distance entre deux clusters
définie par :

• Les fonctions de lien ci-dessus s’attachent à garantir la séparabilité des clusters.

o À l’inverse, il est possible de chercher à maximiser leur homogénéité : il s’agit
de minimiser

72 | P a g e
 o Dans le cas où d est la distance euclidienne, alors

o Le clustering deWard utilise une formulation similaire : il s’agit d’agglomérer

deux clusters de sorte à minimiser la variance intra-cluster du résultat.
• Le clustering hiérarchique a l’avantage de ne pas requérir de définir à l’avance le
nombre de clusters.
o Ce qui permet d’explorer toutes les possibilités le long du dendrogramme.
o Cependant, il faut généralement prendre cette décision à un moment.
o Il est possible pour cela d’utiliser un dendrogramme, pour y déceler un « niveau
» auquel les clusters sont clairement distants les uns des autres – on se rappellera
que la longueur d’une branche est proportionnelle à la distance entre les deux
clusters qu’elle sépare.
o Une solution alternative est d’évaluer les différentes partitions trouvées, c’est-
à-dire les différents nœuds du dendrogramme, à l’aide d’une mesure de
performance telle que le coefficient de silhouette.

10.4 Méthodes de K moyennes

• Plutôt que d’explorer toutes les partitions possibles à différentes échelles, il peut être
préférable de se fixer un nombre K de clusters.
o Ce qui permet de réduire les temps de calculs.
o Nous avons vu ci-dessus que le clustering de Ward cherche à minimiser la
variance intra-cluster afin de créer des clusters homogènes.
• La méthode dite des K-moyennes, ou du K-means, cherche à résoudre ce problème
pour un nombre de clusters K fixé.
o Il s’agit alors de trouver l’affectation des observations à K clusters qui minimise
la variance intra-cluster globale :

• Cependant, résoudre ce problème de manière exacte n’est pas possible.

o On utilise donc une heuristique, l’algorithme de Lloyd, décrit comme ci-
dessous.
▪ Étant donné n observations dans ℝ𝑝 et un nombre K de clusters,
l’algorithme de Lloyd procède de la manière suivante :
• 1. Choisir K observations 𝑢 ⃗ 1, 𝑢
⃗ 2, … , 𝑢 ⃗ 𝑘 parmi les n
observations, pour servir de centroïdes initiaux.
• 2. Affecter chaque observation x⃗𝑖 ∈ 𝒟 au centroïde dont elle est
le plus proche :

73 | P a g e
 • 3. Recalculer les centroïdes de chaque cluster :

• 4. Répéter les opérations 2-3 jusqu’à convergence, c’est-à-dire

jusqu’à ce que les affectations ne changent plus.

10.5 Clustering par densité

• Le clustering par densité est l’autre manière d’obtenir des clusters non-convexes.
o Il observe que les points les plus proches d’un point donné sont sur le même
cercle et non sur un autre cercle.
o Cette idée est illustrée sur la figure 12.5.

• On appelle DBSCAN, pour Density-Based Spatial Clustering of Applications with

Noise, ou partitionnement dans l’espace par densité pour des applications bruitées, la
procédure de partitionnement suivante :
o Initialisation : Un ensemble d’éléments visités 𝒱 = ∅, une liste de clusters 𝒦 =
∅, une liste d’observations aberrantes 𝒜 = ∅.
o Pour chaque élément x⃗ ∈ 𝒟 \𝒱 :
▪ 1. Construire 𝒩𝜀 (x).
▪ 2. Si |𝒩𝜀 (𝑥⃗ )| < 𝑛𝑚𝑖𝑛 : considérer (temporairement) x⃗ comme une
observation aberrante : 𝒜 ← 𝒜 ∪ {𝑥⃗ }.
sinon :
• créer un cluster 𝒞 = {𝑥⃗ } ;

74 | P a g e
 • augmenter ce cluster par la procédure grow_cluster (𝒞, 𝒩𝜀 (x).,
𝜀, 𝑛𝑚𝑖𝑛 ).
▪ 3. Ajouter 𝒞 à la liste des clusters : 𝒦 ← 𝒦 ∪ 𝒞.
▪ 4. Marquer tous les éléments de 𝒞 comme visités : 𝒱 ← 𝒱 ∪ 𝒞.
o La procédure grow_cluster (𝒞, 𝒩., 𝜀, 𝑛𝑚𝑖𝑛 ) est définie comme suit :
▪ Pour tout 𝑢⃗ ∈ 𝒩\𝒱 :
• créer 𝒩 = 𝑁𝜀 (𝑢 ⃗);
• si |𝒩| ≥ 𝑛𝑚𝑖𝑛 : actualiser 𝒩 de sorte à prendre les éléments de
𝒩 en considération : 𝒩 ← 𝒩 ∪ 𝒩 ;
▪ si 𝑢 ⃗ n’appartient à aucun autre cluster, l’ajouter à 𝒞. 𝒞 ← 𝒞 ∪ {𝑢 ⃗};
▪ si 𝑢 ⃗ était précédemment cataloguée comme aberrante, l’enlever de la
liste des observations aberrantes : 𝒜 ← 𝒜 ∪ {𝑢 ⃗ }.
• Un des avantages de DBSCAN est sa robustesse aux données aberrantes, qui sont
identifiées lors de la formation des clusters.
o Le fléau de la dimension rend DBSCAN difficile à appliquer en très grande
dimension.
o Cependant, DBSCAN ne requiert pas de prédéfinir le nombre de clusters, et est efficace
en temps de calcul.

75 | P a g e