Fluch der Dimensionalität: kNN-Klassifikator

11

Ich lese Kevin Murphys Buch: Maschinelles Lernen - Eine probabilistische Perspektive. Im ersten Kapitel erklärt der Autor den Fluch der Dimensionalität und es gibt einen Teil, den ich nicht verstehe. Als Beispiel gibt der Autor an:

Beachten Sie, dass die Eingaben gleichmäßig entlang eines D-dimensionalen Einheitswürfels verteilt sind. Angenommen, wir schätzen die Dichte von Klassenbeschriftungen, indem wir einen Hyperwürfel um x wachsen lassen, bis er den gewünschten Bruchteil der Datenpunkte enthält. Die erwartete Kantenlänge dieses Würfels beträgt $f$ . $e_D(f) = f^{\frac{1}{D}}$

Es ist die letzte Formel, die ich nicht verstehen kann. Wenn Sie beispielsweise 10% der Punkte abdecken möchten, sollte die Kantenlänge in jeder Dimension 0,1 betragen. Ich weiß, dass meine Argumentation falsch ist, aber ich kann nicht verstehen, warum.

self-study k-nearest-neighbour high-dimensional user42140
quelle

6

Stellen Sie sich die Situation zunächst in zwei Dimensionen vor. Wenn ich ein 1 m * 1 m großes Blatt Papier habe und ein Quadrat von 0,1 m * 0,1 m aus der unteren linken Ecke herausschneide, habe ich nicht ein Zehntel des Papiers entfernt, sondern nur ein Hundertstel .

David Zhang

13

Das ist genau das unerwartete Verhalten von Entfernungen in hohen Dimensionen. Für 1 Dimension haben Sie das Intervall [0, 1]. 10% der Punkte befinden sich in einem Segment mit einer Länge von 0,1. Aber was passiert, wenn die Dimensionalität des Merkmalsraums zunimmt?

Dieser Ausdruck sagt Ihnen, dass Sie, wenn Sie diese 10% der Punkte für 5 Dimensionen haben möchten, eine Länge für den Würfel von 0,63 in 10 Dimensionen von 0,79 und 0,98 für 100 Dimensionen haben müssen.

Wie Sie sehen, müssen Sie zum Erhöhen der Abmessungen weiter wegschauen, um die gleiche Anzahl von Punkten zu erhalten. Noch mehr sagt Ihnen, dass sich die meisten Punkte an der Grenze des Würfels befinden, wenn die Anzahl der Dimensionen zunimmt. Welches ist unerwartet.

jpmuc
quelle

4

Ich denke, die Hauptsache ist, dass der Ausdruck

e_{D.} (f) = f^{\frac{1}{D.}}

$e_D(f) = f^{\frac{1}{D}}$

ist am Anfang wirklich sehr, sehr steil. Dies bedeutet, dass die Größe der Kante, die Sie benötigen, um einen bestimmten Bruchteil des Volumens zu erfassen, insbesondere zu Beginn drastisch zunimmt. dh die Kante, die Sie benötigen, wird mit zunehmendem lächerlich groß . $D$

Um dies noch deutlicher zu machen, erinnern Sie sich an die Handlung, die Murphy zeigt:

Wenn Sie bemerken, dass für Werte von die Steigung sehr groß ist und daher die Funktion am Anfang sehr steil wächst. Dies kann besser gewürdigt werden, wenn Sie die Ableitung von : $D > 1$ $e_D(f)$

e_{D.}^{'} (f) = \frac{1}{D.} f^{\frac{1}{D.} - - 1} = \frac{1}{D.} f^{\frac{1 - - D.}{D.}}

$e'_D(f) = \frac{1}{D} f^{\frac{1}{D} - 1} = \frac{1}{D} f^{\frac{1 - D}{D}}$

$D > 1$ $1-D < 0$

e_{D.}^{'} (f) = \frac{1}{D.} (f^{1 - - D.})^{\frac{1}{D.}}

$e'_D(f) = \frac{1}{D} (f^{1 - D})^{\frac{1}{D}}$

$f$ $x^{-1} = \frac{1}{x}$ $f < 1$ $k$ $N$ $D$ $D$

$f^{1 - D}$ $\frac{1}{D}$

Charlie Parker
quelle

2

Ja, wenn Sie also einen Einheitswürfel oder in Ihrem Fall eine Einheitslinie haben und die Daten gleichmäßig verteilt sind, müssen Sie eine Länge von 0,1 wählen, um 10% der Daten zu erfassen. Wenn Sie nun die Dimensionen vergrößern, nimmt D zu, wodurch die Leistung abnimmt und f kleiner als 1 ist. Wenn D gegen unendlich geht, müssen Sie den gesamten Würfel erfassen, e = 1.

plumSemPy
quelle

0

Ich denke, für kNN spielt die Entfernung eine größere Rolle. Was mit einem (Hyper-) Würfel passiert, ist analog zu dem, was mit dem Abstand zwischen Punkten passiert. Wenn Sie die Anzahl der Dimensionen erhöhen, wächst das Verhältnis zwischen der nächstgelegenen Entfernung und der durchschnittlichen Entfernung. Dies bedeutet, dass der nächstgelegene Punkt fast so weit entfernt ist wie der durchschnittliche Punkt. Dann hat er nur eine geringfügig höhere Vorhersagekraft als der durchschnittliche Punkt. Dieser Artikel erklärt es schön

Joel Grus hat dieses Problem in Data Science from Scratch gut beschrieben. In diesem Buch berechnet er den durchschnittlichen und minimalen Abstand zwischen zwei Punkten in einem Dimensionsraum, wenn die Anzahl der Dimensionen zunimmt. Er berechnete 10.000 Abstände zwischen Punkten mit einer Anzahl von Dimensionen zwischen 0 und 100. Anschließend zeichnet er den durchschnittlichen und minimalen Abstand zwischen zwei Punkten sowie das Verhältnis des nächstgelegenen Abstands zum durchschnittlichen Abstand (Distance_Closest / Distance_Average) auf. .

In diesen Darstellungen zeigte Joel, dass das Verhältnis der nächstgelegenen Entfernung zur durchschnittlichen Entfernung von 0 bei 0 Dimensionen auf ~ 0,8 bei 100 Dimensionen anstieg. Dies zeigt die grundlegende Herausforderung der Dimensionalität bei Verwendung des Algorithmus für k-nächste Nachbarn. Wenn die Anzahl der Dimensionen zunimmt und sich das Verhältnis der nächsten Entfernung zur durchschnittlichen Entfernung 1 nähert, nimmt die Vorhersagekraft des Algorithmus ab. Wenn der nächste Punkt fast so weit entfernt ist wie der Durchschnittspunkt, hat er nur eine geringfügig höhere Vorhersagekraft als der Durchschnittspunkt.

David Refaeli
quelle

Fluch der Dimensionalität: kNN-Klassifikator

Antworten: