Intuition

Les \(k\) plus proches voisins est un des algorithmes de apprentissage automatique les plus simples. Il est typiquement utiliser pour la classification.

Soit un nouveau échantillon à classer \(\mathbf{p}\). L’intuition est de sélectionner les \(k \in \mathbb{Z}^+\) exemples d’entraînement les plus proche de \(\mathbf{p}\) et de retourner la classe moyenne des \(k\) exemples.

Dans l’exemple ci-dessous, \(\mathbf{p} = (5.05, 2.62)\). Si \(k = 3\), les \(k\) plus proches voisins sont deux versicolore et un virginica. La décision pour la classe sera est versicolore.

L’algorithme peut donner des frontières de décisions non linéaires.

Soit le cas où les \(\mathbf{x}_i \in \mathbb{R}^3\). L’intuition visuelle 3D est la même qu’en 2D. Par contre, pour des dimensions plus élevées, la visualisation est dificile. Tout de même, il est possible d’imaginer des points dans un hyperespace où certains points sont plus proches que d’autres. Calculer la distance entre points de dimensions \(n\) est simple.

Nombre impair pour \(k\)

En classification binaire (où il n’y a que deux classes), si \(k\) est pair, il existe une possibilité d’égalité, c’est-à-dire que les \(k\) plus proches voisins pourraient inclure un nombre égal de points des deux classes. En choisissant un nombre impair pour \(k\), il y aura toujours une classe majoritaire parmi les voisins, évitant une égalité dans la décision.

Les mesures de distances

Ils existent plusieurs mesures autres qu’euclédienne. Selon le contexte, une méthode peut être plus adaptée qu’une autre. Quelques autres méthodes peuvent être vue ici.

Calculer la distance entre chaque point

Soit \(X\) le vecteur contenant le vecteur de caractéristique de chaque exemple dans \(D\).

\[ \begin{align} X &= ((x_{0,0},\ x_{0,1},\ ...,\ x_{0,n-1}), (x_{1,0},\ x_{1,1},\ ...,\ x_{1,n-1}), \ ..., (x_{m,0},\ x_{m-1,1},\ ...,\ x_{m-1,n-1}))\\ &= (\mathbf{x}_0,\ \mathbf{x}_1,\ ...,\ \mathbf{x}_{m-1}) \end{align} \]

L’algorithme pour calculer itérativement la distance entre un point et plusieurs autres est simple :

# soit un point p et un ensemble de points X
1. distances = []
2. distances[i] = distance(p, X[i]) pour chaque Xi 

Il est possible de calculer la distance entre un vecteur \(\mathbf{p}\) et plusieurs vecteurs \(\mathbf{x}_i\) à l’aide d’opérations d’algèbre linéaire.

Car chaque exemples dans le jeu de données possède le même nombre \(n\) de caractéristiques, \(X\) peut être une matrice :

\[X \in \mathbb{R}^{m \times n} = \begin{bmatrix} \mathbf{x}_0 \\ \mathbf{x}_1 \\ \vdots \\ \mathbf{x}_{m-1}\end{bmatrix} = \begin{bmatrix} x_{0,0} & x_{0,1} & \dots & x_{0,n-1} \\ x_{1,0} & x_{1,1} & \dots & x_{1,n-1} \\ \vdots & \vdots & \ddots & \vdots \\ x_{m-1,0} & x_{m-1,1} & \dots & x_{m-1,n-1} \end{bmatrix}\]

La compléxité de l’algorithme itérative est \(O(m)\) où \(m\) est le nombre de points dans \(X\).

Il est possible de calculer la distance entre un vecteur \(\mathbf{p}\) et plusieurs vecteurs \(\mathbf{x}_i\) à l’aide de matrices. Il suffit de broadcast \(\mathbf{p}\) pour effectuer une soustraction entre deux matrices.

\[P = \begin{bmatrix} \mathbf{p} \\ \mathbf{p} \\ \vdots \\ \mathbf{p}\end{bmatrix},\\ P - X = \begin{bmatrix} \mathbf{p} \\ \mathbf{p} \\ \vdots \\ \mathbf{p}\end{bmatrix} - \begin{bmatrix} \mathbf{x}_0 \\ \mathbf{x}_1 \\ \vdots \\ \mathbf{x}_{m-1}\end{bmatrix} = \begin{bmatrix} \mathbf{p} - \mathbf{x}_0 \\ \mathbf{p} - \mathbf{x}_1 \\ \vdots \\ \mathbf{p} - \mathbf{x}_{m-1} \end{bmatrix} \]

La soustraction entre matrice est habituellement faite en parallèle (chaque soustraction est indépendante !). Ceci est vrai pour plusieurs opérations d’algèbre linéaire, incluant la multiplication matricielle. La complexité de ces opérations est aussi \(O(m)\), mais ils sont considérablement plus rapide qu’utiliser une boucle for.

