Vytěžování znalostí z dat

Vytěžování znalostí z dat Pavel Kordík, Jan Motl Department of Computer Systems Faculty of Information Technology Czech Technical University in Prague

Přednáška 4: K-nejbližších sousedů BI-VZD, 09/2011 MI-POA

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Pavel Kordík, Jan Motl (ČVUT FIT)

Vytěžování znalostí z dat

BI-VZD, 2012, Přednáška 4

1/27

Osnova

Přednáška 1) Způsoby učení 2) Metoda K-nejbližších sousedů 3) Plasticita modelu




2/27

Způsoby učení

Modely v data miningu

Učení Klasifikace

Shlukováni

„s učitelem“

„bez učitele“

(máme informaci, jak třídit do tříd)

(nemáme informaci, jak třídit do tříd)




3/27

Způsoby učení

Přehled metod generujících modely Funkce Klasifikace

Metody K-nejbližších sousedů, Rozhodovací stromy, Bayesův klasifikátor, Neuronové sítě.

Shlukování

K-means, Hierarchické shlukování.




4/27

Způsoby učení

Vytvoření a použití modelu • Dvě fáze 1. Fáze učení, trénování • Model je vygenerován, upravuje se vnitřní struktura, parametry

2. Fáze použití, vybavování • Model je použit, vypočítá se výstup, model to neovlivní




5/27

KNN

1NN – nejbližší soused 1. Trénování – generování modelu o Ulož trénovací data

2. Klasifikace – použití modelu o Najdi nejbližšího souseda a klasifikuj stejnou třídou

? třída A třída B třída ke klasifikaci

o http://www.theparticle.com/applets/ml/nearest_neighbor/




6/27

KNN

Metrika, Euklidovská vzdálenost o Je třeba nějak určit podobnost vzorů – jejich vzdálenost o Vzdálenost musí splňovat určité podmínky: 1. 2. 3. 4.

d(x,y) > 0. d(x,y) = 0 iff x = y. d(x,y) = d(y,x). d(x,y) < d(x,z) + d(z,y) (trojúhelníková nerovnost ).

Dva body v n-rozměrném prostoru: Euklidovská vzdálenost P a Q =

o Odmocňování není nezbytně nutné, když vzdálenosti porovnáváme Pavel Kordík, Jan Motl (ČVUT FIT)



7/27

KNN

Manhattonská vzdálenost • Jak budeme počítat vzdálenost dvou cyklistů v Manhattonu?

M (P, Q ) = p1 − q1 + p2 − q2 + ... + pn − qn Pavel Kordík, Jan Motl (ČVUT FIT)



8/27

KNN

Váha atributů • Problém – různé rozsahy vzdáleností • Při určování euklidovské vzdálenosti mají atributy různou váhu – např. p je 100x důležitější než q

3,5 q

0

p 2


350



9/27

KNN

Normalizace atributů •

Problém vyřešíme přeškálováním (normalizací) atributů: 1) Mini-max normalizace

vi − min vi ai = max vi − min vi 2) Z-score normalizace vi − Avg (vi ) ai = StDev ( vi )

•

Původní rozsahy se u obou transformují do <0,1>




10/27

KNN

Rozhodovací hranice

1 q

0

Kde přesně je rozhodovací hranice tříd?

p 0


1



11/27

KNN

Voronoiův diagram

http://www.cs.cornell.edu/Info/People/chew/Delaunay.html Pavel Kordík, Jan Motl (ČVUT FIT)



12/27

KNN

kNN – k nejbližších sousedů • Najdi k nejbližších sousedů a klasifikuj majoritní třídou

3NN klasifikace:

5NN klasifikace:

?

?

Jak zvolit optimální k? Pavel Kordík, Jan Motl (ČVUT FIT)



13/27

KNN

1NN 90

80

70

60

50

40

30

20 20

30


40

50


60

70

80


14/27

KNN

3NN 90

80

70

60

50

40

30

20 20

30


40

50


60

70

80


15/27

KNN

9NN 90

80

70

60

50

40

30

20 20

30


40

50


60

70

80


16/27

KNN

9NN – měkké rozhodnutí (poměr mezi počtem sousedů z různých tříd) 90

80

70

60

50

40

30

20 20

30


40

50


60

70

80


17/27

KNN

31NN – měkké rozhodnutí 90

80

70

60

50

40

30

20 20

30


40

50


60

70

80


18/27

KNN

Závislost chybovosti na k

Zdroj: University of California, Irvine Pavel Kordík, Jan Motl (ČVUT FIT)



19/27

KNN

Menší trénovací množina




20/27

KNN

Porovnání vlivu velikosti datasetu




21/27

Plasiticita

Přeučení 80

70

60

50

40

30

20 20

30


40

50

60


70

80


22/27

Plasiticita

Přeučení 80

70

60

50

40

30

20 20

30


40

50

60


70

80


23/27

Plasiticita

Lineární klasifikátor (separátor) 80

70

60

50

40

30

20 20

30


40

50

60


70

80


24/27

Plasiticita

Nelineární klasifikátor 80

70

60

50

40

30

20 20

30


40

50

60


70

80


25/27

Plasiticita

Varianty kNN

• Příspěvek souseda je vážen vzdáleností od klasifikovaného vzoru • Klasifikace pomocí etalonů – vybrána vhodná podmnožina trénovací množiny




26/27

Diskuze

Diskuze • Velmi populární metoda klasifikace a často i velmi úspěšná • Okamžité vytvoření modelu • Ale pomalé používání o Při klasifikaci nutno projít celou trénovací množinu

• Model je paměťově náročný o Nutno si pamatovat celou trénovací množinu

• Pozor na váhy atributů o Řešením je normalizace dat

• Důležité je najít vhodné k o Pro minimalizaci chyb na testovacích datech




27/27

Vytěžování znalostí z dat

Recommend Documents