Todos los desafíos
Intermedio 1 resuelto 100.0% de aceptación

Clasificador de k vecinos más cercanos

Predice una etiqueta por mayoría de votos entre los k puntos de entrenamiento más cercanos.

Lo que aprenderás

  • Encontrar los puntos de entrenamiento más cercanos
  • Predecir por voto mayoritario
  • Desempatar de forma determinista

Problema

Ver original (inglés)

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.

  1. Calcula la distancia euclidiana de query a cada punto.
  2. Ordena los puntos por distancia; si dos distancias son iguales, va primero el punto con el índice menor.
  3. Toma los primeros k puntos y cuenta sus etiquetas.
  4. 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

Ejemplo 1
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.

Ejemplo 2
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.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 930 ms - 5/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 1 solución completa abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.