Problema
Il k-nearest neighbors (KNN) classifica un nuovo punto guardando i k punti di addestramento più vicini e prendendo l'etichetta più comune.
- Calcola la distanza euclidea da
querya ogni punto. - Ordina i punti per distanza; se due distanze sono uguali, viene prima il punto con l'indice minore.
- Prendi i primi k punti e conta le loro etichette.
- Restituisci l'etichetta con più voti. In caso di parità, restituisci l'etichetta il cui punto più vicino compare per primo nell'ordine.
Implementa knn_predict(points, labels, query, k).
Input
points: I punti di addestramento, ognuno una lista di coordinate.
labels: L'etichetta di ogni punto.
query: Il punto da classificare.
k: Quanti vicini votano.
Output
Restituisci l'etichetta prevista.
Vincoli
1 ≤ k ≤ numero di punti ≤ 1.000
1 ≤ dimensioni ≤ 20
-1.000 ≤ ogni coordinata ≤ 1.000
Esempi
Input:
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
Output atteso:
expected = "A"
Input:
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;
Output atteso:
std::string expected = "A";
Input:
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;
Output atteso:
string expected = "A";
Spiegazione
Distanze da (3, 3): (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. Le 3 etichette più vicine sono A, A e B, quindi la risposta è A.
Input:
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
Output atteso:
expected = "red"
Input:
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;
Output atteso:
std::string expected = "red";
Input:
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;
Output atteso:
string expected = "red";
Spiegazione
Il punto più vicino è (0, 0) (red); i due successivi, (4, 0) e (0, 4), sono alla stessa distanza, quindi vince l'indice minore, (4, 0) (blue). Red e blue hanno un voto ciascuno, e il punto di red è arrivato per primo, quindi la risposta è red.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Misura la distanza euclidea di ogni punto dalla query, poi ordina i punti per distanza rompendo i pari indice più piccolo.
Suggerimento 2
Votano solo i primi k punti ordinati, quindi l’etichetta finale dipende da una piccola parte del training set.
Suggerimento 3
Se i conteggi dei voti sono pari, usa l’etichetta il cui punto contributivo più vicino appare per primo nella lista ordinata dei vicini.
Complessità attesa
tempo O(n log n), spazio aggiuntivo O(n)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.