Chapitre 4 — Algorithmes de classification

🎯 Objectifs d'apprentissage

Décrire le fonctionnement de la régression logistique, du KNN, du SVM, des arbres de décision et des forêts aléatoires.
Appliquer les formules de la sigmoïde, des distances euclidienne et de Manhattan, du vote majoritaire.
Connaître les hyperparamètres clés ( $k$ , $q$ , marge).
Comparer les avantages et limites de chaque algorithme.

4.1 — Vue d'ensemble

💡 Intuition

Régression logistique (RL) : calcule un score pondéré puis le compresse en probabilité.
k-Plus Proches Voisins (KNN) : dis-moi qui sont tes $k$ voisins les plus proches, et je te dirai qui tu es (vote de majorité).
SVM : trace une « autoroute » la plus large possible (marge maximale) entre deux clans.
Arbre de décision (DT) : joue au jeu du portrait chinois (« Est-il fumeur ? Si oui, a-t-il plus de 50 ans ? »).
Forêts aléatoires (RF) : fait voter une foule d'arbres décisionnels indépendants pour éviter les erreurs individuelles.

4.2 — Régression logistique

La régression logistique est un algorithme d'apprentissage supervisé utilisé pour prédire la probabilité d'une variable cible catégorielle. Elle est principalement utilisée pour la classification binaire. main_3.pdf, p. 14

Algorithme

Soit $E = {(x i, y i) i=1,\dots,n}$ un jeu de données avec $x i \in ℝ p$ et $y i \in {0, 1}$ .

Étape 1 — Combinaison linéaire : l'algorithme calcule une somme pondérée des caractéristiques :

z = w_{1} x_{1} + w_{2} x_{2} + \dots + w_{p} x_{p} + b = {\vec{w}}^{T} \vec{x} + b

où $w 1, \dots, w p$ sont les poids et $b$ le biais.

Étape 2 — Fonction sigmoïde : pour convertir le score continu $z$ en probabilité, on le passe dans la fonction sigmoïde :

