Einführung in die CLUSTERANALYSE - Zentraler ...homepage.univie.ac.at/marcus.hudec/Lehre/WS 2006/Methoden DA... · Multivariate Statistische Verfahren CLUSTERANALYSE INHALTSVERZEICHNIS

Einführung in die CLUSTERANALYSE

Skriptum zur Vorlesung

MULTIVARIATE STATISTISCHE VERFAHREN

Ao.Univ.Prof. Dr. Marcus HUDEC

Institut für Statistik & Decision Support Systems

UNIVERSITÄT WIEN

März 2003

Multivariate Statistische Verfahren CLUSTERANALYSE

INHALTSVERZEICHNIS

1 PROBLEMSTELLUNG UND ANWENDUNGSBEISPIELE ............................................................. 1-1

2 THEORETISCHE GRUNDLAGEN ...................................................................................................... 2-1

2.1 ÄHNLICHKEITS- UND DISTANZMAßE .................................................................................................. 2-1 2.2 PRÄORDNUNGEN................................................................................................................................ 2-4 2.3 KLASSIFIKATION................................................................................................................................ 2-5

3 HIERARCHISCHE CLUSTERVERFAHREN..................................................................................... 3-1

3.1 EINLEITUNG....................................................................................................................................... 3-1 3.2 AGGLOMERATIVE VERFAHREN.......................................................................................................... 3-3 3.3 SPEZIELLE AGGLOMERATIVE VERFAHREN ......................................................................................... 3-4 3.4 REKURSIVE BERECHNUNG DER KLASSENDISTANZEN......................................................................... 3-8

4 OPTIMALE PARTITIONEN ................................................................................................................. 4-1

4.1 ALLGEMEINE ASPEKTE ...................................................................................................................... 4-1 4.2 BESTIMMEN EINER STARTPARTITION ................................................................................................. 4-1 4.3 OPTIMERUNGSKRITERIEN................................................................................................................... 4-2 4.4 NEAREST CENTROID SORING (QUICK CLUSTER)........................................................................... 4-4

5 MODELLBASIERENDE HIERARCHISCHE KLASSIFIKATION ................................................. 5-1

5.1 EINLEITUNG....................................................................................................................................... 5-1 5.2 MULTIVARIAT-NORMALVERTEILTE KLASSEN .................................................................................... 5-2

6 EIN ANWENDUNGSBEISPIEL ............................................................................................................ 6-1

6.1 DER DATENSATZ ............................................................................................................................... 6-1 6.2 DESKRIPTIVE ANALYSE ..................................................................................................................... 6-2 6.3 HIERARCHISCHE CLUSTERANALYSE MIT S-PLUS.............................................................................. 6-9 6.4 HIERARCHISCHE VERFAHREN IN SPSS ............................................................................................ 6-20 6.5 MODELLBASIERENDE HIERARCHISCHE CLUSTERANALYSE MIT SPLUS........................................... 6-23 6.6 QUICK-CLUSTER ALGORITHMUS MIT SPSS ................................................................................... 6-29

7 ÄHNLICHKEIT BEI BINÄREN MERKMALEN................................................................................ 7-1

7.1 VERTAUSCHUNGSINVARIANTE ÄHNLICHKEITSMAßE ......................................................................... 7-2 7.1.1 Der M-Koeffizient: ....................................................................................................................... 7-2 7.1.2 Äquivalente Modifikationen des M-Koeffizienten: ....................................................................... 7-2

7.2 NICHTVERTAUSCHUNGSINVARIANTE ÄHNLICHKEITSMAßE................................................................ 7-3


7.2.1 Der S-Koeffizient und seine Modifikationen ................................................................................ 7-3 7.3 ASSOZIATIONSMAßE .......................................................................................................................... 7-5

7.3.1 Der Korrelationskoeffizient bei binären Merkmalen ................................................................... 7-5 7.4 BEISPIELE FÜR BINÄRE CLUSTERANALYSEN MIT SPSS ...................................................................... 7-6

8 S-PLUS LIBRARY CLUSTER............................................................................................................... 8-1

8.1 DAISY DISSIMILARITY MATRIX CALCULATION................................................................................ 8-1 8.2 PARTITIONING AROUND MEDOIDS - PAM ........................................................................................... 8-1 8.3 CLUSTERING LARGE APPLICATIONS - CLARA .................................................................................... 8-8 8.4 FUZZY ANALYSIS - FANNY................................................................................................................. 8-9 8.5 AGGLOMERATIVE NESTING -AGNES................................................................................................. 8-12 8.6 DIVISIVE ANALYSIS - DIANA............................................................................................................ 8-12 8.7 MONOTHETIC ANALYSIS - MONA ..................................................................................................... 8-15

9 LITERATUR ............................................................................................................................................ 9-1


1 Problemstellung und Anwendungsbeispiele

Die klassische Aufgabenstellung der Clusteranalyse ist es, eine zunächst ungeordnete

Stichprobe von N Elementen ω1, ..., ωN aufgrund von Ähnlichkeitsbeziehungen in kleinere,

homogene Klassen oder Gruppen zu gliedern.

Cluster - a group of contigous elements of a statistical population.

Kendall & Buckland, Dictionary of Statistical Terms

Eine solche Klassifikation von Objekten ermöglicht es häufig, die Struktur der

zugrundeliegenden Objektmenge in vereinfachter und übersichtlicher Weise darzustellen.

Insbesondere wenn höherdimensionale Beobachtungen pro Einzelobjekt vorliegen, helfen

Methoden der Clusteranalyse als datenreduzierendes Verfahren beim Erkennen von

Zusammenhängen bzw. der Interpretation der Daten. Häufig kann mittels sog. Objekttypen,

welche individuelle Repräsentanten von aufgefundenen homogenen Klassen sind, eine

wertvolle Strukturierung des Datenmaterials erfolgen. In diesem Sinne lässt sich die

Clusteranalyse als Hilfsmittel zur Typenbildung auffassen.

Dadurch, dass man gleichartige oder ähnliche Dinge in homogene Klassen zusammenfasst

und die Merkmale jeder Klasse als repräsentativ für die betreffenden Objekte ansieht, ist es

zunächst möglich, die Struktur der betrachteten Objektmenge vereinfacht darzustellen und die

Vielfalt der beobachteten Erscheinungsformen auf ein erträgliches, überschaubares Maß zu

reduzieren. Das Prinzip der Klassenbildung erweist sich somit als eine Methode der

Datenreduktion und insofern - ähnlich wie die Abstraktion - als ein nützliches Hilfsmittel zur

Erkenntnis neuer und unbekannter Zusammenhänge.

H.H. Bock (1974)

Ein wesentliches Charakteristikum der Clusteranalyse ist, dass es sich hierbei um ein

exploratives, hypothesengenerierendes Instrument der angewandten Statistik handelt.

Während die Diskriminanzanalyse stark konfirmatorisch orientiert ist (Bestätigung einer

vermuteten Klassenstruktur), dient die Clusteranalyse zum Auffinden einer möglichen

Klassenstruktur. Wenngleich manche Verfahren unter dem Aspekt einer Optimalität bei

Vorliegen eines bestimmten Stichprobenmodells hergeleitet werden, spielen Fragen der

© Marcus Hudec 1-1


Signifikanz oder Kriterien der Validität im Kontext der Clusteranalyse eine untergeordnete

Rolle. Im Vordergrund steht der deskriptive Charakter.

Classification procedures are essentialy descriptive techniques for multivariate data, and

solutions given should lead to a proper re-examination of the data matrix rather than a mere

acceptance of the clusters produced.

B. Everitt (1974)

Das Klassifikationsproblem stellt bereits seit den Wurzeln der Philosophie einen zentralen

Aspekt der Erkenntnistheorie dar.

Unter den Philosophen scheint Einigkeit darüber zu bestehen, dass die Klassifikation eine

fundamentale Tätigkeit des Menschen ist, ohne die kein methodisches Denken möglich ist. In

allen Wissenschaften muss der Bildung von Konzepten, Hypothesen und Theorien ein Ordnen,

Systematisieren und Klassifizieren von realen und imaginären Dingen vorausgehen.

F. Vogel (1975)

All the real knowledge which we possess, depends on methods by which we distinguish the

similar from the dissimilar.

C. Linnaeus; Genera Plantarum 1737

Geht man davon aus, dass Klassifikation ein allgemeines Grundprinzip des menschlichen

Denkens und Strebens nach Erkenntnis ist, welches dazu dient, die vielfältigen

Erscheinungsformen unserer Umwelt durch Klassifikation und Benennung besser zu

begreifen und auch besser kommunikativ bewältigen zu können, erscheint es sinnvoll ein

Klassifikationsproblem immer im Kontext einer konkreten Aufgabenstellung bzw. eines

intendierten Zweckes zu sehen. Dies relativiert die Frage nach „richtigen“ oder „wahren“

Klassifikationsergebnissen.

All classifications are subjective...

S.T. Cowan (1955)

Vielmehr rückt die Frage in den Vordergund, ob die gefundene Klassifikation für den

intendierten Zweck brauchbar bzw. praxistauglich ist.

© Marcus Hudec 1-2


Die Klassifikation ist nie Selbstzweck, sondern immer Mittel zum Zweck. Das aber heißt, dass

jedes Klassifikationsergebnis nur im Hinblick auf den Zweck oder das Ziel, das damit erreicht

werden soll, beurteilt und verstanden werden kann.

F. Vogel (1975)

In gewisse Sinne sind die beiden Methodengruppen der automatischen Klassifikation und der

Diskriminanzanalyse als komplementär zueinander einzustufen. Dies trifft insbesondere dann

zu, wenn man neben den zur automatischen Klassifikation verwendeten Merkmalen noch über

einen zweiten Satz von Merkmalen verfügt, die nicht zur Klassenbildung herangezogen

wurden.

Die Ausgangsdaten einer Clusteranalyse bildet eine (Nxp)-Datenmatrix, wenn wir davon

ausgehen, dass für jedes ωn (n = 1, ..., N) ein p-dimensionaler Merkmalsvektor xn beobachtet

wird. Schematisch lässt sich diese Datenstruktur wie folgt darstellen:

Objekt Merkmal: X1 Merkmal: X2 … Merkmal: Xp ω1 x11 x12 x1p

ω2 x21 x22 x2p

...

ωN xN1 xN2 xNp

Neben der Bezeichnung Clusteranalyse finden sich in der Literatur auch häufig die Termini

Automatische Klassifikation, Numerische Taxonomie (numerical taxonomy), Klassifikations-

verfahren, unsupervised learning oder pattern recognition. Dabei handelt es sich um ein

breites Methodenspektrum, dem gemein ist, möglichst homogene und gut separierte

Klassenstrukturen zu generieren.

Dieser Zielsetzung entspricht es, dass Objekte, die derselben Klasse zugerechnet werden

möglichst ähnlich sein sollen (Homogenität), während Objekte, die in verschiedenen Klassen

zugeordnet werden, möglichst stark voneinander unterscheiden (Separation).

© Marcus Hudec 1-3


The aim of cluster analysis is to classify a data set into groups that are internally cohesive

and externally isolated.

S-PLUS Ver.3.3 Guide to Statistical and Mathematical Analysis p.15-2

Unterschiedliche Operationalisierungen des Begriffs der „Ähnlichkeit“, der zugrundegelegten

Optimierungskriterien und der verwendeten Optimierungsalgorithmen sowie unterschiedliche

Ausgangsdaten in bezug auf das Skalenniveau begründen die große und nahezu unüber-

schaubare Methodenvielfalt.

Die Anwendungsgebiete der Clusteranalyse sind vielfältig und weit gestreut

• Sozialwissenschaften

- Typisierung von Personen nach ihrem Verhalten bzw. aufgrund von relevanten Merkmalen

- Typenbildung von Karriereverläufen

- Segmentierung von Ländern nach sozialen, wirtschaftlichen oder demographischen Indikatoren

- Klassifikation von Staaten nach ihrem Abstimmungsverhalten bei der UNO

• Medizin, Psychologie

- Differenzierung von Krankheitsbildern

- Typologie von Verhaltensweisen

• Biologie

- Gruppierung von Bakterien und Mikroorganismen

- Klassifikation von Pflanzen und Tieren

• Informatik

- Content-Classification beim Design von Informationssystemen („Suchmaschinen“)

• Betriebswirtschaftslehre

- Gruppierung von Absatzmärkten

- Käuferschichten etc. im Marketing

• Archäologie bzw. Paläontologie

- Datierung von archäologischen und paläontologischen Funden

© Marcus Hudec 1-4


2 Theoretische Grundlagen

Den Ausgangspunkt für die Anwendung der Clusteranalyse bildet die im Abschnitt 1 kurz

vorgestellte Datenmatrix. Allerdings verwenden eine Reihe von Klassifikationsverfahren, die

Rohdatenmatrix nur indirekt. Diese Verfahren, die auch als Ähnlichkeitsmethoden bezeichnet

werden, verwenden als Ausgangsinformation lediglich die NxN-Ähnlichkeitsmatrix, welche

die Ähnlichkeit aller Objetkpaare Oj, Ok enthält.

2.1 Ähnlichkeits- und Distanzmaße

Wir betrachten eine Menge von N Objekten O = O1, ..., ON. Die Funktion

s O O: × → R heißt Ähnlichkeitsmaß (similitudo), -funktion oder -koeffizient, wenn

s s und s s mit m n Nnm mn mn nn= ≤ =, , ,1… . In der Regel geht man von der Forderung

aus, dass gilt. Im Falle von normierten Ähnlichkeitskoeffizienten verlangt man häufig

zusätzlich s , so dass der Wertebereich von s auf das Intervall [0, 1] beschränkt wird.

smn ≥ 0

nn = 1

Als Ähnlichkeitsmatrix bezeichnen wir die symmetrische N N× −Matrix S = (smn), welche

die Ähnlichkeitskoeffizienten zwischen allen Objektpaaren enthält.

Alternativ operiert man häufig mit Distanzmaßen oder Distanzfunktionen d O O: × → R , für

welche gelten muß, dass d d und d d mit m n Nnn mn mn nm= ≥ = =0 0 1, , …, , .

N

Häufig wird

statt dmn auch d(m, n) bzw. d(xm, xn) als Schreibweise verwendet.

Analog zur Ähnlichkeitsmatrix S bezeichnen wir die Matrix D=(dmn) als Distanzmatrix.

Erfüllt ein Distanzmaß d die Dreiecksungleichung d d d mit l m nmn ml≤ + =ln , , , ,1… so

spricht man von einem metrischen Distanzmaß.

Für manche Algorithmen der Clusteranalyse ist nicht einmal die genaue Kenntnis der

numerischen Werte der Distanzmatrix erforderlich. Diese Algorithmen operieren lediglich auf

der Rangfolge der Distanzmaße und verwenden die dadurch auf der Menge aller Objektpaare

induzierte (Prä)Ordnung.

© Marcus Hudec 2-1


Um zu vermeiden, dass die auf den Distanzmaßen beruhenden Ergebnisse bei quantitativen

Variablen nicht durch die oft willkürliche Wahl von Maßeinheiten beeinflusst werden,

erscheint es sinnvoll Invarianz - Forderungen an die betrachteten Distanzmaße zu stellen.

Skaleninvarianz:

Wir betrachten folgende Transformationen der p-dimensionalen Merkmalsvektoren xn:

mit ~x C xn = ⋅ n

C diag c c und c i pp i= > =( , , ) , ,1 0 1… …

Ein Distanzmaß d() heißt skaleninvariant falls gilt:

( ) (d x x d x x~ , ~ ,n m n m= )

Die strenge Forderung der Skaleninvarianz wird in der Praxis häufig (z.B. wenn alle

Merkmale in der selben Maßeinheit gemessen wurden) durch die etwas schwächere

Forderung:

( ) ( )d x x d x x~ , ~ ,n m n m pc mit c c c= ⋅ = = = = >1 2 0… c

ersetzt.

Eine zusätzliche Forderung an ein Distanzmaß ist die Forderung, dass das Ergebnis

unabhängig von der konkreten Wahl des Koordinatenursprungs ist. Man nennt diese

Eigenschaft Translationsinvarianz. Es gilt dann:

~ ( , ) (~ , ~ )x x b b x x x xn n n m n md d= + ∈ ⇒ =( )pR .

Sei T eine Menge von Transformationen des Merkmalsraums X, so heißt ein Distanzmaß d()

invariant bezüglich T, wenn für jede Transformation T ∈ T gilt ( ) (d x x d Tx xn m n mT, ,= ) . Für

die Praxis ist es wesentlich zu überlegen, dass die Invarianzeigenschaften eines gewählten

Distanzmaßes mit der Semantik der Daten übereinstimmen.

© Marcus Hudec 2-2


Im Fall von intervall- oder verhältnisskalierten Merkmalen stellen die Lq-Distanzen (auch

Minkowski-q-Metriken) die wohl am häufigsten benutzten Distanzmaße dar.

d n m x x qq ni miq

i

p q

( , ) | | ,/

= −⎛⎝⎜

⎞⎠⎟ >

=∑

1

1

1

Lq-Distanzen sind metrische, translationsinvariante jedoch nicht skaleninvariante Distanzen.

Außer für q=2 (Euklidsche Distanz) sind sie auch nicht invariant gegenüber orthogonaler

linearer Transformationen (Drehungen, Spiegelungen).

Aufgrund der fehlenden Skaleninvarianz müssen die Daten daher in vielen Anwendungen vor

Berechnung der Distanzen auf eine gemeinsame Maßeinheit gebracht werden (Normierung).

In der Praxis geschieht dies häufig durch spaltenweise Standardisierung nach einer der

folgenden Verfahren:

a) ~ : min( )max( ) min( )

, , , ,x x xx xni

ni i

i i

mit n N und i p=−−

= =1 1… …

b) ~ : , , , ,.x x xni

ni i

i

mit n N und i p=−

= =σ

1 1… …

Besondere Bedeutung in der Praxis haben die L2-Distanz (euklidsche Distanz), welche der

üblichen geometrischen Abstandsvorstellung entspricht und die L1-Distanz (City-Block-

Metrik).

d n m x xni mii

p

11

( , ) | |= −=∑

( )d n m x xni mii

p

n m22

1

1 2

( , )/

= −⎛⎝⎜

⎞⎠⎟ = −

=∑ x x

Während bei der L1-Distanz kleine und große Differenzen einer Komponente gleich behandelt

werden, wirken sich bei große Differenzen aufgrund der Potenzierung stärker aus. q ≥ 2

Für )(max),( miniimnq xxdq −=∞→ wird die Lq-Distanz durch die maximale Differenz in

einer Komponente bestimmt.

Eine weitergehende Invarianzeigenschaft zeichnet die Mahalanobis-Distanz aus, die sowohl

skalen- als auch translationsinvariant ist. Außerdem führt die Verwendung der Mahalanobis-

© Marcus Hudec 2-3


Distanz implizit zu einer solchen Transformation der Merkmale, dass die Distanzen stets

unter Verwendung von p unkorrelierten Merkmalen berechnet werden. Aus diesem Grund

wird der Mahalanobis-Distanz beim Vorliegen stark korrelierter Merkmalsvektoren häufig der

Vorzug gegenüber der euklidschen Distanz eingeräumt.

Die Mahalanobis-Distanz dM(n, m) ist wie folgt definiert:

)()'(),( 1mnmnM xxxxmnd −Σ−= −

mit

∑=

−−=ΣN

nnn xxxx

N 1

)')((1 und xN

xnn

N

==∑1

1

.

2.2 Präordnungen

Für viele praktische Anwendungsfälle steht eine Vielzahl von Distanzmaßen zur Verfügung.

In diesem Zusammenhang ist es von Interesse diese zu vergleichen. Dabei kommt es weniger

auf den absoluten Wert der Distanzen zwischen den Objektpaare sondern auf deren

Reihenfolge an.

N2

⎛⎝⎜

⎞⎠⎟

Sei S =O1, ..., ON die Menge der N Objekte und F die Menge aller Objektpaare aus S.

dij sei eine auf SxS definierte Distanzmatrix. Wir definieren auf F eine Relation ∠ wie folgt:

Für 2 Objektpaare h = i,j ∈ F und g =k,l ∈ F sei g ∠ h genau dann, wenn gilt dkl ≤ dij.

Die Relation ∠ erfüllt folgende Axiome:

1. Für jedes Paar g, h ∈ F gilt entweder g ∠ h oder h ∠ g oder beides (Totalität). 2. Für jedes g F gilt g ∠ g (Reflexivität). 3. Wenn g ∠ h und h ∠ t gilt, so gilt auch g ∠ t (Transitivität). Eine Relation, welche die Bedingungen 1 bis 3 erfüllt, heißt eine totale Präordnung auf F. Gilt

zusätzlich noch die Bedingung 4 spricht man von einer totalen Ordnung.

4. Aus g ∠ h, h ∠ g folgt g = h. Somit induziert jedes Distanzmaß auf F eine totale Präordnung, und wenn alle Distanzen dkj

verschieden sind, sogar eine totale Ordnung.

© Marcus Hudec 2-4


Zwei Distanzmaße d1, d2 heißen äquivalent, wenn die zugehörigen Präordnungen

übereinstimmen. Gleichbedeutend ist, dass d2 eine streng monotone Funktion von d1 ist.

Zum Vergleich zweier Distanzmaße d1, d2 betrachtet man häufig die Anzahl der Inversionen:

Inversion: d1ij ∠ d1kl und d2kl ∠ d2ij.

2.3 Klassifikation

Wir betrachten eine Objektmenge S aus N Objekten O1, ..., ON, für die eine Datenmatrix, eine

Ähnlichkeits- oder Distanzmatrix oder zumindest eine die Ähnlichkeitsstruktur der

Objektmenge beschreibende Relation bekannt sei.

Die Aufgabe der automatischen Klassifikation ist es nun eine solche Klassifikation δ = (A1,

A2, ..., Am) von S zu finden, welche die Ähnlichkeitsstruktur der Objekte möglichst gut

wiedergibt.

Eine Klassifikation Ω ist ein System von Teilmengen (Klassen, Gruppen, cluster) A1, A2, ...,

Am der Objektmenge S. In der Praxis der Clusteranalyse können unterschiedliche Typen von

Klassifikationen auftreten.

Eine Klassifikation δ heißt disjunkt, wenn sich ihre Klassen nicht überschneiden:

A Ai j∩ = ∅ für i j≠

Treten auch sich überschneidende Klassen auf, so spricht man von einer nichtdisjunkten

Klassifikation. Im zweiten Fall gibt es Objekte, die nicht eindeutig einem Cluster zugeordnet

werden können.

Weiters unterscheidet man exhaustive und nicht exhaustive Klassifikationen. Bei exhaustiven

Klassifikationen wird jedes Element zumindest einer Klasse zugeordnet, während bei nicht

exhaustiven Klassifikationen einzelne Objekte unklassifiziert bleiben. Demgemäß werden

exhaustive Klassifikationen durch die nachfolgende Bedingung charakterisiert

. A Sii

m

=

=1∪

© Marcus Hudec 2-5


Disjunkte, exhaustive Klassifikationen nennt man eine Partition der Objektmenge. Die

Anzahl der Partitionen einer Objektmenge S mit Kardinalität N, welche genau m nichtleere

Klassen aufweisen, ist durch S(N,m) - die STIRLINGsche Zahlen zweiter Art, gegeben.

S N mm

mr

m rr

mN( , )

!( ) ( )= −

⎛⎝⎜

⎞⎠⎟ −

=∑1 1

0

S(N, m) m=2 m=5 m=10

N=5 15 1 0

N=10 511 42 525 1

N=20 524 287 7,492*1011 5.918*1012

N=100 6,342*1029 6,573*1067 2,756*1093

Für großes N und kleines m hat S(N, m) die Gößenordnung von mN/m!. Zur praktischen

Berechnung ist die folgende Rekursionsformel nützlich:

S N m S N m m S N m( , ) ( , ) ( ,+ = − )+ ⋅1 1

mit und S NS N S N N( , ) , ( , )1 1= = 1 m( , ) = 0 falls N m< .

Betrachtet man die Menge aller möglichen Partitionen von S ohne Vorgabe einer Klassenzahl,

so wird deren Anzahl durch die sog. BELLschen Zahlen oder auch Exponentialzahlen

angegeben. Natürlich gilt für diese

B N S N S N S N N( ) ( , ) ( ,2) ( , )= + + +1 …

Für gilt die Rekursionsformel N ≥ 0

B NNr

B rr

N

( ) (+ =⎛⎝⎜

⎞⎠⎟ ⋅

=∑1

0

)

wobei B(0) = 1 und B(1) = 1 gilt.

© Marcus Hudec 2-6


N=5 B(N) = 52 N=20 B(N) = 5,172*1013

N=10 B(N) = 115 975 N=50 B(N)=1,857*1047

Beim Vergleich von Partitionen A und B sind folgende Begriffe gebräuchlich: A heißt eine

Verfeinerung von B, wenn für jede Klasse Aj von A gilt, dass sie ganz in einer Klasse Bi von B

enthalten ist. A besitzt dann mindestens ebenso viele Klassen wie B und entsteht aus B

dadurch, dass eine oder mehrere Klassen Bi aus B in Unterklassen aufgeteilt werden.

Umgekehrt heißt B eine Vergröberung von A.

Manche Algorithmen generieren ein System von Teilmengen, welches aus Klassen besteht,

die einander in der Form eines Stammbaums über- bzw. untergeordnet sind. In diesem Fall

spricht man von einer Hierarchie.

Ein System H = (A, B, C, D,...) von nichtleeren Teilmengen von S heißt eine Hierarchie, wenn

alle Mengen A, B, C, D, ... aus H verschieden sind und wenn für zwei beliebige Mengen C

und D aus H nur eine der 3 Möglichkeiten zutrifft:

C D oder C D oder D C∩ = ∅ ⊂ ⊂

Die Mengen A, B, C, ... heißen die Klassen der Hierarchie.

Eine Hierarchie, die sowohl die Objektmenge S selbst als auch alle ein-elementigen Klassen

1, 2, ..., N enthält, nennt man eine totale Hierarchie.

© Marcus Hudec 2-7


Zur Verdeutlichung betrachten wir eine Menge von 4 Objekten S=a, b, c, d.

Sei H1 folgendes System von Teilmengen:

H1=a, b,c,d,a,b,c,d,a,b,c,d

Wie man leicht überprüft repräsentiert H1 eine totale Hierarchie.


H2=a, b,c,d,a,b,c,d

Wie man leicht überprüft repräsentiert H2 eine Hierarchie.


H3=a, b,c,d,a,b,c,d, a,b,c

Wie man leicht überprüft repräsentiert H3 keine Hierarchie.

Während die obige Definition einer Hierarchie zwar Inklusionsbeziehungen zwischen den

einzelnen Klassen definiert, enthält sie zunächst keinen Hinweis auf die Heterogenität der

einzelnen Klassen. Dies kann durch die Berücksichtigung eines Indexs erzielt werden.

Ein Index zur Hierarchie H ist formal eine für alle Klassen A H∈ definierte, nichtnegative

Funktion h(A), welche die Ungleichung h(B) < h(A) für alle A, B ∈ H mit B ⊂ A erfüllt

(starke Indexbedingung). Außerdem gelte h(A) = 0 genau dann, wenn A nur äquivalente

Objekte enthält.

Eine Hierarchie H, die mit einem Index h() versehen ist, nennt man eine indizierte Hierarchie

(H, h) oder ein Dendrogramm. Bei der praktischen Anwendung in der Clusteranalyse misst

der Index h() die Heterogenität der Klassen. Die in der Praxis verwendeten Heterogenitäts-

maße werden entweder unmittelbar aus den Distanzen der Objekte einer Klasse abgeleitet

(z.B. mittlere oder maximale Distanz aller Objektpaare aus der Klasse) oder basieren auf

allgemeinen statistischen Konzepten zur Messung derVariabilität von Objekten (Varianz,

Entropie).

© Marcus Hudec 2-8


In einem Dendrogramm existiert zu jedem Wert h* ≥ 0 eine eindeutig bestimmte Partition

A(h*) der Objektmenge S, die dadurch definiert ist, dass für alle Klassen Aj aus A(h*) gilt

h(Aj) ≤ h*. Für 2 Werte h und h* mit h < h* sind die zugehörigen Partitionen entweder ident,

oder A(h) ist eine Verfeinerung von A(h*). Variiert man h, so ändert sich die Partition A(h)

genau an jenen Stellen, wo es zu einer Verschmelzung von Klassen kommt. Demgemäß ergibt

sich für n+1 Werte von h

h h h n0 1 20= < < <… h

eine Folge von n+1 immer gröberen Partitionen

A0 = A(h0) = (ω1, ω2, ..., ωN)

…

Aj = A(hj)

…

An = A(hn) = (ω1, ω2, ..., ωN),

deren Klassenzahl m monoton fällt

m N m m mn0 1 2 1= < < < =… .

Man spricht in diesem Zusammenhang auch von einer Partitionenhierarchie.

© Marcus Hudec 2-9


h1

h

2
h
h21
h
1 2 3 4 5 6 7 8

Die Anzahl ψ(N) aller Partitionenhierarchien der Menge 1, ..., Nergibt sich durch die

Rekursionsgleichung

, Ψ Ψ( ) ( , ) ( )N S N mm

N

= ⋅=

−

∑1

1

m

wobei S(N, m) die bereits zuvor definierten STIRLINGsche Zahlen zweiter Art sind.

Wie leicht zu überlegen ist ergibt sich ψ(1) = 1, ψ(2) = 1, ψ(3) = 4, ψ(4) = 32, ψ(5) = 436.

© Marcus Hudec 2-10


3 Hierarchische Clusterverfahren

3.1 Einleitung

Da in der Praxis häufig keine konkreten Vorstellungen über die Zahl der Klassen vorliegt ist

es oft sinnvoll nicht eine einzige disjunkte Gruppierung zu konstruieren, sondern eine Folge

von Gruppierungen, die sich in bezug auf die Klassenzahl und somit die Homogenität der

Gruppen unterscheiden. Um jedoch eine einfache Interpretation einer solchen Partitionenfolge

zu gewährleisten erscheint es sinnvoll zu fordern, dass bei Zunahme des Homogenitätsgrades

(Zunahme der Klassenzahl), die Partitionen durch schrittweise Verfeinerung auseinander

entstehen, dass also homogenere Klassen durch Aufteilung von größeren Klassen in

Untergruppen entstehen. Für die Praxis bedeutet dies, dass wir, um eine einfache

Interpretation zu gewährleisten, insbesondere solche Homogenitäts- bzw. Heterogenitätsmaße

verwenden werden, welche die zuvor formulierte Indexbedingung erfüllen. Andernfalls treten

beim Vorliegen einer Verletzung der Indexbedingung nur schwer interpretierbare Inversionen

