imported>Doc z: Änderung 252410438 von 2A01:599:90D:3548:A0D7:2C56:EA8A:880F rückgängig gemacht; s. WP:LIT

2025-01-19T13:17:58Z

Änderung 252410438 von 2A01:599:90D:3548:A0D7:2C56:EA8A:880F rückgängig gemacht; s. WP:LIT

Neue Seite

[[Datei:Area conversion - square mm in a square cm.png|mini|320px|Ein einfaches Beispiel für den ''Fluch der Dimensionalität'': Ein [[Zentimeter]] besteht aus 10 [[Millimeter]]n, ein [[Quadratzentimeter]] hingegen aus 100 [[Quadratmillimeter]]n.]]
'''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 [[Raum (Mathematik)|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<sup>10</sup>=10<sup>20</sup> 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),<ref>{{Literatur
| DOI = 10.1007/3-540-49257-7_15
| Titel = When is “Nearest Neighbor” Meaningful?
| Jahr = 1999
| Autor = K. Beyer, J. Goldstein, R. Ramakrishnan, U. Shaft
| Sammelwerk = Proc. 7th International Conference on Database Theory - ICDT’99
| Band = LNCS 1540
| Seiten = 217
| Verlag = Springer
| ISBN = 978-3-540-65452-0
}}</ref> 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

:<math>\lim_{d \to \infty} \frac{\text{dist}_\text{max} - \text{dist}_\text{min}}{\text{dist}_\text{min}} = 0</math>

Aktuelle Forschungsergebnisse deuten jedoch darauf hin, dass nicht die reine Anzahl der Dimensionen ausschlaggebend ist,<ref>{{Literatur
| Autor=M. E. Houle, [[Hans-Peter Kriegel|H.-P. Kriegel]], P. Kröger, E. Schubert, A. Zimek
| Jahr=2010
| Titel=Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?
| Sammelwerk=Proc. 21st International Conference on Scientific and Statistical Database Management (SSDBM)
| Ort=Heidelberg, Germany
| Verlag=Springer
| DOI=10.1007/978-3-642-13818-8_34
}}</ref> 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ßer]]erkennung ist mit geeigneten Methoden weiterhin möglich.<ref>{{Literatur
| Autor = A. Zimek, E. Schubert, [[Hans-Peter Kriegel|H.-P. Kriegel]]
| Titel = A survey on unsupervised outlier detection in high-dimensional numerical data
| DOI = 10.1002/sam.11161
| Sammelwerk = Statistical Analysis and Data Mining
| Band = 5
| Nummer = 5
| Seiten = 363-387
| Jahr = 2012
}}</ref>

Eine weitere Möglichkeit, den „Fluch“ zu charakterisieren, bietet der Vergleich zwischen einer <math>d</math>-dimensionalen [[Sphäre (Mathematik)|Hypersphäre]] mit Radius <math>r</math> und einem <math>d</math>-dimensionalen [[Hyperwürfel]] mit Seitenlängen <math>2r</math>. Das Volumen der Hypersphäre ist gegeben durch
:<math>V_\text{Sphäre} = \frac{2r^d\pi^{d/2}}{d \; \Gamma(d/2)}</math>,
wobei <math>\Gamma</math> die [[Gammafunktion]] ist, und das Volumen des Hyperwürfels ist gegeben durch <math>V_\text{Würfel} = (2r)^d</math>. 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

:<math>\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</math> für <math>d \rightarrow \infty</math>.

Diese Konvergenz lässt sich durch die Abschätzung

:<math>\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 </math> für <math>d \rightarrow \infty</math>

zeigen, wobei verwendet wird, dass <math>\pi = 3{,}14\ldots < 4 = 2^2 </math> und <math>\Gamma(x) > 0 </math> für <math>x > 0 </math>.
== Maschinelles Lernen ==
Der Fluch der Dimensionalität ist eine ernst zu nehmende Hürde bei [[Maschinelles Lernen|Maschinellen-Lern]]-Problemen, die von wenigen Stichprobenelementen die Struktur eines hochdimensionalen Raumes lernen müssen.

== Indexstrukturen ==
Viele [[Datenbankindex|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 [[Numerische Integration|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 ==
<references />

== Quellen ==

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

[[Kategorie:Numerische Mathematik]]
[[Kategorie:Multivariate Statistik]]

Fluch der Dimensionalität - Versionsgeschichte

imported>Doc z: Änderung 252410438 von 2A01:599:90D:3548:A0D7:2C56:EA8A:880F rückgängig gemacht; s. WP:LIT