Dobývání znalostí. Doc. RNDr. Iveta Mrázová, CSc. Katedra teoretické informatiky Matematicko-fyzikální fakulta Univerzity Karlovy v Praze

Dobývání znalostí Doc. RNDr. Iveta Mrázová, CSc. Katedra teoretické informatiky Matematicko-fyzikální fakulta Univerzity Karlovy v Praze

Dobývání znalostí – Předzpracování dat – Doc. RNDr. Iveta Mrázová, CSc. Katedra teoretické informatiky Matematicko-fyzikální fakulta Univerzity Karlovy v Praze

Výběr a uspořádání příznaků Pravděpodobnost chybného rozhodnutí

×

Množství informace obsažené ve vstupních vzorech Š Příliš velký počet příznaků: „ „ „

technická realizovatelnost rychlost zpracování nebezpečí přeučení z

„

počet proměnných × počet trénovacích vzorů

korelace příznaků I. Mrázová: Dobývání znalostí

3

Volba informativních příznaků Š Výběr minimálního počtu příznaků z předem zvolené množiny příznaků „

„

nelze zaručit, že tato množina obsahuje informativní příznaky volba závisí na konkrétní úloze

Š Uspořádání příznaků v předem zvolené množině příznaků „ „

podle množství nesené informace využití např. u sekvenčních klasifikátorů I. Mrázová: Dobývání znalostí

4

Karhunen-Loevovův rozvoj (1) Vlastnosti Karhunen-Loevova rozvoje: 1. Při daném počtu členů rozvoje poskytuje ze všech rozvojů nejmenší střední kvadratickou odchylku od původních vzorů 2. Vzory jsou po použití disperzní matice po aproximaci nekorelované → dekorelace příznaků I. Mrázová: Dobývání znalostí

5

Karhunen-Loevovův rozvoj (2) 3.

Členy rozvoje nepřispívají rovnoměrně k aproximaci Š

4.

Vliv každého z členů na přesnost aproximace se zmenšuje s jeho pořadovým číslem → Vliv členů s vysokými indexy bude malý a můžeme je zanedbat (~ vynechat)

Velikost chyby aproximace neovlivňuje strukturu rozvoje Š

Změna požadavků na chybu aproximace nevyžaduje přepočítávat celý rozvoj → Stačí jen přidat či odstranit několik posledních členů

Výhodné zejména u sekvenčních metod klasifikace I. Mrázová: Dobývání znalostí

6

Karhunen-Loevovův rozvoj (3) Š

Volba vhodného zobrazení V : Xm → Xp tak, aby vzory z Xp byly nejlepší aproximací původních vzorů z Xm ve smyslu střední kvadratické odchylky K vzorů z jedné třídy m příznaků p ortonormálních vektorů ei ( 1≤ i ≤ p ) v Xm ( p ≤ m )

→ Aproximace vektorů xk z Xm ( 1≤ k ≤ K ) lineární p kombinací vektorů ei : y

k

=

∑

i=1

c

ki

e

i

tak, aby kvadrát odchylky xk od yk : ε k2 = x k − y k byl minimální I. Mrázová: Dobývání znalostí

2

7

Karhunen-Loevovův rozvoj (4) Měřeno m příznaků, z nichž chceme získat p nejdůležitějších příznaků ( 1 ≤ p << m) Matice V : p × m ⎛ v11 K v1 p ⎞ ⎟ ⎜ V =⎜ M O M ⎟ ⎜v K v ⎟ mp ⎠ ⎝ m1

v = ( v1, v2, …) T , x = ( x1, x2, …) T y = v T x = v1 x1 + v2 x2 + …

Výpočet vektoru p nejdůležitějších příznaků: y = VT x

I. Mrázová: Dobývání znalostí

8

Karhunen-Loevovův rozvoj (5) Výpočet matice V: Š Š

Š

n 1 vycentrovat data: μ j = x ij ∑ n i=1 disperzní matice pro trénovací množinu: 1 n (xki − μi ) (xkj − μ j ) wij = w ji = ∑ n k =1 vektory definující nejdůležitější příznaky jsou charakteristickými vektory disperzní matice

I. Mrázová: Dobývání znalostí

