13 Analiza skupień

Analiza skupień jest narzędziem analizy danych służącym do grupowania jednostek eksperymentalnych (lub/i zmiennych), opisanych za pomocą wektora obserwacji, w \(K\) niepustych, rozłącznych i możliwie “jednorodnych” grup - skupień. Jednostki (zmienne) należące do danego skupienia powinny być “podobne” od siebie (używa się w tym celu różnych miar podobieństwa, a w zasadzie niepodobieństwa), a jednostki (zmienne) należące do różnych skupień powinny być z kolei możliwie mocno “niepodobne” do siebie. Głównym celem tej analizy jest wykrycie z zbiorze danych, tzw. “naturalnych” skupień, czyli skupień, które dają się w sensowny sposób interpretować.

Algorytmy analizy skupień:

  1. hierarchiczne (np. metoda aglomeracyjna),
  2. niehierarchiczne (np. metoda \(k\)-średnich).

Metoda aglomeracyjna

Podstawowe miary niepodobieństwa jednostek (zmiennych):

  1. odległość euklidesowa - stosowana w przypadku grupowania jednostek opisanych zmiennymi ilościowymi,
  2. niezgodność procentowa - stosowana w przypadku grupowania jednostek opisanych zmiennymi jakościowymi,
  3. \(1-r\) Pearsona - stosowana w przypadku grupowania zmiennych.

Podstawowe sposoby wiązania skupień:

  1. metoda pojedynczego wiązania (najbliższego sąsiedztwa) - miara niepodobieństwa pomiędzy dwoma skupieniami jest określona jako najmniejsza miara niepodobieństwa między dwoma jednostkami (zmiennymi) należącymi do różnych skupień,
  2. metoda pełnego wiązania (najdalszego sąsiedztwa) - miara niepodobieństwa pomiędzy dwoma skupieniami jest określona jako największa miara niepodobieństwa między dwoma jednostkami (zmiennymi) należącymi do różnych skupień,
  3. metoda średniego wiązania - miara niepodobieństwa pomiędzy dwoma skupieniami jest określona jako średnia miara niepodobieństwa między wszystkimi parami jednostek (zmiennych) należących do różnych skupień.

Algorytm aglomeracyjny

  1. W pierwszym kroku każda z jednostek (zmiennych) tworzy oddzielne skupienie.
  2. Łączymy (wiążemy ze sobą) dwa najbardziej podobne do siebie skupienia - w sensie wybranej miary niepodobieństwa skupień - zmniejszając w ten sposób liczbę skupień o jeden.
  3. Powtarzamy krok drugi do momentu uzyskania zadeklarowanej, końcowej liczby skupień \(K\) lub do połączenia wszystkich jednostek (zmiennych) w jedno skupienie.

Uwaga: Graficzną ilustracją przebiegu aglomeracji jest wykres zwany dendrogramem.

Metoda \(k\)-średnich

Główną ideą metody \(K\)-średnich jest taka alokacja jednostek, która minimalizuje zmienność wewnątrz powstałych skupień, a co za tym idzie maksymalizuje zmienność pomiędzy skupieniami.

Niech \(C_K\) oznacza funkcję, która każdej jednostce (dokładnie jego numerowi), przyporządkowuje numer skupienia do którego jest ona przyporządkowana (przy podziale na \(K\) skupień).

Dla ustalonej funkcji \(C_K\), oznaczmy macierze zmienności (analogicznie jak w ANOVA):

  • \(SSE(C_K)\) - macierz zmienności wewnątrz skupień,
  • \(SSA(C_K)\) - macierz zmienności pomiędzy skupieniami,
  • \(SST\) - macierz zmienności całkowitej, przy czym \[SST=SSE(C_K)+SSA(C_K).\]

Powszechnie stosowane algorytmy metody \(K\)-średnich minimalizują ślad macierzy \(SSE(C_K)\).

Oznaczmy przez \(C^*_K\) funkcję realizującą optymalny podział jednostek na \(K\) skupień.

Wtedy \[C^*_K=\min_{C_K} \mathrm{tr}[SSE(C_K)].\]

Algorytm \(K\)-średnich

  1. Rozmieszczamy \(n\) jednostek w \(K\) skupieniach. Niech funkcja \(C_K^{(1)}\) opisuje to rozmieszczenie.
  2. Dla każdego z \(K\) skupień obliczamy wektory średnich \({\pmb {\bar x}_k}\), \((k=1,2,\ldots ,K)\).
  3. Rozmieszczamy ponownie jednostki w \(K\) skupieniach, w taki sposób że \[C_K^{(l)}(i)=\arg\min_{1\leq k\leq K} \mathrm{tr}[SSE(C_K)].\]
  4. Powtarzamy kroki drugi i trzeci aż do momentu, gdy przyporządkowanie jednostek do skupień pozostanie niezmienione, tzn. aż do momentu, gdy \(C_K^{(l)}=C_K^{(l-1)}\).

Istnieje wiele modyfikacji powyższego algorytmu. Przykładowo, losowe rozmieszczenie elementów w skupieniach - krok pierwszy algorytmu, zastąpione zostaje narzuconym podziałem, mającym na celu szybsze ustabilizowanie się algorytmu. Inna modyfikacja polega na przeliczeniu średnich skupień natychmiast po przesunięciu pomiędzy skupieniami choćby jednego elementu.

Wszystkie wersje algorytmu \(K\)-średnich są zbieżne. Nie gwarantują one jednak zbieżności do optymalnego rozwiązania \(C^*_K\). Niestety, w zależności od początkowego podziału, algorytm zbiega do zazwyczaj różnych lokalnie optymalnych rozwiązań. W związku z tym, aby uzyskać najlepszy podział, zaleca się często wielokrotne stosowanie tego algorytmu z różnymi, wstępnymi rozmieszczeniami jednostek.

Funkcje związane z analizą skupień:

dist - obliczanie macierzy odległości,

hclust - metoda aglomeracyjna, procedura główna,

plclust - dendrogram,

cutree - podział na skupienia,

kmeans - metoda \(k\)-średnich, procedura główna.