105 
(4.10) 
n L 
D(C) = 2 2 2ix ik -x Ik y 
j = i ¡ec, k = i 
Eine Partition C’ e P(n, O), der Menge aller Partitionen C der Länge n von O heißt optimal 
bezüglich [4.10], wenn gilt: 
D(C’)= min D(C). (4.11) 
CEP(n, O) 
Theoretisch müßten für die Suche nach solchen Partitionen C’ bei gegebener Anzahl der 
Objekte bzw. Vektoren und gewünschter Anzahl Cluster die Varianzkriterien aller möglichen 
Partitionen miteinander verglichen werden. Das ist aber aus Gründen kombinatorischer 
Explosion praktisch nicht durchführbar [Ultsch et al. 91a], [Späth 83]. Darum wird versucht, 
die optimalen Partitionen mit Hilfe von iterativen Verfahren anzunähern. Zu solchen Ver 
fahren gehört das Minimaldistanz-Verfahren. Dieses Verfahren wird ein wenig modifiziert, 
um dem Konzept der Repräsentativität Rechnung zu tragen. 
Für das Verfahren wird ein Iterationsindex t = 0 gesetzt. Es wird ein Parameter für die 
maximale Anzahl von Iterationen ITMAX > 0 gewählt und eine im Sinne von [4.8] zulässige 
Anfangspartition C(0) = (C,(0),... C n (0)}. Diese Partition wurde mit Hilfe eines Zufalls 
generators zufällig gewählt. Dann folgt: 
la. Für die t-te Iteration werden die Zentrumsvektoren Xj von C{t) auf folgende Weise berechnet: 
*/( 0 = —tt-2 A m j( 0 siehe ( 4 -8) j=\,...n 
rrtj (i) ec,«) 
lb. Um dem Konzept der Repräsentativität Rechnung zu tragen, wird ein zusätzlicher Zwischenschritt 
eingeführt. Bestimme für jedes Cluster einen Vektor xj(i). der dem entsprechenden Zentrumsvektor 
X: am ähnlichsten ist: 
II a(0 - x ’,{ 9 II = mjn || xft) - Xi || /EC//). j=\,...n 
2. Berechne eine Minimaldistanz-Partition C(t + 1) = {C ; (r + 1), . . . C„(r +1)} mit 
Cj(t + 1) := {/: || A - x)(t) || = min || x, - x’ k (t) ||} j=l,...n 
k=l, ...n 
wobei verabredungsgemäß jeweils für j der kleinste Index k gewählt wird, für den das Minimum an 
genommen wird. Dabei steht die Metrik ||x|| für 
Ist D(C(t + 1)) < D(C(t)), so erhöhe t um 1 und fahre mit Schritt la fort. 
Ist D(C(t + 1)) = D{C{t)), so erhöhe t ebenfalls um 1, 
fahre aber nur dann mit Schritt la fort, wenn t <, ITMAX gilt, sonst breche ab. (4-12) 
Das Ergebnis wird eine Endpartition beim modifizierten Minimaldistanz-Verfahren genannt 
[Späth 83]. Weil nicht das arithmetische Mittel der Vektoren, sondern der Vektor, der diesem 
Mittel am ähnlichsten ist, als Zentrumsvektor gewählt wird, ist das Varianzkriterium D(C) für