K-Nearest Neighbours (KNN) : qu'est-ce que c'est et comment il est utilisé dans l'apprentissage automatique

Les K-plus proches voisins (KNN) sont une technique fondamentale de l'apprentissage automatique (ML). Ce guide vous aidera à comprendre KNN, son fonctionnement, ainsi que ses applications, avantages et défis.

Table des matières

Qu'est-ce que l'algorithme des k-voisins les plus proches ?

Comment fonctionne KNN ?

Différence entre les k voisins les plus proches et d'autres algorithmes

Comment KNN est-il utilisé dans l’apprentissage automatique ?

Applications du KNN

Avantages de KNN

Inconvénients du KNN

Qu'est-ce que l'algorithme des k-voisins les plus proches ?

L'algorithme des k-plus proches voisins (KNN) est une technique d'apprentissage supervisé utilisée à la fois pour la classification et la régression. KNN détermine l'étiquette (classification) ou la valeur prédite (régression) d'un point de données donné en évaluant les points de données proches dans l'ensemble de données.

Comment fonctionne KNN ?

KNN repose sur le principe selon lequel les points de données spatialement proches les uns des autres dans un ensemble de données ont tendance à avoir des valeurs similaires ou à appartenir à des catégories similaires. KNN utilise cette idée simple mais puissante pour classer un nouveau point de données en recherchant un nombre prédéfini (l'hyperparamètre k) de points de données voisins dans l'ensemble de données d'entraînement étiqueté. Cette valeur, k, est l'un des hyperparamètres KNN, qui sont des variables de configuration prédéfinies que les praticiens du ML utilisent pour contrôler la manière dont l'algorithme apprend.

Ensuite, l'algorithme détermine laquelle des valeurs voisines est la plus proche du nouveau point de données et lui attribue la même étiquette ou catégorie que ses voisins. La valeur choisie de k affecte les performances du modèle. Des valeurs plus petites augmentent la sensibilité au bruit, tandis que des valeurs plus grandes augmentent la robustesse mais peuvent faire manquer les modèles locaux au KNN.

La proximité, ou la distance, entre les points de données est calculée à l'aide de métriques initialement développées pour mesurer la similarité des points dans un espace mathématique. Les mesures courantes incluent la distance euclidienne, la distance de Manhattan et la distance de Minkowski. Les performances de KNN sont affectées par la métrique choisie, et différentes métriques fonctionnent mieux avec différents types et tailles de données.

Par exemple, le nombre de dimensions dans les données, qui sont des attributs individuels décrivant chaque point de données, peut affecter les performances des métriques. Quelle que soit la métrique de distance choisie, l'objectif est de catégoriser ou de prédire un nouveau point de données en fonction de sa distance par rapport à d'autres points de données.

• La distance euclidienneest la distance le long d’une ligne droite entre deux points de l’espace et constitue la métrique la plus couramment utilisée. Il est préférable de l'utiliser pour les données comportant un nombre inférieur de dimensions et sans valeurs aberrantes significatives.
• La distance de Manhattanest la somme des différences absolues entre les coordonnées des points de données mesurés. Cette métrique est utile lorsque les données sont de grande dimension ou lorsque les points de données forment une structure en forme de grille.
• La distance de Minkowskiest une métrique réglable qui peut agir comme la distance euclidienne ou la distance de Manhattan en fonction de la valeur d'un paramètre réglable. L'ajustement de ce paramètre contrôle la façon dont la distance est calculée, ce qui est utile pour adapter KNN à différents types de données.

D'autres mesures moins courantes incluent les distances de Chebyshev, Hamming et Mahalanobis. Ces métriques sont plus spécialisées et conviennent à des types de données et à des distributions particuliers. Par exemple, la distance de Mahalanobis mesure la distance d'un point à une distribution de points, en tenant compte des relations entre variables. En tant que telle, la distance de Mahalanobis est bien adaptée pour travailler avec des données où les entités utilisent différentes échelles.

KNN est souvent qualifié d’algorithme d’apprentissage « paresseux » car il ne nécessite pas de formation, contrairement à de nombreux autres algorithmes. Au lieu de cela, KNN stocke les données et les utilise pour prendre des décisions uniquement lorsque de nouveaux points de données nécessitent une régression ou une classification. Cependant, cela signifie que les prédictions nécessitent souvent des calculs élevés puisque l’ensemble des données est évalué pour chaque prédiction. ∫

Différence entre les k voisins les plus proches et d'autres algorithmes

KNN fait partie d'une famille plus large de techniques de ML supervisées orientées vers la classification et la régression, qui comprend des arbres de décision/forêts aléatoires, la régression logistique et des machines à vecteurs de support (SVM). Cependant, KNN diffère de ces techniques en raison de sa simplicité et de son approche directe du traitement des données, entre autres facteurs.

Arbres de décision et forêts aléatoires

Comme KNN, les arbres de décision et les forêts aléatoires sont utilisés pour la classification et la régression. Cependant, ces algorithmes utilisent des règles explicites apprises à partir des données lors de l'entraînement, contrairement à l'approche basée sur la distance de KNN. Les arbres de décision et les forêts aléatoires ont tendance à avoir des vitesses de prédiction plus rapides car ils ont des règles pré-entraînées. Cela signifie qu'ils sont mieux adaptés que KNN aux tâches de prédiction en temps réel et à la gestion de grands ensembles de données.

Régression logistique

La régression logistique suppose que les données sont distribuées linéairement et les classe à l'aide d'une ligne droite ou d'un hyperplan (une limite séparant les points de données dans des espaces de dimension supérieure) pour séparer les données en catégories. KNN, en revanche, ne suppose pas de distribution de données particulière. En tant que tel, KNN peut s'adapter plus facilement aux données complexes ou non linéaires, tandis que la régression logistique est mieux utilisée avec des données linéaires.

Machines vectorielles de support

Au lieu d'examiner les distances entre les points comme KNN, les machines à vecteurs de support (SVM) se concentrent sur la création d'une ligne de démarcation claire entre les groupes de points de données, souvent dans le but de rendre l'écart entre eux aussi large que possible. SVM est idéal pour gérer des ensembles de données complexes comportant de nombreuses fonctionnalités ou lorsqu'une séparation claire entre les groupes de points de données est nécessaire. En comparaison, KNN est plus simple à utiliser et à comprendre, mais ne fonctionne pas aussi bien sur de grands ensembles de données.

Comment KNN est-il utilisé dans l’apprentissage automatique ?

De nombreux algorithmes ML ne peuvent gérer qu’un seul type de tâche. KNN se distingue par sa capacité à gérer non pas un mais deux cas d’usage courants : la classification et la régression.

Classification

KNN classe les points de données en utilisant une métrique de distance pour déterminer les k voisins les plus proches et en attribuant une étiquette au nouveau point de données en fonction des étiquettes des voisins. Les cas d'utilisation courants de la classification KNN incluent la classification du spam par courrier électronique, le regroupement des clients en catégories en fonction de l'historique des achats et la reconnaissance des numéros manuscrits.

Régression

KNN effectue une régression en estimant la valeur d'un point de données sur la base de la moyenne (ou moyenne pondérée) de ses k voisins les plus proches. Par exemple, KNN peut prédire les prix des logements en fonction de propriétés similaires dans le quartier, les cours des actions en fonction de données historiques pour des actions similaires ou la température en fonction de données météorologiques historiques dans des endroits similaires.

Applications de l'algorithme KNN en ML

En raison de sa relative simplicité et de sa capacité à effectuer à la fois une classification et une régression, KNN a un large éventail d'applications. Ceux-ci incluent la reconnaissance d’images, les systèmes de recommandation et la classification de texte.

Reconnaissance d'images

La reconnaissance d'images est l'une des applications les plus courantes de KNN en raison de ses capacités de classification. KNN effectue la reconnaissance d'image en comparant les caractéristiques de l'image inconnue, telles que les couleurs et les formes, aux caractéristiques d'un ensemble de données d'image étiquetées. Cela rend KNN utile dans des domaines comme la vision par ordinateur.

Systèmes de recommandation

KNN peut recommander des produits ou du contenu aux utilisateurs en comparant leurs données de préférences aux données d'utilisateurs similaires. Par exemple, si un utilisateur a écouté plusieurs chansons de jazz classiques, KNN peut trouver des utilisateurs ayant des préférences similaires et recommander des chansons qu'ils ont appréciées. En tant que tel, KNN peut aider à personnaliser l'expérience utilisateur en recommandant des produits ou du contenu basés sur des données similaires.

Classement du texte

La classification de texte cherche à classer un texte non catégorisé en fonction de sa similitude avec un texte pré-catégorisé. La capacité de KNN à évaluer la proximité des modèles de mots en fait un outil efficace pour ce cas d'utilisation. La classification de texte est particulièrement utile pour des tâches telles que l'analyse des sentiments, où les textes sont classés comme positifs, négatifs ou neutres, ou pour déterminer la catégorie d'un article d'actualité.

Avantages de l'algorithme KNN en ML

KNN présente plusieurs avantages notables, notamment sa simplicité, sa polyvalence et l'absence de phase de formation.

Simplicité

Comparé à de nombreux autres algorithmes ML, KNN est facile à comprendre et à utiliser. La logique derrière KNN est intuitive : elle classe ou prédit (régression) de nouveaux points de données en fonction des valeurs des points de données proches, ce qui en fait un choix populaire pour les praticiens du ML, en particulier les débutants. De plus, outre le choix d'une valeur pour k, un réglage minimal des hyperparamètres est requis pour utiliser KNN.

Versatilité

KNN peut être utilisé à la fois pour des tâches de classification et de régression, ce qui signifie qu'il peut être appliqué à un large éventail de problèmes et de types de données, de la reconnaissance d'images à la prédiction de valeurs numériques. Contrairement aux algorithmes spécialisés limités à un seul type de tâche, KNN peut être appliqué à n’importe quel ensemble de données étiqueté et structuré de manière appropriée.

Phase de formation explicite

De nombreux modèles de ML nécessitent une phase de formation gourmande en temps et en ressources avant de devenir utiles. KNN, en revanche, stocke simplement les données d'entraînement et les utilise directement au moment de la prédiction. En tant que tel, KNN peut être mis à jour avec de nouvelles données, immédiatement disponibles pour être utilisées dans la prédiction. Cela rend KNN particulièrement attrayant pour les petits ensembles de données.

Inconvénients de l'algorithme KNN en ML

Malgré ses atouts, KNN présente également plusieurs défis. Ceux-ci incluent des coûts de calcul et de mémoire élevés, une sensibilité au bruit et aux fonctionnalités non pertinentes, ainsi que la « malédiction de la dimensionnalité ».

Coût informatique de la prédiction

Étant donné que KNN calcule la distance entre un nouveau point de données et chaque point de données de son ensemble de données d'entraînement global à chaque fois qu'il effectue une prédiction, le coût de calcul de la prédiction augmente rapidement à mesure que l'ensemble de données grandit. Cela peut entraîner des prédictions lentes lorsque l'ensemble de données est volumineux ou que le KNN est exécuté sur un matériel insuffisant.

Malédiction de la dimensionnalité

KNN souffre de ce qu’on appelle la « malédiction de la dimensionnalité », qui limite sa capacité à gérer des données de grande dimension. À mesure que le nombre d’entités dans un ensemble de données augmente, la plupart des points de données deviennent clairsemés et presque équidistants les uns des autres. En tant que telles, les mesures de distance deviennent moins utiles, ce qui rend difficile pour KNN de trouver des voisins dans des ensembles de données de grande dimension réellement proches.

gourmand en mémoire

Une caractéristique unique de KNN est qu'il stocke l'intégralité de l'ensemble de données d'entraînement en mémoire pour une utilisation au moment de la prédiction. Lorsqu’il s’agit d’une mémoire limitée ou de grands ensembles de données, cela peut s’avérer problématique et peu pratique. D'autres algorithmes de ML évitent ce défi en condensant et en distillant les données d'entraînement en fonctionnalités apprises grâce à l'entraînement du modèle et à l'optimisation des paramètres. KNN, en revanche, doit conserver chaque point de données, ce qui signifie que la mémoire augmente linéairement avec la taille de l'ensemble de données d'entraînement.

Sensibilité au bruit et fonctionnalités non pertinentes

La puissance de KNN réside dans son calcul de distance simple et intuitif. Cependant, cela signifie également que des caractéristiques ou du bruit sans importance peuvent donner lieu à des calculs de distance trompeurs, affectant négativement la précision des prévisions. En tant que telles, les techniques de sélection de caractéristiques ou de réduction de dimensionnalité, comme l'analyse en composantes principales (ACP), sont souvent utilisées avec KNN pour garantir que les caractéristiques importantes ont le plus d'influence sur la prédiction.