methodenlehre ll – Clusteranalyse · 24.06.2009 3 methodenlehre ll – Clusteranalyse Clusteranalyse: Vorgehensweise Bestimmung der Ähnlichkeit Prüfung der Merkmalsausprägung

24.06.2009

1

methodenlehre ll – Clusteranalyse

• Clusteranalyse

Thomas Schäfer | SS 2009 1


• Grundidee

• Mögliche Anwendungsgebiete

Die Clusteranalyse

g g g

• Vorgehensweise

• Beispiele


24.06.2009

2


Grundidee:Eine heterogene Gesamtheit von „Fällen“ (Personen/Objekte) soll in homogene Gruppen oder Cluster aufgeteilt werden

Die Clusteranalyse

soll in homogene Gruppen oder Cluster aufgeteilt werden. Dabei wird die Ähnlichkeit der Fälle auf allen relevanten Variablen berücksichtigt

Die zwei zentralen Fragen:

• Wie wird Ähnlichkeit von Fällen bestimmt?

Thomas Schäfer | SS 2009

• Wie wird die Gruppenaufteilung vorgenommen, wenn die Ähnlichkeit zwischen Fällen bekannt ist?

3

Analyse einer heterogenen Gesamtheit von Objekten, mit dem Ziel, homogene Teilmengen zu identifizieren.


• Aufteilung von Personen/Objekten in Subgruppen

• Erstellen von Typologien

Clusteranalyse: mögliche Anwendungen

yp g

• Marktforschung (Konsumentengruppen, Kaufverhalten, Produktanalyse)

• Differenzieren von Bevölkerungsgruppen


24.06.2009

3


Clusteranalyse: Vorgehensweise

Bestimmung der ÄhnlichkeitPrüfung der Merkmalsausprägung für je 2 Personen oder Objekte und Messung der Unterschiede/ ÜÜbereinstimmungen mit Hilfe eines Zahlenwertes (Proximitätsmaß)

Auswahl des Fusionierungsalgorithmus

Personen/Objekte werden aufgrund ihrer Ähnlichkeitswerte zu Gruppen zusammengefasst.

Bestimmung der ClusterzahlEntscheidung über Clusteranzahl, Zielkonflikt: Handhabbarkeit (geringe Clusteranzahl) & hohe Lösungsgüte (hohe Clusterzahl)


g g ( )

Interpretation der Cluster und Überprüfen der Güte

Inhaltliche Interpretation der resultierenden Cluster


Bestimmung der ÄhnlichkeitVariable1 Variable2 … Variable j

Objekt1

Objekt2j.::

Objekt k

Objekt1 Objekt2 … Objekt kObjekt1

Rohdatenmatrix


Objekt2.::

Objekt k

Distanz‐ oder Ähnlichkeitsmatrix

24.06.2009

4


Proximitätsmaße

(Ähnlichkeits‐ bzw. Distanzmaße)

Auswahl eines Ähnlichkeits‐/Distanzmaßes

bei Nominal‐Skalen bei metrischen SkalenTanimoto‐KoeffizientM‐KoeffizientKulczynski‐KoeffizientRR‐KoeffizientDice‐Koeffizient

L1 ‐ Norm L2 ‐ NormQ‐Korrelations‐KoeffizientMahalanobis‐Distanz…


….



Rohdatenmatrix

α β γ δ ε ζ

Objekt 1

Objekt 2

Objekt 3 1 1 1 0 0 0

1 1 0 1 0 0

0 1 0 1 1 1


Objekt 4 1 0 0 0 1 0

0 – nicht vorhanden1 – vorhanden

24.06.2009

5



ZeilensummeObjekt 1

Ei h ft i htEi h ft

Objekt 2

Eigenschaft nicht vorhanden (0)

Eigenschaft vorhanden (1)

Eigenschaft vorhanden (1)

Eigenschaft nichth d (0)

a

b

c

d

a+c

b+d


Spaltensumme

vorhanden (0) b d

a+b c+d

b+d

m



Rohdatenmatrix

α β γ δ ε ζ

Objekt 1

Objekt 2

Objekt 3 1 1 1 0 0 0

1 1 0 1 0 0

0 1 0 1 1 1

b


Objekt 4 1 0 0 0 1 0ab c

24.06.2009

6



Fall x

Fall y + ‐

Nichtübereinstimmung soll keine Rolle spielen Fall y

+ a c

‐ b d

z. B. Tanimoto‐Koeffizient:

cbaaKoeffTanimoto++

=− .

Nichtübereinstimmung soll berücksichtigt werden (z. B. bei „echt‐dichotomen“ Daten)

+ Eigenschaft vorhanden‐ Eigenschaft nicht vorhandena: Anzahl der Variablen, in denen für beide Fälle die


( „ )z. B. M‐Koeffizient (Simple Matching):

dcbadaM+++

+=

denen für beide Fälle die Eigenschaft vorhanden istb: Anzahl der Variablen, in denen die Eigenschaft für Fall xvorhanden ist, aber für Fall ynichtusw.



