Diskriminační analýza

Historie a využití v současnosti

Za zakladatele DA je považován sir Ronald Aylmer Fisher, který ve své práci z roku 1936 použil metodu dnes označovanou jako Fisherova diskriminační analýza ke klasifikaci druhového jména rostlin kosatců na základě čtyř pozorovaných znaků. Metodu demonstroval na datech známých jako Iris flower data set.

Zpočátku byla DA využívána v biologii k třídění rostlin a zemědělských plodin, dále také v medicíně a v antropologii při klasifikaci koster. Širšího uplatnění se dočkala teprve s rozmachem výpočetní techniky, která umožnila rychle zpracovávat větší množství dat. +more V roce 1954 ji použili Maurice M. Tatsuoka a David V. Tiedeman v oblasti sociologie k psychologickým testům. William R. Klecka v roce 1980 například aplikoval DA na sledování obyvatelstva v průběhu voleb, tedy v politice. V bankovnictví se DA používala k rozhodování o přidělení úvěrů (tedy ke klasifikaci klientů dle solventnosti) a k odhalování podezřelých finančních transakcí.

V současnosti DA nalézá stále uplatnění v lékařství při stanovování diagnóz a určování rizikových skupin pacientů a rovněž v numerické taxonomii (fenetice), tedy ke klasifikaci rostlin a živočichů. Další oblastí, kde se DA participuje je rozpoznávání tváří (face recognition), nebo obecněji v rozpoznávání tvarů (pattern recognition), a dále například v kybernetice. +more Modely lineární DA se rovněž používají ve finančnictví a v marketingu, například také k předvídání krachů firem (bankruptcy prediction).

Základní principy DA

Předpoklady úlohy DA a značení v textu

V celém textu \mathbb{R} značí množinu reálných čísel a \mathbb{N} množinu přirozených čísel.

Nechť n \in \mathbb{N}, k \in \mathbb{N}, n \gg k, d \in \mathbb{N}. Diskriminační analýzu používáme v situaci, kdy chceme rozlišit n\,\. +more objektů pocházejících z k\,\. disjunktních tříd (tzn. každý objekt pochází z právě jedné třídy) pouze na základě zvolených znaků, které na objektech pozorujeme. Soubor znaků \mathbf{x} sledovaných na jednom objektu reprezentujeme obecně d\,\. -rozměrným reálným vektorem, \mathbf{x} \in \mathbb{R}^d. Přitom předpokládáme, že znaky pozorované na objektech ze stejné třídy respektují stejné pravděpodobnostní rozdělení na množině \mathbb{R}^d. Naopak po rozděleních znaků z různých tříd je přirozené požadovat, aby se vzájemně lišila, jinak nemá smysl diskriminační analýzu provádět.

V textu jsou jednotlivé třídy opatřeny indexy a značí se T_i\,\! pro i=1,...,k\,\!.

Pravděpodobnostní míru definovanou na měřitelném prostoru (\mathbb{R}^d,\mathcal{B}(\mathbb{R}^d)) udávající rozdělení pozorovaných znaků na objektech z třídy T_i\,\. označujeme P_i\,\. +more pro i=1,. ,k\,\. Jestliže rozdělení P_i\,\. jsou absolutně spojitá vzhledem k d\,\. -rozměrné lebesgueově míře na \mathbb{R}^d, pak vůči ní mají také hustotu pravděpodobnosti. V textu pak značíme malým písmenem p_i\,\. hustotu pravděpodobnosti rozdělení znaků pozorovaných na objektech z třídy T_i\,\.

Čtenář, který není dostatečně obeznámen s teorií pravděpodobnosti může (byť s malou újmou na obecnosti, ne však takovou, která by znemožnila pochopení textu) předpokládat, že hustoty pravděpodobnosti rozdělení znaků ve všech třídách existují. Hustotu si pak může představovat jako funkci definovanou na všech možných znacích (na \mathbb{R}^d), zobrazující do množiny nezáporných čísel (do \mathbb{R}_0^+), která udává „jak často“ se daný znak vyskytuje při velkém počtu pozorování. +more Přesněji, integrál z hustoty p_i\,\. přes nějakou oblast znaků A\,\. určuje, s jakou pravděpodobností na náhodně zvoleném objektu z třídy T_i\,\. budeme pozorovat znak z oblasti A\,\. , pro i=1,. ,k\,\. o.

Dále se zpravidla předpokládá modelová situace, že náhodně zvolený objekt pochází z třídy T_i\,\. s pravděpodobností \pi_i\,\. +more pro i=1,. ,k\,\. , takže rozdělení P_i\,\. pak mají význam podmíněných rozdělení s podmínkou, že objekt pochází z třídy T_i\,\. Jestliže existují hustoty p_i\,\. , pak celková směs má hustotu pro \mathbf{x} \in \mathbb{R}^d danou jako :p(\mathbf{x})= \sum_{i=1}^k \pi_i \, p_i(\mathbf{x}). Na náhodně zvoleném objektu tedy modelově naměříme znak \mathbf{x} s pravděpodobností, která je daná hustotou p(\mathbf{x}).

Rozhodovací pravidlo

V DA se objekty rozlišují na základě rozhodovacího pravidla. * Deterministické rozhodovací pravidlo je zobrazení definované na množině všech přípustných znaků pozorovaných na objektech (uvažujeme obecně \mathbb{R}^d), které zobrazuje do množiny tříd, tj. +more do množiny \{T_1,. ,T_k\}\,\. Deterministickým pravidlem je tedy rozlišení objektů jednoznačně určeno. Aplikací tohoto pravidla na vektor znaků příslušící nějakému objektu totiž začlení objekt do právě jedné ze tříd. Každé deterministické rozhodovací pravidlo lze charakterizovat uspořádaným souborem (k \,\. -ticí) disjunktních množin pokrývajících množinu přípustných znaků (dále rozkladem) \{W_1,. ,W_k\} \,\. Stačí pro dané zobrazení ztotožnit úplný vzor T_i\,\. s množinou W_i\,\. pro i=1,. ,k \,\. Množinu všech rozkladů (resp. pravidel) budeme značit \mathcal{W} .

