Probleme – Des $k$ plus proches voisins au choix de $k$

1. Les deux fonctions manquantes.

(* Les k premiers éléments de l, ou l entière si elle est plus courte.
   Précondition : k >= 0. Terminaison : k décroît strictement, ou l se vide.
   Complexité : Theta(min(k, |l|)). *)
let rec prendre k l = match k, l with
  | 0, _ | _, [] -> []
  | k, x :: r -> x :: prendre (k - 1) r

(* Étiquette majoritaire d'une liste de booléens ; None en cas d'égalité.
   Précondition : l non vide. Complexité : Theta(|l|). *)
let majoritaire l =
  let o = List.length (List.filter (fun b -> b) l) in
  let n = List.length l in
  if 2 * o > n then Some true else if 2 * o < n then Some false else None

Le type de retour bool option n'est pas une coquetterie : c'est l'égalité de l'exercice 26.2, rendue visible dans le type. Une fonction qui renverrait bool devrait inventer une réponse, et l'appelant ne saurait jamais qu'elle a été inventée. C'est la discipline du chapitre chap:abstraction : ce qui peut échouer le dit dans sa signature.

2. La complexité annoncée n'est pas atteinte. Le code du cours trie avec fun a b -> compare (d2 a) (d2 b) : la distance est donc recalculée à chaque comparaison, et il y a $\Theta (n\log n)$ comparaisons. Le coût réel est $\Theta (nd\log n)$, non $O(nd+n\log n)$. En comptant les appels à d2 :

Le rapport croît comme $2{\log }_{2}n$ : chaque comparaison appelle d2 deux fois. La correction est le procédé décorer, trier, ôter la décoration :

(* Étiquette prédite pour x. Précondition : k >= 1, donnees non vide.
   Complexité : Theta(n·d) pour les distances + Theta(n log n) pour le tri. *)
let knn donnees k x =
  let decore = List.map (fun (p, e) -> (d2 p x, e)) donnees in   (* n·d *)
  let triees = List.sort (fun (a, _) (b, _) -> compare a b) decore in
  majoritaire (List.map snd (prendre k triees))

Une ligne de plus, et la complexité annoncée devient vraie. C'est un défaut de classe : dès qu'une clé de tri coûte cher, on la calcule une fois par élément, jamais dans le comparateur.

3. Choisir $k$ sans tricher. Il faut trois lots, et non deux :

Choisir $k$ sur le lot de test serait une fuite : le chiffre annoncé serait le meilleur de dix essais, donc optimiste. C'est un sur-apprentissage du choix de $k$, plus insidieux que celui du modèle parce qu'il ne laisse aucune trace. Quand les données sont rares, on remplace le lot de validation par une validation croisée : on découpe l'entraînement en cinq parts, on entraîne cinq fois sur quatre parts et l'on évalue sur la cinquième, et l'on moyenne.

4. Ne prendre que les $k$ plus proches. Trier coûte $\Theta (n\log n)$ pour une information dont on n'utilise que les $k$ premiers termes. Deux procédés font mieux :

• un tas de taille $k$ (chapitre chap:tas) : on parcourt les $n$ points en maintenant les $k$ meilleurs, soit $\Theta (n\log k)$ ;
• une sélection par partition à la Hoare (chapitre chap:diviser) : $\Theta (n)$ en moyenne.

Pour $n=10^6$ et $k=5$, le premier divise le nombre de comparaisons par ${\log }_{2}10^6/{\log }_{2}5\approx 8,6$. Et si les requêtes sont nombreuses, on ne parcourt plus du tout : c'est l'arbre $k$-d de l'exercice 26.7, qui descend en $O(\log n)$ en moyenne — en petite dimension seulement, car en dimension élevée le test d'élagage échoue presque toujours et l'arbre redevient un parcours complet.