Hloubka dat a její použití pro klasifikaci
Daniel Hlubinka, Lukáš Kotík, Ondˇrej Vencálek, Stanislav Nagy a Miroslav Šiman Univerzita Karlova v Praze Matematicko-fyzikální fakulta ˇ Katedra pravdepodobnosti a matematické statistiky
Novohradské statistické dny Nové Hrady, cˇ erven 2012
Úvod Co je vlastneˇ hloubka dat? • Zcela obecne: ˇ pˇriˇrazení poˇradí mnohorozmerné ˇ náhodné
ˇ Klidneˇ i nekoneˇcnerozm ˇ ˇ veliˇcine. erné (funkcionální ˇ promenné). • Bud’ X : (Ω, F, P) → (E, E, PX ) náhodná veliˇcina. Hloubka
ˇ ˇ je funkce rozdelení náhodné veliˇciny a bodu˚ ve výberovém prostoru: D : (E, PE ) → R+
(pˇríp. → [0, 1]).
• Mužeme ˇ ˚ používat ruzná ˚ znaˇcení. Nejˇcasteji
D(x, Q) = DQ (x), pˇrípadneˇ D(x) bude-li jasné o jaké ˇ rozdelení se jedná.
Jaké podmínky na hloubku klást?
• Hloubka by mela ˇ zohlednovat ˇ polohu bodu s ohledem na
ˇ rozdelení. • Typicky se jedná o cˇ ásteˇcné lineární uspoˇrádání. Hloubku
každých dvou bodu˚ lze porovnat, body se stejnou hloubkou tvoˇrí kontury hloubky. Tyto kontury lze chápat ˇ ˇ jako variantu kvantilu˚ rozdelení mnohorozmerných ˇ náhodných veliˇcin (které nelze pˇrirozene definovat kvuli ˚ absenci lineárního uspoˇrádání). • Jak název napovídá, body u „okraje“ nosiˇce rozdelení ˇ by
ˇ mít malou hloubku, naopak budy „uprostˇred“ mely ˇ ˇ mít hloubku velkou. rozdelení by mely
Intuitivní pojetí hloubky
• Ochrana krále: Duležitá ˚ osoba musí mít ze všech stran
ˇ v okruhu svých krytá záda. Musí být ukryta nejhloubeji strážcu. ˚ • Slavnostní veceˇ ˇ re: Význaˇcní hosté jsou „uprostˇred“ a s
ˇ klesajícím významem hostu˚ se zvetšuje vzdálenost jejich sezení od centra. • Uspoˇrádání zevnitˇr-ven: Data, která jsou „uvnitˇr“
ˇ ˇ pravdepodobnostního rozdelení dostanou velkou hloubku, data vneˇ dostanou malou hloubku. ˇ • Opak odlehlosti: Cím ˇ hloubka, tím méneˇ jsou data vetší „odlehlá“ a naopak.
Serflinguv ˚ pruvodce ˚ po hloubce
• Liu (1990) udává nekolik ˇ žádoucích vlastností hloubky.
H1 Hloubka má být afinneˇ invariantní funkcí. ˇ H2 Hloubka má být maximální v centru symetrie rozdelení. ˇ H3 Hloubka má klesat smerem od nejhlubšího bodu. H4 Hloubka má jít nule pro body jdoucí k nekoneˇcnu (od nejhlubšího bodu). • Serfling a Zuo (2000) pak zkoumají jednotlivé hloubky s
ohledem na H1–H4 a jako statistickou hloubku definují ˇ nezápornou omezenou funkci splnující H1–H4.
Serflinguv ˚ pruvodce ˚ po hloubce
• Serfling a Zuo (2000) dále delí ˇ hloubku na nekolik ˇ typu: ˚
A D(x, P) = EP h(x; X1 , . . . , Xr ), kde h je libovolná nezáporná ˇ ritelná funkce meˇ ˇ rící blízkost bodu x k bodum omezená meˇ ˚ x1 , . . . , xr . −1 B D(x, P) = 1 + EP h(x; X1 , . . . , Xr ) , kde h je libovolná ˇ ritelná funkce meˇ ˇ rící vzdálenost nezáporná neomezená meˇ bodu x od bodu˚ x1 , . . . , xr . −1 C D(x, P) = 1 + O(x, P) , kde O(x, P) je funkce udávající ˇ odlehlost bodu x vzhledem k rozdelení P. D D(x, P; H) = infH∈H P[x ∈ H], kde H je vhodná tˇrída ˇ ritelných množin. meˇ
Hloubka je globální funkcionál • Pˇrirozeneˇ se naskýtá otázka: je hustota hloubkou? • Mohla by být v širším smyslu; hloubka ale je zavedena jako
ˇ funkcionál zduraz ˚ nující globální nebo alesponˇ ne limitní ˇ charakter pravdepodobnostní míry. • V nekterých ˇ pˇrípadech ale hloubka a hustota úzce
souvisejí: z vlastností H1–H4 plyne, že pro unimodální ˇ elipticky symetrická absolutneˇ spojitá rozdelení musí existovat neklesající funkce φ : R+ → R+ propojující hloubku a hustotu, tj D(x, P) = φ fP (x) , ˇ kde fP je hustota rozdelení P vuˇ ˚ ci Lebesgueoveˇ míˇre.
• Hustotu tedy nebudeme považovat za hloubkový
funkcionál.
Hloubka a kvantil • Oznaˇcme úrovnové ˇ množiny a kontury hloubky
L(D, P, q)= {x : D(x, P) ≤ q}, C(D, P, q)= L(D, P, q) \ L◦ (D, P, q) kde L◦ je vnitˇrek množiny. • Kontura hloubky muže ˇ ˚ být použita jako mnohorozmerná
analogie kvantilu. • Je tedy žádoucí, aby definice hloubky použitá na
ˇ jednorozmerná data definovala kvantil (ve skuteˇcnosti dva symetrické kvantily). • Vnoˇrení jednotlivých úrovnových ˇ množin hloubky je
samozˇrejmostí.
Kvantil a hloubka
• Pokud máme vhodnou definici mnohorozmerného ˇ kvantilu
ve smyslu uzavˇrených (do sebe vnoˇrených) kontur Q(P, p), lze definovat hloubku pomocí jejích kontur množin ˇ C D, P, ψ(p) = Q(P, p) pro nejakou klesající ψ.
ˇ • Cím ˇ kvantil, tím má menší hloubku (je dál od stˇredu). vetší • Aby šlo o rozumnou hloubku, je nutné aby kvantil mel ˇ
rozumné vlastnosti. • Kvantil a hloubka se tedy dají v urˇcitém pˇrípadeˇ sjednotit
do jednoho pojmu.
Hloubka = kvantil
C1−2α • Mnohorozmerným ˇ ˇ hloubkou. mediánem je bod s nejvetší • Body se stejnou hloubkou tvoˇrí kvantilové kontury. • Hloubka zobecnuje ˇ ˇ u. kvantil do více rozmer ˚ Místo dvojice
kvantilu˚ qα a q1−α máme kvantilovou konturu C1−2α .
Neparametrické hloubky • Hloubkových funkcí je možná více, než matematiku˚
zabývajících se jimi. • Historicky první a nejznámejší ˇ je poloprostorová hloubka
definovaná poprvé v cˇ lánku (Tukey, 1975). • Poloprostorová hloubka je typický pˇredstavitel hloubky typu
D. • Velkou popularitu získala i simplexová hloubka definovaná
v (Liu, 1990). • Simplexová hloubka zastupuje hloubky typu A. • Hloubku typu C reprezentuje napˇríklad Mahalanobisova
−1 hloubka D(x, P) = 1 + MD(x, P) , hloubku typu B pak napˇríklad hloubka založená na objemu náhodného simplexu.
Semiparametrické kvantily
• Pro mnohorozmerné ˇ kvantily je možné použít definici
regresních kvantilu. ˚ • Místo regresní pˇrímky (kˇrivky), ale volíme vhodnou tˇrídu
ˇ uzavˇrených kˇrivek a místo uspoˇrádání vetší/menší volíme uspoˇrádání uvnitˇr/vneˇ (spolu se vzdáleností od kˇrivky). • Typicky volme parametrický tvar kˇrivky, proto jde o
semiparametrický pˇrístup. • Vhodné jsou napˇríklad elipsy. Pak jde o eliptické kvantily. • Vhodnout volbou ztrátové funkce snadno dostaneme
pˇrírozenou afinní ekvivarianci eliptických kvantilu˚ a tím pádem afinní invarianci pˇríslušné hloubky.
ˇ u, Mnoho rozmer ˚ problémy na obzoru
• Nekdy ˇ ˇ lze ˇríci, že nejaký bod není moc hluboko a jiný je. • Ale nekdy ˇ to tak jednoznaˇcné není.
Hloubka a klasifikace
• Chaudhuri a Ghosh (2005) zkoumali klasifikaci pomocí
maximální hloubky. • To se zdá být pˇrirozeným postupem a hloubkovou analogií
ˇ k verohodnostní klasifikaci. • Bohužel bayesovská optimalita muže ˚ být zaruˇcena pouze
ˇ pro unimodální elipticky symetrická rozdelení se stejnou varianˇcní maticí. • Na druhou stanu: to není pˇrekvapivé, protože v tom
ˇ hloubka odpovídá vyšší hustote. ˇ pˇrípadeˇ vetší
Nestejné rozptyly jsou problém
• Pˇredstavme si dveˇ rozdelení: ˇ N(0, 1) a N(0, 4). • Klasifikace pomocí hustot dává bayesovskou optimalitu:
klasifikujme do N(0, 1), pokud |x| <
8 log 2 3
1/2
.
• Proti tomu stojí fakt, že každý bod kromeˇ poˇcátku má
ˇ vuˇ hloubku vetší ˚ ci N(0, 1) než vuˇ ˚ ci N(0, 4). • Hlavní duvod ˚ je v invarianci hloubky (na rozdíl od hustoty,
která invariantní není).
ˇ D-D diagram pro dva výbery
• Vykreslíme dvojice D(x, P1 ), D(x, P2 ) , kde za bod x
dosazujeme pozorované body.
• Pamatujeme si, které pozorování patˇrí ke kterému výberu ˇ a
ˇ na této tréninkové skupineˇ zvolíme nejvhodnejší klasifikaˇcní kritérium. • Tento postup se poprvé objevuje v preprintu (Cuesta-Albertos a kol., 2009–10).
Jak obelstít invarianci?
• Místo maximální hloubky najdeme jiné pravidlo na
klasifikaci.
Jak obelstít invarianci?
• Napˇríkladu zmenou ˇ ˇ smernice obcházíme afinní invarianci
hloubky. Namísto klasifikace D(x, P1 ) >1⇒k =1 D(x, P2 ) ˇ použijeme pro nejakou vhodnou konstantu c pravidlo D(x, P1 ) > c ⇒ k = 1. D(x, P2 ) • To nápadneˇ pˇripomíná test pomerem ˇ ˇ verohodností. • Ale zárovenˇ se mužeme ˚ ptát, proˇc tak trváme na invarianci
hloubky, když ji potom obcházíme.
Invariance hloubky
• O užiteˇcnosti invariance pro statistické metody píše
Serfling (2010). • Jednorozmerné ˇ kvantily jsou ekvivariantní vuˇ ˚ ci libovolné
rostoucí transformaci. • Neco ˇ podobného ve více rozmerech ˇ je nedosažitelné. • Afinní invariance hloubky a z ní plynoucí afinní
ekvivariance kvantilu založeného na hloubce je asi ˇ rozumný požadavek na invarianci. nejsilnejší
Klasifikace pomocí hloubky
• Klasifikovat mnohorozmerná ˇ data pomocí bayesovského
ˇ ˇ je nároˇcné. kriteria (verohodnostn e) • Je složité a asymptoticky pomalé odhadnout hustoty. • Hloubka dat muže ˚ být vhodnou alternativou redukce
dimenze ke známé metodeˇ hlavních komponent. • Hloubka redukuje rozmer ˇ opravdu dukladn ˇ na ˚ e;
ˇ jednorozmernou hodnotu. • Jak jsme videli, ˇ je potˇreba ješteˇ druhý krok: vhodný
klasifikátor založený na hloubce. • Nabízí se, opet ˇ jakési bayesovské kritérium: odhadnout
ˇ u˚ v D-D diagramu. Poˇcet „hustotu“ jednotlivých výber ˇ u˚ je roven poˇctu tˇríd. rozmer
Na hloubce záleží
• Dvoustupnová ˇ klasifikace pomocí hloubky. • Spoˇcítejme hloubku každého bodu tréninkového výberu ˇ
ˇ vuˇ ˚ ci všem rozdelením. • Krok 1: místo puvodního ˚ pozorování použijme vektor
y = D(x, P1 ), . . . , D(x, Pk ) —redukce dimenze.
• Krok 2: na pozorováních Y odlad’me nejaké ˇ vhodné
klasifikaˇcní pravidlo. Toto pravidlo použijme na nová ˚ ci všem pozorování, respektive na jejich vektor hloubek vuˇ ˇ rozdelením. • V obou krocích je možné hledat optimální volbu.
Globální a pˇreci lokální
• Pokud má hloubka být co nejvhodnejší ˇ pro klasifikaci z
ˇ hlediska bayesovského pravidla, musí nejakým zpusobem ˚ ˇ ˇ zohlednovat lokální vlastnosti rozdelení, nebo • klasifikaˇcní pravidlo založené na hloubce musí být v
ˇ nejakém smyslu lokální. • Nabízejí se tedy dveˇ možnosti. • Použijeme lokální variantu hloubky. • Klasifikaˇcní pravidlo nebude založené jen na hodnoteˇ
hloubky.
Lokální hloubka
• K definici hloubky pˇriˇradíme váhovou funkci. • Napˇríklad vážená poloprostorová hloubka: každý bod v
daném poloprostoru dostane váhu odpovídající jeho ˇ ˇ vzdálenosti od smerového vektoru a od delící nadroviny. • Typicky ztratíme afinní invarianci hloubky, nekdy ˇ i
jednoznaˇcnost nejhlubšího bodu. • Získáme hloubkové kontury, které jsou ponekud ˇ bližší
konturám hustoty. • Výsledky klasifikace pomocí D-D diagramu se zlepší • Symetrickou variantu dostaneme vydelením ˇ vážených
ˇ pravdepodobností protilehlých poloprostoru. ˚
Nejblíže hlubocí sousedé
• Pozorování je zaˇrazeno do skupiny, kde Lebesgueova míra
množiny nejblíže hlubokých sousedu˚ je nejmenší • Jde o obdobu metody k nejbližších sousedu; ˚ blízkost není
dána geometrickou vzdáleností, ale hloubkou. • Tato metoda je podstatneˇ lepší než metoda nejvetší ˇ
hloubky. • Asymptotická optimalita se dá dokázat pro i pro nestejná
ˇ elipticky symetrická rozdelení.
ˇ erozm ˇ ˇ ˇ Hloubka a nekonecn erné veliciny
• Hloubka nepotˇrebuje k definici hustotu ani distribuˇcní
funkci. • Je vhodná i pro funkcionální data (není tˇreba se zabývat
ˇ rozdelením na funkˇcních prostorech). • Vetšina ˇ souˇcasných definic jsou hloubky typu A. • Kromeˇ funkˇcních hodnot lze do výpoˇctu zapojit i další
charakteristiky funkcí. Napˇríklad derivace.
8 6 4 2 0 −2
−2
0
2
4
6
8
Klasifikace funkcionálních dat
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
• Tato data sestávají z funkcí s mírneˇ odlišnou stˇrední
hodnotou a velmi rozdílnou kovarianˇcní strukturou. • Ukážeme si, jak moc závisí na volbeˇ hloubkového
funkcionálu.
0.0
−2
0
0.1
2
0.2
GLP
4
0.3
6
0.4
8
Hloubka Lopez-Pintado (2009)
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.1
0.2
0.3 GLP
0.4
−2
0.15 0.00
0
0.05
0.10
2
4
AKLP
0.20
6
0.25
8
0.30
ˇ hodnoty i derivace Hloubka zahrnující funkcní
0.0
0.2
0.4
0.6
0.8
1.0
0.00
0.05
0.10
0.15 AKLP
0.20
0.25
0.30
0.35
−2
0.10 0.00
0
0.05
2
4
RKLP
6
8
0.15
Hloubka zahrnující hlavneˇ derivaci
0.0
0.2
0.4
0.6
0.8
1.0
0.00
0.05
0.10 RKLP
0.15
0.20
GLP
0.0
0
0.1
2
0.2
4
0.3
6
0.4
8
Ješteˇ více názorný pˇríklad
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.1
0.2
0.3
0.4
0.15 0.00
0
0.05
2
0.10
AKLP
4
0.20
6
0.25
8
0.30
GLP
0.0
0.2
0.4
0.6
0.8
1.0
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.00
0
0.05
2
RKLP
4
0.10
6
0.15
8
AKLP
0.0
0.2
0.4
0.6
0.8
1.0
0.00
0.05
0.10 RKLP
0.15
0.20
