Multidimensionale Skalierung

Das Verfahren zur multidimensionalen Skalierung lässt sich in 4 Schritten beschreiben:

1. Definiere Matrix ${\displaystyle A=(a_{ij})}$ mit ${\displaystyle a_{ij}=-{\frac {1}{2}}d_{ij}^{2}}$
2. Definiere Matrix ${\displaystyle B=(b_{ij})}$ mit ${\displaystyle b_{ij}=a_{ij}-a_{i\bullet }-a_{\bullet j}+a_{\bullet \bullet }}$ wobei ${\displaystyle a_{i\bullet }={\frac {1}{n}}\sum _{j=1}^{n}a_{ij}}$ den Durchschnitt der Zeile ${\displaystyle i}$, ${\displaystyle a_{\bullet j}={\frac {1}{n}}\sum _{i=1}^{n}a_{ij}}$ den Durchschnitt der Spalte ${\displaystyle j}$ und ${\displaystyle a_{\bullet \bullet }={\frac {1}{n^{2}}}\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}}$ den Durchschnitt aller Elemente von ${\displaystyle A}$ bezeichne.
3. Bestimme die Eigenwerte ${\displaystyle \lambda _{i}}$ und die zugehörigen Eigenvektoren ${\displaystyle \gamma _{i}=(\gamma _{ij})}$ der Matrix ${\displaystyle B=(b_{ij})}$ mit der Eigenschaft: ${\displaystyle \sum _{j=1}^{n}\gamma _{ij}^{2}=\lambda _{i}}$.
4. Die Koordinaten der zu skalierenden Datenpunkte im ${\displaystyle m}$ dimensionalen Raum ergeben sich dann aus den Eigenvektoren zu den ${\displaystyle m}$ größten Eigenwerten: ${\displaystyle x_{i}=\gamma _{i}}$.

Gegeben sind die Distanzen der schnellsten Autoverbindungen zwischen verschiedenen Städten und gesucht werden die Koordinaten der Städte.

Die metrische multidimensionale Skalierung für eine Konfiguration in zwei Dimensionen mit einer Statistiksoftware ergibt

Stadt	X	Y	Grafische Konfiguration
Berlin	0,8585	−1,1679
Frankfurt	−0,6363	0,6660
Hamburg	1,5036	0,0800
Köln	−0,0438	1,1760
München	−1,6821	−0,7542

Die gefundene Konfiguration ist eindeutig, bis auf Rotation und Skalierung:

• Jede rotierte Lösung liefert natürlich die gleichen (euklidischen) Distanzen zwischen den Städten und damit sind diese Lösungen gleichwertig.
• Aufgrund der Standardisierung im Algorithmus ${\displaystyle \left(\textstyle \sum _{j=1}^{n}\gamma _{ij}^{2}=\lambda _{i}\right)}$ liefert eine gleichmäßige Vervielfachung des Abstandes aller Städte vom Nullpunkt die gleichen Koordinaten für die Städte.

Der Shepard-Kruskal Algorithmus ermittelt die Konfiguration iterativ:

1. Initialisierung ${\displaystyle (t=0)}$: Wähle gewünschte Dimensionalität ${\displaystyle m}$ und ordne Objekte zufällig im Zielraum an. (Für ${\displaystyle m=2{,}3}$ lassen sich die Ergebnisse oft eingänglich darstellen.) Berechne die Distanzen ${\displaystyle d_{ij}^{(0)}}$ zwischen allen Objekten ${\displaystyle i}$ und ${\displaystyle j}$.
2. Schritt ${\displaystyle t}$: Schätze Disparitäten ${\displaystyle {\hat {d}}_{ij}^{(t)}}$ der Objekte ${\displaystyle i}$ und ${\displaystyle j}$ unter Verwendung ihrer Distanz ${\displaystyle d_{ij}^{(t)}}$. Hierfür kann der Pool-Adjacent Violators Algorithmus (siehe unten) benutzt werden.
3. Abbruchbedingung: Sobald eines der ausgewählten Abbruchkriterien (siehe folgenden Abschnitt) für den iterativen Prozess erreicht ist, endet der iterative Prozess mit der gefundenen Konfiguration, die (eventuell nur lokal) optimal ist. Andernfalls fahre mit Punkt 4 fort.
4. Anpassung der Positionen ${\displaystyle x_{i}}$ an die Disparitäten: Berechne die neuen Koordinatenwerte ${\displaystyle x_{i}^{(t+1)}}$ für alle Objektpaare ${\displaystyle i}$ und ${\displaystyle j\neq i}$ (siehe unten), z. B. ähnlich einem Gradientenverfahren. Ermittle die Distanzen ${\displaystyle d_{ij}^{(t+1)}}$ für die neuen Positionen ${\displaystyle x_{i}^{(t+1)}}$ und fahre mit Punkt 2 fort.

