data > opinion

Tom Alby

08 Clustering

2021-05-03


Segmentierung: Clustering

Hierarchisches Clustering

Hierarchisches Clustering ist ein populärer Ansatz des Unsupervised Machine Learnings. Zunächst laden wir eine Library für das Clustering:

library(cluster)

Der folgende Datensatz beinhaltet das Alter und die Noten von Studierenden, natürlich völlig fiktiv.

(age_grades <- data.frame(age = c(22,22,21,23,27,27,26,20), grades = c(1,3,5,1,5,3,4,1)))
##   age grades
## 1  22      1
## 2  22      3
## 3  21      5
## 4  23      1
## 5  27      5
## 6  27      3
## 7  26      4
## 8  20      1

Zunächst wird die euklidische Distanz verwendet, um die Distanz zwischen allen Datenpunkten zueinander zu berechnen, zum Beispiel Beispiel Datenpunkt 1 (22,1) und Datenpunkt 2 (22,3):

\[\sqrt{(22-22)^2 + (1-3)^2}\]

Beispiel Datenpunkt 1 (22,1) und Datenpunkt 3 (21,5): \[\sqrt{(22-21)^2 + (1-5)^2} = \sqrt{(1 + 16)} = 4,123106\]

Das soll an einem vereinfachten Beispiel erläutert werden. Zunächst wird die Distanzmatrik erstellt:

(age_grades.dist <- dist(age_grades, method="euclidean"))
##          1        2        3        4        5        6        7
## 2 2.000000                                                      
## 3 4.123106 2.236068                                             
## 4 1.000000 2.236068 4.472136                                    
## 5 6.403124 5.385165 6.000000 5.656854                           
## 6 5.385165 5.000000 6.324555 4.472136 2.000000                  
## 7 5.000000 4.123106 5.099020 4.242641 1.414214 1.414214         
## 8 2.000000 2.828427 4.123106 3.000000 8.062258 7.280110 6.708204

Aus dieser Distanzmatrix kann ein Dendrogramm erstellt werden. Das Dendrogramm ist so zu lesen, dass auf der y-Achse die Entfernungen zwischen den Clustern gezeigt werden; die Abstände auf der x-Achse haben nichts zu sagen.

age_grades.hc <- hclust(age_grades.dist, method = "complete")
plot(age_grades.hc)

Allerdings hat dieser Ansatz noch einen Schönheitsfehler, denn wenn eine Variable höhere Werte als die andere Variable hat wie in diesem Beispiel, so können die höheren Werte das Ergebnis dominieren. Daher werden die Daten in der Regel zunächst einmal normalisiert:

(age_grades.dist <- dist(scale(age_grades), method="euclidean"))
##           1         2         3         4         5         6         7
## 2 1.1581526                                                            
## 3 2.3441201 1.2128260                                                  
## 4 0.3600411 1.2128260 2.4256521                                        
## 5 2.9336002 2.1405742 2.1602469 2.7275160                              
## 6 2.1405742 1.8002057 2.4511189 1.8480778 1.1581526                    
## 7 2.2565545 1.5522253 1.8910500 2.0456370 0.6818790 0.6818790          
## 8 0.7200823 1.3637580 2.3441201 1.0801234 3.4230281 2.7736563 2.7721167

Normalisierung bzw. Standardisierung mit scale() bedeutet, dass von jedem Wert in einer Spalte das arithmetische Mittel der Spalte substrahiert wird und das Ergebnis dann durch die Standardabweichung der Spalte geteilt wird. Man könnte auch sagen, dass der standardisierte Wert angibt, wie viele Standardabweichungen ein Wert vom Mittelwert abweicht. Beispiel:

mean(age_grades$age)
## [1] 23.5
sd(age_grades$age)
## [1] 2.77746

Dann ist der standardisierte Alterswert des ersten Studierenden:

(age_grades[1,1] - mean(age_grades$age)) / sd(age_grades$age)
## [1] -0.5400617

Noch mal prüfen:

head(scale(age_grades$age),1)
##            [,1]
## [1,] -0.5400617
age_grades.hc <- hclust(age_grades.dist, method = "complete")
plot(age_grades.hc)

Schauen wir uns das mal mit 3 Vektoren an:

(age_grades <- data.frame(age = c(22,22,21,23,27,27,26,20), grades = c(1,3,5,1,5,3,4,1), term = c(2,2,1,4,9,10,8,1)))
##   age grades term
## 1  22      1    2
## 2  22      3    2
## 3  21      5    1
## 4  23      1    4
## 5  27      5    9
## 6  27      3   10
## 7  26      4    8
## 8  20      1    1

Auch hier wird wieder die euklidische Distanz berechnet, Beispiel Datenpunkt 1 (22,1,2) und Datenpunkt 2 (22,3,2):

