Warum müssen wir einen Klassifikator für k-nächste Nachbarn anpassen?

11

Wie ich verstanden habe, ist k-NN ein fauler Lernalgorithmus und benötigt keine Trainingsphase. Warum müssen wir .fit()sklearn verwenden und was passiert, wenn wir es verwenden?

TmSmth
quelle

Antworten:

9

Auf konzeptioneller Ebene

Das Anpassen eines Klassifikators bedeutet, einen Datensatz als Eingabe zu nehmen und dann einen Klassifikator auszugeben, der aus einem Raum möglicher Klassifikatoren ausgewählt wird. In vielen Fällen wird ein Klassifizierer durch einen Satz von Parametern identifiziert, dh von anderen möglichen Klassifizierern unterschieden. Die Parameter werden typischerweise durch Lösen eines Optimierungsproblems oder eines anderen numerischen Verfahrens ausgewählt. Im Fall von knn wird der Klassifizierer jedoch durch die Trainingsdaten selbst identifiziert. Auf abstrakter Ebene erfordert das Anpassen eines Knn-Klassifikators lediglich das Speichern des Trainingssatzes.

Auf der Implementierungsebene

Das Auswerten eines bekannten Klassifikators an einem neuen Datenpunkt erfordert die Suche nach seinen nächsten Nachbarn im Trainingssatz. Dies kann eine teure Operation sein, wenn der Trainingssatz groß ist. Wie RUser erwähnt hat, gibt es verschiedene Tricks, um diese Suche zu beschleunigen. Diese funktionieren normalerweise, indem verschiedene Datenstrukturen basierend auf dem Trainingssatz erstellt werden. Die allgemeine Idee ist, dass ein Teil der Rechenarbeit, die zum Klassifizieren neuer Punkte erforderlich ist, tatsächlich über Punkte hinweg gemeinsam ist. Diese Arbeit kann also im Voraus ausgeführt und dann wiederverwendet werden, anstatt für jede neue Instanz wiederholt zu werden. Eine bekannte Implementierung mit diesen Tricks würde diese Arbeit während der Trainingsphase erledigen. Zum Beispiel kann scikit-learn während des Aufrufs der fit()Funktion kd-Bäume oder Ballbäume konstruieren .

Auswahl von und der Abstandsmetrikk

Die Anzahl der Nachbarn und die Abstandsmetrik sind Hyperparameter von knn-Klassifikatoren. Die Leistung kann normalerweise verbessert werden, indem sie entsprechend dem Problem ausgewählt werden. Die optimalen Einstellungen sind jedoch normalerweise nicht im Voraus bekannt, und wir müssen sie während des Trainingsvorgangs suchen. Diese Suche läuft auf die Lösung eines Optimierungsproblems hinaus und ähnelt der Optimierung von Hyperparametern für andere Methoden.k

user20160
quelle
11

Sie können es faul implementieren und es macht eine anständige Übung, wenn Sie eine Sprache entdecken. (siehe Beispiel einen meiner Blog-Beiträge ). Sie können die Daten aber auch indizieren, um die Vorhersage zu treffen (viel schneller).

Wenn der Feature-Space eine Dimension von eins hätte, könnten Sie die Nachbarn viel schneller finden, indem Sie die Punkte nach diesem Feature sortieren (mithilfe der dichotomischen Suche pro Beispiel). In größeren Dimensionen gibt es keine natürliche Verallgemeinerung der Sortierung, aber Sie können die Punkte mithilfe von (pro Beispiel) Quadtrees indizieren .

Wenn Sie sich die Quelle ansehen, können Sie sehen, dass verschiedene Methoden in scikit learn implementiert wurden. Und es gibt einige Untersuchungen , die diese Anfragen von nächsten Nachbarn ständig verbessern.

RUser4512
quelle
5

Während die Punkte, die die anderen Antwortenden gemacht haben, sicherlich gültig und interessant sind, möchte ich noch eines aus rein softwaretechnischer Sicht hervorheben:

Um es mit ihrer API konsistent zu machen

Die Schätzer von sklearn sollten unter anderem eine fitMethode haben, die ein oder zwei Array-Likes (abhängig davon, ob es sich um einen überwachten / unbeaufsichtigten Schätzer handelt) und eine Reihe implementierungsspezifischer Details ( Quelle ) verwendet.

Selbst wenn die fitMethode von knn absolut nichts tun würde, würde sie wahrscheinlich immer noch existieren, da knn ein Schätzer ist und die Entwickler von sklearn sowie der Code, den sie beitragen, erwarten, dass Schätzer eine fitMethode haben.

Brian K.
quelle