9

Karhunen-Loevovův rozvoj (6) Š

Charakteristická čísla odpovídají rozptylu nejdůležitějších příznaků „

„

prvním sloupcem matice V bude charakteristický vektor odpovídající největšímu charakteristickému číslu, … další sloupce V se přestanou přidávat poté, co lze další charakteristická čísla vzhledem k jejich velikosti zanedbat

Problém: Š Š

volba odpovídajícího počtu charakteristických čísel ( p ) nelze zaručit optimální volbu p vzhledem ke skutečnému významu jednotlivých příznaků I. Mrázová: Dobývání znalostí

10

Karhunen-Loevovův rozvoj (7) Modifikace: 1.

Centrované nejdůležitější příznaky y = V T( x – μ ) ,

2.

kde μ = ( μ1, … ) je vektor středních hodnot

Normalizované nejdůležitější příznaky y = L-1/2 V T ( x – μ ) , kde L je matice p × p , prvky diagonály jsou charakteristická čísla odpovídající sloupcům V, ostatní prvky jsou nulové

3.

Normalizace nejdůležitějších příznaků vzhledem k rozptylům w ij w ´ ij =

w ii w

jj

I. Mrázová: Dobývání znalostí

11

Kontingenční tabulky ~ vztah mezi dvěma kategoriálními veličinami, např. binárními

Obecná kontingenční tabulka Š Pro n pozorování s R hodnotami pro veličinu X a S hodnotami pro veličinu Y

I. Mrázová: Dobývání znalostí

12

Kontingenční tabulky (2) Š akl … četnost (frekvence) kombinace ( X = Xk ) ˄ ( Y = Yl ) Š rk , sl … řádkové, sloupcové součty (tzv. marginální hodnoty) Š ekl … očekávaná četnost kombinace ( X = Xk ) ˄ ( Y = Yl ) při nezávislosti X a Y S

rk = ∑ akl l =1

R

; sl = ∑ akl k =1

R

S

; n = ∑∑ akl k =1 l =1

I. Mrázová: Dobývání znalostí

rk ⋅ sl ; ekl = n 13

2 χ

- test

Š Zjišťování vztahu mezi X a Y Š Vyhodnocení rozdílu mezi pozorovanými četnostmi jednotlivých kombinací (uvedenými v tabulce) a četnostmi očekávanými při platnosti hypotézy o nezávislosti obou veličin (počítanými z marginálních hodnot) R

S

χ 2 = ∑∑ k =1 l =1

(akl − ekl )2 ekl

rk ⋅ sl ⎞ ⎛ a − ⎟ R S ⎜ kl n ⎠ ⎝ 2 ⇒ χ = n ∑∑ rk ⋅ sl k =1 l =1

I. Mrázová: Dobývání znalostí

2

14

2 χ

– test

(2)

Š Při platnosti nulové hypotézy nezávislosti veličin X a Y: H0: P ( X = Xk ˄ Y = Yl ) = P ( X = Xk ) P ( Y = Yl ) ; ∀ k,l

má χ2 ( R - 1 ) . ( S – 1 ) stupňů volnosti Š Je-li hodnota χ2 - statistiky ≥ hodnotě χ2 - rozdělení s příslušným počtem stupňů volnosti na zvolené hladině významnosti α : χ 2 ≥ χ 2 ( R − 1 )( S − 1 )

zamítne se nulová hypotéza = > alternativní hypotéza závislosti I. Mrázová: Dobývání znalostí

15

2 χ

– test

(3)

Příklad: čtyřpolní kontingenční tabulka

I. Mrázová: Dobývání znalostí

16

2 χ

– test

(4)

Příklad (pokračování):

Š Hodnota statistiky χ2 : 42.857 Š Hodnota rozdělení χ2 s 1 stupněm volnosti je pro hladinu významnosti α = 0.05 : χ2(1) (0.05) = 3.84

= > závislost mezi výší příjmu a poskytnutím úvěru I. Mrázová: Dobývání znalostí

17

