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 (![]() ![]() |
![]() |
for (![]() ![]() |
![]() ![]() ![]() |
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 (![]() ![]() |
![]() |
for (![]() ![]() |
![]() ![]() ![]() |
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 ![]() ![]() |
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.