Zagadnienia

6. Klasteryzacja

Klasteryzacja jest, podobnie jak analiza składowych głównych, metodą redukcji wymiaru danych. W tym przypadku jednak redukcja będzie się odbywać w pionie a zamiast odcinania części danych, będziemy je grupować. Nowym wymiarem danych będzie liczba grup. Dla macierzy X_{{n\times p}} będziemy szukać optymalnego podziału na K części, czyli szukać podziału C na K grup:

\{ 1,\ldots,n\}=C_{1}\cup\ldots\cup C_{K},

parami rozłącznych o licznościach odpowiednio n_{1},\ldots,n_{K}. Będziemy używać oznaczenia X^{k} na podmacierz X o indeksach z C_{k}, k=1,\ldots,K.

6.1. Klasteryzacja K-średnich

Klasteryzacji K-średnich używamy, gdy znamy ilość grup K, na ile chcemy podzielić dane. Zdefiniujmy następujące macierze:

Macierz wariancji całkowitej:

T=\text{var}(X)=\frac{1}{n}\sum _{{i=1}}^{n}(X_{i}-\overline{X})(X_{i}-\overline{X})^{T},

nie zależy od podziału C, var oznacza próbkową macierz kowariancji.

Zmienność całkowita to ślad macierzy T: \text{tr}(T).

Macierz wariancji wewnątrzgrupowej:

W_{C}=\sum _{{k=1}}^{K}\frac{n_{k}}{n}\text{var}(X^{k})=\frac{1}{n}\sum _{{k=1}}^{K}\sum _{{i\in C_{k}}}(X_{i}-\overline{X^{k}})(X_{i}-\overline{X^{k}})^{T},

zależy od podziału C.

Zmienność wewnątrzgrupowa to ślad macierzy W_{C}: \text{tr}(W_{C}).

Macierz wariancji międzygrupowej:

B_{C}=\sum _{{k=1}}^{K}\frac{n_{k}}{n}(\overline{X^{k}}-\overline{X})(\overline{X^{k}}-\overline{X})^{T},

zależy od podziału C.

Zmienność międzygrupowa to ślad macierzy B_{C}: \text{tr}(B_{C}).

\overline{X^{k}} oznacza p-wymiarowy wektor średnich kolumnowych dla macierzy X^{k}, a \overline{X} p-wymiarowy wektor średnich kolumnowych dla całej macierzy X. \overline{X^{k}} nazywane są centroidami, redukcja wymiaru polega na zastępowaniu grup danych przez ich centroidy.

Stwierdzenie 6.1
T=W_{C}+B_{C}\quad\forall\text{ podziału }C.
T=\frac{1}{n}\sum _{{i=1}}^{n}(X_{i}-\overline{X})(X_{i}-\overline{X})^{T}=
=\frac{1}{n}\sum _{{k=1}}^{K}\sum _{{i\in C_{k}}}(X_{i}-\overline{X^{k}}+\overline{X^{k}}-\overline{X})(X_{i}-\overline{X^{k}}+\overline{X^{k}}-\overline{X})^{T}=
=\frac{1}{n}\sum _{{k=1}}^{K}\sum _{{i\in C_{k}}}(X_{i}-\overline{X^{k}})(X_{i}-\overline{X^{k}})^{T}+\frac{1}{n}\sum _{{k=1}}^{K}\sum _{{i\in C_{k}}}(\overline{X^{k}}-\overline{X})(\overline{X^{k}}-\overline{X})^{T}+
+\underbrace{\frac{1}{n}\sum _{{k=1}}^{K}\sum _{{i\in C_{k}}}(X_{i}-\overline{X^{k}})(\overline{X^{k}}-\overline{X})^{T}}_{{=0}}+\underbrace{\frac{1}{n}\sum _{{k=1}}^{K}\sum _{{i\in C_{k}}}(\overline{X^{k}}-\overline{X})(X_{i}-\overline{X^{k}})^{T}}_{{=0}}=
=\frac{1}{n}\sum _{{k=1}}^{K}\sum _{{i\in C_{k}}}(X_{i}-\overline{X^{k}})(X_{i}-\overline{X^{k}})^{T}+\sum _{{k=1}}^{K}\frac{n_{k}}{n}(\overline{X^{k}}-\overline{X})(\overline{X^{k}}-\overline{X})^{T}=
=W_{C}+B_{C}.
Wniosek 6.1
\text{tr}(T)=\text{tr}(W_{C})+\text{tr}(B_{C}).

