Problema
Os k vizinhos mais próximos (KNN) classificam um ponto novo olhando os k pontos de treinamento mais próximos e escolhendo o rótulo mais comum.
- Calcule a distância euclidiana de
queryaté cada ponto. - Ordene os pontos pela distância; se duas distâncias forem iguais, o ponto com o menor índice vem primeiro.
- Pegue os k primeiros pontos e conte seus rótulos.
- Retorne o rótulo com mais votos. Em caso de empate, retorne o rótulo cujo ponto mais próximo aparece primeiro na ordem.
Implemente knn_predict(points, labels, query, k).
Entrada
points: Os pontos de treinamento, cada um uma lista de coordenadas.
labels: O rótulo de cada ponto.
query: O ponto a classificar.
k: Quantos vizinhos votam.
Saída
Retorne o rótulo previsto.
Restrições
1 ≤ k ≤ número de pontos ≤ 1.000
1 ≤ dimensões ≤ 20
-1.000 ≤ cada coordenada ≤ 1.000
Exemplos
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]
]
Saída 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}
};
Saída 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}
};
Saída esperada:
string expected = "A";Explicação
Distâncias a partir de (3, 3): (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. Os 3 rótulos mais próximos são A, A e B, então a resposta é 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]
]
Saída 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}
};
Saída 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}
};
Saída esperada:
string expected = "red";Explicação
O ponto mais próximo é (0, 0) (red); os dois seguintes, (4, 0) e (0, 4), estão à mesma distância, então vence o menor índice, (4, 0) (blue). Red e blue têm um voto cada, e o ponto de red veio primeiro, então a resposta é red.
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.