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 będziemy szukać optymalnego podziału na części, czyli szukać podziału na grup:
parami rozłącznych o licznościach odpowiednio . Będziemy używać oznaczenia na podmacierz o indeksach z ,
Klasteryzacji -średnich używamy, gdy znamy ilość grup , na ile chcemy podzielić dane. Zdefiniujmy następujące macierze:
Macierz wariancji całkowitej:
nie zależy od podziału , var oznacza próbkową macierz kowariancji.
Zmienność całkowita to ślad macierzy T: .
Macierz wariancji wewnątrzgrupowej:
zależy od podziału .
Zmienność wewnątrzgrupowa to ślad macierzy : .
Macierz wariancji międzygrupowej:
zależy od podziału .
Zmienność międzygrupowa to ślad macierzy : .
oznacza -wymiarowy wektor średnich kolumnowych dla macierzy , a -wymiarowy wektor średnich kolumnowych dla całej macierzy . nazywane są centroidami, redukcja wymiaru polega na zastępowaniu grup danych przez ich centroidy.
Czyli
Ideą klasteryzacji -średnich jest minimalizacja po podziałach zmienności wewnątrzgrupowej, co jest jednoznaczne z maksymalizcją zmienności międzygrupowej:
Idea zachłannego algorytmu -średnich (zależnego od wybranego podziału startowego ), z którego można korzystać np. w programie wygląda następująco:
Wielokrotnie powtarzamy przy różnym podziale startowym : |
repeat |
for ( in ) |
for ( in ) |
until warunek stopu |
Przykładowy wynik algorytmu klasteryzacji -średnich znajduje się na rysunku 6.1.
Klasteryzacja -medoidów jest podobna do klasteryzacji -ś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 .
Wielokrotnie powtarzamy przy różnym podziale startowym : |
repeat |
for ( in ) |
# m jako mediana, należy do zbioru obserwacji |
for ( in ) |
until warunek stopu |
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 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 odległość dwóch klastrów i od siebie przy założeniach
możemy zdefiniować jako:
Single linkage
Average linkage
gdzie oznacza liczność zbioru.
Complete linkage
Ideę algorytmu klasteryzacji hierarchicznej możemy zapisać jako:
for (l in 1:(n-1)) |
połącz najbliższe dwa klastry: |
klastry oraz zastąp przez 0 |
odnów macierz odległości |
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.
Oznaczmy jako minimalną wysokość, na której obserwujemy podział na części. Na przykład, na obrazku 6.2 dla .
Separowalność dla klasteryzacji hierarchicznej definiujemy jako:
Z definicji separowalności możemy wywnioskować następujące własności:
separowalność przyjmuje wartości z przedziału ;
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 , żeby było duże w stosunku do . 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 . Przykładowo, na rysunku 6.3 optymalnym wyborem jest ( też jest dobrym wyborem, chociaż dążymy do tego aby jak najbardziej zredukować wymiar danych, czyli wybrać jak najmniejsze ).
Można zdefiniować także separowalność dla klasteryzacji -średnich. Oznaczmy:
Ponieważ wiemy, że:
możemy zdefiniować separowalność jako:
Separowalność dla klasteryzacji -średnich jest niemalejącą funkcją , liczby klastrów. Funkcja jest więc nierosnąca ze względu na liczbę klastrów.
Jako praca domowa.
∎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.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
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.