Lokale Hauptkurven (Local Principal Curves)

From Teachwiki
Jump to: navigation, search

Diese Arbeit fasst den Artikel „Local Principal Curves“ von Jochen Einbeck, Gerhard Tutz und Ludger Evers aus Statistics and Computing 15: 301-313, 2005 zusammen.

Einleitung[edit]

Eines der klassischen Probleme in der Statistik ist die Dimensionsreduktion. Mehrdimensionale Datensätze sollen in ihrer Komplexität reduziert werden, um ihre Beschreibung bzw. Interpretation zu erleichtern, ohne diese jedoch durch einen zu hohen Verlust an Informationen abzuschwächen. Die Hauptkomponentenanalyse ist ein wichtiges Verfahren zur Dimensionsreduktion. Die Hauptkomponenten sind dabei Linearkombinationen der ursprünglichen Variablen, wobei die erste Hauptkomponente für den größten Teil der Variation verantwortlich ist, die zweite Hauptkomponente für den zweitgrößten Teil usw. Im Gegensatz zur Regressionsanalyse wird hier keine Annahme über die Abhängigkeit zwischen den Variablen getroffen, sondern eine symmetrische Beziehung unterstellt. Die Hauptkurven, als Erweiterung der Hauptkomponenten können allgemein als glatte Kurven, die durch die Mitte eines Datensatzes verlaufen, definiert werden. Die verschiedenen Verfahren zur Berechnung der Hauptkurven unterscheiden sich jedoch in der Frage, wie die Mitte eines Datensatzes zu bestimmen sei. Die existierenden Algorithmen können grob in zwei Gruppen unterteilt werden:

Top-down Algorithmen beginnen mit einer geraden Linie, die durch den Datensatz verläuft. Meistens entspricht diese der ersten Hauptkomponente. Diese wird dann so ausgeweitet oder mit anderen Linien verbunden, dass die resultierende Kurve ausreichend gut durch die Datenmitte verläuft.

Bottom-up Algorithmen beziehen in jedem Schritt nur die Daten in der lokalen Umgebung des jeweils betrachteten Punktes zur Bestimmung der Kurve ein. Ein Beispiel für einen Bottom-up Ansatz ist der LPC (lokale Hauptkurven)-Algorithmus, der im folgenden Abschnitt im Detail beschrieben wird.

Algorithmus[edit]

Für eine d-dimensionale Datenwolke X_\mathrm{i}= (X_\mathrm{i1},..., X_\mathrm{id}) \in\R^d mit i=1,...,n wird eine glatte Kurve, die durch die Mitte der Beobachtungen verläuft, gesucht.

Schritt 1: Startpunkt[edit]

Der Startpunkt x_\mathrm{0} wird per Zufall aus den Beobachtungen ausgewählt. Dafür kommt jeder Punkt innerhalb oder nahe der Datenwolke in Frage. Handelt es sich dabei jedoch um einen Ausreißer, so wird der Algorithmus gleich im ersten Durchgang gestoppt und ein neuer Startpunkt ausgewählt. Für die folgenden Schritte wird x = x_\mathrm{0} gesetzt.

Schritt 2: lokaler Massenmittelpunkt[edit]

H sei eine Bandbreitenmatrix, K_\mathrm{H} eine d-dimensionale Kernelfunktion und alle Komponenten von X werden auf der gleichen Skala gemessen. Es wird H=\{h^2 \cdot I :h>0\}\, gesetzt, wobei I die d-dimensionale Identitätsmatrix ist. So ist der lokale Massenmittelpunkt um x gegeben durch:

\mu^x = \mu(x) =\frac{\sum_{i=1}^n K_\mathrm{H} (X_\mathrm{i}-x)X_\mathrm{i}}{\sum_{i=1}^n K_\mathrm{H} (X_\mathrm{i}-x)}

Die j-te Komponente von \mu^x wird mit \mu_j^x bezeichnet.

Schritt 3: erster lokaler Eigenvektor[edit]

Sei \Sigma^x die lokale Kovarianzmatrix von x, deren (j,k)-tes Element gegeben ist durch:

\sigma_\mathrm{jk}^x = \sum_{i=1}^n w_i(X_\mathrm{ij}-\mu_j^x)(X_\mathrm{ik}-\mu_k^x)

Mit den Gewichtungsfaktoren:

w_i=\frac{K_H(X_i-x)}{\sum_{i=1}^n K_H(X_i-x)}.

Die Jordan-Zerlegung von \Sigma^x ergibt:

\Sigma^x = \Gamma\Lambda\Gamma^\top.

\Lambda ist die Diagonalmatrix mit den absteigend nach der Größe sortierten Eigenwerten von \Sigma^x. Die Ladungsmatrix \Gamma enthält die zugehörigen Eigenvektoren. Die erste Spalte von \Gamma ist somit der erste Eigenvektor von \Sigma^x und wird im folgenden mit \gamma^x bezeichnet.

Schritt 4: neuer Wert[edit]

Von \mu^x ausgehend folgt man der ersten lokalen Hauptkomponente \gamma^x. Die lokale Hauptkomponentenlinie \nu^x wird parametriert durch:

\nu^x(t)=\mu^x+t\gamma^x\,

Ein neuer Wert für x ergibt sich durch:

x\,:=\mu^x+t_0\gamma^x\,

Der Wert für t_0 ist im Vorfeld festzulegen. Hier gilt t_0=h.

Schritt 5: Wiederholung Schritte 2 – 4[edit]

Wenn der Rand der Datenwolke erreicht oder ein vorher festgelegter Minimalwert für die Differenz der \mu^x in zwei aufeinander folgenden Durchgängen unterschritten wird, bleibt der Algorithmus stecken und liefert nahezu konstante Werte für \mu^x.

Die lokale Hauptkurve ergibt sich als Folge der einzelnen lokalen Massenmittelpunkte \mu^x.

Der LPC-Algorithmus wird in der folgenden Grafik veranschaulicht.

Abb. 1: Grafische Darstellung des LPC-Algorithmus
Lpc.png
Quelle: Einbeck et al., 2005

Ausgehend vom Startpunkt x_0=0 wird innerhalb des Kreises, dessen Radius der Bandbreite h entspricht, der lokale Massenmittelpunkt m berechnet. Die Bewegung von m entlang der ersten Hauptkomponente führt zum nächsten x-Wert 1. Innerhalb des Kreises um 1 mit dem Radius h wird wiederum ein lokaler Massenmittelpunkt m ermittelt usw. Die Verbindung der einzelnen m-Werte liefert die lokale Hauptkomponente.

Der Algorithmus gleicht zwei gegensätzliche Tendenzen aus: während die lokale Hauptkomponentenlinien nach „außen“ zeigen, erfolgt durch die Berechnung der lokalen Massenmittelpunkte eine Glättung nach „innen“.

Technische Details[edit]

  • Richtung beibehalten

Verändert sich die Orientierung der Eigenvektoren von einem Durchgang zum anderen, so „schlenkert“ der Algorithmus zwischen diesen beiden Punkten endlos hin und her. Daher ist in jeder „Runde“ zu überprüfen, ob die Richtung beibehalten wird. Dazu berechnet man den Cosinus des Winkels \alpha zwischen den jeweils aufeinanderfolgenden Eigenvektoren als deren Skalarprodukt:

cos(\alpha_\mathrm{(i)}^x)=\gamma_\mathrm{(i-1)}^x \circ \gamma_\mathrm{(i)}^x

Ist cos(\alpha_\mathrm{(i)}^x)< 0, so wird \gamma_\mathrm{(i)}^x:=-\gamma_\mathrm{(i)}^x gesetzt und Algorithmus fortgesetzt.

  • Rückwärts gehen

Folgt man von x_0 aus den lokalen Hauptkomponenten, so gelangt man an ein „Ende“ der Datenwolke. Um jedoch den gesamten Datensatz abzudecken, muss auch das andere „Ende“ berücksichtigt werden indem man von x_0 aus in beide Richtungen geht. Der Algorithmus wird daher um einen Schritt ergänzt:

Schritt 6: Schritte 4 und 5 werden für die Startrichtung -\gamma_\mathrm{(0)}^x:= -\gamma^{x_{(0)}} wiederholt.

Für den Fall, dass die Daten eine geschlossene Kurve beschreiben, ist dieser Schritt nicht nötig.

  • Winkel bestrafen

An möglicherweise vorhandenen Kreuzungen innerhalb der Datenwolke hat die lokale Hauptkurve jeweils drei verschiedene Möglichkeiten für ihren weiteren Verlauf. Um zu verhindern, dass die Kurve hier willkürlich nach links oder rechts abbiegt, wird in jedem Durchgang eine „Winkelbestrafung“ (angle penalization) vorgenommen. Dazu wird der Winkel

\alpha_\mathrm{(i)}^x:=\mid cos(\alpha_\mathrm{(i)}^x)\mid^k

gesetzt und die Eigenvektoren korrigiert:

\gamma_\mathrm{(i)}^x:=\alpha_\mathrm{(i)}^x \cdot \gamma_\mathrm{(i)}^x +(1-\alpha_\mathrm{(i)}^x) \cdot \gamma_\mathrm{(i-1)}^x

Je größer die positive Zahl k ist, desto stärker wird die Kurve geradeaus „gezwungen“. Es wird empfohlen, k=1 oder 2 zu setzen, da die Kurve bei höheren Werten zu viel an Flexibilität verliert.

  • mehrfache Initialisierung

Weist die Datenwolke eine verzweigte Struktur auf, so kann eine einzige lokale Hauptkurve diese nicht in ihrer Gesamtheit beschreiben. Um die Wahrscheinlichkeit zu erhöhen, alle „Zweige“ zu erfassen, werden mehrere verschiedene Startpunkte ausgewählt. Der Algorithmus wird um einen weiteren Schritt ergänzt:

Schritt 7: Aus der Menge der Startpunkte S_0 wird ohne Ersetzen ein neuer Startpunkt x_0 ausgewählt und damit der gesamte Algorithmus wiederholt.

Abdeckung[edit]