auf.

1 2 3 4 5 6

h

A

B

Beispiel eines Dendrogramms mit einer Inversion

© Marcus Hudec 3-1


Das Ergebnis einer hierarchischen Klassifikation lässt sich graphisch in der Form eines

Dendrogramms zusammenfassen. Ein Dendrogramm stellt die einzelnen Klassen in der Form

eines Stammbaums übersichtlich dar. Insbesondere lässt sich der Heterogenitätsgrad einer

Partition daran beurteilen, wie hoch bzw. wie tief sie in der Hierarchie eingezeichnet sind. Je

größer die Ähnlichkeit zwischen 2 Gruppen bzw. Objekten ist, desto tiefer treffen diese im

Klassifikationsbaum aufeinander.

Die Dendrogrammdarstellung eröffnet zahlreiche interpretatorische Möglichkeiten. So wird

deutlich, ob die Gruppen durch sukzessive Adjunktion von Einzelobjekten entstehen, oder ob

die Gruppen durch sukzessive Fusion annähernd gleich großer Klassen entstehen. Weiters

können gut separierte Klassen daran erkannt werden, dass sie über größere Heterogenitäts-

bereiche unverändert bleiben. Untypische Objekte (Ausreißer) sind daran zu erkennen, dass

sie erst relativ spät einer größeren Klasse zugeordnet werden.

Ist man nur an einer konkreten Partition interessiert, kann der Anwender durch Wahl eines

beliebigen Heterogenitätsgrades h* die zugehörige Partition einfach identifizieren.

Prinzipiell können 2 Arten von Algorithmen unterschieden werden. Bei den agglomerativen

Verfahren erfolgt ausgehend von den N einelementigen Klassen eine sukzessive Fusion der

einzelnen Klassen bis schließlich nur noch eine Klasse vorliegt. Umgekehrt führen divisive

Algorithmen ausgehend von einer alle Objekte umfassenden Klasse eine schrittweise

Verfeinerung der Partitionen durch, bis nur mehr lauter einelementige Klassen vorliegen. Für

die Praxis ist die erste Gruppe von größerer Relevanz.

© Marcus Hudec 3-2


3.2 Agglomerative Verfahren

Ein allgemeines Konstruktionsprinzip für den Ablauf agglomerativer Verfahren kann wie

folgt angegeben werden:

Für v=0 sei A0=(1,...,N) die feinste Partition der Objektmenge S=O1,...,ON.

(1) Man erhält die Partition Av durch Vergröberung aus Av-1, die sich durch die Fusionierung von jenen 2 Klassen Ar und As aus Av-1 ergibt, für die die Distanz zwischen den beiden Objektmengen minimal ist: D A A Min D A A hr s i j i j( , ) ( , ) v= ⇒

≠.

(2) Man iteriere den Schritt (2) bis Av=S. Durch obigen Algorithmus erhält man eine totale Partitionenhierarchie, die durch hv indiziert

wird.

Um eine operative Umsetzung zu ermöglichen gilt es noch zu definieren, in welcher Form die

Distanz zwischen Objektmengen Ar und As, die mehr als ein Element enthalten berechnet

wird. Dies kann durch die Anwendung einer Aggregatfunktion (z.B. min, max, mean) auf

sämtliche Distanzen zwischen den Objektpaaren (Oi, Oj) mit Oi ∈ Ar und Oj ∈ As erfolgen.

Alternativ dazu können auch Heterogenitätsmaße, die die Heterogenität einer Objektmenge

beurteilen, herangezogen werden. Als „Distanz“ zwischen 2 Objektmengen fungiert dann die

inkrementelle Erhöhung dieses Heterogenitätsmaßes, welche durch die Fusionierung der

beiden Objektmengen zu einer gemeinsamen Klasse entsteht.

Um zu gewährleisten, dass das Ergebnis einer Klassifikation der Indexbedingung genügt ist es

notwendig eine Monotonieforderung an das Distanzmaß zwischen den Klassen zu stellen, d.h.

dass der minimale Klassenabstand hv im Verlaufe des Verfahrens nie abnimmt:

0 1 2≤ ≤ ≤ ≤h h h n…

Es sei jedoch darauf hingewiesen, dass in der Praxis auch hierarchische Clusterverfahren

Anwendung finden, bei denen nicht automatisch gewährleistet ist, dass die obige Bedingung

für alle Datenkonstellationen erfüllt ist. Es kann dann passieren, dass h(X) > h(Y), obwohl X

eine echte Teilmenge von Y ist. Wie wir in 3.4 sehen werden, kann dies insbesondere beim

Zentroid- und Median-Verfahren auftreten.

© Marcus Hudec 3-3


Eine weitere Präzisierung ist noch in bezug auf die Minimumsbildung im Schritt (2)

erforderlich. Bisweilen kann es auftreten, dass mehrere Klassenpaare den gleichen

Minimalabstand aufweisen. In diesem Fall können 2 unterschiedliche Strategien angewandt

werden.

(1) In jedem Fusionsschritt wird genau ein Klassenpaar fusioniert, um eine dichotome Hierarchie zu konstruieren. Aus der Menge der Kandidatenpaare mit gleichem Abstand wird dann zufällig ein Paar gewählt. Der Nachteil dieser Methode ist, dass die leichtere Interpretierbarkeit des Klassenbaums dadurch erkauft wird, dass die gefundene Hierarchie nicht eindeutig bestimmt ist.

(2) In einem Fusionsschritt können auch mehrere Klassen gleichzeitig fusioniert werden. Dadurch ist im allgemeinem natürlich nicht mehr gewährleistet, dass die gefundene Partition dichotom ist.

Zur konkreten Wahl der relevanten Partition geht man bei unbekannter Klassenanzahl so vor,

dass man die Veränderung des Heterogenitätsmaßes gegen die Klassenanzahl aufträgt. Es

bietet sich dann die Verwendung jener Klassenanzahl an, bei der der Heterogenitätszuwachs

bei kleinerwerdender Klassenanzahl einen deutlichen Knick nach oben zeigt (Scree-Plot).

3.3 Spezielle agglomerative Verfahren

Single-Linkage-Verfahren:

Dieses Verfahren, das auch mit den Begriffen „minimum distance“-, „nearest neighbor“- und

„connectedness“-method bezeichnet wird basiert darauf, dass der Abstand zweier

Objektklassen Ar, As durch den Minimalabstand der zugehörigen Objekte charakterisiert

wird.

D A A Min dr s k A l A klr s

( , ): ,

=∈ ∈

© Marcus Hudec 3-4


Für das Minimierungskriterium in Schritt (2) unseres allgemeinen Algorithmus ergibt sich

dann:

. Min Min di j k A l A kl

i j≠ ∈ ∈

,

Für die Fusionierung zweier Klassen genügt es, dass lediglich ein Objekt aus der einen und

eines aus der anderen Klasse nahe beisammen liegen (Brückenbildung, Verkettung). Dadurch

entstehen in der Praxis häufig „langgestreckte“ - den üblichen Kompaktheitsbegriffen nicht

entsprechende - Cluster.

Complete-Linkage-Verfahren:

Dieses Verfahren, das auch mit den Begriffen „maximum distance“-, „furthest neighbor“- und

„diameter“-method bezeichnet wird basiert darauf, dass der Abstand zweier Objektklassen Ar,

As durch den Maximalabstand der zugehörigen Objekte charakterisiert wird.

D A A Max dr s k A l A klr s

( , ): ,

=∈ ∈

Für das Minimierungskriterium in Schritt (2) unseres allgemeinen Algorithmus ergibt sich

dann:

. Min Max di j k A l A kl

i j≠ ∈ ∈

,

Für die Fusionierung zweier Klassen ist es erforderlich, dass alle Objekte aus der einen und

alle aus der anderen Klasse nahe beisammen liegen. Dadurch entstehen in der Praxis häufig

sehr dicht gepackte, homogene Cluster.

Average-Linkage-Verfahren:

Dieses Verfahren nimmt eine Mittelstellung zwischen den beiden extremen Methoden (single

-bzw. complete - linkage) ein. Es basiert darauf, dass der Abstand zweier Objektklassen Ar,

As durch den Durchschnitt aller Distanzen zwischen Objekten aus den beiden Klassen

gebildet wird.

D A An n

dr sr s

kll Ak A sr

( , ):=∈∈∑∑1

© Marcus Hudec 3-5


Demgemäß genügt es für die Fusionierung zweier Klassen beim Average Linkage-Verfahren,

dass die Objekte der Klassen im Mittel nahe beisammen liegen. Entfernte Objektpaare,

können also durch nahe Objektpaare kompensiert werden.

Im Programmpaket SPSS wird obige Methode als average-linkage between groups

(BAVERAGE) bezeichnet, während eine Variante davon unter dem Namen average-linkage

within groups (WAVERAGE) angeboten wird. Bei dieser Variante erfolgt die Mittelung über

die Distanzen aller im neu entstehenden Cluster möglichen Paarbildungenn nr s+⎛

⎝⎜

⎞

⎠⎟2 .

Zentroid - Methode

Bei diesem Verfahren, welches ebenfalls auf den „mittleren“ Abstand zweier Objektklassen

abzielt, wird die Distanz zweier Objektklassen durch die quadrierte euklidische Distanz der

Klassenschwerpunkte (das sind die Mittelwertsvektoren der jeweiligen Klassen) definiert.

Dieses Verfahren genügt im Allgemeinen nicht der zuvor formulierten Indexbedingung.

Median - Methode

Ein Nachteil der Zentroid-Methode besteht darin, dass bei der Zusammenfassung von zwei

sehr ungleich besetzten Klassen, das Zentroid der entstehenden Klasse durch die größere

Klasse stark dominiert wird, so dass Lance & Williams reklamieren „... characteristic

properties of the smaller group are virtually lost.“.

Die Median Methode versucht diesen Effekt dadurch zu vermeiden, dass beim Verschmelzen

von zwei Klassen die Berechnung des neuen Klassenzentrums für spätere Fusionsschritte

durch eine reine Mittelung der beiden bisherigen Klassenzentren ohne Berücksichtigung der

Besetzungszahlen erfolgt.

Beim Beispiel in der nachstehenden Graphik gehen wir davon aus, dass die Fallzahl in der

Gruppe Ar wesentlich größer als in der Gruppe As sei, dementsprechend liegt der Zentroid der

Gruppe A, welche durch Fusion von Ar und As entstanden ist, näher beim Schwerpunkt von

Ar, während das neue Klassenzentrum beim Medianverfahren genau in der Mitte zu liegen

kommt.

© Marcus Hudec 3-6


Zentroid Methode

r A x A x sAx

i A x

i r A A D

iA, A D i s A A D

Median Methode

rAz A z sAz

iAz

irAAD

i A , A D i s A A D

Ward - Methode

Während alle bisherigen Verfahren den Distanzbegriff zwischen zwei Objekten direkt auf den

zwischen Objektmengen ausweiten, gehört das Ward-Verfahren zu jener Gruppe von

Verfahren, bei denen die Entscheidung über den nächsten Fusionsschritt so getroffen wird,

dass ein globales Heterogenitätsmaß möglichst gering zunimmt. Dieses Verfahren fusioniert

jene beiden Cluster, die zu einem minimalen Homogenitätsverlust (Heterogenitätszuwachs) in

bezug auf das Varianzkriterium führen. Es werden also jene beiden Cluster Ar und As

fusioniert, für die der Ausdruck

n nn n

x xr s

r sr s

⋅+

−2

minimiert wird. Es wird also so fusioniert, dass die Summe der Varianzen innerhalb der

Cluster möglichst langsam wächst.

Diese Methode steht in engem Kontext zu den in Abschnitt 4 behandelten Verfahren, die nach

einer in bezug auf ein bestimmtes Kriterium optimalen Partition suchen. Konkret kann man

als Zielkriterium die minimale Varianzsumme innerhalb der Cluster bei einer vorgegebenen

Clusteranzahl wählen.

Selbstverständlich führt die Anwendung eines hierarchischen Algorithmus, der nur eine

schrittweise Optimierung implementiert, jedoch nicht automatisch zu im Sinne des Varianz-

kriteriums optimalen Partitionen auf den einzelnen Aggregationsebenen.

© Marcus Hudec 3-7


3.4 Rekursive Berechnung der Klassendistanzen

Die in der Praxis relevanten agglomerativen Verfahren lassen sich allgemein durch die im

Folgenden näher beschriebene rekursive Berechnung der Klassendistanzen charakterisieren.

Konkret können wir die Distanz der Objektmenge A, welche durch Fusion von Ar und As

entstanden ist, zu irgendeiner anderen Objektmenge Ai durch folgende Rekursionsformel

ermitteln:

D A A D A A D A A D A A D A A D A Ai r r i s s i r s r i s( , ) ( , ) ( , ) ( , ) ( , ) ( , )= ⋅ + ⋅ i+ ⋅ + ⋅ −α α β γ

Verfahren αr αs β γ

Single-Linkage 1/2 1/2 0 -1/2

Complete-Linkage 1/2 1/2 0 1/2

Zentroid nr/n ns/n -nrns/n 0

Average-Linkage nr/n ns/n 0 0

WARD (nr+ni)/(n+ni) (ns+ni)/(n+ni) -(ni)/(n+ni) 0

Median 1/2 1/2 -1/4 0

Flexible Strategie α α 1-2α 0

Dabei sei n, nr, ns und ni die Anzahl der Elemente in A, Ar, As und Ai.

Es läßt sich zeigen, dass agglomerative Verfahren genau dann monotone hierarchische

Verfahren sind, d.h. dass sie die Indexbedingung immer dann erfüllen, wenn

α α α α β

γ γ γr s r s

α αr s

und

entweder: oder mit

, ,

,

≥ + + ≥

≥ < ≤

0 1

0 0

Bis auf das Zentroid- und Median-Verfahren sind somit alle Verfahren aus der obigen Tabelle

monoton.

© Marcus Hudec 3-8


Abgesehen von der übersichtlichen Parametrisierung, die aus dieser generalisierten Sicht

mittels der rekursiven Darstellungsform ergibt, eignet sich diese vor allem auch für die

algorithmische Umsetzung in bezug auf Laufzeit und Speicherplatzbedarf.

© Marcus Hudec 3-9


4 Optimale Partitionen

4.1 Allgemeine Aspekte

Ausgangspunkt dieser Verfahren bildet ein Gütekriterium für eine Partition, welches die

Qualität einer konkreten Klassifikation misst. Man sucht dann jene Partition, die hinsichtlich

dieses Gütekriteriums optimal ist. Äquivalent dazu kann natürlich auch ein negatives

Kriterium (Heterogenitätsmaß), welches dann minimiert wird, herangezogen werden.

Für die praktische Durchführung sind 3 Detailspezifikationen erforderlich:

• Konkrete Wahl des Gütekriteriums • Vorgabe der Clusteranzahl m • Algorithmische Ermittlung der optimalen Partition Bevor wir die gebräuchlichsten Kriterien vorstellen, wollen wir kurz einen allgemeinen

algorithmischen Ansatz angeben, welcher auf einem Austauschverfahren beruht. Prinzipiell

ist davon auszugehen, dass für in der Praxis relevante Fallzahlen eine exhaustive Suche nach

der optimalen Partition aufgrund des großen Rechenaufwandes unmöglich ist.

Die Anwendung des nachstehenden Verfahrens wird mit unterschiedlichen Startlösungen

empfohlen. Weiters sind zahlreiche Modifikationen des Basisalgorithmus zur Vermeidung

