Search
KNN Les voisins les plus proches

La méthode des voisins les plus roches (K-nearest neighbors) est un des plus simples des algorithmes d’apprentissage supervisé. Avant de plonger dans les détails de cet algorithme, introduisons d'abord quelques concepts de base qui nous permettront de bâtir un KNN.

Distances entre deux observations

Si l'on considère chaque observation comme un point dans un espace à $p$ dimensions, où $p$ est le nombre de variables explicatives dans l'ensemble de données, on peut calculer la distance mathématique entre ces points. Plus la distance est faible, plus ils sont proches (ou regroupés lorsque nous verrons la notion sur le clustering).

Distance Euclidienne

Il existe de nombreuses façons de calculer les distances et différents algorithmes utilisent différentes méthodes de calcul de la distance. Voyons la méthode la plus connue, soit la distance Euclidienne à l'aide d'un exemple.

import pandas as pd
import matplotlib.pyplot as plt
import numpy as np

Tout d'abord, créons quelques points dans l'espace $\mathbb{R}^2$

d = {'Points' : ["p1","p2","p3","p4","p5","p6"],
    'x_Coordinate' : [0.4,0.22,0.35,0.26,0.08,0.45],
     'y_Coordinate' : [0.53,0.38,0.32,0.19,0.41,0.3]}
df_h=pd.DataFrame(d)
df_h
Points x_Coordinate y_Coordinate
0 p1 0.40 0.53
1 p2 0.22 0.38
2 p3 0.35 0.32
3 p4 0.26 0.19
4 p5 0.08 0.41
5 p6 0.45 0.30

Traçons ensuite un nuage de points;

x=df_h.x_Coordinate
y=df_h.y_Coordinate
n=df_h.Points
fig, ax = plt.subplots(figsize=(10,8))
ax.scatter(x, y,s=50, alpha=0.5);
for i, txt in enumerate(n):
    ax.annotate(txt, (x[i]+.005,y[i]))

la distance euclidienne entre chaque couple de points se calcule comme suit:

\begin{equation} \label{eq:euc} \mathrm{d}(\mathbf{x},\mathbf{y})= \sqrt{\sum_{i=1}^n (x_i-y_i)^2} \end{equation}

Si l'on prend comme exemple la distance Euclidienne entre le point $p_1$ et le point $p_2$;

$$ d(p_1,p_2)=\sqrt{(.4-.22)^2 + (.53-.38)^2} $$
print(np.sqrt(((.4-.22)**2)+(.53-.38)**2))
0.23430749027719966

Rapidemnt;

from scipy.spatial.distance import squareform, pdist
df_dis_mtx1=pd.DataFrame(squareform(pdist(df_h.iloc[:, 1:])), columns=df_h.Points.unique(), index=df_h.Points.unique())
df_dis_mtx1
p1 p2 p3 p4 p5 p6
p1 0.000000 0.234307 0.215870 0.367696 0.341760 0.235372
p2 0.234307 0.000000 0.143178 0.194165 0.143178 0.243516
p3 0.215870 0.143178 0.000000 0.158114 0.284605 0.101980
p4 0.367696 0.194165 0.158114 0.000000 0.284253 0.219545
p5 0.341760 0.143178 0.284605 0.284253 0.000000 0.386005
p6 0.235372 0.243516 0.101980 0.219545 0.386005 0.000000

Ou on peut utiliser aussi utiliser euclidean_distances de sklearn

from sklearn.metrics.pairwise import euclidean_distances
df_dis_mtx=pd.DataFrame(euclidean_distances(df_h.iloc[:, 1:],df_h.iloc[:, 1:]), index=["p1","p2","p3","p4","p5","p6"])
df_dis_mtx.columns=["p1","p2","p3","p4","p5","p6"]
df_dis_mtx
p1 p2 p3 p4 p5 p6
p1 0.000000 0.234307 0.215870 0.367696 0.341760 0.235372
p2 0.234307 0.000000 0.143178 0.194165 0.143178 0.243516
p3 0.215870 0.143178 0.000000 0.158114 0.284605 0.101980
p4 0.367696 0.194165 0.158114 0.000000 0.284253 0.219545
p5 0.341760 0.143178 0.284605 0.284253 0.000000 0.386005
p6 0.235372 0.243516 0.101980 0.219545 0.386005 0.000000