σ (z) = \frac{1}{1 + e^{- z}} \in] 0, 1 [

Étape 3 — Seuillage : pour obtenir une classification finale, on applique un seuil (généralement 0,5) :

f (x) = {\begin{matrix} 1 & si σ (z) > 0, 5 \\ 0 & sinon \end{matrix}

✏️ Exemple guidé — Risque cardiaque

Un médecin évalue le risque cardiaque à l'aide de deux variables : $x 1$ = âge (50 ans), $x 2$ = cholestérol (2,5 g/L). Poids appris : $w 1 = 0,08$ , $w 2 = 1,2$ , $b = -6,0$ .

Combinaison linéaire :
$z = (0,08 \times 50) + (1,2 \times 2,5) - 6,0 = 4,0 + 3,0 - 6,0 = +1,0$
Exponentielle :
$e -z = e -1,0 \approx 0,36788$
Sigmoïde :
$σ(1,0) = 1 / (1 + 0,36788) \approx 0,73105$ (soit 73,11 %)
Décision : puisque $σ(z) \approx 0,7311 > 0,5$ , le modèle prédit la classe positive $f(x⃗) = 1$ (patient à risque).

Interprétation : le patient a 73,11 % de chances d'être à risque. Le score $z = +1,0 > 0$ le place du côté positif de la frontière de décision linéaire.

⚠️ Attention — pièges classiques

Erreur de signe : ne pas oublier le signe moins dans l'exponentielle. La formule est bien $1 / (1 + e -z)$ .
Valeur en $z = 0$ : $σ(0) = 1 / (1 + 1) = 0,5$ , ce qui correspond à l'incertitude maximale.

4.3 — k-Plus Proches Voisins (KNN)

📘 Définition à connaître

Étant donné un ensemble d'apprentissage $E = {(X i, y i) i=1,\dots,n}$ , une distance $d$ sur $𝒳$ et un hyperparamètre $k \in ℕ*$ , l'algorithme des $k$ plus proches voisins consiste à étiqueter une nouvelle observation $X$ en fonction des étiquettes des $k$ points de l'ensemble d'apprentissage dont elle est la plus proche.

main_3.pdf, p. 17

Règle de décision

En notant $N k (X)$ l'ensemble des $k$ plus proches voisins de $X$ dans $E$ :

Classification — vote de majorité : $f (X) = \underset{c = 1, \dots, C}{argmax} | {X^{i} \in N_{k} (X) : y^{i} = c} |$
Régression — moyenne : $f (X) = \frac{1}{k} \sum_{X^{i} \in N_{k} (X)} y^{i}$

Distances

L'ingrédient essentiel de l'algorithme est la distance permettant de déterminer quelles sont les observations les plus proches du point à étiqueter. Soient deux points $u⃗$ et $v⃗$ de coordonnées respectives $(u 1, \dots, u p)$ et $(v 1, \dots, v p)$ dans $ℝ p$ .

Distance euclidienne : $d (\vec{u}, \vec{v}) = \sqrt{\sum_{i = 1}^{p} {(u_{i} - v_{i})}^{2}}$
Distance de Manhattan : $d (\vec{u}, \vec{v}) = \sum_{i = 1}^{p} | u_{i} - v_{i} |$

main_3.pdf, p. 21

✏️ Exemple guidé — Calcul de distances

Soit deux points $u⃗ = (1, 2)$ et $v⃗ = (4, 6)$ .

$Δ 1 = |4 - 1| = 3$ , $Δ 2 = |6 - 2| = 4$
Euclidienne : $d = \sqrt(3² + 4²) = \sqrt(9 + 16) = \sqrt25 = 5$
Manhattan : $d = 3 + 4 = 7$

Choix de $k$ : dilemme biais-variance

Valeur de $k$	Effet sur la frontière	Risque
$k = 1$	Frontière très découpée, épouse chaque point	Sur-apprentissage
$k$ intermédiaire	Frontière lissée, structure locale préservée	Bon compromis
$k$ très grand	Frontière excessivement lissée	Sous-apprentissage

⚠️ Attention — égalité dans le vote

Si deux classes ou plus sont aussi fréquentes dans le $k$ -voisinage, on peut :

Augmenter $k$ de 1.
Tirer une classe au hasard parmi les plus fréquentes.
Attribuer la classe majoritaire dans les données.
Pondérer les exemples par leur distance à la donnée à classer.

Avantages et limites

Avantages	Limites
Flexible : s'adapte à tous types de distribution Simple : le modèle est l'ensemble des vecteurs et leurs classes	Coût en mémoire : le modèle peut être de très grande taille Coût en calcul : dépend linéairement de $n$ et $p$ Malédiction de la dimensionnalité Pas de réelle phase d'apprentissage Nécessite une notion de distance pertinente

main_3.pdf, p. 22

4.4 — Machines à Vecteurs Supports (SVM)

Les SVM sont des algorithmes basés sur un algorithme linéaire (Vapnik et Lerner, 1963) permettant d'apprendre bien plus que des modèles linéaires grâce à l'astuce du noyau. Ce sont des approches discriminatives qui construisent des surfaces de séparation optimales en maximisant la marge. main_3.pdf, p. 23

Séparabilité linéaire

Soit $E = {(x i, y i) i=1,\dots,n}$ avec $x i \in ℝ p$ et $y i \in {-1, +1}$ . On dit que $E$ est linéairement séparable s'il existe au moins un hyperplan dans $ℝ p$ tel que tous les points positifs (étiquetés +1) soient d'un côté et tous les points négatifs (étiquetés −1) de l'autre.

Marge et vecteurs de support

📘 Définitions à connaître

Marge $γ$ : distance de l'hyperplan séparateur à l'observation du jeu d'entraînement la plus proche.
Hyperplans $H +$ et $H -$ : hyperplans parallèles au séparateur, situés à une distance $γ$ de part et d'autre.
Vecteurs de support : observations situées à une distance exactement égale à $γ$ de l'hyperplan séparateur. Ce sont elles qui « soutiennent » $H +$ et $H -$ .
Zone d'indécision : zone située entre $H +$ et $H -$ ; elle ne contient aucune observation.

main_3.pdf, p. 25–26

🔗 Lien mathématique

Pour l'hyperplan séparateur $H : w⃗ T x⃗ + b = 0$ , la marge vaut $γ = 1 / ‖w⃗‖$ dans la formulation canonique. L'objectif de la SVM est de maximiser cette marge, ce qui équivaut à minimiser $‖w⃗‖²$ sous contraintes $y i (w⃗ T x i + b) \geq 1$ .

Note : la formulation duale et l'astuce du noyau ne sont pas détaillées mathématiquement dans les diapositives du cours.

Deux cas de SVM

Type	Conditions
SVM à marge rigide	Données linéairement séparables
SVM à marge souple	Données linéairement non séparables

⚠️ Remarque importante

Si l'on déplace légèrement une observation qui est vecteur de support, la zone d'indécision et l'hyperplan séparateur changent. À l'inverse, si l'on déplace légèrement une observation qui n'est pas vecteur de support, $H$ n'est pas affecté.

4.5 — Arbres de décision

📘 Définition à connaître

Un arbre de décision est un modèle de prédiction représenté sous la forme d'un arbre, dont :

Les nœuds internes sont étiquetés par un test (fonction de décision) applicable à tout individu, généralement sur un attribut de description.
Les arcs (ou enfants) contiennent les résultats du test, chaque arc correspondant à une réponse possible.
Les feuilles sont étiquetées par une classe.

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. Ce classifieur a une traduction immédiate en règles de décision mutuellement exclusives et ordonnées (si… alors… sinon…).

main_3.pdf, p. 27

Deux types d'arbres

Arbres de classification : la prédiction est une étiquette de classe.
Arbres de régression : la prédiction est une valeur numérique réelle.

Construction : structure générique de l'algorithme

Initialiser l'arbre courant à vide ; racine = nœud courant.
Répéter :
- Décider si le nœud courant est terminal.
- Si terminal, lui affecter une classe (classe majoritaire du nœud).
- Sinon, sélectionner un test et créer autant de nouveaux nœuds qu'il y a de réponses possibles.
- Passer au nœud suivant non exploré.
Arrêt : plus de nœud sans classe.

main_3.pdf, p. 40

Critères d'arrêt (nœud terminal)

(Presque) tous les exemples correspondant à ce nœud sont de la même classe.
Il n'y a plus d'attribut non utilisé dans la branche.
On a atteint la profondeur maximale autorisée.

Algorithmes célèbres

CART (Classification and Regression Tree) — Breiman, 1984.
C4.5 — Quinlan, 1994.

⚠️ Remarque — omission dans les diapositives

Les formules mathématiques d'impureté (indice de Gini pour CART, gain d'information pour C4.5) ne sont pas explicitées dans les diapositives du cours. Le critère reste qualitatif : « le pivot qui disperse le mieux les classes ».

✏️ Exemple — Évaluation du risque cardiaque

Attributs : âge (discrétisé en jeune < 20, actif 21–50, senior > 50), sexe, fumeur, corpulence (faible, moyenne, forte). Une partie de la base est étiquetée par un cardiologue en « à risque » (O) ou « non à risque » (N).

L'arbre choisit d'abord le pivot qui disperse le mieux les classes (ici Âge), puis continue récursivement sur chaque fils (Sexe, Corpulence, Fumeur) jusqu'à obtenir des feuilles pures.

main_3.pdf, p. 31–38

4.6 — Forêts aléatoires

Motivation : instabilité des arbres

C'est le principal inconvénient des arbres de décision : choisir un attribut plutôt qu'un autre se joue à peu de chose, et le choix d'un attribut-test près de la racine influence grandement le reste de la construction. Ces algorithmes ont donc une variance importante. L'idée des forêts aléatoires est d'apprendre plusieurs arbres et de faire voter l'ensemble. main_3.pdf, p. 42

📘 Algorithme des forêts aléatoires

Soit $E$ un ensemble d'apprentissage de $n$ observations étiquetées et $p$ attributs, et $K$ le nombre d'échantillons :

Tirer aléatoirement et avec remise (bootstrap) $K$ échantillons $D j$ de taille $n$ .
Entraîner un arbre de décision sur chaque $D j$ en respectant la règle suivante : à chaque sélection d'un attribut de split, le choisir dans un sous-ensemble de $q$ attributs tiré aléatoirement.
Exécuter les $K$ arbres sur les nouvelles données.
Agréger le résultat : par vote majoritaire (classification) ou moyenne (régression).

main_3.pdf, p. 44

Choix de $q$

Tâche	Valeur par défaut de $q$
Classification	$q = \sqrtp$
Régression	$q = p/3$

Ce qui permet aussi de réduire considérablement les temps de calcul puisqu'on ne considère que peu de variables à chaque nœud.

4.7 — Comparaison des algorithmes

Algorithme	Idée clé	Hyperparamètres	Forces	Faiblesses
Régression logistique	Score linéaire → probabilité par sigmoïde	Seuil (0,5 par défaut)	Interprétable, probabilités calibrées	Frontière linéaire uniquement
KNN	Vote des $k$ voisins les plus proches	$k$ , distance	Simple, non paramétrique	Coûteux, malédiction de la dimensionnalité
SVM	Marge maximale	Noyau, paramètre de régularisation	Robuste, efficace en grande dimension	Peu interprétable, sensible aux hyperparamètres
Arbre de décision	Partitionnement récursif	Profondeur, critère de split	Interprétable, gère données hétérogènes	Instable (variance élevée)
Forêts aléatoires	Bagging + sous-espace d'attributs	$K$ , $q$	Réduit la variance, robuste	Moins interprétable, plus coûteux

📌 À retenir

RL : $z = w⃗ T x⃗ + b$ , $σ(z) = 1/(1+e -z)$ , seuil 0,5.
KNN : distances euclidienne / Manhattan, vote majoritaire ou moyenne, $k$ à choisir.
SVM : marge maximale, vecteurs de support, hyperplans $H +$ et $H -$ .
Arbre : partitionnement récursif par le pivot qui disperse le mieux les classes.
Forêt : $K$ échantillons bootstrap, $q = \sqrtp$ ou $p/3$ , vote/moyenne.

🎯 À l'examen

Écrivez la fonction sigmoïde et donnez la valeur de $σ(0)$ .
Calculez les distances euclidienne et Manhattan entre $u⃗ = (1, 2)$ et $v⃗ = (4, 6)$ .
Expliquez le rôle des vecteurs de support dans une SVM.
Pour une base avec $p = 100$ caractéristiques, combien de variables sont sélectionnées à chaque nœud dans une forêt aléatoire pour la classification ?
Quels sont les inconvénients majeurs de KNN en termes de mémoire et de temps de calcul ?