Buchvorstellung
Buchcover

Er ist ein Mathematiker und also hartnäckig.
Johann Wolfgang von Goethe

Ausgleichender Kreis mittels Least-Median-Square (LMS) als Online-Rechner

Die Ergebnisse einer Ausgleichung sind idR. unbrauchbar, wenn mehrere grobe Fehler im Datenbestand vorhanden sind. Das klassische Data-Snooping versagt, wenn die Anzahl und Größe der Ausreißer zunimmt (z.B. Hekimoglu und Koch, 2000). Dass sich hier der Einsatz eines sogenannten robusten Schätzers, der weitgehend unempfindlich gegenüber Messfehlern ist, anbietet, wurde mit der Ausgleichungssoftware JAG3D am Beispiel eines Nivellements und eines räumlichen Rückwärtsschnittes anschaulich demonstriert. Dass hierfür auch die Verwendung des bekannten Standardwerkzeugs EXCEL genügen kann, wurde bei der Vorstellung des SOLVERS Add-in diskutiert. In diesem Beitrag soll der Fokus auf der praktischen Umsetzung bei einer robusten Parameterbestimmung liegen. Neben einer kurzen Herleitung soll ein kleines Rechenbeispiel, welches bei aktivem JavaScript mit eigenen Werten durchgerechnet werden kann, den Sachverhalt am Beispiel des ausgleichenden Kreises verbildlichen.

Die Effektivität dieser robusten Schätzer wird in der Literatur oft an ihrem Bruch- und Hebelpunkt gemessen (vgl. Wicki, 1999). Mit diesen Angaben ist zum einen die (prozentuale) Anzahl der Ausreißer im Datenbestand gemeint, bei der der Algorithmus noch die korrekte Lösung liefert, und zum anderen wie der Schätzer auf fehlerbehaftete Daten reagiert, die weit von der Masse der übrigen Beobachtungen entfernt liegen. Eine sehr robuste Bestimmung eines Messwertes aus einer Beobachtungsreihe ist der Median. Hierbei ist der Median xmed der Wert einer der Größe nach geordnet Messreihe, der sich wie folgt ergibt:


Definition Median
Definition Median

Worin n die Anzahl der Messwerte in der Messreihe ist.

Für eine ungerade Anzahl an Werten ist der Median somit der Wert in der Mitte der sortierten Reihe; bei gerade Anzahl ergibt er sich aus dem Mittelwert der beiden mittleren Werte. Beispiel: Für die Reihe [4, 7, 5, 6, 12, 8, 6, 5, 6] ist 6 der Median und das arithmetische Mittel 6.6. Beide Werte liegen hier verhältnismäßig dicht beisammen. Dies ändert sich aber, wenn eine weitere Messung mit dem Wert 100 in die Reihe eingefügt wird. Während der Median unverändert 6 beträgt, wirkt sich die neue Messung spürbar auf den Mittelwert, der nun 15.9 beträgt, aus. Es lässt sich zeigen, dass der Median einen Bruchpunkt von 50% hat. Dies ist gleichzeitig das Maximal mögliche (Wicki, 1999).


Vorgehensweise bei der Anwendung des Least-Median-Square (LMS)

Diese positiven Eigenschaften des Medians hat Rousseeuw (1984) erkannt und einen robusten Schätzer - den Least-Median-Square (LMS) - abgeleitet, der auch für mehrdimensionale Problemstellungen nutzbar ist. Die Zielfunktion lautet:


LMS-Zielfunktion
Zielfunktion

Die grundlegende Vorgehensweise soll am Beispiel der Kreisausgleichung nachfolgend erklärt werden. Gegeben sind hierzu n Punkte P, die einen Kreis beschreiben. Gesucht sind der Mittelpunkt M und der Radius R des Kreises. Unklar ist jedoch, ob das Datenmaterial frei von groben Fehlern ist.

