Hauptseminar

Der Two-Step-Clusteralgorithmus in SPSS:

Methodenbeschreibung und Vergleich mit der k-Means

Clusteranalyse

Eingereicht am

Lehrstuhl für Statistik

Josef Seibold

8. Fachsemester BWL

---

Inhaltsverzeichnis

1 Einführung in die Clusteranalyse

1

1.1 Problemstellung der Clusteranalyse .

1

1.2 Ablauf der Clusteranalyse .

1

2 Der Two-Step-Clusteralgorithmus in SPSS

3

2.1 Problemstellung des Verfahrens .

3

2.2 Ablauf der zweistugen Clusteranalyse .

4

2.2.1 Erste Stufe: Vorläuge Clusterung aller Objekte .

5

2.2.2 Zweite Stufe: Hierarchische Clusterung der Sub-Cluster .

7

2.2.3 Distanzmaÿe des Two-Step-Clusteralgorithmus .

7

3 Anwendung des Two-Step-Clusteralgorithmus in der Praxis

10

3.1 Beschreibung des empirischen Datensatzes 10

3.2 Durchführung der Two-Step-Clusteranalyse 10

3.3 Auswertung der Ergebnisse des Clusterverfahrens 11

4 k-Means-Clusteranalyse

21

4.1 Beschreibung und Problemstellung der k-Means-Methode 21

4.2 Ablaufschema der k-Means-Clusteranalyse 21

5 Anwendung der k-Means-Methode in der Praxis

23

5.1 Problematik des empirischen Datensatzes 23

5.2 Durchführung der k-Means-Clusteranalyse 23

5.3 Auswertung der Ergebnisse der Clusteranalyse 26

6 Vergleich der beiden Clusterverfahren

33

6.1 Theoretischer Vergleich 33

6.2 Vergleich der SPSS-Ergebnisse 34

6.3 Schlussfolgerung 36

A Statements der Usage & Attitudes-Studie

III

B Balkendiagramme der Clusterprole

V

C SPSS-Ausdrücke

XV

I

---

Inhaltsverzeichnis

II

Literaturverzeichnis

XXXIII

---

1 Einführung in die Clusteranalyse

1.1 Problemstellung der Clusteranalyse

Die Clusteranalyse ist ein multivariates statistisches Verfahren zur Klassenbil-

dung. Das Ziel der Clusteranalyse besteht darin, möglichst homogene Grup-

pen aus einer Menge von Objekten zu klassizieren, wobei sich die Gruppen

möglichst heterogen voneinander unterscheiden sollen. Der Ausgangspunkt der

Clusteranalyse bildet eine Rohdatenmatrix X mit N Objekten und p Varia-

blen.1

x

11

...

x1p

.

X = .

.

... ... .

xN1

...

xNp

Die Zuordnung der Objekte in die Cluster erfolgt so, dass genau jedes Ob-

jekt genau einem von g Clustern (C1, C2, ..., Cg) zugewiesen wird. Eine solche

Clusterzuordnung wird auch Partition P = (C1, C2, ..., Cg) genannt.

1.2 Ablauf der Clusteranalyse

Nachdem das Hauptziel der Clusteranalyse kurz erläutert wurde, soll nun kurz

der Ablauf einer Klassikationsbildung dargestellt werden.2 Zu Beginn der

Clusteranaylse werden die Ähnlichkeiten der einzelnen Objektpaare aus der

Datenmatrix berechnet. Je gröÿer der Wert des Ähnlichkeitsmaÿes ist, desto

ähnlicher sind sich zwei Objekte und umso homogener ist das Cluster, das sie

bilden. Bei der Bestimmung des Distanzmaÿes ist das Skalenniveau der Va-

riablen sehr entscheidend. Folglich gibt es spezielle Distanzmaÿe, auch Proxi-

mitätsmaÿe genannt, bei nominalskalierten und metrischskalierten Variablen.

