Fluch der Dimensionalität

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 100^10=10^20 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

${\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 ${\displaystyle d}$-dimensionalen Hypersphäre mit Radius ${\displaystyle r}$ und einem ${\displaystyle d}$-dimensionalen Hyperwürfel mit Seitenlängen ${\displaystyle 2r}$. Das Volumen der Hypersphäre ist gegeben durch

${\displaystyle V_{\text{Sphäre}}={\frac {2r^{d}\pi ^{d/2}}{d\;\Gamma (d/2)}}}$,

wobei ${\displaystyle \Gamma }$ die Gammafunktion ist, und das Volumen des Hyperwürfels ist gegeben durch ${\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

${\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 ${\displaystyle d\rightarrow \infty }$.

Diese Konvergenz lässt sich durch die Abschätzung

${\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 ${\displaystyle d\rightarrow \infty }$

zeigen, wobei verwendet wird, dass ${\displaystyle \pi =3{,}14\ldots <4=2^{2}}$ und ${\displaystyle \Gamma (x)>0}$ für ${\displaystyle x>0}$.

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.