KNN: 1 nächster Nachbar

9

Meine Frage bezieht sich auf den 1-nächsten Nachbarn-Klassifikator und auf eine Aussage, die in dem ausgezeichneten Buch Die Elemente des statistischen Lernens von Hastie, Tibshirani und Friedman gemacht wurde. Die Aussage lautet (S. 465, Abschnitt 13.3):

"Da nur der Trainingspunkt verwendet wird, der dem Abfragepunkt am nächsten liegt, ist die Abweichung der Schätzung des nächsten Nachbarn oft gering, aber die Varianz ist hoch."

Das Buch ist unter http://www-stat.stanford.edu/~tibs/ElemStatLearn/download.html verfügbar

Für den Anfang können wir definieren, was Voreingenommenheit und Varianz sind. Aus der Frage "Wie kann man die Dimension vergrößern, die Varianz erhöhen, ohne das Bi zu erhöhen" haben wir Folgendes:

"Erstens ist die Vorspannung eines Klassifikators die Diskrepanz zwischen seiner gemittelten geschätzten und wahren Funktion, während die Varianz eines Klassifikators die erwartete Abweichung der geschätzten Vorhersagefunktion von seinem Durchschnittswert ist (dh wie abhängig der Klassifikator vom Zufall ist Probenahme im Trainingssatz).

Daher weist das Vorhandensein einer Verzerrung darauf hin, dass mit dem Modell grundsätzlich etwas nicht stimmt, während die Varianz ebenfalls schlecht ist, aber ein Modell mit hoher Varianz könnte zumindest im Durchschnitt eine gute Vorhersage treffen. "

Könnte jemand bitte erklären, warum die Varianz hoch und die Vorspannung für den 1-nächsten Nachbarn-Klassifikator niedrig ist?

FredikLAa
quelle

Antworten:

13

Die Abweichung ist gering, da Sie Ihr Modell nur an den 1-nächstgelegenen Punkt anpassen. Dies bedeutet, dass Ihr Modell Ihren Trainingsdaten sehr nahe kommt.

Die Varianz ist hoch, da die Optimierung auf nur 1 nächstgelegenen Punkt bedeutet, dass die Wahrscheinlichkeit, dass Sie das Rauschen in Ihren Daten modellieren, sehr hoch ist. Gemäß Ihrer obigen Definition hängt Ihr Modell stark von der Teilmenge der Datenpunkte ab, die Sie als Trainingsdaten auswählen. Wenn Sie die ausgewählten Datenpunkte nach dem Zufallsprinzip neu mischen, unterscheidet sich das Modell in jeder Iteration erheblich. Damit

erwartete Abweichung der geschätzten Vorhersagefunktion von ihrem Durchschnittswert (dh wie abhängig der Klassifizierer von der Zufallsstichprobe im Trainingssatz ist)

wird hoch sein, weil jedes Mal Ihr Modell anders sein wird.

Beispiel Im Allgemeinen passt ein k-NN-Modell einen bestimmten Punkt in den Daten mit den N nächstgelegenen Datenpunkten in Ihrem Trainingssatz an. Für 1-NN hängt dieser Punkt nur von einem einzelnen anderen Punkt ab. ZB möchten Sie Ihre Proben in zwei Gruppen aufteilen (Klassifizierung) - rot und blau. Wenn Sie Ihr Modell für einen bestimmten Punkt p trainieren, für den die nächsten 4 Nachbarn rot, blau, blau, blau wären (aufsteigend nach Abstand zu p). Dann würde ein 4-NN Ihren Punkt in Blau klassifizieren (3-mal blau und 1-mal rot), aber Ihr 1-NN-Modell klassifiziert ihn in rot, da Rot der nächste Punkt ist. Dies bedeutet, dass Ihr Modell Ihren Trainingsdaten sehr nahe kommt und daher die Tendenz gering ist. Wenn Sie das RSS zwischen Ihrem Modell und Ihren Trainingsdaten berechnen, liegt es nahe bei 0. Im Gegensatz dazu ist die Varianz in Ihrem Modell hoch, da Ihr Modell äußerst empfindlich und wackelig ist. Wie oben erwähnt, wird ein zufälliges Mischen Ihres Trainingssatzes Ihr Modell wahrscheinlich dramatisch verändern. Im Gegensatz dazu wäre 10-NN in solchen Fällen robuster, könnte aber zu steif sein. Welches k Sie wählen müssen, hängt von Ihrem Datensatz ab. Dies hängt stark von derBias-Varianz-Kompromiss , der sich genau auf dieses Problem bezieht.