Ideálním rozhodovacím pravidlem je pravidlo, které začleňuje objekty do tříd, z nichž skutečně pochází. To samozřejmě prakticky téměř nikdy nelze zajistit. +more Okolí nějakého vektoru (zpravidla rozsáhlá podmnožina \mathbb{R}^d) může mít tu vlastnost, že s významnou pravděpodobností se příslušné znaky (vektory z tohoto okolí) objevují na objektech z více než jedné třídy. Pozorujeme-li objekt se znaky z tohoto okolí, pak se nedokážeme jednoznačně (resp. na nějaké úrovni spolehlivosti) rozhodnout, ze které třídy objekt pochází. Pro lepší představu o rozlišení objektů se proto někdy zavádí následující zobecnění deterministického pravidla.

* Znáhodněné (randomizované) rozhodovací pravidlo je vektorová funkce definovaná také na množině všech znaků zobrazující ale do [0,1]^k\,\. (tj. +more do kartézského součinu k\,\. uzavřených jednotkových intervalů), přičemž jednotlivé složky obrazu vektoru znaků příslušící nějakému objektu odpovídají pravděpodobnostem zařazení tohoto objektu do příslušných tříd.

Deterministické rozhodovací pravidlo je speciálním případem znáhodněného. Lze totiž uvažovat u znáhodněného pravidla pouze vektorové funkce zobrazující do \{0,1\}^k\,\. +more a ztotožnit kanonický vektor e_i\,\. s třídou T_i\,\. u deterministického pravidla.

Formulace úlohy DA

Úloha diskriminační analýzy se obecně skládá z více částí.

V první části předpokládáme, že na malé skupině z velkého počtu n\,\. daných objektů (na tzv. +more trénovací množině) jsme schopni určit, z jaké třídy objekty pocházejí, resp. pro libovolnou třídu jsme schopni označit nějakou skupinu objektů, o kterých víme, že pocházejí z této třídy. Přitom uvažujeme, že takový postup přesného zařazení je pro větší skupiny objektů „nákladnější“, nebo časově náročnější, a přesné zařazení všech n\,\. objektů je z hlediska těchto nákladů nepřípustné. Prvním úkolem DA je proto vhodně zvolit trénovací množinu.

V diskriminační části je úkolem na základě znaků pozorovaných na objektech ve zvolené trénovací množině sestavit rozhodovací pravidlo, tedy prediktor pro třídění zbylých objektů. Po rozhodovacím pravidle se obvykle požaduje, aby následovalo některé z kritérií uvedených v sekci Kritéria rozhodovacích pravidel. +more V dalších sekcích jsou naznačeny důvody, proč se tato kritéria jeví jako vhodná. V sekci s tradičními přístupy jsou pak popsány nejčastější postupy, kterými se dojde od modelového kritéria k explicitnímu vyjádření rozhodovacího pravidla.

Úkolem klasifikační části je rozčlenění zbylých objektů dle sestaveného rozhodovacího pravila, což je ryze výpočetní záležitost.

Součástí DA (stejně jako každé statistické procedury) by měla být správná interpretace kvality výsledného roztřídění, neboli odhad pravděpodobností chybné klasifikace.

Příklady použití

V medicíně se DA využívá ke stanovení diagnózy na základě testů. Nejprve se za trénovací množinu vezme skupina pacientů doplněná několika zdravými jedinci. +more Předpokládá se, že u pacientů již byla nějaká z k-1\,\. nemocí diagnostikována dříve, k\,\. -tá třída znamená, že jedinec z této třídy je zdravý (nebo aspoň nemá žádnou ze sledovaných chorob). Trénovací množina se podrobí sérii d\,\. různých druhů testů. Na základě výsledků těchto testů pak slouží teorie DA k sestavení pravidla pro určení diagnózy dalších osob na základě série stejných d\,\. testů. Znáhodněné rozhodovací pravidlo například poskytne po otestování osoby informaci o tom, s jakou pravděpodobností trpí nějakou z k-1\,\. chorob a pravděpodobnost, s jakou netrpí na žádnou z těchto chorob. Důležité je určit také spolehlivost pravidla. Pokud budou pacienti testováni takovými testy, jejichž výsledek vůbec nesouvisí s žádnou nemocí, pak sestavené pravidlo ani nemůže být spolehlivé. * V bance může DA sloužit k rozhodnutí o přidělení úvěru. Pro jeden daný úvěrový produkt se tedy pracuje pouze s k=2\,\. třídami. Klienti z první třídy jsou například ti spolehlivější, kteří celý úvěr splatí (s velmi malým rizikem nesplacení, např. 1% až 5%; nesplacení úvěru je pro banku spojeno s náklady). Banka si vede v evidenci u každého klienta několik znaků, jako např. druh zaměstnání, výše platu, apod. Na základě dat z minulosti pak může využít DA k sestavení pravidla, které dokáže rozhodnout o přidělení úvěru na základě dotazovaných znaků. * Podobně se může škola rozhodovat o přijetí či nepřijetí studenta. Lze například sledovat výsledky z předchozích studií a výsledky přijímacích testů, a jednotlivé třídy pak mohou znamenat rok ukončení studia, a další třídy úspěšné absolvování studia, případně absolvování s vyznamenáním.

