Fluch der Dimensionalität

aus Wikipedia, der freien Enzyklopädie
Ein einfaches Beispiel für den Fluch der Dimensionalität: Ein Zentimeter besteht aus 10 Millimetern, ein Quadratzentimeter hingegen aus 100 Quadratmillimetern.

Fluch der Dimensionalität ist ein Begriff, der von Richard Bellman eingeführt wurde, um den rapiden Anstieg im Volumen beim Hinzufügen weiterer Dimensionen in einen mathematischen Raum zu beschreiben.

Leo Breiman beschreibt beispielhaft, dass 100 Beobachtungen den eindimensionalen Raum der reellen Zahlen zwischen 0 und 1 gut abdecken. Aus diesen Beobachtungen lässt sich ein Histogramm berechnen und Schlussfolgerungen lassen sich ziehen. Werden vergleichsweise in einem 10-dimensionalen Raum der gleichen Art (jede Dimension kann Werte zwischen 0 und 1 annehmen) 100 Stichproben gesammelt, sind dies isolierte Punkte, die den Raum nicht ausreichend abdecken, um sinnvolle Aussagen über diesen Raum zu treffen. Um eine ähnliche Abdeckung wie im eindimensionalen Raum zu erreichen, müssen 10010=1020 Stichproben gezogen werden, was einen wesentlich höheren Aufwand zur Folge hat.

Auswirkung auf Distanzfunktionen

Eine oft zitierte Formulierung des „Fluchs“ besagt, dass für verschiedene Arten von zufälligen Verteilungen der Datensätze der Unterschied zwischen der kleinsten und der größten Distanz zwischen Datensätzen im Vergleich zur kleinsten Distanz beliebig klein wird, wenn sich die Dimensionalität d erhöht (mit anderen Worten: die kleinste und größte Distanz unterscheiden sich nur noch relativ wenig),[1] und daher für die betreffenden Verteilungen in hochdimensionalen Räumen die Ergebnisse von Distanzfunktionen (und darauf basierenden Algorithmen) nicht mehr brauchbar sind. Dies lässt sich formalisieren als

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lim_{d \to \infty} \frac{\text{dist}_\text{max} - \text{dist}_\text{min}}{\text{dist}_\text{min}} = 0}

Aktuelle Forschungsergebnisse deuten jedoch darauf hin, dass nicht die reine Anzahl der Dimensionen ausschlaggebend ist,[2] da zusätzliche relevante Informationen die Daten besser trennen können. Lediglich zur Trennung „irrelevante“ zusätzliche Dimensionen verursachen den Effekt. Während die exakten Distanzwerte ähnlicher werden, bleibt dann jedoch die daraus resultierende Reihenfolge stabil. Clusteranalyse und Ausreißererkennung ist mit geeigneten Methoden weiterhin möglich.[3]

Eine weitere Möglichkeit, den „Fluch“ zu charakterisieren, bietet der Vergleich zwischen einer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} -dimensionalen Hypersphäre mit Radius Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} und einem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} -dimensionalen Hyperwürfel mit Seitenlängen . Das Volumen der Hypersphäre ist gegeben durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V_\text{Sphäre} = \frac{2r^d\pi^{d/2}}{d \; \Gamma(d/2)}} ,

wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Gamma} die Gamma-Funktion ist, und das Volumen des Hyperwürfels ist gegeben durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V_\text{Würfel} = (2r)^d} . Betrachten wir nun den Quotienten, so fällt auf, dass das Volumen der Hypersphäre im Vergleich zum Volumen des Hyperwürfels mit steigender Dimension sehr klein („insignifikant“) wird, denn

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{V_\text{Sphäre}}{V_\text{Würfel}} = \frac{\frac{2r^d\pi^{d/2}}{d \; \Gamma(d/2)}}{(2r)^d} =\frac{\pi^{d/2}}{d2^{d-1}\Gamma(d/2)}\rightarrow 0} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d \rightarrow \infty} .

Diese Konvergenz lässt sich durch die Abschätzung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{\pi^{d/2}}{d2^{d-1}\Gamma(d/2)} < \frac{(2^2)^{d/2}}{d2^{d-1}\Gamma(d/2)} = \frac{2^d}{d2^{d-1}\Gamma(d/2)} = \frac{2}{d \Gamma(d/2)} \rightarrow 0 } für Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle d\rightarrow \infty }

zeigen, wobei verwendet wird, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi = 3{,}14\ldots < 4 = 2^2 } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Gamma(x) > 0 } für .

Maschinelles Lernen

Der Fluch der Dimensionalität ist eine ernst zu nehmende Hürde bei Maschinellen-Lern-Problemen, die von wenigen Stichprobenelementen die Struktur eines hochdimensionalen Raumes lernen müssen.

Indexstrukturen

Viele Indexstrukturen sind entweder distanzbasiert oder versuchen, den Raum dimensionsweise zu teilen. Diese Verfahren haben meist Probleme mit hochdimensionalen Daten, da entweder die Distanzwerte nicht mehr aussagekräftig genug sind oder die Anzahl der Dimensionen und die daraus resultierenden Partitionsmöglichkeiten Probleme bereiten.

Numerische Integration

Bei der numerischen Integration spielt der Fluch der Dimensionalität ebenfalls eine große Rolle, da die Anzahl der benötigten Funktionsauswertungen bei einfachen Algorithmen wie der Trapezregel exponentiell mit der Anzahl der Dimensionen steigt. Das führt dazu, dass die Konvergenzgeschwindigkeit drastisch abnimmt. Bei einfachen Aufgabenstellungen lässt sich dieses Problem mittels Monte-Carlo-Verfahren umgehen, da diese nicht von der Dimensionalität abhängig sind. Ansonsten werden hierarchische Zerlegungsverfahren verwendet.

Einzelnachweise

  1. ↑ K. Beyer, J. Goldstein, R. Ramakrishnan, U. Shaft: When is “Nearest Neighbor” Meaningful? In: Proc. 7th International Conference on Database Theory - ICDT’99. LNCS 1540. Springer, 1999, ISBN 978-3-540-65452-0, S. 217, doi:10.1007/3-540-49257-7_15.
  2. ↑ M. E. Houle, H.-P. Kriegel, P. Kröger, E. Schubert, A. Zimek: Can Shared-Neighbor Distances Defeat the Curse of Dimensionality? In: Proc. 21st International Conference on Scientific and Statistical Database Management (SSDBM). Springer, Heidelberg, Germany 2010, doi:10.1007/978-3-642-13818-8_34.
  3. ↑ A. Zimek, E. Schubert, H.-P. Kriegel: A survey on unsupervised outlier detection in high-dimensional numerical data. In: Statistical Analysis and Data Mining. Band 5, Nr. 5, 2012, S. 363–387, doi:10.1002/sam.11161.

Quellen

  • Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.
Abgerufen von „https://de.wikiup.org/index.php?title=Fluch_der_Dimensionalität&oldid=222854289“