Fisherův test Š χ2 – test lze použít jen v případě dostatečně velkých četností – pro ( rk . sl ) / n ≥ 5 ∀ k, l Š pro čtyřpolní tabulky lze použít Fisherův test (použitelný pro nízké četnosti) Š Výpočet pravděpodobnosti, že při daných marginálních četnostech r a s má čtyřpolní tabulka skutečné četnosti akl :

r1 ! r 2 ! s 1 ! s 2 ! p = n ! a 11 ! a 12 ! a 21 ! a I. Mrázová: Dobývání znalostí

22

! 18

Fisherův test (2) Š Pravděpodobnosti p se nasčítají pro různé hodnoty skutečných četností při daných marginálech (předpokládá a11 = mink,l akl ):

P =

a11

∑ i =0

r1! r2 ! s1! s2 ! n! (a11 − i )! (a12 + i )! (a21 + i )! (a22 − i )!

Š Je-li P ≤ α , zamítne se nulová hypotéza o

nezávislosti na hladině významnosti α I. Mrázová: Dobývání znalostí

19

Regresní analýza ~ určit, jaký vztah má proměnná Y k jedné anebo vícero jiným proměnným X1,…,Xn

Důvody využití: 1. 2. 3. 4.

Nákladné měření výstupů => hledáme predikci výstupu na základě snadno získaných vstupů Hodnoty vstupů jsou k dispozici dříve než výstup => potřebujeme pracovat s odhadem výstupu Řízené vstupní hodnoty mohou pomoci správně odhadnout chování odpovídajících výstupů Může existovat kauzální spojitost mezi vstupy a výstupy => tento vztah chceme najít I. Mrázová: Dobývání znalostí

20

Regresní analýza (2) Š Korelační analýza Platí mezi dvěma numerickými veličinami lineární závislost?

Š Lineární regrese Jaké parametry má lineární závislost mezi dvěma numerickými veličinami? → Aproximace pozorovaných hodnot [ xi , yi ] ; i = 1, … pomocí y = q1 x + q0 + ε I. Mrázová: Dobývání znalostí

21

Regresní analýza (3) → metodou nejmenších čtverců (minimalizace rozdílů mezi skutečnou a očekávanou hodnotou) y y = f(x)= q1 x + q0

→ hledáme min

x

n

∑ (y i =1

− f ( x i ))

2

i

I. Mrázová: Dobývání znalostí

22

Regresní analýza (4) → metodou nejmenších čtverců (minimalizace rozdílů mezi skutečnou a očekávanou hodnotou) ∂ ∂q

→

∂ ∂q0 ∂ ∂q1

n

2 ( ( ) ) y f x − = ∑ i i

0

i =1

n

∑ ( y − (q i =1

i =1

i =1

1

xi + q0 )) = − 2∑ xi yi + 2q1 ∑ xi2 + 2q0 ∑ xi

∑ ( y − (q i =1

n

xi + q0 )) = − 2∑ yi + 2q1 ∑ xi + 2q0 n

n

i

n

1

i

2

2

n

n

n

i =1

i =1

i =1

→ obě parciální derivace by měly být rovné nule I. Mrázová: Dobývání znalostí

23

Regresní analýza (5) →

q

0

q1

⎛ ⎜ = ⎝

⎞⎛ yi ⎟⎜ ⎠⎝

⎞ ⎛ n ⎞⎛ x ⎟ − ⎜ ∑ xi yi ⎟⎜ ∑ i=1 ⎠ ⎝ i=1 ⎠⎝ 2 n ⎛ n ⎞ ⎛ ⎞ n ⎜ ∑ x i2 ⎟ − ⎜ ∑ x i ⎟ ⎝ i=1 ⎠ ⎝ i=1 ⎠

n

∑

i=1

⎛ n⎜ ⎝ =

n

2 i

⎞ ⎛ n xi yi ⎟ − ⎜ ∑ xi ∑ i=1 ⎠ ⎝ i=1 ⎛ n ⎛ n 2 ⎞ n⎜ ∑ xi ⎟ − ⎜ ∑ ⎝ i=1 ⎠ ⎝ i=1 n

⎞⎛ ⎟⎜ ⎠⎝

n

∑

i=1 2

n

∑

i=1

⎞ xi ⎟ ⎠

⎞ yi ⎟ ⎠

⎞ xi ⎟ ⎠

