k -algorithme des plus proches voisins - k-nearest neighbors algorithm

En statistique , l' algorithme des k -plus proches voisins ( k -NN ) est une méthode de classification non paramétrique développée pour la première fois par Evelyn Fix et Joseph Hodges en 1951, puis développée par Thomas Cover . Il est utilisé pour la classification et la régression . Dans les deux cas, l'entrée se compose des k exemples d'apprentissage les plus proches dans un ensemble de données . La sortie dépend de si k -NN est utilisé pour la classification ou la régression :

  • Dans la classification k-NN , la sortie est une appartenance à une classe. Un objet est classé par un vote de pluralité de ses voisins, l'objet étant affecté à la classe la plus courante parmi ses k voisins les plus proches ( k est un entier positif , typiquement petit). Si k  = 1, alors l'objet est simplement affecté à la classe de ce voisin le plus proche.
  • Dans la régression k-NN , la sortie est la valeur de propriété de l'objet. Cette valeur est la moyenne des valeurs de k plus proches voisins.

k -NN est un type de classification où la fonction n'est approchée que localement et tous les calculs sont différés jusqu'à l'évaluation de la fonction. Étant donné que cet algorithme repose sur la distance pour la classification, si les caractéristiques représentent différentes unités physiques ou se présentent à des échelles très différentes, la normalisation des données d'entraînement peut améliorer considérablement leur précision.

Tant pour la classification que pour la régression, une technique utile peut être d'attribuer des poids aux contributions des voisins, de sorte que les voisins les plus proches contribuent davantage à la moyenne que les plus éloignés. Par exemple, un schéma de pondération courant consiste à donner à chaque voisin un poids de 1/ d , où d est la distance au voisin.

Les voisins sont extraits d'un ensemble d'objets dont la classe (pour la classification k -NN) ou la valeur de propriété de l'objet (pour la régression k -NN) est connue. Cela peut être considéré comme l'ensemble d'apprentissage de l'algorithme, bien qu'aucune étape d'apprentissage explicite ne soit requise.

Une particularité de l' algorithme k- NN est qu'il est sensible à la structure locale des données.

Paramétrage statistique

Supposons que nous ayons des paires prenant des valeurs dans , où Y est l'étiquette de classe de X , de sorte que pour (et les distributions de probabilité ). Étant donné une norme sur et un point , soit une réorganisation des données d'apprentissage telle que .

Algorithme

Exemple de classification k -NN. L'échantillon d'essai (point vert) doit être classé soit en carrés bleus, soit en triangles rouges. Si k = 3 (cercle en trait plein), il est attribué aux triangles rouges car il y a 2 triangles et seulement 1 carré à l'intérieur du cercle intérieur. Si k = 5 (cercle en pointillés), il est attribué aux carrés bleus (3 carrés contre 2 triangles à l'intérieur du cercle extérieur).

Les exemples d'apprentissage sont des vecteurs dans un espace de caractéristiques multidimensionnel, chacun avec une étiquette de classe. La phase d'apprentissage de l'algorithme consiste uniquement à stocker les vecteurs de caractéristiques et les étiquettes de classe des échantillons d'apprentissage.

Dans la phase de classification, k est une constante définie par l'utilisateur et un vecteur non étiqueté (une requête ou un point de test) est classé en attribuant l'étiquette qui est la plus fréquente parmi les k échantillons d'apprentissage les plus proches de ce point de requête.

Une mesure de distance couramment utilisée pour les variables continues est la distance euclidienne . Pour les variables discrètes, comme pour la classification de texte, une autre métrique peut être utilisée, telle que la métrique de chevauchement (ou distance de Hamming ). Dans le contexte des données de microarray d'expression génique, par exemple, k- NN a été utilisé avec des coefficients de corrélation, tels que Pearson et Spearman, en tant que métrique. Souvent, la précision de classification de k- NN peut être considérablement améliorée si la métrique de distance est apprise avec des algorithmes spécialisés tels que Large Margin Nearest Neighbor ou Neighborhood Components Analysis .

