+ All Categories
Home > Documents > KLASIFIKACNÍ METODA k NEJBLIZ ÍCH SOUSEDU A HLOUBKA DATantoch/robust12/... · 2012. 9. 9. ·...

KLASIFIKACNÍ METODA k NEJBLIZ ÍCH SOUSEDU A HLOUBKA DATantoch/robust12/... · 2012. 9. 9. ·...

Date post: 25-Jan-2021
Category:
Upload: others
View: 1 times
Download: 0 times
Share this document with a friend
27
KLASIFIKA ˇ CN ´ I METODA k NEJBLI ˇ Z ˇ S ´ ICH SOUSED ˚ U A HLOUBKA DAT Ondˇ rej Venc´ alek ırodovˇ edeck´ a fakulta Univerzity Palack´ eho v Olomouci 12.9.2012
Transcript
  • KLASIFIKAČNÍ METODA k NEJBLIŽŠ́ICH SOUSEDŮA HLOUBKA DAT

    Onďrej VencálekPř́ırodovědecká fakulta Univerzity Palackého v Olomouci

    12.9.2012

  • Obsah

    Metoda k nejbližš́ıch sousedůÚloha klasifikacekNN a jádrové odhady hustoty - dvě strany téže mince

    Metoda k nejbližš́ıch sousedů a hloubkaPř́ıstup založený na

    ”distribučńım“okoĺı

    Symetrizačńı p̌ŕıstupDD p̌ŕıstup

  • Úloha klasifikace

    ?

    X = (X1, . . . ,Xm) = (vek,BMI , systol .tlak, . . .)

    X ∼ P1 (hustota f1) X ∼ P2 (hustota f2)

    d : Rm → {1, 2}

  • Optimalita funkce d

    I minimalizace pravděpodobnosti chybného zǎrazeńı

    K∑i=1

    P(d(X) 6= i |X ∼ Pi )P(X ∼ Pi ) (1)

    I minimalizace sťredńı hodnoty ztráty

    K∑i=1

    K∑j=1

    ∫{y:d(y)=j}

    zi ,j fi (y)dy

    P(X ∼ Pi ) (2)kde zi,j je ztráta, když objekt ze skupiny i p̌rǐrad́ıme do sk. j ;pro zi,j = 1 když i 6= j a nula jinak se (2) redukuje na (1).

    I minimalizacemax

    iP(d(X) 6= i |X ∼ Pi ) (3)

  • Hustoty fi známé - Bayesovský klasifikátor

    d(x) = arg maxi

    πi fi (x),

    kde πi = P(X ∼ Pi ) ... apriorńı pravděp.dk. optimality viz Antoch a Vorĺıčková (1992).

    −4 −2 0 2 4 6

    0.00

    0.05

    0.10

    0.15

    0.20

    x

    hust

    ota

    π1 = 0.5

    π2 = 0.5

    −4 −2 0 2 4 6

    0.00

    0.10

    0.20

    0.30

    hust

    ota

    π1 = 0.1

    π2 = 0.9

  • Hustoty fi neznámé

    I d(x) = arg maxi πi fi (x)

    I d(x) = arg maxi π̂i f̂i (x)

    Tréningová (trénovaćı) množina:

    Značeńı:TSi = {xi,j , j = 1, . . . , ni} pro i = 1, . . . ,K... i-tá část tréningové množinyn =

    ∑i ni

    ... celkový počet prvk̊u tréningové množiny

  • Odhad hustoty fiI parametrický p̌ŕıstup

    I LDA (Fisher 1936), QDA

    I neparametrický p̌ŕıstupI jádrový odhad hustoty (Rosenblatt 1956, Parzen 1962)I metoda k nejbližš́ıch sousedů (kNN) (Fix a Hodges 1951)

    ————————————————————————————Neparametrický p̌ŕıstup:mějme bod x ∈ Rm a nějaké jeho okoĺı Li (x), pak odhad fi (x)můžeme založit na aproximaci

    P(X ∈ Li (x)|X ∼ Pi ) =∫

    Li (x)fi (y)dy ∼= fi (x)λ(Li (x))

    f̂i (x) =ki

    niλ(Li (x)),

    kde ki ... počet bodů z TSi , které nálež́ı Li (x),ni ... počet všech bodů z TSi .

  • Jádrové odhady hustoty

    f̂i (x) =ki

    niλ(Li (x)),

    Necht’ L1(x) = L2(x) = . . . = LK (x) =: L(x)kde L(x) je takové okoĺı bodu, že λ(L(x)) = V (konst.)

    d(x) = arg maxi

    π̂i f̂i (x) = arg maxi

    π̂i1

    niλ(L(x))

    ni∑j=1

    I[xi,j∈L(x)]

    = arg maxi

    π̂i1

    niλ(L(x))

    ni∑j=1

    Ker (x, xi ,j , L(x))

  • Metoda k nejbližš́ıch soused̊u

    f̂i (x) =ki

    niλ(Li (x)),

    Necht’ L1(x) = L2(x) = . . . = LK (x) =: L(x)kde L(x) je takové okoĺı bodu, že

    ∑i ki = k (konst.)

    Pro π̂i =nin je arg maxi π̂i f̂i (x) = arg maxi ki .

    ●●

    +

  • Kolika soused̊u se ptát aneb jak zvolit k

    (P1) limni→∞ k = ∞(P1) limni→∞ k/ni = 0

    ∀x ∈ Rm f̂i (x) =ki

    niλ(Li (x))P→ fi (x) pro ni →∞⇔ (P1)&(P2)

    Pozor: pro pevné k ∈ N a n ∈ N je∫

    Rm f̂i (x)dx 6= 1.Př́ıklad: 1-NN v R1:

    | | || | | || || |

    xmin xmax x

    ∫∞xmax

    1n(x−xmax )dx =

    1n

    ∫∞0

    1x dx = ∞.

  • O nejbližš́ım sousedovi aneb když k = 1

    E1NN = P(chybné zařazeńı pomoćı 1-NN)EBayes = P(chybné zařazeńı pomoćı Bayes. klasifikátoru)

    E1NN ≤ 2EBayes

    Přesněji: pro K ≥ 2 skupin plat́ı

    E1NN ≤ EBayes(

    2− KK − 1

    EBayes

    )dk. viz Hand (1981).

  • Obsah

    Metoda k nejbližš́ıch sousedůÚloha klasifikacekNN a jádrové odhady hustoty - dvě strany téže mince

    Metoda k nejbližš́ıch sousedů a hloubkaPř́ıstup založený na

    ”distribučńım“okoĺı

    Symetrizačńı p̌ŕıstupDD p̌ŕıstup

  • kNN s využit́ım hloubky, p̌ŕıstup”distribučńıho“ okoĺı

    Připomeňme:

    P(X ∈ L(x)) ∼= f (x) · λd (L(x)) ,

    kde L(x) je nějaké okoĺı bodu x:

    I L(x) ={y ∈ Rd : ‖x− y‖ < η

    }I L(x;P) =

    {y ∈ Rd : |f (x;P)− f (y;P)| < η

    }.

    0.02

    0.04

    0.06

    0.08

    −4 −2 0 2 4

    −3

    −2

    −1

    01

    23

    0.02

    0.04

    0.06

    0.08

    0.02

    0.04

    0.06

    0.08

    −4 −2 0 2 4

    −3

    −2

    −1

    01

    23

    0.02

    0.04

    0.06

    0.08

  • kNN s využit́ım hloubky, p̌ŕıstup”distribučńıho“ okoĺı

    Připomeňme:

    P(X ∈ L(x)) ∼= f (x) · λd (L(x)) ,

    kde L(x) je nějaké okoĺı bodu x:

    I L(x) ={y ∈ Rd : ‖x− y‖ < η

    }I L(x;P) =

    {y ∈ Rd : |D(x;P)− D(y;P)| < η

    }.

    0.02

    0.04

    0.06

    0.08

    −4 −2 0 2 4

    −3

    −2

    −1

    01

    23

    0.02

    0.04

    0.06

    0.08

    0.02

    0.04

    0.06

    0.08

    −4 −2 0 2 4

    −3

    −2

    −1

    01

    23

    0.02

    0.04

    0.06

    0.08

  • kNN s využit́ım hloubky, p̌ŕıstup”distribučńıho“ okoĺı

    fi (x) = hi (D(x;Pi )) i = 1, . . . ,K

    π̂i f̂i (x) =nin

    kini

    1

    λ̂d(Li (x))=

    ki

    nλ̂d(Li (x))

    d(x) = arg mini=1,...,K

    λ̂d(L(x, P̂i )),

    kde L(x, P̂i ) je ”distribučńım“ okoĺı bodu x, které obsahuje právě

    k bodů z TSi .

  • kNN s využit́ım hloubky, symetrizačńı p̌ŕıstup

    0.05

    0.1

    0.15

    −2 −1 0 1 2 3 4

    −2

    −1

    01

    2

    + +

  • kNN s využit́ım hloubky, symetrizačńı p̌ŕıstup

    0.05

    0.1

    0.15

    −2 −1 0 1 2 3 4

    −2

    −1

    01

    2

    + + +

    0.05

    0.1

    0.15

  • kNN s využit́ım hloubky, symetrizačńı p̌ŕıstup

    0.05

    0.1

    0.15

    −2 −1 0 1 2 3 4

    −2

    −1

    01

    2

    + + +

    0.05

    0.1

    0.15

    0.02

    0.04

    0.06

    0.08

  • kNN s využit́ım hloubky, symetrizačńı p̌ŕıstup

    0.05

    0.1

    0.15

    −2 −1 0 1 2 3 4

    −2

    −1

    01

    2

    + + +

    0.05

    0.1

    0.15

    0.02

    0.04

    0.06

    0.08

  • kNN s využit́ım hloubky, symetrizačńı p̌ŕıstup

    0.05

    0.1

    0.15

    −2 −1 0 1 2 3 4

    −2

    −1

    01

    2

    0.05

    0.1

    0.15

    + +

  • kNN s využit́ım hloubky, symetrizačńı p̌ŕıstup

    Př́ıklad:Okoĺı bodů [0,1], [2,0] a [25

    √5, 25

    √5] vzhledem k rozděleńı

    N2

    ((00

    ),

    (4 00 1

    )).

    −4 −2 0 2 4

    −2

    −1

    01

    2

    + ++

    +

    +

    +

  • kNN s využit́ım hloubky, symetrizačńı p̌ŕıstup

    Značeńı:X1, . . . ,Xn ... všechny body tréningové množinyx ... nové pozorováńı

    Postup:

    1.”Reflexe“: Xn+i := 2x− Xi pro i = 1, . . . , n,

    body X1, . . . ,X2n určuj́ı rozděleńı P(n)x .

    2. Sěrad’me body X1, . . . ,Xn tak, aby platilo

    D(X(1),P(n)x ) ≥ D(X(2),P

    (n)x ) ≥ . . . ≥ D(X(n),P

    (n)x ).

    3. Pro libovolné k ∈ {1, . . . , n} p̌redstavuj́ı bodyX(i), i = 1, . . . , k, k nejbližš́ıch sousedů bodu x.

  • kNN s využit́ım hloubky, DD p̌ŕıstup

    ●●

    ●●

    ●●

    ●●

    ●●

    ●●

    ● ●

    ●●

    ● ●

    ●●

    ●●

    ● ●

    ● ●

    ●●●

    ●●

    ●●●

    ● ●

    ●●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ●●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ●●

    ●●

    ●●●●

    ●●

    ● ●

    ●●

    ●●

    ● ●

    ●●●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ● ●●

    ●●

    ●●

    ●●

    ●●

    ● ●●

    −2 −1 0 1 2 3 4

    −3

    −2

    −1

    01

    23

  • kNN s využit́ım hloubky, DD p̌ŕıstup

    ●●

    ●●

    ●●

    ●●

    ●●

    ●●

    ● ●

    ●●

    ● ●

    ●●

    ●●

    ● ●

    ● ●

    ●●●

    ●●

    ●●●

    ● ●

    ●●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ●●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ●●

    ●●

    ●●●●

    ●●

    ● ●

    ●●

    ●●

    ● ●

    ●●●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ● ●●

    ●●

    ●●

    ●●

    ●●

    ● ●●

    −2 −1 0 1 2 3 4

    −3

    −2

    −1

    01

    23

    ●●

    ● ●●●

    ●●

    ●●

    ●●

    ●● ●● ● ●

    ● ●● ●

    ● ●●● ●

    ●●●

    ●●

    ●●

    ●● ●●

    ●●

    ●●● ●

    ●●

    ● ●●●

    ●●●

    ●●● ●

    ● ● ●

    ●● ●

    ●●●●

    ● ●

    ●●

    ●●

    ●●

    ●●

    ● ●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ● ●

    ● ●

    ● ●●

    ●●●

    ● ●●

    ●● ●

    ●●● ●

    ● ● ●●

    ●●

    ●●

    ●●

    ●● ●

    ●●●

    ●●

    ●●

    ●●

    ●●

    ●●●

    ●●

    ●●

    ●●

    ●●

    0.0 0.1 0.2 0.3 0.4

    0.0

    0.1

    0.2

    0.3

    0.4

    Hl[,

    2]

  • kNN s využit́ım hloubky, DD p̌ŕıstup

    ●●

    ●●

    ●●

    ●●

    ●●

    ●●

    ● ●

    ●●

    ● ●

    ●●

    ●●

    ● ●

    ● ●

    ●●●

    ●●

    ●●●

    ● ●

    ●●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ●●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ●●

    ●●

    ●●●●

    ●●

    ● ●

    ●●

    ●●

    ● ●

    ●●●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ● ●●

    ●●

    ●●

    ●●

    ●●

    ● ●●

    −2 −1 0 1 2 3 4

    −3

    −2

    −1

    01

    23

    ●●

    ● ●●●

    ●●

    ●●

    ●●

    ●● ●● ● ●

    ● ●● ●

    ● ●●● ●

    ●●●

    ●●

    ●●

    ●● ●●

    ●●

    ●●● ●

    ●●

    ● ●●●

    ●●●

    ●●● ●

    ● ● ●

    ●● ●

    ●●●●

    ● ●

    ●●

    ●●

    ●●

    ●●

    ● ●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ● ●

    ● ●

    ● ●●

    ●●●

    ● ●●

    ●● ●

    ●●● ●

    ● ● ●●

    ●●

    ●●

    ●●

    ●● ●

    ●●●

    ●●

    ●●

    ●●

    ●●

    ●●●

    ●●

    ●●

    ●●

    ●●

    0.0 0.1 0.2 0.3 0.4

    0.0

    0.1

    0.2

    0.3

    0.4

    Hl[,

    2]

  • kNN s využit́ım hloubky, DD p̌ŕıstup

    ●●

    ●●

    ●●

    ●●

    ●●

    ●●

    ● ●

    ●●

    ● ●

    ●●

    ●●

    ● ●

    ● ●

    ●●●

    ●●

    ●●●

    ● ●

    ●●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ●●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ●●

    ●●

    ●●●●

    ●●

    ● ●

    ●●

    ●●

    ● ●

    ●●●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ● ●●

    ●●

    ●●

    ●●

    ●●

    ● ●●

    −2 −1 0 1 2 3 4

    −3

    −2

    −1

    01

    23

    ●●

    ● ●

    ●●

    ●●

    ●●

    ● ●●●

    ●●

    ●●

    ●●

    ●● ●● ● ●

    ● ●● ●

    ● ●●● ●

    ●●●

    ●●

    ●●

    ●● ●●

    ●●

    ●●● ●

    ●●

    ● ●●●

    ●●●

    ●●● ●

    ● ● ●

    ●● ●

    ●●●●

    ● ●

    ●●

    ●●

    ●●

    ●●

    ● ●

    ●●

    ● ●

    ●●

    ●●

    ●●

    ● ●

    ● ●

    ● ●●

    ●●●

    ● ●●

    ●● ●

    ●●● ●

    ● ● ●●

    ●●

    ●●

    ●●

    ●● ●

    ●●●

    ●●

    ●●

    ●●

    ●●

    ●●●

    ●●

    ●●

    ●●

    ●●

    0.0 0.1 0.2 0.3 0.4

    0.0

    0.1

    0.2

    0.3

    0.4

    Hl[,

    2]

  • kNN s využit́ım hloubky, DD p̌ŕıstup

    −2 −1 0 1 2 3 4

    −2

    −1

    01

    2

    ●●

    ●●

    ●●

    ●●●

    ●●

    ●●

    ●●

    ●●●

    ●●●

    ●●

    ●●●

    ●●

    ●●

    ●●

    ●●

    ●+

    −2 −1 0 1 2 3 4

    −2

    −1

    01

    2

    ● ●

    ●●

    ●●

    ●●

    ●●

    ●●

    ●● ●●

    ●●●

    ●●●

    ●●

    ●●

    ●●●

    ●●●

    ●+

    −2 −1 0 1 2 3 4

    −2

    −1

    01

    2

    ●●

    ●●●

    ●●

    ●●

    ●●

    ● ●

    ●● ●

    ●●●

    ●●

    +

    −2 −1 0 1 2 3 4

    −2

    −1

    01

    2●

    ●●

    ●●

    ●●

    ●●

    ●●

    ●●

    ●●

    ●●

    ●●●

    +

    Metoda k nejblizších souseduÚloha klasifikacekNN a jádrové odhady hustoty - dve strany téze mince

    Metoda k nejblizších sousedu a hloubkaPrístup zalozený na „distribucním“ okolíSymetrizacní prístupDD prístup


Recommended