Š Pro lineární závislost x a y nalezneme optimální parametry q0 , q1 vztahu y = q1 x + q0 I. Mrázová: Dobývání znalostí

24

Regresní analýza (6) Š Korelační koeficient: Posouzení „míry“ lineární závislosti lineární závislost ρ ( x, y ) =

S xy 2 x

S S

2 y

; x=

∑x

i

i

n

;

y=

∑y

i

i

n

výběrová kovariance:

S xy =

1 (x − x )( yi − y ) (n − 1) ∑i i

výběrové rozptyly:

S x2 =

1 2 ( ) x − x (n − 1) ∑i i

S y2 =

1 2 ( ) y − y (n − 1) ∑i i

I. Mrázová: Dobývání znalostí

25

Regresní analýza (7) Mnohorozměrná regrese: Š Lineární předpokládáme lineární závislost vysvětlované (závislé) veličiny y na vícero vysvětlujících (nezávislých) veličinách x1 , x2 , … , xm → předpoklad pro i – té pozorování: yi = q0 + q1 xi1 + q2 xi2 + … + qm xim + εi I. Mrázová: Dobývání znalostí

26

Regresní analýza (7) Mnohorozměrná regrese: Š Lineární (pokračování) r r r r T T y = X q ; y = ( y1 , K , yn ) ; q = (q0 ,L , qm )

→ maticový zápis:

⎡1 x11 K x+ m ⎤ X = ⎢⎢M M O M ⎥⎥ ⎢⎣1 xn1 K xnm ⎥⎦

r r → řešení y = X q metodou nejmenších čtverců:

r q =

(X

T

X

)

−1

X

T

I. Mrázová: Dobývání znalostí

r y 27

Regresní analýza (8) Mnohorozměrná regrese (pokračování): Š Nelineární

„

r předpokládáme složitější funkční závislost mezi y a x - kvadratickou, exponenciální, … logistická regrese (případ nelineární regrese) z

z

z

předpokládáme, že závislá veličina y je kategoriální, např. dvouhodnotová modelujeme pravděpodobnost, že y má konkrétní hodnotu r v závislosti na kombinaci hodnot nezávislých veličin x r r podmíněná šance: P y | x 1 − P y | x

(

)(

I. Mrázová: Dobývání znalostí

(

))

28

Regresní analýza (9) Mnohorozměrná regrese (pokračování): Š logistická regrese (pokračování) „

Pro y s hodnotami pouze 1 , resp. 0 :

P( y = 1 | x1 , x2 ,K, xm ) ln = q0 + q1 x1 + K + qm xm 1 − P( y = 1 | x1 , x2 , K, xm ) resp.

q0 +

P( y = 1| x1, x2 ,K, xm ) =

e

∑q j x j j

q0 +

1+ e

∑

I. Mrázová: Dobývání znalostí

qjxj

j

=

1 ∑q j x j

−q0 −

1+ e

j

29

Regresní analýza (10) Mnohorozměrná regrese (pokračování): Š logistická regrese (pokračování) „

Odhad šance, resp. pravděpodobnosti hodnoty y = 1 : Sigmoida:

1

(1 + exp (− sum ))

sum = q 0 + ∑ q j x j j

„

Odhad parametrů modelu metodou maximální věrohodnosti (maximalizace L): n

L = ∏ P( yi = 1 | xi ,1 , xi , 2 , K , xi ,m ) = i =1

n

∏ i =1

⎡⎛ 1 ⎢⎜ − q0 − ∑ q j xi , j ⎢⎜⎜ j ⎢⎣⎝ 1 + e

I. Mrázová: Dobývání znalostí

yi

⎞ ⎛ 1 ⎟ ⎜ ⋅ ⎟ ⎜ q0 + ∑ q j xi , j ⎟ ⎜ ⎠ ⎝1+ e j

1− yi

⎞ ⎟ ⎟ ⎟ ⎠

⎤ ⎥ ⎥ ⎥⎦ 30

Regresní analýza

alternativní odvození (1) Regresní rovnice: Y = α + β1 X 1 + β 2 X 2 + L + β n X n