Alex VII
quelle
Danke @alexvii. Sie sagen, dass dieser Klassifikator für einen neuen Punkt zu einem neuen Punkt führt, der den Testsatz sehr gut "nachahmt". Und wenn der Testsatz gut ist, wird die Vorhersage nahe an der Wahrheit liegen, was zu einer geringen Verzerrung führt? Richtig? Oder verpasse ich etwas?
FredikLAa
Ich habe einige Informationen hinzugefügt, um meinen Standpunkt klarer zu machen.
Alex VII
Noch etwas: Wenn Sie die drei nächsten Nachbarn im Vergleich zu den nächsten verwenden, wären Sie nicht "sicherer", dass Sie Recht haben, und würden die "neue" Beobachtung nicht einem Punkt zuordnen, der mit den anderen Punkten "inkonsistent" sein könnte und damit die Vorspannung senken?
FredikLAa
Dies wird auf der Wikipedia-Seite unter dem Punkt K-nächste Nachbarn fast am Ende der Seite ziemlich gut erklärt .
Alex VII
11

Beachten Sie, dass der 1-Nearest Neighbor-Klassifikator tatsächlich das komplexeste Modell für den nächsten Nachbarn ist. Mit "am komplexesten" meine ich, dass es die gezackteste Entscheidungsgrenze hat und am wahrscheinlichsten überpasst. Wenn Sie einen N-Nächsten-Nachbarn-Klassifikator verwenden (N = Anzahl der Trainingspunkte), klassifizieren Sie alles als Mehrheitsklasse. Unterschiedliche Permutationen der Daten erhalten die gleiche Antwort. Sie erhalten eine Reihe von Modellen mit einer Varianz von Null (sie sind alle genau gleich), aber einer hohen Verzerrung (sie sind alle durchweg falsch). Durch Verringern der Einstellung von K kommen Sie den Trainingsdaten immer näher (geringe Abweichung), das Modell hängt jedoch wesentlich stärker von den ausgewählten Trainingsbeispielen ab (hohe Varianz).

Nuclear Wang
quelle
danke @Matt. Eine Frage: Woher wissen Sie, dass die Tendenz für den nächsten Nachbarn am niedrigsten ist? Woher wissen Sie, dass es in Bezug auf die Voreingenommenheit besser wäre, nicht drei nächste Nachbarn zu verwenden?
FredikLAa
Stellen Sie sich ein diskretes kNN-Problem vor, bei dem wir eine sehr große Datenmenge haben, die den Probenraum vollständig abdeckt. Jeder Testpunkt kann korrekt klassifiziert werden, indem er mit seinem nächsten Nachbarn verglichen wird, bei dem es sich tatsächlich um eine Kopie des Testpunkts handelt. Die Vorspannung ist in diesem Fall Null. Wenn wir mehr Nachbarn verwenden, sind Fehlklassifizierungen möglich, was auf die zunehmende Verzerrung zurückzuführen ist. Dieses Beispiel gilt für sehr große Trainingssätze. In der Realität kann es möglich sein, mit ein paar mehr Nachbarn eine experimentell niedrigere Verzerrung zu erzielen, aber der allgemeine Trend mit vielen Daten ist weniger Nachbarn -> geringere Verzerrung.
Nuclear Wang
3

Hier ist ein sehr interessanter Blog-Beitrag über Voreingenommenheit und Varianz. Der Abschnitt 3.1 befasst sich mit dem knn-Algorithmus und erklärt, warum niedriges k zu hoher Varianz und geringer Vorspannung führt.

Abbildung 5 ist sehr interessant: Sie können in Echtzeit sehen, wie sich das Modell ändert, während k zunimmt. Für niedriges k gibt es viel Überanpassung (einige isolierte "Inseln"), was zu einer geringen Vorspannung, aber einer hohen Varianz führt. Für sehr hohe k haben Sie ein glatteres Modell mit geringer Varianz, aber hoher Vorspannung. In diesem Beispiel ergibt ein Wert von k zwischen 10 und 20 ein Abstiegsmodell, das allgemein genug (relativ geringe Varianz) und genau genug (relativ geringe Vorspannung) ist.

Anil Narassiguin
quelle