Kritéria rozhodovacích pravidel

Nechť \mu_i \,\! je střední hodnota a \Sigma_i \,\! rozptyl rozdělení znaků v třídě T_i\,\! pro i=1,...,k\,\!.

* Kritérium minimální Mahalanobisovy vzdálenosti zařazuje prvek se znaky \mathbf{x} \in \mathbb{R}^d do třídy s indexem :: j=\begin{matrix} \\ \operatorname{arg\,min} \\ { }^{i=1,...,k} \end{matrix} \ (\mathbf{x}-\mu_i)^T \Sigma_i^{-1} (\mathbf{x}-\mu_i),

:tedy do takové třídy, která je nejblíže k vektoru \mathbf{x} ve smyslu Mahalanobisovy vzdálenosti.

Následující dvě kritéria mají smysl, existují-li hustoty p_i \,\! rozdělení P_i \,\! v třídách T_i\,\! pro i=1,...,k\,\!.

* Kritérium maximální věrohodnosti zařazuje prvek se znaky \mathbf{x} \in \mathbb{R}^d do třídy s indexem :: j=\begin{matrix} \\ \operatorname{arg\,max} \\ { }^{i=1,...,k} \end{matrix} \ p_i(\mathbf{x}).

* Bayesovo kritérium zařazuje prvek se znaky \mathbf{x} \in \mathbb{R}^d do třídy s indexem :: j=\begin{matrix} \\ \operatorname{arg\,max} \\ { }^{i=1,...,k} \end{matrix} \ \pi_i \, p_i(\mathbf{x}).

Je ihned patrné, že Bayesovo kritérium je zobecněním kritéria maximální věrohodnosti, které zohledňuje apriorní pravděpodobnosti tříd. Anebo opačně můžeme říci, že kritérium maximální věrohodnosti je speciálním případem Bayesova kritéria, které využívá princip neurčitosti a za odhad apriorních pravděpodobností klade :\hat{\pi}_1=. +more=\hat{\pi}_k=\frac{1}{k} .

V následující sekci je demonstrováno, že Bayesovo pravidlo minimalizuje celkovou střední ztrátu vzniklou nesprávnou klasifikací pro konkrétní ohodnocení dílčích ztrát.

* Fisherovo kritérium zařazuje prvek se znaky \mathbf{x} \in \mathbb{R}^d do třídy s indexem :: j=\begin{matrix} \\ \operatorname{arg\,min} \\ { }^{i=1,...,k} \end{matrix} \ |\mathbf{a}^T \mathbf{x} - \mathbf{a}^T \mu_i| , :kde pro matici mezitřídní variability \mathbf{B} a matici vnitrotřídní variability \mathbf{W} je ::\mathbf{a}=\begin{matrix} \\ \operatorname{arg\,max} \\ { }^{\mathbf{w} \in \mathbb{R}^d} \end{matrix} \ \frac{\mathbf{w}^T \mathbf{B} \mathbf{w}}{\mathbf{w}^T \mathbf{W} \mathbf{w}} .

Podrobněji se Fisherově metodě věnuje samostatná sekce.

Ekonomické ocenění rozhodovacího pravidla

Cílem sekce je ukázat jakým způsobem se převádí úloha výběru třídy na srovnávání skórů jednotlivých tříd pro daný znak \mathbf{x}. V této sekci se pracuje s pojmem střední hodnota, která (jednoduše řečeno) vyjadřuje „nejvíce očekávanou“ hodnotu pozorování na nějaké náhodné veličině (resp. +more náhodném vektoru).

Předpokládejme, že znak pozorovaný na náhodně zvoleném objektu je náhodný vektor \mathbf{X}, který se řídí distribucí (pravděpodobnostním rozdělením) směsi s hustotou p \,\. popsané v odstavci s předpoklady, a příslušná podmíněná rozdělení mají hustoty p_i \,\. +more pro i=1,. ,k \,\. Dále si zvolme nějaké rozhodovací pravidlo dané rozkladem \{W_1,. ,W_k\} \in \mathcal{W} a oceňme ztrátu vzniklou použitím tohoto pravidla.

Označme r_{ij} \,\. hodnotu ztráty vzniklé zobrazením objektu pocházejícího z třídy T_i \,\. +more zvoleným pravidlem na třídu T_j \,\. Objekt se znaky \mathbf{X} zobrazíme na třídu T_j \,\. , jestliže \mathbf{X} \in W_j. Takže za podmínky, že objekt se znaky \mathbf{X} pochází ze třídy T_i \,\. , je pravděpodobnost zobrazení tohoto objektu na třídu T_j \,\. dána jako :L_{ij} = \int_{W_j} p_i(\mathbf{x}) \mathrm{d} \mathbf{x}.

Střední hodnota ztráty za podmínky, že objekt se znaky \mathbf{X} pochází ze třídy T_i \,\!, pak má tvar :L_{i} = \sum_{j=1}^k r_{ij} \, L_{ij} .

Protože předpokládáme, že náhodně zvolený objekt pochází z třídy T_i \,\. s pravděpodobností \pi_i \,\. +more pro i=1,. ,k \,\. , je celková střední ztráta dána vztahem :L = \sum_{i=1}^k \pi_i \, L_{i} .

Z ekonomického hlediska je samozřejmě optimální preferovat pravidlo minimalizující celkovou střední ztrátu, tedy pravidlo : \{W_1^*,. ,W_k^*\} = \begin{matrix} \\ \operatorname{arg\,min} \\ { }^{\{W_1,. +more,W_k\} \in \mathcal{W}} \end{matrix} \ L = \begin{matrix} \\ \operatorname{arg\,min} \\ { }^{\{W_1,. ,W_k\} \in \mathcal{W}} \end{matrix} \ \sum_{i=1}^k \pi_i \sum_{j=1}^k r_{ij} \int_{W_j} p_i(\mathbf{x}) \mathrm{d} \mathbf{x} .

