Problema
K vecinos más cercanos (KNN) clasifica un punto nuevo mirando los k puntos de entrenamiento más cercanos y tomando la etiqueta más común.
- Calcula la distancia euclidiana de
querya cada punto. - Ordena los puntos por distancia; si dos distancias son iguales, va primero el punto con el índice menor.
- Toma los primeros k puntos y cuenta sus etiquetas.
- Devuelve la etiqueta con más votos. Si hay empate, devuelve la etiqueta empatada cuyo punto más cercano aparece primero en el orden.
Implementa knn_predict(points, labels, query, k).
Entrada
points: Los puntos de entrenamiento, cada uno una lista de coordenadas.
labels: La etiqueta de cada punto.
query: El punto a clasificar.
k: Cuántos vecinos votan.
Salida
Devuelve la etiqueta predicha.
Restricciones
1 ≤ k ≤ número de puntos ≤ 1000
1 ≤ dimensiones ≤ 20
-1000 ≤ cada coordenada ≤ 1000
Ejemplos
Entrada:
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]
]
Salida esperada:
expected = "A"Entrada:
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}
};
Salida esperada:
std::string expected = "A";Entrada:
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}
};
Salida esperada:
string expected = "A";Explicación
Distancias desde (3, 3): (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. Las 3 etiquetas más cercanas son A, A y B, así que la respuesta es A.
Entrada:
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]
]
Salida esperada:
expected = "red"Entrada:
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}
};
Salida esperada:
std::string expected = "red";Entrada:
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}
};
Salida esperada:
string expected = "red";Explicación
El punto más cercano es (0, 0) (red); los dos siguientes, (4, 0) y (0, 4), están a la misma distancia, así que gana el índice menor, (4, 0) (blue). Red y blue tienen un voto cada uno, y el punto de red apareció primero, así que la respuesta es red.
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.