METODY PRO REDUKCI DIMENZE ˇ ´ STATISTICE V MNOHOROZMERN E ´ ˇ A JEJICH VYPO CET Jan Kalinaa , Jurjen Duintjer Tebbensa,b ´ ˇ v.v.i., Pod Vod´arenskou vˇeˇz´ı 2, 182 07 Adresa: a Ustav informatiky AV CR, b Praha 8. Univerzita Karlova v Praze, Farmaceutick´a fakulta v Hradci Kr´alov´e, Heyrovsk´eho 1203, 500 05 Hradec Kr´alov´e. Abstract: The paper is devoted to standard multivariate statistical methods for dimension reduction. Their common basis is the eigendecomposition (i.e. computation of eigenvalues and eigenvectors) or, more generally, the singular value decomposition of specific matrices. These matrix decompositions possess excellent properties from the point of view of numerical mathematics. The paper overviews some results of numerical linear algebra on the numerical stability of methods for the computation of these decompositions. After that, it discusses various dimension reduction methods based on the decompositions, like principal component analysis, correspondence analysis, multidimensional scaling, factor analysis, and linear discriminant analysis for high-dimensional data. Keywords: Dimension reduction, eigendecomposition, numerical stability. ˇ anek je vˇenov´ Abstrakt: Cl´ an standardn´ım mnohorozmˇern´ ym statistick´ ym metod´ am pro redukci dimenze. Jejich spoleˇcn´ ym rysem je spektr´aln´ı rozklad urˇcit´e matice (tj. v´ ypoˇcet vlastn´ıch ˇc´ısel a vlastn´ıch vektor˚ u) anebo obecnˇeji singul´ arn´ı rozklad. Takov´e rozklady maj´ı vynikaj´ıc´ı vlastnosti z hlediska numerick´e matematiky. Tento ˇcl´ anek shrnuje nˇekter´e v´ ysledky numerick´e line´ arn´ı algebry o numerick´e stabilitˇe metod pro v´ ypoˇcet popsan´ ych rozklad˚ u. Pot´e diskutuje moˇznosti pouˇzit´ı metod pro redukci dimenze zaloˇzen´ ych na tˇechto rozkladech jako anal´ yzy hlavn´ıch komponent, korespondenˇcn´ı anal´ yzy, mnohorozmˇern´eho ˇsk´ alov´ an´ı, faktorov´e anal´ yzy a line´arn´ı diskriminaˇcn´ı anal´ yzy v kontextu vysoce dimenzion´ aln´ıch dat. Kl´ıˇcov´ a slova: Redukce dimenze, spektr´ aln´ı rozklad, numerick´a stabilita.
1.
Problematika redukce dimenzionality
Redukce dimenze pˇredstavuje d˚ uleˇzit´ y krok statistick´e anal´ yzy ˇci extrakce informace z mnohorozmˇern´ ych dat, kter´ y m˚ uˇze b´ yt v pˇr´ıpadˇe vysoce dimenzion´ aln´ıch dat zcela nezbytn´ y. Jednotliv´e metody slouˇz´ı ke zjednoduˇsen´ı 1
Metoda Anal´ yza hlavn´ıch komponent Korespondenˇcn´ı anal´ yza Mnohorozmˇern´e ˇsk´ alov´ an´ı Faktorov´ a anal´ yza Line´ arn´ı diskriminaˇcn´ı anal´ yza
Vlastnosti Line´arn´ı Nesupervidovan´a Line´arn´ı Nesupervidovan´a Neline´arn´ı Nesupervidovan´a Line´arn´ı Nesupervidovan´a Line´arn´ı Supervidovan´a
Tabulka 1: Pˇrehled statistick´ ych metod pro redukci dimenze
dalˇs´ıch anal´ yz (jako napˇr. klasifikaˇcn´ı nebo shlukov´e anal´ yzy) a souˇcasnˇe i umoˇzn ˇuj´ı pˇr´ımo extrakci informace z dat, popisuj´ı rozd´ıly mezi skupinami, odhaluj´ı dimenzionalitu separace mezi skupinami i vyjadˇruj´ı pˇr´ıspˇevek jednotliv´ ych promˇenn´ ych k t´eto separaci. Z anglicky psan´ ych knih m˚ uˇzeme k dan´emu t´ematu doporuˇcit [15, 28] anebo [16, 22], kde jsou tyt´eˇz metody diskutov´ any sp´ıˇse z hlediska dolov´ an´ı znalost´ı (data mining). Nˇekter´e metody pro redukci dimenze jsou pops´ any i v ˇcesk´ ych uˇcebnic´ıch [2, 25, 33]. Metody pro redukci dimenze se nˇekdy dˇel´ı do dvou rozs´ahl´ ych skupin, zejm´ena v aplikac´ıch dolov´ an´ı znalost´ı [22]: 1. Selekce promˇenn´ ych (selekce pˇr´ıznak˚ u, variable selection, feature selection, variable subset selection) 2. Extrakce pˇr´ıznak˚ u (feature extraction) • Line´ arn´ı • Neline´ arn´ı Selekc´ı promˇenn´ ych se rozum´ı v´ ybˇer jen tˇech promˇenn´ ych, kter´e jsou relevantn´ı. Naproti tomu metody pro extrakci pˇr´ıznak˚ u nahrazuj´ı pozorovan´a data jejich kombinac´ı. Jsou zaloˇzeny na takov´em zobrazen´ı, kter´e pˇrev´ad´ı pozorovan´ a data z vysoce rozmˇern´eho prostoru do prostoru menˇs´ı dimenze. V´ ypoˇcty tak sice probˇehnou v prostoru menˇs´ı dimenze, ale pˇresto je nutn´e napozorovat hodnoty vˇsech promˇenn´ ych. Podle charakteru tohoto zobrazen´ı rozliˇsujeme metody line´ arn´ı a neline´ arn´ı [22]. Podle jin´eho krit´eria dˇel´ıme metody pro redukci dimenze na supervidovan´e a nesupervidovan´e. Supervidovan´ ymi jsou takov´e, kter´e jsou urˇceny pro data poch´ azej´ıc´ı ze dvou nebo v´ıce skupin a souˇcasnˇe vyuˇz´ıvaj´ı informaci o tom, kter´e pozorov´ an´ı patˇr´ı do kter´e skupiny. To umoˇzn ˇuje zachovat oddˇelitelnost mezi skupinami. Nˇekteˇr´ı autoˇri varuj´ı, ˇze kupˇr´ıkladu anal´ yza
2
Metoda Hierarchick´ a shlukov´ a anal´ yza k pr˚ umˇer˚ u (k-means) k nejbliˇzˇs´ıch soused˚ u (k-nearest neighbour)
Vlastnost Nesupervidovan´a Nesupervidovan´a Supervidovan´a
Tabulka 2: Pˇrehled metod shlukov´e anal´ yzy
hlavn´ıch komponent jako pˇr´ıklad nesupervidovan´ ych metod nen´ı vhodn´a pro redukci dimenze dat poch´ azej´ıc´ıch ze dvou nebo v´ıce skupin v situaci, kdy c´ılem je klasifikaˇcn´ı anal´ yza [7]. Spoleˇcn´ ym rysem line´ arn´ıch metod pro redukci dimenze je skuteˇcnost, ˇze naleznou nejd˚ uleˇzitˇejˇs´ı transformace pozorovan´ ych dat pomoc´ı n´astroj˚ u line´ arn´ı algebry a n´ aslednˇe i nahrad´ı p˚ uvodn´ı data tˇemito nov´ ymi transformovan´ ymi promˇenn´ ymi. Vˇsechny metody v tomto ˇcl´anku prov´adˇej´ı transformaci dat pomoc´ı v´ ypoˇctu vlastn´ıch a/nebo singul´arn´ıch vektor˚ u. Pˇritom pouˇzit´ı vlastn´ıch/singul´ arn´ıch vektor˚ u zp˚ usob´ı i nekorelovanost transformovan´ ych promˇenn´ ych. Sn´ıˇzen´ım poˇctu promˇenn´ ych se sn´ıˇz´ı redundance v p˚ uvodn´ıch datech. To m˚ uˇze napravit pot´ıˇze se spolehlivost´ı z´avˇer˚ u n´asledn´e statistick´e anal´ yzy. Tento ˇcl´ anek struˇcnˇe popisuje klasick´e mnohorozmˇern´e statistick´e metody pro redukci dimenze uveden´e v tabulce 1 a vˇenuje se i jejich vhodnosti pro vysoce dimenzion´ aln´ı data. V kapitole 2 shrneme metody line´arn´ı algebry, kter´e tvoˇr´ı spoleˇcn´ y z´ aklad r˚ uzn´ ych statistick´ ych metod pro redukci dimenze. Pˇritom pro vysoce rozmˇern´ a data je d˚ uleˇzit´ y i pohled numerick´e line´arn´ı algebry, kter´ y se t´ yk´ a numerick´e stability v´ ypoˇctu jednotliv´ ych rozklad˚ u matic. Jednotliv´e metody pro redukci dimenze jsou pak pops´any ve zb´ yvaj´ıc´ıch kapitol´ ach. Nejde pˇritom o vyˇcerp´ avaj´ıc´ı pˇrehled poznatk˚ u o klasick´ ych metod´ ach, ale sp´ıˇse o zamyˇslen´ı nad jejich pouˇzitelnost´ı pro vysoce dimenzion´ aln´ı data, kdy poˇcet promˇenn´ ych p pˇrevyˇsuje poˇcet pozorov´an´ı n. Tˇemto aspekt˚ um se vˇenuje znaˇcn´ a pozornost i v bioinformatice nebo anal´ yze obrazu. Mezi dalˇs´ı metody, kter´e by si zaslouˇzily pozornost, patˇr´ı i kanonick´a korelaˇcn´ı anal´ yza, kter´ a zkoum´ a line´ arn´ı vztah mezi dvˇema skupinami promˇenn´ ych, nebo shlukov´ a anal´ yza, kter´ a prov´ ad´ı pr˚ uzkum dat s c´ılem naj´ıt nˇejak´e jejich shluky [16, 30, 20]. Na rozd´ıl od metod popsan´ ych v tomto ˇcl´anku tedy shlukov´ a anal´ yza nen´ı zaloˇzena na pˇrevodu dat do prostoru menˇs´ı dimenze za pomoci nˇejak´eho (line´ arn´ıho ˇci neline´ arn´ıho) zobrazen´ı [22]. Pˇrehled r˚ uzn´ ych metod shlukov´e anal´ yzy uv´ ad´ı tabulka 2. Mezi dalˇs´ı postupy pro redukci dimenze patˇr´ı napˇr´ıklad metoda locally linear embedding anebo metoda self-
3
organizing maps zaloˇzen´ a na neuronov´ ych s´ıt´ıch, coˇz jsou metody obl´ıben´e napˇr´ıklad v anal´ yze obrazu [19]. Z grafick´ ych metod pro exploratorn´ı anal´ yzu dat stoj´ı za zm´ınku biplot, zobrazuj´ıc´ı souˇcasnˇe data i promˇenn´e a b´ yv´a pouˇzit napˇr. pro interpretaci v´ ysledk˚ u anal´ yzy hlavn´ıch komponent [22]. V ˇcl´ anku budeme pouˇz´ıvat n´ asleduj´ıc´ı znaˇcen´ı. Jednotkovou matici o velikosti p oznaˇc´ıme I p , pˇr´ıpadnˇe I, pokud je dimenze jasn´a z kontextu. Prvek matice M ∈ n×p na i-t´em ˇradku a v j-t´em sloupci p´ıˇseme jako mij . D´ale oznaˇc´ıme
R
mi· =
n X
mij ,
m·j =
j=1
p X
mij ,
i=1
m·· =
p n X X
mij .
(1)
i=1 j=1
Normou vektoru i matice vˇzdy rozum´ıme euklidovskou normu.
2.
Singul´ arn´ı a spektr´ aln´ı rozklad matice
Z´ akladem cel´e ˇrady statistick´ ych metod pro redukci dimenze jsou singul´ arn´ı a spektr´ aln´ı rozklad matice. Oba pojmy se ve statistice ˇcasto povaˇzuj´ı za synonyma, ale v line´ arn´ı algebˇre pˇredstavuj´ı odliˇsn´e matematick´e koncepty. V t´eto sekci je pop´ıˇseme postupnˇe a uvedeme vlastnosti (vˇetˇsinou bez d˚ ukazu), kter´e jsou pro n´ as d˚ uleˇzit´e. Pro odvozen´ı, d˚ ukazy a detailnˇejˇs´ı popis odk´ aˇzeme na [32, kap. 4, 5 a 6] a [12, kap. 2.4, 7 a 8] anebo na ˇcesk´e pr´ace [11, kap. 2] a [9, kap. 2 a 5]. R˚ uzn´e algoritmy pro v´ ypoˇcet rozklad˚ u matic byly pops´ any napˇr. v pˇrehledu v´ ypoˇcetn´ı statistiky [6]. Naproti tomu v t´eto kapitole klademe d˚ uraz na numerickou stabilitu algoritm˚ u, coˇz je kl´ıˇcov´a vlastnost pˇri aplikac´ıch na vysoce rozmˇern´ a data.
2.1.
Spektr´ aln´ı rozklad
Nejprve definujeme vlastn´ı ˇc´ısla a vlastn´ı vektory. Pro re´alnou ˇctvercovou matici A ∈ p×p nazveme ˇc´ıslo λ ∈ vlastn´ım ˇc´ıslem (charakteristick´ ym ˇc´ıslem, eigenvalue) matice A, pokud existuje nenulov´ y vektor q ∈ p takov´ y, ˇze Aq = λq. Vektor q nazveme vlastn´ım vektorem (eigenvector) matice A. Kaˇzd´e vlastn´ı ˇc´ıslo λ s pˇr´ısluˇsn´ ym vlastn´ım vektorem q matice A zˇrejmˇe splˇ nuje vztah (A − λI)q = 0. Matice A − λI je proto singul´arn´ı a jej´ı determinant je nulov´ y. Rovnice det(A − λI) = 0 pˇredstavuje polynomi´aln´ı rovnici s nezn´ amou λ. Jelikoˇz kaˇzd´ y nekonstantn´ı polynom m´a alespoˇ n jeden komplexn´ı koˇren, v´ıme, ˇze existuje vˇzdy alespoˇ n jedno vlastn´ı ˇc´ıslo. Vlastn´ı ˇc´ısla re´ aln´e matice mohou b´ yt komplexn´ı, protoˇze koˇreny polynomu s re´aln´ ymi koeficienty jsou obecnˇe komplexn´ı.
R
C
4
C
Z existence alespoˇ n jednoho vlastn´ıho ˇc´ısla vypl´ yv´a, ˇze lze k dan´emu line´ arn´ımu zobrazen´ı z line´ arn´ıho prostoru do stejn´eho prostoru vˇzdy naj´ıt vektor, kter´ y pˇri zobrazen´ı nemˇen´ı sv˚ uj smˇer. V pˇr´ıpadˇe, kdy existuje maxim´ aln´ı poˇcet p n´ avz´ ajem line´ arnˇe nez´ avisl´ ych vlastn´ıch vektor˚ u, zˇrejmˇe existuje b´ aze prostoru p sloˇzen´ a z vlastn´ıch vektor˚ u. Matici A m˚ uˇzeme potom pomoc´ı t´eto b´ aze transformovat na jak´ ysi kanonick´ y tvar, tj. na diagon´aln´ı matici, jej´ıˇz vˇsechny vlastn´ı vektory jsou jednotkov´e vektory (sloupce jednotkov´e matice). Spektr´ aln´ı rozklad ˇctvercov´e matice A popisuje pr´avˇe tuto transformaci, a to ve tvaru
R
A = QΛQ−1 ,
(2)
kde Λ je diagon´ aln´ı matice s vlastn´ımi ˇcisly λ1 , . . . , λp na diagon´ale. Rozep´ıˇseme-li ekvivalentn´ı vztah AQ = QΛ po sloupc´ıch, dostaneme Aqi = λi qi ,
i = 1, . . . , p,
(3)
kde qi znaˇc´ı i-t´ y sloupec matice Q. Vid´ıme, ˇze sloupce matice Q jsou tvoˇreny vlastn´ımi vektory A. Tˇr´ıdou matic, pro kterou spektr´ aln´ı rozklad vˇzdy existuje, je tˇr´ıda symetrick´ ych pozitivnˇe semidefinitn´ıch matic. Empirick´a varianˇcn´ı matice i korelaˇcn´ı matice patˇr´ı k t´eto tˇr´ıdˇe. Pro symetrick´e pozitivnˇe semidefinitn´ı matice plat´ı, ˇze vˇsechna vlastn´ı ˇc´ısla jsou re´aln´a a nez´aporn´a. Nav´ıc existuje t´ım p´ adem vˇzdy b´ aze vlastn´ıch vektor˚ u, kter´e jsou navz´ajem ortogon´aln´ı, qTi qj = 0,
i 6= j,
qTi qi = 1,
i = 1, . . . , p.
(4)
V tomto pˇr´ıpadˇe plat´ı QT Q = I, tedy Q−1 = QT a spektr´aln´ı rozklad (2) lze ps´ at jako A = QΛQT . (5)
2.2.
Singul´ arn´ı rozklad
Singul´ arn´ı rozklad (singular value decomposition, SVD) je narozd´ıl od spektr´ aln´ıho rozkladu definov´ an pro libovolnou obd´eln´ıkovou matici A ∈ n×p . Je-li r ≤ min{n, p} hodnost matice A, pak m´a tvar
R
A = UΣVT ,
R
(6)
Rp×p jsou ortonorm´aln´ı matice, tj. UT U = I n a Rn×p m´a na prvn´ıch r diagon´aln´ıch pozic´ıch prvky
kde U ∈ n×n a V ∈ VT V = I p a matice Σ ∈
σii > 0,
i = 1, . . . , r 5
(7)
ˇ ısla σii se naz´ a je nulov´ a jinde. C´ yvaj´ı singul´ arn´ı ˇc´ısla a plat´ı, ˇze se rovnaj´ı odmocninˇe nenulov´ ych vlastn´ıch ˇc´ısel matice AAT (i AT A). Jsou tedy vˇzdy re´ aln´ a a kladn´ a. Je konvenc´ı uv´ adˇet singul´arn´ı ˇc´ısla matice Σ tak, aby byla sestupnˇe uspoˇr´ adan´ a. Sloupce matice U obsahuj´ı takzvan´e lev´e singul´arn´ı vektory a jsou z´ aroveˇ n vlastn´ımi vektory matice AAT . Sloupce V se naz´ yvaj´ı prav´e singul´ arn´ı vektory a jsou i vlastn´ımi vektory AT A. Nen´ı tˇeˇzk´e vidˇet, ˇze pro symetrick´e matice (A = AT ) pˇredstavuje spektr´aln´ı a singul´arn´ı rozklad tot´eˇz. V line´ arn´ı algebˇre se pro symetrick´e matice pouˇz´ıv´a vˇzdy pojem spektr´ aln´ı rozklad, kdyˇzto statistick´ a literatura pouˇz´ıv´a i pojem singul´arn´ı rozklad. Ze singul´ arn´ıho rozkladu (6) dostaneme po jednoduch´em (ale dlouh´em) rozeps´ an´ı po prvc´ıch ekvivalentn´ı vyj´ adˇren´ı A=
r X
σii ui viT .
(8)
i=1
Pro jednotliv´e ˇcleny pˇritom plat´ı kσii ui viT k = σii a tud´ıˇz kσ11 u1 v1T k = σ11 ≥ kσ22 u2 v2T k = σ22 ≥ · · · ≥ kσrr ur vrT k = σrr .
(9)
Ve vztahu (8) nahl´ıˇz´ıme na matici A jako na souˇcet celkov´eho poˇctu r komponent. Jde vlastnˇe o ekvivalentn´ı vyj´ adˇren´ı pozorovan´ ych dat v˚ uˇci jin´ ym ortonorm´ aln´ım b´ az´ım. Lze ˇr´ıci, ˇze komponenty pˇr´ısluˇsn´e nejvˇetˇs´ım singul´arn´ım ˇc´ısl˚ um maj´ı v pozorovan´ ych datech nejvˇetˇs´ı v´ahu. Statistick´e metody pro redukci dimenze zaloˇzen´e na singul´arn´ım (popˇr. pro symetrick´e pozitivnˇe semidefinitn´ı matice spektr´aln´ım) rozkladu urˇcit´e matice A lze interpretovat i tak, ˇze samotnou matici A nahrad´ı aproximac´ı podle s X A≈ σii ui viT , (10) i=1
v nˇemˇz s < r. To znamen´ a, ˇze se zcela ignoruje vliv takov´ ych komponent z (8), kter´e pˇr´ısluˇs´ı nejmenˇs´ım (a tedy v urˇcit´em smyslu nejm´enˇe d˚ uleˇzit´ ym) singul´ arn´ım ˇc´ısl˚ um.
2.3.
Numerick´ e vlastnosti
Singul´ arn´ı rozklad je velmi siln´ y n´ astroj nejen z teoretick´eho hlediska, ale i v´ ypoˇcetnˇe, pakliˇze je spr´ avnˇe implementov´an. Standardn´ı metoda pro jeho v´ ypoˇcet je sice draˇzˇs´ı (ale ne ˇr´ adovˇe) neˇz metody pro jin´e rozklady jako napˇr. LU rozklad (Gaussova eliminace), ale ze vˇsech rozklad˚ u si nejl´epe dok´aˇze 6
poradit v situac´ıch, kdy dan´ a matice je singul´arn´ı nebo t´emˇeˇr singul´arn´ı. Napˇr´ıklad urˇcen´ı hodnosti matice je v ˇradˇe pˇr´ıpad˚ u moˇzn´e jen pomoc´ı SVD. Spr´ avn´ a implementace SVD je totiˇz schopn´a naj´ıt veˇsker´a singul´arn´ı ˇc´ısla vˇcetnˇe tˇech nejmenˇs´ıch s pˇresnost´ı stejnou jako strojov´a pˇresnost [3]. Nav´ıc singul´ arn´ı (v symetrick´em pozitivnˇe semidefinitn´ım pˇr´ıpadˇe spektr´ aln´ı) rozklad lze spoˇc´ıst tzv. zpˇetnˇe stabilnˇe. To znamen´a, ˇze existuj´ı metody pro SVD dan´e matice A, kter´e spoˇctou v koneˇcn´e aritmetice vˇzdy rozklad, kter´ y je pˇresn´ ym rozkladem (tj. rozkladem v pˇresn´e aritmetice) pro matici velmi bl´ızkou p˚ uvodn´ı matici A. Zd˚ urazn´ıme, ˇze tato vlastnost nen´ı vlastnost´ı singul´ arn´ıho rozkladu, ale vlastnost´ı metody jej´ıho v´ ypoˇctu. Na v´ ybˇeru nejvhodnˇejˇs´ı metody maticov´eho v´ ypoˇctu velice zaleˇz´ı. Typick´ ym pˇr´ıkladem je ˇreˇsen´ı probl´emu nejmenˇs´ıch ˇctverc˚ u minp kAx − bk,
x∈
R
A∈
Rn×p ,
b∈
Rn ,
n > p.
(11)
Matematicky pˇresn´ ym ˇreˇsen´ım je x = A† b, kde A† je Mooreova-Penroseova pseudoinverze k matici A. Naivn´ı pˇr´ıstup spoˇc´ıv´a v tom, ˇze se n´asob´ı inverze matice AT A s vektorem AT b. Jsou-li sloupce matice A t´emˇeˇr line´arnˇe z´ avisl´e, pak m˚ uˇze doj´ıt k obrovsk´ ym chyb´ am pˇri v´ ypoˇctu (AT A)−1 . Vhodn´a implementace zaloˇzen´ a na SVD vyuˇz´ıv´ a vzorec x = A† b = VΣ† UT b =
r X uT b i
i=1
σii
vi
(12)
obdobn´ y vzorci (8), pˇriˇcemˇz v´ ypoˇcet SVD je numericky stabiln´ı. Pro nejstabilnˇejˇs´ı a ˇcasto z´ aroveˇ n nejrychlejˇs´ı maticov´e metody doporuˇcujeme sofware Matlab [23], kter´ y obsahuje nejmodernˇejˇs´ı implementace maticov´ ych metod pˇr´ımo od vˇedeck´e komunity numerick´e line´arn´ı algebry, tedy komunity, kter´ a se specializuje pr´ avˇe na efektivn´ı (computationally efficient) maticov´e v´ ypoˇcty. Alternativnˇe lze pouˇz´ıt popul´arn´ı statistick´ y software R [26], kter´ y je narozd´ıl od Matlabu zdarma. I kdyˇz samotn´e metody maticov´eho poˇctu byly jiˇz d´ avno podrobnˇe pops´any v statistick´e literatuˇre [27], zat´ım se jim vˇenovalo m´ alo pozornosti z numerick´eho hlediska a nen´ı ani vˇzdy zaruˇceno, ˇze metody jsou efektivnˇe implementov´any v R. To plat´ı zejm´ena pro pr´ aci s vysoce dimenzion´ aln´ımi daty. V´ ypoˇcet singul´ arn´ıho rozkladu ˇctvercov´e matice velikosti p stoj´ı pˇribliˇznˇe 16/3 · p3 aritmetick´ ych operac´ı. Pro vysoce dimenzion´aln´ı data (napˇr. p ≥ 10 000) obecnˇe plat´ı, ˇze v´ ypoˇcet nelze prov´est v rozumn´em ˇcase anebo doch´az´ı ˇ k vyˇcerp´ an´ı u ´loˇzn´eho prostoru v pamˇeti poˇc´ıtaˇce. Casto jsou data vˇsak ˇr´ıdk´ a, tzn. mnoho prvk˚ u dan´e matice je nulov´ ych, coˇz m˚ uˇze v´ ypoˇcet usnadnit. Existuj´ı iteraˇcn´ı metody, kter´e vyˇzaduj´ı v kaˇzd´e iteraci jen jedno pomˇernˇe levn´e 7
n´ asoben´ı vektoru s danou ˇr´ıdkou matic´ı. V´ ysledkem iteraˇcn´ıho procesu jsou aproximace singul´ arn´ıch ˇc´ısel a vektor˚ u s t´ım, ˇze zpravidla nejrychleji konverguj´ı nejvˇetˇs´ı singul´ arn´ı ˇc´ısla. Takov´ y postup je pro redukci dimenze vhodn´ y vzhledem k (10) a ˇcasto i umoˇzn ˇuje vyhnout se regularizaci [16, 10].
3.
Anal´ yza hlavn´ıch komponent
Anal´ yza hlavn´ıch komponent (PCA, principal component analysis) pˇredstavuje nejˇcastˇeji pouˇz´ıvanou metodu pro redukci dimenze. Pˇredpokl´ad´ame, ˇze m´ ame k dispozici nez´ avisl´e stejnˇe rozdˇelen´e p-rozmˇern´e n´ahodn´e vektory X1 , . . . , Xn ∈ p . Metoda je zaloˇzena na spektr´ aln´ım rozkladu empirick´e varianˇcn´ı matice
R
n
S=
1 X ¯ ¯ T (Xi − X)(X i − X) ∈ n − 1 i=1
Rp×p ,
(13)
¯ oznaˇc´ı vektor v´ kde X ybˇerov´eho pr˚ umˇeru. Tato matice je symetrick´a a pozitivnˇe semidefinitn´ı s nez´ aporn´ ymi vlastn´ımi ˇc´ısly. Hodnost S je nejv´ yˇse min{n, p}. Protoˇze souˇcet vlastn´ıch ˇc´ısel matice je roven souˇctu jej´ıch diagon´ aln´ıch prvk˚ u (tj. jej´ı stopˇe), je v pˇr´ıpadˇe varianˇcn´ı matice roven souˇctu rozptyl˚ u jednotliv´ ych promˇenn´ ych. C´ılem anal´ yzy hlavn´ıch komponent je nahradit p-rozmˇern´a pozorov´an´ı mal´ ym poˇctem s (s < min{n, p}) hlavn´ıch komponent, kter´e pˇredstavuj´ı navz´ ajem nekorelovan´e line´ arn´ı kombinace namˇeˇren´ ych promˇenn´ ych vysvˇetluj´ıc´ı velkou (maxim´ aln´ı moˇznou) ˇc´ ast variability dat [2]. Hlavn´ı komponenty lze interpretovat i tak, ˇze jednotliv´e namˇeˇren´e pozorov´an´ı se skl´ad´a z pr˚ umˇeru spoˇc´ıtan´eho pˇres vˇsechna pozorov´ an´ı plus nˇejak´a line´arn´ı kombinace vˇsech jednotliv´ ych hlavn´ıch komponent. Pˇritom existuj´ı r˚ uzn´a doporuˇcen´ı, jak volit vhodnou hodnotu s. Anal´ yza hlavn´ıch komponent prom´ıt´ a jednotliv´a pozorov´an´ı Xi na podprostor generovan´ y s vlastn´ımi vektory q1 , . . . , qs matice S, kter´e pˇr´ısluˇs´ı nejvˇetˇs´ım vlastn´ım ˇc´ısl˚ um, Xi
−→
[q1 , . . . , qs ][q1 , . . . , qs ]T Xi .
(14)
N´ asleduj´ıc´ı v´ ypoˇcty pak prob´ıhaj´ı v prostoru mal´e dimenze generovan´em vektory q1 , . . . , qs a m´ısto Xi se pracuje s line´arn´ı kombinac´ı [q1 , . . . , qs ]T Xi ,
(15)
tedy se skal´ arn´ımi souˇciny s vlastn´ımi vektory q1 , . . . , qs . Pˇr´ıspˇevek i-t´e hlavn´ı komponenty (i = 1, . . . , p), tj. komponenty pˇr´ısluˇsn´e i-t´emu nejvˇetˇs´ımu 8
vlastn´ımu ˇc´ıslu, k vysvˇetlen´ı celkov´e variability v datech pˇritom vyj´adˇr´ıme jako λ Pp i , (16) j=1 λj kde λ1 , . . . , λp jsou vlastn´ı ˇc´ısla matice S. Alternativnˇe lze poˇc´ıtat hlavn´ı komponenty z empirick´e korelaˇcn´ı matice, coˇz se doporuˇcuje sp´ıˇse jen v pˇr´ıpadˇe velk´ ych odliˇsnost´ı ve variabilitˇe jednotliv´ ych promˇenn´ ych [28]. V´ ypoˇcet hlavn´ıch komponent lze prov´est numericky stabilnˇe i pro vysoce dimenzion´ aln´ı data (n p). V softwaru je vˇsak moˇzn´e narazit na takovou implementaci, kter´ a pro n p selh´ av´a. V softwaru R jsou k dispozici specializovan´e knihovny HDMD ˇci FactoMineR pro v´ ypoˇcet (nejen) hlavn´ıch komponent pro vysoce dimenzion´ aln´ı data, kter´e lze doporuˇcit pˇred bˇeˇzn´ ymi implementacemi [24].
4.
Korespondenˇ cn´ı anal´ yza
Korespondenˇcn´ı anal´ yza pˇredstavuje obdobu anal´ yzy hlavn´ıch komponent pro kategori´ aln´ı data [14, 25, 28]. Nˇekteˇr´ı autoˇri ji ponˇekud pˇrekvapivˇe oznaˇcuj´ı i jako korespondenˇcn´ı faktorovou anal´ yzu [13]. Tzv. jednoduch´ a korespondenˇcn´ı anal´ yza studuje vztah mezi dvˇema kategori´ aln´ımi promˇenn´ ymi. Oznaˇcme pomoc´ı N ∈ I×J kontingenˇcn´ı tabulku pozorovan´ ych ˇcetnost´ı nij s I ˇr´ adky a J sloupci. Pomoc´ı χ2 budeme znaˇcit testovou statistiku Pearsonova χ2 testu nez´avislosti (nebo homogenity) pro stanoven´ı vztahu mezi sloupci a ˇr´ adky. Dejme tomu, ˇze χ2 test zam´ıt´a nulovou hypot´ezu nez´ avislosti mezi kategori´ aln´ı promˇennou v ˇr´adc´ıch tabulky a kategori´ aln´ı promˇennou v jej´ıch sloupc´ıch. C´ılem korespondenˇcn´ı anal´ yzy je d´ ale redukovat mnohorozmˇern´ y prostor ˇr´adkov´e a sloupcov´e promˇenn´e a prostudovat interakci mezi obˇema promˇenn´ ymi. Statistika χ2 se obvykle poˇc´ıt´ a jako
R
χ2 =
2 I X J X ni· n·j ni· n·j . nij − n·· n·· i=1 j=1
(17)
To lze napsat pomoc´ı relativn´ıch ˇcetnost´ı pij = nij /n·· jako χ2 = n··
I X J X
2
(pij − pi· p·j ) /pi· p·j .
(18)
i=1 j=1
Matice P, jej´ıˇz prvky jsou relativn´ı ˇcetnosti pij , se v tomto kontextu oznaˇcuje 9
jako korespondenˇcn´ı matice. Dalˇs´ı z´ apisy t´ehoˇz jsou 2
χ = n··
I X i=1
pi·
J X pij j=1
pi·
2 − p·j
/p·j = n··
J X j=1
p·j
I X pij i=1
p·j
2 − pi·
/pi· , (19)
kde ˇc´ısla tvaru pij /pi· a pij /p·j jsou prvky tzv. profil˚ u. Vektory margin´ aln´ıch pravdˇepodobnost´ı oznaˇc´ıme jako T
c = (p·1 , . . . , p·J ) ,
r = (p1· , . . . , pI· )
T
a definujeme ˇr´ adkov´e a sloupcov´e profily jako T T ni1 pi1 niJ piJ ri = = , ,..., ,..., ni· ni· pi· pi· T T n1j nIj p1j pIj cj = ,..., = ,..., . n·j n·j p·j p·j
(20)
(21) (22)
Ze vztahu (19) dostaneme χ2 = n··
I X
pi· (ri − c)T D−1 c (ri − c) = n··
i=1
J X
p·j (cj − r)T D−1 r (cj − r), (23)
j=1
kde Dr = diag(r), Dc = diag(c) a diag znaˇc´ı diagon´aln´ı matici. Zˇrejmˇe PI PJ 2 plat´ı i=1 pi· = j=1 p·j = 1 a testovou statistiku χ lze tedy interpretovat jako v´ aˇzen´ y pr˚ umˇer χ2 vzd´ alenost´ı mezi ˇr´adkov´ ymi profily ri a margin´ aln´ımi sloupcov´ ymi pravdˇepodobnostmi c. Stejnˇe tak lze na hodnotu χ2 nahl´ıˇzet jako na v´ aˇzen´ y pr˚ umˇer χ2 vzd´ alenost´ı mezi sloupcov´ ymi profily cj a margin´ aln´ımi ˇr´ adkov´ ymi pravdˇepodobnostmi r. V r´ amci redukce mnohorozmˇern´eho prostoru lze vzorec (18) s vyuˇzit´ım toho, ˇze ˇc´ısla pij − pi· p·j jsou prvky matice P − rcT , vyj´adˇrit jako T −1 T T χ2 = n·· tr D−1 , (24) r (P − rc )Dc (P − rc ) kde tr znaˇc´ı stopu matice. Jsou-li λ21 , . . . , λ2r nenulov´a vlastn´ı ˇc´ısla matice T −1 T T D−1 r (P − rc )Dc (P − rc ) ,
(25)
pak s vyuˇzit´ım vˇety o stopˇe m´ ame χ2 = n··
r X i=1
10
λ2i .
(26)
Dalˇs´ı v´ ypoˇcty pak vedou ke grafick´emu zn´azornˇen´ı vztah˚ u mezi ˇr´adky a sloupci kontingenˇcn´ı tabulky za pomoci redukce dat do dvou dimenz´ı [25]. Potˇrebn´e dvˇe hlavn´ı komponenty jsou pˇreˇsk´alovan´ ymi lev´ ymi a prav´ ymi sin−1/2 −1/2 T gul´ arn´ımi vektory v SVD rozkladu matice Dr (P − rc )Dc , pro kterou lze dok´ azat, ˇze m´ a singul´ arn´ı ˇc´ısla λ1 , . . . , λr . Tyto dvˇe hlavn´ı komponenty pˇr´ısluˇs´ı vlastn´ım ˇc´ısl˚ um λ21 a λ22 matice (25) a jejich pˇr´ıspˇevek k vysvˇetlen´ı vˇsech dimenz´ı lze vyj´ adˇrit jako pod´ıl λ2 + λ22 P1r 2, j=1 λj
(27)
Pr 2 2 kde yv´ a celkov´ a inercie. Zde je na m´ıstˇe upozori=1 λi = χ /n·· se naz´ nit na dalˇs´ı nekonzistenci mezi terminologi´ı ve statistice a line´arn´ı algebˇre. Inercie v line´ arn´ı algebˇre je pojem spojen´ y s poˇcty (a ne souˇcty) vlastn´ıch ˇc´ısel, pˇresnˇeji jde o poˇ c ty z´ a porn´ y ch, nulov´ ych a kladn´ ych vlastn´ıch ˇc´ısel. Pr Celkov´ a inercie i=1 λ2i = χ2 /n·· je obl´ıbenou m´ırou asociace mezi dvˇema kategori´ aln´ımi promˇenn´ ymi, kter´ a se bˇeˇznˇe oznaˇcuje jako φ (koeficient f´ı) [1]. Inercie odpov´ıd´ a stupni rozpt´ ylen´ı bod˚ u v mnohorozmˇern´em prostoru a rovn´a se v´ aˇzen´emu pr˚ umˇeru χ2 vzd´ alenost´ı ˇr´ adkov´ ych profil˚ u od sv´eho pr˚ umˇeru. Jednotliv´e u ´rovnˇe ˇr´ adkov´e i sloupcov´e promˇenn´e se zobrazuj´ı do jedin´eho spoleˇcn´eho grafu. Vodorovn´e ose v grafu odpov´ıd´a prvn´ı hlavn´ı komponenta a ˇ adky zobrazen´e svisl´e ose druh´ a hlavn´ı komponenta transformovan´ ych dat. R´ bl´ızko u sebe pak maj´ı podobn´e profily a obdobnˇe i sloupce zobrazen´e bl´ızko sebe. Souˇcasnˇe plat´ı, ˇze bod odpov´ıdaj´ıc´ı konkr´etn´ımu ˇr´adku a bod odpov´ıdaj´ıc´ı konkr´etn´ımu sloupci jsou si bl´ızko tehdy a jen tehdy, kdyˇz se dan´a kombinace objevuje ˇcastˇeji, neˇz by se oˇcek´ avalo v modelu nez´avislosti. Polohy bod˚ u tak vyjadˇruj´ı asociaci mezi konkr´etn´ımi u ´rovnˇemi ˇr´adkov´eho a sloupcov´eho profilu a tato asociace se oznaˇcuje jako stupeˇ n korespondence. Grafick´ y v´ ystup tedy hodnot´ı rozd´ıl pozorovan´e tabulky ˇcetnost´ı oproti situaci, kdyby platil model nez´ avislosti mezi obˇema promˇenn´ ymi. To n´aslednˇe umoˇzn ˇuje napˇr. shlukov´ an´ı kategori´ı nomin´aln´ıch promˇenn´ ych. Zobecnˇen´ım na v´ıce neˇz dvˇe kategori´ aln´ı promˇenn´e je mnohorozmˇern´a korespondenˇcn´ı anal´ yza, kterou podrobnˇe studuje kniha [29]. Korespondenˇcn´ı anal´ yza je numericky stabiln´ı i pro vysoce dimenzion´aln´ı data [5].
5.
Mnohorozmˇ ern´ eˇ sk´ alov´ an´ı
Mnohorozmˇern´e ˇsk´ alov´ an´ı (v´ıcerozmˇern´e ˇsk´alov´an´ı) je metoda pro redukci dimenze mnohorozmˇern´ ych dat a jejich grafick´e zobrazen´ı, kter´e co
11
moˇzn´ a nejpˇresnˇeji zachov´ a vzd´ alenosti mezi pozorov´an´ımi. Nejˇcastˇeji se jedn´a o dvourozmˇernou vizualizaci [22], tedy o redukci dimenzionality dat do dvou dimenz´ı. Pˇredpokl´ adejme, ˇze jsou k dispozici mnohorozmˇern´a spojit´a data mˇeˇren´a na n objektech. Metoda pak pracuje s matic´ı euklidovsk´ ych vzd´alenost´ı mezi objekty. Metodu vˇsak lze pouˇz´ıt i v pˇr´ıpadˇe, ˇze jsou k dispozici pouze vzd´alenosti mezi objekty, zat´ımco p˚ uvodn´ı namˇeˇren´e hodnoty nejsou zn´amy. Jinou moˇznost´ı je situace, kdy jsou namˇeˇreny sp´ıˇse podobnosti mezi objekty, pokud je lze snadno pˇrev´est na nepodobnosti (vzd´alenosti). Nejjednoduˇsˇs´ım pˇr´ıpadem je tzv. klasick´e mnohorozmˇern´e ˇsk´alov´an´ı, kter´e se t´eˇz oznaˇcuje jako anal´ yza hlavn´ıch souˇradnic (t´eˇz anal´ yza hlavn´ıch koordin´ at, principal coordinate analysis). To pˇredstavuje line´arn´ı metodu pro redukci dimenze [22]. Necht’ δij pˇredstavuje vzd´alenost mezi i-t´ ym a j-t´ ym pozorov´ an´ım a necht’ D ∈ n×n znaˇc´ı symetrickou ˇctvercovou matici s prvky
R
1 2 , dij = − δij 2
i = 1, . . . , n,
j = 1, . . . , n.
(28)
R
Pomoc´ı C ∈ n×n oznaˇc´ıme symetrickou ˇctvercovou matici s prvky cij , kde pro i, j = 1, . . . , n, cij = dij − (di· − d·· ) − (d·j − d·· ) = dij − di· − d·j + d·· .
(29)
Klasick´e mnohorozmˇern´e ˇsk´ alov´ an´ı je zaloˇzeno na spektr´aln´ım rozkladu matice C, kter´ a je pozitivnˇe semidefinitn´ı [15]. Vlastn´ı vektory pˇr´ısluˇsn´e pr´avˇe dvˇema nejvˇetˇs´ım vlastn´ım ˇc´ısl˚ um poslouˇz´ı k transformaci souˇradnic dat a jejich n´ asledn´emu grafick´emu zobrazen´ı [25]. D˚ uleˇzitou roli hraje i metrick´e mnohorozmˇern´e ˇsk´alov´an´ı, kter´e umoˇzn ˇuje transformovat vzd´ alenosti pomoc´ı monot´ onn´ı funkce, a je tedy neline´arn´ı metodou pro redukci dimenze. V´ ypoˇcet je pak zaloˇzen na iterativn´ım ˇreˇsen´ı minimalizace ztr´ atov´e funkce, kter´ a vyjadˇruje odliˇsnost mezi transformovan´ ymi vzd´ alenostmi (po redukci dimenze) a p˚ uvodn´ımi namˇeˇren´ ymi vzd´alenostmi. Kromˇe toho existuje nemetrick´e (ordin´ aln´ı) mnohorozmˇern´e ˇsk´alov´an´ı, kter´e bylo podrobnˇeji pops´ ano napˇr. v knih´ ach [25, 22]. Obecnˇe lze mnohorozmˇern´e ˇsk´ alov´ an´ı popsat jako soubor mnoha r˚ uzn´ ych metod a algoritm˚ u. Pˇritom jsou nˇekter´e z nich vhodn´e i pro anal´ yzu vysoce dimenzion´ aln´ıch dat. V tomto kontextu se za nejvhodnˇejˇs´ı povaˇzuj´ı pr´avˇe algoritmy zaloˇzen´e na singul´ arn´ım rozkladu [4]. Jako v´ yhodu metod mnohorozmˇern´eho ˇsk´ alov´ an´ı lze uv´est i jejich schopnost odhalit shluky v datech.
12
6.
Faktorov´ a anal´ yza
Faktorov´ a anal´ yza je zaloˇzena na pˇredpokladu, ˇze lze pozorovan´a data vysvˇetlit pomoc´ı mal´eho poˇctu latentn´ıch promˇenn´ ych (faktor˚ u) [2, 33]. Pˇredstavuje ˇcast´ y n´ astroj pˇri vyhodnocov´ an´ı psychologick´ ych test˚ u ˇci v ekonomii. Faktorov´ a anal´ yza vzbuzuje urˇcit´e kontroverze i kv˚ uli problematick´e interpretaci vznikl´ ych faktor˚ u. Model faktorov´e anal´ yzy pro i-t´e pozorov´an´ı zap´ıˇseme jako Xi1 − µ1 = .. .
γ11 fi1 + · · · + γ1t fit + ei1 , .. .
Xip − µp
γp1 fi1 + · · · + γpt fit + eip ,
=
(30)
kde i = 1, . . . , n. Pozorov´ an´ı Xi = (Xi1 , . . . , Xip )T zde vysvˇetlujeme pomoc´ı latentn´ıch faktor˚ u fi1 , . . . , fit , parametr˚ u µi , . . . , µp a γ11 , . . . , γpt a ˇsumu ei1 , . . . , eip . Model m˚ uˇzeme vyj´ adˇrit maticovˇe jako Xi − µ = Γfi + ei ,
i = 1, . . . , n.
(31)
Oproti anal´ yze hlavn´ıch komponent se nepˇredpokl´ad´a, ˇze by latentn´ı promˇenˇ ast variability jednotn´e vysvˇetlily veˇskerou variabilitu pozorovan´ ych dat. C´ liv´e promˇenn´e, kter´ a je vysvˇetlena latentn´ımi promˇenn´ ymi, se oznaˇcuje jako komunalita. Nyn´ı struˇcnˇe pop´ıˇseme moˇzn´ y zp˚ usob pro odhad parametr˚ u v (30). Oznaˇcme pomoc´ı S empirickou varianˇcn´ı matici spoˇc´ıtanou ze vˇsech pozorov´an´ı X1 , . . . , Xn . Pˇredpokl´ ad´ a se, ˇze S = ΓΓT + var e a ˇze matice var e je diagon´ aln´ı. D´ıky tomu se odhadnou mimodiagon´aln´ı prvky matice T = S − var e pˇr´ımo pomoc´ı mimodiagon´ aln´ıch prvk˚ u S. Pokud jde o diagon´aln´ı prvky T, lze je odhadnout iteraˇcn´ım postupem [2]. T´ım se z´ısk´a odhad cel´e matice T a d´ ale se hled´ a takov´ a matice Γ, kter´ a splˇ nuje vztah ΓΓT = T. Kompli∗ kac´ı je i to, ˇze tak´e pro matici Γ = ΓU plat´ı Γ∗ Γ∗T = T, pokud U je (libovoln´ a) ortonorm´ aln´ı matice. To znamen´a, ˇze latentn´ı promˇenn´e nejsou urˇceny jednoznaˇcnˇe. Byly navrˇzeny r˚ uzn´e metody pro odhad matice Γ: 1. Metoda hlavn´ıch komponent 2. Metoda hlavn´ıch faktor˚ u 3. Iterovan´ a metoda hlavn´ıch faktor˚ u 4. Metoda maxim´ aln´ı vˇerohodnosti 5. Metoda minimalizace rezidu´ı 13
Metodu hlavn´ıch komponent pro odhad parametr˚ u ve faktorov´e anal´ yze lze nast´ınit pomoc´ı spektr´ aln´ıho rozklad matice T ve tvaru T = QΛQT .
(32)
Oznaˇcme napˇred pomoc´ı Qt matici obsahuj´ıc´ı prvn´ıch t sloupc˚ u Q a po1/2 moc´ı Λt diagon´ aln´ı matici, jej´ıˇz diagon´ aln´ı prvky jsou rovny odmocnin´am t prvn´ıch diagon´ aln´ıch prvk˚ u matice Λ. Matice Γ se pak urˇc´ı jako 1/2
Γ = Q t Λt .
(33)
Alternativnˇe lze matici S nahradit empirickou korelaˇcn´ı matic´ı [28]. Pro vysoce dimenzion´ aln´ı data (n p) lze faktorovou anal´ yzu pouˇz´ıt, ˇ pokud se zvol´ı vhodn´ a metoda pro odhad matice Γ. Casto pouˇz´ıvan´a metoda maxim´ aln´ı vˇerohodnosti zde vˇsak selh´ av´ a. Vhodnˇe implementovanou metodu nab´ız´ı napˇr. knihovna HDMD v softwaru R.
7.
Line´ arn´ı diskriminaˇ cn´ı anal´ yza
Pˇrestoˇze line´ arn´ı diskriminaˇcn´ı anal´ yza (LDA) pˇredstavuje klasifikaˇcn´ı metodu, lze ji interpretovat jako metodu, kter´a jiˇz v sobˇe automaticky zahrnuje supervidovanou redukci dimenze [22]. Pˇredpokl´ adejme, ˇze m´ ame k dispozici celkov´ y poˇcet K r˚ uzn´ ych skupin, v nichˇz jsou pozorov´ any nez´ avisl´e p-rozmˇern´e n´ahodn´e veliˇciny X1 , . . . , Xn poch´ azej´ıc´ı z p-rozmˇern´eho norm´ aln´ıho rozdˇelen´ı. Pˇredpokl´ad´ame, ˇze kaˇzd´e skupinˇe pˇr´ısluˇs´ı odliˇsn´ y vektor stˇredn´ıch hodnot, ale varianˇcn´ı matice Σ je spoleˇcn´ a pro vˇsechny skupiny. Jej´ı odhad oznaˇc´ıme jako S. V k-t´e sku¯ k a celkov´ pinˇe oznaˇc´ıme v´ ybˇerov´ y pr˚ umˇer pozorovan´ ych dat jako X y pr˚ umˇer ¯ napˇr´ıˇc skupinami jako X. LDA zaˇrad´ı nov´e pozorov´an´ı do t´e skupiny, k jej´ımuˇz pr˚ umˇeru m´ a nejbl´ıˇz ve smyslu Mahalanobisovy vzd´alenosti. Ekvivalentnˇe lze v´ ypoˇcet LDA zaloˇzit na tzv. diskriminaˇcn´ıch sk´orech, kter´ ych je pr´ avˇe s = min{K − 1, p}. Tento pˇr´ıstup se typicky vyuˇz´ıv´a v softwarov´ ych implementac´ıch [18, 8]. Matice B o rozmˇerech p × p je definovan´a jako K X ¯ k − X)( ¯ X ¯ k − X) ¯ T. B= (X (34) k=1
Dalˇs´ı v´ ypoˇcet je zaloˇzen na spektr´ aln´ım rozkladu matice S−1 B. Diskriminaˇcn´ı sk´ ory se rovnaj´ı tˇem hlavn´ım vektor˚ um S−1 B, kter´e pˇr´ısluˇs´ı nenulov´ ym vlastn´ım ˇc´ısl˚ um.
14
Vˇeta: Uvaˇzujme p-rozmˇern´e pozorov´ an´ı Z. Oznaˇcme vlastn´ı vektory matice S−1 B pˇr´ısluˇsn´e nenulov´ ym vlastn´ım ˇc´ısl˚ um jako v1 , . . . , vs . Pak line´arn´ı diskriminaˇcn´ı anal´ yza klasifikuje pozorov´ an´ı Z do skupiny k pr´avˇe tehdy, kdyˇz s s X T 2 X T ¯ ¯ i) 2 , vj (Z − Xk ) ≤ vj (Z − X j=1
i = 1, . . . , K.
(35)
j=1
D˚ ukaz je uveden napˇr. v knize [18]. D˚ usledkem vˇety je pak n´asleduj´ıc´ı tvrzen´ı, kter´e ukazuje, jak LDA speci´ alnˇe pro K = 2 redukuje dimenzi na hodnotu 1. Vˇeta: Uvaˇzujme K = 2 a mˇejme k dispozici p-rozmˇern´e pozorov´an´ı Z. Pak m´a matice S−1 B jedin´e nenulov´e vlastn´ı ˇc´ıslo, jemuˇz pˇr´ısluˇs´ı vlastn´ı vektor, kter´ y ¯ 1 > vT X ¯ 2 . Line´arn´ı diskriminaˇcn´ı oznaˇc´ıme v. Pˇredpokl´ adejme d´ ale vT X anal´ yza klasifikuje pozorov´ an´ı Z do skupiny 1 pr´avˇe tehdy, kdyˇz vT Z >
¯ 1 + vT X ¯2 vT X . 2
(36)
¯ 1 < vT X ¯ 2 , line´ Pokud vˇsak plat´ı vT X arn´ı diskriminaˇcn´ı anal´ yza klasifikuje Z do skupiny 1 pr´ avˇe tehdy, kdyˇz vT Z <
¯ 1 + vT X ¯2 vT X . 2
(37)
Pro vysoce dimenzion´ aln´ı data za pˇredpokladu n p trp´ı line´arn´ı diskriminaˇcn´ı anal´ yza tzv. proklet´ım dimenzionality. Pˇri v´ ypoˇctu diskriminaˇcn´ıch sk´ or˚ u je velmi obt´ıˇzn´e nejprve spoˇc´ıtat potˇrebn´a vlastn´ı ˇc´ısla, pˇriˇcemˇz odpov´ıdaj´ıc´ı vlastn´ı vektory nemus´ı v tomto kontextu ani b´ yt definov´any [10]. Moˇzn´ ym ˇreˇsen´ım je pouˇz´ıt regularizovan´ y odhad varianˇcn´ı matice [16] anebo vhodnˇe modifikovat Fisherovo optimalizaˇcn´ı krit´erium, kter´e stoj´ı v pozad´ı metody LDA a vyˇzaduje v´ ypoˇcet vlastn´ıch ˇc´ısel matice S−1 B [10].
Podˇ ekov´ an´ı Pr´ ace vznikla za finanˇcn´ı podpory Nadaˇcn´ıho fondu Neuron na podporu vˇedy. Druh´ y autor byl podpoˇren grantem GA13-06684S Grantov´e agentury ˇ e republiky. Cesk´
15
Literatura [1] Agresti A. (2002): Categorical data analysis. Second edition. Wiley, New York. [2] Andˇel J. (1978): Matematick´ a statistika. SNTL, Praha. [3] Barlow J.L., Bosner N., Drmaˇc Z. (2005): A new stable bidiagonal reduction algorithm. Linear Algebra and its Applications 397, 35 – 84. [4] B´ecavin C., Tchitchek N., Mintsa-Eya C., Lesne A., Benecke A. (2011): Improving the efficiency of multidimensional scaling in the analysis of high-dimensional data using singular value decomposition. Bioinformatics 27 (10), 1413 – 1421. [5] Busygin S., Pardalos P.M. (2007): Exploring microarray data with correspondence analysis. In Pardalos P.M. et al. (Eds.): Data Mining in Biomedicine. Springer, New York, 2007, 25 – 38. ˇ ıˇzkov´ ˇ ıˇzek P. (2012): Numerical linear algebra. In Gentle J.E., [6] C´ a L, C´ H¨ ardle W.K., Mori Y. (Eds.): Handbook of Computational Statistics. Springer, Berlin, 105 – 137. [7] Dai J.J., Lieu L., Rocke D. (2006): Dimension reduction for classification with gene expression microarray data. Statistical Applications in Genetics and Molecular Biology 5 (1), Article 6. [8] Duda R.O., Hart P.E., Stork D.G. (2001): Pattern Classification. Second edition. Wiley, New York. [9] Duintjer Tebbens J., Hnˇetynkov´ a I., Pleˇsinger M., Strakoˇs Z., Tich´ y P. (2012): Anal´yza metod pro maticov´e v´ypoˇcty. Matfyzpress, Praha. [10] Duintjer Tebbens J., Schlesinger P. (2007): Improving implementation of linear discriminant analysis for the high dimension/small sample size problem. Computational Statistics & Data Analysis 52, 423 – 437. [11] Fiedler M. (1981): Speci´ aln´ı matice a jejich pouˇzit´ı v numerick´e matematice. SNTL, Praha. [12] Golub G., van Loan Ch. (1996): Matrix computations. Johns Hopkins University Press, Baltimore. [13] G¨ ohlmann H., Talloen W. (2009): Gene expression studies using Affymetrix microarrays. Chapman & Hall/CRC, Boca Raton. [14] Greenacre M. (1984): Theory and applications of correspondence analysis. Academic Press, London. [15] H¨ ardle W.K., Simar L. (2007): Applied multivariate statistical analysis. Springer, Berlin. [16] Hastie T., Tibshirani R., Friedman J. (2001): The elements of statistical learning. Springer, New York. 16
[17] Havel V., Holenda J. (1984): Line´ arn´ı algebra. SNTL, Praha. [18] Johnson R.A., Wichern D.W. (1982): Applied multivariate statistical analysis. Prentice-Hall, Englewood Cliffs. [19] Kalina J. (2011): Facial image analysis in anthropology: A review. Anthropologie 49 (2), 141 – 153. [20] Kalina J. (2013): Robustness aspects of knowledge discovery. In Pokorn´ y ˇ J., Saloun P., Paraliˇc J., Horv´ ath T. (Eds.): Datakon a Znalosti 2013, ˇ Part II. VSB-Technick´ a univerzita, Ostrava, 34 – 43. [21] Ledoit O., Wolf M. (2004): A well-conditioned estimator for largedimensional covariance matrices. Journal of Multivariate Analysis 88, 365 – 411. [22] Martinez W.L., Martinez A.R., Solka J.L. (2011): Exploratory data analysis with MATLAB. 2nd edn. Chapman & Hall/CRC, Boca Raton. [23] MathWorks, Inc., 1984–2013. MATLAB 8.1, http://www.mathworks. com/products/matlab. [24] McFerrin L. (2013): Package HDMD. Staˇzeno z http://cran.r-project. org/web/packages/HDMD/HDMD.pdf (14.6.2013). [25] Meloun M., Militk´ y J. (2006): Kompendium statistick´eho zpracov´ an´ı dat. Metody a ˇreˇsen´e u ´lohy. Academia, Praha. [26] R Development Core Team: R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, 2012, http://www.R-project.org/. [27] Rao C.R. (1973): Linear statistical inference and its applications. Wiley, New York. [28] Rencher A.C. (2002): Methods of multivariate analysis. Second edn. Wiley, New York. ˇ ak J., Reh´ ˇ akov´ [29] Reh´ a B. (1986): Anal´yza kategorizovan´ych dat v sociologii. Academia, Praha. ˇ [30] Rezankov´ a H., H´ usek D., Sn´ aˇsel V. (2007): Shlukov´ a anal´yza dat. Professional Publishing, Praha. [31] Saad Y. (2011): Numerical methods for large eigenvalue problems. Revised edition. SIAM, Philadelphia. [32] Watkins D.S. (2010): Fundamentals of matrix computations. Third edition. John Wiley & Sons, New York. ˇ Valenta Z., Berka P., Buchtela D., Jirouˇsek R., [33] Zv´ arov´ a J., Svaˇcina S., Mal´ y M., Pap´ıkov´ a V., Peleˇska J., Rauch J., Vajda I., Vesel´ y A., Zv´ara K., Zvolsk´ y M. (2009): Syst´emy pro podporu l´ekaˇrsk´eho rozhodov´ an´ı. Karolinum, Praha.
17
