Problem
K-nächste Nachbarn (KNN) klassifiziert einen neuen Punkt, indem es die k Trainingspunkte betrachtet, die ihm am nächsten liegen, und das häufigste Label nimmt.
- Berechne den euklidischen Abstand von
queryzu jedem Punkt. - Sortiere die Punkte nach Abstand; bei gleichen Abständen kommt der Punkt mit dem kleineren Index zuerst.
- Nimm die ersten k Punkte und zähle ihre Labels.
- Gib das Label mit den meisten Stimmen zurück. Bei Gleichstand gib das Label zurück, dessen nächster Punkt in der sortierten Reihenfolge zuerst kommt.
Implementiere knn_predict(points, labels, query, k).
Eingabe
points: Die Trainingspunkte, jeweils eine Liste von Koordinaten.
labels: Das Label jedes Punkts.
query: Der zu klassifizierende Punkt.
k: Wie viele Nachbarn abstimmen.
Ausgabe
Gib das vorhergesagte Label zurück.
Einschränkungen
1 ≤ k ≤ Anzahl der Punkte ≤ 1.000
1 ≤ Dimensionen ≤ 20
-1.000 ≤ jede Koordinate ≤ 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
Abstände von (3, 3): (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. Die 3 nächsten Labels sind A, A und B, also ist die Antwort 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
Der nächste Punkt ist (0, 0) (red); die nächsten beiden, (4, 0) und (0, 4), haben denselben Abstand, also gewinnt der kleinere Index (4, 0) (blue). Red und blue haben je eine Stimme, und der Punkt von red kam zuerst, also ist die Antwort red.
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.