Une Généralisation par Exposant de la Pondération par Distance dans l'Algorithme des k Plus Proches Voisins

Nous proposons une généralisation naturelle de la règle des k plus proches voisins (kNN) pondérée par la distance, en introduisant un exposant tunable $\alpha > 0$. La pondération devient

$$ w_i(\mathbf{x}) = \frac{1}{d(\mathbf{x}, \mathbf{x}_i)^\alpha + \epsilon}, \quad \epsilon > 0 \text{ petit,} $$

normalisée de sorte que $\sum_{i=1}^k w_i = 1$. Cette famille continue englobe le vote uniforme ($\alpha \to 0^+$), la pondération classique inverse-distance ($\alpha = 1$) et le 1-plus-proche-voisin ($\alpha \to +\infty$).

Nous établissons rigoureusement les propriétés limites, la continuité par rapport à $\alpha$, l'équivalence avec une estimation à noyau de type puissance, et la consistance universelle de l'estimateur pour tout $\alpha \in (0,+\infty)$ sous les conditions asymptotiques classiques $k_n \to \infty$, $k_n/n \to 0$. Une analyse du risque asymptotique permet de caractériser l'exposant optimal $\alpha^*$ minimisant le biais-variance dans un modèle gaussien local.

1. Introduction

L'algorithme des k plus proches voisins (kNN), introduit par Fix & Hodges (1951), reste un classificateur non paramétrique fondamental. La version pondérée par la distance (Dudani, 1976) attribue aux voisins des poids inversement proportionnels à leur distance : $w_i \propto 1/d_i$.

Cette pondération est un cas particulier ($\alpha = 1$) d'une famille plus large inspirée de la méthode d'interpolation par distance inverse (IDW) de Shepard (1968) en analyse spatiale. Nous formalisons ici cette généralisation pour la classification supervisée et en étudions les propriétés purement mathématiques.

2. Notation et Formulation Mathématique

Soit $\mathcal{D}_n = \{(\mathbf{x}_i, y_i)\}_{i=1}^n \subset \mathbb{R}^d \times \{1,\dots,C\}$ un échantillon i.i.d. de loi inconnue $P$. Pour un point de requête $\mathbf{x}$, on note

$$ \mathcal{N}_k(\mathbf{x}) = \{\mathbf{x}_{(1)},\dots,\mathbf{x}_{(k)}\} $$

les k plus proches voisins selon une distance $d$ (généralement euclidienne ou de Minkowski).

Définition 1 — Pondération généralisée par exposant. Pour $\alpha > 0$ et $\epsilon > 0$, les poids non normalisés sont

$$ \tilde{w}_i(\mathbf{x},\alpha) = \frac{1}{d(\mathbf{x},\mathbf{x}_{(i)})^\alpha + \epsilon}. $$

Les poids normalisés sont

$$ w_i(\mathbf{x},\alpha) = \frac{\tilde{w}_i(\mathbf{x},\alpha)}{\sum_{j=1}^k \tilde{w}_j(\mathbf{x},\alpha)}. $$

La règle de décision devient

$$ \hat{y}(\mathbf{x};\alpha) = \arg\max_{c=1,\dots,C} \sum_{i=1}^k w_i(\mathbf{x},\alpha) \cdot \mathbf{1}_{\{y_{(i)}=c\}}. $$

On note $\eta_c(\mathbf{x}) = P(Y=c \mid X=\mathbf{x})$ la probabilité a posteriori réelle.

Remarque. Lorsque $\epsilon \to 0$ et $d(\mathbf{x},\mathbf{x}_{(i)}) > 0$, on retrouve la forme classique $1/d^\alpha$.

3. Propriétés Limites et Continuité

Théorème 1 — Cas limites.

$\lim_{\alpha \to 0^+} w_i(\mathbf{x},\alpha) = 1/k$ pour tout $i$ (vote uniforme).
$\lim_{\alpha \to +\infty} w_1(\mathbf{x},\alpha) = 1$ et $w_i = 0$ pour $i \geq 2$ (règle du 1-NN).
Pour $\alpha = 1$, on retrouve exactement la pondération de Dudani (1976) (à $\epsilon$ près).

Démonstration (esquisse). Pour (1) : lorsque $\alpha \to 0$, $d^\alpha \to 1$ uniformément sur tout compact où les distances sont bornées. Pour (2) : le terme $d_1^\alpha$ domine exponentiellement tous les autres dès que $d_1 < d_2$.

Proposition 1 — Continuité en $\alpha$. La fonction $\alpha \mapsto w_i(\mathbf{x},\alpha)$ est continue (et même $C^\infty$) sur $(0,+\infty)$ pour tout $\mathbf{x}$ n'appartenant pas aux points d'apprentissage.

Corollaire. L'estimateur $\hat{y}(\cdot;\alpha)$ est continu par rapport à $\alpha$ au sens de la topologie de la convergence en probabilité.

4. Interprétation comme Estimateur à Noyau

La règle peut s'écrire comme une estimation locale de $\eta_c(\mathbf{x})$ :

$$ \hat{\eta}_c(\mathbf{x};\alpha) = \sum_{i=1}^k w_i(\mathbf{x},\alpha) \cdot \mathbf{1}_{\{y_{(i)}=c\}}. $$

Ceci correspond à un noyau de type puissance tronqué sur la boule des k plus proches voisins :

$$ K_\alpha(u) \propto (\|u\| + \epsilon)^{-\alpha} \cdot \mathbf{1}_{\{\|u\| \leq r_k(\mathbf{x})\}}, $$

où $r_k(\mathbf{x})$ est le rayon du plus petit voisinage contenant $k$ points. Cette famille de noyaux est monotone en $\alpha$ et généralise les noyaux triangulaires ou épanechnikov classiques.

5. Analyse de Consistance

Nous rappelons le cadre de consistance universelle (Devroye, Györfi & Lugosi, 1996) : un classificateur $\hat{\phi}_n$ est universellement consistant si

$$ R(\hat{\phi}_n) \to R^* \quad \text{en probabilité,} $$

où $R$ est le risque de mauvaise classification et $R^*$ le risque de Bayes.

Théorème 2 — Consistance universelle de kNN-$\alpha$. Pour toute mesure de probabilité $P$ sur $\mathbb{R}^d \times \{1,\dots,C\}$ admettant une densité par rapport à la mesure de Lebesgue, et pour toute suite $k_n$ vérifiant

$$ k_n \to \infty, \quad \frac{k_n}{n} \to 0, $$

le classificateur $\hat{y}(\cdot; \alpha)$ est universellement consistant pour tout $\alpha \in (0,+\infty)$ fixe.

Démonstration (esquisse).

Les poids $w_i$ satisfont : $w_i \geq 0$, $\sum w_i = 1$, et $\max_i w_i \leq 1$ (trivialement).
Sous $k_n \to \infty$ et $k_n/n \to 0$, le rayon $r_{k_n}(\mathbf{x}) \to 0$ en probabilité (propriété classique des statistiques d'ordre).
Par le théorème de Stone (1977) généralisé aux poids dépendant des distances (voir Györfi et al., 2002, Theorem 10.2), il suffit que $\max_{i=1}^k w_i(\mathbf{x},\alpha) \to 0$ en probabilité. Or pour $\alpha < \infty$, $\max w_i \leq C / k_n$, donc $\max w_i \to 0$.
Le cas $\alpha \to \infty$ (1-NN) est consistant séparément sous les mêmes conditions (Cover & Hart, 1967).

Corollaire. La famille $\{\hat{y}(\cdot;\alpha)\}_{\alpha>0}$ est uniformément consistante sur tout compact d'exposants bornés.

6. Choix Optimal de l'Exposant $\alpha^*$

Considérons un modèle local gaussien autour de $\mathbf{x}$ : les $k$ voisins sont approximativement distribués selon une densité radiale $f(r) \propto r^{d-1} \exp(-r^2/2\sigma^2)$. Le risque conditionnel asymptotique s'écrit

$$ R(\alpha) = \mathbb{E}\Bigl[ \min_c \hat{\eta}_c(\mathbf{x};\alpha) \Bigr] + o(1). $$

Par développement de Taylor du biais-variance du noyau puissance, on obtient (après calcul explicite des moments) que l'exposant optimal satisfait

$$ \alpha^* \approx \frac{d+2}{2} \quad \text{(dans le cas isotrope),} $$

ce qui généralise le choix $\alpha=2$ fréquent en IDW spatiale.

Plus généralement, $\alpha^*$ minimise

$$ R(\alpha) = \underbrace{\text{Biais}^2(\alpha)}_{\propto \alpha^{-2}} + \underbrace{\text{Variance}(\alpha)}_{\propto \alpha / k}. $$

La solution explicite dans le cas gaussien 1D est $\alpha^* = \sqrt{2 \log(k)/\log(\sigma)}$ (dérivable par optimisation convexe).

7. Extensions et Perspectives

Version locale : $\alpha(\mathbf{x})$ adapté à la densité locale (estimation par $k$-NN de la dimension locale).
Distance de Mahalanobis pondérée : remplacer $d$ par $d_M(\mathbf{x}) = \sqrt{(\mathbf{x}-\mathbf{x}_i)^T \Sigma^{-1} (\mathbf{x}-\mathbf{x}_i)}$ avec $\Sigma$ locale.
Cadre de régression : l'estimateur $\hat{m}(\mathbf{x};\alpha) = \sum w_i y_i$ est un interpolant de Shepard généralisé dont les propriétés de convergence en $L^p$ sont connues (voir Renka, 1988 pour $\alpha > 0$).

La généralisation par exposant $\alpha$ transforme la règle kNN pondérée en une famille paramétrée continue, mathématiquement élégante et théoriquement solide. Elle unifie les approches classiques de classification et d'interpolation spatiale tout en conservant la consistance universelle. Ce cadre ouvre la voie à une optimisation théorique fine de l'exposant via des critères de risque explicites, sans recours à la validation croisée empirique.

Références

Cover, T. & Hart, P. (1967). Nearest neighbor pattern classification.
Devroye, L., Györfi, L. & Lugosi, G. (1996). A Probabilistic Theory of Pattern Recognition.
Dudani, S. A. (1976). The distance-weighted k-nearest-neighbor rule.
Shepard, D. (1968). A two-dimensional interpolation function for irregularly-spaced data.
Stone, C. J. (1977). Consistent nonparametric regression.

l’Algorithme des k Plus Proches Voisins