Aufbau der Distanz‐ oder ÄhnlichkeitsmatrixObjekt 1 Objekt 2 Objekt 3 … Objekt k

Objekt 1

Objekt 2

Objekt 3

1 ‐ ‐ ‐

? 1 ‐ ‐

? ? 1 ‐


Objekt 3:

Objekt k

? ? 1 ‐

? ? ? 1

24.06.2009

7



• „echte“ Ähnlichkeitsmaße – z.B. Q‐Korrelationskoeffizient(wenn Kovariation inhaltlich wichtig ist)

• Abstandsmaße – z. B. Minkowski‐Metriken(wenn absoluter Abstand inhaltlich wichtig ist)

z.B. City‐Block‐Metrik (L1 – Norm), Euklidische Distanz (L2 –Norm)




Ähnlichkeitsermittlung bei metrischer Variablenstrukturam häufigsten angewandte Distanznorm: Minkowski‐Metriken

Euklidische Distanz: r = 2

City‐Block‐Metrik: r = 1:

∑ −==

J

jbjajba XXd

1,


(oft auch quadriert):

∑ −==

J

jba X bjX ajd

1

2,

x , x :Wert der Variablen j bei den Objekten k,l (j=1,2,…J)

d : Distanz der Objekte k und l

r > 1 : Minkowski‐Konstante

k,l

k,j l,j

_

24.06.2009

8



k

Variable 2

-

Xk,2

l,2

4 5 6 7


Variable 1

l

X - Xk,1 l,1

X k

1 2 3 4 5 6 7 8

1 2 3

15


Zur Messung der Ähnlichkeit zwischen Objekten sind


• Distanzmaße immer dann geeignet, wenn der absolute Abstand zwischen Objekten von Interesse ist und die Unähnlichkeit dann als um so größer anzusehen ist, wenn zwei Objekte weit entfernt voneinander liegen.

• Ähnlichkeitsmaße immer dann geeignet, wenn der primäre


ß g g , pÄhnlichkeitsaspekt im Gleichlauf zweier Profile zu sehen ist, unabhängig davon, auf welchem Niveau die Objekte liegen.

16

24.06.2009

9



Unternehmen A Unternehmen BJahr

Gewinn

2006

2003

2000


die Profile beider Unternehmen sind gleich, ein Ähnlichkeitsmaß würde einen hohenWert liefern

die beiden Unternehmen haben aber absolut gesehen einen großen Abstand, ein Distanzmaß würde daher einen kleinenWert liefern


Clusteralgorithmen

Clusterverfahren

Hierarchische Verfahren

agglomerativ divisiv

GraphentheoretischeVerfahren

Partitionierende Verfahren

Austausch‐verfahren

Optimierungs‐verfahren

Iteriertes Minimaldistanz‐

Verfahren


Single‐Linkage

WardComplete‐Linkage

Average‐Linkage

Centroid Median

24.06.2009

10


Partitionierende Verfahren• Anfangsgruppierung vorgeben

S k i V l Obj kt i d G

Clusteralgorithmen

• Sukzessive Verlagerung von Objekten in andere Gruppen• Zielkriterium: Minimierung der Varianz innerhalb der

Gruppen(Gruppeneinteilung reversibel)

Hierarchische Verfahren

a) agglomerativ: anfangs so viele Gruppen wie Fälle,


sukzessives Zusammenfassen der Gruppen

b) divisiv: anfangs alle Fälle in einer Gruppe, sukzessives Aufteilen der Fälle in Gruppen(Gruppeneinteilung nicht reversibel)

19


Algorithmen für hierarchische Clusteranalyse

Single linkage

(nächster Nachbar)

Complete linkage

(entferntester Nachbar)(nächster Nachbar) (entferntester Nachbar)


Average linkage: mittlere Distanz aller Fälle eines Clusters von allen Fällen des anderen Clusters

24.06.2009

11


Algorithmen für hierarchische Clusteranalyse

Single LinkageDas Single Linkage Verfahren neigt zur Kettenbildung und kann daher Ausreißer ausfindig machen. Nachdem man diese entfernt hat, kann man mit Verfahren fortfahren, die schöne homogene Cluster bilden, z.B. Average Linkage oder Ward.


Ward – VerfahrenVereinige diejenigen Objekte, die die Streuung in einer Gruppe am wenigsten erhöhen (homogene Cluster).


• nach statistischen Kriterien

– z.B. Entwicklung des Heterogenitätsmaßes( hl )

Bestimmung der Clusterzahl

(z.B. per Fehlerquadratsumme)

– Dendrogramm

• durch sachlogisch Überlegungen

– Konflikt zwischen der „Heterogenitätsanforderung der Clusterzahl“ und der „Handhabbarkeit der Clusterlösung“

