Plus Proches Voisins (PPV)
- Introduite par
- Cover, T.M. & Hart, P.E.
- Année
- 1967
- Type
- Instance-based (non-parametric) learning
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
L'algorithme des plus proches voisins (PPV), formalisé par Cover et Hart en 1967, est une méthode non paramétrique basée sur les instances qui classe ou prédit une nouvelle observation en examinant les k exemples les plus proches dans les données d'entraînement.
Pour la classification, il prend un vote majoritaire parmi ces voisins ; pour la régression, il fait la moyenne de leurs valeurs.
L’intuition derrière la méthode
L'idée est simple : des entrées similaires ont tendance à avoir des sorties similaires. Pour étiqueter un nouveau point, le PPV trouve la poignée d'exemples d'entraînement qui lui sont les plus proches dans l'espace des caractéristiques et les laisse décider. Aucune équation n'est ajustée à l'avance — les données d'entraînement elles-mêmes constituent le modèle, et une prédiction n'est faite que lorsqu'un nouveau point arrive.
Histoire
La classification de motifs par plus proches voisins a reçu sa base statistique formelle de Thomas Cover et Peter Hart dans leur article de 1967 paru dans l'IEEE Transactions on Information Theory, qui analysait le taux d'erreur de la règle du plus proche voisin. Le PPV est devenu l'une des méthodes d'apprentissage basées sur les instances les plus anciennes et les plus durables et reste un classifieur de référence standard.
Quand l’utiliser
Utilisez le PPV pour la classification ou la prédiction sur des données tabulaires avec des caractéristiques continues, binaires ou ordinales et au moins environ 30 observations. Il ne suppose aucune distribution particulière, mais il exige que les caractéristiques soient normalisées et que le nombre de caractéristiques reste faible par rapport à la taille de l'échantillon (p beaucoup plus petit que n est préférable). Dans les échantillons de petite taille ou de grande dimension, la malédiction de la dimensionnalité domine — les distances entre voisins deviennent non informatives — et un modèle paramétrique tel que la régression logistique ou le Naive Bayes est le meilleur choix.
Limites et points d’attention
- Sensible à la mise à l'échelle des caractéristiques ; sans standardisation, les caractéristiques à grande échelle dominent la distance.
- Se dégrade rapidement en haute dimension (malédiction de la dimensionnalité), où les distances entre voisins perdent leur signification.
- Chaque prédiction nécessite de parcourir l'ensemble d'entraînement, ce qui est lent au moment de la prédiction sur de grandes données.
- Nécessite au moins une taille d'échantillon modérée ; dans les petits échantillons, les distances entre plus proches voisins ne sont pas significatives.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Conceptuellement simple et facile à expliquer : pas d'équation au moment de l'entraînement, les données sont le modèle.
- Non paramétrique — ne fait aucune hypothèse sur la distribution sous-jacente.
- Gère naturellement les problèmes multi-classes et les frontières de décision complexes et non linéaires.
- Fonctionne pour la classification et la régression avec la même idée de base.
Applications
- Classification de données tabulaires en deux catégories ou plus.
- Prédiction numérique (régression) en faisant la moyenne des exemples les plus proches.
- Une base de référence simple et interprétable avant d'essayer des modèles plus complexes.
- Reconnaissance de formes où la similarité avec des exemples connus motive la décision.
Comment ça marche
Comment ça marche
Pour une nouvelle observation, le PPV mesure sa distance par rapport à chaque exemple d'entraînement, généralement en utilisant la distance euclidienne sur l'ensemble des caractéristiques. Étant donné que la distance est sensible à l'échelle, les caractéristiques doivent d'abord être standardisées — sinon une variable mesurée sur une grande échelle numérique dominerait le calcul et fausserait la détermination des voisins considérés comme les plus proches.
Formule
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}Les k points d'entraînement ayant les plus petites distances par rapport à la nouvelle observation sont sélectionnés comme ses voisins. La valeur de k contrôle le degré de localité de la décision : un petit k suit les données de près mais est sensible au bruit, tandis qu'un k plus grand lisse la frontière. k doit être choisi par validation croisée (par exemple, la méthode du coude) plutôt que deviné.
Les voisins décident de la prédiction : pour la classification, le nouveau point prend la classe la plus fréquente parmi ses k voisins (un vote majoritaire), et pour la régression, il prend la moyenne de leurs valeurs. Cela rend la méthode facile à comprendre, mais chaque prédiction nécessite de parcourir l'ensemble d'entraînement.
Formule
\hat{y} = \text{mode/mean of the } k \text{ nearest neighbors}Pièges courants
- Omettre la standardisation des caractéristiques, de sorte qu'une variable à grande échelle contrôle silencieusement la distance.
- Choisir k à la main au lieu de le sélectionner par validation croisée.
- Appliquer le PPV avec de nombreuses caractéristiques et peu d'observations, où le rapport dimension/échantillon le rend inopérant.
- Ne rapporter que la précision au lieu de la précision, du rappel, du score F1 et d'une matrice de confusion.
Questions fréquentes
Comment choisir la valeur de k?
k doit être sélectionné par validation croisée plutôt que deviné — par exemple en essayant une plage de valeurs et en utilisant la méthode du coude pour trouver où l'erreur cesse de s'améliorer. Un petit k suit les données de près mais est sensible au bruit, tandis qu'un k plus grand lisse la frontière de décision.
Pourquoi dois-je standardiser les caractéristiques?
Le PPV décide qui est le « plus proche » en utilisant la distance, qui est sensible à l'échelle. Si une caractéristique est sur une échelle numérique beaucoup plus grande que les autres, elle domine la distance et fausse l'ensemble des voisins. La standardisation des caractéristiques (par exemple avec un StandardScaler) est nécessaire pour que chaque caractéristique contribue équitablement.
Pourquoi le PPV a-t-il des difficultés avec de nombreuses caractéristiques?
Dans les espaces de grande dimension, tous les points deviennent approximativement équidistants — la malédiction de la dimensionnalité — de sorte que les voisins « les plus proches » ne sont plus significativement proches. Les performances du PPV diminuent rapidement, et un modèle paramétrique tel que le Naive Bayes ou la régression logistique est généralement préférable. Maintenir p beaucoup plus petit que n aide.
Y a-t-il une étape d'entraînement?
Pas au sens habituel. Le PPV est basé sur les instances (paresseux) : il stocke simplement les données d'entraînement et effectue tout le travail au moment de la prédiction, lorsqu'il calcule les distances pour trouver les plus proches voisins d'un nouveau point.
Méthodes associées
Sources
Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.
Ouvrir la référence DOICopié.