Fluch der Dimensionalität

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}$.

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.

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.

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.

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.

• Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.