• Wenn die Monotoniebedingung zwischen zwei benachbarten Punkten nicht verletzt ist, verwenden wir die jeweiligen Distanz als Disparität, also ${\displaystyle {\hat {d}}_{ij}^{(t)}=d_{ij}^{(t)}}$.
• Wenn die Monotonie-Bedingung zwischen zwei (${\displaystyle p=2}$) oder mehr (${\displaystyle p>2}$) benachbarten Punkten verletzt ist, so verwenden wir den Mittelwert der entsprechenden Distanzen als Disparitäten, also ${\displaystyle {\hat {d}}_{i_{l}j_{l}}^{(t)}=1/p\sum _{q=1}^{p}d_{i_{l+q}j_{l+q}}^{(t)}}$.[2]

Welche Transformationen bei der Berechnung der Disparitäten zulässig sind, hängt vom Skalenniveau der Rohdaten ab. Die Distanzen im Wahrnehmungsraum können aber durchaus ein anderes Skalenniveau annehmen. Inwieweit eine Anhebung des Skalenniveaus zulässig ist, wird mittels des Verdichtungsquotienten Q (Zahl der Ähnlichkeiten/(Zahl der Dimensionen*Zahl der Objekte)) beurteilt. Bei der „einfachen“ MDS liegen die Rohdaten schon in aggregierter Form vor, stellen also meist die Mittelwerte über die Antworten der Befragten dar.

Die neue Position ${\displaystyle x_{i}^{(t+1)}}$ wird berechnet als

${\displaystyle x_{i}^{(t+1)}=x_{i}^{(t)}+\alpha \sum _{j\neq i}\left(1-{\frac {{\hat {d}}_{ij}^{(t)}}{d_{ij}^{(t)}}}\right)(x_{i}^{(t)}-x_{j}^{(t)})}$.

Dabei ist ${\displaystyle x_{i}^{(t)}}$ die Position von Objekt ${\displaystyle i}$ zum Zeitpunkt ${\displaystyle t}$ und ${\displaystyle \alpha }$ ein Gewichtungsfaktor (nicht zu groß wählen, da sich der Stress-Wert auch verschlechtern kann – in der Regel 0,2).

Wenn nun zwei Objekte im Verhältnis zu ihrer Ähnlichkeit zu weit auseinanderliegen (${\displaystyle {\hat {d}}_{ij}^{(t)}/d_{ij}^{(t)}}$ ist größer 1, wodurch der Ausdruck in der Klammer negativ wird), werden sie aufeinander zu geschoben (die Richtung wird dabei durch die Differenz in der zweiten Klammer bestimmt). Zwei eher unähnliche Objekte, die zu nahe beieinander liegen, bewegt man voneinander weg. Dadurch wird der Stress-Wert in der Regel gesenkt und die Iteration wird mit Schritt 2. fortgeführt, wodurch sich der Stress-Wert in der Regel erneut senkt.

Basierend auf dem obigen Beispiel können wir eine Rangfolge der Distanzen erstellen und die Monotoniebedingung aufstellen:

Distanz:	${\displaystyle 195}$	<	${\displaystyle 289}$	<	${\displaystyle 392}$	<	${\displaystyle 427}$	<	${\displaystyle 493}$	<	${\displaystyle 548}$	<	${\displaystyle 576}$	<	${\displaystyle 577}$	<	${\displaystyle 586}$	<	${\displaystyle 776}$
Monotoniebedingung:	${\displaystyle d_{F,K}}$	<	${\displaystyle d_{B,HH}}$	<	${\displaystyle d_{F,M}}$	<	${\displaystyle d_{HH,K}}$	<	${\displaystyle d_{F,HH}}$	<	${\displaystyle d_{B,F}}$	<	${\displaystyle d_{B,K}}$	<	${\displaystyle d_{K,M}}$	<	${\displaystyle d_{B,M}}$	<	${\displaystyle d_{HH,M}}$

Es wurde zu Beginn eine zufällige Konfiguration gewählt:

daraus ergibt sich:

Monotoniebed.:	${\displaystyle d_{F,K}}$	${\displaystyle \leq }$	${\displaystyle d_{B,HH}}$	${\displaystyle \leq }$	${\displaystyle d_{F,M}}$	${\displaystyle \leq }$	${\displaystyle d_{HH,K}}$	${\displaystyle \leq }$	${\displaystyle d_{F,HH}}$	${\displaystyle \leq }$	${\displaystyle d_{B,F}}$	${\displaystyle \leq }$	${\displaystyle d_{B,K}}$	${\displaystyle \leq }$	${\displaystyle d_{K,M}}$	${\displaystyle \leq }$	${\displaystyle d_{B,M}}$	${\displaystyle \leq }$	${\displaystyle d_{HH,M}}$
${\displaystyle d_{ij}^{(0)}}$	${\displaystyle 1.3172}$	${\displaystyle \leq }$	${\displaystyle 3{,}0824}$	${\displaystyle \not \leq }$	${\displaystyle 2{,}3635}$	${\displaystyle \not \leq }$	${\displaystyle 1{,}1783}$	${\displaystyle \not \leq }$	${\displaystyle 0{,}3942}$	${\displaystyle \leq }$	${\displaystyle 3{,}1866}$	${\displaystyle \not \leq }$	${\displaystyle 1{,}9041}$	${\displaystyle \not \leq }$	${\displaystyle 1{,}1428}$	${\displaystyle \not \leq }$	${\displaystyle 1{,}4483}$	${\displaystyle \not \leq }$	${\displaystyle 2{,}1096}$
PAV			${\displaystyle (3{,}0824+2{,}3635+1{,}1783+0{,}3942)/4}$								${\displaystyle (3{,}1866+1{,}9041+1{,}1428+1{,}4483+2{,}1096)/5}$
			${\displaystyle =1{,}7546}$								${\displaystyle =1{,}9447}$
