Maschinelles Lernen Fluch der Dimensionalität erklärt?

Ich habe Probleme, den Fluch der Dimensionalität zu verstehen. Insbesondere bin ich beim Ausführen des scikit-learnTutorials in Python darauf gestoßen. Kann mir bitte jemand das untenstehende auf einfachere Weise erklären? Entschuldigung, ich habe die längste Zeit versucht zu verstehen und kann nicht verstehen, wie sie auf die Berechnung der Anzahl der Trainingsbeispiele gekommen sind, um einen effizienten KNN-Schätzer zu erhalten.

Hier ist die Erklärung:

Damit ein Schätzer effektiv ist, muss der Abstand zwischen benachbarten Punkten kleiner als ein Wert d sein, was vom Problem abhängt. In einer Dimension erfordert dies durchschnittlich n ~ 1 / d Punkte. Wenn im Kontext des obigen KNN-Beispiels die Daten durch nur ein Merkmal mit Werten im Bereich von 0 bis 1 und mit n Trainingsbeobachtungen beschrieben werden, sind neue Daten nicht weiter als 1 / n entfernt. Daher ist die Entscheidungsregel für den nächsten Nachbarn effizient, sobald 1 / n im Vergleich zur Skala der Merkmalsvariationen zwischen Klassen klein ist.

Wenn die Anzahl der Features p ist, benötigen Sie jetzt n ~ 1 / d ^ p Punkte. Nehmen wir an, wir benötigen 10 Punkte in einer Dimension: Jetzt werden 10 ^ p Punkte in p Dimensionen benötigt, um den Raum [0, 1] zu ebnen. Wenn p groß wird, nimmt die Anzahl der für einen guten Schätzer erforderlichen Trainingspunkte exponentiell zu.

hier verlinken

EDIT: soll auch die tilde ( ~) in diesem beispiel ungefähr darstellen? oder der Python-Tilde-Operator?

Übersetzen dieses Absatzes:

Es gebe eine Reihe von Features, die einen Datenpunkt beschreiben. Vielleicht schaust du auf das Wetter. Zu diesen Funktionen gehören beispielsweise Temperatur, Luftfeuchtigkeit, Tageszeit usw. Jeder Datenpunkt verfügt möglicherweise über eine Funktion (wenn Sie nur die Temperatur anzeigen) oder über zwei Funktionen (wenn Sie die Temperatur anzeigen) und Luftfeuchtigkeit) und so weiter. Dieser Absatz besagt, dass es umso schwieriger ist, basierend auf der Anzahl der Dimensionen Ihrer Daten (wie viele Features sie haben), einen Schätzer zu erstellen. Dies liegt daran, dass Sie, wenn Sie nur ein Merkmal von Daten oder eindimensionale Daten haben, beim Zeichnen dieser Daten ein Liniendiagramm erhalten und sich ein Liniendiagramm zwischen beispielsweise 0 und 50 Grad C vorstellen, das nur ausreicht 50 zufällige Punkte vor jedem Datenpunkt sind ungefähr 1 Grad von jedem anderen Datenpunkt entfernt. Nun lass' Wenn Sie über 2 Dimensionen nachdenken und über Luftfeuchtigkeit und Temperatur sprechen, ist es jetzt schwieriger, d so zu finden, dass alle Punkte innerhalb von "d" -Einheiten voneinander liegen. Stellen Sie sich vor, die Temperatur liegt immer noch zwischen 0 und 50, aber jetzt liegt die Luftfeuchtigkeit auch zwischen 0 und 100%. Wie viele zufällige Punkte werden benötigt, um alle Punkte innerhalb von 1 oder 2 zu erreichen? Jetzt sind es 100 * 50 oder ~ 5.000! Stellen Sie sich nun 3 Dimensionen usw. vor. Sie benötigen deutlich mehr Punkte, um sicherzustellen, dass jeder Punkt innerhalb von d eines anderen Punktes liegt. Um Ihnen das Leben zu erleichtern, nehmen Sie an, dass "d" 1 ist, und sehen Sie, was passiert. Ich hoffe, das hilft! Wie viele zufällige Punkte werden benötigt, um alle Punkte innerhalb von 1 oder 2 zu erreichen? Jetzt sind es 100 * 50 oder ~ 5.000! Stellen Sie sich nun 3 Dimensionen usw. vor. Sie benötigen deutlich mehr Punkte, um sicherzustellen, dass jeder Punkt innerhalb von d eines anderen Punktes liegt. Um Ihnen das Leben zu erleichtern, nehmen Sie an, dass "d" 1 ist, und sehen Sie, was passiert. Ich hoffe, das hilft! Wie viele zufällige Punkte werden benötigt, um alle Punkte innerhalb von 1 oder 2 zu erreichen? Jetzt sind es 100 * 50 oder ~ 5.000! Stellen Sie sich nun 3 Dimensionen usw. vor. Sie benötigen deutlich mehr Punkte, um sicherzustellen, dass jeder Punkt innerhalb von d eines anderen Punktes liegt. Um Ihnen das Leben zu erleichtern, nehmen Sie an, dass "d" 1 ist, und sehen Sie, was passiert. Ich hoffe, das hilft!

matty-d hat bereits eine sehr gute Antwort geliefert, aber ich habe eine andere Antwort gefunden, die dieses Problem ebenfalls erklärt, und zwar von einem Quora-Benutzer, Kevin Lacker:

Nehmen wir an, Sie haben eine gerade Linie, die 100 Meter lang ist, und Sie haben irgendwo einen Penny darauf geworfen. Es wäre nicht zu schwer zu finden. Sie gehen die Linie entlang und es dauert zwei Minuten.

Nehmen wir an, Sie haben ein Quadrat von 100 Metern auf jeder Seite und irgendwo darauf einen Penny geworfen. Es wäre ziemlich schwer, über zwei zusammengeklebte Fußballfelder zu suchen. Es könnte Tage dauern.

Jetzt ein Würfel mit einem Durchmesser von 100 Metern. Das ist wie das Durchsuchen eines 30-stöckigen Gebäudes in der Größe eines Fußballstadions. Pfui.

Die Schwierigkeit, den Raum zu durchsuchen, wird immer größer härter , wie Sie mehr Dimensionen haben. Sie können dies nicht intuitiv erkennen, wenn es nur in mathematischen Formeln angegeben ist, da sie alle die gleiche "Breite" haben. Das ist der Fluch der Dimensionalität. Es bekommt einen Namen, weil es nicht intuitiv, nützlich und doch einfach ist.

Dieses Beispiel kann eine Vorstellung von dem Problem geben, ist jedoch eigentlich kein strenger Beweis: Dies ist nur ein Beispiel, bei dem viele Stichproben erforderlich sind, um eine "gute" Raumabdeckung zu erzielen. Es könnte (und es gibt in der Tat bereits z. B. Sechsecke in 2D) viel effizientere Abdeckungen geben als ein reguläres Gitter ... (der anspruchsvolle Bereich von Sequenzen mit geringer Diskrepanz ist diesem gewidmet) ... und dies auch mit solch besseren Abdeckungen beweisen Es gibt immer noch einen Fluch der Dimensionalität, ein ganz anderes Thema. Tatsächlich gibt es in bestimmten Funktionsräumen sogar Möglichkeiten, dieses offensichtliche Problem zu umgehen.