Distance de Manhattan

from sklearn.metrics.pairwise import manhattan_distances
df_dis_mtx=pd.DataFrame(manhattan_distances(df_h.iloc[:, 1:],df_h.iloc[:, 1:]), index=["p1","p2","p3","p4","p5","p6"])
df_dis_mtx.columns=["p1","p2","p3","p4","p5","p6"]
df_dis_mtx
p1 p2 p3 p4 p5 p6
p1 0.00 0.33 0.26 0.48 0.44 0.28
p2 0.33 0.00 0.19 0.23 0.17 0.31
p3 0.26 0.19 0.00 0.22 0.36 0.12
p4 0.48 0.23 0.22 0.00 0.40 0.30
p5 0.44 0.17 0.36 0.40 0.00 0.48
p6 0.28 0.31 0.12 0.30 0.48 0.00

Normalisation des distances

Ces distances peuvent parfois être trompeuses si les variables ne sont pas dans la même plage numérique, par exemple les salaires avec les âges... etc. Dans ce cas, les variables ayant des valeurs numériques plus élevées commencent à influencer la distance plus que celles ayant des valeurs numériques plus faibles. Cela donne une importance excessive aux variables ayant de grandes valeurs numériques et atténue l'importance de celles qui ont de petites valeurs numériques.

La solution à ce problème consiste à normaliser les valeurs des variables pour les amener dans la même plage numérique. La normalisation implique la transformation numérique de chaque valeur pour qu'elles se situent dans la même plage numérique. La méthode suivante est utilisée pour normaliser les valeurs. Cette méthode utilise les valeurs $min$ et $max$ et la transformation est définie comme suit

$$ Z_i=(\frac{\mathbf{x}_i-\mathbf{x}_{min}}{\mathbf{x}_{max}-\mathbf{x}_{min}}) $$

Notez que $X_i$ est la valeur des variables, $X_min$ est la valeur minimale de la variable, $X_max$ est la valeur maximale de la variable, et $Z_i$ est la valeur normalisée de la variable.

KNN Exemple

  • Il s'agit d'un algorithme simple d'apprentissage supervisé.
  • Pour une base de données $(y_i, \mathbf{x}_i)_{i = 1, 2, \ldots, n}$ et une valeur de $K$, on définit l'ensemble des $K$ plus proches voisins du point $\mathbf{x}_0$, $\mathcal{X}_0^{(K)}$, comme étant l'ensemble des $K$ points $\mathbf{x}_i$ de la base de données pour lesquels la valeur de $||\mathbf{x}_i - \mathbf{x}_0||_2$ est la plus petite.
  • Pour une nouvelle observation $\mathbf{x}_0$, la prédiction sera donnée par \begin{align*} \tilde{Y} &= \frac{1}{K}\sum_{i: \mathbf{x}_i \in \mathcal{X}_0^{(K)}} y_i. \end{align*}

image.png

from sklearn import neighbors
import seaborn as sns
np.random.seed(6100)
X = np.sort(5 * np.random.rand(40, 1), axis=0)
T = np.linspace(0, 5, 500)[:, np.newaxis]
y = np.sin(X).ravel()
y
array([ 0.08335401,  0.08287275,  0.35255811,  0.51276741,  0.54515842,
        0.59232352,  0.69768928,  0.70457307,  0.93602295,  0.9397481 ,
        1.15614179,  0.99883968,  0.99969643,  0.99992081,  0.94583152,
        0.77365989,  0.89352103,  0.52547213,  0.46315809,  0.41146282,
       -0.10279616,  0.20040521,  0.13815842,  0.03586796, -0.03051141,
        0.18531811, -0.21539671, -0.24100595, -0.37553478, -0.39863881,
       -0.87358208, -0.80252455, -0.90181282, -0.90687202, -0.93555622,
       -0.78345686, -0.98252169, -0.99280093, -0.99952885, -0.97265408])
