HODNOCENÍ KVALITY SHLUKŮ

HODNOCENÍ KVALITY SHLUKŮ Hana Řezanková Vysoká škola ekonomická v Praze http://nb.vse.cz/~rezanka Analýza dat 2008/II

1

Obsah  Principy metod shlukové analýzy  Shlukování objektů (vektorů pozorování)  Porovnávání se známým zařazením objektů  Statistické testy  Hodnocení disjunktního shlukování  Hodnocení fuzzy shlukování  Možnosti programových systémů

Analýza dat 2008/II

2

Metody shlukové analýzy Literatura – knihy:  Řezanková, H., Húsek, D., Snášel, V.: Shluková analýza dat. Professional Publishing, Praha 2007, 196 s.  Řezanková, H.: Analýza dat z dotazníkových šetření. Professional Publishing, Praha 2007, 212 s.  Hebák, P. a kol.: Vícerozměrné statistické metody [3]. 2. vyd. Informatorium, Praha 2007. 272 s. Analýza dat 2008/II

3

Metody shlukové analýzy Literatura – sborníky:  Řezanková, H.: Klasifikace pomocí shlukové analýzy. Sborník přednášek ze semináře Analýza dat 2003/II, TriloByte Statistical Software, s. 119–135.  Řezanková, H.: Shlukování a velké soubory dat. Sborník přednášek ze semináře Analýza dat 2004/II, TriloByte Statistical Software, s. 7–19. Analýza dat 2008/II

4

Metody shlukové analýzy Literatura – sborníky:  Řezanková, H.: Shluková analýza kategoriálních dat. Sborník přednášek ze semináře Analýza dat 2007/II, TriloByte Statistical Software, s. 89–102.


5

Metody shlukové analýzy Shluková analýza je postup formulovaný jako procedura, pomocí níž objektivně seskupujeme jedince do skupin na základě jejich podobnosti a odlišnosti (zkráceně R. C. Tryon, 1939). Cílem shlukové analýzy je nalézt skupiny objektů (v širším smyslu) tak, aby dva objekty z téže skupiny si byly podobnější než dva objekty z různých skupin. Analýza dat 2008/II

6

Metody shlukové analýzy Vstupní data:  m-rozměrná pozorování (matice vzorů – pattern matrix) matice X, prvky xil  matice vzdáleností/podobností

(matice blízkostí - proximity matrix)

 kontingenční tabulka

(tabulka četností)

X

/

m proměnných (znaků) 1. znak

2. znak

1. objekt

2. objekt

1. objekt 2. objekt …

1. objekt 2. objekt …

Y

1. kategorie

2. kategorie

…

1. kategorie 2. kategorie …


7

Metody shlukové analýzy Značka

X1

X2

X3

X4

X5

X6

X7

Bonaqua Dobrá voda Evian Hanácká kyselka Korunní Mattoni Ondrášovka Poděbradka Poděbradka PL Rajec Toma Natura Valvert Vittel

0,02 0,10 0,05 2,68 1,07 0,69 0,27 3,39 4,62 0,01 0,01 0,02 0,07

0,04 0,64 0,07 1,14 1,72 1,23 0,11 3,41 4,10 0,03 0,17 0,01 0,34

1,37 0,32 0,80 2,39 1,03 0,83 0,63 1,62 2,26 0,81 0,21 0,07 0,67

0,69 0,10 0,87 3,02 0,97 0,98 0,21 1,59 1,85 0,67 0,29 0,75 1,02

0,03 0,01 0,05 2,26 0,14 0,13 0,07 4,64 5,48 0,02 0,07 0,05 0,05

0,40 0,07 0,29 0,01 1,72 1,29 0,38 2,30 2,38 0,29 0,36 0,51 2,99

0,64 0,19 0,62 2,84 1,12 0,96 1,19 1,68 2,40 0,39 0,17 0,35 0,45


8

Metody shlukové analýzy

X1 X2 X3 X4 X5 X6 X7

kationty sodné (Na+) kationty draselné (K+) kationty hořečnaté (Mg2+) kationty vápenaté (Ca2+) anionty chloridové (Cl-) anionty síranové (SO42-) anionty hydrogenuhličitanové (HCO3-)


