Na ostatnich zajęciach zajmiemy się tzw. technikami analizy skupień, zwanymi również technikami klastrowania danych (ang. clustering). Podobnie jak analiza składowych głównych, są to techniki uczenia bez nadzoru. Jak nazwa wskazuje, służą do wykrywania skupisk w danych. Na przykład, poniższy wykres przedstawia wyniki algorytmu k-means na danych iris - w tym przypadku skupiska dość dobrze pokrywają się z gatunkami. W typowym zastosowaniu kolumny typu Species nie są znane - nie wiemy, czemu odpowiadają poszczególne skupiska.

Analiza skupień jako taka to prawdopodobnie najmniej precyzyjnie zdefiniowany problem spośród tych, z którymi się dotychczas spotkaliśmy. Nie ma żadnej ogólnie przyjętej definicji skupisk, jakie te techniki miałyby wykrywać - dość często tego typy algorytmy projektuje się tak, aby dawały wynik zgodny z intuicją, a następnie jeśli trzeba to dobiera się definicję skupiska pod dany algorytm.

K-means, k-medoids

Algorytm k-means służy do klastrowania punktów w przestrzeni euklidesowej \(\mathbb{R}^d\). W pierwszym kroku tworzymy \(k\) tzw. centroidów, czyli punktów w przestrzeni \(\mathbb{R}^d\), a następnie dla każdego punktu znajdujemy najbliższy centroid i przesuwamy każdy centroidu w środek zbioru utworzonego z najbliższych mu punktów. Dwa ostatnie kroki są powtarzane iteracyjnie. Z praktycznego punktu widzenia algorytm ma następujące własności:

Algorytm k-medoids jest stosunkowo podobny do k-means. Zamiast centroidów stosujemy tu medoidy, czyli wybrane obserwacje z naszych danych reprezentujące środki klastrów. Najpopularniejszym podejściem do techniki k-medoidów jest algorytm PAM (partitioning around medoids). W pierwszym kroku wybieramy losowo \(k\) obserwacji jako medoidy. Następnie iteracyjnie przenoismy medoid na inną obserwację i sprawdzamy czy suma odległości punktów od najbliższych im medoidów zmalała. Z praktycznego punktu widzenia algorytm ma następujące własności:

Więcej na temat algorytmu k-means można przeczytać tutaj, a na temat k-medoids tutaj.

Zadanie 1. Zadanie przykładowe. Przeprowadź analizę skupień na danych iris korzystając z algorytmów k-means oraz PAM.

Rozwiązanie. Klastrowanie algorytmem k-means przeprowadzamy za pomocą funkcji kmeans z R-owej biblioteki standardowej. Jako pierwszy argument przekazujemy kolumny numeryczne (algorytm k-means nie potrafi wykorzystywać innych zmiennych niż numeryczne, więc nie możemy przekazać mu kolumny Species). Jako drugi argument przekazujemy liczbę klastrów.

iris_kmeans <- kmeans(iris[, 1:4], 3)
iris_kmeans
## K-means clustering with 3 clusters of sizes 21, 96, 33
## 
## Cluster means:
##   Sepal.Length Sepal.Width Petal.Length Petal.Width
## 1     4.738095    2.904762     1.790476   0.3523810
## 2     6.314583    2.895833     4.973958   1.7031250
## 3     5.175758    3.624242     1.472727   0.2727273
## 
## Clustering vector:
##   [1] 3 1 1 1 3 3 3 3 1 1 3 3 1 1 3 3 3 3 3 3 3 3 3 3 1 1 3 3 3 1 1 3 3 3 1 3 3
##  [38] 3 1 3 3 1 1 3 3 1 3 1 3 3 2 2 2 2 2 2 2 1 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2
##  [75] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2
## [112] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [149] 2 2
## 
## Within cluster sum of squares by cluster:
## [1]  17.669524 118.651875   6.432121
##  (between_SS / total_SS =  79.0 %)
## 
## Available components:
## 
## [1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss"
## [6] "betweenss"    "size"         "iter"         "ifault"

Wynik funkcji kmeans zawiera m.in. położenia centroidów oraz klaster przypisany do każdej obserwacji. Wykorzystamy je żeby odtworzyć wykres z początku tego skryptu:

library(ggplot2)
klastry <- factor(iris_kmeans$cluster)
ggplot(iris, aes(x=Petal.Length, y=Petal.Width, shape=klastry, col=Species)) + geom_point() + theme_minimal()

