Authors: Bernholt, Thorsten
Title: Effiziente Algorithmen und Komplexität in der robusten Statistik
Language (ISO): de
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.
Subject Headings: Algorithmen
Robuste Statistik
Algorithmische Geometrie
Zeitreihen
time series
algorithms
robust statistics
computational geometry
outlier
URI: http://hdl.handle.net/2003/23027
http://dx.doi.org/10.17877/DE290R-17
Issue Date: 2006-10-26T13:40:19Z
Appears in Collections:LS 02 Komplexitätstheorie und Effiziente Algorithmen

Files in This Item:
File Description SizeFormat 
diss_25.10.2006b_final.pdfDNB941.5 kBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.