9

Metody shlukové analýzy Klasifikace tradičních metod:  metody rozkladu (partitioning) pro disjunktní shluky (se zadaným počtem shluků) iterativní relokační (přemísťovací) algoritmy  metody matematického programování  grafické zobrazování pomocí minimální kostry  hybridní klasifikace  metody založené na hustotě 

 metody pro překrývající se shluky Analýza dat 2008/II

10

Metody shlukové analýzy Klasifikace tradičních metod:


11


2 1

(PAM)

0

k-medoidů

-1

S-PLUS

-2

Component 2

3

Klasifikace tradičních metod:

-2

0

2

4

Component 1 These two components explain 90.43 % of the point variability.


12

Metody shlukové analýzy Klasifikace tradičních metod:  metody rozkladu 





pevné shlukování

shluky

1

0

0

0

0

1

1

0

0

…

…

…

objekty 0,4

0,3

0,3

0,2

0,3

0,5

0,8

0,1

0,1

…

…

…

0,4

0,3

0,3

0,2

0,3

0,5

1

0

0

…

…

…

fuzzy shlukování částečné fuzzy shlukování Analýza dat 2008/II

13

Metody shlukové analýzy Klasifikace tradičních metod: *** Fuzzy Partitioning *** Membership coefficients: [,1] Bonaqua 0.90683520 Dobrá voda 0.89786306 Evian 0.93671025 Hanácká kys. 0.37934570 Korunní 0.72712138 Martini 0.82509199 Ondrášovka 0.90356517 Poděbradka 0.08990355 Poděbradka PL 0.11051759 Rajec 0.93996091 Toma Natura 0.92084109 Valvert 0.91850890 Vittel 0.74303721

[,2] 0.09316480 0.10213694 0.06328975 0.62065430 0.27287862 0.17490801 0.09643483 0.91009645 0.88948241 0.06003909 0.07915891 0.08149110 0.25696279


fuzzy (FANNY) S-PLUS

14

Metody shlukové analýzy Klasifikace tradičních metod: fuzzy (FANNY)

*** Fuzzy Partitioning *** Closest hard clustering:

Bonaqua Dobrá voda Evian Hanácká kys. Korunní Mattoni Ondrášovka Poděbradka 1 1 1 2 1 1 1 2 Poděbradka PL Rajec Toma Natura Valvert Vittel 2

1

1

1

1


15

Metody shlukové analýzy Metody hierarchické shlukové analýzy:  monotetické – divizivní (S-PLUS)  polytetické aglomerativní  divizivní (S-PLUS) 

 modifikované metody  dvourozměrné shlukování (STATISTICA, SYSTAT)  dvoukroková shluková analýza (SPSS)  ROCK (RObust Clustering using linKs) Analýza dat 2008/II

16

Analýza dat 2008/II Vittel

Poděbradka PL

Poděbradka

Mattoni

Korunní

Valvert

Toma Natura

Dobrá voda

Ondrášovka

Rajec

Evian

Bonaqua

0

2

Hanácká kys.

4

Height 6

8


Metody hierarchické shlukové analýzy: divizivní

(DIANA)

S-PLUS

17

Metody shlukové analýzy Metody hierarchické shlukové analýzy: Stromový diagram pro 13 případů Úplné spojení Euklidovské vzdálenosti

aglomerativní

Bonaqua Evian Rajec

(AGNES)

Ondrášovka Dobrá voda Toma Natura Valvert Korunní

STATISTICA

Mattoni Vittel Hanácká kys. Poděbradka Poděbradka PL 0

2

4

6

8

10

Vzdálenost spojení


18

Metody shlukové analýzy Metody hierarchické shlukové analýzy: Výsledky dvojrozměrného spojování Bonaqua Valvert

dvourozměrné shlukování

Evian Rajec Vittel Dobrá vo Toma Nat

STATISTICA

Ondrášov Korunní Mattoni Hanácká

5 4 3 2 1

Poděbrad Poděbrad Na+

Mg2+

HCO3-

Ca2+

K+

Cl-


SO42-

19

Symbolika (značení) Proměnná Objekt

1.

2.

…

m

1. …

n

xil , i = 1, 2, …, n l = 1, 2, …, m k … počet shluků