Bei gemischtskalierten Merkmalen wird das Log-Likelihood Distanzmaÿ zur

Berechnung der Distanzen herangezogen. Die Berechnung der Distanz zweier

Objekte wird im nächsten Kapitel ausführlich dargestellt anhand der Euklidi-

schen Distanz und der Log-Likelihood Distanz. Nach der Berechnung der Ähn-

lichkeitswerte der einzelnen Objektpaare erfolgt der Fusionierungsalgorithmus.

1siehe Fahrmeir u. a. (1996, S. 438)

2siehe Backhaus u. a. (2006, S. 481 f.)

1

---

Kapitel 1. Einführung in die Clusteranalyse

2

Bei der Auswahl des Clusteralgorithmus unterscheidet man zwischen den Hier-

archischen Clusterverfahren und den Partitionierenden Clusterverfahren. Die

Hierarchischen Clusterverfahren konstruieren eine Folge von Partitionen der

gesamten Objektmenge I3 I = 1,2,...,N.

Dabei werden die Hierarchische Clustermethoden in agglomerative und divisive

Clusterverfahren unterteilt. Die agglomerativen hierarchischen Clusterverfah-

ren beginnen mit der feinsten Partition, d.h. jedes Objekt stellt zu Beginn

ein eigenes Cluster dar und wird sukzessive mit Hilfe der Ähnlichkeitsmatrix

der Objektpaare zu optimalen Clustern fusioniert. Bei divisiven hierarchischen

Clusterverfahren wird mit der gröbsten Partition gestartet, d.h. die Rohdaten-

matrix X stellt zu Beginn des Algorithmus ein einziges Cluster dar und wird

sukzessive in mehrere optimale Cluster zerlegt. Durch die sukzessive Aufspal-

tung in Teilklassen wird eine höhere Homogenität erreicht.

Die partitionierenden Clusterverfahren beginnen mit einer fest vorgegebenen

Anfangspartition, die im Bezug auf ein bestimmtes Gütekriterium, wie z.B.

das Varianzkriterium, sukzessive verbessert wird. Ziel dieses iterativen Clus-

teralgorithmus ist es, durch geeignete Umgruppierung der Objekte und durch

geeignete Korrektur der in der Startpartition vorgegebenen Clusterschwer-

punkte die Start-Clusterlösung in Bezug auf ein bestimmtes Gütekriterium zu

verbessern. Die partitionierenden Clusterverfahren unterscheiden sich in opti-

mierende Austauschverfahren und Minimal-Distanz-Verfahren. Optimierende

Austauschverfahren berechnen zunächst die Clusterschwerpunkte für eine vor-

liegende Anfangspartition, sowie die Werte der Objekte eines vorgegebenen

Gütekriteriums.4 Anhand der Werte des Gütekriteriums wird für jedes Objekt

entschieden, ob durch eine Umgruppierung des Objektes eine Verbesserung

der Clusterlösung erzielt werden kann. Das Minimal-Distanz-Verfahren wird

später am Beispiel der k-Means-Clusteranalyse ausführlich beschrieben. Hier-

archische Clusterverfahren sind sehr geeignet bisher unbekannte Clusterstruk-

turen aufzudecken, während partitionierende Verfahren, von einer Startparti-

tion ausgehend, die Cluster anhand eines gewählten Gütekriteriums iterativ

umgruppieren, um eine optimale Clusterlösung zu erhalten.

Im letzten Schritt des Ablaufs eines Clusterverfahrens wird die Anzahl der

Cluster bestimmt. Bei partitonierenden Clusterverfahren wird die Clusteran-

zahl bereits zu Beginn festgelegt und auch nicht mehr im Laufe des Verfahrens

verändert. Hingegen bei den hierarchischen Clusterverfahren wird die Clus-

teranzahl im sequentiellen Ablauf des Verfahrens ermittelt und hängt von der

Heterogenität aller Objekte der Datenmatrix ab.

3siehe Fahrmeir u. a. (1996, S. 453 f.)