Un inconvénient de la classification de base « vote majoritaire » se produit lorsque la distribution des classes est asymétrique. C'est-à-dire que les exemples d'une classe plus fréquente ont tendance à dominer la prédiction du nouvel exemple, car ils ont tendance à être communs parmi les k voisins les plus proches en raison de leur grand nombre. Une façon de surmonter ce problème est de pondérer la classification, en tenant compte de la distance du point de test à chacun de ses k voisins les plus proches. La classe (ou la valeur, dans les problèmes de régression) de chacun des k points les plus proches est multipliée par un poids proportionnel à l'inverse de la distance entre ce point et le point test. Une autre façon de surmonter l'asymétrie est l'abstraction dans la représentation des données. Par exemple, dans une carte auto-organisée (SOM), chaque nœud est un représentant (un centre) d'un groupe de points similaires, quelle que soit leur densité dans les données d'apprentissage d'origine. K -NN peut alors être appliqué au SOM.

Sélection des paramètres

Le meilleur choix de k dépend des données ; généralement, des valeurs plus élevées de k réduisent l'effet du bruit sur la classification, mais rendent les frontières entre les classes moins distinctes. Un bon k peut être sélectionné par diverses techniques heuristiques (voir optimisation des hyperparamètres ). Le cas particulier où la classe est prédite être la classe de l'échantillon d'apprentissage le plus proche (c'est-à-dire lorsque k = 1) est appelé l'algorithme du plus proche voisin.

La précision de l' algorithme k- NN peut être gravement dégradée par la présence de caractéristiques bruyantes ou non pertinentes, ou si les échelles de caractéristiques ne sont pas cohérentes avec leur importance. De nombreux efforts de recherche ont été consacrés à la sélection ou à la mise à l' échelle des caractéristiques afin d'améliorer la classification. Une approche particulièrement populaire est l'utilisation d' algorithmes évolutifs pour optimiser la mise à l'échelle des caractéristiques. Une autre approche populaire consiste à mettre à l'échelle les caractéristiques par l' information mutuelle des données d'apprentissage avec les classes d'apprentissage.

Dans les problèmes de classification binaire (à deux classes), il est utile de choisir k comme nombre impair car cela évite les votes à égalité. Une façon populaire de choisir le k empiriquement optimal dans ce cadre est la méthode du bootstrap.

Le classificateur à 1 voisin le plus proche

Le classificateur de type voisin le plus intuitif est le classificateur le plus proche qui affecte un point x à la classe de son voisin le plus proche dans l'espace des caractéristiques, c'est-à-dire .

À mesure que la taille de l'ensemble de données d'apprentissage approche l'infini, le classificateur le plus proche voisin garantit un taux d'erreur non pire que le double du taux d'erreur de Bayes (le taux d'erreur minimum réalisable compte tenu de la distribution des données).

Le classificateur du plus proche voisin pondéré

Le k -nearest classificateur voisin peut être considéré comme l' attribution du k plus proches voisins un poids et tous les autres 0 poids. Ceci peut être généralisé aux classificateurs de voisins les plus proches pondérés. C'est-à-dire, où le i ème voisin le plus proche se voit attribuer un poids , avec . Un résultat analogue sur la forte cohérence des classificateurs pondérés des plus proches voisins est également valable.

Soit le classificateur pondéré le plus proche avec des poids . Sous réserve de conditions de régularité sur les distributions de classes, l'excès de risque a le développement asymptotique suivant

pour les constantes et où et .

Le schéma de pondération optimal , qui équilibre les deux termes dans l'affichage ci-dessus, est donné comme suit : set ,

pour et
pour .

Avec des poids optimaux, le terme dominant dans l'expansion asymptotique de l'excès de risque est . Des résultats similaires sont vrais lors de l'utilisation d'un classificateur de voisin le plus proche en sac .

Propriétés

k -NN est un cas particulier d'un estimateur « ballon » à densité de noyau et à bande passante variable avec un noyau uniforme .