Porównajmy teraz wynik z algorytmem PAM. Wykorzystamy funkcję pam z biblioteki cluster.

library(cluster)
iris_pam <- pam(iris[, 1:4], 3)
iris_pam
## Medoids:
##       ID Sepal.Length Sepal.Width Petal.Length Petal.Width
## [1,]   8          5.0         3.4          1.5         0.2
## [2,]  79          6.0         2.9          4.5         1.5
## [3,] 113          6.8         3.0          5.5         2.1
## Clustering vector:
##   [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [38] 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
##  [75] 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 3 3 3 3 2 3 3 3 3
## [112] 3 3 2 2 3 3 3 3 2 3 2 3 2 3 3 2 2 3 3 3 3 3 2 3 3 3 3 2 3 3 3 2 3 3 3 2 3
## [149] 3 2
## Objective function:
##     build      swap 
## 0.6709391 0.6542077 
## 
## Available components:
##  [1] "medoids"    "id.med"     "clustering" "objective"  "isolation" 
##  [6] "clusinfo"   "silinfo"    "diss"       "call"       "data"

Struktura wyniku jest bardzo podobna jak poprzednio. W tym przypadku wyniki też będą bardzo podobne - główna różnica to to, że tym razem środki klastrów pokrywają się z obserwacjami, podczas gdy w przypadku algorytmu k-means praktycznie zawsze środki klastrów leżą pomiędzy obserwacjami.

W przeciwieństwie do algorytmu k-means, algorytm PAM umożliwia również wykorzytanie innych miar odległości między punktami. Zobaczmy jakie wyniki dostaniemy, jeśli zamiast odległości euklidesowej wykorzystamy odległość supremum:

macierz_odleglosci <- dist(iris[, 1:4], method='maximum')
iris_pam2 <- pam(macierz_odleglosci, 3)
ggplot(iris, aes(x=Petal.Length, y=Petal.Width, shape=factor(iris_pam2$clustering), col=Species)) + geom_point() + theme_minimal()

Wyniki są bardzo podobne - m.in. dlatego, że w przypadku danych iris poszczególne gatunki tworzą klastry które jest bardzo łatwo wyodrębnić. W następnym zadaniu przyjrzymy się danym, na których już nie jest tak łatwo.

Zadanie 2. W tym zadaniu porównamy metody k-means oraz k-medoids na zbiorze danych typu mouse. Jest to typ zbioru danych zaprojektowany specjalnie po to, żeby zobrazować wady tych dwóch algorytmów.
Utwórz dane, losując:

Przedstaw dane na wykresie i pokoloruj punkty w zależności od rozkładu, z którego były losowane. Następnie sklastruj dane algorytmem k-means, korzystając z funkcji kmeans, oraz algorytmem PAM, korzystając z funkcji pam z pakietu cluster. W obu przypadkach rozpatrz od dwóch do trzech różnych wartości \(k\), w szczególności \(k=3\). Wyniki przedstaw na wykresie, na którym kolorem zaznaczysz numer klastru. Zaznacz również położenia centroidów lub medoidów.

Klastrowanie hierarchiczne

Zadanie 3. Wczytaj i obejrzyj zbiór danych dotyczący sportowców ais.txt, który był analizowany na poprzednich zajęciach. Zbiór danych możesz również znaleźć tutaj.

  1. Wybierz zmienne numeryczne, wycentruj je i przeskaluj. Wybierz losowo od 20 do 40 obserwacji.
  2. Sklastruj dane za pomocą algorytmu klastrowania hierarchicznego zaimplementowanego w funkcji hclust (zwróć uwagę na specyficzną składnię funkcji, opisaną w dokumentacji - funkcja nie przyjmuje po prostu tabeli z danymi).
  3. Obejrzyj dendrogram. Oznacz na liściach sport jaki uprawia dany sportowiec (sprawdź jak to zrobić w dokumentacji funkcji plot.hclust). Czy podobne sporty są w podobnych klastrach?
  4. Oznacz liście płcią sportowca. Czy klastry znalezione przez hclust lepiej zgadzają się z typem sportu, czy płcią?

Porównaj wyniki dla różnych algorytmów klastrowania hierarchicznego (argument method w funkcji hclust) oraz różnych miar odległości pomiędzy obserwacjami.