4siehe Eckey u. a. (2002, S. 260)

---

2 Der Two-Step-Clusteralgorithmus in SPSS

2.1 Problemstellung des Verfahrens

Der Two-Step-Clusteralgorithmus ist ein zweistuges Clusterverfahren zur Klas-

senbildung. In der ersten Stufe des Verfahrens wird zunächst eine grobe und

vereinfachte Clusterung aller Objekte vorgenommen, die dann in der zweiten

Stufe mit einer rechenaufwändigeren hierarchischen Clusteranalyse zu präzi-

seren Clustern verdichtet wird. Ziel dieses Clusteralgorithmus ist es, ebenso

wie bei den herkömmlichen Clusterverfahren, möglichst homogene Objekte in

einem Cluster zusammenzufassen, wobei sich die verschiedenen Cluster mög-

lichst deutlich voneinander unterscheiden sollen.

Dabei unterscheidet sich der Two-Step-Clusteralgorithmus in SPSS im Ver-

gleich zu den anderen Clusterverfahren insbesondere im Algorithmus, nach

dem die Clusterbildung vorgenommen wird. Während die zweistuge Cluster-

analyse in einem sequentiellen Ablauf zwei Clusterungen durchführt, - zuerst

eine vorläuge Clusterung mit einer anschlieÿenden hierarchischen Clusterung

- erfolgt die Clusterbildung bei den üblichen Clusterverfahren in einem ein-

stugen Algorithmus. Die zweistuge Clusteranalyse hat den groÿen Vorteil

gegenüber klassischen Clusterverfahren, sehr umfangreiche Datensätze ohne

enormen Rechenaufwand zu klassizieren. Es müssen also nicht zu jedem Ob-

jektpaar die Distanzen berechnet werden, um die Objekte einer gemeinsa-

men Gruppe zuzuordnen, die sich am ähnlichsten sind. Benden sich in ei-

nem groÿen Datensatz sowohl kategoriale als auch metrischskalierte Variablen,

so ist der Two-Step-Clusteralgorithmus auch in der Lage, die Ähnlichkeiten

der Objekte bei Vorliegen von gemischtskalierte Merkmalen mit Hilfe der Log-

Likelihood Distanz zu bestimmen. Hingegen bei anderen Clusterverfahren kön-

nen keine Varialben mit unterschiedlichen Skalenniveaus zur Berechnung der

Ähnlichkeiten verwendet werden. Hier müssen entweder Distanzmaÿe für Va-

riablen mit einer Nominal-Skala oder für Variablen mit einer metrischen Skala

zur Berechnung der Distanzen verwendet werden. Jedoch liefert der Two-Step-

Clusteralgorithmus eine ungenauere Clusterlösung als hierarchische Cluster-

verfahren. Dies liegt daran, dass im ersten Schritt eine sehr grobe Clusterung

vorgenommen wird, die zum Ziel hat, alle Objekte, die sich in der rieÿigen

3

---

Kapitel 2. Der Two-Step-Clusteralgorithmus in SPSS

4

Datenmatrix benden, transparenter zu ordnen, was auch notwendig ist, um

die zweite Stufe der Clusterung vorzunehmen.

Es besteht folglich ein Trade-O zwischen der Genauigkeit der Clusterlösung

und dem immensen Rechenaufwand. Der Two-Step-Clusteralgorithmus ver-

sucht hier einen Mittelweg zu nden, indem in der ersten Stufe eine ziemlich

grobe Clusterung in Kauf genommen wird, um die Berechnungen der Distanzen

der einzelnen Objektpaare zu vermeiden, die bei einem sehr groÿen Data-Set

oft nicht mehr aufgrund der aufwendigen Rechenschritte durchgeführt werden

können. Und schlieÿlich wird in der zweiten Stufe auf eine exaktere Cluster-

bildung gezielt, indem konkrete Berechnungen durchgeführt werden um eine

optimale Clusterlösung zu erhalten.

