Effiziente Algorithmen und Komplexität in der robusten Statistik
Loading...
Date
2006-10-26T13:40:19Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Ein Ausgangspunkt der robusten Statistik ist, dass der
Least-Squares-Schätzer zwar einfach zu berechnen ist, aber Probleme
mit Ausreißern hat. Es genügt, dass ein Punkt des Datensatzes von
den anderen weit entfernt ist, um das Ergebnis stark zu verfälschen.
Die robuste Statistik hat das Ziel, Schätzer zu finden, die wenig
sensitiv gegenüber Ausreißern sind. Allerdings haben diese robusten
Schätzer häufig den Nachteil, dass ad hoc kein schneller Algorithmus
für ihre Berechnung zur Verfügung steht. In dieser Arbeit werden neue
Algorithmen für einige robuste Schätzer vorgestellt:
Für Punktmengen in der Ebene der Least-Quartile-Difference-Schätzer
mit einer Rechenzeit von grob O(n^2 log n) und das Multiresolutions-
Kriterium mit einer Rechenzeit von O(n log n).
Im Kontext von Zeitreihen-Daten werden Update-Algorithmen für den
Repeated-Median-Schätzer mit Update-Zeit O(n) und den Median-Absolute-
Deviation-Schätzer mit Update-Zeit O(log n) vorgestellt.
Für d-dimensionale Punktmengen werden Exponentialzeit-Algorithmen
für den Least-Median-of-Squares-Schätzer und den Minimum-Covariance-
Determinant-Schätzer vorgestellt. Abschließend wird die NP-Härte
vieler robuster Schätzer bewiesen sowie eine praxisrelevante
und schwierige Eingabe angegeben, so dass die Suchheuristik Fast-LTS
nur mit einer exponentiell kleinen Wahrscheinlichkeit das Optimum
findet. Damit wird aufgezeigt, dass die theoretischen Eigenschaften
robuster Schätzer in die Praxis nur schwer zu verwirklichen sind.
Description
Table of contents
Keywords
Algorithmen, Robuste Statistik, Algorithmische Geometrie, Zeitreihen, time series, algorithms, robust statistics, computational geometry, outlier