La version naïve de l'algorithme est facile à mettre en œuvre en calculant les distances entre l'exemple de test et tous les exemples stockés, mais elle est gourmande en calculs pour les grands ensembles d'apprentissage. En utilisant une approximation la plus proche voisin de recherche algorithme fait K- même NN informatiquement pour tractable grands ensembles de données. De nombreux algorithmes de recherche du plus proche voisin ont été proposés au fil des ans ; celles-ci visent généralement à réduire le nombre d'évaluations à distance réellement effectuées.

k- NN a de forts résultats de cohérence . Lorsque la quantité de données approche l'infini, l' algorithme k- NN à deux classes est garanti pour produire un taux d'erreur pas pire que le double du taux d'erreur de Bayes (le taux d'erreur minimum réalisable compte tenu de la distribution des données). Diverses améliorations de la vitesse k- NN sont possibles en utilisant des graphiques de proximité.

Pour la classification k- NN multi-classes , Cover et Hart (1967) prouvent un taux d'erreur de la borne supérieure de

où est le taux d'erreur de Bayes (qui est le taux d'erreur minimal possible), est le taux d'erreur k- NN, et M est le nombre de classes dans le problème. Car et au fur et à mesure que le taux d'erreur bayésien approche de zéro, cette limite se réduit à "pas plus de deux fois le taux d'erreur bayésien".

Taux d'erreur

Il existe de nombreux résultats sur le taux d'erreur des k classificateurs des plus proches voisins. Le classificateur du k-plus proche voisin est fortement (c'est-à-dire pour toute distribution conjointe sur ) cohérent à condition de diverger et de converger vers zéro en tant que .

Notons le classificateur k plus proche voisin basé sur un ensemble d'apprentissage de taille n . Sous certaines conditions de régularité, l' excès de risque donne l'expansion asymptotique suivante

pour certaines constantes et .

Le choix offre un compromis entre les deux termes de l'affichage ci-dessus, pour lequel l' erreur du plus proche voisin converge vers l'erreur de Bayes au taux optimal ( minimax ) .

Apprentissage métrique

Les performances de classification des K-plus proches voisins peuvent souvent être considérablement améliorées grâce à l' apprentissage ( supervisé ) des métriques. Les algorithmes populaires sont l' analyse des composantes de voisinage et le voisin le plus proche à large marge . Les algorithmes d'apprentissage de métriques supervisés utilisent les informations d'étiquette pour apprendre une nouvelle métrique ou pseudo-métrique .


Extraction de caractéristiques

Lorsque les données d'entrée d'un algorithme sont trop volumineuses pour être traitées et qu'elles sont suspectées d'être redondantes (par exemple, la même mesure en pieds et en mètres), les données d'entrée seront transformées en un ensemble de représentation réduit de caractéristiques (également appelé vecteur de caractéristiques ). La transformation des données d'entrée en un ensemble de caractéristiques s'appelle l' extraction de caractéristiques . Si les caractéristiques extraites sont soigneusement choisies, on s'attend à ce que l'ensemble de caractéristiques extraie les informations pertinentes des données d'entrée afin d'effectuer la tâche souhaitée en utilisant cette représentation réduite au lieu de l'entrée en taille réelle. L'extraction de caractéristiques est effectuée sur des données brutes avant d'appliquer l' algorithme k- NN sur les données transformées dans l' espace de caractéristiques .

Un exemple de pipeline de calcul de vision par ordinateur typique pour la reconnaissance faciale à l' aide de k- NN, y compris les étapes de pré-traitement d'extraction de caractéristiques et de réduction de dimension (généralement implémenté avec OpenCV ):

  1. Détection de visage Haar
  2. Analyse du suivi du décalage moyen
  3. Projection PCA ou Fisher LDA dans l'espace des caractéristiques, suivie d' une classification k -NN

Réduction dimensionnelle

Pour les données de grande dimension (par exemple, avec un nombre de dimensions supérieur à 10) , la réduction de dimension est généralement effectuée avant d'appliquer l' algorithme k- NN afin d'éviter les effets de la malédiction de la dimensionnalité .