Après la soustraction, il est possible d’effectuer le produit scalaire de \((\mathbf{p} - \mathbf{x}_i) \cdot (\mathbf{p} - \mathbf{x}_i)\) pour \(\ 0 \le i < m\) et prendre la racine carrée de chaque résultat pour obtenir les distances.

\[distances =\begin{bmatrix} \sqrt{(\mathbf{p} - \mathbf{x}_0) \cdot (\mathbf{p} - \mathbf{x}_0)}\\ \sqrt{(\mathbf{p} - \mathbf{x}_1) \cdot (\mathbf{p} - \mathbf{x}_1)} \\ \vdots \\ \sqrt{(\mathbf{p} - \mathbf{x}_{m-1}) \cdot (\mathbf{p} - \mathbf{x}_{m-1})} \end{bmatrix}\]

Calculer les distances peut aussi être exprimé purement mathématiquement :

\[ \quad A = \begin{bmatrix} \mathbf{p} - \mathbf{x}_0 \\ \mathbf{p} - \mathbf{x}_1 \\ \vdots \\ \mathbf{p} - \mathbf{x}_{m-1} \end{bmatrix} \odot \begin{bmatrix} \mathbf{p} - \mathbf{x}_0 \\ \mathbf{p} - \mathbf{x}_1 \\ \vdots \\ \mathbf{p} - \mathbf{x}_{m-1} \end{bmatrix} = \begin{bmatrix} (p_{,0} - x_{0,0})^2 ,\ (p_{,1} - x_{0,1})^2,\ \ldots \\ (p_{,0} - x_{1,0})^2 ,\ (p_{,1} - x_{1,1})^2,\ \ldots \\ \vdots \\ (p_{,0} - x_{m-1,0})^2,\ (p_{,1} - x_{m-1,1})^2,\ \ldots \\ \end{bmatrix} \] \[ \begin{eqnarray} \quad \mathbf{d} = A\mathbf{1} &=& \begin{bmatrix} (p_{,0} - x_{0,0})^2 ,\ (p_{,1} - x_{0,1})^2,\ \ldots \\ (p_{,0} - x_{1,0})^2 ,\ (p_{,1} - x_{1,1})^2,\ \ldots \\ \vdots \\ (p_{,0} - x_{m-1,0})^2,\ (p_{,1} - x_{m-1,1})^2,\ \ldots \\ \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} \\ &=& \begin{bmatrix} (p_{,0} - x_{0,0})^2 + (p_{,1} - x_{0,1})^2,\ \ldots \\ (p_{,0} - x_{1,0})^2 + (p_{,1} - x_{1,1})^2,\ \ldots \\ \vdots \\ (p_{,0} - x_{m-1,0})^2 + (p_{,1} - x_{m-1,1})^2,\ \ldots \\ \end{bmatrix}\\ &=& \begin{bmatrix} (\mathbf{p} - \mathbf{x}_0) \cdot (\mathbf{p} - \mathbf{x}_0)\\ (\mathbf{p} - \mathbf{x}_1) \cdot (\mathbf{p} - \mathbf{x}_1) \\ \vdots \\ (\mathbf{p} - \mathbf{x}_{m-1}) \cdot (\mathbf{p} - \mathbf{x}_{m-1}) \end{bmatrix} \end{eqnarray} \] \[ distances = \sqrt{\mathbf{d}} = \begin{bmatrix} \sqrt{(\mathbf{p} - \mathbf{x}_0) \cdot (\mathbf{p} - \mathbf{x}_0)}\\ \sqrt{(\mathbf{p} - \mathbf{x}_1) \cdot (\mathbf{p} - \mathbf{x}_1)} \\ \vdots \\ \sqrt{(\mathbf{p} - \mathbf{x}_{m-1}) \cdot (\mathbf{p} - \mathbf{x}_{m-1})} \end{bmatrix} \]

Le module linalg

numpy contient un module linalg. Ce module possède plusieurs fonctions d’algèbre linéaire avec des implémentations exploitant le parallelisme.

La fonction np.linalg.norm(.) peut calculer la norme de chaque ligne dans une matrice en donnant le paramètre axis=1. Par exemple, distances = np.linalg.norm(A, axis=1).

Solution

def knn(p, X, y, k):
    distances = np.linalg.norm(p - X, axis=1)
    d_sorted_idx = np.argsort(d)
    nn_idx = d_sorted_idx[0:k]
    nn_ys = y[nn_idx]
    unique, counts = np.unique(nn_ys, return_counts=True)
    y_hat = unique[np.argmax(counts)]

    return y_hat

Comment pourriez-vous optimiser la vitesse de calcul pour votre modèle KNN ? Éliminer la racine carrée ! Elle ne change pas l’ordre des voisins triés.