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

\section{Préliminaires} 

\begin{exo}[Fonctions auxiliaires : distance]
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$.

\lstinline$Ly$ est une liste de points $y$ de $\R^d$.
\end{enumerate}
\end{exo}

\begin{exo}[Fonctions auxiliaires : minima]
~\\\vspace{-1cm}
\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 
\begin{center}
\lstinline$M=[(i, L[i])\quad  for i in range(len(L))]$.
\end{center}
É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\in\N^*$ éléments : on se contente de placer correctement les $k$ plus
petits éléments de \lstinline$M$ (pour l'ordre sur la seconde composante).

La méthode de tri utilisé sera un tri par sélection. 
On pourra
utiliser une version modifiée de la fonction codée à la question 1.
\end{enumerate}
Si vous êtes bloqués à la dernière question, contournez la temporairement
-- pour la suite du TP -- en
utilisant 
l'instruction suivante pour trier \lstinline$M$ selon la seconde composante :
\lstinline$sorted(M, key=lambda m : m[1])$.

Ce qui consiste à trier (\lstinline$sorted$) en appliquant avant la fonction
(\lstinline$lambda$) « prendre l'élément d'indice $1$ » à chaque élément de
\lstinline$M$.

%sorted(donnees, key=lambda d: (d[0] - m[0]) ** 2 + (d[1] - m[1]) ** 2)[:k]$.
\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 (noté $r=1$) les
 points à l'intérieur du disque unité, et en bleu (noté $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çues par mail. (Vous pouvez lire les fonctions pour comprendre ce
  qu'elles font).
\item Testez les deux fonctions : 
\begin{itemize}
\item \lstinline$Ly, labels = obtenir_disque()$ 
\item  \lstinline$affiche_donnees_disque(Ly, labels)$
\end{itemize}
\end{enumerate}
\end{exo}

\section{Algorithme kNN}


\begin{exo}[Recherche des $k$ plus proches voisins]
On utilisera les fonctions écrites dans les trois précédents exercices.
\begin{enumerate}
\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, Ly, labels, k)$ 
qui renvoie la valeur du label 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$Ly_essai$ et \lstinline$labels_essai$ contenant respectivement
des points de $[-1,1]^2$ et leur label 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 label, et
prendre la même proportion de points pour $\cE_T$ dans chaque label.

Nous allons faire plus simple.
\begin{enumerate}
\item À l'aide de \lstinline$np.random.shuffle$, mélanger la liste
\lstinline$list(range(len(Ly)))$, où \lstinline$Ly$ contient l'ensemble
$\cE$. C'est une fonction {\em en place}.
\item Construire une fonction \lstinline$partage_donnees(Ly, labels, ratio)$
qui retourne un quadruplet 
\lstinline$(Ly_test, labels_test, Ly_app, labels_app)$, où une proportion \lstinline$ratio$ des données est dans
\lstinline$(Ly_test, labels_test)$ et le reste dans
\lstinline$(Ly_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(Ly_app, labels_app, Ly_test, k)$,
  qui retourne une liste \lstinline$labels_kNN$ des labels calculées par
  \lstinline$kNN(x, Ly_app, labels_app, k)$.
\item Écrire une fonction \lstinline{confusion(labels_test, labels_kNN)} qui
  calcule la 
  matrice de confusion. 

\item Écrire une fonction \lstinline{pourcentage_reussite(labels_test, labels_kNN)} qui
  prend en entrée les labels connues \lstinline{labels_test}, ainsi que
  les labels \lstinline{labels_kNN} prédies par l'algorithme kNN, et qui
  renvoie 
  le pourcentage de bons labels.
\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 Ly]$

Cette instruction va rajouter du « bruit », des points bleus dans le disque
rouge avec une probabilité de $1/10$. En détail :
   \lstinline$np.random.random_sample()$ 
retourne un nombre au hasard entre $0$ et $1$, selon une loi uniforme.
Donc \lstinline$(np.random.random_sample()*10 > 1)$ vaut $0$ avec probabilité 
de  $1/10$, et vaut 1 sinon.


Faire un graphique qui affiche le pourcentage de bons labels pour les données test en fonction de la valeur \lstinline{k} pour l'algorithme kNN.
\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_2024
%%% End:
