Scikit Learn - K-Nearest Neighbours (KNN)

Ce chapitre vous aidera à comprendre les méthodes de voisinage le plus proche dans Sklearn.

Les méthodes d'apprentissage basées sur les voisins sont des deux types, à savoir supervised et unsupervised. L'apprentissage supervisé basé sur les voisins peut être utilisé à la fois pour les problèmes prédictifs de classification et de régression, mais il est principalement utilisé pour les problèmes prédictifs de classification dans l'industrie.

Les méthodes d'apprentissage basées sur les voisins n'ont pas de phase de formation spécialisée et utilisent toutes les données pour la formation lors de la classification. Il ne suppose rien non plus sur les données sous-jacentes. C'est la raison pour laquelle ils sont de nature paresseuse et non paramétrique.

Le principe principal des méthodes du plus proche voisin est -

• Pour trouver un nombre prédéfini d'échantillons d'entraînement, à distance du nouveau point de données

• Prédisez l'étiquette à partir de ce nombre d'échantillons d'apprentissage.

Ici, le nombre d'échantillons peut être une constante définie par l'utilisateur comme dans l'apprentissage du voisin le plus proche K ou varier en fonction de la densité locale du point comme dans l'apprentissage du voisin basé sur le rayon.

Module sklearn.neighbors

Scikit-learn ont sklearn.neighborsmodule qui fournit des fonctionnalités pour les méthodes d'apprentissage basées sur les voisins non supervisés et supervisés. En entrée, les classes de ce module peuvent gérer des tableaux NumPy ouscipy.sparse matrices.

Types d'algorithmes

Les différents types d'algorithmes qui peuvent être utilisés dans l'implémentation des méthodes basées sur le voisinage sont les suivants:

Force brute

Le calcul par force brute des distances entre toutes les paires de points de l'ensemble de données fournit l'implémentation de recherche de voisin la plus naïve. Mathématiquement, pour N échantillons en dimensions D, l'approche par force brute est0[DN²]

Pour les petits échantillons de données, cet algorithme peut être très utile, mais il devient irréalisable au fur et à mesure que le nombre d'échantillons augmente. La recherche de voisins par force brute peut être activée en écrivant le mot-cléalgorithm=’brute’.

Arbre KD

L'une des structures de données arborescentes qui ont été inventées pour remédier aux inefficacités de calcul de l'approche par force brute est la structure de données arborescente KD. Fondamentalement, l'arbre KD est une structure arborescente binaire appelée arbre K-dimensionnel. Il partitionne récursivement l'espace des paramètres le long des axes de données en le divisant en régions orthographiques imbriquées dans lesquelles les points de données sont remplis.

Avantages

Voici quelques avantages de l'algorithme d'arborescence KD -

Construction is fast - Le partitionnement étant effectué uniquement le long des axes de données, la construction de l'arbre KD est très rapide.

Less distance computations- Cet algorithme prend très moins de calculs de distance pour déterminer le voisin le plus proche d'un point de requête. Il faut seulement[ ()] calculs de distance.

Désavantages

Fast for only low-dimensional neighbor searches- Il est très rapide pour les recherches de voisins de faible dimension (D <20) mais au fur et à mesure que D grandit il devient inefficace. Comme le partitionnement est effectué uniquement le long des axes de données,

Les recherches de voisins dans l'arborescence KD peuvent être activées en écrivant le mot-clé algorithm=’kd_tree’.

Arbre à boules

Comme nous savons que KD Tree est inefficace dans les dimensions supérieures, par conséquent, pour remédier à cette inefficacité de KD Tree, une structure de données d'arbre à billes a été développée. Mathématiquement, il divise récursivement les données, en nœuds définis par un centroïde C et un rayon r, de telle sorte que chaque point du nœud se trouve dans l'hyper-sphère définie par le centroïdeC et rayon r. Il utilise l'inégalité triangulaire, donnée ci-dessous, qui réduit le nombre de points candidats pour une recherche de voisin

$$ \ arrowvert X + Y \ arrowvert \ leq \ arrowvert X \ arrowvert + \ arrowvert Y \ arrowvert $$

Avantages

Voici quelques avantages de l'algorithme Ball Tree -

Efficient on highly structured data - Comme l'arbre à billes partitionne les données en une série d'hyper-sphères imbriquées, il est efficace sur des données hautement structurées.

Out-performs KD-tree - L'arbre à billes surpasse l'arbre KD en grandes dimensions car il a une géométrie sphérique des nœuds de l'arbre à billes.

Désavantages

Costly - Partitionner les données en une série d'hyper-sphères imbriquées rend sa construction très coûteuse.

Les recherches de voisins d'arbre à billes peuvent être activées en écrivant le mot-clé algorithm=’ball_tree’.

Choisir l'algorithme des voisins les plus proches

Le choix d'un algorithme optimal pour un ensemble de données donné dépend des facteurs suivants -

Nombre d'échantillons (N) et dimensionnalité (D)

Ce sont les facteurs les plus importants à prendre en compte lors du choix de l'algorithme du voisin le plus proche. C'est pour les raisons données ci-dessous -

• Le temps de requête de l'algorithme Brute Force augmente en tant que O [DN].

• Le temps de requête de l'algorithme d'arbre à billes augmente comme O [D log (N)].

• Le temps de requête de l'algorithme de l'arbre KD change avec D d'une manière étrange qui est très difficile à caractériser. Lorsque D <20, le coût est O [D log (N)] et cet algorithme est très efficace. En revanche, il est inefficace dans le cas où D> 20 car le coût augmente à près de O [DN].

Structure de données

Un autre facteur qui affecte les performances de ces algorithmes est la dimensionnalité intrinsèque des données ou la rareté des données. C'est parce que les temps de requête des algorithmes d'arbre à billes et d'arbre KD peuvent en être grandement influencés. Alors que le temps de requête de l'algorithme Brute Force est inchangé par la structure de données. Généralement, les algorithmes d'arbre à billes et d'arbre KD produisent un temps de requête plus rapide lorsqu'ils sont implantés sur des données plus éparses avec une dimensionnalité intrinsèque plus petite.

Nombre de voisins (k)

Le nombre de voisins (k) demandé pour un point de requête affecte le temps de requête des algorithmes d'arbre à billes et d'arbre KD. Leur temps de requête devient plus lent à mesure que le nombre de voisins (k) augmente. Alors que le temps de requête de Brute Force ne sera pas affecté par la valeur de k.

Nombre de points de requête

Parce qu'ils ont besoin d'une phase de construction, les algorithmes d'arbre KD et d'arbre à billes seront efficaces s'il y a un grand nombre de points de requête. D'autre part, s'il y a un plus petit nombre de points de requête, l'algorithme Brute Force fonctionne mieux que les algorithmes d'arbre KD et d'arbre à billes.