Clusteranalyse

_Explorative Verfahren

Prof. Dr. Armin Eichinger

TH Deggendorf

14.11.2024

Einleitung

Allgemeines

  • Ausgangspunkt: Objekte mit Eigenschaften (→ Matrix)
  • Ziel: Objekte nach ihren Eigenschaften so in Gruppen zusammenfassen, dass die Unterschiede innerhalb der Gruppen möglichst gering und zwischen den Gruppen möglichst groß wird; heterogene Gesamtheit – homogene Teilmengen
  • Bezieht sich auf Ähnlichkeiten bzw. Distanzen zwischen Personen oder Objekten
  • „Clusteranalyse“ als Sammelbegriff für eine Vielzahl an Techniken bzw. Varianten

Beispiele

  • Gruppierung von Schulkindern nach Leistungsschwerpunkten oder -defiziten
  • Segmentierung von Internetnutzern nach Nutzungserfahrung
  • Identifikation von Fahrertypen
  • Klassifizierung biologischer Arten
  • Erkennen von Patientengruppen mit ähnlichen Krankheitsbildern
  • Segmentierung von Kunden

Vorgehen

  1. Art des Clusterverfahrens
  2. Bestimmung der Ähnlichkeiten
  3. Auswahl des Fusionierungsalgorithmus
  4. Bestimmung der Clusterzahl

Umsetzung

Art des Clusterverfahrens: Hierarchisch

Eigenschaften:

  • Verfahren: Agglomerative und divisive Methoden
  • Ziel: Erstellung einer Hierarchie von Clustern (Dendrogramm)
  • Beispiele:
    • Agglomerative Verfahren: Startet mit jedem Objekt als eigenem Cluster und fusioniert sukzessive Cluster (unterschiedliche Fusionierungsverfahren; s. u.)
    • Divisive Verfahren: Startet mit allen Objekten in einem Cluster und teilt sukzessive Cluster auf
  • Implementierung in R: hclust() (agglomerativ)

Anwendungsbereich:

  • Kleine bis mittelgroße Datensätze
  • Visualisierung der Clusterstruktur

Weitere Verfahren (unberücksichtigt): Gridbasierte Verfahren, Partitionierende Verfahren, Optimierungsverfahren

Bestimmung der Ähnlichkeiten

  • Wahl des Distanz- oder Ähnlichkeitsmaßes

  • Allgemeines Format: Minkowski-Metrik \(d(x, y) = \left( \sum_{i=1}^{n} |x_i - y_i|^p \right)^{\frac{1}{p}}\)

Realisierungen:

  • \(p=1\): City-Block-Metrik (Manhatten-Distanz)
  • \(p=2\): Euklidische Distanz (am häufigsten verwendet)

Weitere Verfahren (unberücksichtigt): Cosine-Ähnlichkeit, Korrelationskoeffizient, Jaccard-Koeffizient

Auswahl des Fusionierungsalgorithmus (Linkage-Methode)

  • Complete Linkage (in hclust(): method="complete"): Complete Linkage definiert die Distanz zwischen zwei Clustern als die maximale Distanz zwischen einem Punkt im ersten Cluster und einem Punkt im zweiten Cluster. Empfindlich bei Ausreißern.

  • Ward-Methode (in hclust(): method="ward.D"): Die Ward-Methode minimiert die Summe der quadrierten Abweichungen innerhalb der Cluster (Varianz). Bei jedem Schritt wird das Paar von Clustern fusioniert, dessen Zusammenführung die kleinste Zunahme der Gesamtsumme der quadrierten Abweichungen zur Folge hat.

  • Single Linkage (auch Nearest Neighbour; in hclust(): method="single"): Bei Single Linkage wird die Distanz zwischen zwei Clustern als die minimale Distanz zwischen einem Punkt im ersten Cluster und einem Punkt im zweiten Cluster. Zur Identifikation von Ausreißern.

Weitere Verfahren (unberücksichtigt): Average Linkage, Centroid Linkage, Median Linkage

Bestimmung der Clusterzahl

  • Agglomerative Verfahren: Am Ende ein großer Cluster
  • Viele Freiheitsgrade bei der Entscheidung
  • Konflikt: Homogenität vs. Handhabbarkeit
  • Scree-Test: Elbow-Kriterium
  • Dendrogramm

Beispiel Regionen 🗺️
(vgl. EFA)

Daten 1

Wir haben für 12 Regionen folgende Variablen vorliegen:

  • Bevölkerungsdichte (Einwohner je qkm): ED
  • Bruttoinlandsprodukt (BIP) je Einwohner (DM): BIP
  • Anteil der Erwerbstätigen in der Landwirtschaft (Prozent): EL
  • Wachstumsrate des BIP (in den letzten zehn Jahren): WBIP
  • Allgemeine Geburtenziffer (Lebendgeborene je 1000 Einwohner): GEB
  • Wanderungssaldo (Zu- minus Fortwanderungen je 1000 Einw.): WS

Frage FA: Gibt es eine sparsamere Struktur, die diesen Variablen zugrunde liegt?