# Ajoutons un peu de bruit à notre 
y[::5] += 1 * (0.5 - np.random.rand(8))
plt.subplots(1,1)
plt.scatter(x=X, y=y, facecolor='None', edgecolor='k', alpha=0.3, label='vraies données');
sns.regplot(x=X, y=y, order = 1, truncate=True, scatter=False, label='régression');
plt.axvline(x=2, color="g");
plt.axvline(x=1, color="r")
plt.legend();

k=5

knn = neighbors.KNeighborsRegressor(5)
model_knn=knn.fit(X, y)
y_hat_knn=model_knn.predict(T)
y_ = knn.fit(X, y).predict(T)
plt.subplots(1,1)
plt.scatter(x=X, y=y, facecolor='None', edgecolor='k', alpha=0.3, label='data')
plt.plot(T, y_hat_knn, color='navy', label='prediction')
plt.legend();

k=30

knn = neighbors.KNeighborsRegressor(30)

model_knn=knn.fit(X, y)

y_hat_knn=model_knn.predict(T)

y_ = knn.fit(X, y).predict(T)

plt.subplots(1,1)
plt.scatter(x=X, y=y, facecolor='None', edgecolor='k', alpha=0.3, label='data')
plt.plot(T, y_hat_knn, color='navy', label='prediction')
plt.legend();

k=[1,3,10]

k=[1,3,10]
for i in k:
    knn = neighbors.KNeighborsRegressor(i)
    model_knn=knn.fit(X, y)
    y_hat_knn=model_knn.predict(T)
    plt.figure()
    plt.subplots(1,1)
    plt.scatter(x=X, y=y, facecolor='None', edgecolor='k', alpha=0.3, label='data')
    plt.plot(T, y_hat_knn, color='navy', label='prediction')
    plt.show();
<Figure size 432x288 with 0 Axes>
<Figure size 432x288 with 0 Axes>
<Figure size 432x288 with 0 Axes>

Les inconvénients

Premier inconvénient

la valeur prédite est une fonction constante (non lisse) des prédicteurs. Pour de nombreux phénomènes, il est raisonnable de penser que la réponse attendue devrait varier de façon régulière en fonction des prédicteurs.

Deuxième inconvénient

La méthode KNN est notoirement peu performante dans certains problèmes de grande dimension : c'est-à-dire lorsque $p := dim(\mathbf{x})$ est grand. En effet, considérons le cas de $p$ prédicteurs $X = X^{(1)}, \dots, X^{(p)}$ qui sont tous des variables aléatoires Uniform $[0, 1]$ indépendantes. Supposons que l'on voudrait construire un hypercube de dimension $p$ qui couvre 100 % du volume total de l'hypercube $[0,1]^p$ pour former le voisinage.

La longueur du bord de l'hypercube que nous devons considérer est $s=r^{1/p}$ puisque $(r^{1/p})^p = r$.

Pour obtenir environ $1%$ des observations en $1$ dimension, il suffit de considérer les observations dont les prédicteurs $X = X^{(1)}, \dots, X^{(p)}$ sont à $0,01$. Le voisinage (les points les plus proches) ne comprend que les observations dont les prédicteurs sont tous très proches de l'observation que nous essayons de prédire.

Donc, pour obtenir $1%$ des observations en $p=10$ dimensions, il faut considérer les observations dont les prédicteurs vont jusqu'à $0,613$ dans chaque dimension. Cela représente plus de la moitié de la fourchette de chaque prédicteur. Les poins voisins ne sont plus proches localement. En effet, certaines observations dans ce voisinage prédits peuvent avoir des valeurs très différentes pour certains des prédicteurs.

image.png

Fonction de cout

En l'absence d'une structure stochastique permettant de construire un test statistique formel, on peut se baser sur un critère permettant d'évaluer la qualité de l'ajustement.

On définit une fonction de cout (ou de perte) comme étant une fonction à valeurs réelles telles que $c(x, y) \geq 0$ et $c(x,x) = 0$. Le choix de cette fonction dépend généralement du type de problème considéré.

