logo-IBA logo-MU © Institut biostatistiky a analýz INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ logo-MU ANALÝZA A KLASIFIKACE DAT prof. Ing. Jiří Holčík, CSc. logo-IBA logo-MU © Institut biostatistiky a analýz IX. METODA FUKUNAGY - KOONTZE levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PROBLÉMY A PODMÍNKY þPCA algoritmus dokáže najít popis obrazů s optimálně redukovaným počtem příznaků s hlediska střední kvadratické odchylky aproximace þdisperzní matice Þ preference příznaků s největším rozptylem þautokorelační matice Þ sice lepší situace, ale může být i tak dost bezcenná z hlediska klasifikace levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PROBLÉMY A PODMÍNKY þPCA algoritmus dokáže najít popis obrazů s optimálně redukovaným počtem příznaků s hlediska střední kvadratické odchylky aproximace þdisperzní matice Þ preference příznaků s největším rozptylem þautokorelační matice Þ sice lepší situace, ale může být i tak dost bezcenná z hlediska klasifikace þ þJAK NA TO? levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PROBLÉMY A PODMÍNKY þPCA algoritmus dokáže najít popis obrazů s optimálně redukovaným počtem příznaků s hlediska střední kvadratické odchylky aproximace þdisperzní matice Þ preference příznaků s největším rozptylem þautokorelační matice Þ sice lepší situace, ale může být i tak dost bezcenná z hlediska klasifikace þ þJAK NA TO? þvýběr příznaků podle charakteristických čísel uspořádaných vzestupně levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PROBLÉMY A PODMÍNKY þPCA algoritmus dokáže najít popis obrazů s optimálně redukovaným počtem příznaků s hlediska střední kvadratické odchylky aproximace þdisperzní matice Þ preference příznaků s největším rozptylem þautokorelační matice Þ sice lepší situace, ale může být i tak dost bezcenná z hlediska klasifikace þ þJAK NA TO? þvýběr příznaků podle charakteristických čísel uspořádaných vzestupně þv dichotomickém případě – třeba rozklad podle Fukunagy a Koontze levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PRINCIP þvychází z normalizace autokorelační funkce; þvýstupem normalizace situace popsaná vztahem þk(y’) = E, þ E je jednotková matice a y’ reprezentuje obraz, pro který platí þy’ = U.y, þ kde U je matice normalizační transformace levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PRINCIP þpro autokorelační matici transformovaných příznaků platí þ þ þ þs tím můžeme psát þU.k(y).TU = E levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PRINCIP þpřipomínka: þ þ þtedy pro dichotomickou situaci je þk(y) = P(ω1). kω1(y) + P(ω2). kω2(y), þkde þ þ þje autokorelační matice pro prvky z r-té třídy þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þrovnici U.k(y).TU = E s tím můžeme psát ve tvaru þS1 + S2 = E, þkde þSr = P(ωr).U. kωr(y).TU, r = 1,2. PRINCIP levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þpro charakteristická čísla λi(1) a charakteristické vektory vi(1) matice S1 z definice platí þS1.vi(1) = λi(1).vi(1), i = 1, 2, …, m. þobdobně pro matici S2 þS2.vi(2) = (E-S1).vi(2) = λi(2).vi(2), þi = 1, 2, …, m; þ odkud po úpravách þS1.vi(1) = (1 - λi(2)).vi(2), þi = 1, 2, …, m. þ PRINCIP levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þz toho pak srovnáním je þvi(1) = vi(2), i = 1, 2, …, m a λi(1) = 1 - λi(2). þ Protože z vlastností matic jsou jejich vlastní čísla λi(r)Îá0,1ñ, r=1,2; i=1,…,m, jsou vlastní čísla matice S1 podle indexu i uspořádána vzestupně a matice S2 sestupně. Tedy nejdůležitější příznaky pro popis jedné třídy jsou současně nejméně důležité pro popis druhé třídy. þbázový souřadnicový systém vybíráme z vektorů v1(1), v2(1),… pro třídu ω1 a vm(1), vm-1(1), … pro třídu ω2. þ þ þ PRINCIP levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þMATICE U NORMALIZAČNÍ TRANSFORMACE þbez důkazů U = U1.U2, þkde U1 představuje matici transformace autokorelační matice k(y) na matici diagonální k(U1.y). To lze provést, když þ þ þ þ þ kde vi, i=1,…,m jsou vlastní vektory autokorelační matice k(y). PRINCIP levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þMATICE U NORMALIZAČNÍ TRANSFORMACE þtransformovaná matice k(U1.y) má tvar þ þ þ þ PRINCIP levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þMATICE U NORMALIZAČNÍ TRANSFORMACE þU2 převádí výše uvedenou diagonální matici na jednotkovou þ þ þ þ PRINCIP logo-IBA logo-MU © Institut biostatistiky a analýz X. ANALÝZA NEZÁVISLÝCH KOMPONENT levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ANALÝZA NEZÁVISLÝCH KOMPONENT PRINCIP METODY þx1(t) = a11.s1(t) + a12.s2(t) þx2(t) = a21.s1(t) + a22.s2(t) þ Úloha spočívá v nalezení originálních neznámých signálů z jednotlivých zdrojů s1(t) a s2(t) máme-li k dispozici pouze zaznamenané signály x1(t) a x2(t). þ x1 x2 s2 s1 s1 s2 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ANALÝZA NEZÁVISLÝCH KOMPONENT PRINCIP METODY þICA umožňuje určit koeficienty aij za předpokladu, že známé signály jsou dány lineárních kombinací zdrojových a za předpokladu statistické nezávislosti zdrojů v každém čase t. þ x1 x2 s2 s1 s1 s2 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þnechť x =T(x1,x2,…, xm) je m-rozměrný náhodný vektor (s nulovou střední hodnotou E(x)=0). þxi = ai1orig.s1orig + ai2orig.s2orig+…+ aimorig.smorig þi = 1,2,…,m þ nebo þx = Aorig.sorig þsorig je vektor orginálních skrytých nezávislých komponent a s1orig jsou nezávislé komponenty (předpoklad vzájemně statisticky nezávislosti); þAorig je transformační matice ANALÝZA NEZÁVISLÝCH KOMPONENT MODEL DAT levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þdefinice þs = W.x, þcíl: þ nalézt lineární transformaci (koeficienty transformační matice W tak, aby vypočítané nezávislé komponenty si byly vzájemně statisticky nezávislé [W = A-1] þ þ[p(s1,s2,…,sm) = p1(s1).p2(s2)… pm(sm)] ANALÝZA NEZÁVISLÝCH KOMPONENT MODEL DAT levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þpouze jedna originální nezávislá komponenta může mít normální rozložení pravděpodobnosti (pokud má více zdrojů normální rozložení není ICA schopna tyto zdroje ze vstupních dat extrahovat); þpro dané m-rozměrné obrazové vektory je ICA schopna najít pouze m nezávislých komponent; þnelze obecně určit polaritu nezávislých komponent; þnelze určit pořadí nezávislých komponent (?!) ANALÝZA NEZÁVISLÝCH KOMPONENT OMEZENÍ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ANALÝZA NEZÁVISLÝCH KOMPONENT OMEZENÍ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ODHAD NEZÁVISLÝCH KOMPONENT þoptimalizace pomocí zvolené optimalizační (účelové, kriteriální, objektové) funkce þß þa) nalézt kriteriální funkci þb) vybrat optimalizační algoritmus þ þad a) možnost ovlivnit statistické vlastnosti metody; þad b) spojitá optimalizační úloha s „rozumnou“ kriteriální funkcí – gradientní metoda, Newtonova metoda – ovlivňujeme rychlost výpočtu (konvergenci), nároky na paměť,… levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ODHAD NEZÁVISLÝCH KOMPONENT ZÁKLADNÍ ÚVAHA þnechť existuje m nezávislých náhodných veličin s určitými pravděpodobnostními rozděleními (jejich součet za dosti obecných podmínek konverguje s rostoucím počtem sčítanců k normálnímu rozdělení – centrální limitní věta); þo vektoru x (který máme k dispozici) předpokládáme, že vznikl součtem nezávislých komponent sorig þß þ jednotlivé náhodné veličiny xi mají pravděpodobnostní rozdělení, které je „bližší“ normálnímu než rozdělení jednotlivých komponent siorig levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ODHAD NEZÁVISLÝCH KOMPONENT ZÁKLADNÍ ÚVAHA þodhad nezávislých komponent si probíhá tak, že hledáme takové řádkové vektory wi transformační matice W, aby pravděpodobnostní rozdělení součinu wi.x bylo „co nejvíce nenormální“ þß þtj. nalézt takovou transformační matici W, aby proměnné wi.x měly pravděpodobnostní rozdělení, které se co nejvíce liší od normálního þß þpotřeba nalézt míru náhodné veličiny, která by mohla být použita pro kvantifikaci míry (podobnost, vzdálenost) nenormality levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ODHAD NEZÁVISLÝCH KOMPONENT POUŽÍVANÉ MÍRY NENORMALITY þkoeficient špičatosti þnegativní normalizovaná entropie; þaproximace negativní normalizované entropie; levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ODHAD NEZÁVISLÝCH KOMPONENT KOEFICIENT ŠPIČATOSTI þ þkurt(s) = E{s4} – 3(E{s2}) 2 þGaussovo rozložení má koeficient špičatosti roven nule, zatímco pro jiná rozložení (ne pro všechna) je koeficient nenulový. þPři hledání nezávislých komponent hledáme extrém, resp. kvadrát koeficientu špičatosti veličiny s = wi.x levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ODHAD NEZÁVISLÝCH KOMPONENT KOEFICIENT ŠPIČATOSTI þvýhody: þrychlost a relativně jednoduchá implementace; þnevýhody: þmalá robustnost vůči odlehlým hodnotám (pokud v průběhu měření získáme několik hodnot, které se liší od skutečných, výrazně se změní KŠ a tím i nezávislé komponenty nebudou odhadnut korektně); þexistence náhodných veličin s nulovým KŠ, ale nenormálním rozdělením; levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ODHAD NEZÁVISLÝCH KOMPONENT NEGATIVNÍ NORMALIZOVANÁ ENTROPIE þ(NNE, negentropy) þInformační entropie - množství informace náhodné veličiny þpro diskrétní náhodnou veličinu s je þH(s) = -Si P(s=ai).log2P(s=ai), þkde P(s=ai) je pravděpodobnost, že náhodná veličina S je rovna hodnotě ai. þpro spojitou proměnnou platí þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þentropie je tím větší, čím jsou hodnoty náhodné veličiny méně predikovatelné; þpro normální rozdělení má entropie největší hodnotu ve srovnání v dalšími rozděleními þ þNNE þJ(s) = H(sgauss) – H(s), þ kde sgauss je náhodná veličiny s normálním rozdělením ODHAD NEZÁVISLÝCH KOMPONENT NEGATIVNÍ NORMALIZOVANÁ ENTROPIE levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þvýhody: þpřesné vyjádření nenormality; þdobrá robustnost vůči odlehlým hodnotám; þnevýhody: þčasově náročný výpočet Þ snaha o vhodnou aproximaci NNE aby byly zachovány její výhody a současně byl výpočet nenáročný ODHAD NEZÁVISLÝCH KOMPONENT NEGATIVNÍ NORMALIZOVANÁ ENTROPIE levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þpoužití momentů vyšších řádů þ þ þ kde s je náhodná veličina s nulovou střední hodnotou a jednotkovým rozptylem þnevýhoda: þopět menší robustnost vůči odlehlým hodnotám ODHAD NEZÁVISLÝCH KOMPONENT APROXIMACE NEGATIVNÍ NORMALIZOVANÉ ENTROPIE levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þPoužití tzv. p-nekvadratických funkcí þ þ þ kde ki>0 je konstanta, Gi jsou šikovně navržené nelineární funkce a sgauss je normální náhodná proměnná, která spolu s s má nulovou střední hodnotu a jednotkový rozptyl. þ Je-li použita pouze jedna funkce G, pak je þJ(s) » [E{G(s)} - E{G(sgauss)}]2 ODHAD NEZÁVISLÝCH KOMPONENT APROXIMACE NEGATIVNÍ NORMALIZOVANÉ ENTROPIE levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þdoporučujeme: þ þ þ þ kde a1Îá1,2ñ nebo ODHAD NEZÁVISLÝCH KOMPONENT APROXIMACE NEGATIVNÍ NORMALIZOVANÉ ENTROPIE levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ODHAD NEZÁVISLÝCH KOMPONENT PŘÍKLAD POUŽITÍ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ODHAD NEZÁVISLÝCH KOMPONENT PŘÍKLAD POUŽITÍ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ODHAD NEZÁVISLÝCH KOMPONENT PŘÍKLAD POUŽITÍ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ODHAD NEZÁVISLÝCH KOMPONENT PŘÍKLAD POUŽITÍ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ODHAD NEZÁVISLÝCH KOMPONENT PŘÍKLAD POUŽITÍ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þPříprava nových učebních materiálů þoboru Matematická biologie þje podporována projektem ESF þč. CZ.1.07/2.2.00/07.0318 þ„VÍCEOBOROVÁ INOVACE STUDIA MATEMATICKÉ BIOLOGIE“ INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ logo-MU