ANALÝZA A KLASIFIKACE DAT prof. Ing. Jiří Holčík, CSc. IX. METODA FUKUNAGY - KOONTZE 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 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? 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ě 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 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 princip þ pro autokorelační matici transformovaných příznaků platí þ s tím můžeme psát U.(y).^TU = E princip þ připomínka: þ tedy pro dichotomickou situaci je k(y) = P(ω[1]). [ω][1](y) + P(ω[2]). [ω][2](y), kde je autokorelační matice pro prvky z r-té třídy princip þ rovnici U.(y).^TU = E s tím můžeme psát ve tvaru S[1] + S[2] = E, kde S[r] = P(ω[r]).U. [ω][r](y).^TU, r = 1,2. princip þ pro charakteristická čísla λ[i]^(1) a charakteristické vektory v[i]^(1) matice S[1] z definice platí S[1].v[i]^(1) = λ[i]^(1).v[i]^(1), i = 1, 2, …, m. [þ ]obdobně pro matici S[2] S[2].v[i]^(2) = (E-S[1]).v[i]^(2) = λ[i]^(2).v[i]^(2), i = 1, 2, …, m; odkud po úpravách S[1].v[i]^(1) = (1 - λ[i]^(2)).v[i]^(2), i = 1, 2, …, m. princip þ z toho pak srovnáním je v[i]^(1) = v[i]^(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 S[1] podle indexu i uspořádána vzestupně a matice S[2] 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ů v[1]^(1), v[2]^(1),… pro třídu ω[1] a v[m]^(1), v[m-1]^(1), … pro třídu ω[2]. princip Matice U normalizační transformace [þ ]bez důkazů U = U[1].U[2,] þ kde U[1] představuje matici transformace autokorelační matice k(y) na matici diagonální k(U[1].y). To lze provést, když kde v[i], i=1,…,m jsou vlastní vektory autokorelační matice k(y). princip Matice U normalizační transformace þ transformovaná matice k(U[1].y) má tvar princip Matice U normalizační transformace þ U[2] převádí výše uvedenou diagonální matici na jednotkovou X. analýza nezávislých komponent Analýza nezávislých komponent princip metody x[1](t) = a[11].s[1](t) + a[12].s[2](t) x[2](t) = a[21].s[1](t) + a[22].s[2](t) Úloha spočívá v nalezení originálních neznámých signálů z jednotlivých zdrojů s[1](t) a s[2](t) máme-li k dispozici pouze zaznamenané signály x[1](t) a x[2](t). Analýza nezávislých komponent princip metody ICA umožňuje určit koeficienty a[ij] 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. Analýza nezávislých komponent model dat þ nechť x =T(x[1],x[2],…, x[m]) je m-rozměrný náhodný vektor (s nulovou střední hodnotou E(x)=0). x[i] = a[i1]^orig.s[1]^orig + a[i2]^orig.s[2]^orig+…+^ a[im]^orig.s[m]^orig i = 1,2,…,m nebo x = A^orig.s^orig s^orig je vektor orginálních skrytých nezávislých komponent a s[1]^orig jsou nezávislé komponenty (předpoklad vzájemně statisticky nezávislosti); A^orig je transformační matice Analýza nezávislých komponent model dat þ definice s = W.x, þ cíl: nalézt lineární transformaci (koeficienty transformační matice W tak, aby vypočítané nezávislé komponenty s[i] byly vzájemně statisticky nezávislé [W = A^-1] [p(s[1],s[2],…,s[m]) = p[1](s[1]).p[2](s[2])… p[m](s[m])] Analýza nezávislých komponent omezení þ 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í 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ěť,… 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 s^orig ß jednotlivé náhodné veličiny x[i] mají pravděpodobnostní rozdělení, které je „bližší“ normálnímu než rozdělení jednotlivých komponent s[i]^orig Odhad nezávislých komponent základní úvaha þ odhad nezávislých komponent si probíhá tak, že hledáme takové řádkové vektory w[i] transformační matice W, aby pravděpodobnostní rozdělení součinu w[i].x bylo „co nejvíce nenormální“ ß tj. nalézt takovou transformační matici W, aby proměnné w[i].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 Odhad nezávislých komponent používané míry nenormality þ koeficient špičatosti þ negativní normalizovaná entropie; þ aproximace negativní normalizované entropie; Odhad nezávislých komponent koeficient špičatosti kurt(s) = E{s^4} – 3(E{s^2})^ 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 = w[i].x 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; 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) = -S[i ]P(s=a[i]).log[2]P(s=a[i]), kde P(s=a[i]) je pravděpodobnost, že náhodná veličina S je rovna hodnotě a[i]. þ pro spojitou proměnnou platí Odhad nezávislých komponent negativní normalizovaná entropie þ 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(s[gauss]) – H(s), kde s[gauss] je náhodná veličiny s normálním rozdělením Odhad nezávislých komponent negativní normalizovaná entropie 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 aproximace negativní normalizované entropie þ 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 þ Použití tzv. p-nekvadratických funkcí kde k[i]>0 je konstanta, G[i] jsou šikovně navržené nelineární funkce a s[gauss] 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(s[gauss])}]^2 Odhad nezávislých komponent aproximace negativní normalizované entropie þ doporučujeme: ^ ^ ^ kde a[1]Îá1,2 nebo Odhad nezávislých komponent příklad použití Odhad nezávislých komponent příklad použití Odhad nezávislých komponent příklad použití Odhad nezávislých komponent příklad použití Odhad nezávislých komponent příklad použití