Uczenie maszynowe w R

• Analiza skupień
• Algorytmy
  • k-means, k-medoids
  • AHC
  • DBSCAN
• Miary podobieństwa
• Miary oceny

Celem algorytmów analizy skupień (grupowania) jest połączenie w grupy obiektów podobnych do siebie i oddzielenie obiektów, które się od siebie różnią.

Definicja miary podobieństwa między obiektami jest kluczowa dla każdego algorytmu grupowania. To co rozumiane jest jako grupa, też bywa różnie definiowane. Wynika to z faktu, że grupowanie jest “źle zdefiniowanym problemem”.

Podstawowe typy algorytmów:

• Iteracyjne (k-means, k-medoids)
• Hierarchiczne (AHC)
• Gęstościowe (DBSCAN, OPTICS)
• Komunikacyjne (affinity propagation)
• Oparte o rozkłady (EM)

Algorytmy analizy skupień pozostają rozproszone po różnych paczkach w R.

Pokażemy tylko kilka podstawowych zagadnień z grupowania. Przykłady będą wykonywane na zbiorze Iris.

library(factoextra)
library(fpc)
library(NbClust)

set.seed(23)
df <- iris[, -5] # usuwamy kolumnę Species
df <- scale(df)

1. Ustalamy liczbę skupień k
2. Losujemy k punktów (wstępnych środków skupień)
3. Obliczamy odległości obiektów od środków skupień
4. Przypisujemy obiekty do najbliższych skupień
5. Wyliczamy nowe środki skupień
6. Wykonujemy kroki 3,4,5 do czasu, aż:
   • środki skupień przestaną się zmieniać
   • wykonamy maksymalną liczbę iteracji

Sprawdzamy sumę sum kwadratów (wss) odległości od centroidu dla wszystkich skupień przy rosnącym k. Następnie analizujemy wykres zależności wws od k (elbow plot). Alternatywnie wykorzystujemy miarę gap statistic, lub rysujemy silhouette plot.

wss <- (nrow(df)-1)*sum(apply(df,2,var))
for (i in 2:15) 
  wss[i] <- sum(kmeans(df,
                centers=i)$withinss)
wssDf = data.frame(n=1:15, wss=wss)

Dla k-średnich jak i innych algorytmów grupowania kluczowe jest określenie miary odległości między przykładami. Typowe miary to:

• miara euklidesowa
• miara manhattańska
• inne miary Minkowskiego
• odległość Jaccarda
• odległość Mahalonobisa
• miary mieszane

Algorytm jest bardzo podobny do k-średnich, z tą różnicą, że po każdej iteracji wyliczany jest nie centroid tylko medoid. Medoid jest to przykład, który znajduje się najbliżej centrum skupień.

Ponieważ jest to konkretny przykład a nie punkt w przestrzeni, medoid może być traktowany jako konkretny reprezentant skupienia ze zbioru danych.

Popularne wersje: PAM i CLARA

AHC = Agglomerative Hierarchical Clustering

1. Ustal każdy przykład jako osobne skupienie
2. Oblicz macierz odległości między skupieniami
3. W macierzy odległości znajdź parę najbliższych skupień
4. Połącz znalezioną parę w jedno skupienie
5. Powtórz kroki 2-4 dopóki nie powstanie jedno skupienie

• Single-link: odległość między najbliższymi elementami w skupieniach
• Complete-link: odległość między najdalszymi elementami w skupieniach
• Average-link: średnia odległości wszystkich par między skupieniami
• Centroid: odległość między centroidami
• Ward: połączenie, które minimalizuje wss

Density-Based Spatial Clustering and Application with Noise

1. Dla przykładu x_i oblicz jego odległość od innych przykładów
2. Znajdź wszystkich sąsiadów x_i w odległości eps.
3. Każdy punkt z liczbą sąsiadów większą niż MinPts jest oznaczany jako rdzenny, reszta jako odwiedzone.
4. Dla każdego rdzennego punktu, jeśli nie jest przypisany do żadnego skupienia, stwórz nowe skupienie. Przypisz gęstościowo połączone punkty do tego samego skupienia.
5. Przejdź do kolejnego nieodwiedzonego przykładu x_i (1)
6. Przykłady nieprzypisane do skupień to wartości odstające

Jak znamy poprawne etykiety to mamy do dyspozycji macierz pomyłek i możemy wykorzystać miary znane z klasyfikacji

kc <- kmeans(df, 3)
table(iris$Species, kc$cluster)

              1  2  3
  setosa      0 33 17
  versicolor 46  0  4
  virginica  50  0  0

Polecanymi miarami przy znajomości etykiet są Adjuested Mutual Information (AMI) i Adjusted Rand Index (ARI).

Jeśli nie znamy poprawnych etykiet dla danych uczących to typowymi miarami oceny są:

• Silhouette coefficient: ocena przynależności punktu do skupienia w którym jest (intracluster-similarity) oraz odległości od punktów innych skupień (intercluster dissimilarity); średnia z silhouette dla wszystkich punktów daje ocenę całego grupowania
• Dunn index: podobna miara, przy czym skupia się na ocenie spójności (diameter) i odległości (separation) całych grup; Dunn = min(separation) / max(diameter)

• Stwórz zbiór danych w następujący sposób:

library(fpc)

set.seed(23)
face <- rFace(1000, p=2, dMoNo=3)
df = data.frame(x=face[,1], y=face[,2])
labels = as.integer(attr(face,"grouping"))

• df to dane do pogrupowania, labels poprawne etykiety

• Przetestuj różne algorytmy grupowania
• Dla każdego algorytmu określ jakość skupień:
  • za pomocą miary liczbowej
  • tworząc macierz pomyłek
  • wizualizując dane

ggplot(df, aes(x, y, color=factor(predicted))) + 
    geom_point() + 
    theme_bw()

• http://www.sthda.com/english/articles/29-cluster-validation-essentials/97-cluster-validation-statistics-must-know-methods/
• http://www.sthda.com/english/articles/30-advanced-clustering/105-dbscan-density-based-clustering-essentials/
• http://www.statmethods.net/advstats/cluster.html
• http://wiki.math.yorku.ca/index.php/R:_Cluster_analysis