Ainsi, le risque d'un prédicteur $\hat{f}$ pour la fonction inconnue $f$ est

$$ \mathcal{R}(\widehat{f}) = \mathbb{E}\Big[{c\left(Y, \widehat{f}(\mathbf{X})\right)}\Big], $$
où $Y = f(\mathbf{X}) + \epsilon$. 

Risque quadratique

Dans un contexte de régression, on travaille généralement avec une fonction de cout quadratique donnée par

\begin{align*} c(x,y) &= (y-x)^2. \end{align*}

On obtient alors la fonction de risque

$$ \mathcal{R}(\widehat{f}) = \mathbb{E}\Big[{\left(Y - \widehat{f}(\mathbf{X})\right)^2}\Big], $$

où $\widehat{f}(\mathbf{X})$ représente une prédiction.

On obtient un risque quadratique ou risque des moindres carrés.

La distribution exacte de $Y$ n'est pas connue, il n'est donc pas possible de calculer la fonction de risque. On cherchera plutôt à l'approximer par une fonction de risque empirique:

Risque empirique

\begin{align*} \widehat{\mathcal{R}}(\widehat{f}) &= \frac{1}{n}\sum_{i=1}^n c\left(\widehat{f}(\mathbf{x}_i), y_i\right), \end{align*}

où $\{\mathbf{x}_i, y_i\}_{i=1, \ldots, n}$ est un échantillon aléatoire et $\widehat{f}(\mathbf{x}_i) \to \tilde{y}_i$ représente une prédiction obtenue pour l'observation $i$.

Erreur quadratique moyenne

Dans un contexte de régression, on travaille généralement avec l'erreur quadratique moyenne, ou Mean Squared Error (MSE), donnée par

\begin{align*} \text{MSE} &= \frac{1}{n}\sum_{i=1}^n \left(y_i - \widehat{f}(\mathbf{x}_i)\right)^2. \end{align*}

Plus petite est l'erreur quadratique moyenne, meilleur l'ajustement du modèle est.

Base d’entrainement et surapprentissage

  • Dans la formule précédente, l'échantillon utilisé pour calculer l'erreur quadratique moyenne est le même que celui utilisé pour ajuster le modèle $\to$ erreur d'entrainement (in-sample MSE).
  • Cette façon de procéder va favoriser le modèle le plus flexible, car il s'agit du modèle qui s'adaptera au maximum aux données présentes dans l'échantillon.
  • Ainsi, le modèle aura tendance à capturer beaucoup de bruit et à sur-ajuster les données.

Base d’entrainement et base de validation

  • Très souvent, il y a peu d'intérêt à ce que le modèle s'ajuste bien aux données de l'échantillon.
  • On est surtout intéressé à la capacité de généralisation du modèle, c'est-à-dire à sa capacité à bien performer sur des données qu'il n'a jamais vues.
  • Pour éviter ce problème de surapprentissage, on va diviser aléatoirement la base de données initiale en une base d'entrainement et une base de validation.
  • La base d'entrainement, de taille $(n-m) < n$, sera utilisée pour estimer les paramètres du modèle.
  • La base de validation, de taille $m$, sera utilisée pour sélectionner le modèle en minimisant une erreur quadratique moyenne de validation (out-of-sample MSE)
\begin{align*} \text{vMSE} &= \frac{1}{m}\sum_{i=1}^m \left(y_i - \widehat{f}(\mathbf{x}_i)\right)^2. \end{align*}

Décomposition de l’erreur quadratique moyenne$^1$

Petit rappel*:

