1

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

2

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

3

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

)

(

j

j

ij

ij

x

S

x

x

z

−

=

,

gdzie:

)

(x

S

- odchylenie standardowe,

__

x

średnia wartość zmiennej

Unitaryzacja. Cel: uzyskanie zmiennych o ujednoliconym zakresie

zmienności

{ }

{ }

{ }

ij

i

ij

i

ij

i

ij

ij

x

x

x

x

z

min

max

min

−

−

=

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

k

jk

ik

ij

x

x

d

1

2

)

(

Odległość Mińkowiskego

m

m

jk

p

k

iki

ij

x

x

d

1

1

)

|

|

(

−

=

∑

=

Odległość miejska

∑

=

−

=

p

k

jk

ik

ij

x

x

d

1

|

|

Odległość Mahalanobisa

∑∑

=

=

−

−

=

p

k

kl

jl

il

jk

ik

p

l

ij

s

x

x

x

x

d

1

1

)

)(

(

Odległość Czebyszewa

|}

{|

max

,...

1

jk

ik

p

k

ij

x

x

d

−

=

=

4

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

5

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

6

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