Ein Kriterium zur Einschätzung, wie gut Hauptkurven die zugrundeliegenden Daten beschreiben, ist die Abdeckung (coverage). Diese wird allgemein definiert als der Anteil der Datenpunkte, die sich in einer bestimmten Umgebung der Hauptkurve befinden. Konkret ist

C_m(\tau)= \frac{\#\{x \in \{X_1,...,X_n\}\mid \exists p \in P_m  mit  \| x-p \| \le\tau\}}{n}

die Abdeckung für die Hauptkurve m, die aus den Punkten P_m besteht, mit dem Abdeckungsparameter \tau. Für {\tau \to \infty} gilt C_m (\tau) \to 1. Um nun eine Hauptkurve zu beurteilen, ist die gesamte Abdeckungskurve zu betrachten.

Abb. 2: Beispiele für mögliche Verläufe der Abdeckungskurve
Beispiele für mögliche Verläufe der Abdeckungskurve
Quelle: Einbeck et al., 2005

Je kleiner die Fläche oberhalb der Abdeckungskurve ist, desto besser ist die Hauptkurve zur Beschreibung der Daten geeignet. Um ein quantitatives Maß für die Güte der Hauptkurve zu erhalten, wird diese Fläche ins Verhältnis zur der Fläche gesetzt, die sich bei der normalen Hauptkomponentenanalyse ergibt. Je kleiner der so ermittelte Quotient A_C ist, desto besser ist die Hauptkurve im Vergleich zu den Hauptkomponenten geeignet. Der Wert R_C = 1-A_C kann ähnlich wie das R^2 in einer Regressionsanalyse interpretiert werden. Je näher R_C an 1 liegt, desto größer ist die Güte der Hauptkurve. R_C kann zum Vergleich von nach verschiedenen Algorithmen berechneten Hauptkurven verwendet werden. Für den Vergleich von Kurven eines spezifischen Algorithmus’, jedoch mit verschiedenen Bandbreiten ist R_C hingegen nicht geeignet. Stattdessen wird eine modifizierte Version der Abdeckung, verwendet:

S(\tau)=C_\mathrm{m(\tau)}(\tau)\,

Für die Berechnung der Selbstabdeckung (self coverage) wird die Hauptkurve m durch m(\tau) mit dem Abdeckungsparameter \tau als Bandbreite ersetzt. Die optimale Bandbreite h einer Hauptkurve ergibt sich danach als das erste lokale Maximum von S(\tau).

Vorteile und Herausforderungen des LPC-Algorithmus[edit]

Der LPC-Algorithmus funktioniert sowohl mit simulierten, als auch mit realen Daten (siehe Beispiele weiter unten). Besonders für Datensätze mit höheren Störfaktoren oder komplexeren Strukturen, wie z.B. Verzweigungen, liefert die LPC-Methode teilweise bessere Ergebnisse und ist dabei rechnerisch weniger aufwendig als andere Algorithmen.

Da es kein statistisches Modell für die LPCs gibt, existiert auch keine „wahre“ Kurve. Die geschätzten Hauptkurven sind abhängig von den jeweils gewählten Startpunkten. Da jedoch die lokalen Massenmittelpunkte in jedem Fall für die selben Daten berechnet werden, unterscheiden sich die einzelnen Hauptkurven nur wenig.

Für Hauptkurven im Allgemeinen gilt, dass sie nicht geeignet sind, den Wert einer Variablen für gegebene Werte anderer Variablen vorherzusagen. Dies ist in der bereits weiter oben erwähnten Annahme symmetrischer Beziehungen zwischen den Variablen begründet.

Beispiele[edit]

Zur Veranschaulichung sollen in diesem Abschnitt zwei Anwendungsbeispiele mit realen Daten kurz dargestellt werden. Die verwendeten Datensätze, sowie die entsprechenden R-Programme können hier eingesehen werden.

Überflutungsgebiete in Pennsylvania[edit]

Der Datensatz wird durch die Digitalisierung einer Karte gewonnen, welche die Überflutungsgebiete in Beaver County in Pennsylvania, USA von 1996 zeigt.

Auf diese Daten wird der oben beschriebene LPC-Algorithmus mit 50 Initialisierungen und einer Bandbreite von h=1,4 angewandt. Abb. 3 zeigt den entsprechenden R-Output. Die einzelnen Datenpunkte werden darin als graue Kreise dargestellt. Die Folgen der roten Kreuze bilden die lokalen Hauptkurven. Vergleicht man Abb. 3 mit einer Landkarte von Beaver County, so stellt man fest, dass die LPCs deutlich die größeren Flüsse der Region nachzeichnen.

Abb. 3: Überflutungsgebiete in Pennsylvania und LPCs

Europäische Seebäder[edit]

Das oben beschriebene Verfahren wird mit 20 Startpunkten und h=1,9 auf einen Datensatz, der aus einer Karte europäischer Seebäder gewonnen wird, angewandt. Der entsprechende R-Output ist in Abb. 4 dargestellt. Hier zeigt der Vergleich mit einer Europakarte, dass die LPCs deutlich die Küsten Europas nachzeichnen.
Abb. 4: Europäische Seebäder und LPCs

Quellen[edit]