Segmentacja. Analiza skupień

Algorytm grupowania usiłuje podzielić cały zbiór danych na zgodne podgrupy, przy czym podobieństwo rekordów wewnątrz grup jest maksymalizowane, a podobieństwo do obiektów z poza grup minimalizowane

Założenia

• nie istnieją żadne warunki wstępne, na jakich musiałoby się opierać postępowanie segmentacyjne

• nie zakłada się żadnej informacji o właściwościach ani o liczbie grup

• podział jest dokonywany w całości w oparciu o informację zawartą w obiektach

1

Możliwy cel grupowania:

• Ekstrapolacja danych – ustalenie określonej struktury hierarchicznej np. w postaci drzewa binarnego

• Porównanie istniejącej typologii wynikającej z teorii (albo wcześniejszych badań) z wynikami empirycznymi

• Agregacja informacji w pojedynczych obiektach do poziomu grup.

Dzięki temu w dalszym etapie badań można się posługiwać grupami

– zamiast pojedynczymi obiektami

Metody hierarchiczne

Aglomeracyjne – punktem wyjścia jest sytuacja, gdzie każdy obiekt jest osobnym skupieniem. Dalej oblicza się odległość między wszystkimi obiektami i łączny dwa najbliższe. Cała procedura trwa, aż wszystkie obiekty będą w jednym skupieniu

Podziałowe – (algorytm działa w przeciwnym kierunku). Punktem wyjścia jest jedno skupienie, do którego należą wszystkie obiekty. W kolejnych krokach tworzy się grupy obiektów najbardziej się różniących. W końcu otrzymuje się pojedyncze obiekty

2

Etapy działania

1. Przekształcenie zmiennych – doprowadzenie zmiennych do porównywalności – normalizacja.

Typowe metody przekształcania zmiennych

Standaryzacja. Cel: jest otrzymanie zmiennych o jednostkowym odchyleniu standardowym

x − x

ij

j

z =

,

ij

S ( x )

j

__

gdzie: S( x) - odchylenie standardowe, x średnia wartość zmiennej Unitaryzacja. Cel: uzyskanie zmiennych o ujednoliconym zakresie zmienności

x − min x

ij

{ ij}

z =

ij

ma {

i

x x

− min x

ij }

{ ij}

i

i

2. Wybór miary podobieństwa, która pozwoli wyznaczyć macierz odległości obiektów

Typowe miary odległości (podobieństwa)

Odległość euklidesowa

p

d

( x

x

2

)

ij =

∑ ik − jk

k =1

Odległość Mińkowiskego

p

1

m

m

d = (∑| x − x | )

ij

iki

jk

k 1

=

Odległość miejska

p

d

| x

x |

ij = ∑

ik −

jk

k =1

Odległość Mahalanobisa

p

p

d

( x

x )( x

x ) s

ij =

∑∑

ik −

jk

il −

jl

kl

k =1 l =1

Odległość Czebyszewa

d = max{| x − x |}

ij

ik

jk

k = ,

1 ... p

3

3. Wyznaczenie macierzy odległości

Wybór najmniejszej wartości w macierzy odległości i utworzenie skupienia z jednostek, których ta najmniejsza odległość dotyczy.

Liczba obiektów w tym kroku zmniejszyła się z n do n-1.

4. i kolejne kroki….

Ponowne wyznaczenie macierzy odległości dla zredukowanego – o dokonane połączenie w kroku pierwszym – zbioru obiektów Liczba obiektów zmniejsza się o kolejną jednostkę.

Po n-tym powtórzeniu wszystkie badane jednostki będą w jednej grupie.

Metody wyznaczania kolejnych odległości

• Metoda najbliższego sąsiedztwa

• Metoda najdalszego sąsiedztwa

• Metoda średniej

• Metoda mediany

• Metoda centroidalna

• Metoda Warda

4

Metoda najbliższego sąsiedztwa (pojedyncze wiązanie)

• odległość między dwoma skupieniami to najmniejsza z odległości pomiędzy ich elementami;

Metoda najdalszego sąsiedztwa (pełne wiązanie)

• odległość między dwoma skupieniami to największa odległość między ich elementami

Metoda średniej

• Odległość między dwoma skupieniami – średnia z odległości między jednostkami jednego i drugiego skupienia

Metoda mediany

• Odległość między dwoma skupieniami – mediana z odległości między jednostkami jednego i drugiego skupienia

Metoda centroidalna

• W każdym kroku po utworzeniu skupienia wyznacza się nową macierz odległości na podstawie uśrednionych wartości cech (stanowiących kryteria segmentacji) tych jednostek, które połączono w skupienia

Metoda Warda (preferowana)

• Kryterium grupowania jednostek: minimum zróżnicowania wartości cech, względem wartości średnich skupień tworzonych w kolejnych krokach

• Gdy powiększymy jedno ze skupisk, wówczas wariancja wewnątrzgrupowa (liczona jako kwadraty odchyleń od średnich w skupisku) rośnie; metoda polega na takiej fuzji skupisk, aby nastąpił

jak najmniejszy przyrost wariancji dla danej iteracji

5

Metody optymalnego podziału. Metoda k – średnich W ramach metody algorytm dzieli zbiór danych na ustaloną liczbę skupień optymalizując pewne kryterium celu – np. podobieństwo wewnątrz skupień.

Etapy działania:

• Ustalenie a priori docelowej liczby segmentów

• Dla ustalonej liczby segmentów dokonuje się rozdziału jednostek według wstępnie wybranych przedstawicieli każdego segmentu

• Zasada rozdziału: kryterium najmniejszej odległości względem wybranych przedstawicieli

Krok 1. Wybór przedstawicieli segmentów

Krok 2. Wyznaczenie środków ciężkości dla utworzonych skupień

• Środki ciężkości – wartości średnie zmiennych, które stanowią podstawę grupowania – wyznaczone dla tych jednostek, które tworzą grupę

Krok 3. Określenie odległości każdej jednostki od wszystkich wyznaczonych środków ciężkości. Skorygowanie składu grup Po wykonaniu segmentacji należy ocenić jej jakość oraz dokonać profilowania utworzonych klas

6