Friedrich Schmid

0ber ein Problem der mehrdimensionalen Skalierunq

1. Einleitung

Ausgangspunkt der mehrdimensionalen Skalierung ist eine Menge M := {al,a 2 ..... a n }von Objekten sowie eine Matrix S = (sij)

i,j = I, .... n, von Un~hnlichkeiten zwischen den Objekten, yon der wir annehmen wollen, dab

I. s > O i,j = 1,...,n 13 -

2. s.. = O i = 1,...,n ll

(1 .1 )

3. sij = sji i,j = I ..... n

Gesucht werden Punkte Xl,...,x n aus einem ~P mit geeignetem

p e ~, so dab IIxi-xjll in einem zu pr~zisierenden Sinne mit

sij m6glichst gut Hbereinstimmt, wobei II.ll die euklidische

Norm auf ~P bezeichnet.

Die ~ltere metrische mehrdimensionale Skalierung (siehe Tor- gerson (1958)) verlangt die Ubereinstimmung in der Form

llxi-xjl I = sij xi,x j E ]R p i,j = I ..... n (1.2)

Die neuere nichtmetrische mehrdimensionale Skalierung verlangt nut mehr

sij < Skl <=> llxi-xjll < llXk-Xlll

sij = Skl <=> llxi-xjll = ItXk-Xlll

(1.3)

xi,xj,xk,x I ~P 6 i,j,l,k = I .... ,n

oder eine noch schw~chere Bedingung.

Drygas (1978) und Kirsch (1978) zeigen an Gegenbeispielen, dab (1.2) f~r n > 4 i.a. nicht zu erreichen ist und zwar auch dann nicht, wenn-die Un~hnlichkeiten sogar eine Metrik sind (d.h. zus~tzlich zu (1.1) noch gilt, dab aus sij = O folgt,

140

dab i = j ist, sowie die Dreiecksungleichung gilt) und p 6 beliebig groB gew~hlt wird. (Man beachte jedoch, dab Young und Householder (1938) notwendige und hinreichende Bedingungen ~ber sij fur (1.2) hergeleitet haben).

Im zweiten Abschnitt beweisen wir einen Satz, der auf die Na- tur des Problems einiges Licht wirft. Er besagt im wesentli- chen, dab (1.2) mit p ~ n-1 dann m6glich ist, wenn man fur i ~ j die Unahnlichkeit s.. durch s~ . := s.. + c mit einer ge-

�9 3 13 13 n~gend groBen Konstanten c > O ersetzt. Wenn man annimmt, dab die Unahnlichkeiten sij (i ~ j) auf Intervallskalenniveau er-

hoben werden, bedeutet die Addition einer Konstanten c eine spezielle Festlegung des Ursprungs der Skala.

Eine einfache Folgerung aus dem im 2. Abschnitt bewiesenen ist, dab (1.3) immer m6glich ist mit p < n-1. Leider erlaubt der Satz nicht die Bestimmung des minimalen p, fur das (1.3) gilt. Dieses Problem scheint nach wie vor ungel6st zu sein.

2. Ein Satz ~ber mehrdimensionale Skalierun~

Die entscheidende Rolle spielt im folgenden eine yon c 6 c > O abhangende (n-1)x(n-1) Matrix D(c) mit (i,j=1,...,n-1)

I Dij (c) := ~ [ (Sin+C)

wobei

2 + (Snj+C) 2 6~j(sij+c)2 ]

? i = J

6". := i,j = I ..... n-1 i]

i#j

Ausmultiplizieren der Quadrate und Umordnen der Terme ergibt

I 2 2 6* 2 Dij(C) = y [Sin + Snj - lj sij

- ~* Sij) + 2 C (Sin + Snj lj

+ 2 c 2 - 6*. c 2] i3

Mit den (n-1)• Matrizen H=(Hij) und G=(Gij) wobei

- 6" , s. i,j = I ..... n-1 Hij := Sin + Snj 13 13

1 i+j Gij :=

2 i = j

(2.1)

141

IHBt sich (2.1) folgendermaBen schreiben

I c 2 D(c) = O(o) + cH + ~ G c > O

Wir beweisen das folgende

Lemma: Es gibt ein c o ~ O, so dab for c ~ c o gilt:

D(c) ist nichtnegativ definit, d.h. fHr x 6 ~n-1 gilt

x' D(c) x > O

Beweis: Die quadratische Form x' D(c) x l~Bt sich folgender- maBen nach unten absch~tzen (siehe z.B. Bellman (1970), S. 113 ff.)

I 2 x' D(c) x = x' D(o) x + c x' H x + ~ c x' G x

I c 2 (G)M Hi 2 > Imin(D(o))ff~f2 + c Imin(H)J1~i2 + ~ Imin