Bei der Anwendung des Least-Median-Square werden aus den n Beobachtungen j Unterklassen (Sub-Samples) gebildet, die genau so viel Punkte u enthalten, wie zur Berechnung notwendig sind. Der Kreis ist eindeutig bestimmt, wenn u=3 Punkte, die nicht auf einer Geraden liegen, in einem Sub-Sample sind. Aus jedem j-ten Sub-Sample werden die Kreisparameter Kj(M, R) (Kreismittelpunkt und –radius) bestimmt und die Verbesserung v zu den restlichen Punkten ermittelt. Von diesen quadrierten Verbesserungen wird letztlich der Median mj zusammen mit dem Sub-Sample gespeichert.


Median der Verbesserungen eines Sets
Median der Verbesserungen

Dieser Vorgang wird für alle j Sub-Samples wiederholt. Der Kreis, bei dem mj minimal war - also am kleinsten -, ist abschließend die Lösung des LMS, da sie die o.g. Minimierungsfunktion erfüllt.

Die bei der Berechnung entstehende j Permutation sind letztlich das große Problem dieses Verfahrens, da diese bei großen Punktwolken extrem schnell anwachsen und zu sehr zeitintensiven Berechnungen führen. Die Bestimmung der maximalen Anzahl der j Sub-Samples kann über die Binomialkoeffizienten erfolgen (Jäger et al., 2005):


Binomialkoeffizienten
Binomialkoeffizienten

Im Fall der Kreisausgleichung, bei der u=3 ist, lassen sich somit bei gerade einmal n=10 Punkten bereits j=120 Kombinationen bilden. Bei 20 Punkten sind es 1140 und bei 100 Punkten sogar 161700 mögliche Kombinationen. Da jedoch alle Permutationen nur dann benötigt werden, wenn wirklich die Hälfte des Datenmaterials fehlerbehaftet ist, kann die Anzahl der Permutationen auch reduziert werden, wenn mit weniger Ausreißer zu rechnen ist. Die Wahrscheinlichkeit P, das mindestens ein fehlerfreies Sub-Sample bei einer angenommenen Anzahl an Ausreißern ε in der Auswahl enthalten ist, ergibt sich aus (Rousseeuw und Leroy, 2003):


Wahrscheinlichkeit P eines fehlerfreien Subsets
Wahrscheinlichkeit P

Mit einer gegeben Wahrscheinlichkeit P, die ungefähr bei 1 liegt (z.B. 0.95 oder 0.99), lässt sich somit j bestimmen:


Anzahl der notwendigen Subsets
Anzahl nötigter Subsets

Nehmen wir an, das im Datenmaterial ε=35% fehlerbehaftetes Material enthalten ist und eine Wahrscheinlichkeit P=0.99 erreicht werden soll, dann beträgt j=15 für einen Kreis. Bei praktischen Anwendungen wird meist über diese Mindestanzahl hinausgegangen, um auf der sicheren Seite zu sein.

Die Lösung, die der LMS liefert, sind die Parameter eines Sub-Sets. Dies bedeutet, dass die Kreisparameter K lediglich aus drei Punkten bestimmt werden und nicht von der Anzahl der Beobachtungen abhängt. Deshalb wird idR. nach der Parameterbestimmung mittels LMS noch eine Reweighted-Least-Square (RLS) durchgeführt, bei denen alle Punkte, die vermutlich keine Ausreißer sind, in die Lösung mit einbezogen werden. Die Berechnung erfolgt dabei im bekannten Gauß-Markov-Modell oder Gauß-Helmert-Modell, wobei die Gewichtsmatrix modifiziert wird. Die Modifizierung kann dabei nach verschiedenen Kriterien erfolgen. Rousseeuw und Leroy (2003) schlagen folgenden Aufbau vor:


Gewichtung der einzelnen Beobachtungen im RLS
Gewichtung der einzelnen Beobachtungen im RLS

Weitere Ansätze sind bei Wicki (1999) oder Jäger et al. (2005) zu finden. In diesem Artikel wollen wir diesen Schritt nicht näher beleuchten und uns dem Beispiel der Kreisausgleichung nun widmen.


Berechnung eines Kreises aus drei Punkten

Der Kreismittelpunkt M und der Radius R können bei Vorgabe von drei Punkten, die nicht auf einer Geraden liegen, eindeutig bestimmt werden. Hierfür muss lediglich der Umkreis, der durch das Dreieck der drei Punkte definiert ist, bestimmt werden. Der Kreismittelpunkt M fällt dabei mit dem Schnittpunkt der Mittelsenkrechten im Dreieck zusammen.