Frage CA: In welche Cluster können die Regionen zusammengefasst werden?

# Daten einlesen und ausgeben
regionen_data <- read.csv("./data/regionen.csv", sep=";", dec = ",")
regionen_data
      ED   BIP   EL WBIP  GEB   WS
1  212.4 20116  9.8 53.0  8.4 -0.7
2  623.7 24966  3.4 73.1  6.1  3.4
3   93.1 19324 23.6 47.9 12.3 -1.9
4  236.8 23113  8.7 66.8  8.7  2.0
5  412.0 23076  8.9 46.9  8.0 -3.1
6  566.7 24516  6.1 44.3  8.6 -3.0
7  331.9 22187  7.4 57.6 10.3  4.7
8  111.4 20614 16.3 63.8 13.9  5.2
9  489.0 25006  5.7 49.4  6.7 -2.6
10 287.4 23136  8.8 59.4 12.4  1.7
11 166.2 20707 14.1 74.0 13.0  3.6
12 388.1 23624  9.6 54.3  6.9 -0.4

Daten 2

Erster Verarbeitungsschritt: z-Transformation der Daten

# Daten standardisieren (= z-transformieren)
regionen_data_z <- scale(regionen_data)

regionen_data_z
               ED        BIP          EL         WBIP        GEB         WS
 [1,] -0.65651480 -1.2449654 -0.07308063 -0.450043283 -0.4496692 -0.4698356
 [2,]  1.70883627  1.2541546 -1.24237066  1.541707907 -1.3055911  0.8663443
 [3,] -1.34259888 -1.6530692  2.44820101 -0.955412988  1.0016768 -0.8609127
 [4,] -0.51619249  0.2993362 -0.27405235  0.917427683 -0.3380272  0.4100878
 [5,]  0.49136771  0.2802707 -0.23751204 -1.054505087 -0.5985251 -1.2519898
 [6,]  1.38103415  1.0222775 -0.74907643 -1.312144544 -0.3752412 -1.2194000
 [7,]  0.03071947 -0.1778154 -0.51156439  0.005780372  0.2573968  1.2900112
 [8,] -1.23735714 -0.9883547  1.11447956  0.620151386  1.5971008  1.4529599
 [9,]  0.93418811  1.2747659 -0.82215705 -0.806774839 -1.0823071 -1.0890410
[10,] -0.22519622  0.3111877 -0.25578219  0.184146151  1.0388908  0.3123185
[11,] -0.92220704 -0.9404335  0.71253611  1.630890796  1.2621748  0.9315238
[12,]  0.35392085  0.5626455 -0.10962094 -0.321223554 -1.0078791 -0.3720664
attr(,"scaled:center")
          ED          BIP           EL         WBIP          GEB           WS 
3.265583e+02 2.253208e+04 1.020000e+01 5.754167e+01 9.608333e+00 7.416667e-01 
attr(,"scaled:scale")
         ED         BIP          EL        WBIP         GEB          WS 
 173.885393 1940.683078    5.473407   10.091622    2.687161    3.068449

Analyse: CA (Code & Output)

  • Distanzmatrix erstellen: dist()
  • Clusteranalyse durchführen: hclust()
  • Dendrogramm erstellen: plot()
  • Scree-Plot erstellen
# Distanz-Matrix erzeugen; meist euklidische Distanz 
dist_mat <- dist(regionen_data_z, method = 'euclidean')

# Namen der Objekte (Regionen)
region_labels <- c("A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L") 

# Eigentliche Clusteranalyse
hc_result <- hclust(dist_mat, method = "complete")

# Dendrogramm erzeugen; 'hang=-1' formatiert die Beschriftung
plot(hc_result, hang=-1, labels=region_labels)

# Scree-Plot erstellen
plot(1:(length(hc_result$height)), rev(hc_result$height), type = "b",
     xlab = "Anzahl der Cluster",
     ylab = "Höhe der Fusionen",
     main = "Screeplot für hierarchische Clusteranalyse")

[optional] Analyse: Identifikation von Ausreißern

Ausreißer finden mit → Single Linkage (bzw. Nearest Neighbour)

# Daten standardisieren (= z-transformieren)
regionen_data_z <- scale(regionen_data)


# Distanz-Matrix erzeugen; meist euklidische Distanz 
dist_mat <- dist(regionen_data_z, method = 'euclidean')

# Eigentliche Clusteranalyse
hc_result_single <- hclust(dist_mat, method = "single")

# Dendrogramm erzeugen; 'hang=-1' formatiert die Beschriftung
plot(hc_result_single, hang=-1, labels = region_labels)

Ausreißer entfernen; dann → Complete (oder Ward )

#Datensatz Nummer 3 entfernen (nur als Beispiel)
#data_clean <- regionen_data_z[-3, ]

# Datensatz Nummer 2 und 3 entfernen (nur als Beispiel)
data_clean <- regionen_data_z[-c(2,3), ]
region_labels_10 <- c("A", "D", "E", "F", "G", "H", "I", "J", "K", "L") 

