Analýza a klasifikace dat přednáška 8 MU RNDr. Eva Janousova IBA » Podzim 2014 Volba a výběr proměnných - úvod • kolik a jaké proměnné (příznaky)? — málo příznaků - možná chyba klasifikace; — moc příznaků - možná nepřiměřená pracnost, vysoké náklady; KOMPROMIS (potřebujeme kritérium) • přípustná míra spolehlivosti klasifikace (např. pravděpodobnost chybné klasifikace, odchylka obrazu vytvořeného z vybraných příznaků vůči určitému referenčnímu) • určit ty příznakové proměnné, jejichž hodnoty nesou nejvíce informace z hlediska řešené úlohy, tj. ty proměnné, kterou jsou nejefektivnější pro vytvoření co nejoddělenějších klasifikačních tříd mu ,-.*■»»., Janoušová: Analýza a klasifika Volba a výběr proměnných algoritmus pro určení příznakových veličin nesoucích nejvíce informace pro klasifikátor není dosud teoreticky formalizován - pouze dílčí suboptimální řešení spočívající: — ve výběru nezbytného množství veličin z předem zvolené množiny - selekce — vyjádření původních veličin pomocí menšího počtu skrytých nezávislých veličin, které zpravidla nelze přímo měřit, ale mohou nebo také nemusí mít určitou věcnou interpretaci - extrakce počáteční volba příznakových veličin je z velké části empirická, vychází ze zkušeností získaných při empirické klasifikaci člověkem a závisí kromě rozboru podstaty problému i na technických (ekonomických) možnostech a schopnostech hodnoty veličin určit Janoušová: Analýza a klasifika ;J^J Zásady pro volbu příznaků I výběr veličin s minimálním rozptylem uvnitř tříd -\-T~í z í- i výběr veličin s maximální vzdáleností mezi třídami Pcxi> —-X. Xo Janoušová: Analýza a klasifikace dat IBA IMJ 4 Zásady pro volbu příznaků II • výběr vzájemně nekorelovaných veličin — pokud jsou hodnoty jedné příznakové veličiny závislé na příznacích druhé veličiny, pak použití obou těchto veličin nepřináší žádnou další informaci pro správnou klasifikaci - stačí jedna z nich, jedno která • výběr veličin invariantních vůči deformacím — volba elementů formálního popisu závisí na vlastnostech původních i předzpracovaných dat a může ovlivňovat způsob předzpracování A A A A M @ A H A A A E § 0 Hl ffl mu ,-.*■»»., Janoušová: Analýza a klasifikace dat *|L ^jjyjp 5 Výběr příznaků formální popis objektu původně reprezentovaný m rozměrným vektorem se snažíme vyjádřit vektorem n rozměrným tak, aby množství diskriminační informace obsažené v původním vektoru bylo v co největší míře zachováno dva principiálně různé způsoby: 1. selekce - nalezení a odstranění těch příznakových funkcí, které přispívají k separabilitě klasifikačních tříd nejméně 2. extrakce - transformace původních příznakových proměnných na menší počet jiných příznakových proměnných se uxor. y* * ---x---- k.lasifikätok. "r v+ * ■ ---x---- *1 u. y* . KLASIFIVCÁTOe. Janoušová: Analýza a klasifikace dat /BA Extrakce příznaků • jedním z principů výběru příznaků • transformace původních příznakových proměnných na menší počet jiných příznakových proměnných =^> tzn. hledání (optimálního) zobrazení Z, které transformuje původní m-rozměrný prostor (obraz) na prostor (obraz) n-rozměrný (m > n) • pro snadnější řešitelnost hledáme zobrazení Z v oboru lineárních zobrazení • 3 kritéria pro nalezení optimálního zobrazení Z: - obrazy v novém prostoru budou aproximovat původní obrazy ve smyslu minimální střední kvadratické odchylky - rozložení pravděpodobnosti veličin v novém prostoru budou splňovat podmínky kladené na jejich pravděpodobnostní charakteristiky - obrazy v novém prostoru budou minimalizovat odhad pravděpodobnosti chyby Janoušová: Analýza a klasifikace dat *|L ^jjyjj\ 7 Analýza hlavních komponent - opakování • anglicky Principal component analysis (PCA) • snaha redukovat počet proměnných nalezením nových latentních proměnných (hlavních komponent) vysvětlujících co nejvíce variability původních proměnných • nové proměnné (Y^ Y2) lineární kombinací původních proměnných (Xv X2) PCA-opakování • vstup do PCA: - kovarianční matice - matice korelačních koeficientů • hlavní komponenty odpovídají vlastním vektorům kovarianční matice (či matice korelačních koef.) • variabilita vysvětlená příslušnou komponentou odpovídá vlastním číslům • vlastní vektory seřazeny podle vlastních hodnot (sestupně) =^> vybráno prvních n komponent vyčerpávajících nejvíce variability původních dat • předpoklady: kvantitativní proměnné s normálním rozdělením Janoušová: Analýza a klasifika ;J^J PCA- obecněji dáno K obrazů charakterizovaných m příznakovými proměnnými (nerozdělenými do klasifikačních tříd) N _Q O příznaky Pl P2 •" Pm xl x2 • • • XK aproximujme nyní kterýkoliv obraz xk lineární kombinací n ortonormálních vektorů ej (n < m) koeficienty cki lze považovat za velikost i-té souřadnice vektoru xk vyjádřeného v novém systému souřadnic s bází i=l,2,...,n n Cj e ki 1 _ T Cki ~ Xk ei Janoušová: Analýza a klasifikac (^|| PCA - kritérium minimální střední kvadratické odchylky nalezení optimálního zobrazení kvadratické odchylky: pomocí kritéria minimální střední vztah lze pomocí dříve uvedených vztahů upravit na: n Sk = i=l 'ki střední kvadratická odchylka pro všechny obrazy xk, k=l,...,K je s2 = 1 K V _2 1 K Z. k=l K n K k=l i=í K K k=i .e Janoušová: Analýza a klasifikace dat IBA IMJ 11 PCA - kritérium minimální střední kvadratické odchylky • musíme zvolit bázový systém ej tak, aby střední kvadratická odchylka e2 byla minimální En /=1 Ckiei s bázovým systémem optimálním podle kritéria minimální střední kvadratické chyby, nazýváme diskrétní Karhunenův - Loevův rozvoj střední kvadratická odchylka 1 X, 1 K n 6 ~ V 2^Sk ~ 2JX* K k=\ K k=\ -1^ 7=1 1 K v Z~iXk' Xk K k=\ je minimální, když je maximální výraz ^reř.^(x).eř? kde *:(x) = - 7=1 K xk -xk k k=\ je autokorelační matice řádu m. Protože je symetrická a semidefinitní, jsou její vlastní čísla \, i=l,...,m, reálná a nezáporná a vlastní vektory v,, jsou buď ortonormální, neboje můžeme ortonormalizovat (v případě násobných vlastních čísel). Janoušová: Analýza a klasifikace dat IBA IMJ 12 PCA - kritérium minimální střední kvadratické odchylky • uspořádáme-li vlastní čísla sestupně podle velikosti, tj. A1>A2>...>Am>0 a podle toho očíslujeme i odpovídající vlastní vektory, lze dokázat, výše uvedený výraz dosahuje maxima, jestliže platí ej = Vj, i=l,...,n a pro velikost maxima je n n max£ef./r(x).eŕ = £4. 7=1 7=1 pak pro minimální střední kvadratickou platí K n nm s2 = min 1 ä n n m = ^Ih|2"£4 =ŕr(/r(x))-ž>, = k=\ 7=1 7=1 i=n+\ Janoušová: Analýza a klasifikace dat *jL . ^3 PCA - vstupní matice • autokorelační matice - data nejsou nijak upravena (zohledňována průměrná hodnota i rozptyl původních dat) • kovarianční (disperzní) matice - data centrována (od každé příznakové proměnné odečtena její střední hodnota) - zohledňován rozptyl původních dat • matice korelačních koeficientů - data standardizována (odečtení středních hodnot a podělení směrodatnými odchylkami) - použití pokud mají proměnné různá měřítka • každou úpravou původních dat ale přicházíme o určitou informaci!!! Janoušová: Analýza a klasifikac PCA-vlastnosti Karhunenova-Loevova rozvoje * při daném počtu n členů rozvoje poskytuje ze všech možných aproximací nejmenší střední kvadratickou odchylku * při použití disperzní matice jsou transformované souřadnice nekorelované; pokud se výskyt obrazů řídí normálním rozložením zajišťuje nekorelovanost i jejich nezávislost * vliv každého členu uspořádaného rozvoje se zmenšuje s jeho pořadím * změna požadavků na velikost střední kvadratické odchylky nevyžaduje přepočítávat celý rozvoj, nýbrž jen změnit počet jeho členů Janoušová: Analýza a klasifikace dat *jL .. ^5 PCA - geometrická interpretace OBRALO použití obou hlavních komponent Yi použití 1. hlavní komponenty Y2 použití 2. hlavní komponenty Y- v Vi Yi A A Janou y2 ová: Analýza a klasifikace dat IBA IMJ 16 PCA-příklad data: 35 - A 101 16 30 - 25 - B 105 18 20 - 15 - C 103 42 10 - 5L- D 98 23 92 E 93 6 100 102 104 106 Janoušová: Analýza a klasifikace dat IBA W 17 PCA-příklad data: A 101 16 B 105 18 C 103 42 D 98 23 E 93 6 Janoušová: Analýza a klasifikace dat IBA W 18 PCA-příklad data: A 101 16 B 105 18 C 103 42 D 98 23 E 93 6 n-r 100 102 104 106 n-1-1-r _l_I_I_l_ -20 -15 -10 -5 0 5 10 15 20 25 Janoušová: Analýza a klasifikace dat IBA IMJ 19 PCA - rozdělení do tříd Výskyt obrazů v jednotlivých klasifikačních třídách bude popsán podmíněnými hustotami pravděpodobnosti p(x|cor), r=l,2,...,R a apriorní pravděpodobnost klasifikačních tříd bude P(cor). x- Vtom případě autokorelační matice bude R p(x).dx r=\ Janoušová: Analýza a klasifikace dat IBA W 20 PCA - rozdělení do tříd disperzní matice - vztah 1: 1)1 (x) = Z F^°r )• j (x " V r )•(* - Hr )r | cor )dx r=\ cym kde \ir = Jx.^xl íyr)í/x rozlišení klasifikačních tříd jen podle disperze transformované příznak, proměnné nekorelované x- Janoušová: Analýza a klasifikac PCA - rozdělení do tříd • disperzní matice-vztah 2: R D° (x) = ^ P(ú)r). J (x - n).(x - \i)T .p(x \cor).dx= | (x - n).(x - \i)T .p(x).dx r=\