– auf die Clusterzahl beschränken (nicht nach den in den


auf die Clusterzahl beschränken (nicht nach den in den Clustern zusammengefassten Fällen gehen)

22

24.06.2009

12


Das Heterogenitätsmaß gibt die durchschnittliche Unähnlichkeit der Objekte in den Clustern an. Diese steigt natürlich je weniger Cluster man wählt Günstig ist es nach


natürlich, je weniger Cluster man wählt. Günstig ist es, nach einem „Sprung“ in diesem Maß zu suchen.

Es gibt immer einen Schritt weniger als ursprüngliche Fälle.

Von der Gesamtzahl der Fälle zieht man den Schritt vor dem Sprung


mögliche Sprünge

a de Sc tt o de Sp u gab, um die Anzahl der Cluster zu bestimmen. Hier z.B. 16 – 11 = 5


Das Dendrogramm gibt das Heterogenitätsmaß gewissermaßen grafisch wieder und hilft so, die Anzahl von Clustern zu bestimmen


Clustern zu bestimmen.

Man sucht sozusagen die größte Distanz, auf der nichts passiert.


24.06.2009

13


• Nach der Bestimmung der Clusterzahl müssen die Cluster interpretiert werden.

• Dazu schaut man, welche Werte die Fälle

Interpretation der Cluster

in den Clustern nun auf den Ausgangsvariablen haben, mit denen die Analyse gemacht wurde.

• Weiterhin kann man sich überlegen, was die Fälle in den Clustern verbinden könnte.

• Eine Möglichkeit dafür ist, dass man sich potenzielle Variablen – die für die Clusterung verantwortlich sein könnten –


ganzeigen lässt (Label – immer als String).

• So könnte man z.B. finden, dass bei zwei Clustern das eine Cluster aus Frauen, das andere aus Männern besteht.

25


• Clusteranalyse mit den 4 Entscheidungsstilen des DMQ (Vigilance, Hypervigilance, Buckpassing, Procrastination)

• aufgrund dieser Variablen sollen Cluster von Studierenden gesucht

Beispiel

aufgrund dieser Variablen sollen Cluster von Studierenden gesucht werden, die sich ähnlich sind

• betrachten wir 20 Studierende (Fälle) und beginnen zunächst mit dem Single Linkage Verfahren (nächster Nachbar), um mögliche Ausreißer zu entdecken


Ausreißer

24.06.2009

14


• nach Entfernen der Ausreißer suchen wir mit dem Ward‐Verfahren nach homogenen Clustern

Beispiel



• für die gefundenen Cluster sehen wir uns die Werte der enthaltenen Personen auf den Ausgangsvariablen an, um zu sehen, wie genau sie sich unterscheiden (z.B. mit Boxplots)

Beispiel

( p )


24.06.2009

15


• die gefundenen Cluster können anhand der Ausgangsvariablen näher beschrieben werden

k h h l h h

Beispiel

• sie können von nun an hinsichtlich verschiedener Anwendungen einzeln betrachtet oder untersucht werden (z.B. für Forschungszwecke)

• untersucht man zusätzlich, ob die Cluster sich durch bestimmte Merkmale (Label) systematisch unterscheiden, kann man auch das als weiteres Forschungsergebnis benutzen



• Studie von Jankowski und Zill (2009)• Lassen sich Bands (bspw. Korn, Metallica) nach bestimmten Kriterien

(bspw. Anzahl der Mitglieder, Liedanzahl, amerikanisch oder nicht,

Beispiel 2

( p g , , ,Bewertung) zu Clustern gruppieren?

• 13 Versuchspersonen (in verschiedene Alben hineingehört)


24.06.2009

16


Beispiel 2


diese Informationen könnte man z.B. nutzen, um CDs im Geschäft nach Ähnlichkeit zu gruppieren


Wie lassen sich die Stadtteile von Chemnitz zu homogenen Clustern zusammenfassen?

Variablen: Alt t kt

Beispiel 3

‐ Altersstruktur‐ Geschlecht‐ Familienstand‐ Ausländeranteil‐ Bevölkerungsdichte‐ Bevölkerungsentwicklung‐ Haushalte (Größen, Formen)‐ Mobilität/Wanderungen‐ Hilfebedürftigkeit


‐ Flächen im Stadtteil‐ Struktur der Wohngebäude‐ Wohnungsgrößen‐ Bausubstanzen‐ Wahlergebnisse Bundestagswahl 2005

32

Chempirica (http://www.chempirica.de/stadtteilanalyse.htm)

24.06.2009

17


Clusteranalyse mit SPSS I



Clusteranalyse mit SPSS II


24.06.2009

18


Vergleich Faktorenanalyse – Clusteranalyse

Variablen

FälleGemeinsame Ausgangsbasis FälleAusgangsbasis

(meist) Variablen

(meist) Variablen

(meist) Fälle

(meist)Fälle

Korrelations‐matrix

Distanz‐/Ähnlichkeit‐matrix


Variablen Fälle matrix

ZIEL Dimensionsreduktion Gruppenbildung

Documents

methodenlehre ll – Clusteranalyse · 24.06.2009 3 methodenlehre ll – Clusteranalyse Clusteranalyse: Vorgehensweise Bestimmung der Ähnlichkeit Prüfung der Merkmalsausprägung