Ch … h-tý shluk Dij … vzdálenost i-tého a j-tého objektu Dhh … vzdálenost h-tého a h-tého shluku

uih … míra příslušnosti i-tého objektu k h-tému shluku Analýza dat 2008/II

20

Symbolika (značení) Dij Dij  Dij  q

Dhh

… vzdálenost i-tého a j-tého objektu m

2 ( x  x )  il jl  x i  x j

euklidovská vzdálenost

l 1 m

 | xil  x jl |q

Minkowského vzdálenost

l 1

… vzdálenost h-tého a h-tého shluku

- maximum ze všech vzdáleností dvojic z různých shluků - minimum ze všech vzdáleností dvojic z různých shluků - průměr ze všech vzdáleností dvojic z různých shluků - vzdálenost centroidů (vektorů průměrů jednotl. proměnných) Analýza dat 2008/II

21

Porovnání s očekávaným zařazením objektů do shluků  Konfúzní matice  Entropie  Čistota (purity)  Přesnost, pokrytí a F-míra  Vzájemná informace (mutual information)  Rozdílnost informace (variation of information)  Randova statistika a Jaccardův koeficient


22

Porovnání s očekávaným zařazením objektů do shluků  Konfúzní matice

C … struktura jako výsledek shlukování P … předpokládaná (známá) struktura předpokládáme, že počet shluků v C i P je stejný, přiřadíme k sobě shluky, které obsahují co nejvíce stejných objektů, tyto počty zapíšeme na diagonálu konfúzní matice a označíme nhh k

MD 

n   nhh h 1

n

míra nesouhlasu (hodnoty blízké 1 indikují vysoký stupeň nesouhlasu) Analýza dat 2008/II

23

Porovnání s očekávaným zařazením objektů do shluků  Entropie k

nij

j 1

ni

H i  

ln

nij ni

entropie i-tého shluku

‹0; lnk›

ni … počet prvků v i-tém shluku struktury C nij … počet prvků z i-tého shluku C, které jsou v j-tém shluku P k

H (C )   i 1

ni Hi n

‹0; lnk› entropie struktury C (0 indikuje identické struktury)


24

Porovnání s očekávaným zařazením objektů do shluků  Čistota (purity) n n  pi  max  i1 ,, ik   ni   ni k

ni p (C )   pi i 1 n

čistota i-tého shluku

‹1/k; 1›

čistota struktury C (1 indikuje optimální strukturu)


25

Porovnání s očekávaným zařazením objektů do shluků  Přesnost a F-míra

(pojmy z oblasti vyhledávaní informací – IR) Pij  Rij  Fij  2

nij

koef. přesnosti (precision)

ni nij

koef. úplnosti (recall) - pokrytí

nj Pij  Rij Pij  Rij

2

nij ni  n j

F-míra


26

Porovnání s očekávaným zařazením objektů do shluků  Vzájemná informace (mutual information) k

k

MI   i 1 j 1

nij n

ln

n  nij ni n j

0 … není žádný vztah mezi strukturami

 Rozdílnost informace (variation of information) VI  [ H (C )  MI ]  [ H ( P )  MI ]


27

Porovnání s očekávaným zařazením objektů do shluků C … struktura jako výsledek shlukování P … předpokládaná (známá) struktura a … počet párů objektů ve stejném shluku v C i P b … počet párů ve stejném shluku v C, ale ne v P c … počet párů ve stejném shluku v P, ale ne v C d … počet párů v různých shlucích v C i v P

n ( n  1) M  abcd  2 Analýza dat 2008/II

28

Porovnání s očekávaným zařazením objektů do shluků R

ad M

a J abc FM 

a a  ab ac

Randův koeficient (prosté shody) Jaccardův koeficient Folkesův a Mallowsův index (Ochiaiův)

hodnoty z intervalu od 0 do 1 Analýza dat 2008/II

29

Statistické testy  Testy absence struktury

testy náhodnosti ve vstupní datové matici  testy náhodnosti v matici vzdáleností 

 Testy hierarchické struktury

metody stability (modifikování dat)  redukce objektů, modifikace množiny proměnných 

 Testy homogenity shluku (Bealeův test)  Testy počtu shluků (metody založené na hustotě) Analýza dat 2008/II

