Upload
others
View
5
Download
0
Embed Size (px)
Citation preview
8 Clusteranalyse
Ziel: Unterteilung beobachteter Objekte in homogene Gruppen. Vorab meist
weder Anzahl noch Charakteristika der Gruppen bekannt.
Anwendungsbeispiele:
• Mikrobiologie: Ermittlung der Verwandtschaft bei Kleinstlebewesen
• Medizin: Bestimmung von Patienten mit demselben Krankheitsbild
zwecks gezielter Therapie oder Ursachenforschung
• Marketing: Finden von Absatzregionen mit ahnlichen Merkmalen zwecks
gezielter Werbung, Produkttests auf reprasentativen Markten
Schritte einer Clusteranalyse:
1. Messung der Ahnlichkeiten unter Objekten:
Berechnung eines Ahnlichkeitsmaßes fur jedes Paar von Objekten.
2. Gruppierung der Objekte:
Bilden von homogenen Gruppen ahnlicher Objekte, mit großen Unter-
schieden zwischen den Gruppen (Heterogenitat).
Beispiel 8.1. Archaologie
Relief in der Apadana von Persepolis (Sudiran): 24 steinerne persische
Bogenschutzen mit leichten Unterschieden (Lockung des Barts, Kopf-
schmuck,...).
Fragen: Sind alle Bogenschutzen in derselben Zeit entstanden?
Stammen sie von einem oder mehreren Bildhauern?
Antwort mittels Clusteranalyse.
132
Identifikation von 21 Unterschiedsmerkmalen (A - U) zwischen den
Schutzen. Jedes Merkmal mit nur wenigen Variationen (meist 2 oder
3, bis zu 6).
Zur Gruppierung Feststellung der Ahnlichkeiten unter den Bo-
genschutzen. Welche Bogenschutzen sind sich am meisten/wenigsten
ahnlich? Notwendig: Ahnlichkeitsmaß.
Bogen- Merkmal
schutze A B C D E F G H I J K L M N O P Q R S T U
1 2 2 1 2 3 2 1 1 2 1 1 3 0 0 2 3 4 2 2 2 0
2 2 2 1 2 2 2 1 1 2 1 1 3 1 1 2 0 4 2 2 1 2
3 2 2 1 2 2 2 1 1 2 1 2 3 2 2 2 3 0 3 2 1 3
4 2 2 1 2 3 1 1 1 2 1 2 3 2 2 2 3 4 2 2 1 3
5 2 3 1 3 2 2 1 1 2 1 2 0 2 2 4 3 4 3 2 1 3
6 2 3 1 2 2 2 1 1 2 1 2 3 2 2 4 3 4 3 2 1 3
7 2 3 1 3 3 2 1 1 2 2 2 3 2 2 3 3 4 3 2 1 3
8 2 3 1 3 3 2 2 1 2 2 1 2 2 2 3 3 4 3 2 1 3
9 3 1 1 3 2 2 1 2 2 1 1 2 1 1 3 2 2 4 3 2 2
10 3 1 1 3 2 2 1 2 2 2 1 2 2 2 3 2 2 2 2 2 2
11 3 1 1 3 2 2 1 2 2 1 2 2 2 2 0 2 2 4 3 2 2
12 3 1 2 2 2 2 1 2 2 1 2 2 1 1 1 5 2 2 3 1 3
13 3 1 1 3 2 2 1 2 2 2 2 2 1 1 0 0 3 2 2 2 3
14 3 1 1 3 2 2 1 2 2 2 2 2 2 2 2 5 3 2 2 2 3
15 3 1 1 3 2 2 1 2 2 1 2 2 2 2 3 2 2 4 3 2 2
16 3 1 1 3 2 2 1 2 1 1 2 2 1 1 3 2 4 4 3 2 2
17 3 1 2 3 2 3 1 2 2 2 2 2 1 2 2 3 4 2 2 2 2
18 3 1 1 3 2 2 1 2 2 1 2 2 2 2 6 1 1 2 2 2 2
19 2 1 1 3 2 2 1 2 2 1 2 2 2 2 3 1 4 2 2 2 2
20 2 1 2 2 2 2 3 1 2 1 2 2 2 2 1 3 4 2 2 1 3
21 2 1 2 2 2 2 3 1 2 1 2 2 2 2 0 3 4 2 2 2 3
22 2 1 2 2 2 2 3 1 1 1 2 2 2 1 0 3 4 2 2 2 3
23 2 1 2 2 2 2 3 1 2 1 2 2 2 1 1 3 4 2 2 2 3
24 2 1 1 2 2 2 3 1 2 1 2 2 2 1 2 3 4 2 2 2 3
133
8.1 Ahnlichkeits- und Distanzmaße
Bemerkung 8.2. Wir kehren wieder zur Standard-Notation zuruck.
p-dimensionales Merkmal X = (X1, . . . , Xp)′ beobachtet an n Objekten.
Stichprobe: {x1, . . . , xn} mit i-ter Beobachtung xi = (xi,1, . . . , xi,p)′.
Darstellung der Stichprobe als Datenmatrix :
X =
x1,1 . . . x1,p
... ...
xn,1 . . . xn,p
=
x′1...
x′n
.
Die meisten Clusterverfahren teilen x1, . . . , xn in k disjunkte, alle Objekte
umfassende Gruppen (Cluster) C1, . . . , Ck ein, so dass
Ci ∩ Cj = ∅, i 6= j, undk⋃
i=1
Ci = {x1, . . . , xn}.
Jede Beobachtung (Objekt) gehort zu genau einem Cluster.
Definition 8.3. Ahnlichkeitsmaß
Gegeben seien n Objekte {x1, . . . , xn}. Ein Ahnlichkeitsmaß (similarity mea-
sure) s ordnet je zwei Objekten xi, xj einen Ahnlichkeitswert s(xi, xj) zu.
Dabei besitze die Funktion s folgende Eigenschaften:
• s(xi, xj) = s(xj, xi) (Symmetrie)
• s(xi, xj) ≤ s(xi, xi).
Die symmetrische n× n-Matrix S = [s(xi, xj)]i,j heißt Ahnlichkeitsmatrix.
Haufig fordert man als Normierung s(xi, xj) ∈ [0, 1].
Alternativ: Messung von “Unahnlichkeit” als Abstand der Objekte:
134
Definition 8.4. Distanzmaß
Gegeben seien n Objekte {x1, . . . , xn}. Ein Distanzmaß d ordnet je zwei
Objekten xi, xj einen Abstand d(xi, xj) zu. Notige Eigenschaften von d:
• d(xi, xj) = d(xj, xi) (Symmetrie)
• d(xi, xj) ≥ 0 und d(xi, xi) = 0.
Die symmetrische n× n-Matrix D = [d(xi, xj)]i,j heißt Distanzmatrix.
Gilt zusatzlich
• d(xi, xj) ≤ d(xi, x`) + d(x`, xj) (Dreiecksungleichung),
so spricht man von einem metrischen Distanzmaß.
Distanzmaße in Ahnlichkeitsmaße umwandeln und umgekehrt:
Bemerkung 8.5. Zusammenhang Ahnlichkeitsmaß und Distanzmaß
Ist s ein normiertes Ahnlichkeitsmaß mit 0 ≤ s(xi, xj) ≤ 1, so ist d mit
d(xi, xj) = 1− s(xi, xj) ein Distanzmaß.
Ist d Distanzmaß mit maximaler Distanz dmax = maxi,j d(xi, xj) zwischen
zwei Objekten, so ist s mit s(xi, xj) = 1− d(xi, xj)/dmax Ahnlichkeitsmaß.
Bemerkung 8.6. Ahnlichkeit und Distanz: Situationen
Fur verschiedene Situationen benutzt man verschiedene Maße s und d:
• X1, . . . , Xp binare Merkmale mit genau zwei Auspragungen 0 und 1,
• X1, . . . , Xp nominal skaliert (mindestens ein Variable mit mehr als zwei
Auspragungen),
• X1, . . . , Xp ordinal skaliert,
• X1, . . . , Xp metrisch skaliert.
Wir betrachten nur “reine” Situationen, d.h. alle Merkmale mit selbem Ska-
lenniveau. Bei unterschiedlichen Skalenniveaus alle Merkmale an niedrig-
stes Skalenniveau anpassen und mit Maß hierfur arbeiten (aber: Informa-
tionsverlust) oder ein kombiniertes Maß verwenden.
135
Beispiel 8.7. Binare Variablen
Sei X ein 7-dimensionales Merkmal, das in jeder Komponente nur die
Auspragungen 0 und 1 annimmt. Auspragungen fur drei Objekte:
x1 = (1, 0, 0, 1, 0, 1, 1)′, x2 = (0, 0, 1, 1, 1, 0, 0)′, x3 = (1, 0, 0, 1, 1, 0, 0)′.
Vergleich x1 und x2: An Positionen 2 und 4 stimmen beide Objekte ube-
rein, fur 1, 3, 5, 6, 7 hingegen nicht.
Vergleich x1 und x3: Ubereinstimmung an Positionen 1, 2, 3 und 4.
x1 und x3 scheinen sich ahnlicher zu sein als x1 und x2.
Bemerkung 8.8. Ahnlichkeits- und Distanzmaße fur binare Variablen
Sei X ein p-dimensionales Merkmal, das in jeder Komponente nur die Aus-
pragungen 0 und 1 annimmt. Kontingenztafel der Anzahl der Kombinatio-
nen (1, 1), (1, 0), (0, 1), (0, 0) fur je zwei Objekte xi und xj:
xi 1 0
xj 1 a b a + b
0 c d c + d
a + c b + d p
• Allgemeines Ahnlichkeitsmaß:
s(xi, xj) =a + δd
a + δd + λ(b + c)
• M(atching)-Koeffizient:
s(xi, xj) =a + d
p
• S(imilarity)-Koeffizient:
s(xi, xj) =a
a + b + c
136
Beispiel 8.9. Binare Variablen: Ahnlichkeitstafeln fur Beispiel 8.7:
x1 1 0
x2 1 1 2 3
0 3 1 4
4 3 7
x1 1 0
x3 1 2 1 3
0 2 2 4
4 3 7
x2 1 0
x3 1 2 1 3
0 1 3 4
3 4 7
• Resultierende Matching-Koeffizienten:
s(x1, x2) =27
, s(x1, x3) =47
, s(x2, x3) =57
,
s(x1, x1) = s(x2, x2) = s(x3, x3) =77= 1.
Ahnlichkeitsmatrix:
S =
1 2
747
27 1 5
747
57 1
.
• Resultierende Similarity-Koeffizienten:
s(x1, x2) =1
1 + 2 + 3=
16
, s(x1, x3) =2
2 + 1 + 2=
25
s(x2, x3) =2
2 + 1 + 1= 0.5.
Ahnlichkeitsmatrix:
S =
1 0.167 0.4
0.167 1 0.5
0.4 0.5 1
.
Hier sind sich jeweils x2 und x3 ahnlicher als x1 und x3, und diese wie-
derum ahnlicher als x1 und x2.
137
Bemerkung 8.10. Ahnlichkeits- und Distanzmaße fur nominale Variablen
Sei X ein p-dimensionales Merkmal mit nominal skalierten Komponen-
ten, von denen mindestens eine mehr als zwei Auspragungen annehmen
kann. Der verallgemeinerte M-Koeffizient ist s(xi, xj) =up
, wobei u gleich
Anzahl der Komponenten, in denen xi und xj ubereinstimmen.
Beispiel 8.11. Bogenschutzen (Fortsetzung Beispiel 8.1)
Ahnlichkeitsmatrix aus dem verallgemeinerten M-Koeffizienten:
S =121· S∗, mit S∗ =
21 15 13 15 10 12 11 10 7 8 6 6 7 8 6 6 8 8 10 10 11 10 11 1315 21 14 14 11 13 10 9 10 9 7 10 10 8 7 9 9 9 11 11 10 10 11 1313 14 21 17 16 18 15 12 6 8 9 9 8 11 9 6 8 10 11 14 13 11 12 1415 14 17 21 14 16 15 12 4 7 7 8 7 10 7 5 9 9 11 14 13 11 12 1410 11 16 14 21 19 17 15 7 9 10 8 9 11 10 8 9 11 13 14 13 11 12 1312 13 18 16 19 21 17 14 6 8 9 9 8 10 9 7 8 10 12 15 14 12 13 1411 10 15 15 17 17 21 18 6 10 8 6 9 11 9 7 9 9 12 12 11 9 10 1110 9 12 12 15 14 18 21 7 11 7 5 8 10 8 6 8 8 11 12 11 9 10 117 10 6 4 7 6 6 7 21 16 17 13 13 11 18 18 11 13 13 6 7 7 8 98 9 8 7 9 8 10 11 16 21 16 10 14 16 17 13 14 16 16 9 10 8 9 106 7 9 7 10 9 8 7 17 16 21 12 13 14 20 16 12 16 15 9 11 9 9 106 10 9 8 8 9 6 5 13 10 12 21 13 12 12 12 11 11 10 13 11 11 13 117 10 8 7 9 8 9 8 13 14 13 13 21 17 12 13 14 14 13 9 11 11 11 128 8 11 10 11 10 11 10 11 16 14 12 17 21 14 11 15 16 15 11 12 10 11 136 7 9 7 10 9 9 8 18 17 20 12 12 14 21 17 12 16 16 9 10 8 9 106 9 6 5 8 7 7 6 18 13 16 12 13 11 17 21 12 13 14 7 8 10 9 108 9 8 9 9 8 9 8 11 14 12 11 14 15 12 12 21 14 14 11 12 10 11 118 9 10 9 11 10 9 8 13 16 16 11 14 16 16 13 14 21 18 11 12 10 11 12
10 11 11 11 13 12 12 11 13 16 15 10 13 15 16 14 14 18 21 13 14 12 13 1410 11 14 14 14 15 12 12 6 9 9 13 9 11 9 7 11 11 13 21 19 17 19 1711 10 13 13 13 14 11 11 7 10 11 11 11 12 10 8 12 12 14 19 21 19 19 1810 10 11 11 11 12 9 9 7 8 9 11 11 10 8 10 10 10 12 17 19 21 19 1811 11 12 12 12 13 10 10 8 9 9 13 11 11 9 9 11 11 13 19 19 19 21 1913 13 14 14 13 14 11 11 9 10 10 11 12 13 10 10 11 12 14 17 18 18 19 21
Dabei wurde “0” (Relief an dieser Stelle zerstort) als normale Aus-
pragung gezahlt. Stattdessen moglich: “0” als fehlende Beobachtung in-
terpretieren und Ahnlichkeitswerte unter Berucksichtigung der Nullen
adjustieren.
138
Beispiel 8.12. Ordinale Variablen
Merkmale Schulbildung (Auspragungen “Hauptschulabschluss”, “mitt-
lere Reife” und “Abitur”) und Note in einem Leistungstest (Noten von
5 bis 1). Realisierungen fur zwei Personen:
x1 = (mittlere Reife, 3)′, x2 = (Abitur, 5)′
Binarkodierung zur Messung der Ahnlichkeiten:
Die 3 Auspragungen der Schulbildung mittels dreier binarer Variablen
kodieren, die das Erreichte von der “geringsten” bis zur “hochsten”
Schulbildung angeben (“1”: “erreicht”, “0”: “nicht erreicht”, hohere
Schulbildung umfasst niedrigere).
Fur die Note im Leistungstest entsprechend funf binare Variablen.
Fur 1. Person also (1, 1, 1, 0, 0)′, fur 2. Person (1, 0, 0, 0, 0)′.
Neue binare Beobachtungsvektoren durch Konkatenation:
x1 = (1, 1, 0, 1, 1, 1, 0, 0)′, x2 = (1, 1, 1, 1, 0, 0, 0, 0)′.
Bemerkung 8.13. Ahnlichkeits- und Distanzmaße fur ordinale Variablen
Sei X p-dimensionales Merkmal mit ordinal skalierten Komponenten.
Fur jede der p Komponenten Konstruktion so vieler binarer Merkmale, wie
die Komponente Auspragungen besitzt. Die binaren Variablen pro Kompo-
nente werden von der niedrigsten bis zur erreichten Auspragung mit der
Auspragung “1” versehen. Restliche binare Variablen fur diese Kompo-
nente erhalten Wert “0”. Dadurch Umkodierung der ordinalen in binare
Merkmale und Nutzung eines Ahnlichkeitsmaßes fur binare Variablen.
Alternativer Vorschlag fur ordinalskalierte Merkmale:
Kodierung der Merkmalsauspragungen mit den Zahlen 1 bis Anzahl der
139
Auspragungen und Nutzung eines Ahnlichkeits- bzw. Distanzmaßes fur
metrisch skalierte Variablen. Dann setzt man allerdings mehr an die Varia-
blen voraus, als sie erfullen.
Bemerkung 8.14. Ahnlichkeits- und Distanzmaße fur metrische Variablen
Sei X p-dimensionales Merkmal mit metrisch skalierten Komponenten.
Meist misst man dann statt der Ahnlichkeit die Distanz. Gangige Maße:
• Lq-Norm
dq(xi, xj) =
(p
∑=1|xi,` − xj,`|q
)1/q
, q ≥ 1,
• Euklidische Distanz
d2(xi, xj) =√(xi − xj)′ · (xi − xj) =
√p
∑=1(xi,` − xj,`)2,
• City-Block-Metrik
d1(xi, xj) =p
∑=1|xi,` − xj,`|,
• Mahalanobisdistanz
d(xi, xj) =√(xi − xj)′ · Σ−1 · (xi − xj).
Hierbei bezeichnet Σ eine Schatzung der Kovarianzmatrix von (X1, . . . , Xp)′.
Die skalenabhangigen Lq-Normen sollten stets auf Basis der standardisier-
ten Beobachtungen bestimmt werden.
140
Abbildung: Euklidische Distanz
x1
x3
x4
x2
euklidische Distanz
= Länge der
Verbindungsstrecke
x1
x3
x4
x2
euklidische Distanz
= Länge der
Verbindungsstrecke
Abbildung: City-Block-Metrik
x1
x3
x4
x2
City-Block-Distanz
= Länge des Wegs, den
man in einer Stadt mit
gitterförmigem Straßennetz
zurücklegen müsste
x1
x3
x4
x2
City-Block-Distanz
= Länge des Wegs, den
man in einer Stadt mit
gitterförmigem Straßennetz
zurücklegen müsste
Abbildung: Mahalanobisdistanz
x1
x3
x4
x2
x1
x3
x4
x2
Mahalanobis-Distanz
Schritt 1: Kovarianzstruktur feststellen,
Transformation auf „runde“ Struktur
Schritt 2: In der runden Struktur
euklidische Distanzen feststellen
x1
x3
x4
x2x
1
x3
x4
x2
x1
x3
x4
x2x
1
x3
x4
x2
Mahalanobis-Distanz
Schritt 1: Kovarianzstruktur feststellen,
Transformation auf „runde“ Struktur
Schritt 2: In der runden Struktur
euklidische Distanzen feststellen
141
8.2 Zweiter Schritt: Cluster-Algorithmen
Gruppierung der Objekte anhand ihrer Ahnlichkeiten.
Unterscheidung: hierarchische und optimal partitionierende Verfahren.
Bemerkung 8.15. Hierarchische Clusterverfahren
Hierarchische Clusterverfahren konstruieren eine Folge von Partitionen
der Objektmenge. Zwei grundlegende Vorgehensweisen:
• Agglomerative Verfahren: Start mit maximal moglicher Clusteranzahl
(jede Beobachtung bildet eine Gruppe); in jedem Schritt Vereinigung
der beiden ahnlichsten bisherigen Cluster zu einem neuen.
• Divisive Verfahren: Start mit kleinstmoglicher Clusteranzahl (alle Be-
obachtungen in einer Gruppe); in jedem Schritt Aufspaltung eines
Clusters in zwei zueinander moglichst “unahnliche” Gruppen.
Bei beiden Varianten ist die Clusteranzahl nicht im Vorhinein festgelegt,
sondern wird wahrend der Durchfuhrung bestimmt.
Im Folgenden nur agglomerative Verfahren, da einfacher und in Programm-
paketen die Regel.
Hierarchische Clusterverfahren benotigen Ahnlichkeits-/ Distanzmaße nicht
nur fur Paare von Objekten, sondern auch zwischen den Gruppen:
Bemerkung 8.16. Distanz zwischen Clustern
Seien n Objekte {x1, . . . , xn} in ` Gruppen C1, . . . , C` mit n1, . . . , n` Objekten
eingeteilt. Mogliche Abstandsmaße D zwischen Gruppen Ci und Cj:
• nachster Nachbar (nearest neighbour):
D(Ci, Cj) = minxa∈Ci , xb∈Cj
d(xa, xb),
(geringste Distanz zwischen je einem Objekt aus Ci und Cj)
142
• entferntester Nachbar (furthest neighbour):
D(Ci, Cj) = maxxa∈Ci , xb∈Cj
d(xa, xb),
(großte Distanz zwischen je einer Beobachtung aus Ci und Cj)
• “mittlerer” Nachbar:
D(Ci, Cj) =1
ni · nj· ∑
xa∈Ci
∑xb∈Cj
d(xa, xb),
(Durchschnitt aller Distanzen zwischen Beobachtungen aus Ci und Cj)
• Zentroid-Distanz:
D(Ci, Cj) = ‖xi − xj‖,
(euklidischer Abstand zwischen den Gruppenzentren xi =1ni·∑xa∈Ci
xa)
Hierbei sei d ein Distanzmaß fur Abstande zwischen Objekten, vgl. Def.
8.4. Da die Zentroid-Distanz auf der euklidischen Distanz beruht, sollte sie
nur fur metrische skalierte Variablen benutzt werden.
Hierarchische agglomerative Clusterverfahren:
• Single Linkage Verfahren (nachster Nachbar),
• Complete Linkage Verfahren (entferntester Nachbar),
• Average Linkage Verfahren (durchschnittlicher Abstand),
• Zentroid Verfahren (Zentroid-Distanz).
143
Bemerkung 8.17. Agglomerative Verfahren: Vorgehensbeschreibung
Objekte x1, . . . , xn sind in k Cluster C1, . . . , Ck einzuteilen.
Ablauf eines agglomerativen Clusterverfahrens auf Basis eines Objekt-
Distanzmaßes d (Bem. 8.8, 8.10, 8.13 und 8.14) und einer Clusterdistanz
D (Bem. 8.16):
1. Ausgangsclusterung: Ci = {xi}, jedes Objekt bildet ein Cluster
2. Wiederholung der folgenden Schritte
• Berechnung der Distanzen zwischen je zwei Clustern Ci und Cj
fur alle i, j (i 6= j)
• Vereinigung der beiden Cluster mit der kleinsten Distanz zu
einem neuen Cluster; entstehende neue Clusterung: C1, . . . , C`
bis alle Objekte zu einem Cluster vereint sind.
3. Bestimmung einer geeigneten Clusteranzahl k uber geeignetes Kri-
terium: Durch ein Homogenitatsmaß, d.h. Vorgabe einer Grenze
fur die Homogenitaten innerhalb der Gruppen, oder mittels des
Dendrogramms.
Statt eines Distanzmaßes d Verwendung eines Ahnlichkeitsmaßes s
moglich, wobei dann Cluster mit der großten Ahnlichkeit vereinigt wer-
den.
20. 1. 2014
22.Vorlesung
Bemerkung 8.18. Dendrogramm
Dendrogramm eines hierarchisches Clusterverfahrens zeichnet in Form ei-
nes “Stammbaums” auf, welche Cluster im Ablauf des Verfahrens in wel-
cher Reihenfolge vereinigt (getrennt) wurden. Schematisches Aussehen:
144
* * * * * * 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 Average Linkage (Between Groups)
Rescaled Distance Cluster Combine
C A S E 0 5 10 15 20 25
Label Num +---------+---------+---------+---------+---------+
Case 8 8
Case 10 10
Case 7 7
Case 9 9
Case 4 4
Case 6 6
Case 11 11
Case 24 24
Case 12 12
Case 13 13
Case 5 5
Case 1 1
Case 2 2
Case 3 3
Case 19 19
Case 14 14
Case 25 25
Case 22 22
Case 23 23
Case 20 20
Case 21 21
Case 16 16
Case 18 18
Case 17 17
Case 15 15
òûòòòøò÷ ùòøòòòòò÷ ùòòòøòòòòòòò÷ ùòòòøòòòòòòòòòòò÷ ùòòòøòòòûòòòòòø ó óòòò÷ ùòòòòò÷ ùòòòøòòòòòòòòò÷ ó óòòòûòòòòòø ó óòòò÷ ùòòòòòòòòò÷ ùòòòøòòòòòòòòò÷ ó óòûòø ó óò÷ ùòòòòòòòòòø ó ùòòòøòòò÷ ùòòòòòòòòò÷ ó óòòòòòòòòòòòòò÷ ó ùòøòòòòòòòòòòòòòòòòòòòòòòòûòòò÷ ó óòòòòòòòòòòòòòòòòòòòòòòò÷ ó ùòòòòòòòòòòòòòòòøòòòòòòòòòòòòòòòòòûòòòòòòòòòòòòò÷ ó óòòòòòòòòòòòòòòòòò÷ ó óòòòòòòòòòòòûòòòòòòòòòòòòòòòòòòòòò÷ óòòòòòòòòòòò÷ óòòòòòòòòòòòûòòòòòø óòòòòòòòòòòò÷ ùòòòòòòòòòòòòòòòòòø óòòòòòòòòòòòòòòòòò÷ ùòòòòòòòòòòòòò÷òòòòòòòòòòòòòòòòòòòòòòòòòòòòòòòòòòò÷
Links stehen die Objekte (hier bezeichnet mit laufenden Nummern).
Senkrechte Striche zeigen an, wo zwei Cluster vereinigt wurden: Von links
nach rechts verfolgt man die sukzessive Vereinigung der Cluster. Hier wur-
den zuerst Objekt 8 und 10 sowie 1 und 2 geclustert (jeweils gleiche, mini-
male Distanz). Die waagerechte Lange zwischen zwei senkrechten Strichen
zeigt die Distanz zwischen den zugehorigen Clustern.
Anhaltspunkt fur geeignete Clusteranzahl: Suche Stelle im Dendrogramm
mit langen waagerechten Strichen uber die komplette Hohe des Diagramms
(dort deutlich getrennte Cluster mit großer Distanz, die “spat” vereinigt
145
werden). Hier zwei Cluster: eines aus Beobachtungen 15-18, anderes mit
Rest.
Beispiel 8.19. Bogenschutzen (Fortsetzung Beispiele 8.1 und 8.11)
Dendrogramm fur die persischen Bogenschutzen mittels der Ahnlich-
keitsmatrix aus verallgemeinertem M-Koeffizienten und Single-Linkage:
0.3 0.2 0.1 0.0
Dendrogramm Bogenschützen
122423222021784356121718191016911151314
Die großte Lucke zwischen senkrechten Strichen legt drei Gruppen na-
he: zwei große Cluster aus Schutzen Nr. 9-19 (ohne 12) sowie 1-8 und
20-24, sowie einzelne Beobachtung Nr. 12. Cluster 1 besteht aus inneren
Figuren, Cluster 2 aus Figuren am Rand. Archaologen erhielten ahnli-
ches Ergebnis.
146
Bemerkung 8.20. Bei Verwendung des nachsten, des entferntesten oder desmittleren Nachbarn wachsen die Distanzen wahrend des Clusterns mono-ton an. Nach Vereinigung von C1 und C2 hat C0 := C1 ∪ C2 zu jedem an-deren Cluster C3 einen mindestens so großen Abstand wie zuvor C1 zu C2
(sei ni die Anzahl der Elemente von Cluster Ci, i = 0, . . . , 3):
mina∈C0,b∈C3
d(xa, xb) = min{ mina∈C1,b∈C3
d(xa, xb), mina∈C2,b∈C3
d(xa, xb)} ≥ mina∈C1,b∈C2
d(xa, xb)
maxa∈C0,b∈C3
d(xa, xb) = max{ maxa∈C1,b∈C3
d(xa, xb), maxa∈C2,b∈C3
d(xa, xb)} ≥ maxa∈C1,b∈C2
d(xa, xb)
D(C0, C3) =n1
n1 + n2D(C1, C3) +
n2
n1 + n2D(C2, C3) ≥ D(C1, C2),
Dies gilt jedoch nicht unbedingt bei Verwendung der Zentroid-Distanz,
z. B. C3 = {(0, 0)}, C1 = {(−0.55, 1)}, C2 = {(0.55, 1)}.
Beispiel 8.21. Schweizer Banknoten: Kann man mit Hilfe hierarchischer
Clusterverfahren die echten von den falschen trennen?
Scatterplot der ersten beiden Hauptkomponenten (vgl. Bsp. 4.19):
●●
●
●
●
● ●
●
●
●
●
●
● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
●
●●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
−4 −2 0 2 4
−3
−2
−1
0
1
2
3
Ergebnisse verschiedener agglomerative Clusterverfahren unter Ver-
wendung des euklidischen Abstandes als Distanzmaß (Quelle: deut-
scher Wikipedia-Eintrag ”Hierarchische Clusteranalyse”):
147
• Single Linkage:
• Complete Linkage:
148
• Average Linkage:
• Zentroid-Verfahren:
149
Fazit:
• Verschiedene Verfahren liefern recht unterschiedliche Ergebnisse.
• Keines der vier vorgestellten Clusterverfahren liefert hier wirklich
gute Ergebnisse.
• Bei der Wahl der Clusteranzahl neben großen Distanz-Unterschied
auch Große der entstehenden Cluster berucksichtigen (z.B. wenn
wie hier bekannt ist, dass ungefahr gleichgroße Cluster gesucht
werden).
Es gibt aber auch ein Clusterverfahren, dass fur das Banknoten-Beispiel ein
richtig gutes Ergebnis liefert:
Bemerkung 8.22. Clusterverfahren nach Ward
Das Clusterverfahren nach Ward lauft in den gleichen Grundschritten ab
wie die anderen agglomerativen Verfahren. In jedem Iterationsschritt wer-
den aber jeweils die beiden Cluster vereint, deren Verbindung den klein-
sten Zuwachs an Heterogenitat der entstehenden Partition hervorbringt.
Sei C1, . . . , C` die momentane Partition der Objektmenge.
Messung der Heterogenitat des Clusters Ci uber Variabilitat innerhalb von
Ci:
∑xa∈Ci
‖xa − xi‖2
Dabei ist xi Zentrum des Clusters Ci, ‖x− y‖ die euklidische Distanz.
Heterogenitat der Partition C1, . . . , C` als Summe der einzelnen Variabi-
litaten:
H(C1, . . . , C` =`
∑i=1
∑xa∈Ci
‖xa − xi‖2.
150
Eine Vereinigung von zwei Clustern fuhrt zu einem Heterogenitatszuwachs.
Es werden diejenigen Cluster Ci und Cj vereinigt, die zum geringsten Zu-
wachs fuhren. Da die euklidische Distanz verwendet wird, sollte das Ver-
fahren von Ward nur fur metrisch skalierte Variablen angewendet werden.
Ubertragung des Ward-Verfahrens auf nominal skalierte Merkmale:
Messung der Homogenitat der Cluster durch den ‘Informationsinhalt’, der
in gewissem Sinn ebenfalls die Variabilitat innerhalb des Clusters beschreibt.
Beispiel 8.23. Nochmal die Schweizer Banknoten: Ergebnis des Ward-
Clusterverfahrens:
Abschließende Bemerkung: In R gibt es z. B. den Befehl hclust(). Eine Di-
stanzmatrix kann man mit dist() basteln.
151
8.3 Partitionierende Verfahren
Im Gegensatz zu hierarchischen bestimmen partitionierende Clusterme-
thoden eine Partitionierung der Objektmenge in k Cluster, so dass ein vor-
gegebenes Homogenitatskriterium optimiert wird. Dabei geht man meist
davon aus, dass die Anzahl k der Cluster bekannt ist oder im Vorhinein
geschatzt wurde.
Wichtigstes partitionierendes Verfahren: k-means (kmeans() in R)
Vorgehen:
1. Aufteilung der beobachteten Objekte in k beliebige Gruppen
2. Bestimmung der Gruppenzentren (Gruppenmittelwerte, Zentroide)
3. Bestimmung des Abstands jedes Objekts zu allen Gruppenzentren
4. Neuzuweisung jedes Objekts zu derjenigen Gruppe, zu deren Zen-
trum es den geringsten Abstand hat
Wiederholung von 2. bis 4., bis keine Neuzuweisung von Objekten mehr
vorgenommen wird.
Konvergenz: k-means Clustern konvergiert bei Verwendung der L2-Distanz
und der Gruppenmittelwerte binnen endlich vieler Schritte: Es gibt nur
endlich viele Partitionierungen endlich vieler Objekte und daher auch nur
endlich viele Gruppenzentren. Im Laufe des Clusterns wird zudem die
Summe aller Abstande zu Gruppenzentren immer kleiner. Sind x(`)1 , . . . , x(`)
k
die Gruppenzentren und C`1, . . . , C`
k die Cluster im `-ten Schritt, so gilt
k
∑j=1
∑i∈C`
j
||xi − x`j ||2 ≥
k
∑j=1
∑i∈C`+1
j
||xi − x`j ||2 ≥
k
∑j=1
∑i∈C`+1
j
||xi − x`+1j ||
2
Aber: Kein konvexes Optimierungsproblem. Losung abhangig von den
Startwerten. Es gibt verschiedene Varianten des Verfahrens, die sich im We-
152
sentlichen durch eine mehr oder weniger clevere Initialisierung der Zen-
tren unterscheiden. Ublich mehrere Durchlaufe mit verschiedenen Start-
werten. Man wahlt dann die Losung mit dem geringsten Wert des Zielkri-
teriums ∑kj=1 ∑i∈C`
j||xi − x`
j ||2.
Bemerkung 8.24. Bemerkung zu Clusteranalyseverfahren:
• Clusteranalyse ist deskriptiv. Es werden keine Tests durchgefuhrt.
• Die Effektivitat der verschiedenen Clustertechniken hangt von der La-
ge und Form der ‘wahren’ Cluster ab, die nicht bekannt sind.
• Nutzlich: Resultate verschiedener Verfahren vergleichen. Fuhren ver-
schiedene Ansatze zu ahnlichen Ergebnissen, die auch inhaltlich Sinn
machen, so kann man auf die gefundenen Cluster vertrauen.
• Clusteranalysemethoden konnen ausreißeranfallig sein, insbesondere
wenn sie auf der euklidischen Distanz basieren.
• Ohne die Existenz deutlicher Trennungen keine guten Ergebnisse er-
zielbar. Nichtlineare Strukturen werden von wenigen Clusteranalyse-
verfahren getrennt, z.B. kreisformige (Gruppe 1) innerhalb U-formiger
Punktwolke (Gruppe 2)
• Statt Objekten kann man auch Variablen clustern: Alternative zur Fak-
torenanalyse, extrahiert allerdings keine verborgenen Faktoren, son-
dern findet nur ahnliche Variablengruppen.
153