Czyli

\text{zmienność całkowita}=\text{ zmienność wewnątrzgrupowa }+\text{ zmienność międzygrupowa}.

Ideą klasteryzacji K-średnich jest minimalizacja po podziałach zmienności wewnątrzgrupowej, co jest jednoznaczne z maksymalizcją zmienności międzygrupowej:

C_{{opt}}=\min _{C}\text{tr}(W_{C}).
\text{tr}(W_{C})=\frac{1}{n}\sum _{{k=1}}^{K}\sum _{{i\in C_{k}}}\sum _{{j=1}}^{p}(X_{{ij}}-\overline{X^{k}_{j}})^{2}=\frac{1}{n}\sum _{{k=1}}^{K}\sum _{{i\in C_{k}}}||X_{i}-\overline{X^{k}}||^{2}.

Idea zachłannego algorytmu K-średnich (zależnego od wybranego podziału startowego C), z którego można korzystać np. w programie R wygląda następująco:

Algorytm K-średnich
 Wielokrotnie powtarzamy przy różnym podziale startowym C:
 repeat
  for (k in 1\ldots K)
   m_{k}=\text{argmin}_{m}\sum _{{i\in C^{k}}}||X_{i}-m||^{2}=\frac{1}{n_{k}}\sum _{{i\in C^{k}}}X_{i}
  for (i in 1\ldots n)
   i\in C^{k} \Leftrightarrow k=\text{argmin}_{l}||X_{i}-m_{l}||^{2}
  until warunek stopu

Przykładowy wynik algorytmu klasteryzacji K-średnich znajduje się na rysunku 6.1.

\par
Rys. 6.1. Klasteryzacja K-średnich dla danych Iris, K=3. Żeby można było przedstawić wyniki na płaszczyźnie, został zmniejszony wymiar danych poprzez analizę składowych głównych.

6.2. Klasteryzacja K-medoidów

Klasteryzacja K-medoidów jest podobna do klasteryzacji K-średnich, z tą różnicą, że zamiast średnich arytmetycznych w algorytmie będziemy używać median. Dzięki takiemu sformułowaniu, możemy go używać przy dowolnej macierzy odległości między obiektami D=(d_{{ij}})_{{i,j=1}}^{n}.

Algorytm K-medoidów
 Wielokrotnie powtarzamy przy różnym podziale startowym C:
 repeat
  for (k in 1\ldots K)
   m_{k}=\text{argmin}_{m}\sum _{{i\in C^{k}}}d_{{im}}  # m jako mediana, należy do zbioru obserwacji
  for (i in 1\ldots n)
   i\in C^{k} \Leftrightarrow k=\text{argmin}_{l}d_{{im_{l}}}
  until warunek stopu

6.3. Klasteryzacja hierarchiczna

Używając klasteryzacji hierarchicznej nie zakładamy z góry ilości klastrów, na jakie chcemy podzielić dane. Wychodzimy od sytuacji, gdy mamy n klastrów, czyli każda obserwacja jest oddzielną grupą. W każdym kroku algorytmu łączymy 2 klastry, czyli zmniejszamy ich liczbę o jeden i tak aż do połączenia wszystkich obserwacji w jedną grupę. Wybór ilości klastrów opieramy na wykresie separowalności, która obliczana jest dla każdego kroku algorytmu.

W klasteryzacji hierarchicznej możemy używać różnych metod aglomeracji danych. Dla macierzy odległości D=(d_{{ij}})_{{i,j=1}}^{n} odległość dwóch klastrów G i H od siebie przy założeniach

