Nichtparametrische Methoden wie K-Nearest-Neighbors im hochdimensionalen Merkmalsraum

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?

machine-learning artificial-intelligence Strin
quelle

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

Raphael

Antworten:

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 dimensionale Punkte im Einheitshyperwürfel bei 20 gleichmäßig ausgewählten Werten von aus . Für jeden Wert von 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. $50$ $d$ $d$ $1..1000$ $d$

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

, dh

steigt mit

k

$k$

N^{n}

$\mathbb{N}^n$

| N^{n} \cap S_{n} (k) |

$|\mathbb{N}^n \cap S_n(k)|$

n

$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,

, (

). Bei diesen Problemen gehen Sie also davon aus, dass Sie NICHT 'viele Proben' haben.

n

$n$

d

$d$

n << d

$n << d$

Nick

Ich sehe nicht, dass dies per Definition gilt; Es scheint jedoch eine Konvention zu sein, die auf Erfahrung basiert.

Raphael

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