Fonctionnement de l'algorithme k-NN

Étape 1 : Exemple

Pour spécifier le nombre total de points de données à échantillonner à partir du jeu de données d'apprentissage, utilisez le paramètre sample_size. Par exemple, si le jeu de données initial comporte 1 000 points de données, que sample_size a la valeur 100 et que le nombre total d'instances est 2, chaque travail équivaut à 50 points. Un jeu total de 100 points de données sera collecté. L'échantillonnage s'exécute en temps linéaire en ce qui concerne le nombre de points de données.

Étape 2 : Exécution de la réduction de dimension

L'implémentation actuelle de l'algorithme k-NN possède deux méthodes de réduction de dimension. Vous spécifiez la méthode dans l'hyperparamètre dimension_reduction_type. La méthode sign spécifie une projection aléatoire, qui utilise une projection linéaire à l'aide d'une matrice de signes aléatoire ; la méthode fjlt spécifie une méthode FJLT (Fast Johnson-Lindenstrauss Transform), basée sur la transformation de Fourier. Les deux méthodes conservent les distances L2 et produit interne. La méthode fjlt doit être utilisée lorsque la dimension cible est élevée et qu'elle offre de meilleures performances avec l'inférence CPU. Les méthodes diffèrent en termes de complexité de calcul. La méthode sign nécessite un temps O(ndk) pour réduire la dimension d'un lot de n points de dimension d en une dimension cible k. La méthode fjlt nécessite un temps O(nd log(d)), mais les constantes impliquées sont plus grandes. L'utilisation de la réduction de dimension introduit du bruit dans les données et celui-ci peut réduire la précision des prédictions.

Étape 3 : Créer un index

Pendant l'inférence, l'algorithme interroge l'index sur les k-NN voisins d'un point d'échantillonnage. En fonction des références aux points, l'algorithme effectue une prédiction de classification ou de régression. Il base la prédiction sur les étiquettes de classe ou valeurs fournies. L'algorithme k-NN fournit trois différents types d'index : un index plat, un index inversé et un index inversé avec quantification du produit. Vous spécifiez le type avec le paramètre index_type.

Sérialiser le modèle

Lorsque l'algorithme k-NN a terminé l'apprentissage, il sérialise trois fichiers à préparer pour l'inférence.

• model_algo 1 : contient l'index sérialisé pour le calcul des plus proches voisins.

• model_algo-1.labels : contient les étiquettes sérialisées (format binaire np.float32) pour le calcul de l'étiquette prédite en fonction du résultat de la requête à partir de l'index.

• model_algo-1.json : contient les métadonnées du modèle au format JSON qui stocke les hyperparamètres k et predictor_type de l'apprentissage pour l'inférence, ainsi que les autres états pertinents.

Avec l'implémentation actuelle de k-NN, vous pouvez modifier le fichier des métadonnées pour changer la façon dont les prédictions sont calculées. Par exemple, vous pouvez modifier k en 10 ou modifier predictor_type en regressor.

{
  "k": 5,
  "predictor_type": "classifier",
  "dimension_reduction": {"type": "sign", "seed": 3, "target_dim": 10, "input_dim": 20},
  "normalize": False,
  "version": "1.0"
}