\def\NomChapitre{$k$ plus proches voisins}
\def\Type{TP}
\LeTitre{\Type}{\NomChapitre}

\section{Préliminaires} 

\begin{exo}[Fonctions auxiliaires générales]
Nous allons coder plusieurs fonctions qui serviront pour l'algorithme kNN,
mais qui ne sont pas l'algorithme kNN.
\begin{enumerate}
\item Écrire une fonction \lstinline$d_carre(x, y)$ qui prend en arguments deux
  $d$-uplets \lstinline$x$ et \lstinline$y$ représentant des points de $\R^d$
  et retourne la distance entre 
  $x$ et $y$ {\em au carré}.\\
 \rmqbla{On veut minorer la distance, pour ça il est
  inutile de calculer une racine carrée. Ici aussi, la norme euclidienne
  se manipule... au carré !}
\item Écrire une fonction \lstinline$liste_dc(x, Ly)$ qui prends en arguments un
  $d$-uplet \lstinline$x$, et une liste de $d$-uplets \lstinline$Ly$. Elle
  retourne la liste des distances aux carrée : si on note \lstinline$L$ cette
  liste, \lstinline$L[i]$ contient $\norme{x-Ly[i]}_2^2$.
\end{enumerate}
\end{exo}

\begin{exo}[Données d'apprentissage]
Nous allons importer les données $\cE$ d'apprentissage. 

Dans cet exercice, ce sont des points choisis aléatoirement par python
 dans le carré $[-1,1]^2 \subset \R^2$. On étiquette en rouge ($r=1$) les
 points à l'intérieur du disque unité, et en bleu ($r=0$) ceux à l'extérieur.

\begin{enumerate}
\item À l'aide de l'instruction « \lstinline$from donnees_app_TP1 import *$ »,
  importez les fonctions contenues dans \lstinline$donnees_app_TP1.py$ que vous
  avez reçu par mail.
\item Testez les deux fonctions. 
\end{enumerate}
\end{exo}

\section{Algorithme kNN}


\begin{exo}[Recherche des $k$ plus proches voisins]
Si la question $2$ vous bloque, contournez la temporairement en utilisant
l'instruction suivante pour trier \lstinline$M$ selon la seconde composante :
\lstinline$sorted(M, key=lambda m : m[1])$
%sorted(donnees, key=lambda d: (d[0] - m[0]) ** 2 + (d[1] - m[1]) ** 2)[:k]$.
\begin{enumerate}
\item Écrire une fonction qui retourne l'indice du minimum dans une liste
  \lstinline$L$.
% Écrire une fonction \lstinline$ikmini(L, k)$
% qui retourne les indices des $k$ plus petits éléments de \lstinline$L$, sous
% forme de liste.
% On supposera que $k$ est très petit devant la taille de $L$.

% Pour initialiser la valeur du minimum, vous pouvez utiliser un booléen :
% \lstinline$est_init = False$ en 

% \rmqbla{Une autre façon de déterminer les $k$ plus petits consiste à écrire 
\item On se donne une liste \lstinline$L$ et on 
considère la liste \lstinline$M=[(i, L[i]) for i in range(len(L))]$.

Écrire une fonction \lstinline$tri_partiel(M, k)$ qui trie \lstinline$M$
définie précédemment, par
ordre croissant sur la seconde composante, en s'arrêtant après avoir trié $k$
(entier)
éléments. La méthode de tri utilisé sera un tri par sélection. On pourra
adapter la fonction de la question précédente.

\item Écrire une fonction 
\lstinline$indice_voisins(x, Ly, k)$ qui prend en entrée un point 
\lstinline$x$, une liste de points \lstinline$Ly$ et un entier \lstinline$k$,
et renvoie la liste des indices
des \lstinline$k$ voisins de \lstinline$x$ dans \lstinline$Ly$
 les plus proches. On s'aidera des fonctions 
\lstinline$liste_dc(x, Ly)$ et
\lstinline$tri_partiel(M, k)$.
\item Écrire une fonction 
\lstinline$labels_voisins(Lindices, labels)$ qui retourne la valeur la plus
fréquente dans la liste des
\lstinline$labels[i]$ pour \lstinline$i$ parcourant \lstinline$Lindices$.

On pourra utiliser un dictionnaire.
\end{enumerate}
\end{exo}

\begin{exo}[Algorithme kNN]
Écrire une fonction \lstinline$kNN(x, Lx, labels, k)$ 
qui renvoie la valeur de l'étiquette associée à \lstinline$x$ 
via l'algorithme des $k$-plus proches voisins.
\end{exo}

\begin{exo}[Affichage du résultat]
En balayant $[-1, 1]$ à l'aide de \lstinline$np.linspace(-1,1,n)$, créer deux
listes \lstinline$Lx_essai$ et \lstinline$labels_essai$ contenant respectivement
des points de $[-1,1]^2$ et leur étiquette déterminée par \lstinline$kNN$.

Afficher le résultat (les arguments de \lstinline$affiche_donnees_disque$
doivent être des tableaux NumPy).
\end{exo}


\section{Amélioration : $\cE_A$ et $\cE_T$, tests de différents $k$}

Dans cette section, on cherche à tester notre algorithme sur une partie des
données d'apprentissage $\cE$. Il faut donc séparer ces données en deux
ensemble $\cE_A$, qui servira à l'apprentissage, et $\cE_T$, qui servira aux
tests.


\begin{exo}[Séparation des données]
Dans l'idéal, il faut faire la liste des points pour chaque étiquette, et
prendre la même proportion de points pour $\cE_T$ dans chaque étiquette.

Nous allons faire plus simple.
\begin{enumerate}
\item À l'aide de \lstinline$np.random.shuffle$, mélanger la liste
\lstinline$list(range(len(Lx)))$, où \lstinline$Lx$ contient l'ensemble
$\cE$. C'est une fonction {\em en place}.
\item Construire une fonction \lstinline$partage_donnees(Lx, labels, ratio)$
qui retourne un quadruplet 
\lstinline$(Lx_test, labels_test, Lx_app, labels_app)$, où une proportion \lstinline$ratio$ des données est dans
\lstinline$(Lx_test, labels_test)$ et le reste dans
\lstinline$(Lx_app, labels_app)$.
\end{enumerate}
\end{exo}


\begin{exo}[test]
Nous allons tester la qualité de l'algorithme : d'abord un pourcentage de
données test bien étiquetées, puis la matrice de confusion.

\begin{enumerate}
\item
  Écrire une fonction \lstinline$prediction(Lx_app, labels_app, Lx_test, k)$,
  qui retourne une liste \lstinline$labels_kNN$ des étiquettes calculées par
  \lstinline$kNN(x, Lx_app, labels_app, k)$.
\item Écrire une fonction \lstinline{pourcentage_reussite(labels_test, labels_kNN)} qui
  prend en entrée les étiquettes connues \lstinline{labels_test}, ainsi que
  les étiquettes \lstinline{labels_kNN} prédies par l'algorithme kNN, et qui
  renvoie 
  le pourcentage de bonnes étiquettes.
\item Modifier la fonction \lstinline$obtenir_disque$ du fichier
\lstinline$donnees_app_TP1.py$ : 

\lstinline$labels = [int(np.linalg.norm(x) <= 1) * (np.random.random_sample()*10 > 1) for x in Lx]$

Cette instruction va rajouter du « bruit », des points bleus dans le disque
rouge avec une probabilité de $1/10$.

Faire un graphique qui affiche le pourcentage de bonnes étiquettes pour les données test en fonction de la valeur \lstinline{k} pour l'algorithme kNN.
\item Écrire une fonction \lstinline{confusion(labels_test, labels_kNN)} qui
  calcule la 
  matrice de confusion. 
\end{enumerate}
\end{exo}




% \section{Autres données d'apprentissage}

% Avec des images noir et blanc de chiffres de $0$ à $9$, sous forme de tableaux
% NumPy. Les données sont fournies par le package \lstinline$sklearn$.



%%% Local Variables:
%%% mode: latex
%%% TeX-PDF-mode: t
%%% TeX-master: FeuillekNN_2022
%%% End:
