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