Tous les défis
Moyen 1 résolu 100.0 % de réussite

Classifieur des k plus proches voisins

Prédisez une étiquette par vote majoritaire des k points d'entraînement les plus proches.

Ce que vous allez apprendre

  • Trouver les points d'entraînement les plus proches
  • Prédire par vote majoritaire
  • Départager les égalités de façon déterministe

Problème

Les k plus proches voisins (KNN) classent un nouveau point en regardant les k points d'entraînement les plus proches et en prenant l'étiquette la plus fréquente.

  1. Calculez la distance euclidienne entre query et chaque point.
  2. Triez les points par distance ; si deux distances sont égales, le point d'indice le plus petit passe en premier.
  3. Prenez les k premiers points et comptez leurs étiquettes.
  4. Renvoyez l'étiquette qui a le plus de votes. En cas d'égalité, renvoyez l'étiquette dont le point le plus proche apparaît en premier dans l'ordre trié.

Implémentez knn_predict(points, labels, query, k).

Entrée

points : les points d'entraînement, chacun étant une liste de coordonnées.

labels : l'étiquette de chaque point.

query : le point à classer.

k : le nombre de voisins qui votent.

Sortie

Renvoyez l'étiquette prédite.

Contraintes

1 ≤ k ≤ nombre de points ≤ 1 000

1 ≤ dimensions ≤ 20

-1 000 ≤ chaque coordonnée ≤ 1 000

Exemples

Exemple 1
Entrée :
points = [
    [1.0, 1.0],
    [2.0, 2.0],
    [8.0, 8.0],
    [9.0, 9.0]
]
labels = ["A", "A", "B", "B"]
query = [3.0, 3.0]
k = 3

Sortie attendue :
expected = "A"
Entrée :
std::vector<std::vector<double>> points = {
    {1.0, 1.0},
    {2.0, 2.0},
    {8.0, 8.0},
    {9.0, 9.0}
};
std::vector<std::string> labels = {"A", "A", "B", "B"};
std::vector<double> query = {3.0, 3.0};
long long k = 3;

Sortie attendue :
std::string expected = "A";
Entrée :
double[][] points = new double[][] {
    new double[] {1.0, 1.0},
    new double[] {2.0, 2.0},
    new double[] {8.0, 8.0},
    new double[] {9.0, 9.0}
};
string[] labels = new string[] {"A", "A", "B", "B"};
double[] query = new double[] {3.0, 3.0};
long k = 3;

Sortie attendue :
string expected = "A";

Explication

Distances depuis (3, 3) : (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. Les 3 étiquettes les plus proches sont A, A et B, donc la réponse est A.

Exemple 2
Entrée :
points = [
    [0.0, 0.0],
    [4.0, 0.0],
    [0.0, 4.0],
    [4.0, 4.0]
]
labels = ["red", "blue", "blue", "red"]
query = [1.0, 1.0]
k = 2

Sortie attendue :
expected = "red"
Entrée :
std::vector<std::vector<double>> points = {
    {0.0, 0.0},
    {4.0, 0.0},
    {0.0, 4.0},
    {4.0, 4.0}
};
std::vector<std::string> labels = {"red", "blue", "blue", "red"};
std::vector<double> query = {1.0, 1.0};
long long k = 2;

Sortie attendue :
std::string expected = "red";
Entrée :
double[][] points = new double[][] {
    new double[] {0.0, 0.0},
    new double[] {4.0, 0.0},
    new double[] {0.0, 4.0},
    new double[] {4.0, 4.0}
};
string[] labels = new string[] {"red", "blue", "blue", "red"};
double[] query = new double[] {1.0, 1.0};
long k = 2;

Sortie attendue :
string expected = "red";

Explication

Le point le plus proche est (0, 0) (red) ; les deux suivants, (4, 0) et (0, 4), sont à la même distance, donc l'indice le plus petit, (4, 0) (blue), l'emporte. Red et blue ont chacun une voix, et le point de red est arrivé en premier, donc la réponse est red.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Mesurez la distance euclidienne de chaque point à la requête, puis classez les points par distance en départageant les égalités par le plus petit indice.

Indice 2

Seuls les k premiers points triés votent, donc l’étiquette finale dépend d’un tout petit sous-ensemble du jeu d’entraînement.

Indice 3

Si les votes sont à égalité, utilisez l’étiquette dont le point contributeur le plus proche apparaît le plus tôt dans la liste triée des voisins.

Complexité attendue

temps O(n log n), espace supplémentaire O(n)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 930 ms - 5/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.