lokaler Optima sind denkbar (z.B. Verzicht auf striktes „hill climbing“).

(1) Sei A1 eine erste Startpartition mit m Klassen (2) Prüfe für jedes Objekt, ob durch den Austausch des Objektes von seiner aktuellen

Klasse zu einer anderen Klasse das Gütekriterium verbessert werden kann. (3) Tausche jenes Objekt, das die größte Verbesserung bewirkt. (4) Iteriere die Schritte (2) und (3), bis keine weitere Verbesserung erzielt werden kann.

4.2 Bestimmen einer Startpartition

Für das Bestimmen einer Anfangspartition sind verschiedene Vorschläge denkbar:

• Verwenden einer durch ein hierarchisches Verfahren gefundenen Partition • Verwenden mehrerer zufälliger Anfangspartitionen • Gruppierung um „Kristallisationskerne“

Bei diesen Verfahren wird davon ausgehen, dass Anfangsvermutungen in bezug auf die

Clusterschwerpunkte getroffen werden können und die einzelnen Beobachtungen werden

sequentiell jenem Cluster zugeordnet, zu dem sie als nächstes liegen. Dabei kann etwa in

SPSS optional jeweils nach der Zuordnung einer Beobachtung der betroffene Gruppenkern © Marcus Hudec 4-1


neu ermittelt werden, oder es erfolgt die Neuberechnung immer erst nach einem kompletten

Durchgang durch alle Datenpunkte.

4.3 Optimerungskriterien

Varianzkriterium (WARD)

k

G

i ki Ek

tr W= ∈∑ ∑ − =

1

2x x ( )

Für das Varianzkriterium gilt die folgende Eigenschaft, die für die algorithmische

Bestimmung einer optimalen Partition nützlich ist. In einer bezüglich des Varianzkriteriums

optimalen Partition gilt für jedes Element aus der Klasse k (k=1, ..., G), dass sein quadrierter

euklidische Abstand zum Klassenmittelpunkt der eigenen Klasse k kleiner oder höchstens

gleich dem quadrierten euklidischen Abstand zu den übrigen Klassenmittelpunkten ist.

(Minimal-Distanz Eigenschaft).

Ausgehend von einer beliebigen ersten Partition A1 können iterativ neue Partitionen generiert

werden, indem beim Wechsel von der Partition An zu An+1 genau jene Elemente ausgetauscht

werden, welche die notwendige (aber nicht hinreichende!) Minimal-Distanz - Bedingung

noch nicht erfüllen.

© Marcus Hudec 4-2


Determinantenkriterium (FRIEDMAN/RUBIN)

Beim Determinantenkriterium gilt jene Partition als optimal, welche die Determinante der

Streuungsmatrix innerhalb der Klassen minimiert. Ähnlich wie beim Varianzkriterium gilt

auch hier eine notwendige Minimal-Distanz Eigenschaft, doch kommt statt der euklidischen

Distanz die Mahalanobis-Distanz zur Anwendung.

Verallgemeinertes Determinantenkriterium (SCOTT/SYMONS)

Es wird jene Partition als optimal eingestuft, welche das Kriterium nWnk

k

kk

G

log=∑

1minimiert.

Es ist offensichtlich, dass Optimierungskriterien, die auf den Dispersionsmatrizen basieren, in

engem Kontext mit den Verteilungen der Merkmale in den Gruppen stehen und die Wahl

zwischen den Kriterien in Abhängigkeit von a priori Kenntnissen über die Datenstrukturen

getroffen werden sollten.

Nachdem alle hier vorgestellten Kriterien auch im Kontext der modellbasierenden Verfahren

des Abschnitts 5 relevant sind, verweisen wir bei der Diskussion ihrer Implikationen in bezug

auf die zu erwartenden Clustertypen auf den nächsten Abschnitt.

Abschließend sei darauf verwiesen, dass bei Konvergenz eines konkreten Algorithmus im

Allgemeinen nicht automatisch gesichert ist, dass es sich hierbei um ein globales Optimum

handelt. Daher kann sich selbst bei Verwendung eines konkreten Gütekriteriums durch

unterschiedliche Startwerte oder unterschiedliche Algorithmen eine unterschiedliche

Klassifikation ergeben.

Das bedeutet die gefundenen Klassifikationsergebnisse sind optimal oder nahezu optimal in

bezug auf ein bestimmtes Gütekriterium und in bezug auf eine konkrete algorithmische

Umsetzung. In diesem Sinne ist die Bedeutung von „objektiven“ Gütekriterien dahingehend

zu relativieren, dass sie letztendlich nur eine Operationalisierung des Prozesses der

Klassenbildung unter bestimmten Modellvorstellungen in bezug auf die erwartete Gestalt der

Cluster ermöglichen.

© Marcus Hudec 4-3


4.4 Nearest Centroid Soring (QUICK CLUSTER)

Da die algorithmische Umsetzung aufgrund der kombinatorischen Komplexität insbesondere

bei großen Datensätzen einen hohen Aufwand (Rechenzeit, Speicherbedarf) mit sich bringt,

bieten Softwarepakete wie z.B. SPSS auch einfache Algorithmen an. Diese Verfahren erheben

keinen Anspruch, ein globales Optimum erzielen zu wollen und basieren auf einfachen

Heuristiken, die darin bestehen die Beobachtungspunkte um k-Mittelwerte zu gruppieren.

Verfahren dieser Art werden auch als k-means algorithms bezeichnet.

Das in SPSS in der Procedure QUICK CLUSTER implementierte Verfahren des „Nearest

Centroid Sorting“ geht auf Anderberg (1973) zurück und kann als Verfeinerung der

Gruppierung um Kristallisationskerne, die wir bereits zur Bestimmung von Anfangs-

partitionen kennengelernt haben, angesehen werden.

In einem ersten Schritt können die Anfangszentroide auf dreierlei Weise spezifiziert werden:

VALUE Spezifikation der Anfangszentroide durch den User

FIRST Verwende die ersten k-Datenpunkte als Anfangszentroide

SELECT Ermittlung der Zentroide durch das Programm

Die ersten k Beobachtungen werden zunächst als Klassenzentroide

verwendet. Danach werden alle übrigen Beobachtungen sequentiell

abgearbeitet. Ein Datenpunkt ersetzt einen bisherigen Zentroid, falls seine

kleinste Distanz zu einem aktuellen Zentroid größer ist als die Distanz

zwischen den beiden nächsten Zentroiden, oder falls seine kleinste Distanz zu

einem aktuellen Zentroid größer ist als die kleinste Distanz von diesem

Zentroid zu allen anderen Zentroiden. Es wird jeweils der nächste Zentroid

von dem Datenpunkt ersetzt.

Nachdem die Anfangszentroide spezifiert sind, werden alle Beobachtungen ihrem nächstem

Zentroid zugeordnet. Ist auf diese Weise eine erste Partition gefunden, werden für sämtliche

Klassen die Zentroide neu berechnet.

© Marcus Hudec 4-4


In weiteren Schritten erfolgt dann solange eine neuerliche Klassifikation aller Datenpunkte zu

ihrem nunmehr nächsten Zentroid, bis dasVerfahren konvergiert.

Dabei kann die Neuberechnung der Zentroide wahlweise nach jeder Neuzuordnung erfolgen,

oder jeweils erst nach Abschluß eines Durchgangs durch alle Datenpunkte.

© Marcus Hudec 4-5


5 Modellbasierende hierarchische Klassifikation

5.1 Einleitung

Während historisch gesehen die meisten Algorithmen der Clusteranalyse auf vernünftigen

heuristischen Überlegungen bezüglich der Distanz von Objekten bzw. Objektmengen

basierten, richtete sich in jüngerer Zeit das Interesse vermehrt auf Ansätze, die sich auf ein

explizites Verteilungsmodell für die Stichprobe stützen. Dieser wahrscheinlichkeits-

theoretische Hintergrund erlaubt nicht nur eine theoretische Rechtfertigung älterer Methoden,

sondern hilft auch jene Situationen zu identifizieren, in denen diese heuristisch hergeleiteten

Verfahren ein optimales Ergebnis liefern. Nicht zuletzt führte diese Betrachtungsweise auch

zu neuen verallgemeinerten Verfahren, die in bestimmten Situationen zu besseren

Ergebnissen führen können.

Modellbasierende Verfahren zur automatischen Klassifikation (manchmal auch stochastische

Partitionsverfahren bezeichnet) gehen davon aus, dass die beobachtete Datenmatrix eine

Mischung von mehreren Populationen mit unterschiedlichen Verteilungen repräsentiert.

Konkret nehmen wir an, dass die zugrundeliegende Population aus G verschiedenen

Subpopulationen entstammt und dass die Dichtefunktion für den p-dimensionalen

Beobachtungsvektor x, der der Subpopulation k (k = 1, ..., G) entstammt, durch fk(x; θ)

gegeben ist, wobei θ für einen unbekannten Parametervektor steht.

Es seien n Beobachtungen x1, ..., xn gegeben, und es sei weiters deren unbekannte

Klassenzugehörigkeit durch den Vektor γ = (γ1, ..., γn)’ charakterisiert, wobei γi=k bedeutet,

dass die i-te Beobachtung der Klasse k entstammt.

Das Klassifikationsproblem bedingt dann, das Maximieren der Likelihood

, L fi i

i

n

( , ) ( ; )θ γ θγ==∏ x

1

d.h. wir suchen jenen Klassenzugehörigkeitsvektor γ und jenen Parametervektor θ, welcher

bei gegebener Datenmatrix die obige Likelihood maximiert.

© Marcus Hudec 5-1


Faßt man die Objekte aus der k-ten Klasse in Ek i= =i: γ k zusammen, läßt sich die

Likelihood allgemein wie folgt schreiben:

L f i ki Ek

G

k

( , ) ( )θ γ θ=∈=∏∏ x

1

Man beachte, dass für die numerische Lösung nur solche Partitionen zulässig sind, bei denen

für jede Klasse k (k = 1, ..., G) die Existenz von Parameterschätzern gewährleistet ist.

5.2 Multivariat-normalverteilte Klassen

Naturgemäß haben in der Praxis jene Verfahren, die auf der Annahme der Mischung von

multivariaten Normalverteilungen basieren, die größte Bedeutung erlangt. Unter der

Annahme

fk ( ; )x θ ≈ MVN k k( , )µ Σ

ergibt sich für die obige Likelihood, abgesehen von einem konstanten Faktor

L xki Ek

G

i k k i kk

( , ) exp ( ) ( )/

θ γ µ µ= − − ′ −∈=

−−∏∏ Σ

1

1 2

12

1Σ x

Der ML-Schätzer für µ k ist xk ki E

n x ik

= −

∈∑1 , wobei nk die Anzahl der Elemente in Ek ist.

Analog schätzt man Σ k durch Wk kn/ , wobei W x x x xk i ki E

i kk

= − −∈∑( )( )' ist.

Es zeigt sich, dass unter verschiedenen Annahmen über die Struktur der Varianz-

Kovarianzmatrizen, die obige Maximierungsaufgabe vereinfacht und teilweise auf klassische

durch heuristische Überlegungen hergeleitete Ansätze optimaler Partitionen zurückführt

werden kann.

Unter der Annahme, dass Σ k I für k G= =σ2 1( , ,… ) führt das Maximieren der Likelihood

zum Optimierungsansatz von WARD auf der Basis des Varianzkriteriums.

Unter der Annahme, dass Σ Σk für k G= =( , ,1… ) führt das Maximieren der Likelihood zum

Optimierungsansatz von FRIEDMAN/RUBIN auf der Basis des Determinantenkriteriums.

© Marcus Hudec 5-2


Da beide klassischen Ansätze von WARD bzw. FRIEDMAN/RUBIN eine relativ starre

Struktur in bezug auf die Clustertypen implizieren, wurden verschiedene

Verallgemeinerungen vorgeschlagen.

Eine unmittelbare Verallgemeinerung des Ansatzes von WARD geht auf

BANFIELD/RAFTERY (1993) zurück. Hier wird die ML-Gleichung unter der

Modellannahme Σk kI für k G= =λ ( , ,1… ) optimiert, was verschieden große Cluster zuläßt.

und einem Kriterium der Form n trnk

k

kk

G

logW⎛⎝⎜

⎞

⎠⎟

=∑

1 entspricht. In Analogie zur Arbeit von

SCOTT/SYMONS kann dieses Kriterium als ein verallgemeinertes Varianzkriterium

angesehen werden.

Das verallgemeinerte Determinantenkriterium von SCOTT/SYMONS geht von überhaupt

keinen strukturellen Beschränkungen der gruppenspezifischen Varianz-Kovarianzmatrizen

Σ Σk k= aus.

Die Kriterien S bzw S*, welche auf MURTAGH/RAFTERY bzw. BANFIELD/RAFTERY

zurückgehen nehmen eine Mittelposition zwischen dem Determinantenkriterium und dessen

Verallgemeinerung ein. Das S-Kriterium hält zwar Größe und Form der Cluster konstant

erlaubt jedoch eine unterschiedliche Orientierung. Das S*-Kriterium erlaubt zusätzlich auch

noch die Variation der Clustergröße.

Den Ausgangspunkt für diese Kriterien bildet die Eigenwertzerlegung der Varianz-

Kovarianzmatrix Σk k ktk= D A D , wobei Dk die Matrix der Eigenvektoren und Ak eine

Diagonalmatrix mit den Eigenwerten von Σk ist. Während Ak die Größe und Gestalt der

Cluster definiert, wird ihre Orientierung durch die Matrix Dk festgelegt.

MURTAGH/RAFTERY halten nun Ak = A über alle Cluster konstant und erlauben nur

unterschiedliche Dk für die einzelnen Cluster.

Das S-Kriterium ergibt sich dann als S S wobei S trkk

G

k= = k=

−∑1

1, A Ω( ) gilt. Dabei ergibt

sich Ωk, wenn man die Eigenwertzerlegung für den M.L.-Schätzer Wk der Varianz-

Kovarianzmatrix durchführt W L Lk k kt= kΩ .

© Marcus Hudec 5-3


Erlaubt man noch zusätzlich eine Variation der Clustergrößen so erhält man die M.L.-

Schätzer durch Optimierung des folgenden Kriteriums:

S n S nk kk

G

* log( / )==∑

1k

Die nachfolgende Tabelle gibt einen Überblick über verschiedene Optimalitätskriterien und

die jeweils implizierten strukturellen Restriktionen über die Form der Cluster, welche durch

die Annahmen über die Varianz-Kovarianzmatrizen Σ k bedingt sind.

Kriterium Quelle

Methodenbezeichnung

in S-PLUS

Clustertyp Orientierung Größe Form

Tr(W) Ward (1963)

sum of squares oder

trace

Hyperkugel n.a. konstant konstant

|W| Friedman/Rubin

(1967)

determinant

Ellipsoid konstant konstant konstant

n trnk

k

kk

G

logW⎛

⎝⎜

⎞

⎠⎟

=∑

1

Banfield/Raftery

(1993)

spherical

Hyperkugel n.a. verschieden konstant

S Murtagh/Raftery

(1984)

S

Ellipsoid verschieden konstant konstant

S* Banfield/Raftery

(1993)

S*

Ellipsoid verschieden verschieden konstant

nnk

k

kk

G

logW

=∑

1

Scott/Symons (1971)

unconstrained

Ellipsoid verschieden verschieden verschieden

© Marcus Hudec 5-4


Kennt man a priori die Klassenzahl G, wäre es zumindest theoretisch möglich jene Partition

