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 Xn×p będziemy szukać optymalnego podziału na K części, czyli szukać podziału C na K grup:

1,…,n=C1∪…∪CK,

parami rozłącznych o licznościach odpowiednio n1,…,nK. Będziemy używać oznaczenia Xk na podmacierz X o indeksach z Ck, k=1,…,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=var⁢X=1n⁢∑i=1nXi-X¯⁢Xi-X¯T,

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

Zmienność całkowita to ślad macierzy T: tr⁢T.

Macierz wariancji wewnątrzgrupowej:

WC=∑k=1Knkn⁢var⁢Xk=1n⁢∑k=1K∑i∈CkXi-Xk¯⁢Xi-Xk¯T,

zależy od podziału C.

Zmienność wewnątrzgrupowa to ślad macierzy WC: tr⁢WC.

Macierz wariancji międzygrupowej:

BC=∑k=1Knkn⁢Xk¯-X¯⁢Xk¯-X¯T,

zależy od podziału C.

Zmienność międzygrupowa to ślad macierzy BC: tr⁢BC.

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

Stwierdzenie 6.1

T=WC+BC⁢⁢∀ podziału ⁢C.

T=1n⁢∑i=1nXi-X¯⁢Xi-X¯T=

=1n∑k=1K∑i∈Ck(Xi-Xk¯+Xk¯-X¯)(Xi-Xk¯+Xk¯-X¯)T=

=1n⁢∑k=1K∑i∈CkXi-Xk¯⁢Xi-Xk¯T+1n⁢∑k=1K∑i∈CkXk¯-X¯⁢Xk¯-X¯T+

+1n⁢∑k=1K∑i∈CkXi-Xk¯⁢Xk¯-X¯T︸=0+1n⁢∑k=1K∑i∈CkXk¯-X¯⁢Xi-Xk¯T︸=0=

=1n∑k=1K∑i∈Ck(Xi-Xk¯)(Xi-Xk¯)T+∑k=1Knkn(Xk¯-X¯)(Xk¯-X¯)T=

=WC+BC.

∎

Wniosek 6.1

tr⁢T=tr⁢WC+tr⁢BC.

Czyli

zmienność całkowita= zmienność wewnątrzgrupowa + 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:

Co⁢p⁢t=minC⁡tr⁢WC.

tr⁢WC=1n⁢∑k=1K∑i∈Ck∑j=1pXi⁢j-Xjk¯2=1n⁢∑k=1K∑i∈CkXi-Xk¯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⁢…⁢K)

mk=argminm⁢∑i∈CkXi-m2=1nk⁢∑i∈CkXi

for (i in 1⁢…⁢n)

i∈Ck ⇔ k=argminl⁢Xi-ml2

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=di⁢ji,j=1n.

Algorytm K-medoidów

Wielokrotnie powtarzamy przy różnym podziale startowym C:

repeat

for (k in 1⁢…⁢K)

mk=argminm⁢∑i∈Ckdi⁢m # m jako mediana, należy do zbioru obserwacji

for (i in 1⁢…⁢n)

i∈Ck ⇔ k=argminl⁢di⁢ml

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=di⁢ji,j=1n odległość dwóch klastrów G i H od siebie przy założeniach

G,H⊆1,…,n⁢,⁢G∩H=∅,

możemy zdefiniować jako:

Single linkage

dG,H=mini∈G,j∈H⁡di⁢j.
Average linkage

dG,H=1G⁢H⁢∑i⁢jdi⁢j,

gdzie |⋅| oznacza liczność zbioru.
Complete linkage

dG,H=maxi∈G,j∈H⁡di⁢j.

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

Algorytm klasteryzacji hierarchicznej

C=1,2,…,n

for (l in 1:(n-1))

połącz najbliższe dwa klastry:

i*,j*=argmini,j:i<j⁢di⁢j

klastry i* oraz j* zastąp przez 0

odnów macierz odległości d0,k=min⁡di*⁢k,dj*⁢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 hk jako minimalną wysokość, na której obserwujemy podział na k części. Na przykład, na obrazku 6.2 dla k=5 h5≈0,2.

Separowalność dla klasteryzacji hierarchicznej definiujemy jako:

sep⁢k=1-hkh1.

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 s⁢e⁢p⁢k-s⁢e⁢p⁢k-1 było duże w stosunku do s⁢e⁢p⁢k+1-s⁢e⁢p⁢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=tr⁢T;

wk=minC⁡tr⁢WC,⁢k⁢ jest liczbą klastrów;

t=wk+wb.

Ponieważ wiemy, że:

1=wkt+bkt,⁢w1=t,⁢wn=0,

możemy zdefiniować separowalność jako:

sep⁢k=1-wkt.

Stwierdzenie 6.2

Separowalność dla klasteryzacji K-średnich jest niemalejącą funkcją k, liczby klastrów. Funkcja wk 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 K-średnich

Stwierdzenie 6.1

Wniosek 6.1

Algorytm K-średnich

6.2. Klasteryzacja K-medoidów

Algorytm K-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