G,H\subseteq\{ 1,\ldots,n\}\quad,\quad G\cap H=\emptyset,

możemy zdefiniować jako:

  1. Single linkage

    d_{{G,H}}=\min _{{i\in G,j\in H}}d_{{ij}}.
  2. Average linkage

    d_{{G,H}}=\frac{1}{|G||H|}\sum _{{ij}}d_{{ij}},

    gdzie |\cdot| oznacza liczność zbioru.

  3. Complete linkage

    d_{{G,H}}=\max _{{i\in G,j\in H}}d_{{ij}}.

Ideę algorytmu klasteryzacji hierarchicznej możemy zapisać jako:

Algorytm klasteryzacji hierarchicznej
 C=\{ 1\},\{ 2\},\ldots,\{ n\}
 for (l in 1:(n-1))
  połącz najbliższe dwa klastry:
   (i_{*},j_{*})=\text{argmin}_{{i,j:i<j}}d_{{ij}}
   klastry i_{*} oraz j_{*} zastąp przez 0
  odnów macierz odległości d_{{0,k}}=\min(d_{{i_{*}k}},d_{{j_{*}k}})

Definicja 6.1

Dendrogram jest metodą ilustracji wyników klasteryzacji hierarchicznej. Możemy obserwować od dołu dendrogramu (rysunek 6.2) jak kolejne klastry się łączą i dla jakiej wysokości (odległości klastrów) to zachodzi.

\par
Rys. 6.2. Przykładowy dendrogram dla klasteryzacji hierarchicznej.
Definicja 6.2

Oznaczmy h_{k} jako minimalną wysokość, na której obserwujemy podział na k części. Na przykład, na obrazku 6.2 dla k=5 h_{5}\approx 0,2.

Separowalność dla klasteryzacji hierarchicznej definiujemy jako:

\text{sep}(k)=1-\frac{h_{k}}{h_{1}}.

Z definicji separowalności możemy wywnioskować następujące własności:

  • separowalność przyjmuje wartości z przedziału [0,1];

  • jest niemalejącą funkcją liczby klastrów.

Przykładowy wykres separowalności znajduje się na rysunku 6.3. Na podstawie tego wykresu podejmuje się decyzję dotyczącą optymalnej ilości klastrów. Szukamy takiego k, żeby sep(k)-sep(k-1) było duże w stosunku do sep(k+1)-sep(k). Chcemy znaleźć taką niewielką liczbę klastrów, żeby zysk mierzony separowalnością przy łączeniu klastrów w danym kroku był duży, a dalsze sklejanie grup nie dawało już takich korzyści. Graficznie sprowadza się to do szukania ,,kolanka” funkcji separowlaności. Jednym ze sposobów jest szukanie punktu na wykresie najbliższego punktowi (0,1). Przykładowo, na rysunku 6.3 optymalnym wyborem jest k=3 (k=5 też jest dobrym wyborem, chociaż dążymy do tego aby jak najbardziej zredukować wymiar danych, czyli wybrać jak najmniejsze k).

\par
Rys. 6.3. Przykładowy wykres separowalności dla danych Iris.
Definicja 6.3

Można zdefiniować także separowalność dla klasteryzacji K-średnich. Oznaczmy:

t=\text{tr}(T);
w_{k}=\min _{C}\text{tr}(W_{C}),\quad k\text{ jest liczbą klastrów;}
t=w_{k}+w_{b}.

Ponieważ wiemy, że:

1=\frac{w_{k}}{t}+\frac{b_{k}}{t},\quad w_{1}=t,\quad w_{n}=0,

możemy zdefiniować separowalność jako:

\text{sep}(k)=1-\frac{w_{k}}{t}.
Stwierdzenie 6.2

Separowalność dla klasteryzacji K-średnich jest niemalejącą funkcją k, liczby klastrów. Funkcja w_{k} jest więc nierosnąca ze względu na liczbę klastrów.

Jako praca domowa.

6.4. Przykłady w programie R

Klasteryzacja:

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.