Pro j=1,...,k \,\! se definuje j \,\!-tý diskriminační skór pro znak \mathbf{x} \in \mathbb{R}^d jako : S_j(\mathbf{x}) = - \sum_{i=1}^k \pi_i \, r_{ij} \, p_i(\mathbf{x}) .

Celková střední ztráta vyjádřená pomocí skórů je pak :L(\{W_1,...,W_k\}) = - \sum_{j=1}^k \int_{W_j} S_{j}(\mathbf{x}) \mathrm{d} \mathbf{x} .

Pro dané parametry úlohy \pi_1,. ,\pi_k, \, p_1,. +more,p_k \,\. a dané hodnoty ztrát r_{ij}\,\. pro i,j=1,. ,k \,\. jsou jednotlivé skóry jednoznačně určeny. Pro tyto hodnoty je optimálním pravidlem takové pravidlo, které maximalizuje příslušné integrály správným nastavením integračních oblastí \{W_1,. ,W_k\}\,\. Tento požadavek lze vždy zajistit volbou takového pravidla, které se řídí dle hodnot nejvyššího skóru (proto také název skór nebo skóre) a objekt se znakem \mathbf{x} zařazuje do třídy : j=\begin{matrix} \\ \operatorname{arg\,max} \\ { }^{i=1,. ,k} \end{matrix} \ S_i(\mathbf{x}) .

Opačně lze také snadno ukázat, že pravidlo, které se řídí nejvyšším skórem, nabývá mezi všemi pravidly minimální celkové střední ztráty. Z toho důvodu je „ekonomicky nejvýhodnější“ nejprve pro všechny třídy určit (odhadnout) skóry (jakožto funkce \mathbf{x}) a jednotlivé objekty v klasifikační části zařazovat do takové třídy, která má při pozorovaném znaku \mathbf{x} nejvyšší skór.

Běžně se volí hodnoty ztrát r_{ij}=1 \,\. pro i \ne j \,\. +more a r_{ii}=0 \,\. V takovém případě lze j \,\. -tý skór dále upravit na tvar : S_j(\mathbf{x}) = - \sum_{i \ne j} \pi_i \, p_i(\mathbf{x}) = \pi_j \, p_j(\mathbf{x}) - \sum_{i=1}^k \pi_i \, p_i(\mathbf{x}) = \pi_j \, p_j(\mathbf{x}) - p(\mathbf{x}) .

Protože hustota celkové směsi p \,\. je v každém skóru S_j \,\. +more stejná pro j=1,. ,k \,\. , je srovnávání skórů pro daný znak \mathbf{x} ekvivalentní srovnávání výrazů \pi_j \, p_j(\mathbf{x}) \,\. pro j=1,. ,k \,\. , což přesně odpovídá Bayesovu kritériu z předchozí sekce.

Fisherova DA

Uvažujme, že na náhodně zvoleném objektu naměříme náhodný vektor znaků \mathbf{X}. Idea Fisherova postupu spočívá v nalezení takové lineární transformace \mathbf{a} \in \mathbb{R}^d vektoru \mathbf{X}, při které se maximalizuje poměr součtu čtverců mezi třídami ku součtu čtverců uvnitř tříd. +more Jinými slovy, chceme nalézt takovou lineární funkci, která nejvíce eliminuje chybovou složku a umožní co nejlépe rozlišit objekty mezi jednotlivými třídami.

Z (mnohorozměrné) analýzy rozptylu (ANOVA, analysis of variance) víme, že celková variabilita vektoru \mathbf{X}, (ko)varianční matice \mathbf{T} (total variability), lze rozložit na součet matice mezitřídní variability \mathbf{B} (between-classes variability) a matice variability uvnitř tříd \mathbf{W} (within-classes variability). Obdobně pro rozptyly (jednorozměrné) náhodné veličiny \mathbf{a}\mathbf{X} platí následující vztah :Q_{T} = \operatorname{var}\, ( \mathbf{a}\mathbf{X} ) =\mathbf{a}^T\mathbf{T}\,\mathbf{a} =\mathbf{a}^T\mathbf{W}\,\mathbf{a} + \mathbf{a}^T\mathbf{B}\,\mathbf{a}= Q_{W} + Q_{B} .

Fisherova lineární diskriminační funkce je taková funkce, která maximalizuje Fisherův poměr, tj. splňuje :\mathbf{a}=\begin{matrix} \\ \operatorname{arg\,max} \\ { }^{\mathbf{w} \in \mathbb{R}^d} \end{matrix} \ \frac{Q_B}{Q_W}=\begin{matrix} \\ \operatorname{arg\,max} \\ { }^{\mathbf{w} \in \mathbb{R}^d} \end{matrix} \ \frac{\mathbf{w}^T \mathbf{B}\, \mathbf{w}}{\mathbf{w}^T \mathbf{W} \,\mathbf{w}} .

Fisherův kanonický směr.

Na obrázku vpravo jsou znázorněna pozorování dvou znaků (d=2 \,\. ) na objektech ze dvou tříd (k=2 \,\. +more). Na objektech z jedné třídy jsou pozorované znaky znázorněné modře a na objektech z druhé třídy červeně. V levé části jsou znaky projektovány na přímku s nějakým náhodně zvoleným směrem. V pravé části jsou znaky projektovány na přímku se směrem odpovídajícím vektoru \mathbf{a}. Projekce vpravo mezi všemi možnými projekcemi umožňuje nejlépe rozlišit naměřené znaky.