Ö pro jednotlivé vzory y j = α + β1 x1 j + β 2 x2 j + L + β n xnj + ε j regresní odchylka pro vzor j

I. Mrázová: Dobývání znalostí

31

Regresní analýza

alternativní odvození (2) Lineární regrese pro jednu vstupní proměnnou: Š vzory (x1 , y1 ),K, (xn , yn ) ; xi ∈ X , yi ∈ Y Š regresní rovnice Y = α + β X regresní koeficienty Š metoda nejmenších čtverců pro volbu regresních koeficientů Š kvadratická odchylka n

n

n

SSE = ∑ e = ∑ ( yi − y 'i ) = ∑ ( yi − α − β xi ) i =1

2 i

i =1

2

2

i =1

I. Mrázová: Dobývání znalostí

32

Regresní analýza

alternativní odvození (3) n

n

n

SSE = ∑ e = ∑ ( yi − y 'i ) = ∑ ( yi − α − β xi ) i =1

2 i

2

i =1

2

i =1

Š Derivace kvadratické odchylky podle α a β: n ∂ (SSE ) = −2∑ ( yi − α − β xi ) ∂α i =1 n ∂ (SSE ) = −2∑ (( yi − α − β xi ) xi ) ∂β i =1

Š Minimalizace celkové chyby (derivace by měly být rovné 0)

I. Mrázová: Dobývání znalostí

33

Regresní analýza

alternativní odvození (4) n ∂ (SSE ) = −2∑ ( yi − α − β xi ) ∂α i =1

n ∂ (SSE ) = −2∑ (( yi − α − β xi ) xi ) ∂β i =1

n

n

i =1

i =1

nα + β ∑ xi = ∑ yi

α

n

∑ xi + β i =1

n

n

i =1

i =1

2 x ∑ i = ∑ xi yi

α +β x= y

α = y−β x

tedy

(y − β x ) ∑ x + β ∑ x = ∑ x y n

i =1

n

i

i =1

2 i

I. Mrázová: Dobývání znalostí

n

i =1

i

i 34

Regresní analýza

alternativní odvození (5) (y − β x ) ∑ x + β ∑ x = ∑ x y n

n

α = y−β x

i =1

i

i =1

2 i

n

i

i =1

i

n n ⎛ n 2 ⎞ n β ⎜ ∑ xi − x ∑ xi ⎟ = ∑ xi yi − y ∑ xi i =1 i =1 ⎝ i =1 ⎠ i =1

∑ x (y n

β

n

(

)

n

(

∑ xi xi − x = ∑ xi yi − y i =1

i =1

)

tedy

β=

i =1 n

i

i

−y

)

∑ x (x − x ) i =1

i

i

Š Predikce y pomocí y = α +β x I. Mrázová: Dobývání znalostí

35

Regresní analýza

alternativní odvození (6) ∑ x (y n

β=

i =1 n

i

i

−y

)

∑ x (x − x ) i =1

i

∑ (x − x )(y n

i

Š úpravou dostaneme

β=

i =1

i

i

∑ (x − x ) n

i =1

−y

)

2

i

α = y−βx

I. Mrázová: Dobývání znalostí

36

Regresní analýza

alternativní odvození (7) Vícerozměrná lineární regrese: Š proměnná Y se modeluje jako lineární funkce vícero predikčních proměnných Y = α + β1 X 1 + β 2 X 2 + K + β n X n Š maticové vyjádření X … rozšířená matice vstupních vzorů Y =βX Y … matice výstupů

β = (β 0 , β1 ,K, β n ); β 0 = α Š kvadratická odchylka SSE = (Y − β X )T ⋅ (Y − β X ) I. Mrázová: Dobývání znalostí

37

Regresní analýza

alternativní odvození (8) Š optimalizační krok (LMS)

(

)

∂ (SSE ) ∂ (Y − β X ) (Y − β X ) = =0 ∂β ∂β T

⇒ Š vyjádření regresních koeficientů

(X

T

⋅ X ) β = X T ⋅Y

β = (X ⋅ X ) (X T ⋅ Y ) T

−1

Š Vysoké výpočetní nároky při řešení složitých úloh z praxe ⇒ aproximativní řešení I. Mrázová: Dobývání znalostí

38

Diskriminační analýza ~ Klasifikace příkladů do předem zadaných tříd → hledání závislosti jedné nominální veličiny (určující příslušnost ke třídě) na dalších m numerických veličinách

Š Předpokládáme, že ke každé třídě (~ hodnotě nominální veličiny) ct ; t = 1, …, T existuje (diskriminační) funkce ft ; r r f t ( x ) = max f k ( x ) ; k = 1, K , T k r ⇔ x = ( x1 , x 2 , K , x m ) pat řa k c t I. Mrázová: Dobývání znalostí

39

Diskriminační analýza (2) Lineární diskriminační analýza: ft = q0t + q1t x1 + q2t x2 + … + qmt xm

Diskriminace do dvou tříd Š Místo funkcí f1 a f2 můžeme hledat funkci

r r r f ( x ) = f1 ( x ) − f 2 ( x )

Š Příklady se klasifikují podle r znaménka f ( x ) I. Mrázová: Dobývání znalostí

40

Diskriminační analýza (3) Optimální klasifikace ve smyslu minimální chyby → diskriminační funkce ≈ podmíněné (aposteriorní) r pravděpodobnosti zařazení pozorování x do třídy ct

r r r P ( x | c t ) ⋅ P (c t ) f t ( x ) = P (c t | x ) = r ∑ P (x | c k )P (c k )

→ pro dvě třídy:

k

r r r f (x ) = f1 (x ) − f 2 (x ) = r r = P ( x | c1 ) ⋅ P (c1 ) − P ( x | c 2 ) ⋅ P (c 2 ) I. Mrázová: Dobývání znalostí

41

Diskriminační analýza (4) → normální rozdělení (kvadratická diskriminační funkce): r 1 f (x ) = X 2

T

(S

−1 1

)

− S 2− 1 X

T

(

)

r r + μ 1T S 1− 1 − μ 2T S 2− 1 X +

S2 r r 1 1 r T −1 r P (C 1 ) + ln − μ 1 S 1 μ 1 − μ 2T S 2− 1 μ 2 − ln 2 S1 2 P (C 2 )

(

)

→ stejné kovarianční matice, S1 = S2 = S : (lineární diskriminační funkce) f

( xr ) = (μr 1T

r − μ 2T

)S

−1

X −

r r ⋅ (μ 1 − μ 2

)−

1 2 ln

I. Mrázová: Dobývání znalostí

(μr

T 1

r − μ 2T

P (C P (C

)S

−1

⋅

) 2 )

1

42

Diskriminační analýza (5) → jednotkové kovarianční matice, obě třídy stejně pravděpodobné

(

)

(

r rT rT 1 rT rT f ( x ) = μ1 − μ 2 X − μ1 − μ 2 2

) (μ

r

1

r

− μ2 )

→ pro normální rozložení se hledání diskriminační funkce r „redukuje“ na odhad středních hodnot μ i na základě výběrových průměrů a kovariančních matic Si (z výběrových rozptylů) I. Mrázová: Dobývání znalostí

43

Diskriminační analýza (6) Příklady: Š Normální rozdělení pravděpodobností P(x|ck) P(ck) s různými rozptyly

Š Normální rozdělení se stejnými rozptyly → diskriminace jen podle odhadů středních hodnot I. Mrázová: Dobývání znalostí

44

Shluková analýza Š Lze pozorované vzory rozdělit do skupin (shluků) vzájemně si blízkých vzorů? → Předpoklad: umíme měřit vzdálenost mezi vzory Š Každý vzor je charakterizován m numerickými veličinami Š Vzdálenost mezi dvěma vzory: r r x1 = ( x11 , K , x1 m ) a x 2 = ( x 21 , K , x 2 m )

I. Mrázová: Dobývání znalostí

45

Shluková analýza (2) 1.

2.

Hammingova vzdálenost:

Eukleidovská vzdálenost:

dH

r r (x1 , x 2 ) =

r r d E (x1 , x2 ) =

m

∑

j =1

∑ (x

x1 j − x 2 j

1 j − x2 j )

m

j =1

2

r r d C ( x1 , x2 ) = max x1 j − x2 j

3.

Čebyševova vzdálenost:

4.

Minkovského metrika (1.-3. jsou jejím speciálním případem):

L

(z )

r r ( x1 , x 2 ) =

j

∑ (x m

z

j =1

− x2 j )

z

1j

I. Mrázová: Dobývání znalostí

46

Shluková analýza (3) Š

r r r r d H ( x 1 , x 2 ) = L (1 ) ( x 1 , x 2 ) r r r r d E (x 1 , x 2 ) = L (2 ) (x 1 , x 2 ) r r (z ) r r d C ( x 1 , x 2 ) = lim L ( x 1 , x 2 ) z→ ∞

r r d H ( x 1 , x 2 ) = const . r r d E ( x 1 , x 2 ) = const . r r d C ( x 1 , x 2 ) = const .

I. Mrázová: Dobývání znalostí

47

Shluková analýza (4) Š

Volba míry vzdálenosti závisí na měřítku veličin → veličiny normovat ( ~ dělit průměrem, směrodatnou odchylkou, rozpětím ( max – min ), …)

Š

předpokládáme stejný rozptyl u všech veličin

Š

Různý rozptyl veličin → Mahalanobisova vzdálenost

r r r r T −1 r r d M 2 ( x1 , x 2 ) = ( x1 − x 2 ) S ( x1 − x 2 )

I. Mrázová: Dobývání znalostí

48

Shluková analýza (5) Vzdálenost mezi dvěma shluky U a V : Š

Metodou nejbližšího souseda ~ minimum ze vzdáleností mezi jejich prvky r r r r D (U , V ) = min d ( x k , xl ) ; x k ∈ U , xl ∈ V k ,l

Š

Metodou nejvzdálenějšího souseda ~ maximum ze vzdáleností mezi jejich prvky r r r r D (U , V ) = max d ( x k , xl ) ; x k ∈ U , xl ∈ V k ,l

I. Mrázová: Dobývání znalostí

49

Shluková analýza (6) Vzdálenost mezi dvěma shluky U a V (pokračování): Š

Metodou průměrné vzdálenosti ~ průměr ze vzdáleností mezi vzory; ( nU ~ počet vzorů ve shluku U ; nV ~počet vzorů ve shluku V)

1 D(U ,V ) = nU nV Š

nU nV

r r r r ∑∑d (xk , xl ) ; xk ∈U , xl ∈V k =1 l =1

r Centroidní metodou ~ vzdálenost mezi středy shluků; ( u ~ r střed shluku U; v ~ střed shluku V)

(

r r D (U , V ) = d u , v I. Mrázová: Dobývání znalostí

)

50

Shluková analýza (7) Centroid ~ střed shluku Š

„Prototyp“ reprezentující daný shluk

Š

Jeden shluk může být reprezentován i vícero centroidy „

Š

V závislosti na tvaru shluku a zvolené metrice pro výpočet vzdálenosti

Shlukování metodou k-středů

I. Mrázová: Dobývání znalostí

51

Shluková analýza (8) Shlukování metodou k-středů: 1. Náhodně zvol rozklad do k shluků 2. Urči centroidy pro všechny shluky v aktuálním rozkladu r 3. Pro každý vzor x 1. 2. 3.

r

Urči vzdálenosti d ( x , c k ) (1≤k ≤K; ck ~ centroid k-tého shluku) r r r r Nechť d ( x 1 , c l ) = min d ( x 1 , c k )

k r r Není-li rx součástí shluku l (k jehož centroidu cl má nejblíž),

přesuň x do shluku l

4. Došlo-li k nějakému přesunu, potom jdi na 2, jinak KONEC I. Mrázová: Dobývání znalostí

52

Shluková analýza (9) Shlukování metodou k-středů: Š

Varianty algoritmu: „

„

Š

Při počátečním rozkladu prohlásit prvních k vzorů za centroidy (odpadne Krok 2) Aktualizace centroidů po každém přesunu (v cyklu Kroku 3)

Shluky jsou následně reprezentovány svými centroidy

I. Mrázová: Dobývání znalostí

53

Shluková analýza (10) Algoritmus hierarchického shlukování: ~ Š

metodou „zdola nahoru“ Inicializace: 1. 2.

Š

Urči vzájemné vzdálenosti mezi všemi vzory Zařaď každý vzor do samostatného shluku

Hlavní cyklus: 1.

Dokud je více než jeden shluk 1. 2.

Najdi dva navzájem nejbližší shluky a spoj je Spočítej pro tento nový shluk jeho vzdálenost od ostatních shluků I. Mrázová: Dobývání znalostí

54

Shluková analýza (11) Algoritmus hierarchického shlukování (pokračování): Š

dendrogram ~ ukazuje (zleva doprava) postupné spojování shluků ~ optimální počet shluků není předem znám

I. Mrázová: Dobývání znalostí

55

Vektorová kvantizace: Algoritmus LVQ Krok 1: Krok 2:

Krok 3: Krok 4:

r Inicializace všech váhových vektorů w j (0 ) Inicializace parametru učení μ(0) a nastavení k = 0 Otestuj ukončovací podmínku: IF FALSE => CONTINUE IF TRUE => QUIT r Pro každý trénovací vzor xi proveď Kroky 4 a 5 Urči index váhového vektoru ( j = q ) tak, aby min j

r r xi − w

(k ) 2 2

j

r

(použij euklidovskou vzdálenost, wq (k ) je váhový vektor s minimální vzdáleností I. Mrázová: Dobývání znalostí

56

Vektorová kvantizace: Algoritmus LVQ (2) r

Krok 5: Aktualizuj příslušný váhový vektor w q (k ) podle:

[ [

] ]

r r r r IF Cwr q = Cxri ⇒ wq (k + 1) = wq (k ) + μ (k ) xi − wq (k ) r r r r r r IF Cwq ≠ Cxi ⇒ wq (k + 1) = wq (k ) − μ (k ) xi − wq (k ) Krok 6: Nastav k Å k + 1 Sniž parametr učení, např. podle: μ(k)=μ(k–1)/(k+1)

(k>0)

Přejdi ke Kroku 2 I. Mrázová: Dobývání znalostí

57

Vektorová kvantizace: Algoritmus LVQ (3) MATLAB: Funkce pro LVQ1 Function W = lvq1(X,CX,m,mu,maxiter) % W = lvq1(X,CX,m,mu,maxiter) počítá váhovou matici % pro vektorovou kvantizaci LVQ1 % X: je matice vstupů (každý sloupec odpovídá % vstupnímu vektoru % CX: je řádkový vektor „skalárních“ tříd % odpovídajících sloupcovým vektorům z X % m: počet různých tříd % mu: počáteční parametr učení % maxiter: maximální počet iterací N = size(X,2); I. Mrázová: Dobývání znalostí

58

Vektorová kvantizace: Algoritmus LVQ (4) MATLAB: Funkce pro LVQ1 (pokračování) % inicializace váhových vektorů podle prvních m vektorů % z trénovací množiny (musí obsahovat vzory ze všech tříd) W = X(:,1:m); CW = CX(1:m); % třídy pro váhové vektory snorm = zeros(1,m); niter = 1; while niter <= maxiter if niter == 1 for i = m+1:N for j = 1:m snorm(1,j) = norm(X(:,i) - W(:,j))^2; end [mind,index] = min(snorm); I. Mrázová: Dobývání znalostí

59

Vektorová kvantizace: Algoritmus LVQ (5) MATLAB: Funkce pro LVQ1 (pokračování) if CX(i) == CW(index) W(:,index) = W(:,index) + mu*(X(:,i)-W(:,index)); else W(:,index) = W(:,index) mu*(X(:,i)-W(:,index)); end end else for i = 1:N for j = 1:m snorm(1,j) = norm(X(:,i)-W(:,j))^2; end mind,index] = min(snorm); I. Mrázová: Dobývání znalostí

60

Vektorová kvantizace: Algoritmus LVQ (6) MATLAB: Funkce pro LVQ1 (pokračování) if CX(i) == CW(index) W(:,index) = W(:,index) + (mu/niter)* (X(:,i)-W(:,index)); else W(:,index) = W(:,index) - (mu/niter)* (X(:,i)-W(:,index)); end end end niter = niter + 1; end I. Mrázová: Dobývání znalostí

61