bestehend aus G Teilmengen zu ermitteln, für welche das gewählte Kriterium optimiert wird.

In S-PLUS ist die modellbasierende Clusteranalyse jedoch als hierarchisch agglomeratives

Verfahren implementiert. Da dies keineswegs bedeutet, dass auf den einzelnen

Aggregationsebenen das Kriterium optimiert wird, geht man so vor, dass sich man aufgrund

des Dendrogramms zunächst die Klassenanzahl festlegt und danach versucht, durch ein

anschließendes Austauschverfahren (mreloc) das Kriterium für die gewählte Klassenanzahl

noch weiter zu optimieren.

Für die Wahl der Klassen wird aufgrund heuristischer Argumente häufig auch der sog. Bayes-

Faktor herangezogen:

B p G k p Gk = = =( | ) / ( |x x1 )

Das auch in S-PLUS implementierte Maß AWEk (approximate weight of evidence for k

clusters) ist eine Approximation von 2logBk auf Basis der Arbeit von Banfield/Raftery

(1993).

Zusätzlich gibt es noch die Möglichkeit das Modell dahingehend zu robustifizieren, dass man

zulässt, dass einzelne Datenpunkte als outlier nicht bei der Bildung der Gruppenstruktur

berücksichtigt werden müssen. Dazu wird der Ausdruck für die Likelihoodfunktion

entsprechend erweitert.

© Marcus Hudec 5-5


6 Ein Anwendungsbeispiel

6.1 Der Datensatz

Datenquelle:

Prices and Earnings Around the Globe

Union Bank of Switzerland 1991

Inhalt:

48 Städte (davon 46 mit vollständigen Angaben)

City City name

Work Weighted average of the number of working hours in 12

occupations

Price Index of the cost 112 goods and services excluding rent

(Zurich = 100)

Salary Index of hourly earnings in 12 occupations after deductions

(Zurich = 100)

City Work Price Salary Amsterdam 1714 65.6 49.0 Athens 1792 53.8 30.4 Bogota 2152 37.9 11.5 Bombay 2052 30.3 5.3 Brussels 1708 73.8 50.5 Buenos Aires 1971 56.1 12.5 ...

Sydney 1668 70.8 52.1 Taipei 2145 84.3 34.5 Tel Aviv 2015 67.3 27.0 Tokyo 1880 115.0 68.0 Toronto 1888 70.2 58.2 Vienna 1780 78.0 51.3 Zurich 1868 100.0 100.0

© Marcus Hudec 6-1


6.2 Deskriptive Analyse

> cities.df<-read.table("c:\\marcus\\uni\\lehre\\clust\\cities\\cities.dat", sep =";", header=T)

> cities.mat<-as.matrix(cities.df) # Datenmatrix (Rohdaten)

> mean(cities.df$Work) [1] 1879.913

> var(cities.df$Work) [1] 30395.33

> mean(cities.df$Price) [1] 70.1

> var(cities.df$Price) [1] 457.4969

> mean(cities.df$Salary) [1] 39.54565

> var(cities.df$Salary) [1] 612.9439

> cities<-scale(cities.mat) # Standardisierte Datenmatrix

> pairs(cities)

© Marcus Hudec 6-2


Größe der Bubbles: Work

-2 -1 0 1 2

-2

-1

0

1

2

P r i c e

© Marcus Hudec

Salary

6-3


> cities.df<-data.frame(cities) # Redefinition des Data-Frames durch # standardisierte Werte > attach(cities.df) > xyplot(Price ~ Salary)

> WW <- equal.count(Work, number=6, overlap=1/4) > WW Data: Amsterdam Athens Bogota Bombay Brussels Buenos Aires -0.951649 -0.504254 1.56064 0.987062 -0.986064 0.522459 ... Zurich -0.06833124 Intervals: min max count -1.7030440 -0.8197255 10 -0.9516497 -0.5730847 10 -0.6132355 -0.1371613 9 -0.2174629 0.3675922 9 0.3561205 0.9870623 10 0.9239681 2.8397368 10 Overlap between adjacent intervals: [1] 3 2 2 2 3

© Marcus Hudec 6-4


> plot(WW, xlab="Range of Work",ylab="") # Graphische Ausgabe des shingle

> xyplot(Price ~ Salary|WW) # Conditional Plot

© Marcus Hudec 6-5


> cloud(Price ~ Salary * Work) # 3D-Sactterplot

> Price.mod<-loess(Price~Salary*Work) # 3D-Darstellung mit Scatterplot Smoother > s.ax<-seq(min(Salary), max(Salary), length = 50) > w.ax<-seq(min(Work), max(Work), length = 50) > grid <- expand.grid(Salary=s.ax, Work=w.ax) > Price.fit<-predict(Price.mod, grid) > wireframe(Price.fit~Salary*Work, data=grid)

© Marcus Hudec 6-6


© Marcus Hudec 6-7


Visualisierung mittels Chernoff-Faces:

faces(cities.mat), labels=dimnames(cities.mat)[[1]], max=48, ncol=6)

© Marcus Hudec 6-8


6.3 Hierarchische Clusteranalyse mit S-PLUS

> cities.dist<-dist(cities) # Euklid’sche Distanzmatrix > cities.dist [1] 1.0338944 3.2067168 3.0980511 0.3896523 2.1316180 [6] 2.4356627 1.3685592 1.3263546 0.6302958 0.7634794 [1031] 1.9432883 1.4721314 0.7709747 2.1919889 2.2764115 attr(, "Size"): [1] 46

> cities.compl<-hclust(cities.dist) # Complete Linkage Clustering > cities.compl $merge: [,1] [,2] [1,] -21 -34 [2,] -27 -45 [3,] -26 -29 [4,] -7 -38 ... [42,] 32 39 [43,] 40 41 [44,] 35 42 [45,] 43 44 $height: [1] 0.1285884 0.2076316 0.2383813 0.2634688 0.2765655 ... [41] 2.5378425 2.8371501 3.2447364 3.7483766 5.8061829 $order: [1] 23 11 12 1 5 40 9 24 10 21 [11] 34 27 45 22 30 16 28 8 44 13 [21] 46 14 32 39 43 20 37 2 31 36 [31] 19 35 26 29 6 17 25 4 33 3 [41] 18 15 41 42 7 38

Die Komponente merge definiert die einzelnen Fusionsschritte, wobei negative Werte auf

Objekte und positive Werte auf Fusionsschritte referenzieren.

Die Komponente height enthält die Indexwerte h() der Fusionsschritte, d.h. beim Complete

Linkage- Algorithmus die maximale Distanz zwischen 2 Objekten aus den beiden im

jeweiligen Schritt zusammengeführten Klassen.

© Marcus Hudec 6-9


Die Komponente order gibt jene Permutation an, die für das Zeichnen des Dendrogramms zu

verwenden ist.

> plclust(cities.compl) # Ausgabe des Dendrogramms



> plclust(cities.compl, labels=dimnames(cities)[[1]])

Zur Entscheidung über die Klassenanzahl ist auch die nachstehende Graphik sinnvoll. Sie zeigt wie mit wachsender Klassenanzahl, das Heterogenitätsmaß h() abnimmt. Als Kriterium für die Wahl der Klassenzahl, kann die Veränderung von h() herangezogen werden. > plot(1:46,c(cities.compl$height[45:1], 0), type="l", xlab="Anzahl der Klassen", ylab="")



> cities.compl.4<-cutree(cities.compl, k=4) # Definition der Klassenanzahl > cities.compl.4 # Partition bestehend aus 4 Gruppen [1] 3 4 1 1 3 4 1 3 3 3 3 3 2 2 1 3 4 1 4 4 3 3 3 3 1 4 3 3 4 [30] 3 4 2 1 3 4 4 4 1 2 3 1 1 2 3 3 2 attr(, "height"): [1] 2.837150 2.537843 2.418134 1.443911

> for (i in 1:4) print(dimnames(cities)[[1]][cities.compl.4==i]) [1] "Bogota" "Bombay" "Caracas" "Hong Kong" "Kuala Lumpur" "Manila" [7] "Panama" "Singpore" "Taipei" "Tel Aviv" [1] "Geneva" "Helsinki" "Oslo" "Stockholm" "Tokyo" "Zurich" [1] "Amsterdam" "Brussels" "Chicago" "Copenhagen" "Dublin" "Dusseldorf" [7] "Frankfurt" "Houston" "London" "Los Angeles" "Luxembourg" "Madrid" [15] "Milan" "Montreal" "New York" "Paris" "Sydney" "Toronto" "Vienna" [1] "Athens" "Buenos Aires" "Johannesburg" "Lagos" "Lisbon" "Mexico City" [7] "Nairobi" "Nicosia" "Rio de Janeiro" "Sao Paulo" "Seoul"



> cities.compl.7<-cutree(cities.compl, k=7) # Verfeinerte Partition mit 7 Klassen > for (i in 1:7) print(dimnames(cities)[[1]][cities.compl.7==i]) [1] "Caracas" "Hong Kong" "Singpore" "Taipei" "Tel Aviv" [1] "Helsinki" "Oslo" "Stockholm" "Tokyo" [1] "Chicago" "Houston" "Los Angeles" "Montreal" "New York" "Toronto" [1] "Athens" "Buenos Aires" "Johannesburg" "Lagos" "Lisbon" "Mexico City" [7] "Nairobi" "Nicosia" "Rio de Janeiro" "Sao Paulo" "Seoul" [1] "Amsterdam" "Brussels" "Copenhagen" "Dublin" "Dusseldorf" [6] "Frankfurt" "London" "Luxembourg" "Madrid" "Milan" "Paris" [12] "Sydney" "Vienna" [1] "Bogota" "Bombay" "Kuala Lumpur" "Manila" "Panama" [1] "Geneva" "Zurich"

In der nachfolgenden Schleife erfolgt eine strukturierte Ausgabe der Originaldatenmatrix,

gegliedert nach der Klassenzugehörigkeit:

> for (i in 1:4) print(cities.mat[cities.compl.4==i,]) Work Price Salary Bogota 2152 37.9 11.5 Bombay 2052 30.3 5.3 ... Taipei 2145 84.3 34.5 Tel Aviv 2015 67.3 27.0 Work Price Salary Geneva 1880 95.9 90.3 Helsinki 1667 113.6 66.6 ... Tokyo 1880 115.0 68.0 Zurich 1868 100.0 100.0 Work Price Salary Amsterdam 1714 65.6 49.0 Brussels 1708 73.8 50.5 ... Toronto 1888 70.2 58.2 Vienna 1780 78.0 51.3 Work Price Salary Athens 1792 53.8 30.4 Buenos Aires 1971 56.1 12.5 ... Sao Paulo 1856 48.9 11.1



Seoul 1842 58.3 32.7

In der nachfolgenden Schleife werden die 4 Klassen durch die Ausgabe der Klassen-

mittelpunkte (Zentroide) charakterisiert.

> for (i in 1:4) print(apply(cities.mat[cities.compl.4==i,], 2, mean)) Work Price Salary 2133.5 54.17 16.08 Work Price Salary 1780.5 108.55 71.3 Work Price Salary 1792 77.52632 55.15789 Work Price Salary 1855.455 50.78182 16.59091

Graphische Ausgabe der Zentroide durch Profildarstellung:



> cities.prof<-matrix(0, 4, 3) > for (i in 1:4) cities.prof[i, ] <- apply(cities[cities.compl.4==i,], 2, mean) > cities.prof [,1] [,2] [,3] [1,] 1.4545328 -0.7447692 -0.9478122 [2,] -0.5702167 1.7976381 1.2826048 [3,] -0.5042547 0.3471997 0.6306014 [4,] -0.1402899 -0.9031756 -0.9271758

> ts.plot(cities.prof[1,], cities.prof[2,], cities.prof[3,], cities.prof[4,], lty=c(1,3,5,7), xlab= + "Work Price Salary", + xaxt="n") > legend(locator(1), c("1","2","3","4"), lty=c(1, 3, 5, 7))

Auschnitt aus dem Dendrogramm > cities.sub<-subtree(cities.compl,match(c("Luxembourg", "Vienna"), dimnames(cities)[[1]])) > plclust(cities.sub, labels=dimnames(cities)[[1]])



Validierung der Gruppenstruktur durch eine Hauptkomponentenanalyse:

> cities.pc<-prcomp(cities) > x<-cities.pc$x[,1] > y<-cities.pc$x[,2] > plot(x,y,xlab="Princ. Component 1", ylab="Princ. Component 2", type="n") > text(x,y,labels=as.character(cities.compl.4))

1. Hauptkomponente:

0.48 * Work - 0.62 * Price - 0.62 * Salary

2. Hauptkomponente:

0.87 * Work + 0.35 * Price + 0.34 * Salary



Ergebnisse mit dem Single Linkage-Algorithmus

> cities.singl<-hclust(cities.dist, method="connected") > plclust(cities.singl, labels=dimnames(cities)[[1]])

> x<-cities.pc$x[,1] > y<-cities.pc$x[,2] > cities.singl.4<-cutree(cities.singl, k=4) > plot(x,y,xlab="Princ. Component 1", ylab="Princ. Component 2", type="n") > text(x,y,labels=as.character(cities.singl.4))





Ergebnisse mit dem Average Linkage-Algorithmus

> cities.avg<-hclust(cities.dist, method="average") > plclust(cities.avg, labels=dimnames(cities)[[1]])

> x<-cities.pc$x[,1]

> y<-cities.pc$x[,2]

> cities.avg.4<-cutree(cities.avg, k=4)

> plot(x,y,xlab="Princ. Component 1", ylab="Princ. Component 2", type="n")

> text(x,y,labels=as.character(cities.avg.4))



6.4 Hierarchische Verfahren in SPSS

PROXIMITIES work price salary /MATRIX OUT ('C:\DOKUME~1\HUDEC~1.ISO\LOKALE~1\Temp\spss3532\spssclus.tmp') /VIEW= CASE /MEASURE= SEUCLID /PRINT NONE /ID= city /STANDARDIZE= VARIABLE Z . CLUSTER /MATRIX IN ('C:\DOKUME~1\HUDEC~1.ISO\LOKALE~1\Temp\spss3532\spssclus.tmp') /METHOD COMPLETE /ID=city /PRINT SCHEDULE /PLOT DENDROGRAM VICICLE. ERASE FILE= 'C:\DOKUME~1\HUDEC~1.ISO\LOKALE~1\Temp\spss3532\spssclus.tmp'.



Zuordnungsübersicht

Zusammengeführte Cluster

Erstes Vorkommen des Clusters

Schritt Cluster 1 Cluster 2 Koeffizienten Cluster 1 Cluster 2 Nächster

