Fluch der Dimensionalität

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 gibt als ein Beispiel den Fakt, dass 100 Beobachtungen den eindimensionalen Raum der reellen Zahlen zwischen 0 und 1 ziemlich gut abdecken. Aus diesen Beobachtungen lässt sich zum Beispiel ein Histogramm berechnen und Schlussfolgerungen lassen sich ziehen. Wenn man jetzt in einem 10-dimensionalen Raum der gleichen Art (jede Dimension kann Werte zwischen 0 und 1 annehmen) 100 Stichproben sammelt, sind dies isolierte Punkte, die den Raum bei weitem nicht abdecken. Um eine ähnliche Abdeckung wie im eindimensionalen Raum zu erreichen, müsste man 10²⁰ Stichproben ziehen - was zumindest ein sehr aufwändiges Unterfangen wäre.

Auswirkung auf Distanzfunktionen

Eine oft zitierte Formulierung des „Fluchs“ besagt, dass der Unterschied zwischen der kleinsten und der größten Distanz im Datensatz im Vergleich zur kleinsten Distanz beliebig klein wird^[1], und daher in hochdimensionalen Räumen die Ergebnisse von Distanzfunktionen (und darauf basierenden Algorithmen) nicht mehr brauchbar sind. Dies lässt sich formalisieren als

$\lim_{d \to \infty} \frac{dist_\max - dist_\min}{dist_\min} \to 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, eine Clusteranalyse mit geeigneten Methoden weiterhin möglich.

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.
2. ↑ Michael E. Houle, Hans-Peter Kriegel, Peer Kröger, Erich Schubert, Arthur 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.

Quellen

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