2.2 Ablauf der zweistugen Clusteranalyse

Das Verfahren des Two-Step-Clusteralgorithmus basiert auf dem so genannten

BIRCH-Algorithmus, der vorwiegend für die Clusterung sehr umfangreicher

Datensätze angewendet wird.

Im Folgenden wird ganz kurz der Ablauf des BIRCH-Algorithmus dargestellt.1

1. Loading

In der ersten Phase werden alle Objekte des Datensatzes in einem Cluster

Feature Baum aufgenommen. Der Clusterbaum versucht die Informationen

des Datensatzes bei der Klassikation möglichst detailliert zu reektieren.

2. Optional Condensing

Im zweiten Schritt wird der gesamte Datensatz im Cluster Feature Baum wei-

terhin verdichtet, indem kleinere Clusterbäume gebildet werden, welche die

Objekte noch genauer strukturieren.

3. Global Clustering

In der dritten Phase werden schlieÿlich die Objekte, die den Blättern des Clus-

ter Feature Baumes zugeordnet wurden, zu Sub-Clustern zusammengefasst.

4. Optional Rening

In der letzten Phase wird die grobe Clusterlösung, die beim Global Clustering

resultiert, verfeinert und verbessert, indem die Sub-Cluster mit Hilfe einer

agglomerativen hierarchischen Clusteranalyse nochmals geclustert werden.

Der Ablauf der zweistugen Clusteranalyse orientiert sich in ähnlicher Vorge-

hensweise am BIRCH-Algorithmus.

1siehe Zhang u. a. (1997)

---

Kapitel 2. Der Two-Step-Clusteralgorithmus in SPSS

5

2.2.1 Erste Stufe: Vorläuge Clusterung aller Objekte

In der ersten Stufe des Two-Step-Clusteralgorithmus werden zunächst alle Ob-

jekte des gesamten Datensatzes in einer baumartigen Clusterstruktur, die als

Cluster Feature Baum bezeichnet wird, geordnet. Der Algorithmus teilt nun al-

le Fälle sukzessive den einzelnen Blättern bzw. Ästen zu, zu denen der einzelne

Fall die gröÿte

Ähnlic

hk

eit

aufw

eist. Zur Veransc

haulichung wird nachstehend

ein Cluster Feature Baum graphisch dargestellt.2

Ursprung

Alle F

e

l

l

ä

Ast 1

Ast 3

Blatt1

Blatt2

Blatt 3 Blatt 4 Blatt 5

Blatt 6

Ausgehend vom Ursprung, der alle Objekte enthält, wird jede Person suk-

zessive den einzelnen Knoten des Baumes zugeordnet, bis sich schlieÿlich jede

Person in einem Blatt bendet, das die vorläugen Sub-Cluster enthält. Wie in

der Graphik ersichtlich, stellt jeder Punkt eine einzelne Person des Datensat-

zes dar. Personen, die sich sehr ähnlich sind, werden zu einer Gruppe zusam-

mengefasst, die im Clusterbaum als Kreis bzw. Punktewolke markiert ist. Jede

Person wird also genau einem Blatt zugeordnet, wobei jedes Blatt genau einem

übergeordneten Knoten angehört, der im Cluster Feature Baum als Ast darge-

stellt wird. In den Ästen benden sich dann zusammengehörige Sub-Cluster,

die charakteristisch ähnliche Objekte bündeln. Dies wird graphisch im zwei-

ten Ast veranschaulicht. Ebenso werden die Äste groÿeren Ästen zugeordnet,

bis schlieÿlich die gröÿten Äste zum Ursprung zurückführen. Die Baumstruk-

tur kann sich in viele Baumebenen verzweigen. Je mehr Verzweigungen und

je mehr Knoten, desto genauer und detaillierter werden die Objekte zugeord-

net und umso mehr Sub-Cluster werden gebildet. Jedoch bedeutet eine höhere

2siehe Brosius (2004, S. 703)

---