Alle Herausforderungen
Mittel 1 gelöst 100.0% Erfolgsquote

K-Nächste-Nachbarn-Klassifikator

Sage ein Label per Mehrheitsentscheid der k nächstgelegenen Trainingspunkte voraus.

Das lernst du

  • Die nächsten Trainingspunkte finden
  • Per Mehrheitsentscheid vorhersagen
  • Gleichstände deterministisch auflösen

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.

  1. Berechne den euklidischen Abstand von query zu jedem Punkt.
  2. Sortiere die Punkte nach Abstand; bei gleichen Abständen kommt der Punkt mit dem kleineren Index zuerst.
  3. Nimm die ersten k Punkte und zähle ihre Labels.
  4. 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

Beispiel 1
Eingabe:
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

Erwartete Ausgabe:
expected = "A"
Eingabe:
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;

Erwartete Ausgabe:
std::string expected = "A";
Eingabe:
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;

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.

Beispiel 2
Eingabe:
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

Erwartete Ausgabe:
expected = "red"
Eingabe:
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;

Erwartete Ausgabe:
std::string expected = "red";
Eingabe:
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;

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.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Miss zu jedem Punkt die euklidische Distanz zur Query und sortiere dann nach Distanz, wobei kleinere Indizes bei Gleichstand entscheiden.

Hinweis 2

Nur die ersten k sortierten Punkte stimmen ab, also hängt das Endlabel von einer kleinen Teilmenge des Trainingssets ab.

Hinweis 3

Wenn die Stimmen gleich verteilt sind, nimm das Label, dessen nächster beitragender Punkt in der sortierten Nachbarliste am frühesten erscheint.

Erwartete Komplexität

Zeit O(n log n), zusätzlicher Speicher O(n)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 930 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.