Nichtparametrische Methoden wie K-Nearest-Neighbors im hochdimensionalen Merkmalsraum

11

Die Hauptidee von k-Nearest-Neighbor berücksichtigt die nächstgelegenen Punkte und entscheidet über die Klassifizierung der Daten mit Stimmenmehrheit. Wenn ja, sollte es keine Probleme mit höherdimensionalen Daten geben, da Methoden wie lokalitätssensitives Hashing die nächsten Nachbarn effizient finden können.k

Darüber hinaus kann die Merkmalsauswahl mit Bayes'schen Netzwerken die Datendimension verringern und das Lernen erleichtern.

In diesem Übersichtsartikel von John Lafferty zum statistischen Lernen wird jedoch darauf hingewiesen, dass nichtparametrisches Lernen in hochdimensionalen Merkmalsräumen immer noch eine Herausforderung und ungelöst ist.

Was läuft falsch?

Strin
quelle
1
Bitte geben Sie eine vollständige Referenz für das Papier an; Die Autoren scheinen nicht (prominent) darin zu erscheinen.
Raphael

Antworten:

5

Dieses Problem ist als Fluch der Dimensionalität bekannt . Grundsätzlich neigen Punkte im Raum dazu, sich von allen anderen Punkten zu entfernen, wenn Sie die Anzahl der Dimensionen erhöhen . Dies macht die Partitionierung des Speicherplatzes (wie er für die Klassifizierung oder Clusterbildung erforderlich ist) sehr schwierig.d

Sie können dies sehr leicht selbst sehen. Ich habe zufällige d- dimensionale Punkte im Einheitshyperwürfel bei 20 gleichmäßig ausgewählten Werten von d aus 1..1000 erzeugt . Für jeden Wert von d habe ich die Entfernung vom ersten Punkt zu allen anderen berechnet und den Durchschnitt dieser Entfernungen genommen. Wenn wir dies darstellen, können wir sehen, dass der durchschnittliche Abstand mit der Dimensionalität zunimmt, obwohl der Raum, in dem wir die Punkte in jeder Dimension erzeugen, gleich bleibt.50dd1..1000d

Durchschnittlicher Abstand vs. Dimensionalität

Nick
quelle
Natürlich. Sie erhöhen die Anzahl der Punkte in einem Hyper von festen Radius exponentiell in der dimensionalty, wenn Sie also 50 Punkte gleichmäßig zufällig wählen dies hat geschehen. Wenn Ihre Argumentation richtig ist, sollte die Partitionierung daher einfach werden, wenn ich viele Beispiele habe. ist das so?
Raphael
Ich glaube, Sie haben es umgekehrt. Durch Erhöhen der Dimensionalität reduziere ich die Anzahl der Punkte innerhalb einer Hypersphäre. Die Partitionierung wird schwieriger, weil das Entfernungsmaß im Wesentlichen seine Bedeutung verliert (z. B. ist alles weit weg).
Nick
Ich meinte: Die Gesamtzahl der Punkte in einer Hypersphäre mit dem Radius in sagen wir N n , dh | N nS n ( k ) | steigt mit n . kN.n|N.nS.n(k)|n
Raphael
Beachten Sie auch , das bedeutet , was die Leute , wenn sie zu hochdimensionalen Merkmalsraum verweisen , dass die Anzahl der Proben, , ist viel kleiner als die Dimensionalität eines jeden Punktes, d , ( n < < d ). Bei diesen Problemen gehen Sie also davon aus, dass Sie NICHT 'viele Proben' haben. ndn<<d
Nick
Ich sehe nicht, dass dies per Definition gilt; Es scheint jedoch eine Konvention zu sein, die auf Erfahrung basiert.
Raphael
3

Keine vollständige Antwort, aber auf der von Ihnen zitierten Wikipedia-Seite heißt es:

Die Genauigkeit des k-NN-Algorithmus kann durch das Vorhandensein von verrauschten oder irrelevanten Merkmalen oder wenn die Merkmalsskalen nicht mit ihrer Bedeutung übereinstimmen, stark beeinträchtigt werden.

Die Wahrscheinlichkeit, dass dies auftritt, steigt bei Vorhandensein hochdimensionaler Merkmalsräume.

Dave Clarke
quelle
Aber ich denke, mit PCA (Hauptkomponentenanalyse) oder anderen Methoden zur Reduzierung der Dimensionalität und zum Entfernen irrelevanter Daten kann k-NN immer noch funktionieren. Und was die Wikipedia-Seiten bedeuten, ist, dass das naive k-NN versagen wird. Das erklärt also nicht das Übersichtsartikel.
Strin
PCA kann sicherlich funktionieren, aber nicht in allen Situationen.
Dave Clarke