${\displaystyle {\hat {d}}_{ij}^{(0)}}$	${\displaystyle 1{,}3172}$	${\displaystyle \leq }$	${\displaystyle 1{,}7546}$	${\displaystyle \leq }$	${\displaystyle 1{,}7546}$	${\displaystyle \leq }$	${\displaystyle 1{,}7546}$	${\displaystyle \leq }$	${\displaystyle 1{,}7546}$	${\displaystyle \leq }$	${\displaystyle 1{,}9447}$	${\displaystyle \leq }$	${\displaystyle 1{,}9447}$	${\displaystyle \leq }$	${\displaystyle 1{,}9447}$	${\displaystyle \leq }$	${\displaystyle 1{,}9447}$	${\displaystyle \leq }$	${\displaystyle 1{,}9447}$

Lösung der nicht-metrischen multidimensionalen Skalierung

Aus den berechneten euklidischen Distanzen ergibt sich, dass die Monotoniebedingung in zwei Bereichen verletzt ist:

1. ${\displaystyle d_{B,HH}\leq d_{F,M}\leq d_{HH,K}\leq d_{F,HH}}$ und
2. ${\displaystyle d_{B,F}\leq d_{B,K}\leq d_{K,M}\leq d_{B,M}\leq d_{HH,M}}$.

Die Disparitäten ${\displaystyle {\hat {d}}_{ij}^{(0)}}$ werden daher als Mittelwerte (1,7546 bzw. 1,9447) der entsprechenden Bereiche berechnet. Mit den Disparitäten können nun die Punktpositionen verschoben werden. Dieses Verfahren wird iteriert und führt zur nebenstehenden Lösung.

Ziel des Verfahrens ist eine optimale Anpassung der MDS-Lösung an die Rohdaten und somit ein möglichst geringer STRESS- oder Energiewert bzw. ein möglichst großes Bestimmtheitsmaß. Diese Werte sind als Unterschied zwischen Disparität und Distanz zu verstehen. Verändern sich die Werte nicht mehr oder nur geringfügig, wird das Iterationsverfahren abgebrochen.

Der STRESS-Wert (STRESS für STandardized REsidual Sum of Squares, deutsch: standardisierte Residuenquadratsumme) berechnet sich (nach Kruskal) als Wurzel aus der Summe der Abweichungsquadrate der Disparitäten von den Distanzen, geteilt durch die Summe der quadrierten Distanzen. Damit ist STRESS ein normiertes Varianzmaß:

${\displaystyle STRESS_{1}=\left({\frac {\sum _{i<j}(d_{ij}-{\hat {d}}_{ij})^{2}}{\sum _{i<j}d_{ij}^{2}}}\right)^{\frac {1}{2}}}$

Ein alternatives STRESS Maß ist

${\displaystyle STRESS_{2}=\left({\frac {\sum _{i<j}(d_{ij}-{\hat {d}}_{ij})^{2}}{\sum _{i<j}(d_{ij}-{\overline {d}})^{2}}}\right)^{\frac {1}{2}}}$

mit ${\displaystyle {\overline {d}}}$ der Mittelwert aller Distanzen.

Prinzipiell gibt es keine exakten Vorgaben dafür, welcher STRESS-Wert noch akzeptabel ist und welchen man als „gut“ bezeichnen kann. „Um überhaupt eine Norm zu haben, hat man die ‚nullste aller Nullhypothesen’ untersucht und tausende von Zufallsdaten per MDS skaliert und dabei registriert, welche Stress-Werte sich ergeben“ (vgl. BORG/ STAUFENBIEL 1989). Kruskal[1] hat Anhaltswerte für den STRESS-Wert erstellt, an denen man sich orientieren kann.

Neben den einfachen Kostenkriterien STRESS wird ein alternatives Maß als Gütekriterium für die Anpassung der Konfiguration an die Rohdaten verwendet. Das Bestimmtheitsmaß ist die quadrierte Korrelation der Distanzen mit den Disparitäten und als Pegel der linearen Anpassung der Disparitäten an die Distanzen zu sehen. In der Praxis gelten Werte, die größer sind als 0,9 für das Bestimmtheitsmaß als akzeptabel.

Die Gewichtung der Summanden in der ${\displaystyle STRESS_{1}}$-Formel führt zu Energiemaßen[3]

${\displaystyle E=\left({\frac {\sum _{i<j}w_{ij}(d_{ij}-{\hat {d}}_{ij})^{2}}{\sum _{i<j}w_{ij}d_{ij}^{2}}}\right)^{\frac {1}{2}}}$