Schritt 1 21 34 ,017 0 0 12 2 27 45 ,044 0 0 12 3 26 29 ,057 0 0 24 4 7 38 ,073 0 0 22 5 5 40 ,077 0 0 10 6 3 18 ,081 0 0 20 7 11 12 ,096 0 0 23 8 8 44 ,097 0 0 18 9 2 31 ,120 0 0 14 10 1 5 ,152 0 5 23 11 19 35 ,156 0 0 19 12 21 27 ,191 1 2 17 13 14 32 ,255 0 0 37 14 2 37 ,280 9 0 25 15 9 24 ,312 0 0 29 16 6 17 ,312 0 0 24 17 10 21 ,337 0 12 29 18 8 28 ,369 8 0 26 19 19 36 ,392 11 0 32 20 3 33 ,469 6 0 27 21 22 30 ,550 0 0 35 22 7 42 ,571 4 0 36 23 1 11 ,602 10 7 28 24 6 26 ,677 16 3 32 25 2 20 ,683 14 0 34 26 8 16 ,930 18 0 35 27 3 4 ,932 20 0 31 28 1 23 1,032 23 0 33 29 9 10 1,393 15 17 33 30 13 43 1,683 0 0 39 31 3 25 1,744 27 0 42 32 6 19 1,838 24 19 34 33 1 9 2,030 28 29 40 34 2 6 2,153 25 32 41 35 8 22 2,162 26 21 39 36 7 41 2,534 22 0 38 37 14 39 2,729 13 0 40 38 7 15 4,292 36 0 42 39 8 13 5,215 35 30 43 40 1 14 6,392 33 37 43 41 2 46 7,420 34 0 44 42 3 7 8,176 31 38 44 43 1 8 10,529 40 39 45 44 2 3 14,095 41 42 45 45 1 2 34,243 43 44 0



* * * * H I E R A R C H I C A L C L U S T E R A N A L Y S I S * * * * * Dendrogram using Complete Linkage Rescaled Distance Cluster Combine C A S E 0 5 10 15 20 25 Label Num +---------+---------+---------+---------+---------+ London 21 òø Paris 34 òú Milan 27 òôòø Vienna 45 òú ó Dublin 10 ò÷ ó Copenhagen 9 òûòú Madrid 24 ò÷ ùòòòòòø Dusseldorf 11 òø ó ó Frankfurt 12 òú ó ó Brussels 5 òú ó ó Sydney 40 òôò÷ ùòòòòòø Amsterdam 1 òú ó ó Luxembourg 23 ò÷ ó ó Helsinki 14 òûòø ó ó Oslo 32 ò÷ ùòòòòò÷ ùòòòòòòòòòòòòòòòòòòòòòòòòòòòòòòòòòø Stockholm 39 òòò÷ ó ó Geneva 13 òòòûòòòø ó ó Tokyo 43 òòò÷ ó ó ó Los Angeles 22 òûòø ùòòòòòòò÷ ó New York 30 ò÷ ó ó ó Chicago 8 òø ùòòò÷ ó Toronto 44 òú ó ó Montreal 28 òôò÷ ó Houston 16 ò÷ ó Athens 2 òø ó Nicosia 31 òú ó Seoul 37 òôòø ó Lisbon 20 ò÷ ó ó Lagos 19 òø ùòòòòòòòø ó Rio de Janeiro 35 òôòú ó ó Sao Paulo 36 ò÷ ó ó ó Mexico City 26 òø ó ùòòòòòòòòòø ó Nairobi 29 òôò÷ ó ó ó Buenos Aires 6 òú ó ó ó Johannesburg 17 ò÷ ó ó ó Zurich 46 òòòòòòòòòòò÷ ó ó Bogota 3 òø ùòòòòòòòòòòòòòòòòòòòòòòòòòòò÷ Kuala Lumpur 18 òú ó Panama 33 òôòø ó Bombay 4 ò÷ ùòòòòòòòø ó Manila 25 òòò÷ ó ó Caracas 7 òø ùòòòòòòòòò÷ Singpore 38 òôòø ó Tel Aviv 42 ò÷ ùòòòø ó Taipei 41 òòò÷ ùòòò÷ Hong Kong 15 òòòòòòò÷



6.5 Modellbasierende Hierarchische Clusteranalyse mit SPLUS

clnum<-function(x, num)

# Redefinition der Gruppenbezeichnungen durch “1”,“2”, ...

hx<-mclass(x, num)$classification

hy<-sort(unique(hx))

for (i in 1:num) hx[hx==hy[i]] <- i

as.character(hx)

# Berechnung von Klassifikationen auf der Basis verschiedener Optimalitätskriterien

m1<- mclust(cities, method="sum of squares")

m2<- mclust(cities, method="spherical")

m3<- mclust(cities, method="determinant")

m4<- mclust(cities, method="S")

m5<- mclust(cities, method="S*")

m6<- mclust(cities, method="unconstrained")

# Graphische Ausgabe der ermittelten Klassifikationen

win.graph()

par(mfrow=c(2,1))

plclust(m1$tree, labels=dimnames(cities)[[1]], main = "Sum of Squares")

par(mar=c(5,4,0,2))

plot(x,y, xlab="Princ. Component 1", ylab="Princ. Component 2", type="n")

text(x,y, labels=clnum(m1, 4))



win.graph()

par(mfrow=c(2,1))

plclust(m2$tree, labels=dimnames(cities)[[1]], main = "Sphercial")

par(mar=c(5,4,0,2))



win.graph()

par(mfrow=c(2,1))

plclust(m3$tree, labels=dimnames(cities)[[1]], main = "Determinant")

par(mar=c(5,4,0,2))



win.graph()

par(mfrow=c(2,1))

plclust(m4$tree, labels=dimnames(cities)[[1]], main = "S - Criterion")

par(mar=c(5,4,0,2))



win.graph()

par(mfrow=c(2,1))

plclust(m5$tree, labels=dimnames(cities)[[1]], main = "S* - Criterion")

par(mar=c(5,4,0,2))



win.graph()

par(mfrow=c(2,1))

plclust(m6$tree, labels=dimnames(cities)[[1]], main = "Unconstrained")

par(mar=c(5,4,0,2))











Ein heuristisches Hilfsmittel zur Selektion der Klassenanzahl bei den modellbasierenden

Verfahren stellt das AWE-Kriterium dar.

> plot(1:46, m1$awe, xlab="Number of Clusters", ylab="AWE", type="l",

+ main="Approximate Weight of Evidence")

Mittels der Funktion mreloc kann durch eine iterative Relokation von einzelnen Elementen versucht werden, die in einem ersten Schritt gefundene Klassifikation in bezug auf das Gütekriterium noch weiter zu erhöhen. > m2.class <-mclass(m2, 4)

> m2.reclass<-mreloc(m2.class, cities, method="spherical")

> m2.class$classification

[1] 1 2 3 3 1 2 2 8 1 1 1 1 8 8 8 8 2 3 2 2 1 8 1 1 3 2 1 8 2 8 2 8 3 1 2 2 2 2 8 1 8 2 8 8 1 8

> m2.reclass

[1] 1 2 3 3 1 2 2 8 1 1 1 1 8 8 3 8 2 3 2 2 1 8 1 1 3 2 1 8 2 8 2 8 3 1 2 2 2 2 8 1 8 2 8 8 1 8

> m2.class$classification- m2.reclass

