Scikit Learn - K-Nearest Neighbors (KNN)
Dieses Kapitel hilft Ihnen beim Verständnis der Methoden für den nächsten Nachbarn in Sklearn.
Nachbarbasierte Lernmethoden sind nämlich von beiden Arten supervised und unsupervised. Überwachtes, auf Nachbarn basierendes Lernen kann sowohl für Klassifizierungs- als auch für Regressionsvorhersageprobleme verwendet werden, wird jedoch hauptsächlich für Klassifizierungsvorhersageprobleme in der Industrie verwendet.
Nachbarbasierte Lernmethoden haben keine spezielle Trainingsphase und verwenden alle Daten für das Training während der Klassifizierung. Es wird auch nichts über die zugrunde liegenden Daten vorausgesetzt. Das ist der Grund, warum sie faul und nicht parametrisch sind.
Das Hauptprinzip hinter den Methoden des nächsten Nachbarn ist -
Um eine vordefinierte Anzahl von Trainingsmustern im Abstand zum neuen Datenpunkt zu finden
Sagen Sie das Etikett anhand dieser Anzahl von Trainingsmustern voraus.
Hier kann die Anzahl der Abtastwerte eine benutzerdefinierte Konstante sein, wie beim Lernen mit K-nächsten Nachbarn, oder basierend auf der lokalen Punktdichte variieren, wie beim Lernen mit Radius-basierten Nachbarn.
sklearn.neighbors Modul
Scikit-lernen haben sklearn.neighborsModul, das Funktionen für unbeaufsichtigte und überwachte nachbarschaftsbasierte Lernmethoden bietet. Als Eingabe können die Klassen in diesem Modul entweder NumPy-Arrays oder verarbeitenscipy.sparse Matrizen.
Arten von Algorithmen
Es gibt verschiedene Arten von Algorithmen, die bei der Implementierung nachbarschaftlicher Methoden verwendet werden können:
Rohe Gewalt
Die Brute-Force-Berechnung der Abstände zwischen allen Punktpaaren im Datensatz bietet die naivste Implementierung für die Nachbarsuche. Mathematisch skaliert für N Proben in D-Dimensionen der Brute-Force-Ansatz als0[DN2]
Für kleine Datenproben kann dieser Algorithmus sehr nützlich sein, aber er wird unmöglich, wenn die Anzahl der Proben zunimmt. Die Brute-Force-Nachbarn-Suche kann durch Schreiben des Schlüsselworts aktiviert werdenalgorithm=’brute’.
KD-Baum
Eine der baumbasierten Datenstrukturen, die erfunden wurden, um die rechnerischen Ineffizienzen des Brute-Force-Ansatzes zu beheben, ist die KD-Baumdatenstruktur. Grundsätzlich ist der KD-Baum eine binäre Baumstruktur, die als K-dimensionaler Baum bezeichnet wird. Der Parameterraum wird rekursiv entlang der Datenachsen partitioniert, indem er in verschachtelte orthografische Bereiche unterteilt wird, in die die Datenpunkte gefüllt werden.
Vorteile
Im Folgenden sind einige Vorteile des KD-Baumalgorithmus aufgeführt:
Construction is fast - Da die Partitionierung nur entlang der Datenachsen durchgeführt wird, ist der Aufbau des KD-Baums sehr schnell.
Less distance computations- Dieser Algorithmus benötigt sehr viel weniger Entfernungsberechnungen, um den nächsten Nachbarn eines Abfragepunkts zu bestimmen. Es dauert nur[ ()] Entfernungsberechnungen.
Nachteile
Fast for only low-dimensional neighbor searches- Es ist sehr schnell für niedrigdimensionale (D <20) Nachbarsuchen, aber wenn D wächst, wird es ineffizient. Da die Partitionierung nur entlang der Datenachsen durchgeführt wird,
Die Suche nach KD-Baumnachbarn kann durch Schreiben des Schlüsselworts aktiviert werden algorithm=’kd_tree’.
Kugelbaum
Da wir wissen, dass KD Tree in höheren Dimensionen ineffizient ist, wurde die Ball Tree-Datenstruktur entwickelt, um diese Ineffizienz von KD Tree zu beheben. Mathematisch unterteilt es die Daten rekursiv in Knoten, die durch einen Schwerpunkt C und einen Radius r definiert sind, so dass jeder Punkt im Knoten innerhalb der durch den Schwerpunkt definierten Hyperkugel liegtC und Radius r. Es wird die unten angegebene Dreiecksungleichung verwendet, wodurch die Anzahl der Kandidatenpunkte für eine Nachbarsuche verringert wird
$$ \ Pfeil umwandeln X + Y \ Pfeil umkehren \ leq \ Pfeil umkehren X \ Pfeil umwandeln + \ Pfeil umkehren Y \ Pfeil umkehren $$Vorteile
Im Folgenden sind einige Vorteile des Ball Tree-Algorithmus aufgeführt:
Efficient on highly structured data - Da der Ballbaum die Daten in eine Reihe verschachtelter Hyperkugeln aufteilt, ist er bei stark strukturierten Daten effizient.
Out-performs KD-tree - Der Ballbaum übertrifft den KD-Baum in hohen Dimensionen, da er eine sphärische Geometrie der Ballbaumknoten aufweist.
Nachteile
Costly - Die Aufteilung der Daten in eine Reihe von verschachtelten Hyperkugeln macht ihre Konstruktion sehr kostspielig.
Die Suche nach Ballbaumnachbarn kann durch Schreiben des Schlüsselworts aktiviert werden algorithm=’ball_tree’.
Auswahl des Algorithmus für die nächsten Nachbarn
Die Wahl eines optimalen Algorithmus für einen bestimmten Datensatz hängt von den folgenden Faktoren ab:
Anzahl der Proben (N) und Dimensionalität (D)
Dies sind die wichtigsten Faktoren, die bei der Auswahl des Nearest Neighbor-Algorithmus berücksichtigt werden müssen. Es ist aus den unten angegebenen Gründen -
Die Abfragezeit des Brute-Force-Algorithmus wächst mit O [DN].
Die Abfragezeit des Ballbaumalgorithmus wächst mit O [D log (N)].
Die Abfragezeit des KD-Baumalgorithmus ändert sich mit D auf seltsame Weise, die sehr schwer zu charakterisieren ist. Wenn D <20 ist, sind die Kosten O [D log (N)] und dieser Algorithmus ist sehr effizient. Andererseits ist es in dem Fall ineffizient, wenn D> 20 ist, weil die Kosten auf nahezu O [DN] ansteigen.
Datenstruktur
Ein weiterer Faktor, der die Leistung dieser Algorithmen beeinflusst, ist die intrinsische Dimensionalität der Daten oder die Sparsamkeit der Daten. Dies liegt daran, dass die Abfragezeiten von Ball Tree- und KD Tree-Algorithmen stark davon beeinflusst werden können. Während die Abfragezeit des Brute-Force-Algorithmus durch die Datenstruktur unverändert bleibt. Im Allgemeinen erzeugen Ballbaum- und KD-Baumalgorithmen eine schnellere Abfragezeit, wenn sie in sparser Daten mit geringerer intrinsischer Dimensionalität implantiert werden.
Anzahl der Nachbarn (k)
Die Anzahl der Nachbarn (k), die für einen Abfragepunkt angefordert werden, beeinflusst die Abfragezeit von Ball Tree- und KD Tree-Algorithmen. Ihre Abfragezeit wird langsamer, wenn die Anzahl der Nachbarn (k) zunimmt. Während die Abfragezeit von Brute Force vom Wert von k nicht beeinflusst wird.
Anzahl der Abfragepunkte
Da sie eine Bauphase benötigen, sind sowohl KD-Baum- als auch Kugelbaum-Algorithmen effektiv, wenn eine große Anzahl von Abfragepunkten vorhanden ist. Wenn andererseits eine geringere Anzahl von Abfragepunkten vorhanden ist, ist der Brute-Force-Algorithmus leistungsfähiger als der KD-Baum- und der Ballbaum-Algorithmus.