\[\sqrt{((22-22)^2 + (1-3)^2 + (2-2)^2)} = \sqrt{(0+4+0)} = 2\]

Netterweise macht R das alles für uns mit der Funktion dist(), so dass wir das nicht selber rechnen müssen.

(age_grades.dist <- dist(scale(age_grades), method="euclidean"))
##           1         2         3         4         5         6         7
## 2 1.1581526                                                            
## 3 2.3590224 1.2413841                                                  
## 4 0.6402969 1.3233659 2.5523668                                        
## 5 3.4699140 2.8313161 3.0252725 3.0317542                              
## 6 3.0112564 2.7796309 3.4183447 2.4369131 1.1880257                    
## 7 2.7595637 2.2209361 2.6477090 2.3034827 0.7314688 0.8633130          
## 8 0.7672067 1.3892169 2.3441201 1.3406920 4.0252613 3.6565374 3.3345050

Auch diese Daten plotten wir in ein Dendrogramm:

age_grades.hc <- hclust(age_grades.dist, method = "complete")
plot(age_grades.hc)

Die Cluster sind immer noch ähnlich aufgeteilt, haben sich aber leicht verschoben.

K Means Clustering

Der K Means-Algorithmus ist einer der bekanntesten Clustering-Algorithmen. Zunächst einmal werden k Mittelpunkte (Centroids) in die Datenpunkte gesetzt. Durch diese Mittelpunkte werden die Datenpunkte in k Gruppen eingeteilt. Nun werden die tatsächlichen Mittelpunkte innerhalb des jeweiligen Clusters berechnet. Dann werden die Datenpunkte erneut den Clustern zugeordnet. Es kann dabei passieren, dass ein Datenpunkt einem anderen Cluster zugeordnet wird. Der Vorgang wird immer wieder wiederholt, bis es keine Änderungen mehr gibt. Die große Herausforderung ist, dass k zunächst unbekannt ist.

Als Beispiel wird der Wein-Datensatz genutzt:

head(wine_data <- read.table("https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data", sep=","))
##   V1    V2   V3   V4   V5  V6   V7   V8   V9  V10  V11  V12  V13  V14
## 1  1 14.23 1.71 2.43 15.6 127 2.80 3.06 0.28 2.29 5.64 1.04 3.92 1065
## 2  1 13.20 1.78 2.14 11.2 100 2.65 2.76 0.26 1.28 4.38 1.05 3.40 1050
## 3  1 13.16 2.36 2.67 18.6 101 2.80 3.24 0.30 2.81 5.68 1.03 3.17 1185
## 4  1 14.37 1.95 2.50 16.8 113 3.85 3.49 0.24 2.18 7.80 0.86 3.45 1480
## 5  1 13.24 2.59 2.87 21.0 118 2.80 2.69 0.39 1.82 4.32 1.04 2.93  735
## 6  1 14.20 1.76 2.45 15.2 112 3.27 3.39 0.34 1.97 6.75 1.05 2.85 1450

Zunächst entfernen wir die zugeordnete Klasse:

wine = wine_data[,-1] 

Dann werden die Daten normalisiert:

wine.scaled <- as.data.frame(scale(wine))

Um herauszufinden wie viele k sinnvoll sind, wird ein Scree-Test durchgeführt. Ein Knick in einer Scree-Plot-Kurve bedeutet, dass bei dieser Anzahl die Variabilität innerhalb der Cluster abgefallen ist:

wss <- (nrow(wine.scaled)-1)*sum(apply(wine.scaled,2,var))
  for (i in 2:10) wss[i] <- sum(kmeans(wine.scaled,
                                       centers=i)$withinss)
plot(1:10, wss, type="b", xlab="Number of Clusters",
     ylab="Within groups sum of squares")

Nun versuchen wir das Clustering mit k=3:

k.means.fit <- kmeans(wine.scaled, 3) 

In einem Clusterplot werden die Dimensionen reduziert auf zwei Komponenten:

clusplot(wine, k.means.fit$cluster, color=TRUE, shade=TRUE,
labels=4, lines=0, main="K-means cluster plot")

Wichtig ist hier, dass der Anteil der Variabilität, der durch die beiden Komponenten erklärt wird, beachtet wird. Insbesondere wenn durch Dummy-Variablen binäre Daten in vielen Spalten und Zeilen vorhanden sind, dann kann dieser Prozentwert sehr niedrig sein, so dass das Ergebnis wenig sinnvoll ist.

Wie gut hat k Means nun die Weine eingeteilt?

table(wine_data$V1,k.means.fit$cluster)
##    
##      1  2  3
##   1  0 59  0
##   2 65  3  3
##   3  0  0 48