Označíme-li N_i \,\. počet prvků v trénovací množině pocházejících z třídy T_i \,\. +more pro i=1,. ,k\,\. a N=N_1+. +N_k \,\. celkový počet prvků v trénovací množině, pak jednotlivé matice se odhadují takto :\mathbf{T} = \sum_{i=1}^k \sum_{j=1}^{N_i} (\mathbf{X}_{ij}-\hat\mu)(\mathbf{X}_{ij}-\hat\mu)^T , :\mathbf{B} = \sum_{i=1}^k {N_i} (\hat\mu_i-\hat\mu)(\hat\mu_i-\hat\mu)^T , :\mathbf{W} = \sum_{i=1}^k \sum_{j=1}^{N_i} (\mathbf{X}_{ij}-\hat\mu_i)(\mathbf{X}_{ij}-\hat\mu_i)^T , kde \mathbf{X}_{ij} jsou prvky z třídy T_i \,\. pro j=1,. ,N_i, \, i=1,. ,k\,\. a.

:\hat{\mu} = \frac{1}{N} \sum_{i=1}^{k} \sum_{j=1}^{N_i} \mathbf{X}_{ij},\ \hat{\mu}_i = \frac{1}{N_i} \sum_{j=1}^{N_i} \mathbf{X}_{ij} pro i=1,...,k\,\! .

Je-li \mathbf{w}_1 vlastní vektor příslušící největšímu vlastnímu číslu matice \mathbf{W}^{-1} \mathbf{B} (místo vlastní číslo a vlastní vektor se také používají názvy charakteristické číslo a charakteristický vektor, vizte spektrální rozklad matice), pak lze ukázat, že \mathbf{w}_1 maximalizuje Fisherův poměr, takže můžeme vždy položit \mathbf{a}=k \, \mathbf{w}_1, pro libovolný nenulový násobek k \in \mathbb{R}.

Fisherovo diskriminační kritérium pak zařazuje objekt se znaky \mathbf{x} do takové třídy, jejíž obraz střední hodnoty znaků v transformaci \mathbf{a} je nejblíže obrazu \mathbf{x} (měří se vzdálenost na přímce), neboli do třídy :j=\begin{matrix} \\ \operatorname{arg\,min} \\ { }^{i=1,...,k} \end{matrix} \ |\mathbf{a}^T \mathbf{x} - \mathbf{a}^T \mu_i| .