[1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0



6.6 QUICK-Cluster Algorithmus mit SPSS

QUICK CLUSTER work price salary /MISSING=LISTWISE /CRITERIA= CLUSTER(3) MXITER(10) CONVERGE(0) /METHOD=KMEANS(NOUPDATE) /SAVE CLUSTER /PRINT ID(city ) INITIAL ANOVA CLUSTER DISTAN.

Anfängliche Clusterzentren

1583 1978 2375115,5 71,9 63,8

63,7 46,3 27,8

WORKPRICESALARY

1 2 3Cluster

Iterationsprotokolla

133,966 36,908 56,08425,403 11,832 100,133

4,702 6,375 ,000,000 ,000 ,000

Iteration1234

1 2 3Änderung in Clusterzentren

Konvergenz wurde aufgrund geringer oder keinerÄnderungen der Clusterzentren erreicht. Diemaximale Änderung der absoluten Koordinatenfür jedes Zentrum ist ,000. Die aktuelle Iterationlautet 4. Der Mindestabstand zwischen denanfänglichen Zentren beträgt 397,513.

a.



Cluster-Zugehörigkeit

Amsterdam 1 28,907Athens 1 57,656Bogota 3 71,476Bombay 2 100,425Brussels 1 33,281Buenos Aires 2 24,528Caracas 2 81,444Chicago 2 48,999Copenhagen 1 33,424Dublin 1 18,604Dusseldorf 1 50,149Frankfurt 1 92,070Geneva 2 104,819Helsinki 1 85,642Hong Kong 3 154,260Houston 2 20,929Johannesburg 2 25,624Kuala Lumpur 3 55,910Lagos 1 69,239Lisbon 1 33,001London 1 9,323Los Angeles 2 110,835Luxembourg 1 37,709Madrid 1 36,026Manila 3 50,479Mexico City 2 37,270Milan 1 33,723Montreal 1 86,918Nairobi 2 35,297New York 2 42,224Nicosia 1 90,286Oslo 1 163,786Panama 2 118,165Paris 1 6,686Rio de Janeiro 1 46,361Sao Paulo 2 110,492Seoul 1 103,445Singpore 2 80,990Stockholm 1 73,627Sydney 1 73,303Taipei 3 83,957Tel Aviv 2 52,528Tokyo 2 101,820Toronto 2 79,068Vienna 1 39,685Zurich 2 105,417

Fallnummer12345678910111213141516171819202122232425262728293031323334353637383940414243444546

CITY Cluster Distanz



Clusterzentren der endgültigen Lösung

1741 1963 222175,7 67,4 53,945,4 32,7 17,5

WORKPRICESALARY

1 2 3Cluster

Distanz zwischen Clusterzentren der endgültigen Lösung

222,472 481,874222,472 259,415481,874 259,415

Cluster123

1 2 3

ANOVA

575802,02 2 5027,572 43 114,529 ,0001087,678 2 428,186 43 2,540 ,0911918,555 2 498,537 43 3,848 ,029

WORKPRICESALARY

Mittel derQuadrate df

ClusterMittel derQuadrate df

Fehler

F Sig.

Die F-Tests sollten nur für beschreibende Zwecke verwendet werden, da die Cluster sogewählt wurden, daß die Differenzen zwischen Fällen in unterschiedlichen Clusternmaximiert werden. Dabei werden die beobachteten Signifikanzniveaus nicht korrigiertund können daher nicht als Tests für die Hypothese der Gleichheit der Clustermittelwerteinterpretiert werden.

Anzahl der Fälle in jedem Cluster

23,00018,000

5,00046,000

,000

123

Cluster

GültigFehlend



7 Ähnlichkeit bei binären Merkmalen

Wir betrachten p binäre Merkmale M1 bis Mp.

Die Ähnlichkeit zweier Objekte Oj und Ok wird durch das Ausmaß der Übereinstimmung

bzw. Nichtübereinstimmung der binären Merkmale bestimmt. Diese Eigenschaften lassen sich

allgemein in einer 2x2 Kontingenztafel zusammenfassen, die für jedes Paar von Objekten

aufgestellt werden kann:

Ok

Oj

0 1

0 ajk bjk p-ej

1 cjk djk ej

p-ek ek p

Ähnlichkeitsmaße bei binären Daten sind eine Funktion der in der obigen Tabelle enthaltenen

Anzahlen.

Dabei erscheint es sinnvoll zu fordern, dass die Ähnlichkeit

• monoton mit d wächst • symmetrisch in b und c ist • monoton mit b und c fällt Zu unterscheiden sind 2 Typen binärer Merkmale:

symmetrische Merkmale: xki = xji = 1 hat den gleichen Informationswert wie xki = xji = 0

Beispiel: männlich, weiblich

unsymmetrische Merkmale xki = xji = 1 hat anderen Informationswert als xki = xji = 0

Beispiel: rot, nicht rot

Demgemäß können die Ähnlichkeitsmaße typisiert werden:

© Marcus Hudec 7-1


Vertauschungsinvariante Ähnlichkeitsmaße behandlen für alle Merkmale die beden

Alternativen in gleicher Weise. Dann ändert sich der Wert nicht, wenn man für einzelne oder

alle Merkmale die Codierung vertauscht. Ein Ähnlichkeitsmaß ist insbesondere dann

invariant, wenn sein Wert nur von der Anzahl der übereinstimmenden (a+d) sowie der Anzahl

der nicht übereinstimmenden Komponenten (b+c) abhängt. Invariante Ähnlichkeitsmaße

eignen sich zur Behandlung von symmetrischen Merkmalen bei unsymmetrischen Merkmalen

ist ihre Anwendung nicht sinnvoll.

7.1 Vertauschungsinvariante Ähnlichkeitsmaße

7.1.1 Der M-Koeffizient:

SM simple matching similarity measure

relativer Anteil der übereinstimmenden Komponenten

pxx

pcb

pda

s jkjkjkjkjkjk

2

11−

−=+

−=+

=

sjk = 0 für komplementäre Vektoren

sjk = 1 für in allen Komponenten übereinstimmende Vektoren

7.1.2 Äquivalente Modifikationen des M-Koeffizienten:

Der Nenner des M-Koeffizienten p = (a+d) + (b+c) gewichtet die übereinstimmenden und

nicht übereinstimmenden Komponenten gleich stark. Häufig will man jedoch hier eine

Differenzierung vornehmen:

))(1()()(

jkjkjkjk

jkjkjk cbudau

daus

+−++

+= ,

wobei 0 < u < 1.

© Marcus Hudec 7-2


Für u =1/2 erhalten wir den M-Koeffizienten.

Für u =1/3 erhalten wir den Koeffizienten von Rogers und Tanimoto (RT):

)()(

jkjk

jkjkjk cbp

das

++

+=

Für u =2/3 erhalten wir den Koeffizienten von Sokal & Sneath (SS1):

)()(2

jkjk

jkjkjk dap

das

++

+=

HAMAN verwendet die relative Differenz übereinstimmender bzw. nicht übereinstimmender

Komponenten (HAMAN):

1)(

2)()(

−+

=+−+

=p

dap

cbdas jkjkjkjkjkjk

jk

7.2 Nichtvertauschungsinvariante Ähnlichkeitsmaße

7.2.1 Der S-Koeffizient und seine Modifikationen

Ergibt sich, wenn man beim M-Koeffizienten im Zähler und Nenner die übereinstimmenden 0

- Komponenten ignoriert.

S (similarity ratio) in SPSS als JACARD() implementiert:

jkjkjkjkjkjk

jk

jk

jkjk dcbcbd

dap

ds

/)(11++

=++

=−

=

© Marcus Hudec 7-3


sjk = 0 wenn keine 1 Komponenten übereinstimmen

sjk = 1 für in allen Komponenten übereinstimmende Vektoren

Führt man auch hier eine Gewichtung ein so ergeben sich folgende Modifikationen:

))(1( jkjkjk

jkjk cbuud

uds

+−+=

Für u = 2/3 das Maß nach DICE:

)(22

jkjkjk

jkjk cbd

ds

++=

Für u = 1/3 das Maß nach Sokal & Sneath (SS2)

)(2 jkjkjk

jkjk cbd

ds

++=

Eine weitere äquivalente Variante des S-Koeffizienten ist das Maß nach Kulczynski (K1):

)( jkjk

jkjk cb

ds

+=

Betrachtet man:

j

jk

jkjk

jkjk e

ddc

ds =

+=

)(

so läßt sich der Ausdruck als bedingte Wahrscheinlichkeit dafür interpretieren, dass ein

zufällig ausgewähltes Merkmal, das bei Oj den Wert 1 hat auch bei Ok den Wert 1 hat.

Analoges gilt, wenn man ej durch ek ersetzt.

© Marcus Hudec 7-4


Kulczynski (K2) verwendet das arithemtische Mittel dieser bedingten Wahrscheinlichkeiten:

⎟⎟⎠

⎞⎜⎜⎝

⎛+=

k

jk

j

jkjk e

ded

s21

OCHIAI verwendet das geometrische Mittel:

kj

jkjk ee

ds =

7.3 Assoziationsmaße

7.3.1 Der Korrelationskoeffizient bei binären Merkmalen

))()()(()()( dcdbcababcad

eepeep

eepdr

jjkk

jkjkjk

++++−

=−−

−=

vertauschungsinvariant

rjk=1 wenn die Vektoren identisch sind

rjk = -1 wenn die Vektoren komplementär sind

rjk = 0 wenn (empirische) Unabhängigkiet vorliegt

Bei Unabhängigkeit:

1. ===jkjk

jkjkkjjk

cbda

cprbzwpe

pe

pd

© Marcus Hudec 7-5


Weitere Ähnlichkeitsmaße könne aus dem YULE-schen Assoziationskoeffizient bzw. aus

dem Prädikationsmaß von Goodman & Kruskal abgeleitet werden.

YULE: 11

+−

=+−

=cprcpr

bcadbcadQ

sjk = 1 wenn b oder c oder beide gleich null sind. Alle bei j vorhandenen

Merkmale müssen auch bei k vorhanden sein

sjk = -1 wenn a oder d oder beides gleich null sind. Keine 0Komponente und

keine 1 Komponente stimmt überein.

Manchmal wird auch: bcadbcadY

+−

=

verwendet.

7.4 Beispiele für binäre Clusteranalysen mit SPSS

Beispiel für „SIMPLE MATCHING SIMILARITY MEASURE“-Clusteranalyse in SPSS

CLUSTER pricebin salbin workbin

/METHOD COMPLETE

/MEASURE= SM (1,2)

/PRINT SCHEDULE CLUSTER(2)

/PRINT DISTANCE

/PLOT DENDROGRAM VICICLE.

© Marcus Hudec 7-6


SIMPLE MATCHING SIMILARITY MEASURE:

Zuordnungsübersicht

45 46 1,000 0 0 2

5 45 1,000 0 1 6

30 44 1,000 0 0 15

40 43 1,000 0 0 6

38 42 1,000 0 0 7

5 40 1,000 2 4 13

3 38 1,000 0 5 16

36 37 1,000 0 0 9

2 36 1,000 0 8 14

31 35 1,000 0 0 14

32 34 1,000 0 0 13

29 33 1,000 0 0 16

5 32 1,000 6 11 18

2 31 1,000 9 10 26

8 30 1,000 0 3 29

3 29 1,000 7 12 20

27 28 1,000 0 0 18

5 27 1,000 13 17 22

25 26 1,000 0 0 20

3 25 1,000 16 19 28

23 24 1,000 0 0 22

5 23 1,000 18 21 31

16 22 1,000 0 0 29

14 21 1,000 0 0 31

19 20 1,000 0 0 26

2 19 1,000 14 25 42

17 18 1,000 0 0 28

3 17 1,000 20 27 37

8 16 1,000 15 23 41

7 15 1,000 0 0 37

5 14 1,000 22 24 33

12 13 1,000 0 0 33

5 12 1,000 31 32 35

10 11 1,000 0 0 35

5 10 1,000 33 34 36

5 9 1,000 35 0 41

3 7 1,000 28 30 39

4 6 1,000 0 0 39

3 4 1,000 37 38 42

39 41 ,667 0 0 43

5 8 ,667 36 29 44

2 3 ,667 26 39 43

2 39 ,333 42 40 45

1 5 ,333 0 41 45

1 2 ,000 44 43 0

Schritt1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

Cluster 1 Cluster 2

ZusammengeführteCluster

Koeffizienten Cluster 1 Cluster 2

Erstes Vorkommen desClusters Nächster

Schritt

Cluster-Zugehörigkeit

1

2

2

2

1

2

2

1

1

1

1

1

1

1

2

1

2

2

2

2

1

1

1

1

2

2

1

1

2

1

2

1

2

1

2

2

2

2

2

1

2

2

1

1

1

1

Fall1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

2 Cluster

© Marcus Hudec 7-7


* * * * * * H I E R A R C H I C A L C L U S T E R A N A L Y S I S * * * * * * Dendrogram using Complete Linkage Rescaled Distance Cluster Combine C A S E 0 5 10 15 20 25 Label Num +---------+---------+---------+---------+---------+ Vienna 45 -+ Zurich 46 -+ Brussels 5 -+ Sydney 40 -+ Tokyo 43 -+ Oslo 32 -+ Paris 34 -+ Milan 27 -+ Montreal 28 -+ Luxembourg 23 -+ Madrid 24 -+ Helsinki 14 -+ London 21 -+ Frankfurt 12 -+ Geneva 13 -+ Dublin 10 -+---------------+ Dusseldorf 11 -+ I Copenhagen 9 -+ +---------------+ New York 30 -+ I I Toronto 44 -+ I I Chicago 8 -+---------------+ +---------------+ Houston 16 -+ I I Los Angeles 22 -+ I I Amsterdam 1 ---------------------------------+ I Stockholm 39 -----------------+---------------+ I Taipei 41 -----------------+ I I Sao Paulo 36 -+ I I Seoul 37 -+ I I Athens 2 -+ I I Nicosia 31 -+---------------+ +---------------+ Rio de Janeiro 35 -+ I I Lagos 19 -+ I I Lisbon 20 -+ I I Singpore 38 -+ I I Tel Aviv 42 -+ I I Bogota 3 -+ +---------------+ Nairobi 29 -+ I Panama 33 -+ I Manila 25 -+ I Mexico City 26 -+ I Johannesburg 17 -+ I Kuala Lumpur 18 -+ I Caracas 7 -+---------------+ Hong Kong 15 -+ Bombay 4 -+ Buenos Aires 6 -+

© Marcus Hudec 7-8


PRICEBIN * SALBIN * WORKBIN Kreuztabelle

Anzahl

7 1 81 18 198 19 27

13 131 5 6

14 5 19

1,002,00

PRICEBIN

Gesamt1,002,00

PRICEBIN

Gesamt

WORKBIN1,00

2,00

1,00 2,00SALBIN

Gesamt

ZELLE FALL CITY

111,00 2,00 Athens

19,00 Lagos

20,00 Lisbon

31,00 Nicosia

35,00 Rio de Janeiro

36,00 Sao Paulo

37,00 Seoul

112,00 1,00 Amsterdam

121,00 39,00 Stockholm

122,00 5,00 Brussels

9,00 Copenhagen

10,00 Dublin

11,00 Dusseldorf

© Marcus Hudec 7-9


12,00 Frankfurt

13,00 Geneva

14,00 Helsinki

21,00 London

23,00 Luxembourg

24,00 Madrid

27,00 Milan

28,00 Montreal

32,00 Oslo

34,00 Paris

40,00 Sydney

43,00 Tokyo

45,00 Vienna

46,00 Zurich

211,00 3,00 Bogota

4,00 Bombay

6,00 Buenos Aires

7,00 Caracas

15,00 Hong Kong

17,00 Johannesburg

18,00 Kuala Lumpur

25,00 Manila



26,00 Mexico City

29,00 Nairobi

33,00 Panama

38,00 Singpore

42,00 Tel Aviv

221,00 41,00 Taipei

222,00 8,00 Chicago

16,00 Houston

22,00 Los Angeles

30,00 New York

44,00 Toronto



8 S-PLUS Library Cluster

Diese Library enthält eine Implementation der Methoden aus dem Buch von Kaufman &

Rousseeuw.

Partitioning Algorithms Hierarchical Algorithms Distance Calculation

pam, clara, fanny agnes, diana, mona daisy

8.1 daisy Dissimilarity Matrix Calculation

DESCRIPTION

Returns a matrix containing all the pairwise dissimilarities (distances) between observations

in the dataset. The original variables may be of mixed types.

USAGE

daisy(x, metric = "euclidean", stand = F, type = list())

REQUIRED ARGUMENTS

x data matrix or dataframe. Dissimilarities will be computed between the rows

of x. Columns of class numeric will be recognized as interval scaled

variables, columns of class factor will be recognized as nominal variables,

and columns of class ordered will be recognized as ordinal variables. Other

variable types should be specified with the type argument. Missing values

(NAs) are allowed.

OPTIONAL ARGUMENTS

metric character string specifying the metric to be used. The currently available options are "euclidean" and "manhattan". Euclidean distances are root sum-of-squares of differences, and manhattan distances are the sum of absolute differences. If not all columns of x are numeric, then this argument will be ignored.

stand logical flag: if TRUE, then the measurements in x are standardized before calculating the dissimilarities. Measurements are standardized for each variable (column), by subtracting the variable's mean value and dividing by the variable's mean absolute deviation. If not all columns of x are numeric, then this argument will be ignored.

© Marcus Hudec 8-1


type list containing some (or all) of the types of the variables (columns) in x. The list may contain the following components: ordratio (ratio scaled variables to be treated as ordinal variables), logratio (ratio scaled variables that must be logarithmically transformed), asymm (asymmetric binary variables). Each component's value is a vector, containing the names or the numbers of the corresponding columns of x. Variables not mentioned in the type list are interpreted as usual (see argument x).

VALUE

an object of class "dissimilarity" containing the dissimilarities among the rows of x. This is

typically the input for the functions pam, fanny, agnes or diana.

Intervallskalierte Variablen:

euclidean ∑=

−=p

imini xxmnd

1

||),(

manhattan ( ) mn

p

imini xxmnd xx −=⎟⎟

⎠

⎞⎜⎜⎝

⎛−= ∑

=

21

1

2/

),(

Standardisierung:

∑ −

−=

ini

inini

xxN

xxz

.

.

1 mit n=1,...,N und i=1,...,p

Ordinale Variablen:

Ersetzt die durch die entsprechenden Ränge nix ,...,, ini Rr 21∈

Verwendet 11

−−

=i

nini R

rz zur Berechnung der Distanzen

Kategorielle Varibalen:

Die Distanz zwischen 2 Objekten n und m wird durch den relativen Anteil der zwischen den

Objekten n und m nicht übereinstimmenden Merkmale bestimmt (simple matching

coefficient).

Symmetrische binäre Merkmale: simple matching coefficient

Unsymmetrische binäre Merkmale: Jaccard coefficient

© Marcus Hudec 8-2


Gemischte Variablen:

[ 10

1

1 ,),( ∈δ

δ=

∑

∑

=

=p

i

inm

p

i

inm

inmd

mnd ]

Wobei für die Gewichte gilt:

0=δ inm , wenn xni oder xmi NA sind, oder wenn i ein unsymmetrisches binäres Merkmal ist

und gleichzeitig xni und xmi beide 0 sind. Ansonsten gilt: 1=δ inm

Der Beitrag der Variablen i hängt von ihrem Typ ab:

(1) Falls i binär oder nominal ist: 10 === inmmini

inm dsonstxxfallsd ,

(2) Falls i intervallskaliert ist: )(min)(max jijjij

miniinm xx

xxd

−

−=

(3) Falls i einer ordinal oder rational skaliert ist: Bestimme die Ränge und wende die

Formel von (2) an

Anwendungsbeispiele:

daisy(x, metric = "manhattan", stand = T) # if all columns are interval scaled variables

daisy(x, type = list(logratio = c(2,5)) # if columns 2 and 5 must be logaritmically

transformed

8.2 Partitioning Around Medoids - pam

Ähnlich zum k-means Verfahren. Nach Vorgabe der Clusteranzahl k minimiert der

Algorithmus folgende Zielfunktion:

∑=

N

nnmedoidnd

1

),( , wobei der medoidn der jeweils nächste Medoid einer Beobachtung

n(n=1,...,N) ist.

© Marcus Hudec 8-3


Der Algorithmus besteht aus 2 Schritten:

(1) Build step Auffinden von k Anfangsmedoiden

(2) Swap step Austauschen der Gruppenzugehörigkeiten, bis die Zielfunktion nicht

mehr verbessert werden kann

Vorteile:

• Input ist wahlweise eine Distanzmatrix oder eine Datenmatrix

• Silhouette plot

Beim Silhouette Plot wird für jede Beobachtung n ein Wert s(n) ermittelt:

Sei A der Cluster der Beobachtung n, so ist a(n) die durchschnittliche Distanz von n zu

allen anderen Elementen aus der Gruppe A.

Sei C irgendein anderer Cluster und d(n, C) die durchschnittliche Distanz von n zu allen

Elementen aus C, und sei B jener Cluster, für den gilt b(n):=minCd(n, C). B wäre also der

"zweitbeste Cluster" für die Beobachtung n.

)(),(max)()(

)(nbna

nanbns −=

Objekte mit einem Wert von s(n) nahe 1 sind gut mit einem Wert von nahe -1 sind

schlecht klassifiziert.

Beispiel:

> x <- rbind(cbind(rnorm(10,0,0.5), rnorm(10,0,0.5)), cbind(rnorm(10,2,0.5), rnorm(10,2,0.5))) > plot(x)

© Marcus Hudec 8-4


x[,1]

x[,2

]

0.0 0.5 1.0 1.5 2.0 2.5

-10

12

> res<-pam(daisy(x, metric = "manhattan"), 2, diss = T) > print(res) Call: pam(x = daisy(x, metric = "manhattan"), k = 2, diss = T) Medoids: [1] 1 18 Clustering vector: [1] 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 Objective function: build swap 1.083 0.8063 Available arguments: [1] "medoids" "clustering" "objective" "isolation" "clusinfo" [6] "silinfo" "diss" "call"

© Marcus Hudec 8-5


> summary(res) Call: pam(x = daisy(x, metric = "manhattan"), k = 2, diss = T) Medoids: [1] 1 18 Clustering vector: [1] 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 Objective function: build swap 1.083 0.8063 Numerical information per cluster: size max_diss av_diss diameter separation [1,] 10 2.052 0.8257 3.696 1.233 [2,] 10 1.430 0.7869 2.373 1.233 Silhouette plot information: cluster neighbor sil_width 3 1 2 0.7478 1 1 2 0.7458 2 1 2 0.7383 5 1 2 0.7219 9 1 2 0.6812 6 1 2 0.6691 7 1 2 0.6466 4 1 2 0.5339 10 1 2 0.4353 8 1 2 0.3848 11 2 1 0.7768 18 2 1 0.7714 14 2 1 0.7323 16 2 1 0.7247 12 2 1 0.7204 13 2 1 0.6927 15 2 1 0.6394 19 2 1 0.6359 20 2 1 0.5290 17 2 1 0.3782 Average silhouette width per cluster: [1] 0.6305 0.6601 Average silhouette width of total data set: [1] 0.6453

© Marcus Hudec 8-6


Dissimilarities : [1] 0.4462 0.2457 2.0523 0.2267 0.4711 1.6331 1.6440 0.4517 1.0866 [10] 4.1784 4.6932 3.8152 3.4740 3.4747 4.5982 2.3198 3.7501 2.9801 [19] 2.8031 0.2005 2.2102 0.6729 0.9173 1.1869 1.4861 0.8979 1.5328 [28] 4.6246 5.1394 4.2614 3.9202 3.9208 5.0444 2.7660 4.1963 3.4263 [37] 3.2493 2.2260 0.4724 0.7168 1.3875 1.4703 0.6974 1.3323 4.4241 [46] 4.9389 4.0608 3.7197 3.7203 4.8439 2.5655 3.9958 3.2258 3.0488 [55] 1.8486 2.3009 1.2432 3.6963 1.9309 2.1692 5.2609 5.7757 4.8977 [64] 4.5565 4.5572 5.6807 3.4023 4.8326 4.0627 3.8856 0.4523 1.8598 [73] 1.8477 0.2250 0.8599 3.9517 4.4665 3.5885 3.2473 3.2479 4.3715 [82] 2.0931 3.5234 2.7534 2.5764 2.1042 1.3954 0.3700 0.6156 3.7073 [91] 4.2221 3.3441 3.0029 3.0036 4.1271 1.8487 3.2790 2.5090 2.3320 [100] 2.4531 2.0849 2.7198 5.8116 6.3263 5.4483 5.1071 5.1078 6.2314 [109] 3.9529 5.3832 4.6133 4.4362 1.7654 1.8670 3.7529 4.2676 3.3896 [118] 3.0484 3.0491 4.1726 1.8942 3.3245 2.5546 2.3775 0.6349 3.7267 [127] 4.2414 3.3634 3.0222 3.0229 4.1465 1.8680 3.2984 2.5284 2.3514 [136] 3.0918 3.6065 2.7285 2.3873 2.3880 3.5116 1.2331 2.6635 1.8935 [145] 1.7165 0.5148 0.7954 0.7044 1.1340 0.5331 1.8586 0.4283 1.1983 [154] 1.3753 1.1936 1.2192 1.2185 0.9312 2.3734 0.9431 1.7131 1.8901 [163] 1.3581 1.9294 0.7831 1.4954 0.7850 1.4069 1.0121 0.5713 1.1242 [172] 1.1542 0.5730 0.4938 1.3498 1.6670 1.4113 1.1443 0.5225 1.9210 [181] 2.2784 0.8481 1.6181 1.7951 1.4303 0.8888 0.5097 0.7700 0.9470 [190] 1.3985 Metric : manhattan Number of objects : 20 Available arguments: [1] "medoids" "clustering" "objective" "isolation" "clusinfo" [6] "silinfo" "diss" "call"

© Marcus Hudec 8-7


> plot(res)

17201915131216141811

810

47695213

0.0 0.2 0.4 0.6 0.8 1.0Silhouette width

Average silhouette width : 0.65

8.3 Clustering Large Applications - Clara

Dieser Algorithmus wendet pam systematisch auf kleinere Sub-"data sets" an. Für eine

zufällige Teilmenge wird eine pam-Analyse durchgeführt und die restlichen Objekte der

Grundgesamtheit dem jeweils nächsten Medoid zugeordnet. Danach wird die Zielfunktion für

den gesamten Datensatz bestimmt.

Das Verfahren wird für mehrere zufällige Teilmengen wiederholt und jene Partition der

Grundgesamtheit, die den geringsten Wert der Zielfunktion aufweist, wird als Lösung

verwendet.

© Marcus Hudec 8-8


8.4 Fuzzy Analysis - fanny

Hierbei handelt es sich um ein Verfahren, das für jede Beobachtung eine

Klassenzugehörigkeit zu jedem Cluster erlaubt.

Sei die Klassenzugehörigkeit einer Beobachtung n zum Cluster k mit unk bezeichnet.

So ergeben sich diese Werte bei bekannten Distanzen d(n.m) durch Minimierung der

folgenden Zielfunktion:

∑∑

∑=

=

=K

kN

nnk

N

mnmknk

u

mnduu

1

1

2

1

22

,

),(

mit

KvuundNiuK

viviv ,,11,,10

1

…… ===≥ ∑=

wobei die unk die unbekannten variablen Größen darstellen. Die Lösung wird durch einen

iterativen numerischen Algorithmus bestimmt.

Um die Schärfe der resultierenden Klassifikation zu beurteilen wird der Dunn's Partition

Coefficient herangezogen:

∑∑= =

=N

n

K

k

nkk N

uF1 1

2

Dabei nimmt der Koeffizient die folgenden Extremwerte an:

(1) Gilt für alle unk=1/k entirely fuzzy clustering Fk=1/k

(2) Gilt für jede Beobachtung n, dass es einen Wert k gibt mit unk=1 crisp clustering Fk=1

© Marcus Hudec 8-9


> res.f<-fanny(daisy(x, metric = "manhattan"), 2, diss = T) > summary(res.f) Call: fanny(x = daisy(x, metric = "manhattan"), k = 2, diss = T) iterations objective 11 9.133 Membership coefficients: [,1] [,2] [1,] 0.93936 0.06064 [2,] 0.90624 0.09376 [3,] 0.92615 0.07385 [4,] 0.73467 0.26533 [5,] 0.93011 0.06989 [6,] 0.89182 0.10818 [7,] 0.79540 0.20460 [8,] 0.68586 0.31414 [9,] 0.90411 0.09589 [10,] 0.74804 0.25196 [11,] 0.08000 0.92000 [12,] 0.14006 0.85994 [13,] 0.14820 0.85180 [14,] 0.10145 0.89855 [15,] 0.17837 0.82163 [16,] 0.13428 0.86572 [17,] 0.33185 0.66815 [18,] 0.07433 0.92567 [19,] 0.16700 0.83300 [20,] 0.24932 0.75068 Coefficients: dunn_coeff normalized 0.7489 0.4978 Closest hard clustering: [1] 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2



Silhouette plot information: cluster neighbor sil_width 3 1 2 0.7478 1 1 2 0.7458 2 1 2 0.7383 5 1 2 0.7219 9 1 2 0.6812 6 1 2 0.6691 7 1 2 0.6466 4 1 2 0.5339 10 1 2 0.4353 8 1 2 0.3848 11 2 1 0.7768 18 2 1 0.7714 14 2 1 0.7323 16 2 1 0.7247 12 2 1 0.7204 13 2 1 0.6927 15 2 1 0.6394 19 2 1 0.6359 20 2 1 0.5290 17 2 1 0.3782 Average silhouette width per cluster: [1] 0.6305 0.6601 Average silhouette width of total data set: [1] 0.6453 Dissimilarities : [1] 0.4462 0.2457 2.0523 0.2267 0.4711 1.6331 1.6440 [8] 0.4517 1.0866 4.1784 4.6932 3.8152 3.4740 3.4747 [15] 4.5982 2.3198 3.7501 2.9801 2.8031 0.2005 2.2102 [22] 0.6729 0.9173 1.1869 1.4861 0.8979 1.5328 4.6246 [29] 5.1394 4.2614 3.9202 3.9208 5.0444 2.7660 4.1963 [36] 3.4263 3.2493 2.2260 0.4724 0.7168 1.3875 1.4703 [43] 0.6974 1.3323 4.4241 4.9389 4.0608 3.7197 3.7203 [50] 4.8439 2.5655 3.9958 3.2258 3.0488 1.8486 2.3009 [57] 1.2432 3.6963 1.9309 2.1692 5.2609 5.7757 4.8977 [64] 4.5565 4.5572 5.6807 3.4023 4.8326 4.0627 3.8856 [71] 0.4523 1.8598 1.8477 0.2250 0.8599 3.9517 4.4665 [78] 3.5885 3.2473 3.2479 4.3715 2.0931 3.5234 2.7534 [85] 2.5764 2.1042 1.3954 0.3700 0.6156 3.7073 4.2221 [92] 3.3441 3.0029 3.0036 4.1271 1.8487 3.2790 2.5090 [99] 2.3320 2.4531 2.0849 2.7198 5.8116 6.3263 5.4483 [106] 5.1071 5.1078 6.2314 3.9529 5.3832 4.6133 4.4362 [113] 1.7654 1.8670 3.7529 4.2676 3.3896 3.0484 3.0491 [120] 4.1726 1.8942 3.3245 2.5546 2.3775 0.6349 3.7267 [127] 4.2414 3.3634 3.0222 3.0229 4.1465 1.8680 3.2984 [134] 2.5284 2.3514 3.0918 3.6065 2.7285 2.3873 2.3880 [141] 3.5116 1.2331 2.6635 1.8935 1.7165 0.5148 0.7954 [148] 0.7044 1.1340 0.5331 1.8586 0.4283 1.1983 1.3753 [155] 1.1936 1.2192 1.2185 0.9312 2.3734 0.9431 1.7131



[162] 1.8901 1.3581 1.9294 0.7831 1.4954 0.7850 1.4069 [169] 1.0121 0.5713 1.1242 1.1542 0.5730 0.4938 1.3498 [176] 1.6670 1.4113 1.1443 0.5225 1.9210 2.2784 0.8481 [183] 1.6181 1.7951 1.4303 0.8888 0.5097 0.7700 0.9470 [190] 1.3985 Metric : manhattan Number of objects : 20 Available arguments: [1] "membership" "coeff" "clustering" "objective" [5] "silinfo" "diss" "call"

8.5 Agglomerative Nesting -agnes

Implementation von klassischen hierarchischen Verfahren.

8.6 Divisive Analysis - diana

It is probably unique in computing a divisive hierarchy, whereas most other software for hierarchical clustering is agglomerative. Moreover, diana provides (a) the divisive coefficient (see diana.object) which measures the amount of clustering structure found; and (b) the banner, a novel graphical display (see plot.diana).

The diana-algorithm constructs a hierarchy of clusterings, starting with one large cluster containing all n observations. Clusters are divided until each cluster contains only a single observation. At each stage, the cluster with the largest diameter is selected. (The diameter of a cluster is the largest dissimilarity between any two of its observations.) To divide the selected cluster, the algorithm first looks for its most disparate observation (i.e., which has the largest average dissimilarity to the other observations of the selected cluster). This observation initiates the "splinter group". In subsequent steps, the algorithm reassigns observations that are closer to the "splinter group" than to the "old party". The result is a division of the selected cluster into two new clusters.



> res.d<-diana(daisy(x, metric = "manhattan"), diss = T) > summary(res.d) Call: diana(x = daisy(x, metric = "manhattan"), diss = T) Merge: [,1] [,2] [1,] -2 -3 [2,] -5 -9 [3,] -11 -18 [4,] -1 1 [5,] 2 -6 [6,] -14 -19 [7,] -17 -20 [8,] 6 -15 [9,] 3 -16 [10,] 4 5 [11,] 9 -12 [12,] 11 -13 [13,] -4 -7 [14,] 10 -10 [15,] 14 -8 [16,] 12 8 [17,] 16 7 [18,] 15 13 [19,] 18 17 Order of objects: [1] 1 2 3 5 9 6 10 8 4 7 11 18 16 12 13 14 19 15 [19] 17 20 Height: [1] 0.4462 0.2005 0.9173 0.2250 0.4523 1.5328 1.8670 [8] 3.6963 1.2432 6.3263 0.4283 0.8481 0.9431 1.1936 [15] 1.9294 0.4938 0.5713 2.3734 0.5097 Divisive coefficient: [1] 0.8889 Dissimilarities : [1] 0.4462 0.2457 2.0523 0.2267 0.4711 1.6331 1.6440 [8] 0.4517 1.0866 4.1784 4.6932 3.8152 3.4740 3.4747 [15] 4.5982 2.3198 3.7501 2.9801 2.8031 0.2005 2.2102 [22] 0.6729 0.9173 1.1869 1.4861 0.8979 1.5328 4.6246 [29] 5.1394 4.2614 3.9202 3.9208 5.0444 2.7660 4.1963 [36] 3.4263 3.2493 2.2260 0.4724 0.7168 1.3875 1.4703 [43] 0.6974 1.3323 4.4241 4.9389 4.0608 3.7197 3.7203 [50] 4.8439 2.5655 3.9958 3.2258 3.0488 1.8486 2.3009 [57] 1.2432 3.6963 1.9309 2.1692 5.2609 5.7757 4.8977 [64] 4.5565 4.5572 5.6807 3.4023 4.8326 4.0627 3.8856 [71] 0.4523 1.8598 1.8477 0.2250 0.8599 3.9517 4.4665 [78] 3.5885 3.2473 3.2479 4.3715 2.0931 3.5234 2.7534 [85] 2.5764 2.1042 1.3954 0.3700 0.6156 3.7073 4.2221 [92] 3.3441 3.0029 3.0036 4.1271 1.8487 3.2790 2.5090 [99] 2.3320 2.4531 2.0849 2.7198 5.8116 6.3263 5.4483



[106] 5.1071 5.1078 6.2314 3.9529 5.3832 4.6133 4.4362 [113] 1.7654 1.8670 3.7529 4.2676 3.3896 3.0484 3.0491 [120] 4.1726 1.8942 3.3245 2.5546 2.3775 0.6349 3.7267 [127] 4.2414 3.3634 3.0222 3.0229 4.1465 1.8680 3.2984 [134] 2.5284 2.3514 3.0918 3.6065 2.7285 2.3873 2.3880 [141] 3.5116 1.2331 2.6635 1.8935 1.7165 0.5148 0.7954 [148] 0.7044 1.1340 0.5331 1.8586 0.4283 1.1983 1.3753 [155] 1.1936 1.2192 1.2185 0.9312 2.3734 0.9431 1.7131 [162] 1.8901 1.3581 1.9294 0.7831 1.4954 0.7850 1.4069 [169] 1.0121 0.5713 1.1242 1.1542 0.5730 0.4938 1.3498 [176] 1.6670 1.4113 1.1443 0.5225 1.9210 2.2784 0.8481 [183] 1.6181 1.7951 1.4303 0.8888 0.5097 0.7700 0.9470 [190] 1.3985 Metric : manhattan Number of objects : 20 Available arguments: [1] "order" "height" "dc" "merge" "diss" "call" > plot(res.d,ask=T) Make a plot selection (or 0 to exit): 1: plot: All 2: plot: Banner 3: plot: Clustering Tree

1

2 3

4

5

6

7

8

9

10

11

12

13

14 15

16

1718 19 20

02

46

Hei

ght



HeightDivisive Coefficient = 0.89

6.33 5.40 4.80 4.20 3.60 3.00 2.40 1.80 1.20 0.60 0.0

2017151914131216181174810695321

8.7 Monothetic Analysis - mona

Ein divisiver Algorithmus, der über einer binären Datenmatrix operiert.


Multivariate Statistische Verfahren II CLUSTERANALYSE

9 Literatur

Anderberg, M.R. (1973). Cluster Analysis for applications. Academic Press, New York.

Banfield, J.D. and Raftery A.E. (1993). Model-Based Gaussian and Non-Gaussian Clustering.

Biometrics 49, p.803 - 822.

Bock, H.H. (1974). Automatische Klassifikation. Vandenhoeck & Ruprecht, Göttingen.

Deichsel, G. und Trampisch, H.J. (1985). Clusteranalyse und Diskriminanzanalyse. Gustav

Fischer Verlag, Stuttgart - New York.

Everitt, B.S. (1974): Cluster analysis. Heinemann, London.

Fahrmeir, L. und Hamerle, A. (1984). Multivariate Statistische Verfahren. Walter de Gruyter,

Berlin.

Gordon, A.E. (1981). Classification: Methods for the Exploratory Analysis of Multivariate

Data. Chapman and Hall, New York.

Hand, D.J. (1981). Discrimination and Classification. John Wiley & Sons, Chichester.

Hartigan, J.A. (1975). Clustering algorithms. John Wiley & Sons, New York.

Kaufman, L. and Rousseeuw, P.J. (1990). Finding Groups in Data - An Introduction to

Cluster Analysis. John Wiley & Sons, New York.

Murtagh, F. (1985). Multidimensional Clustering Algorithms. Physica-Verlag, Heidelberg.

Vogel, F. (1975). Probleme und Verfahren der numerischen Klassifikation. Vandenhoeck &

Ruprecht, Göttingen.

© Marcus Hudec 9-1

Documents

Einführung in die CLUSTERANALYSE - Zentraler ...homepage.univie.ac.at/marcus.hudec/Lehre/WS 2006/Methoden DA... · Multivariate Statistische Verfahren CLUSTERANALYSE INHALTSVERZEICHNIS