Problem
K-nearest neighbors (KNN) classifies a new point by looking at the k training points closest to it and taking the most common label.
- Compute the Euclidean distance from
queryto every point. - Sort the points by distance; if two distances are equal, the point with the smaller index comes first.
- Take the first k points and count their labels.
- Return the label with the most votes. If labels tie, return the tied label whose closest point comes first in the sorted order.
Implement knn_predict(points, labels, query, k).
Input
points: The training points, each a list of coordinates.
labels: The label of each point.
query: The point to classify.
k: How many neighbors vote.
Output
Return the predicted label.
Einschränkungen
1 ≤ k ≤ number of points ≤ 1,000
1 ≤ dimensions ≤ 20
-1,000 ≤ each coordinate ≤ 1,000
Beispiele
Eingabe:
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]
]
Erwartete Ausgabe:
expected = "A"Eingabe:
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}
};
Erwartete Ausgabe:
std::string expected = "A";Eingabe:
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}
};
Erwartete Ausgabe:
string expected = "A";Erläuterung
Distances from (3, 3): (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. The 3 nearest labels are A, A and B, so the answer is A.
Eingabe:
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]
]
Erwartete Ausgabe:
expected = "red"Eingabe:
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}
};
Erwartete Ausgabe:
std::string expected = "red";Eingabe:
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}
};
Erwartete Ausgabe:
string expected = "red";Erläuterung
The nearest point is (0, 0) (red); the next two, (4, 0) and (0, 4), are at the same distance, so the smaller index (4, 0) (blue) wins the tie. Red and blue have one vote each, and red's point came first, so the answer is red.
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.