Lernzettel: Introduction à k-NN et Distance en Apprentissage Machine

📋 Plan du Cours

1. Problème et notion de modèle ML
2. k-NN : apprentissage supervisé et régression
3. Raisonnement par cas et absence d’étape d’apprentissage
4. Principe de prédiction par k voisins
5. Algorithme k-NN et vote majoritaire
6. Distance : axiomes et rôle dans k-NN
7. Distances euclidienne, Manhattan et Minkowski
8. Choix de k et compromis biais variance
9. Limitations et coût de k-NN

📖 1. Problème et notion de modèle ML

🔑 Notions clés & Définitions

• Features : Les features sont les propriétés des données utilisées pour produire une prédiction.
• Label : Le label est la valeur cible associée à un point de données pour l’apprentissage supervisé.
• Classification : La classification est une tâche qui consiste à prédire une classe (un label discret) pour une nouvelle donnée.
• Régression : La régression est une tâche qui consiste à prédire une valeur numérique à la place d’une classe.
• Modèle ML : Un modèle ML combine des features, une mesure de similarité et une règle de décision pour prédire le label d’un nouvel exemple.

📝 Points essentiels

• Un modèle sert à répondre à une question de prédiction à partir de données.
• Les features décrivent l’entrée utilisée pour comparer des observations.
• Le label correspond à la sortie attendue pour un point de données.
• Pour une nouvelle donnée, on utilise une fonction de similarité pour décider de la prédiction.
• La similarité peut être mesurée via une fonction de distance adaptée au problème.
• Le cours illustre le besoin de prédire une valeur liée à une observation précédente (exemple du fleuriste).

💡 Astuce mémo

Features = Entrées ; Label = Sortie ; Distance + règle = Décision.

📖 2. k-NN : apprentissage supervisé et régression

🔑 Notions clés & Définitions

• k-Nearest Neighbor : k-NN est un algorithme d’apprentissage supervisé qui prédit à partir des k observations les plus proches.
• Apprentissage supervisé : L’apprentissage supervisé utilise des données labellisées pour apprendre à prédire le label d’une nouvelle donnée.
• Données labellisées : Des données labellisées sont des exemples où la sortie attendue (label) est connue pour chaque observation.
• Régression k-NN : La régression k-NN prédit une valeur numérique en agrégeant les sorties des k voisins proches.
• Classification k-NN : La classification k-NN prédit une classe en agrégeant les labels des k voisins proches.

📝 Points essentiels

• k-NN est présenté comme un algorithme d’apprentissage supervisé.
• k-NN nécessite un ensemble de données labellisées pour pouvoir déterminer le label.
• À partir d’un ensemble E, on classe une nouvelle donnée qui n’appartient pas à E.
• k-NN peut aussi être utilisé en régression pour prédire une valeur au lieu d’une classe.
• La prédiction dépend des k observations retenues comme proches.
• Le cours associe explicitement k-NN à la fois à la classification et à la régression.

💡 Astuce mémo

Supervisé = labels connus ; k-NN = regarde les voisins.

📖 3. Raisonnement par cas et absence d’étape d’apprentissage

🔑 Notions clés & Définitions

• Raisonnement par cas : Le raisonnement par cas consiste à décider en recherchant des cas similaires déjà résolus.
• Échantillon d’apprentissage : L’échantillon d’apprentissage est l’ensemble de données utilisé pour construire le modèle à partir d’exemples résolus.
• Pas d’étape d’apprentissage : L’absence d’étape d’apprentissage signifie que la prédiction se fait directement à partir de l’échantillon et de la distance.
• Modèle : Dans k-NN, le modèle correspond à l’échantillon d’apprentissage plus les fonctions nécessaires à la décision.

📝 Points essentiels

• Le raisonnement par cas cherche des observations déjà résolues pour guider la décision.
• k-NN prend une décision en s’appuyant sur des cas similaires à la nouvelle donnée.
• Le cours insiste sur l’absence d’étape d’apprentissage dédiée à la construction d’un modèle paramétrique.
• La construction du modèle se fait à partir d’un échantillon d’apprentissage.
• Le modèle k-NN est décrit comme la combinaison de l’échantillon, d’une fonction de distance et d’une fonction de choix de classe.
• La fonction de choix de classe dépend des classes des voisins les plus proches.

💡 Astuce mémo

Cas similaires → décision ; pas de “phase d’entraînement” lourde.

📖 4. Principe de prédiction par k voisins

🔑 Notions clés & Définitions

