Grupowanie danych:   definicja i cel

Grupowanie 

oznacza 

grupowanie 

rekordów, 

obserwacji  lub  przypadków  w  klasy  podobnych 
obiektów.  Grupa  jest  zbiorem  rekordów,  które  są 
podobne  do  siebie  nawzajem  i  niepodobne  do 
rekordów z innych grup.
Grupowanie  różni  się  od  klasyfikacji  tym,  że  w 
przypadku grupowania nie ma zmiennej celu. Zadanie 
grupowania  nie  próbuje  klasyfikować,  szacować  lub 
przewidywać  wartości  zmiennej  celu.  Zamiast  tego, 
algorytm  grupowania  próbuje  podzielić  cały  zbiór 
danych  w  stosunkowo  zgodne  podgrupy  lub  grupy, 
przy czym podobieństwo rekordów wewnątrz grup jest 
maksymalizowane,  a  podobieństwo  do  rekordów 
spoza grupy minimalizowane.

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie  jest  często  wykorzystywane  jako  krok 
wstępny do procesu eksploracji danych, z wynikowymi 
grupami  użytymi  jako  dane  wejściowe  do  innej 
techniki, takiej jak sieci neuronowe. Z powodu dużego 
rozmiaru  wielu  baz  danych,  często  jest  korzystnie 
najpierw 

przeprowadzić 

analizę 

skupień, 

aby 

zredukować przestrzeń przeszukiwań dla algorytmów.

Grupowanie danych:   definicja i cel

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   definicja i cel

Cel grupowania:

•

  znajdowanie naturalnego podziału danych na 

istotne 

podgrupy

•

  dekompozycja danych na części, które są 

łatwiejsze do 

opisania – bardziej jednolite

•

  poznanie rozkładu przykładów (danych)

•

  wyróżnienie przypadków, tych, które można 

uznać za 

typowe i tych, które za wyjątki

VIII         EKSPLORACJA DANYCH

•

  uzupełnianie brakującej informacji

 

 

Grupowanie danych:   definicja i cel

Przykłady zadań grupowania w badaniach:

Przykłady zadań grupowania w biznesie:

•

  namierzenie grupy potencjalnych klientów 

pewnego  produktu z niszy rynkowej 
wyprodukowanego przez 

małą firmę z małym 

budżetem reklamowym

•

  podział zachowań finansowych na korzystne i 

niepewne  w celu kontroli obliczeń

•

  redukcję wymiarów, gdy zbiór ma setki atrybutów

•

  grupowanie ekspresji genów, gdzie bardzo dużo 

genów może wykazywać podobne zachowanie

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   definicja i cel

Przykłady zadań grupowania w marketingu:

Przykłady zadań grupowania w geodezji i kartografii:

•

  identyfikacja obszarów o podobnych glebach na 

podstawie  zdjęć z obserwacji Ziemi

•

  lokalizacje epicentrów trzęsień Ziemi, na 

podstawie  zaobserwowanych defektów 
kontynentów

•

  identyfikacja grup ubezpieczonych w 

towarzystwach 

ubezpieczeniowych generujących 

wysokie koszty 

napraw

•

  rozpoznanie potrzeb rozwojowych miasta, na 

podstawie grupowania domów o określonej wartości, 
lokalizacji, itp.

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   

metody

•

  metody hierarchiczne, polegają na łączeniu 

pojedynczych elementów, wg założonego kryterium 
odległości (elementy podobne)

•

  metody niehierarchiczne, polegają na wstępnym 

podzieleniu zbioru na określoną liczbę klas, a następnie 
modyfikowaniu podziału (przez przenoszenie elementów 
z grupy do grupy) prowadzącym do poprawy tego 
podziału

Metody grupowania:

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   

metody hierarchiczne

•

  początkowo każda obserwacja traktowana jest jako 

osobne 

skupienie

•

  wyniki przedstawiane są za pomocą drzewka połączeń

Uogólniony algorytm metod hierarchicznych:

•

  następnie tworzona jest macierz odległości pomiędzy 

kolejnymi obserwacjami

•

  określa się odległości pomiędzy poszczególnymi 

skupieniami 

 i na ich podstawie tworzy się nowe 

skupienia obiektów

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   

metody hierarchiczne

•

  metoda najbliższego sąsiada

•

  metoda środka ciężkości

Wybór metody aglomeracji:

•

  metoda najdalszego sąsiada

•

  metoda średniej grupowej

•

  metoda mediany (ważonych środków 

ciężkości)

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   

metody hierarchiczne

•

  metoda najbliższego sąsiada

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   

metody hierarchiczne

•

  metoda najbliższego 

sąsiada

VIII         EKSPLORACJA DANYCH

•

  metoda najdalszego sąsiada

 

 

Grupowanie danych:   metody hierarchiczne

Wady metod hierarchicznych

•

  brak oczywistego kryterium stopu dla 

uzyskania względnie jednorodnych skupień 

•

  otrzymane raz skupienie nie może być 

rozłączone, czyli ewentualny wcześniejszy błąd 
nie może być skorygowany

•

 w metodach aglomeracyjnych nie jest znana z 

góry ani liczba grup (skupień) ani liczba 
obiektów w poszczególnych grupach

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   algorytm k - średnich

Algorytm k – średnich:

procedura 

postępowania

• wybieramy losowo tyle punktów w przestrzeni, na ile 
grup  dzielimy zbiór danych

• obliczamy odległości wszystkich elementów zbioru od 

wylosowanych punktów

• grupujemy zgodnie z bliskością elementów zbioru od 

punktów początkowych

• obliczamy centroidy grup jako średnie elementów 
grupy

• powtarzamy punkty 2 i 3 aż do osiągnięcia 
stabilności

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   algorytm k - średnich

X

Y

1

1

1

2

1

3

2

1

3

3

4

3

4

2

5

3

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   algorytm k - średnich

Wskaźnik jakości algorytmu k - średnich

•

  ZPG – zmienność pomiędzy grupami

•

  ZWG – zmienność wewnątrz grupy

W = 

ZPG

ZWG

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   algorytm k - średnich

Wskaźnik jakości algorytmu k - średnich

W = 

ZPG

ZWG

c

1

c

2

ZPG = d (c

1

, c

2

)

ZWG = 

 

Σ

  

Σ d(m

ij

, c

i

) 

i=1 j

k

m

15

m

14

m

13

m

12

m

11

m

21

m

26

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   algorytm k - średnich

Zalety algorytmu k - średnich

•

  sprawny – η(nkt), gdzie n jest liczbą 

obserwacji, k  jest liczbą klasterów, a t jest 
liczbą iteracji,  zazwyczaj k, t << n

•

  obliczenia kończą się po osiągnięciu 

minimum lokalnego

•

  łatwy w zaprogramowaniu

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   algorytm k - średnich

Wady algorytmu k - średnich

•

  możliwość stosowania jedynie do danych, 

dla  których możliwe jest obliczenie średnich; 

wyłącza to zbiory z danymi 

kategorycznymi

•

  konieczność wstępnego określenia liczby k 

(liczby 

grup) przed rozpoczęciem 

modelowania

•

  niezdolność do radzenia sobie z danymi 

zaszumionymi i z danymi odstającymi

VIII         EKSPLORACJA DANYCH

 

 

Wady algorytmu k - średnich

Grupowanie danych:   algorytm k - średnich

•

  nie do zastosowania w przypadku, gdy modelowana 

grupa ma kształt wklęsły

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   definicja i cel

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   zastosowanie

0

5

10

15

20

25

30

35

300

400

500

600

700

800

900

wytrzymałość [MPa]

w

yd

łu

że

ni

e 

[%

]

10
11

31
42
43
44

46
47
49

sc

VIII         EKSPLORACJA DANYCH

 

 

VIII         EKSPLORACJA DANYCH

Grupowanie danych:   zastosowanie

0

5

10

15

20

25

30

35

300

400

500

600

700

800

900

wytrzymałość [MPa]

w

yd

łu

że

ni

e 

[%

]

10
11
31
42
43
44
46
47
49
sc

Nr 

wyt

C %

Mn 

%

Si %

P %

S %

Cr %

Ni %

Cu %

Mg 

%

Rm

A5

HB

1279,

1

3,84 0,17

2,50

0,05

0,01

0,04

0,02

0,06

0,03

6

747

11,4

248

2039,

1

3,82 0,09

2,50

0,05

7

0,00

8

0,02

0,00

0,03

0,03

7

382

  7,1

156

2036,

1

3,76 0,11

2,54

0,05

7

0,01

1

0,03

0,00

0,04

0,04

0

490

29,0

159

2036,

2

3,81 0,12

2,58

0,05

9

0,01

4

0,03

0,01

0,04

0,04

1

490

29,0

159

średn

i

3,78 0,15

2,53

0,05

0,01

0,03

0,01

0,06

0,03

6

460,

9

20,4

163,

7

0114,

1

3,71 0,15

2,43

0,07

0,01

0,02

0,01

0,11

0,03

6

459

20,7

163

1063,

1

3,87 0,14

2,54

0,05

0,01

0,02

0,01

0,04

0,03

5

459

20,7

156

1063,

2

3,86 0,12

2,49

0,05

0,01

0,02

0,01

0,04

0,03

9

459

20,7

156

1232,

1

3,76 0,18

2,55

0,04

0,01

0,04

0,02

0,17

0,03

2

459

20,7

156

1232,

2

3,79 0,18

2,56

0,04

0,01

0,04

0,02

0,17

0,03

4

459

20,7

156

 

 

Grupowanie danych:   

podsumowanie

Uwaga: niezależnie od zastosowanej metody 
wszystkie podziały będą się mieścić pomiędzy 
dwoma skrajnymi przypadkami:

• skrajny przypadek: wszystkie obiekty rozkładają się 
tak, że uzyskujemy skupienia jednoelementowe (zbiór 
n elementów dzielony jest na n skupień 
jednoelementowych)

• skrajny przypadek: zbiór elementów jest tak 
jednorodny, że nie możliwe jest rozłożenie jego na 
podzbiory, tzn. otrzymujemy jedno skupienie n-
elementowe

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   

podsumowanie

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   

podsumowanie

VIII         EKSPLORACJA DANYCH

 

 

Grupowanie danych:   

podsumowanie

VIII         EKSPLORACJA DANYCH