30

Bealeův test W1  W2 W2 F n 1 2 m 2 1 n2  W1 součet čtvercových vnitroshlukových vzdáleností

pro sledovaný shluk  W2 součet čtvercových vnitroshlukových vzdáleností, pokud by shluk byl optimálním způsobem rozdělen  Statistika F má F rozdělení s počty stupňů volnosti m a (n – 2)m. Analýza dat 2008/II

31

Testy o počtu shluků u metod založených na hustotě Posloupnost testů: H0: počet shluků je hodnota k nebo menší H1: počet shluků je větší než k Zjištění počtu shluků je součástí metod, uživatel nezadává počet shluků, ale zadává parametry pro konkrétní algoritmus, na němž výsledný počet závisí (SAS, SYSTAT)


32

Využití korelačního koeficientu  Hubertova  statistika X … vstupní matice D … matice vzdáleností (n x n) Y … matice n x n 1, Yij   0

g : X  {1, 2, …, k}.

jestliže g ( x i )  g ( x j ), jinak

pro i, j  1, 2, ..., n

n 1 n 2 DijYij    n( n  1) i 1 j i 1


33

Využití korelačního koeficientu  Hubertova  statistika n 1 n 2 DijYij    n( n  1) i 1 j i 1

 normalizovaná  statistika n 1

2  n( n  1)

n

  ( Dij   D )  (Yij  Y ) i 1 j i 1

n 1 n 2 D  Dij   n( n  1) i 1 j i 1

 D Y

hodnoty od –1 do 1

n 1 n 2 Y  Yij   n( n  1) i 1 j i 1


34

Využití korelačního koeficientu  Kofenetický korelační koeficient X … vstupní matice D … matice vzdáleností (n x n) C … matice n x n; úroveň kdy se prvky poprvé vyskytnou ve stejném shluku

rDC 

n 1 n 2 Dij Cij   D  C   n( n  1) i 1 j i 1

 2 2 2 2   2 2  Dij   D    Cij   C   ( 1 ) ( 1 ) n n n n      

hodnoty od –1 do 1

hodnocení metod hierarchického shlukování Analýza dat 2008/II

35

Využití korelačního koeficientu  Modifikovaná Hubertova  statistika 2 n 1 n DijQij    n( n  1) i 1 j i 1 Qij … vzdálenost centroidů shluků, v nichž se nachází i-tý a j-tý objekt

 normalizovaná modifikovaná  statistika


36

Indexy pro hodnocení shluků 1. R-square (RSQ) index – SAS n

I RSQ

ST  S W   ST

m

k

 ( xil  xl )   2

i 1 l 1



m

2 ( x  x )  il hl

h 1 x i Ch l 1

n

m

2 ( x  x )  il l i 1 l 1

2. Semipartial R-squared (SPRSQ) index – SAS

I SPRSQ ( k )  I RSQ ( k  1)  I RSQ ( k ) Analýza dat 2008/II

37

Indexy pro hodnocení shluků

SAS Analýza dat 2008/II

38

Indexy pro hodnocení shluků 3. Pseudo (Calinski-Habarasz) F index

– SAS (PSF), SYSTAT (CHF) I CHF

SB (n  k )  SB  k 1  SW ( k  1)  S W nk

4. Pseudo T-kvadrát statistika – SAS (PST2)

SYSTAT (PTS)

I PTS

Bhh  Wh  Wh n h  n h  2


39



40

Indexy pro hodnocení shluků Minerální vody


41


SAS


42


SAS


43


SYSTAT Analýza dat 2008/II

44

Indexy pro hodnocení shluků 5. Root Mean Square Standard Deviation

(RMSSTD) index – SYSTAT I RMSSTD 

SW m( n  k )


45

Indexy pro hodnocení shluků 6. Daviesův-Bouldinův (DB) index – SYSTAT k

I DB 

 Rh h 1

k

 s D ,h  s D ,h   Rh  max   h , h  h D hh   

 D 2 (x i , x h )

s D ,h 

x i Ch

nh

Dhh  D( x h , x h )

D(.,.) je Minkowského vzdálenost Analýza dat 2008/II