\begin{align*} \mathbb{E}\Big[{\left(Y - \widehat{f}(\mathbf{X})\right)^2}\Big] &= \mathbb{E}\Big[{\left(f(\mathbf{X}) + \epsilon - \widehat{f}(\mathbf{X})\right)^2}\Big]\\ &= \mathbb{E}\Big[{\left(f(\mathbf{X}) - \widehat{f}(\mathbf{X})\right)^2}\Big] + \mathbb{E}\big[{\epsilon^2}\big]\\ &\phantom{=} +2\mathbb{E}\Big[{\epsilon\left(f(\mathbf{X}) - \widehat{f}(\mathbf{X})\right)}\Big]\\ &= \mathbb{E}\Big[{\left(f(\mathbf{X}) - \widehat{f}(\mathbf{X})\right)^2}\Big] + \mathbb{E}\big[{\epsilon^2}\big]\\ &= \mathbb{E}\Big[{\left(f(\mathbf{X}) - \widehat{f}(\mathbf{X})\right)^2}\Big] + Var[{\epsilon}]\\ &= Var\Big[{\left(f(\mathbf{X}) - \widehat{f}(\mathbf{X})\right)}\Big] + \mathbb{E}\Big[{\left(f(\mathbf{X}) - \widehat{f}(\mathbf{X})\right)}\Big]^2 + Var[{\epsilon}]\\ &= Var\Big[{\widehat{f}(\mathbf{X})}\Big] + \mathbb{E}\Big[{\left(f(\mathbf{X}) - \widehat{f}(\mathbf{X})\right)}\Big]^2 + Var[{\epsilon}]. \end{align*}
  • On obtient ainsi une erreur quadratique moyenne qui comprend trois termes: la variance de l'estimateur, le biais au carré et l'erreur stochastique (irréductible).
  • Un bon modèle doit avoir simultanément une variance faible et un biais faible.
  • Un modèle trop flexible n'est pas approprié car sa variance est généralement trop élevée: il est trop sensible au bruit présent dans les données.
  • Un modèle peu flexible n'est pas approprié car son biais est généralement trop élevé: il n'arrive pas à capturer le comportement de la fonction $f$ inconnue.
  • $\to$ compromis entre variance et biais.
  • 1: Notes cours de Pigeon, M. (2019).

k-Validation croisée

  1. On divise la base de données en $k$ sous-ensembles, chacun de taille $n_i$, $i = 1, \ldots, k$ et $\sum_{i=1}^k n_i = n$;
  2. Pour l'itération $j$, $j = 1, \ldots, k$:
    • 2a) On regroupe tous les sous-ensembles sauf le sous-ensemble $j$: on obtient une base d'entrainement de taille $n-n_j$;
    • 2b) utilise cette base d'entrainement pour estimer les paramètres du modèle;
    • 2c) calcule le vMSE$_j$ en utilisant les données du sous-ensemble $j$;
  3. Le MSE total est alors \begin{align*} \text{tMSE} &= \frac{1}{n}\sum_{j=1}^k n_j\text{vMSE}_j. \end{align*}
  • En pratique, on pose généralement $k = 10$ (ten-fold cross validation) ou $k = n$ (leave-one-out cross validation).
  • Lorsque le modèle optimal est sélectionné, on cherche à estimer l'erreur quadratique de prédiction, c'est-à-dire \begin{align*} \mathbb{E}\Big[{\left(Y^* - \widehat{f}(\mathbf{X^*})\right)^2}\Big], \end{align*} où $(Y^*; \mathbf{X^*})$ est une nouvelle observation.
  • Il faut alors faire attention car le tMSE généralement sous-estime cette valeur.
  • Pour contourner ce problème, si la base de données est de taille suffisante, on peut garder une portion des données pour constituer une base de test.
  • On estime alors l'erreur quadratique de prédiction comme étant \begin{align*} \widehat{\mathbb{E}\Big[{\left(Y^* - \widehat{f}(\mathbf{X^*})\right)^2}}\Big] &= \frac{1}{n_{\text{test}}} \sum_{i=1}^{n_{\text{test}}} \left(y_i^* - \widehat{f}(\mathbf{x^*}_i)\right)^2. \end{align*}

  • $y_{i}^*$ est la jième observation de l'ensemble de test,
  • $\widehat{f}(\mathbf{x^*}_i)$ est la prédiction de l'observation du jème test fournie par le test optimal j modèle sélectionné par validation croisée.

image.png

Exercice,

Sur un graphique de nuage de points, montrer le MSE calculé (axe des y) par rapport au nombre de K dans KNN (1-30), avec:

  1. Un ajustement sur tout l'échantillon
  2. Un ajustement sur 70% des données