• Base de données : La base de données est l’ensemble d’observations utilisées pour trouver les voisins d’une nouvelle donnée.
• Voisin : Un voisin est une observation de la base jugée proche de la nouvelle donnée selon une distance.
• k voisins : Les k voisins sont les k observations les plus proches retenues pour effectuer la prédiction.
• Mode : Le mode est la valeur la plus fréquente parmi les labels des k voisins retenus.

📝 Points essentiels

• On veut prédire la classe d’une nouvelle donnée à partir de sa proximité avec la base.
• Si on ne prend qu’un seul voisin, la prédiction suit le label de ce voisin.
• Quand on augmente le nombre de voisins, la prédiction devient une agrégation de plusieurs labels.
• Le cours illustre le principe avec 1, 2, 3 puis 4 voisins pour montrer l’effet du choix de k.
• La prédiction dépend directement des labels associés aux voisins retenus.
• L’idée centrale est que la proximité guide le choix du label final.

💡 Astuce mémo

1 voisin = “copie” ; k voisins = “vote/agrégation”.

📖 5. Algorithme k-NN et vote majoritaire

🔑 Notions clés & Définitions

• Entrée de l’algorithme : L’entrée de l’algorithme k-NN comprend l’ensemble de données D, une distance d, un entier k et une nouvelle observation X.
• Fonction de distance d : La fonction de distance d mesure la similarité entre deux observations et sert à trier les voisins.
• Retenir les k observations proches : Retenir les k observations proches consiste à sélectionner les k exemples de D les plus proches de X selon d.
• Vote majoritaire : Le vote majoritaire est la règle de décision qui choisit la classe la plus fréquente parmi les k voisins.
• Mode des labels : Le mode des labels est la classe la plus fréquente parmi les labels des voisins retenus.

📝 Points essentiels

• L’algorithme prend en entrée un ensemble de données D, une distance d, un entier k et une nouvelle observation X.
• Il calcule toutes les distances entre X et les observations de D.
• Il retient les k observations les plus proches de X selon la fonction de distance.
• Il récupère les valeurs de sortie y associées aux k observations retenues.
• Pour la classification, il calcule le mode des y des k voisins.
• Il retourne la valeur calculée comme prédiction pour X.

💡 Astuce mémo

Distances → tri → k voisins → mode (vote) → prédiction.

📖 6. Distance : axiomes et rôle dans k-NN

🔑 Notions clés & Définitions

• Distance : Une distance est une application qui associe à tout couple d’observations un réel positif ou nul mesurant leur écart.
• Axiome d’identité : L’axiome d’identité impose que la distance soit nulle exactement quand les deux points sont égaux.
• Symétrie : La symétrie impose que la distance entre x et y soit la même que celle entre y et x.
• Inégalité triangulaire : L’inégalité triangulaire impose que la distance directe soit au plus égale à un chemin passant par un troisième point.
• Rôle de la distance : La distance sert à déterminer quels exemples sont les plus proches et donc quels voisins seront retenus.

📝 Points essentiels

• Le cours définit une distance d sur un ensemble E de Rn comme une application de E×E vers R+.
• La distance doit vérifier d(x,y)=0 si et seulement si x=y.
• La distance doit vérifier la symétrie d(x,y)=d(y,x).
• La distance doit vérifier l’inégalité triangulaire d(x,y) ≤ d(x,z)+d(z,y).
• k-NN a besoin d’une fonction de distance entre deux observations pour comparer la proximité.
• Le tri des distances détermine directement les k voisins retenus pour la prédiction.

💡 Astuce mémo

Distance = identité + symétrie + triangle ; k-NN = “proches” selon d.

📖 7. Distances euclidienne, Manhattan et Minkowski

🔑 Notions clés & Définitions

• Distance euclidienne : La distance euclidienne mesure l’écart en utilisant la racine carrée de la somme des carrés des différences de coordonnées.
• Distance de Manhattan : La distance de Manhattan mesure l’écart en utilisant la somme des valeurs absolues des différences de coordonnées.
• Distance de Minkowski : La distance de Minkowski généralise euclidienne et Manhattan via une puissance p sur les différences de coordonnées.
• Distance de Chebyshev : La distance de Chebyshev correspond au cas limite de Minkowski quand p tend vers l’infini.

📝 Points essentiels

• La distance euclidienne s’exprime avec une racine carrée de la somme des (x_i−y_i)^2.
• La distance de Manhattan s’exprime comme une somme des |x_i−y_i| sur les coordonnées.
• La distance de Minkowski d’ordre p utilise la somme des (x_i−y_i)^p.
• Le cours présente Minkowski comme une généralisation reliant euclidienne et Manhattan.
• Quand p→+∞, la distance de Minkowski devient la distance de Chebyshev.
• La distance de Chebyshev s’écrit comme le maximum des |x_i−y_i| sur les coordonnées.

