Wann sollte ich über k nächsten Nachbarn hinausgehen?

9

Für viele maschinelle Lernprojekte, die wir durchführen, beginnen wir mit dem Klassifikator k Nearest Neighbor. Dies ist ein idealer Startklassifikator, da wir normalerweise genügend Zeit haben, um alle Entfernungen zu berechnen, und die Anzahl der Parameter begrenzt ist (k, Entfernungsmetrik und Gewichtung).

Dies hat jedoch häufig den Effekt, dass wir beim knn-Klassifikator bleiben, da später im Projekt kein Platz mehr für den Wechsel zu einem anderen Klassifikator vorhanden ist. Was wäre ein guter Grund, einen neuen Klassifikator auszuprobieren. Offensichtliche sind Speicher- und Zeitbeschränkungen, aber gibt es Fälle, in denen ein anderer Klassifikator die Genauigkeit tatsächlich verbessern kann?

neural-networks classification
quelle
Ist das rein akademisch oder soll es in der Industrie eingesetzt werden?
Dr. Rob Lang
1
Die meisten unserer Anwendungen werden in der Industrie bereitgestellt (daher sind Speicherbedarf und Berechnungszeit

Antworten:

3

k-NN verallgemeinert in einem sehr restriktiven Sinne. Es werden einfach Glättungsprioren (oder Kontinuitätsannahmen) verwendet. Diese Annahme impliziert, dass Muster, die sich im Merkmalsraum befinden, höchstwahrscheinlich zur selben Klasse gehören. Durch k-NN kann keine funktionelle Regelmäßigkeit in der Musterverteilung wiederhergestellt werden.

Daher sind repräsentative Trainingsmuster erforderlich, die insbesondere bei hochdimensionalen Merkmalsräumen extrem groß sein können. Schlimmer noch, diese Beispiele sind möglicherweise nicht verfügbar. Folglich kann es keine Invarianten lernen. Wenn Muster einigen Transformationen unterzogen werden können, ohne ihre Beschriftungen zu ändern, und das Trainingsmuster nicht Muster enthält, die auf alle zulässigen Arten transformiert wurden, erkennt k-NN niemals transformierte Muster, die während des Trainings nicht präsentiert wurden. Dies gilt beispielsweise für verschobene oder gedrehte Bilder, wenn sie vor dem Ausführen von k-NN nicht in einer invarianten Form dargestellt werden. k-NN kann nicht einmal von irrelevanten Merkmalen abstrahieren.

Ein weiteres etwas künstliches Beispiel folgt. Stellen Sie sich vor, dass Muster, die zu verschiedenen Klassen gehören, periodisch verteilt werden (z. B. gemäß Sinus - wenn es kleiner als 0 ist, gehören Muster zu einer Klasse und es ist größer, dann gehören Muster zu einer anderen Klasse). Trainingsset ist endlich. Es wird sich also in einer endlichen Region befinden. Außerhalb dieser Region beträgt der Erkennungsfehler 50%. Man kann sich die logistische Regression mit periodischen Basisfunktionen vorstellen, die in diesem Fall viel besser abschneiden. Andere Methoden können andere Regelmäßigkeiten in Musterverteilungen lernen und gut extrapolieren.

Wenn man also den Verdacht hat, dass der verfügbare Datensatz nicht repräsentativ ist und eine Invarianz gegenüber einigen Transformationen von Mustern erreicht werden sollte, dann ist dies der Fall, in dem man über k-NN hinausgehen sollte.


quelle
Vielen Dank für Ihre Antwort (und danke BartoszKP für den Versuch, sie zu verbessern). Es ist wahr, dass knn keine Muster finden kann, die transformiert werden müssen (es sei denn, Sie verwenden eine seltsame (und falsche) Abstandsmetrik). Das ist ein guter Grund, einen anderen Klassifikator auszuprobieren. Ich denke, svm ist dann eine naheliegende Wahl. Ich bin mit svm nicht ausreichend vertraut, um es zu sagen, aber würde es nicht spezifisches Wissen über das Muster erfordern, nach dem Sie suchen, um den Kernel zu definieren?
Ja. Die Wahl des Kernels hängt von den Mustern ab. Der Gaußsche Kernel hat ähnliche Eigenschaften wie die k-NN-Methode. Andere Standardkerne scheinen ebenfalls unangemessen zu sein. Zumindest könnte man jedoch versuchen, sie zu verwenden.
Wie von @ Necro0x0Der impliziert, würde jede Verbesserung in dieser Richtung davon abhängen, dass das Muster (im Sinusbeispiel Periodizität) für die Parametrisierung natürlich ist. Das heißt, die Parametrisierung (Kernelauswahl) definiert die Struktur (effektiv die Metrik) des Darstellungsraums. Wenn Sie auf irgendeine Weise (möglicherweise durch fundiertes Raten) eine geeignete Struktur bestimmen können, versuchen Sie, das Muster entsprechend zu parametrisieren. Beachten Sie, dass Ihr Klassifizierer dadurch letztendlich bestimmte Arten relevanter Merkmale leicht finden kann.
3

Wenn Sie durch die Komplexität der Berechnungen eingeschränkt wären, sind Entscheidungsbäume (Quinal, 1986) schwer zu übertreffen (insbesondere wenn ein Framework die direkte Konvertierung des DT-Modells in eine Reihe von ifAnweisungen bietet - wie Accord.NET ).

Für hochdimensionale Daten wird der Begriff der Entfernung, auf dem k-NN basiert, wertlos (Kriegel, Kröger, Zimek, 2009) (auch: Wikipedia-Artikel ). Andere Klassifikatoren wie SVM (Corter, Vapnik, 1995) oder Random Forests (Breiman, 2001) könnten daher eine bessere Leistung erbringen .

Verweise:

BartoszKP
quelle
Eine hohe Dimension ist natürlich keine feste Grenze. In den meisten Fällen sind unsere Merkmale so ausdrucksstark, dass die Entfernung funktioniert. Dies könnte natürlich ein wichtiger Punkt sein. Vielleicht hätte ich mit einem Beispiel klarstellen sollen. Angenommen, wir haben einen Klassifikator mit einer Genauigkeit von 93%. Dies ist akzeptabel. Jetzt können wir entweder versuchen, den Klassifikator zu verbessern oder neue Funktionen zu finden. Es hängt alles von den neuen möglichen Funktionen und den Daten ab, aber ich suchte nach Richtlinien für diese Entscheidung.
@Rhand Scheint mir, dass es eine Entscheidung auf Projektmanagementebene ist. Wenn die aktuelle Lösung akzeptabel ist, warum daran basteln? Es ist Zeitverschwendung. Wenn dies nicht akzeptabel ist, definieren Sie genauer, was Sie verbessern möchten (Geschwindigkeit, Genauigkeit usw.).
BartoszKP
Es geht nicht nur um das Projektmanagement, sondern auch darum, wie man eine maximale Genauigkeit erreicht (dies ist in meiner Frage) und in welche Richtung man am besten geht. Sie schlagen SVM und zufällige Gesamtstruktur vor, da die Dimensionalität möglicherweise zu hoch ist. Dies ist eine Möglichkeit, mit der ich experimentieren könnte, um festzustellen, ob sich die Genauigkeit verbessert, und das ist die Art von Antwort, nach der ich gesucht habe.
Nun, dies ist andererseits eine sehr breite Frage. Es gibt keine allgemeinen Regeln, nach denen der Klassifikator X besser als Y ist. Sie sollten nur eine Reihe von Klassifikatoren ausprobieren und dann beispielsweise eine Kreuzvalidierung für die Modellauswahl durchführen .
BartoszKP
3

kNN ist nützlich für große Datenproben

Die Nachteile sind jedoch:

  1. Voreingenommen durch den Wert von k.
  2. Rechenkomplexität
  3. Speicherbeschränkung
  4. Ein überwachter Lern-Lazy-Algorithmus sein
  5. Leicht durch irrelevante Attribute getäuscht.
  6. Die Vorhersagegenauigkeit kann sich schnell verschlechtern, wenn die Anzahl der Attribute zunimmt.

Es ist normalerweise nur dann effektiv, wenn die Trainingsdaten groß sind und das Training sehr schnell ist.

Iancovici
quelle
Ich schaue nicht auf Clustering, sondern auf Klassifizierung
@ Hand hier gehen wir, danke für den Hinweis iliasfl
Iancovici