Kreis aus drei Punkten
Kreis aus drei Punkten

Um den Schnittpunkt der Mittelsenkrechten im Dreieck zu bestimmen, sind diese durch eine Geradengleichung zu beschreiben. Der Anstieg einer Mittelsenkrechten ergibt sich dabei aus dem negativen reziproken Anstieg der betrachteten Dreiecksseite. Hierbei reicht es, wenn zwei Anstiege zB.: ma und mc berechnet werden. Nachfolgend die Formel für ma:


Berechnung des Anstiegs einer Geraden
Geradenanstieg

Die noch fehlenden Absolutglieder na und nc  werden anschließend durch Umstellen der Geradengleichung bestimmt, wobei wir als Punkt auf der Geraden den Mittelpunkt der betrachteten Dreiecksseite nutzen (Berechnung für nc erfolgt analog):


Absolutglied der Geraden
Absolutglied der Geraden

Der Kreismittelpunkt M lässt sich nun durch Gleichsetzen zweiter Mittelsenkrechten bestimmen. Der Radius R ergibt sich anschließend durch Pythagoras zwischen dem Mittelpunkt M und einem Dreieckspunkt; hier Punkt A.


Bestimmung von Kreismittelpunkt und Radius
Bestimmung von Kreismittelpunkt und Radius

Robuste Kreisausgleichung

Ein einfaches Zahlenbeispiel, welches in der nachfolgenden Tabelle zusammengefasst ist, soll die oben beschriebene Vorgehensweise verdeutlichen. Hierzu wurden 8 Punkte (A-H) gewählt, die auf einem verschobenen Einheitskreis liegen. Neben diesen 8 Kreispunkten wurden 4 weitere Punkte (I-L) ergänzt, die extrem weit von diesem Kreis entfernt liegen. Würde der Kreis durch eine kleinste Quadrate Ausgleichung bestimmt werden, so lautet der Kreismittelpunkt M = [-6.4m / 77.9m] und der Radius beträgt R = 74.1m. Die aus der robusten Schätzung erhaltenen Werte sind hingegen M = [5.0 / 10.0] und R = 1.0m – ein deutlicher Unterschied, der die Schwächen der Ausgleichung bei grob fehlerbehafteten Beobachtungsmaterial verdeutlicht.

Robuste Kreisausgleichung
Robuste Schätzung eines Kreises mittles Least-Median-Square (LMS)
Kreispunkte
 A	  5.0000	 11.0000
 B	  6.0000	 10.0000
 C	  4.0000	 10.0000
 D	  5.0000	  9.0000
 E	  5.7071	 10.7071
 F	  4.2929	  9.2929
 G	  5.7071	  9.2929
 H	  4.2929	 10.7071
 I	 75.0000	110.0000
 J	-70.0000	110.0000
 K	  5.0000	-40.0000
 L	 55.0000	 85.0000
 
Robuste Standardabweichung σ0 0.0000183 m  
Kreismittelpunkt M 5.0000 m 10.0000 m
Kreisradius R 1.0000 m  
Berechenbare Permutationen 219  
Punkte der Kreislösung C, E, G  

Zusammenfassung

In diesem Artikel wurde der auf Rousseeuw (1984) zurückgehende robuste Schätzer Least-Media-Square vorgestellt. Am Beispiel des ausgleichenden Kreises wurde die praktische Vorgehensweise demonstriert, die sich auch auf andere Problemstellungen übertragen lässt. Für den Vergleich zwischen der Lösung nach der Methode der Kleinsten Quadrate und dem Least-Median-Square wurde die FormFittingToolbox, bei der das strengen Gauß-Helmert-Modell implementiert ist, benutzt.


Quellen

Verwendete Literatur, die nicht der Bibliothek entnommen ist:

  • Hekimoglu S., Koch K.-R. (2000), How can reliability of the test for outliers be measured?, Allgemeine Vermessungs-Nachrichten (AVN)
  • Rousseeuw, P.J. (1984), Least Median of Squares Regression, Journal of the American Statistical Association

13.03.2010 von Michael Lösler