💡 Astuce mémo

Euclidienne = carrés ; Manhattan = absolus ; Minkowski = puissance p ; p→∞ = max.

📖 8. Choix de k et compromis biais variance

🔑 Notions clés & Définitions

• Choix de k : Le choix de k fixe le nombre de voisins utilisés pour décider la prédiction dans k-NN.
• Sous-apprentissage : Le sous-apprentissage correspond à un modèle trop sensible au petit nombre de voisins (k trop petit) selon le cours.
• Underfitting : Underfitting est le terme utilisé pour décrire le sous-apprentissage lié à un k trop petit.
• Surapprentissage : Le surapprentissage correspond à une prédiction trop dépendante des données d’entraînement (k trop grand) selon le cours.
• Overfitting : Overfitting est le terme utilisé pour décrire le surapprentissage lié à un k trop grand.

📝 Points essentiels

• Le choix de k dépend du jeu de données utilisé pour k-NN.
• Un k petit augmente le risque de sous-apprentissage (underfitting).
• Un k grand rend la classification plus fiable dans le cours.
• Le cours relie k grand à un risque accru de surapprentissage (overfitting).
• Le cas extrême mentionné est k=N, où N est le nombre d’observations.
• Le compromis biais-variance est illustré par l’opposition underfitting (k petit) vs overfitting (k grand).

💡 Astuce mémo

k petit → underfitting ; k grand → overfitting ; trouver le bon milieu.

📖 9. Limitations et coût de k-NN

🔑 Notions clés & Définitions

• Coût de prédiction : Le coût de prédiction correspond au travail nécessaire pour calculer les distances et sélectionner les voisins à chaque requête.
• Taille du jeu d’entraînement : La taille du jeu d’entraînement est le nombre d’observations à conserver, ce qui impacte directement le coût de k-NN.
• Tuning : Le tuning est l’essai de plusieurs combinaisons de paramètres, notamment k et la distance, pour obtenir de meilleurs résultats.
• Choix de la distance : Le choix de la distance consiste à sélectionner une fonction de distance adaptée au type des données.

📝 Points essentiels

• k-NN est présenté comme simple à appréhender grâce à l’absence de modèle nécessaire pour prédire.
• Le contre-cout est qu’il faut conserver l’ensemble des observations pour prédire.
• Le coût dépend donc de la taille du jeu d’entraînement.
• Le choix de la méthode de distance n’est pas toujours évident.
• Le choix de k n’est pas toujours évident non plus.
• Le cours recommande d’essayer plusieurs combinaisons et de faire du tuning pour obtenir un résultat satisfaisant.

💡 Astuce mémo

Pas de modèle → mais stockage + calcul à chaque prédiction.

📊 Tableaux de synthèse

Choix de distance selon le type de données

⚠️ Pièges & confusions fréquents

1. Confondre label et features : le label est la sortie cible, tandis que les features décrivent l’entrée utilisée pour comparer.
2. Croire qu’il existe une vraie phase d’apprentissage paramétrique : dans k-NN, la prédiction s’appuie directement sur l’échantillon et la distance.
3. Choisir k=1 sans comprendre le risque de sous-apprentissage (underfitting) lié au petit nombre de voisins.
4. Choisir k trop grand (jusqu’à k=N) sans voir le risque de surapprentissage (overfitting).
5. Utiliser une distance non adaptée au type de données, alors que le cours recommande un choix selon la nature des variables.
6. Oublier que la règle de décision en classification correspond au mode (vote majoritaire) des labels des k voisins retenus.

✅ Checklist Examen

1. Définir features et label et expliquer le rôle de la similarité (distance) dans un modèle ML.
2. Expliquer pourquoi k-NN est un apprentissage supervisé et ce que signifie “données labellisées”.
3. Décrire le raisonnement par cas et préciser ce que le cours entend par absence d’étape d’apprentissage.
4. Donner le principe de prédiction par k voisins et relier la prédiction au choix de k.
5. Énoncer les étapes de l’algorithme k-NN : calcul des distances, sélection des k proches, mode des y, retour de la prédiction.
6. Rappeler les axiomes d’une distance : identité, symétrie, inégalité triangulaire.
7. Écrire/identifier les formules et caractéristiques : euclidienne (carrés + racine), Manhattan (valeurs absolues), Minkowski (puissance p).
8. Donner le lien Minkowski → Chebyshev quand p→+∞ et l’expression en termes de maximum.
9. Expliquer le compromis underfitting/overfitting en fonction de k, y compris le cas k=N.
10. Lister les limitations : coût lié au stockage et au calcul, et nécessité de tuning (k et distance).