ANALÝZA A KLASIFIKACE DAT prof. Ing. Jiří Holčík, CSc. VII. VOLBA A VÝBĚR PŘÍZNAKŮ ZAČÍNÁME þ kolik a jaké 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) ZAČÍNÁME 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; ZAČÍNÁME þ 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; è 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 Volba příznaků þ 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 Zásady pro volbu příznaků þ výběr veličin s minimálním rozptylem uvnitř tříd Zásady pro volbu příznaků þ výběr veličin s maximální vzdáleností mezi třídami Zásady pro volbu příznaků þ 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á Zásady pro volbu příznaků þ 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í 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 Z: Y ^m ® X ^n Výběr příznaků dva principiálně různé způsoby: þ selekce – nalezení a odstranění těch příznakových funkcí, které přispívají k separabilitě klasifikačních tříd nejméně; þ extrakce – transformace původních příznakových proměnných na menší počet jiných příznakových proměnných Výběr příznaků dva principiálně různé způsoby: þ selekce – nalezení a odstranění těch příznakových funkcí, které přispívají k separabilitě klasifikačních tříd nejméně; þ extrakce – transformace původních příznakových proměnných na menší počet jiných příznakových proměnných Abychom dokázali realizovat libovolný z obou způsobů výběru, je třeba definovat a splnit určité podmínky optimality. Výběr příznaků podmínky optimality Nechť J je kriteriální funkce, jejíž pomocí vybíráme příznakové veličiny. V případě selekce vybíráme vektor x=^T(x[1],…,x[n]) ze všech možných n-tic c příznaků y[i], i=1,2,…,m. Optimalizaci selekce příznaků formálně zapíšeme jako Problémy k řešení: è stanovení kriteriální funkce; è stanovení nového rozměru kriteriální funkce; è stanovení optimalizačního postupu Výběr příznaků podmínky optimality Nechť J je kriteriální funkce, jejíž pomocí vybíráme příznakové veličiny. V případě extrakce transformujeme příznakový prostor na základě výběru zobrazení Z z množiny všech možných zobrazení z prostoru Y ^m do X ^n, tj. Příznakový prostor je pomocí optimálního zobrazení Z dán vztahem x =Z(y) Problémy k řešení: è stanovení kriteriální funkce; è stanovení nového rozměru kriteriální funkce; è zvolení požadavků na vlastnosti zobrazení; è stanovení optimalizačního postupu Selekce příznaků pravděpodobnostní míry þ pro bayesovské klasifikátory je-li c = ([1], [2],…, [n]) možná n-tice příznaků, vybraných ze všech možných m hodnot y[i], i=1,…,m, n  m, pak pravděpodobnost chybného rozhodnutí P[eme] je pro tento výběr rovna Selekce příznaků pravděpodobnostní míry þ pro dichotomický bayesovský klasifikátor (R=2) je celková pravděpodobnost chybného rozhodnutí þ pravděpodobnost chyby bude maximální, když integrál bude nulový – obě váhované hustoty pravděpodobnosti budou stejné, pravděpodobnost chyby bude minimální, když se obě hustoty nebudou překrývat. þ Čím větší vzdálenost mezi klasifikačními třídami, tím menší pravděpodobnost chyby ß Integrál může být považován za vyjádření „pravděpodobnostní vzdálenosti“ Selekce příznaků pravděpodobnostní míry þ zobecnění þ J(c) ³ 0; þ J(c) = 0, když jsou hustoty pravděpodobnosti totožné; þ J(c) je maximální, když se hustoty nepřekrývají Selekce příznaků pravděpodobnostní míry Selekce příznaků pravděpodobnostní míry Selekce příznaků pravděpodobnostní míry þ pro více klasifikačních tříd tzv. bayesovská vzdálenost Selekce příznaků poměr rozptylů þ rozptyl uvnitř třídy pomocí disperzní matice Selekce příznaků poměr rozptylů þ rozptyl mezi třídami může být dán þ pokud Selekce příznaků poměr rozptylů þ vyjádření vztahu obou rozptylů J[r1](c)=tr(D^-1(c).B(c)) J[r2](c)=tr(B(c)/tr(D(c)) J[r3](c)=|D^-1(c).B(c)|= |B(c)|/|D(c)| J[r4](c) = ln(J[r3](c)) Nepravděpodobnostní metriky þ Euklidovská metrika (s nejnázornější geometrickou interpretaci) þ Hammingova metrika (Manhattan m.) þ Minkovského metrika Nepravděpodobnostní metriky þ Euklidovská metrika (s nejnázornější geometrickou interpretaci) þ Hammingova metrika (Manhattan m.) þ Minkovského metrika Nepravděpodobnostní metriky þ Euklidovská metrika (s nejnázornější geometrickou interpretaci) þ Hammingova metrika (Manhattan m.) þ Minkovského metrika Nepravděpodobnostní metriky þ Čebyševova metrika Čebyševovu metriku lze vyjádřit jako limitu þ Sokalova metrika Nepravděpodobnostní metriky þ Čebyševova metrika Čebyševovu metriku lze vyjádřit jako limitu þ Sokalova metrika Nepravděpodobnostní metriky þ Čebyševova metrika Čebyševovu metriku lze vyjádřit jako limitu þ Sokalova metrika Nepravděpodobnostní metriky Volba podle toho jak potřebujeme posílit vliv proměnných, u nichž je pro dané obrazy x[1] a x[2] velký rozdíl. Nepravděpodobnostní metriky nevýhody: þ fyzikální nesmyslnost vytvářet kombinaci veličin s různým fyzikálním rozměrem þ jsou-li příznakové veličiny zahrnovány do výsledné vzdálenosti se stejnými vahami, zvyšuje se vliv korelovaných veličin Nepravděpodobnostní metriky možné odstranění (potlačení) nevýhod: vztažením k nějakému vyrovnávacímu faktoru, např. střední hodnotě, směrodatné odchylce, normě daného obrazu x=(x[1], x[2], …,x[n]) rozpětí resp. standardizací podle vztahu Nepravděpodobnostní metriky možné odstranění (potlačení) nevýhod: þ lze i subjektivně či na základě nějaké apriorní informace o úloze přiřadit každé příznakové proměnné váhový koeficient, např. váhovaná Minkovského metrika má tvar Nepravděpodobnostní metriky možné odstranění (potlačení) nevýhod: þ váhování příznaků lze zapsat maticově u[i] = ^TC.x[i], kde prvky transformační matice C jsou definovány jako c[ii] = a[i], pro i = 1, …, n c[ij] = 0, pro i ≠ j Za tohoto formalismu je Euklidova metrika definována vztahem Nepravděpodobnostní metriky možné odstranění (potlačení) nevýhod: þ pokud jsou složky transformovaného obrazu dány lineární kombinací více složek původního obrazu, není ani matice C, ani matice C.^TC čistě diagonální. Použijeme-li místo matice C.^TC inverzní kovarianční matice K^-1, pak definiční vztah pro váhovanou Euklidovu metriku je definičním vztahem pro Mahalanobisovu metriku Nepravděpodobnostní metriky možné odstranění (potlačení) nevýhod: þ pokud jsou složky transformovaného obrazu dány lineární kombinací více složek původního obrazu, není ani matice C, ani matice C.^TC čistě diagonální. Použijeme-li místo matice C.^TC inverzní kovarianční matice K^-1, pak definiční vztah pro váhovanou Euklidovu metriku je definičním vztahem pro Mahalanobisovu metriku þ Kovarianční matice dvou (náhodných) vektorů x=^T(x[1],…,x[m]) a y=^T(y[1],…,y[n]) je dána vztahem [þ ]K(x,y)=E((x-Ex).^T(y-Ey)) = [cov(x[i],y[j])][m,n][] KoefIcienty korelace KoefIcienty korelace to snad opakovat nemusíme Koeficienty asociace Koeficienty asociace þ Koeficienty asociace jsou míry podobnosti mezi obrazy obsahujícími logické (binární, dichotomické) příznakové veličiny. þ Ke zjištění podobnosti je třeba sledovat shodu či neshodu hodnot odpovídajících si příznaků Þ čtyři možné situace Koeficienty asociace • u obou obrazů sledovaný jev nastal (oba odpovídající si příznaky mají hodnotu true) – pozitivní shoda; • u obrazu x[i ]jev nastal (x[ik] = true), zatímco u obrazu x[j] nikoliv (x[jk] = false); • u obrazu x[i ]jev nenastal (x[ik] = false), zatímco u obrazu x[j] ano (x[jk] = true); • u obou obrazů sledovaný jev nenastal (oba odpovídající si příznaky mají hodnotu false) – negativní shoda; Koeficienty asociace Koeficienty asociace þ sledujeme, kolikrát pro všechny příznaky obrazů x[i] a x[j ]nastaly případy shody a neshody è A+D celkový počet shod příznaků; è B+C celkový počet neshod příznaků; è A+B+C+D =n tj. počet příznaků obou obrazů Na základě počtu zjištěných shod a neshod jsou definovány různé koeficienty asociace. Koeficienty asociace þ Jaccardův (Tanimotův) koeficient (není definován pro dvojice obrazů, které vykazují negativní shodu ve všech příznacích); þ Sokalův- Michenerův koeficient þ Diceův koeficient Koeficienty asociace þ Russelův- Raoův koeficient Asociační koeficienty zpravidla nabývají hodnot z intervalu á0,1. V případě R-R koeficientu je při srovnání dvou týchž obrazů hodnota s[RR] = 1 pouze když došlo u všech příznaků jen k pozitivní shodě. Koeficienty asociace þ Rogersův-Tanimotův koeficient þ Hammanův koeficient Na rozdíl od všech předcházejících nabývá Hammanův koeficient hodnot z intervalu á-1,1, přičemž hodnoty -1 nabývá, pokud se příznaky neshodují ani jednou, 0 nabývá když je počet shod a neshod v rovnováze a +1 je v případě úplné shody mezi všemi příznaky. Koeficienty asociace Na základě četností A až D lze vytvářet také dříve uvedené míry: þ Pearsonův korelační koeficient ^þ kritérium shody c^2 Koeficienty asociace Na základě četností A až D lze vytvářet také dříve uvedené míry: þ Hammingova vzdálenost þ Euklidova vzdálenost Koeficienty asociace Z koeficientů asociace, které vyjadřují míru podobnost lze odvodit koeficienty nepodobnosti V případě Jaccardova a Dicova koeficientu nepodobnosti je dodefinována hodnota i pro případy úplné negativní shody tak, že d[J](x[i],x[j]) = d[D](x[i],x[j]) = 0 pro A = B = C = 0 Koeficienty asociace Koeficienty asociace Podobnost mezi třídami þ „podobnost“ jednoho obrazu s více obrazy jedné třídy (skupin, množin, shluků); þ „podobnost“ obrazů dvou tříd (skupin, množin, shluků); þ zavedeme funkci, která ke každé dvojici skupin obrazů (C[i], C[j]) přiřazuje číslo D(C[i], C[j]), které podobně jako míry podobnosti či nepodobnosti (metriky) jednotlivých obrazů musí splňovat minimálně podmínky: Podobnost mezi třídami PODMÍNKY þ (S1) D(C[i], C[j]) ³ 0 þ (S2) D(C[i], C[j]) = D(C[j], C[i]) þ (S3) D(C[i], C[i]) = max[i,j]D(C[i], C[j]) (pro míry podobnosti) þ (S3’) D(C[i], C[i]) = 0 pro všechna i (pro míry podobnosti) METODA NEJBLIŽŠÍHO SOUSEDA þ je-li d libovolná míra nepodobnosti (vzdálenosti) dvou obrazů a C[i] a C[j] jsou libovolné skupiny množiny obrazů {x[i]}, i=1,…,K, potom metoda nejbližšího souseda definuje mezi skupinami C[i] a C[j] vzdálenost Pozn.: Při použití této metody se mohou vyskytovat v jednom shluku často i poměrně vzdálené obrazy. Tzn. metoda nejbližšího souseda může generovat shluky protáhlého tvaru. METODA K NEJBLIŽŠÍch SOUSEDů Je zobecněním metody nejbližšího souseda. Je definována vztahem tj. vzdálenost dvou shluků je definována součtem k nejkratších vzdáleností mezi obrazy dvou skupin obrazů. Pozn.: Při shlukování metoda částečně potlačuje generování řetězcových struktur. METODA nejvzdálenějšího SOUSEDA þ opačný princip než nejbližší sousedi Pozn.: Generování protáhlých struktur tato metoda potlačuje, naopak vede ke tvorbě nevelkých kompaktních shluků. þ je možné i zobecnění pro více nejbližších sousedů METODA centroidní þ vychází z geometrického modelu v euklidovském n rozměrném prostoru a určuje vzdálenost dvou tříd jako čtverec Euklidovy vzdálenosti těžišť obou tříd. þ je-li těžiště třídy definováno jako střední hodnota z obrazů patřících do této třídy, tj. þ pak METODA průměrné vazby þ vzdálenost dvou tříd C[i] a C[j] je průměrná vzdálenost mezi všemi obrazy tříd C[i] a C[j]. Obsahuje-li shluk C[i] P obrazů a C[j] Q obrazů, pak jejich vzdálenost je definována vztahem Pozn.: Metoda často vede k podobným výsledkům jako metoda nejvzdálenějšího souseda. Wardova METODA þ vzdálenost mezi třídami (shluky) je definována přírůstkem součtu čtverců odchylek mezi těžištěm a obrazy shluku vytvořeného z obou uvažovaných shluků C[i] a C[j] oproti součtu čtverců odchylek mezi obrazy a těžišti v obou shlucích C[i] a C[j]. Wardova METODA þ jsou-li a těžiště tříd C[i] a C[j] a těžiště sjednocené množiny, pak Wardova vzdálenost obou shluků je definována výrazem Pozn.: Metoda má tendenci vytvářet shluky zhruba stejné velikosti, tedy odstraňovat shluky malé, resp. velké. Wardova METODA Algoritmy selekce příznaků þ výběr optimální podmnožiny obsahující n (n£ m) příznakových proměnných – kombinatorický problém (m!/(m-n)!n! možných řešení) ß hledáme jen kvazioptimální řešení Algoritmus ohraničeného větvení předpoklad: [þ ]monotónnost kritéria selekce - označíme-li X[j] množinu obsahující j příznaků, pak monotónnost kritéria znamená, že podmnožiny[] X[1] Ì X[2] Ì …  X[j] Ì … Ì X[m] splňuje selekční kritérium vztah J(X[1]) £ J(X[1]) £ …  J(X[m]) Algoritmus ohraničeného větvení uvažme případ selekce dvou příznaků z pěti Algoritmus sekvenční dopředné selekce þ algoritmus začíná s prázdnou množinou, do které se vloží proměnná s nejlepší hodnotou selekčního kritéria; þ v každém následujícím kroku se přidá ta proměnná, která s dříve vybranými veličinami dosáhla nejlepší hodnoty kritéria, tj. J({X[k+1]})=max J({X[k]Èy[j]}), y[j ]Î{Y-X[k]} Algoritmus sekvenční zpětné selekce þ algoritmus začíná s množinou všech příznakových veličin; þ v každém následujícím kroku se eliminuje ta proměnná, která způsobuje nejmenší pokles kriteriální funkce, tj. po (k+1). kroku platí J({X[m-k-1]})=max J({X[m-k]-y[j]}), y[j ]Î{X[m-k]} Algoritmy sekvenční selekce suboptimalita Suboptimalita nalezeného řešení sekvenčních algoritmů je způsobena: þ dopředná selekce - tím, že nelze vyloučit ty veličiny, které se staly nadbytečné po přiřazení dalších veličin; þ zpětná selekce – neexistuje možnost opravy při neoptimálním vyloučení kterékoliv proměnné; Dopředný algoritmus je výpočetně jednodušší, protože pracuje maximálně v n-rozměrném prostoru, naopak zpětný algoritmus umožňuje průběžně sledovat množství ztracené informace. Algoritmus plus P mínus Q þ po přidání p veličin se q veličin odstraní; þ proces probíhá, dokud se nedosáhne požadovaného počtu příznaků; þ je-li p>q, pracuje algoritmus od prázdné množiny; þ je-li p