dist_mat <- dist(data_clean, method = 'euclidean')

hc_result_10 <- hclust(dist_mat, method = "complete")

plot(hc_result_10, hang=-1, labels = region_labels_10)

# Scree-Plot erstellen
plot(1:(length(hc_result_10$height)), rev(hc_result_10$height), type = "b",
     xlab = "Anzahl der Cluster",
     ylab = "Höhe der Fusionen",
     main = "Screeplot für hierarchische Clusteranalyse")

Vergleich mit EFA

Positionierung der Regionen im zweidimensionalen Faktorraum

Clusterlösung verarbeiten

# Cluster-Zuordnung für k Cluster
cluster_assignments <- cutree(hc_result_10, k = 2)

# Daten ohne Ausreißer
data_clean <- regionen_data_z[-c(2,3), ]

# Übersichtlicher: Auf drei Stellen runden
data_clean <- round(data_clean,3)

# Matrix wird in Dataframe umgewandelt (macht das Spalte-Anhängen leichter)
regionen_data_z <- as.data.frame(data_clean)

# Daten OHNE Cluster
head(regionen_data_z, n = 10)
       ED    BIP     EL   WBIP    GEB     WS
1  -0.657 -1.245 -0.073 -0.450 -0.450 -0.470
2  -0.516  0.299 -0.274  0.917 -0.338  0.410
3   0.491  0.280 -0.238 -1.055 -0.599 -1.252
4   1.381  1.022 -0.749 -1.312 -0.375 -1.219
5   0.031 -0.178 -0.512  0.006  0.257  1.290
6  -1.237 -0.988  1.114  0.620  1.597  1.453
7   0.934  1.275 -0.822 -0.807 -1.082 -1.089
8  -0.225  0.311 -0.256  0.184  1.039  0.312
9  -0.922 -0.940  0.713  1.631  1.262  0.932
10  0.354  0.563 -0.110 -0.321 -1.008 -0.372
# Der Dataframe erhält eine neue Spalte "Cluster"
regionen_data_z$Cluster <- factor(cluster_assignments)

# Daten MIT Cluster
head(regionen_data_z, n = 10)
       ED    BIP     EL   WBIP    GEB     WS Cluster
1  -0.657 -1.245 -0.073 -0.450 -0.450 -0.470       1
2  -0.516  0.299 -0.274  0.917 -0.338  0.410       1
3   0.491  0.280 -0.238 -1.055 -0.599 -1.252       2
4   1.381  1.022 -0.749 -1.312 -0.375 -1.219       2
5   0.031 -0.178 -0.512  0.006  0.257  1.290       1
6  -1.237 -0.988  1.114  0.620  1.597  1.453       1
7   0.934  1.275 -0.822 -0.807 -1.082 -1.089       2
8  -0.225  0.311 -0.256  0.184  1.039  0.312       1
9  -0.922 -0.940  0.713  1.631  1.262  0.932       1
10  0.354  0.563 -0.110 -0.321 -1.008 -0.372       2

Profil-Diagramme

# Code-Vorlage arbeitet mit "df", daher umbenennen
df <- regionen_data_z

# Mittelwerte für jede Dimension pro Cluster berechnen
cluster_means <- aggregate(. ~ Cluster, data = df, FUN = mean)

# Anzahl der Cluster
num_clusters <- length(unique(df$Cluster))

# Layout für die Plots
par(mfrow = c(1, num_clusters))  # Layout festlegen für die Anzahl der Cluster

# Für jedes Cluster ein Balkendiagramm erstellen
for (i in 1:num_clusters) {
  # Daten für das aktuelle Cluster (ohne Cluster-Spalte)
  data <- as.numeric(cluster_means[i, -1])
  
  # Namen der Attribute für die x-Achse
  names(data) <- names(cluster_means)[-1]
  
  # Balkendiagramm erstellen
  barplot(
    data,
    main = paste("Cluster", cluster_means$Cluster[i]),  # Titel des Diagramms
    ylim = c(-2, 2),  # Skalierung der y-Achse
    col = "lightblue",  # Farbe der Balken
    xlab = "Attribute",  # Bezeichnung der x-Achse
    ylab = "Mittelwert",  # Bezeichnung der y-Achse
    las = 2  # Dreht die x-Achsenbeschriftungen für bessere Lesbarkeit
  )
}

Schließlich …

Empfehlungen

  • Auswahl der Variablen:

    • keine strikten Vorgaben
    • relevante Variable auswählen
    • hoch korrelierte Variable ausschließen (r > 0.9)
    • alternativ: Faktorwerte aus einer explorativen Faktorenanalyse verwenden
    • keine konstanten Merkmale

  • z-Transformation

  • Distanz-Maß: euklidische Distanz

  • (Single-Linkage (auch: nächstgelegener Nachbar) zur Identifizierung von Ausreißern

  • Complete Linkage oder Ward-Verfahren (mit entfernten Ausreißern; ergibt “runde” Cluster))