1 = [ Imin(D(o)) + c Imin(H) + ~ c21iiz~i 2

Hierbei ist Imin (.) der kleinste Eigenwert der entsprechenden

Matrix. Wegen der Symmetrie yon D(O), H und G sind alle Eigen- werte reell. AuBerdem zeigt man leicht, dab Imin(G) = Iist.

Es sei nun c > O die kleinste Zahl, so dab fHr alle c > c o -- - o

gilt

I c 2 Imi n (D(o)) + c Imin(H) + ~ ~ O

Es folgt, dab D(c o) nicht negativ definit und D(c) positiv

definit fHr c > c ist. - o

Wir halten im folgenden ein c > c fest und unterdr~cken in der Notation die Abh~ngigkeit ~on~

Falls p der Rang von D ist, so l~Bt sich D in der Form D = AA' schreiben, wobei A = (aij) eine (n-1)xp Matrix ist.

Dies kann man leicht so einsehen: Bekanntlich (siehe z.B. Bellmann (1970), S. 54) gibt es zur symmetrischen Matrix D eine orthogonale Matrix U, so dab

U' D U = diag(ll,...,In_ I)

wobei diag(ll,...,In_ I) eine Matrix mit den reellen Eigenwerten

11,...,In_i von D in der Diagonalen, und Nullen sonst, ist. Da

D nichtnegativdefinit vom Rang p ist, kSnnen wir annehmen, dab

142

I. > O i = 1..,p l I. = O i = p + I,...,n-I

l

Wir setzen nun

A := U diag(/[1,...,./~p, O ...... O)

und erhalten hieraus die gesuchte Matrix A, indem wit die letzten n-1-p Nullspalten yon ~ streichen. Wie man leicht sieht, gilt:

D = AA'

Wir setzen nun

x i := (ail, .... alp)'

x := (O,O,..,O) ' n

i = I,...,n-I

(2 .2)

Man beachte, dab Xl,...,Xn_ Ivon unserem festgehaltenen c ab- h~ngen.

Wir beweisen den folgenden

e ~P wie in (2.2) dann gilt Satz Es sei xl,...,x n

llxi-xjll = ~*'(sij+c)i3 i,j = 1,..,n

Beweis: F~r i,j = I,...,n-I gilt

llxi-xjll 2 = (xi-xj) '(xi-xj) = x~xi+x~xj-2xlx j

= Dii(c)+Djj(c)-2Dij(c)

= ~I [Sin2+Sni2+2c(Sin+Sni)+2c 2]

1 + ~[Sjn2+Snj2+2c(Sjn+Snj)+2c 2]

- [Sin2+Snj2-6~j sij2+2c(Sin+Snj-~j sij)

+ 2c2-6~j c 2]

* sij2+6 ~ 2c , 2 = 6i j j si9+6i j c

2 * (sij+c) = 6ij

143

FHr i = I,... ,n-1 gilt

2 2 �9 ' x i = D (c) = (Sin+C) llXn-XiEJ = xi ii

Bemerkunqen: I. Wie man sieht, ist fur c > c o der Rang yon

D(c) gleich n-1. Es ist also nur der Fall c = c von Inter- o

esse, wo eventuell p < n-1.

2. Offensichtlich ~ndert die Addition einer Konstanten c nicht die Ordnung der (si~).j Aus dem Satz folgt deshalb, dab

sij < Skl <=> llx.-x.ll < tJXk-Xlll i 3

s.13. = Skl <-> llxi-xjlt = llXk-XllJ

d.h., das Problem der nichtmetrischen mehrdimensionalen Ska-

lierung ist immer in einem ~P mit p ~ n-1 und p = Rang (D(Co)) 16sbar.

3. Unser Problem ist verwandt mit dem sogenannten "additive- constant-problem" der metrischen mehrdimensionalen Skalierung. Hierbei wird die additive Konstante c allerdings nach anderen (n~mlich rein pragmatischen) Gesichtspunkten bestimmt. (FHr Details siehe Torgerson (1958), S. 268 ff.).

Literaturverzeichnis

Bellman, R.: Introduction to ~trix Analysis. New York usw., 1970.

Drygas, H.: Uber multidimensionale Skalierung. Statistische Hefte, 19, (1978), S. 63-66.

Kirsch, A.: Bemerkung zu H. Drygas, "Uber multidimensionale Skalierung". Statistische Hefte, 19, (1978), S. 211-212.

Torgerson, W.S. : Theory and Methods of Scaling. New York 1958. Young, G. and Householder, A.S.: Discussion of a set of points

in terms of their mutual distances. Psychometrica, 3~ (1938), S. 19-22.

144