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 VII. VOLBA A VÝBĚR PŘÍZNAKŮ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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) levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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; levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þ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 è ZAČÍNÁME levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ZÁSADY PRO VOLBU PŘÍZNAKŮ þvýběr veličin s minimálním rozptylem uvnitř tříd levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ZÁSADY PRO VOLBU PŘÍZNAKŮ þvýběr veličin s maximální vzdáleností mezi třídami levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þ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Ů levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þ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í ZÁSADY PRO VOLBU PŘÍZNAKŮ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 003.jpg 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 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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(x1,…,xn) ze všech možných n-tic c příznaků yi, 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 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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 levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz SELEKCE PŘÍZNAKŮ KRITERIÁLNÍ FUNKCE þpro bayesovské klasifikátory (to už jsme si říkali) èje-li x = (x1, x2,…, xn) možná n-tice příznaků, vybraných ze všech možných m hodnot yi, i=1,…,m, n £ m, pak pravděpodobnost chybného rozhodnutí Peme je pro tento výběr rovna levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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“ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz SELEKCE PŘÍZNAKŮ PRAVDĚPODOBNOSTNÍ MÍRY þpro více klasifikačních tříd tzv. bayesovská vzdálenost levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz SELEKCE PŘÍZNAKŮ POMĚR ROZPTYLŮ þrozptyl uvnitř třídy pomocí disperzní matice levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz SELEKCE PŘÍZNAKŮ POMĚR ROZPTYLŮ þrozptyl mezi třídami může být dán þ þ þ þ þpokud levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz SELEKCE PŘÍZNAKŮ POMĚR ROZPTYLŮ þvyjádření vztahu obou rozptylů þ þJr1(x)=tr(D-1(x).B(x)) þJr2(x)=tr(B(x)/tr(D(x)) þJr3(x)=|D-1(x).B(x)|= |B(x)|/|D(x)| þJr4(x) = ln(Jr3(x)) levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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í levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ALGORITMUS OHRANIČENÉHO VĚTVENÍ þpředpoklad: þmonotónnost kritéria selekce - označíme-li Xj množinu obsahující j příznaků, pak monotónnost kritéria znamená, že podmnožiny þX1 Ì X2 Ì … Ì Xj Ì … Ì Xm þ splňuje selekční kritérium vztah þJ(X1) £ J(X1) £ … £ J(Xm) þ þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ALGORITMUS OHRANIČENÉHO VĚTVENÍ þuvažme případ selekce dvou příznaků z pěti þ þ 004.jpg levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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({Xk+1})=max J({XkÈyj}), yj Î{Y-Xk} levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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({Xm-k-1})=max J({Xm-k-yj}), yj Î{Xm-k} levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz 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