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.
- Calculez la distance euclidienne entre
queryet chaque point. - Triez les points par distance ; si deux distances sont égales, le point d'indice le plus petit passe en premier.
- Prenez les k premiers points et comptez leurs étiquettes.
- 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
Entrée :
k = 3
query = [3.0, 3.0]
labels = ["A", "A", "B", "B"]
points = [
[1.0, 1.0],
[2.0, 2.0],
[8.0, 8.0],
[9.0, 9.0]
]
Sortie attendue :
expected = "A"Entrée :
long long k = 3;
std::vector<double> query = {3.0, 3.0};
std::vector<std::string> labels = {"A", "A", "B", "B"};
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{2.0, 2.0},
{8.0, 8.0},
{9.0, 9.0}
};
Sortie attendue :
std::string expected = "A";Entrée :
long k = 3;
double[] query = new double[] {3.0, 3.0};
string[] labels = new string[] {"A", "A", "B", "B"};
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}
};
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.
Entrée :
k = 2
query = [1.0, 1.0]
labels = ["red", "blue", "blue", "red"]
points = [
[0.0, 0.0],
[4.0, 0.0],
[0.0, 4.0],
[4.0, 4.0]
]
Sortie attendue :
expected = "red"Entrée :
long long k = 2;
std::vector<double> query = {1.0, 1.0};
std::vector<std::string> labels = {"red", "blue", "blue", "red"};
std::vector<std::vector<double>> points = {
{0.0, 0.0},
{4.0, 0.0},
{0.0, 4.0},
{4.0, 4.0}
};
Sortie attendue :
std::string expected = "red";Entrée :
long k = 2;
double[] query = new double[] {1.0, 1.0};
string[] labels = new string[] {"red", "blue", "blue", "red"};
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}
};
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.
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.