\documentclass[a4paper,11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais,bloc,completemulti]{automultiplechoice}
\usepackage[french]{babel}
\usepackage{amsmath, amssymb}

\title{k plus proches voisins (k-NN)}
\date{Numérique et sciences informatiques}

\begin{document}

\noindent\textbf{k plus proches voisins (k-NN)} \hfill \textit{Numérique et sciences informatiques}\\[0.4em]
Nom~: \dotfill\ Prénom~: \dotfill

\bigskip

\element{premiereknn}{
  \begin{question}{q01}
    Que fait l'algorithme des \textbf{k plus proches voisins}
(k-NN, \textit{k-Nearest Neighbors}) ?
    \begin{choices}
    \correctchoice{Prédit la classe d'un nouvel élément en regardant les classes des k éléments les plus proches dans un jeu de données déjà étiqueté}
    \wrongchoice{Mesure la complexité d'un programme}
    \wrongchoice{Cherche un élément dans une liste triée}
    \wrongchoice{Trie une liste par ordre croissant}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q02}
    Pourquoi parle-t-on d'apprentissage
\textbf{supervisé} pour k-NN ?
    \begin{choices}
    \wrongchoice{Parce qu'il est lent à l'exécution}
    \wrongchoice{Parce qu'il ne fonctionne qu'avec un professeur dans la salle}
    \wrongchoice{Parce qu'un humain doit surveiller le programme pendant son exécution}
    \correctchoice{Parce que les données d'entraînement sont étiquetées : chaque exemple est associé à sa classe connue}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q03}
    Comment calcule-t-on la \textbf{distance euclidienne}
entre deux points $A=(x_A, y_A)$ et $B=(x_B,
y_B)$ du plan ?
    \begin{choices}
    \correctchoice{$d = \sqrt{(x_B - x_A)^2 + (y_B - y_A)^2}$}
    \wrongchoice{$d = |x_A - x_B|$}
    \wrongchoice{$d = x_A + y_A + x_B + y_B$}
    \wrongchoice{$d = x_A \times y_A - x_B \times y_B$}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q04}
    Une fois les k plus proches voisins
identifiés, comment k-NN détermine-t-il la
classe à attribuer ?
    \begin{choices}
    \wrongchoice{Au hasard}
    \wrongchoice{En choisissant la classe du voisin le plus proche}
    \correctchoice{Par vote majoritaire : la classe la plus représentée parmi les k voisins l'emporte}
    \wrongchoice{En faisant la moyenne des classes}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q05}
    Pourquoi prend-on souvent k \textbf{impair} quand
on classe en deux classes ?
    \begin{choices}
    \correctchoice{Pour éviter les égalités lors du vote majoritaire entre deux classes}
    \wrongchoice{Aucune raison particulière}
    \wrongchoice{Parce que les nombres impairs sont plus rapides à calculer}
    \wrongchoice{Parce que k pair ne fonctionne pas}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q06}
    Lequel de ces problèmes est un \textbf{bon candidat}
pour l'algorithme k-NN ?
    \begin{choices}
    \wrongchoice{Compresser un fichier pour gagner de la place}
    \wrongchoice{Trier une liste de nombres}
    \correctchoice{Reconnaître si un mail est un spam ou non, à partir d'exemples étiquetés}
    \wrongchoice{Calculer la racine carrée d'un nombre}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q07}
    Quelle particularité de k-NN le distingue
d'autres algorithmes d'apprentissage ?
    \begin{choices}
    \correctchoice{Il n'a quasiment pas de phase d'entraînement : il mémorise les exemples et fait tout le calcul au moment de la prédiction}
    \wrongchoice{Il fonctionne sans aucune donnée d'entraînement}
    \wrongchoice{Il a une phase d'entraînement très longue}
    \wrongchoice{Il invente de nouveaux exemples au cours de la prédiction}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q08}
    Quelle est la \textbf{structure générale} de
l'algorithme k-NN pour classer un nouveau
point \texttt{p} ?
    \begin{choices}
    \correctchoice{1. Calculer la distance de \texttt{p} à chaque exemple connu.
2. Trier les exemples par distance croissante.
3. Garder les k premiers.
4. Retourner la classe majoritaire parmi ces k voisins.
}
    \wrongchoice{1. Trier les exemples par classe.
2. Retourner la première classe.
}
    \wrongchoice{1. Choisir un exemple au hasard.
2. Retourner sa classe.
}
    \wrongchoice{1. Calculer la moyenne des exemples.
2. La retourner comme classe.
}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q09}
    Que se passe-t-il si l'on prend \textbf{k = 1} ?
    \begin{choices}
    \correctchoice{La classe prédite est celle de l'unique voisin le plus proche, l'algorithme est très sensible aux exceptions (bruit) dans le jeu d'entraînement}
    \wrongchoice{La complexité du calcul devient logarithmique}
    \wrongchoice{La prédiction est plus stable}
    \wrongchoice{L'algorithme ne fonctionne pas avec $k = 1$}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q10}
    Avec k = 3, on classe un nouveau point P. Ses
3 plus proches voisins ont les classes : A, B,
A. Quelle classe prédit k-NN pour P ?
    \begin{choices}
    \wrongchoice{Aucune des deux (égalité)}
    \wrongchoice{B (le plus proche)}
    \correctchoice{A (deux votes contre un pour B)}
    \wrongchoice{Les deux à la fois}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q11}
    Quel code calcule correctement la \textbf{distance
euclidienne} entre deux points 2D représentés
comme tuples \texttt{a = (xa, ya)} et \texttt{b = (xb, yb)} ?
    \begin{choices}
    \correctchoice{\texttt{((a[0] - b[0])  2 + (a[1] - b[1])  2)  0.5}}
    \wrongchoice{\texttt{a[0] \textit{ b[0] + a[1] } b[1]}}
    \wrongchoice{\texttt{a + b}}
    \wrongchoice{\texttt{abs(a[0] - b[0]) + abs(a[1] - b[1])}}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q12}
    Pour trouver les k plus proches voisins d'un
point P parmi N exemples, quelle approche est
la plus simple ?
    \begin{choices}
    \correctchoice{Calculer la distance à chacun des N exemples, trier, garder les k premiers}
    \wrongchoice{Aucune solution n'existe pour ce problème}
    \wrongchoice{Choisir k exemples au hasard}
    \wrongchoice{Calculer la moyenne des exemples}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q13}
    Pourquoi est-il souvent \textbf{utile de normaliser}
les caractéristiques des données avant
d'appliquer k-NN ?
    \begin{choices}
    \correctchoice{Parce qu'une caractéristique avec une plage de valeurs très grande (ex. revenu en €) écraserait l'influence d'une caractéristique à plus petite plage (ex. âge en années) dans le calcul de distance}
    \wrongchoice{Pour rendre l'algorithme déterministe}
    \wrongchoice{Pour économiser de la mémoire}
    \wrongchoice{Parce que c'est obligatoire en Python}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q14}
    Quel \textbf{risque} y a-t-il à choisir un k \textbf{trop
grand} (par exemple k = nombre total
d'exemples) ?
    \begin{choices}
    \wrongchoice{Aucun risque ; un grand $k$ est toujours préférable}
    \wrongchoice{Le coût d'un calcul explose en $n^3$}
    \wrongchoice{L'algorithme cesse de fonctionner}
    \correctchoice{La prédiction tend vers la classe majoritaire globale : on perd toute spécificité locale}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q15}
    Que sont les \textbf{données d'entraînement}
(training set) pour k-NN ?
    \begin{choices}
    \wrongchoice{Les nouvelles données à classer}
    \wrongchoice{Une formule mathématique}
    \correctchoice{L'ensemble des exemples étiquetés que k-NN utilise pour comparer un nouveau point. La taille et la qualité de ce jeu déterminent la performance.}
    \wrongchoice{Le code source de l'algorithme}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q16}
    Quel code en Python implémente correctement
k-NN pour classer un point \texttt{p} ?
\begin{lstlisting}
# exemples = [(point, classe), ...]
# k entier, dist(a, b) renvoie la distance
\end{lstlisting}
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
return exemples[0][1]
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
return min(exemples)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
return k
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
from collections import Counter
paires = [(dist(p, x), c) for (x, c) in exemples]
paires.sort()
voisins = [c for (_, c) in paires[:k]]
return Counter(voisins).most_common(1)[0][0]
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q17}
    Le jeu de données \textbf{Iris} est célèbre pour
illustrer la classification. Que contient-il ?
    \begin{choices}
    \wrongchoice{Des mesures de couleurs au format rouge-vert-bleu}
    \correctchoice{150 fleurs d'iris décrites par 4 mesures (longueur/largeur des sépales et pétales) et leur espèce (setosa, versicolor, virginica)}
    \wrongchoice{Des graines à planter}
    \wrongchoice{Des images de fleurs au format JPEG}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q18}
    Si l'on a N exemples d'entraînement, quel est
le \textbf{coût} d'une prédiction k-NN naïve ?
    \begin{choices}
    \wrongchoice{Logarithmique en N}
    \correctchoice{Linéaire en N (proportionnel au nombre d'exemples)}
    \wrongchoice{Constant, indépendant de N}
    \wrongchoice{Quadratique en N}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q19}
    Quelle est une \textbf{limite importante} de k-NN ?
    \begin{choices}
    \wrongchoice{Il ne peut pas faire de classification}
    \wrongchoice{Il ne fonctionne qu'en dimension 2}
    \correctchoice{Il est lent à la prédiction sur de gros jeux d'entraînement (pas de modèle compact appris) et sensible aux échelles des caractéristiques}
    \wrongchoice{Il invente de nouveaux exemples au cours de la prédiction}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q20}
    Une variante de k-NN consiste à \textbf{pondérer le
vote} des voisins. Pourquoi ?
    \begin{choices}
    \correctchoice{Pour donner plus d'influence aux voisins plus proches (typiquement avec un poids proportionnel à $1/d$)}
    \wrongchoice{Pour économiser la mémoire}
    \wrongchoice{Pour rendre l'algorithme aléatoire}
    \wrongchoice{Pour ralentir intentionnellement le programme}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q21}
    Avec k = 3, on classe un point P. Les 5
exemples les plus proches sont (par distance
croissante) : (1.0, classe A), (1.5, B), (2.0,
A), (3.0, A), (4.0, B). Quelle classe prédit
k-NN ?
    \begin{choices}
    \correctchoice{A}
    \wrongchoice{B}
    \wrongchoice{Indéterminé}
    \wrongchoice{Égalité}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q22}
    Pourquoi k-NN devient-il \textbf{moins efficace en
haute dimension} (par exemple 1000 attributs) ?
    \begin{choices}
    \correctchoice{En haute dimension, les distances entre points deviennent presque toutes égales : la notion de « proche » perd son sens. C'est la malédiction de la dimensionnalité.}
    \wrongchoice{La mémoire n'est plus suffisante}
    \wrongchoice{Aucun problème particulier en haute dimension}
    \wrongchoice{Le programme plante systématiquement}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q23}
    Pour évaluer la qualité de k-NN sur un jeu
étiqueté, quelle est la \textbf{bonne pratique} ?
    \begin{choices}
    \wrongchoice{Mesurer la précision sur les exemples d'entraînement eux-mêmes}
    \wrongchoice{Aucune évaluation n'est possible}
    \wrongchoice{Demander l'avis d'un expert humain}
    \correctchoice{Séparer le jeu en données d'entraînement et données de test disjointes, puis mesurer la précision sur les données de test}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q24}
    Peut-on adapter k-NN pour \textbf{prédire un nombre}
(régression) au lieu d'une classe ?
    \begin{choices}
    \wrongchoice{Oui, mais à condition de doubler la valeur de $k$}
    \wrongchoice{Non, l'algorithme est strictement limité à la classification}
    \wrongchoice{Non, il faut nécessairement un autre algorithme}
    \correctchoice{Oui, en remplaçant le vote majoritaire par la moyenne (ou médiane) des valeurs des k voisins}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q25}
    Parmi les affirmations suivantes sur k-NN,
laquelle est \textbf{fausse} ?
    \begin{choices}
    \wrongchoice{La phase d'entraînement se résume essentiellement à mémoriser les exemples.}
    \wrongchoice{La distance euclidienne est un choix courant pour la mesure de proximité.}
    \correctchoice{Plus k est grand, plus l'algorithme est sensible au bruit local.}
    \wrongchoice{k-NN est un algorithme d'apprentissage supervisé.}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q26}
    Outre la distance euclidienne, on rencontre
souvent la \textbf{distance de Manhattan}
(|Δx| + |Δy|). Quel critère permet de choisir
entre ces deux distances ?
    \begin{choices}
    \wrongchoice{Aucun critère, on choisit au hasard}
    \wrongchoice{La distance euclidienne est toujours préférable car elle est plus précise}
    \correctchoice{Le choix dépend de la nature du problème :
la distance euclidienne convient aux
espaces continus avec des déplacements
directs ; la distance de Manhattan
convient aux situations où l'on se déplace
sur une grille (par exemple un quadrillage
urbain ou des composantes indépendantes)
}
    \wrongchoice{La distance de Manhattan est plus rapide à calculer}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q27}
    On veut détecter une maladie rare avec k-NN.
Le jeu d'entraînement contient 95 % d'exemples
« sain » et 5 % d'exemples « malade ». Avec
k = 7, que va prédire l'algorithme pour
presque tous les nouveaux patients ?
    \begin{choices}
    \wrongchoice{« malade » à 5 % des nouveaux patients, par symétrie}
    \wrongchoice{Une classe au hasard, l'algorithme étant non déterministe}
    \correctchoice{« sain » dans la quasi-totalité des cas,
car les voisins les plus proches sont
presque toujours majoritairement « sain » à
cause du déséquilibre des classes ;
l'algorithme passe à côté des cas
« malade »
}
    \wrongchoice{« malade » dans la majorité des cas, par sécurité}
    \end{choices}
  \end{question}
}

\element{premiereknn}{
  \begin{question}{q28}
    On classe le point \texttt{P = (3, 4)} avec k = 3 et
la distance euclidienne. Les exemples
étiquetés sont :
\texttt{(0, 0, A)}, \texttt{(6, 8, A)}, \texttt{(2, 1, B)},
\texttt{(5, 4, B)}, \texttt{(3, 0, A)}. Quelle classe
prédit k-NN ?
    \begin{choices}
    \wrongchoice{A}
    \wrongchoice{Égalité entre A et B}
    \wrongchoice{Indéterminé sans plus d'informations}
    \correctchoice{B}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{premiereknn}
  \insertgroup{premiereknn}
}

\end{document}
