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 Bearbeiten
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), 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
Aktuelle Forschungsergebnisse deuten jedoch darauf hin, dass nicht die reine Anzahl der Dimensionen ausschlaggebend ist, 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.
Eine weitere Möglichkeit, den „Fluch“ zu charakterisieren, bietet der Vergleich zwischen einer -dimensionalen Hypersphäre mit Radius und einem -dimensionalen Hyperwürfel mit Seitenlängen . Das Volumen der Hypersphäre ist gegeben durch
wobei die Gammafunktion ist, und das Volumen des Hyperwürfels ist gegeben durch . 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
Diese Konvergenz lässt sich durch die Abschätzung
zeigen, wobei verwendet wird, dass und für .
Maschinelles Lernen Bearbeiten
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 Bearbeiten
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 Bearbeiten
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 Bearbeiten
- 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.
- 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.
- 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 Bearbeiten
- Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.