Diskriminační analýza
Diskriminační analýza
1/1
Diskriminační analýza
Data:
• (x/5i,... ,x/5P, Yi)T pro / = 1,..., n.
• x, = (x/i,... ,x/p)T je vektor (spojitých) regresorů .
• Y; udává příslušnost /-tého pozorování k dané skupině.
• Y; je kategoriální proměnná nabývající hodnot 1, 2,..., J.
Cíl: Na základě dat zkonstruovat rozhodovací pravidlo, které bude co nejlépe klasifikovat nová pozorování (x*l3... ,x*p)T do příslušné skupiny.
Metody diskriminační analýzy
• Úloha supervised learning (učení s učitelem).
o Zakladatel: R. A. Fisher (1936) - klasifikace kosatců (iris).
• Způsoby odvození klasifikačního pravidla:
• Kanonická diskriminační analýza (kombinace PCA a MANOVÁ - hledání nového souřadnicového systému, který maximalizuje podíl vnitro a meziskupinové variability).
Parametrické metody (lineární a kvadratická diskriminační analýza).
• Neparametrické metody (/c-nearest neighbors, metody založené na jádrových odhadech hustoty, na hloubce dat, apod.)
Parametrické metody - rozhodovací pravidla
• Nechť jsou naše data generována náhodným vektorem X = (Xi,... ,XP)/ a nechť Y značí náhodnou veličinu udávající příslušnost daného pozorování k dané skupině; Y nabývá hodnot 1, 2,..., J.
9 Předpokládejme, že známe hustotu rozdělení náhodného vektoru X pro j-tou skupinu, tj. nechť rozdělení X| Y = j má hustotu p/(x) (známá p-rozměrná hustota).
• V praxi se pro určení pravidel nejčastěji používá princip maximální věrohodnosti a Bayesovský přístup.
Princip maximální věrohodnosti: Pozorování x* zařaď do skupiny arg max{p/(x*);7 = 1,..., J}.
Bayesovský přístup: Pozorování x* zařaď do skupiny
arg max{p/(x*)7Ty; j" = 1,..., J}, kde ttj je apriorní pravděpodobnost, že
pozorování patří do skupiny j, tj. ttj = P(Y = j).
9 Bayesovské pravidlo minimalizuje pravděpodobnost špatné klasifikace.
Lineární diskriminační analýza
Předpokládejme, že p/(x) jsou hustoty p-rozměrného normálního rozdělení A/^,(/u.;, Z) se stejnými variančními maticemi Z.
P/W
exp<! -^(x-u)'Z *(x-/*.■)
V(2tt)p|Z
7
x G
• Bayesovské pravidlo - můžeme hledat maximum \og Pj(x)ttj = logp/(x) + logvr/.
• logp/(x) + \0g7Tj = \0g7Tj + ^-Z_1x - 1/2/XyE"1/^ + K\
• /-/(x) = logp/(x) + log7Ty = log7Ty + /ijZ_1x — 1/2/íJZ_1/íj se nazývá lineární diskriminační funkce - tu maximalizujeme přes j = 1,..., J.
9 K = -p/2log2vr- l/2log|Z| - l/2x/Z~1x nezávisí na j.
Diskriminační analýza
Lineární diskriminační analýza - praktické použití
• Na trénovacích datech nejprve odhadneme neznámé parametry modelu a poté model vyzkoušíme na testovacích datech.
• TVj neznáme, musíme je odhadnout. Pokud věříme proporcionálnímu zastoupení skupin v našich datech, pak ir; = — je relativní četnost j-té skupiny v datech (rij je počet pozorování z j-té skupiny). Jinak využijeme princip neurčitosti ttj = j - vede na princip maximální věrohodnosti.
fij odhadneme pomocí výběrového průměru v j-té skupině.
• Označme Sy odhad varianční matice v j-té skupině, pak společný odhad společné varianční matice je Z = -^j ((r?i — l)Si + ... + (nj — 1)Sj)
o Pro klasifikaci použijeme výběrovou verzi Lj(x), kde 7r/,/Xy a Z nahradíme jejich odhady.
Kvadratická diskriminační analýza
Předpokládejme, že p/(x) jsou hustoty p-rozměrného normálního rozdělení J\íp(fij, Ey).
p;(x)=v/(2^^expH(x" ^yz7l(x"
x e
• l0gp,(x) + log7T/ =
log 717 - 1/2 log |Z;| + tip]-1* - l/2/*;zrV; - l/2x'Zr1x + K\
• (?;(x) = log 717 - 1/2 log |Z;| + /a^x - 1/2/*;Z/V; - l/2x'Zr1x se nazývá kvadratická diskriminační funkce - tu maximalizujeme přes
7    1,..., w/.
9 K = —p/2 log27t nezávisí na 7.
Diskriminační analýza
7/1
Kvadratická diskriminační analýza - praktické použití
• Na trénovacích datech nejprve odhadneme neznámé parametry modelu a poté model vyzkoušíme na testovacích datech.
• Pro klasifikaci použijeme výběrovou verzi Q/(x), kde 7r/,/Xy a Ey nahradíme jejich odhady.
Neparametrická diskriminační analýza
• Idea: hustotu p/(x) pro J-tou skupinu neznáme - odhadneme ji pomoci trénovacích dat.
• Typicky se uvažují jadrové odhady hustot p/(x), označme je p/(x).
• Upravíme Bayesovské rozhodovací pravidlo: Pozorovaní x* zařaď do skupiny arg max{p/(x*)7ry; j" = 1,..., J}.
• Výpočetně náročné (obzvláště ve vyšších dimenzích).
• Ve vyšších dimenzích trpí prokletím dimenzionality (odhady hustot mají obrovskou variabilitu - jsou nepřesné).
Metoda k nejbližších sousedů
o k nearest neighbors (kNN).
9 Zvolíme nějakou vzdálenost (např. Mahalanobisovu) v mp.
Pro dané pozorování x* najdeme jeho k nejbližších sousedů (v této vzdálenosti).
• Upravíme Bayesovské rozhodovací pravidlo, P/(x*) odhadneme pomoci " histogramu" na základě k nejbližších sousedů.
• P/(x*) = ^7, kde kj je počet pozorování ze skupiny j mezi k nejbližšími sousedy x*.
o Pozorování x* zařaď do skupiny
argmax{j5-(x*)7t/;y = 1,..., J} = arg max {^717:7 = 1,..., J j.
• Odhadneme-li ttj pomocí relativních četností, pak x* zařaď do skupiny arg n\ax{kj\j = 1,..., J}. Tedy x* zařaď do skupiny, která je nejčastěji zastoupena mezi k nejbližšími sousedy x*.
Metody založené na hloubce dat
o Maximal depth classifier.
• Pozorování x* zařaď do skupiny arg max{D(x*, Pj)\j = 1,..., J}. o D(x*, Pj) je hloubka bodu x* vzhledem k rozdělení j-té skupiny Pj.