Zagadnienia

6.1 Klasteryzacja $K$ -średnich
6.2 Klasteryzacja $K$ -medoidów
6.3 Klasteryzacja hierarchiczna
6.4 Przykłady w programie R

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:

Single linkage

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

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

gdzie $|\cdot|$ oznacza liczność zbioru.
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:

k-średnich i hierarchiczna na danych Kraby, kobiety Pima i Irysy: http://www.mimuw.edu.pl/~pokar/StatystykaII/EKSPLORACJA/ileKlastrow.R
wybór liczby klastrów na podstawie wykresu separowalności i sylwetki dla algorytmów k-średnich i k-medoidów: http://www.mimuw.edu.pl/~pokar/StatystykaII/EKSPLORACJA/sep_syl.r
k-średnich i hierarchiczna zobrazowane przy pomocy analizy składowych głównych: http://www.mimuw.edu.pl/~pokar/StatystykaII/EKSPLORACJA/pca.R
k-średnich i hierarchiczna oraz PCA i skalowanie wielowymiarowe dla danych Iris i Kraby: http://www.mimuw.edu.pl/~pokar/StatystykaII/EKSPLORACJA/rzutDanych.R

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

Statystyka II wykłady

Zagadnienia

6. Klasteryzacja

6.1. Klasteryzacja -średnich

Stwierdzenie 6.1

Wniosek 6.1

Algorytm -średnich

6.2. Klasteryzacja -medoidów

Algorytm -medoidów

6.3. Klasteryzacja hierarchiczna

Algorytm klasteryzacji hierarchicznej

Definicja 6.1

Definicja 6.2

Definicja 6.3

Stwierdzenie 6.2

6.4. Przykłady w programie R

6.1. Klasteryzacja $K$ -średnich

Algorytm $K$ -średnich

6.2. Klasteryzacja $K$ -medoidów

Algorytm $K$ -medoidów