Fisherův poměr je analogií technického pojmu poměr signálu a šumu (SNR, signal to noise ratio). Na přiloženém obrázku je znázorněno pro jednorozměrný případ (d=1 \,\. +more), jak ovlivňuje nastavení hranice rozlišující nějaký signál od šumu (jiného signálu, který nás nezajímá) poměr správných klasifikací signálu (hits), správných zamítnutí, že jde o signál (correct rejections), nesprávné klasifikace, že jde o signál, jedná-li se o šum (false alarms), a nesprávné klasifikace, že jde o šum, jedná-li se skutečně o signál (misses). Zelenou barvou je v obrázku znázorněna hustota výskytu signálu, který sledujeme, a červenou barvou hustota nějakých jiných signálů (šumu). Zmíněná hranice (criterion) je znázorněna svislou čarou. Příchozí události, které vykazují hodnoty (znaky) vpravo od svislé čáry pravidlo klasifikuje jako signál, hodnoty vlevo jako šum. Pravidlo na obrázku (dané svislou čarou) je vychýlené od pravidla, které bychom získali DA. Obrázek je výstupem kódu pro program Mathematica. Bližší informace o demonstraci (kódu) lze získat kliknutím na následující [url=http://demonstrations. wolfram. com/SignalDetectionTheory/]odkaz[/url].

Wilksovo lambda

Wilksovo lambda je testová statistika, která se používá v mnohorozměrné analýze rozptylu k testování hypotézy odlišnosti průměrů znaků v jednotlivých třídách. Wilksovo lambda nabývá hodnot z intervalu [0,1] \,\. +more, přičemž vyšší hodnoty znamenají, že průměry se liší méně. Při značení z předchozího odstavce se Wilksovo lambda definuje jako :\Lambda = \frac{\operatorname{det} \, \mathbf{W}} {\operatorname{det} \, \mathbf{T}} = \frac{ \operatorname{det} \, \mathbf{W} } {\operatorname{det} \, ( \mathbf{W} + \mathbf{B} )} . Čím nižší jsou hodnoty Wilksova lambda, tím spolehlivější je výsledek diskriminační části DA. Hodnota \Lambda = 0 \,\. tedy odpovídá „perfektní diskriminaci“ objektů a hodnota \Lambda = 1 \,\. znamená, že výsledek (lineární) DA nemá význam, protože objekty na základě pozorovaných znaků prakticky není možné rozlišit (lineární funkcí).

Další tradiční přístupy a speciální případy DA

Tato sekce se zaměřuje na diskriminační část DA. Nechť trénovací množina obsahuje N\,\. +more prvků. Pokud apriorní pravděpodobnosti tříd \pi_1,. ,\pi_k \,\. nejsou známé, lze použít jejich odhad pro i=1,. ,k \,\. pomocí relativních četností :\hat{\pi}_i = \frac{N_i}{N} , kde N_i \,\. je počet prvků v trénovací množině pocházejících z třídy T_i \,\. V některých případech ale trénovací množina nemusí věrně reprezentovat skutečné relativní zastoupení prvků z příslušných tříd, například pokud do ní objekty nevybíráme náhodně. V takovém případě volíme odhad :\hat{\pi}_1=. =\hat{\pi}_k=\frac{1}{k} . Dále v úloze DA v zásadě rozlišujeme dva základní přístupy.

* Parametrický přístup předpokládá, že pro i=1,. ,k\,\. +more jsou rozdělení P_i\,\. znaků v třídě T_i \,\. některá ze známých typů rozdělení charakterizovaných nějakým vektorem parametrů, a spočívá tedy v odhadu těchto parametrů. Nejčastěji se pracuje s normálními rozděleními, která jsou charakterizovaná střední hodnotou a rozptylem. K odhadu těchto parametrů se standardně využívají výběrový průměr a výběrová varianční matice, tedy pro i=1,. ,k\,\. klademe ::\hat{\mu}_i = \frac{1}{N_i} \sum_{j=1}^{N_i} \mathbf{X}_{ij}, \ \hat{\Sigma}_i = \frac{1}{N_i-1} \sum_{j=1}^{N_i} (\mathbf{X}_{ij}-\hat{\mu}_i)(\mathbf{X}_{ij}-\hat{\mu}_i)^T, :kde \mathbf{X}_{ij} pro j=1,. ,N_i \,\. jsou prvky z třídy T_i \,\. pro i=1,. ,k \,\. Pokud předpokládáme rovnost variančních matic ve všech třídách \Sigma_1=. =\Sigma_k=\Sigma \,\. , pak používáme odhad ::\hat{\Sigma} = \frac{1}{N-k} \sum_{i=1}^{k} \sum_{j=1}^{N_i} (\mathbf{X}_{ij}-\hat{\mu}_i)(\mathbf{X}_{ij}-\hat{\mu}_i)^T. :Jestliže tedy předpokládáme normalitu všech rozdělení, pak příslušné hustoty pro i=1,. ,k \,\. odhadneme dosazením odhadnutých parametrů, tj pro \mathbf{x} \in \mathbb{R}^d ::\hat{p}_i(\mathbf{x}) = (2\pi)^{-\frac{d}{2}} (\operatorname{det} \, \hat{\Sigma}_i)^{-\frac{1}{2}} e^{-\frac{1}{2} (\mathbf{x}-\hat{\mu}_i)^T \hat{\Sigma}_i^{-1} (\mathbf{x}-\hat{\mu}_i)} . : Dosazením získaných odhadů do některého z kritérií již získáme explicitně vyjádřené rozhodovací pravidlo.

* Neparametrický přístup používáme, pokud nemáme žádnou apriorní informaci o rozděleních P_1,. ,P_k \,\. +more V této situaci se nabízí využít neparametrické metody odhadu hustot, např. jádrový odhad hustot. Pro další informace o neparametrickém přístupu v DA vizte článek M. Forbelské.

Pro DA pracující s diskrétními rozděleními P_1,...,P_k \,\! se používá název diskriminační korespondenční analýza.

Problémem parametrických modelů bývá citlivost na malé porušení předpokladu o rozdělení dat, které může výrazně ovlivnit výsledek DA. Jde především o odlehlá pozorování (vzniklá například nepřesným měřením), která mají vliv na hodnotu výběrového průměru i rozptylu. +more Jednou z alternativ je pak užití robustních metod, jejichž cílem je tyto nepříznivé vlivy eliminovat. V souvislosti s aplikací těchto metod v DA hovoříme o robustní diskriminační analýze, které se podrobněji věnuje diplomová práce E. Horákové.

Kvadratická diskriminační analýza (QDA)

Pokud v úloze DA předpokládáme, že rozdělení P_i\,\. znaků v jednotlivých třídách T_i\,\. +more pro i=1,. ,k\,\. jsou regulární d \,\. -rozměrná normální rozdělení N_d(\mu_i,\Sigma_i) \,\. a pro diskriminaci objektů volíme Bayesovo kritérium, pak mluvíme o úloze kvadratické diskriminační analýzy. Dosazením hustoty P_i \,\. lze Bayesovo kritérium upravit logaritmováním a odečtením konstanty (vzhledem k i\,\. ). : \begin{matrix} \\ \operatorname{arg\,max} \\ { }^{i=1,. ,k} \end{matrix} \, (\pi_i \, p_i(\mathbf{x})) = \begin{matrix} \\ \operatorname{arg\,max} \\ { }^{i=1,. ,k} \end{matrix} \, \operatorname{ln}(\pi_i \, p_i(\mathbf{x})) = \begin{matrix} \\ \operatorname{arg\,max} \\ { }^{i=1,. ,k} \end{matrix} \, ( \operatorname{ln} \, \pi_i -\frac{1}{2}\operatorname{ln}(\operatorname{det} \, \Sigma_i)-\frac{1}{2}(\mathbf{x}-{\mu}_i)^T {\Sigma}_i^{-1} (\mathbf{x}-{\mu}_i)) .

Výsledek kvadratické diskriminační analýzy.

Pro i=1,...,k, \ \mathbf{x} \in \mathbb{R}^d se výraz : S_i(\mathbf{x})= \operatorname{ln} \, \pi_i -\frac{1}{2}\operatorname{ln}(\operatorname{det} \, \Sigma_i)-\frac{1}{2}(\mathbf{x}-{\mu}_i)^T {\Sigma}_i^{-1} (\mathbf{x}-{\mu}_i)

nazývá i\,\. -tý kvadratický diskriminační skór. +more Objekt s pozorovanými znaky \mathbf{x} tedy v kvadratické DA zařazujeme do třídy T_j \,\. , jestliže : j=\begin{matrix} \\ \operatorname{arg\,max} \\ { }^{i=1,. ,k} \end{matrix} \, S_i(\mathbf{x}) .

Jeden z možných výsledků kvadratické diskriminační analýzy ukazuje obrázek vpravo. Jsou na něm zakreslena pozorování dvou znaků (d=2 \,\. +more) na objektech ze dvou tříd (k=2 \,\. ). Znaky pozorované na objektech první třídy jsou zakresleny červenými body, znaky druhé modrými body. Za výsledek se v obrázku považuje rozklad \{ W_1,W_2 \} \,\. roviny \mathbb{R}^2 \,\. , kde W_1 \,\. označuje červenou oblast, W_2 \,\. modrou. Pokud bychom v klasifikační části DA pozorovali objekt s vektorem znaků \mathbf{x}, který patří do červené oblasti W_1 \,\. , zařadili bychom takový objekt podle výsledného pravidla do první (červené) třídy T_1 \,\. Jak je vidět, hranicí mezi oběma oblastmi je kuželosečka. Ve vyšší dimenzi by obecněji byla hranicí vždy kvadrika. Přerušovaná čára pak naznačuje hranici mezi oblastmi, které by byly výsledkem aplikace lineární diskriminační analýzy na stejný soubor pozorování, vizte dále.

Lineární diskriminační analýza (LDA)

Lineární diskriminační analýza je speciálním případem kvadratické DA, kde navíc předpokládáme, že normální rozdělení v jednotlivých třídách mají stejnou kovarianční strukturu, tj. \Sigma_1=. +more=\Sigma_k=\Sigma \,\. V tomto případě lze pokračovat v úpravě rozhodovacího z předchozího odstavce roznásobením a odečtením výrazů nezávislých na i \,\. , čímž dostaneme kritérium v následující podobě.

Hustoty normálních rozdělení.

:\begin{matrix} \\ \operatorname{arg\,max} \\ { }^{i=1,. ,k} \end{matrix} \, (\pi_i \, p_i(\mathbf{x})) = \begin{matrix} \\ \operatorname{arg\,max} \\ { }^{i=1,. +more,k} \end{matrix} \, ( \operatorname{ln} \, \pi_i +\mu_i^T {\Sigma}^{-1}\mathbf{x} - \frac{1}{2} \mu_i^T {\Sigma}^{-1}\mu_i ) .

Pro i=1,...,k, \ \mathbf{x} \in \mathbb{R}^d se výraz : S_i(\mathbf{x})= \operatorname{ln} \, \pi_i +\mu_i^T {\Sigma}^{-1}\mathbf{x} - \frac{1}{2} \mu_i^T {\Sigma}^{-1}\mu_i

nazývá i\,\. -tý lineární diskriminační skór. +more Objekt s pozorovanými znaky \mathbf{x} v lineární DA zařazujeme do třídy T_j \,\. , pokud platí : j=\begin{matrix} \\ \operatorname{arg\,max} \\ { }^{i=1,. ,k} \end{matrix} \, S_i(\mathbf{x}) .

Na obrázku jsou vidět hustoty dvourozměrných normálních rozdělení (d=2 \,\. ) se stejnou jednotkovou varianční maticí a různými středními hodnotami. +more Matematicky zapsáno, červená, zelená a modrá hustota \{p_1,p_2,p_3\}\,\. postupně přísluší třídám \{T_1,T_2,T_3\}\,\. s rozděleními : N_2(\begin{pmatrix}0\\0\end{pmatrix},\begin{pmatrix}1&0\\0&1\end{pmatrix} ), \ N_2(\begin{pmatrix}2\\{-1}\end{pmatrix},\begin{pmatrix}1&0\\0&1\end{pmatrix} ), \ N_2(\begin{pmatrix}2\\1\end{pmatrix},\begin{pmatrix}1&0\\0&1\end{pmatrix} ) . Při pohledu shora lze vidět barevně rozlišené jednotlivé části roviny \mathbb{R}^2, které by odpovídaly pravidlu \{W_1,W_2,W_3\}\,\. získanému použitím kritéria maximální věrohodnosti. Toto pravidlo totiž zařazuje objekt se znaky \mathbf{x} do takové třídy, která má v bodě \mathbf{x} nejvyšší hustotu. Kdybychom tedy například měli na základě tohoto pravidla klasifikovat objekt, na kterém pozorujeme znaky (vektor) \begin{pmatrix}0\\{-1}\end{pmatrix}, zařadili bychom jej do třídy T_1\,\. , protože náleží do červené oblasti W_1\,\. Z obrázku je taky patrné, proč se používá název lineární DA. Důvod je ten, že pravidlo získané LDA rozlišuje každé dvě třídy pomocí lineární funkce (zobrazující z \mathbb{R}^d do \mathbb{R}), takže jednotlivé dvojice tříd jsou odděleny vždy nadrovinou v \mathbb{R}^d, speciálně v \mathbb{R}^2 přímkou, v \mathbb{R} bodem.

Regularizovaná diskriminační analýza (RDA)

Regularizovaná diskriminační analýza je DA vzniklá kombinací LDA a QDA, kde se optimalizuje kombinace rozptylových matic. Tato metoda byla uvedena J. +moreH. Friedmanem v roce 1988 a patří mezi často používané metody DA.

Odhady pravděpodobností správné klasifikace

Samotný výsledek diskriminační části DA, tj. samotné rozhodovací pravidlo, je bezcenný, pokud nemáme dodatečné informace o jeho spolehlivosti. +more * Základní odhad pravděpodobnosti správného zařazení získáme aplikací sestaveného rozhodovacího pravidla na všech n^* \,\. objektů z trénovací množiny. Označme n_{ij} \,\. počet prvků trénovací množiny pocházejících z třídy T_i \,\. , které rozhodovací pravidlo zařazuje do třídy T_j \,\. Potom matice relativních četností :\frac{1}{n^*} \{n_{ij}\}_{i,j=1,. ,k} \,\.

:dává odhady příslušných pravděpodobností. Na diagonále matice jsou postupně odhady pravděpodobností správné klasifikace pro jednotlivé třídy, takže stopa matice (součet prvků na diagonále) pak udává optimistický odhad celkové pravděpodobnosti správného zařazení náhodně zvoleného prvku. +more Samozřejmě každý z objektů se byť malou měrou podílí na konstrukci rozhodovacího pravidla, což „zvyšuje jeho šanci“ na správné zařazení tímto pravidlem. * Křížový odhad (Cross Validation) spočívá v náhodném rozdělení trénovací množiny na dva soubory. Na první soubor aplikujeme diskriminační část DA, kterou získáme rozhodovací pravidlo. Na druhém souboru pak prověřujeme kvalitu získaného pravidla základním postupem (z předchozího odstavce). Tento postup sice oproti předchozímu „nezvýhodňuje“ objekty při klasifikaci, ale klade pro srovnatelnou hodnotu odhadu vyšší nároky na velikost trénovací množiny. Tento postup se používá pouze pro odhad pravděpodobností správné klasifikace, vlastní rozhodovací pravidlo se utvoří podle celé trénovací množiny, tj. stejně jako u následující metody. * Metoda Jackknife pro každý z n^* \,\. objektů trénovací množiny vytvoří rozhodovací pravidlo na základě zbylých n^* -1\,\. objektů, a příslušný vynechaný prvek pak tímto pravidlem testuje, zda je správně zařazen. Celkem je tedy nutné n^* \,\. -krát použít diskriminační část DA, což může být výpočetně náročný proces. Dále se postupuje analogicky jako u základního odhadu. Ke klasifikaci se pak používá rozhodovací pravidlo utvořené na základě všech prvků trénovací množiny, které se pro velká n^* \,\. „významně neliší“ od každého z pravidel získaných vynecháním jednoho objektu.

Odkazy

Reference

Odstavec o historii je volnou parafrází diplomové práce, doplněnou o některé informace z anglické wikipedie. Matematická část byla zpracována převážně na základě přednášky Mnohorozměrná statistická analýza konané na MFF UK vedené Doc. +more RNDr. Janem Hurtem, CSc.

Externí odkazy

Srozumitelné vysvětlení základních postupů DA v pracovním textu k přednášce na ZČU v Plzni: * [url=http://home.zcu.cz/~alexk/sad1/vyuka/DA-prednaska.pdf]DA-přednáška[/url]

Názorné příklady použití DA na stránkách [url=http://demonstrations. wolfram. +morecom/]demonstrations. wolfram. com[/url] (vše anglicky): * [url=http://demonstrations. wolfram. com/SignalDetectionTheory/]Signal Detection Theory[/url] * [url=http://demonstrations. wolfram. com/FisherDiscriminantAnalysis/]Fisher Discriminant Analysis[/url] * [url=http://demonstrations. wolfram. com/PatternRecognitionPrimer/]Pattern Recognition Primer[/url] * [url=http://demonstrations. wolfram. com/PatternRecognitionPrimerII/]Pattern Recognition Primer II[/url].

Prezentace Doc. Hurta pro uživatele systému Mathematica: * [url=http://library.wolfram.com/infocenter/Conferences/5777/]Discriminant Analysis and Multidimensional Scaling[/url]

Mnoho vědeckých článků o DA (v angličtině) je dostupných v pdf na [url=http://www. sciencedirect. +morecom/]sciencedirect. com[/url]: * [url=http://www. sciencedirect. com/science. _ob=MImg&_imagekey=B6V8V-47183X8-1-75&_cdi=5880&_user=1490772&_pii=S0167947302002992&_orig=search&_coverDate=03%2F01%2F2004&_sk=999549997&view=c&wchp=dGLbVtb-zSkzk&md5=84dbb97cc1b82a89fc099d85ca1adad0&ie=/sdarticle. pdf]Fast and robust discriminant analysis[/url] * [url=http://www. sciencedirect. com/science. _ob=MImg&_imagekey=B6V8V-4234917-1-6J&_cdi=5880&_user=1490772&_pii=S0167947300000190&_orig=search&_coverDate=01%2F28%2F2001&_sk=999649996&view=c&wchp=dGLbVtb-zSkzk&md5=d9c27396520362dfe2ff095028c168e2&ie=/sdarticle. pdf]An algorithm for nonmetric discriminant analysis[/url] * [url=http://www. sciencedirect. com/science. _ob=MImg&_imagekey=B6V8V-3SWT44Y-V-3&_cdi=5880&_user=1490772&_pii=S0167947396000436&_orig=search&_coverDate=01%2F09%2F1997&_sk=999769996&view=c&wchp=dGLbVtb-zSkzk&md5=1d38adcd5f7e3d95fc8a38063dbd1a43&ie=/sdarticle. pdf]Regularization in discriminant analysis: an overview[/url] * [url=http://www. sciencedirect. com/science. _ob=MImg&_imagekey=B6TFP-3SHC8MD-2-2&_cdi=5232&_user=1490772&_pii=S0169743997000440&_orig=search&_coverDate=08%2F31%2F1997&_sk=999619998&view=c&wchp=dGLbVtb-zSkzk&md5=ca021f9e6046f278795dc96458cb6e6b&ie=/sdarticle. pdf]Regularised discriminant analysis (RDA) - modelling for the binary discrimination between pollution types[/url].

Kategorie:Statistika