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:
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
Salida esperada:
expected = "A"
Entrada:
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;
Salida esperada:
std::string expected = "A";
Entrada:
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;
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:
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
Salida esperada:
expected = "red"
Entrada:
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;
Salida esperada:
std::string expected = "red";
Entrada:
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;
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.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Mide la distancia euclidiana de cada punto al query y luego ordena los puntos por distancia, rompiendo empates con el índice más pequeño.
Pista 2
Solo los primeros k puntos ordenados votan, así que la etiqueta final depende de un subconjunto pequeño del set de entrenamiento.
Pista 3
Si hay empate en los votos, usa la etiqueta cuyo punto contribuyente más cercano aparezca primero en la lista ordenada de vecinos.
Complejidad esperada
tiempo O(n log n), espacio extra O(n)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.