46

Indexy pro hodnocení shluků 7. Dunnův index – SYSTAT (též separační index)   Dhh   I D  min  min  1 h  k 1 h k max diam l   1l  k   D hh  

min

x i Ch , x j Ch 

D(x i , x j )

diam h  max D ( x i , x j ) x i ,x j Ch


47

Indexy pro hodnocení shluků Alternativní Dunnův index (AD)

I AD

  min D ( x j , x h )  D ( x i , x h )   x C , x C   min  min i h j h  1 h  k 1 h k     max  max D ( x i , x j )  1l  k  x i ,x j Ch   

vysoké hodnoty – kompaktní a dobře oddělené shluky


48

Indexy pro hodnocení shluků Indexy platnosti (SD, S_Dbw ) sW

k

σ 2 (X h )

průměrná vnitroshluková charakteristika

1   2 k h 1 σ ( X )

 ( xil  xhl )

 hl2 

sB 

max D( x h , x h )

1 h ,h k

min D( x h , x h

1 h ,h k

k

 ) h 1

 l2 

x i Ch

nh

1 k

n

2

 D ( x h , x h )

 ( xil  xl ) 2 i 1

n

úplná separace

h1

D(.,.) je euklidovská vzdálenost

nejlepší je minimální hodnota (ze součtu) Analýza dat 2008/II

49

Indexy pro hodnocení shluků Index průměrné kompaktnosti 2

I AC

 xil  x jl    m  k Rl  n   h   h 1 n x i ,x j Ch l 1 n h ( n h  1)

Rl … variační rozpětí

k porovnání různých metod nejlepší je minimální hodnota princip lze použít i pro kategoriální proměnné


50

Indexy pro hodnocení shluků Randův index k1 k 2

1 2 IR 1  n  hh n   h 1 h1   2

2 2 k1 k2 k2 k1       1    nhh      nhh     n   h 1  h  h1 h    2  2

nhh′ je počet objektů v průniku shluků Ch a C′h′ C′ … shluk vytvořený jinou metodou než C 0 … zcela rozdílné shluky 1 … shluky jsou identické Analýza dat 2008/II

51

Koeficienty pro hodnocení shluků v systému S-PLUS (PAM, CLARA, FANNY) 8.

Obrysový koeficient (silhouette coefficient)

i   i i  maxi ,  i  i 

 Dij

jCh

nh  1

  Dij    jC h i  min h h   n  h    n



i i 1

n

Rajec Evian Toma Valve Dobrá Bonaq Ondrá Korun Hanác

FANNY

Vitte Matto Poděb Poděb -0.2

0.0

0.2

0.4

0.6

0.8

1.0

Silhouette width Average silhouette width : 0.45


52

Koeficienty pro hodnocení shluků v systému S-PLUS (PAM, CLARA, FANNY) Obrysový koeficient (silhouette coefficient)

nh  1




i i 1

n

3 2 1

jCh

0

 Dij

-1

i 

i   i maxi ,  i 

-2

i 

Component 2

8.

-2

0

2

4



53



i   i i  maxi ,  i  i 

 Dij

jCh

nh  1




i i 1

n

Rajec Toma Evian Valve Dobrá Ondrá Bonaq Matto Vitte

PAM

Korun Hanác Poděb Poděb 0.0

0.2

0.4

0.6

0.8

1.0



54

Koeficienty pro hodnocení shluků v systému S-PLUS (PAM, CLARA, FANNY) Obrysový koeficient (silhouette coefficient) i   i maxi ,  i 

2

i 

3

8.

  Dij    jC h i  min h h   n  h   

1 0

nh  1

-1

jCh

Component 2

i 

 Dij

n



i i 1

n

-2

0

2

4



55



i   i i  maxi ,  i 

Rajec Evian Toma Valve

i 

 Dij

jCh

Ondrá

nh  1

Dobrá




Bonaq

i i 1

n

Matto Vitte

PAM, PAM FANNY

Korun Poděb Poděb Hanác 0.0

0.2

0.4

0.6

0.8

1.0



56

Kritéria pro hodnocení shluků v systému SPSS (dvoukroková SA) 9. Schwarzovo bayesovské informační kritérium

