L'unité change le voisin

En (kg, mm) : $d^2(x,A)=0,4^2+28^2=784,16$ et $d^2(x,B)=0,6^2+2^2=4,36$. Le plus proche est $B$ : l'algorithme répond gros.

En (g, mm) : $A=(1000,100)$, $B=(2000,130)$, $x=(1400,128)$, d'où $d^2(x,A)=400^2+28^2=160784$ et $d^2(x,B)=600^2+2^2=360004$. Le plus proche est $A$ : l'algorithme répond petit.

La même donnée, la même distance, deux réponses opposées. La distance euclidienne additionne des carrés d'écarts exprimés dans leurs unités : elle n'a aucune raison d'être invariante par changement d'échelle. En kilogrammes, la masse pèse trop peu et la longueur décide seule ; en grammes, c'est l'inverse.

La parade est le centrage-réduction : on remplace chaque coordonnée $v$ par $(v-\mu )/\sigma$, où $\mu$ et $\sigma$ sont la moyenne et l'écart type de cette coordonnée sur les données d'entraînement. Les valeurs réduites ne portent plus d'unité, et le calcul refait sur les données réduites donne $d^2(x,A)=4,1244$ et $d^2(x,B)=1,4578$ — les mêmes deux nombres en kilogrammes et en grammes, comme il se doit.

(* Renvoie la fonction qui centre et réduit un point, calibrée sur pts.
   Précondition : pts non vide, aucun écart type nul. *)
let reduire pts =
  let d = Array.length (List.hd pts) in
  let n = float_of_int (List.length pts) in
  let moy = Array.init d (fun j ->
      List.fold_left (fun s p -> s +. p.(j)) 0.0 pts /. n) in
  let ec = Array.init d (fun j ->
      sqrt (List.fold_left (fun s p -> s +. (p.(j) -. moy.(j)) ** 2.0) 0.0 pts /. n)) in
  fun p -> Array.init d (fun j -> (p.(j) -. moy.(j)) /. ec.(j))

Deux pièges dans ces six lignes. Le premier : $\mu$ et $\sigma$ se calculent sur les données d'entraînement seules, et la même fonction s'applique ensuite au test — les calculer sur l'ensemble complet ferait fuiter de l'information du test vers l'entraînement, et le problème 26.4 montre ce que cela coûte. Le second : un écart type nul, c'est-à-dire une coordonnée constante, produit une division par zéro ; cette coordonnée n'apporte rien et doit être retirée.