La malédiction de la dimensionnalité dans le contexte k -NN signifie essentiellement que la distance euclidienne est inutile dans les dimensions élevées car tous les vecteurs sont presque équidistants du vecteur de requête de recherche (imaginez plusieurs points situés plus ou moins sur un cercle avec le point de requête au centre ; la distance entre la requête et tous les points de données dans l'espace de recherche est presque la même).

L'extraction de caractéristiques et la réduction de dimension peuvent être combinées en une seule étape en utilisant des techniques d' analyse en composantes principales (ACP), d'analyse discriminante linéaire (LDA) ou d' analyse de corrélation canonique (CCA) comme étape de pré-traitement, suivies d'un regroupement par k -NN sur la caractéristique vecteurs dans un espace de dimension réduite. Ce processus est également appelé intégration à faible dimension .

Pour les ensembles de données de très grande dimension (par exemple, lors d'une recherche de similarité sur des flux vidéo en direct, des données ADN ou des séries temporelles de grande dimension ), exécuter une recherche approximative rapide k -NN en utilisant un hachage sensible à la localité , des "projections aléatoires", des "croquis" ou d'autres techniques de recherche de similarité de grande dimension de la boîte à outils VLDB pourraient être la seule option possible.

Limite de décision

Les règles du plus proche voisin en effet calculent implicitement la limite de décision . Il est également possible de calculer explicitement la frontière de décision, et de le faire efficacement, de sorte que la complexité de calcul soit fonction de la complexité de la frontière.

Réduction de donnée

La réduction des données est l'un des problèmes les plus importants pour le travail avec des ensembles de données volumineux. Habituellement, seuls certains des points de données sont nécessaires pour une classification précise. Ces données sont appelées les prototypes et peuvent être trouvées comme suit :

  1. Sélectionnez les valeurs aberrantes de la classe , c'est-à-dire les données d'apprentissage qui sont classées de manière incorrecte par k -NN (pour un k donné )
  2. Séparez le reste des données en deux ensembles : (i) les prototypes qui sont utilisés pour les décisions de classification et (ii) les points absorbés qui peuvent être correctement classés par k -NN à l'aide de prototypes. Les points absorbés peuvent ensuite être retirés de l'ensemble d'entraînement.

Sélection des valeurs aberrantes de classe

Un exemple d'apprentissage entouré d'exemples d'autres classes est appelé une valeur aberrante de classe. Les causes des valeurs aberrantes de classe comprennent :

  • erreur aléatoire
  • exemples d'apprentissage insuffisants de cette classe (un exemple isolé apparaît à la place d'un cluster)
  • des fonctionnalités importantes manquantes (les classes sont séparées dans d'autres dimensions que nous ne connaissons pas)
  • trop d'exemples de formation d'autres classes (classes déséquilibrées) qui créent un arrière-plan « hostile » pour la petite classe donnée

Les valeurs aberrantes de classe avec k -NN produisent du bruit. Ils peuvent être détectés et séparés pour une analyse future. Étant donné deux nombres naturels, k>r>0 , un exemple d'apprentissage est appelé un (k,r) NN class-outlier si ses k voisins les plus proches incluent plus de r exemples d'autres classes.

Voisin le plus proche condensé pour la réduction des données

Le voisin le plus proche condensé (CNN, l' algorithme de Hart ) est un algorithme conçu pour réduire l'ensemble de données pour la classification k- NN. Il sélectionne l'ensemble de prototypes U à partir des données d'apprentissage, de sorte que 1NN avec U peut classer les exemples presque aussi précisément que 1NN le fait avec l'ensemble de données.

Calcul du ratio de frontière.
Trois types de points : prototypes, valeurs aberrantes de classe et points absorbés.

Étant donné un ensemble d'apprentissage X , CNN fonctionne de manière itérative :

  1. Balayez tous les éléments de X , à la recherche d'un élément x dont le prototype le plus proche de U a une étiquette différente de x .
  2. Supprimer x de X et l'ajouter à U
  3. Répétez l'analyse jusqu'à ce qu'aucun autre prototype ne soit ajouté à U .

Utilisez U au lieu de X pour la classification. Les exemples qui ne sont pas des prototypes sont appelés points « absorbés ».

Il est efficace de parcourir les exemples d'apprentissage dans l'ordre décroissant du ratio de bordure. Le rapport de frontière d'un exemple d'entraînement x est défini comme

un ( x ) = | | x'-y | |/| | xy | |

| | xy | | est la distance à l'exemple le plus proche y ayant une couleur différente de x , et | | x'-y | | est la distance de y à son exemple le plus proche x' avec la même étiquette que x .

Le rapport de frontière est dans l'intervalle [0,1] car | | x'-y | | ne dépasse jamais | | xy | | . Cet ordre privilégie les frontières des classes à inclure dans l'ensemble des prototypes U . Un point d'étiquette différente de x est appelé externe à x . Le calcul du taux de frontière est illustré par la figure de droite. Les points de données sont étiquetés par des couleurs : le point initial est x et son étiquette est rouge. Les points externes sont bleus et verts. Le point externe le plus proche de x est y . Le point rouge le plus proche de y est x' . Le rapport de frontière a ( x ) = | | x'-y | | / | | xy | | est l'attribut du point initial x .

Vous trouverez ci-dessous une illustration de CNN dans une série de chiffres. Il existe trois classes (rouge, vert et bleu). Fig. 1 : il y a initialement 60 points dans chaque classe. La figure 2 montre la carte de classification 1NN : chaque pixel est classé par 1NN en utilisant toutes les données. La figure 3 montre la carte de classification 5NN. Les zones blanches correspondent aux régions non classées, où le vote 5NN est à égalité (par exemple, s'il y a deux points verts, deux rouges et un bleu parmi les 5 voisins les plus proches). La figure 4 montre l'ensemble de données réduit. Les croisements sont les valeurs aberrantes de classe sélectionnées par la règle (3,2)NN (les trois voisins les plus proches de ces instances appartiennent à d'autres classes) ; les carrés sont les prototypes, et les cercles vides sont les points absorbés. Le coin inférieur gauche indique les nombres de valeurs aberrantes de classe, de prototypes et de points absorbés pour les trois classes. Le nombre de prototypes varie de 15 % à 20 % pour les différentes classes de cet exemple. La figure 5 montre que la carte de classification 1NN avec les prototypes est très similaire à celle avec l'ensemble de données initial. Les chiffres ont été produits à l'aide de l'applet Mirkes.

k -NN régression

Dans la régression k -NN, l' algorithme k -NN est utilisé pour estimer les variables continues. Un tel algorithme utilise une moyenne pondérée des k voisins les plus proches, pondérée par l'inverse de leur distance. Cet algorithme fonctionne comme suit :

  1. Calculez la distance euclidienne ou de Mahalanobis entre l'exemple de requête et les exemples étiquetés.
  2. Ordonnez les exemples étiquetés en augmentant la distance.
  3. Trouvez un nombre heuristiquement optimal k de voisins les plus proches, basé sur RMSE . Ceci est fait en utilisant la validation croisée.
  4. Calculez une moyenne pondérée par distance inverse avec les k voisins multivariés les plus proches.

k -NN valeur aberrante

La distance au k ème voisin le plus proche peut également être considérée comme une estimation de densité locale et est donc également un score aberrant populaire dans la détection d'anomalies . Plus la distance au k -NN est grande, plus la densité locale est faible, plus le point de requête est susceptible d'être aberrant. Bien qu'assez simple, ce modèle aberrant, associé à une autre méthode classique d'exploration de données, le facteur local aberrant , fonctionne assez bien également par rapport à des approches plus récentes et plus complexes, selon une analyse expérimentale à grande échelle.

Validation des résultats

Une matrice de confusion ou "matrice d'appariement" est souvent utilisée comme un outil pour valider l'exactitude de la classification k- NN. Des méthodes statistiques plus robustes telles que le test du rapport de vraisemblance peuvent également être appliquées.

Voir également

Les références

Lectures complémentaires