BIC (Bayesian Information Criterion) k

I BIC  2  h  wk ln( n ) h 1

10. Akaikovo informační kritérium

AIC (Akaike Information Criterion) k

I AIC  2  h  2 wk h 1

 (1) m   1 2 2  h   nh   ln( sl  shl )   H hl  , wk  k  2m   ( K l  1)    l 1 2 l 1   l 1   (1) m

m( 2 )


(2)

57

Kritéria pro hodnocení shluků v systému SPSS (dvoukroková SA)


58

Kritéria pro hodnocení shluků v systému SPSS (dvoukroková SA)


59

Koeficienty pro hodnocení výsledků fuzzy shlukové analýzy (S-PLUS) 11. Dunnův koeficient rozkladu

(Partition Coefficient) – PC index (Bezdek) I PC

1 n k 2   uih n i 1 h 1

‹1/k; 1›

1 I PC  kI PC  1 k   I PC  1 k 1 1 k I PC ( k *)  max I PC ( k ) 2 k  n 1

Coefficients: dunn_coeff normalized 0,7729203 0,5458407

‹0; 1›

2 shluky


3 shluky


4 shluky


60

Indexy pro hodnocení výsledků fuzzy shlukové analýzy 12. Entropie rozkladu

(Partition Entropy) – PE index (Bezdek) I PE

1 n k    uih ln(uih ) n i 1 h 1

‹0; lnk›

I PE ( k *)  min I PE ( k ) 2 k  n 1


61

Indexy pro hodnocení výsledků fuzzy shlukové analýzy 13. Xieův a Beniův (XB) index

separační (S) index n

I XB 

k

 i 1 h 1

n

uih2 D 2 ( x i , x h )

n min D 2 ( x h , x h ) 1 h  h  k



k

 uih2 x i  x h

2

n min x h  x h

2

i 1 h 1

1 h  h k

I XB ( k *)  min I XB ( k ) 2 k  n 1


62

Indexy pro hodnocení výsledků fuzzy shlukové analýzy 14. Fukuyamův a Sugenoův (FS) index n

k

I FS   i 1 h 1

uihq

D

2



n

k



( x i , x h )  D ( x h , x )   uihq x i  x h 2

i 1 h 1

2

 xh  x

Malé hodnoty indikují, že objekty jsou rozděleny do kompaktních a dobře oddělených shluků (CWS – Compact and Well Separated).


63

2



Indexy pro hodnocení výsledků fuzzy shlukové analýzy 15. CS (Compact and Separate) index n



k

I CS   h 1

i 1

n

uihq D 2 ( x i , x h )

n

k

i 1

h 1

k

 uih  D ( x h , x h ) 2

q u  ih x i  x h

 h 1

2

i 1

n

k

i 1

h 1

 uih  x h  x h

2

Nižší hodnota indikuje lepší rozdělení objektů do shluků.


64

Indexy pro hodnocení výsledků fuzzy shlukové analýzy 16. PS (Partition Separation) index n

uih2

i 1

uM

PS h  

 min hh x h  x h  exp     n

u M  max  1 h  k

i 1

uih2

2

   

k

I PS   PS h h 1

1 k    xh  x k h 1

I PS ( k *)  max I PS ( k ) 2 k  n 1


65

Indexy pro hodnocení výsledků fuzzy shlukové analýzy 17. G index (Rhee a Oh)

n 1 n k 2 2 DW  D (x i , x j )  min{uih , u jh }    n(n  1) i 1 j i 1 h 1 D(.,.) je euklidovská vzdálenost

1 n n 2 DB  2  D (x i , x j )  min{maxh uih , max h u jh } DB G n i 1 j 1

DW

podobnost populace

P  1



 max

IG 

G P

max je směrodatná odchylka z prvků k-rozměrného vektoru, který obsahuje jako první hodnotu n (celkový počet objektů) a ostatní hodnoty jsou nuly, a I G ( k *)  max I G ( k ) 2 k  n 1  je směrodatná odchylka z hodnot n1, n2, …, nk, kde nh je četnost v h-tém shluku pro pevné shlukování Analýza dat 2008/II

66

HODNOCENÍ KVALITY SHLUKŮ

Recommend Documents