logo-IBA logo-MU
© Institut biostatistiky a analýz
ANALÝZA A KLASIFIKACE DAT
prof. Ing. Jiří Holčík, CSc.

logo-IBA logo-MU
© Institut biostatistiky a analýz
VI.
SEKVENČNÍ KLASIFIKACE

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ZAČÍNÁME
þaž dosud (bayesovské klasifikátory, klasifikátory s diskriminační hranicí, s minimální
vzdáleností, …) – pevný konstantní počet příznaků
þ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;
èpoužít příznaky, které nesou co nejvíce informace o klasifikační úloze;
è

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ZAČÍNÁME
þsekvenční klasifikace - kompromis mezi velikostí klasifikační chyby a cenou určení příznaků
èklasifikace na základě klasifikačního stromu;

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ZAČÍNÁME
001.jpg
Rozhodovací strom pro klasifikaci rytmu signálu EKG

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ZAČÍNÁME
þsekvenční klasifikace - kompromis mezi velikostí klasifikační chyby a cenou určení příznaků
èklasifikace na základě klasifikačního stromu;
èklasifikace s rostoucím počtem příznaků, přičemž okamžik ukončení klasifikační procedury stanoví
klasifikátor sám podle předem daného kritéria pro kvalitu rozhodnutí (tj. na základě vlastností
klasifikačních tříd, resp. obrazů v nich);

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
PRINCIP
002.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
WALDOVO KRITÉRIUM
þpředpokládejme dichotomický klasifikátor obrazů popsaných příznakovými vektory (x1, x2, …); þnechť
p(x1, x2, …, xi|ω1) a p(x1, x2, …, xi|ω2) jsou i-rozměrné hustoty pravděpodobnosti výskytu obrazu x
= (x1, x2, …, xi) v i-tém klasifikačním kroku v třídách ω1 a ω2;
þnechť A a B jsou konstanty (0<B<1<A<∞);

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
WALDOVO KRITÉRIUM
þpokud pro věrohodnostní poměr
þ
þ
þ
þ je Λi £ B, pak dw(x) = ω2, je-li Λi ³ A, pak dw(x) = ω1; když Λi Î (B,A), pokračujeme s dalším
příznakem

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
WALDOVO KRITÉRIUM
þjsou-li dány pravděpodobnosti chybné klasifikace
þ
þ
þ můžeme určit meze A a B podle vztahů

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
WALDOVO KRITÉRIUM
þOPTIMALITA
þ
þpro libovolné kritérium s pevným počtem n příznaků a s pravděpodobnostmi α a β chybných rozhodnutí
platí pro n, že je větší nebo rovno střední hodnotě počtu kroků podle W.k.; þpro libovolné
sekvenční kritérium je k rozhodnutí potřeba průměrný počet kroků větší než je průměrný počet kroků
podle W.k.

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
MODIFIKOVANÉ WALDOVO KRITÉRIUM
þpřes optimální vlastnosti Waldova kritéria může nastat: þpočet kroků potřebných k přijetí
rozhodnutí může být pro některé obrazy příliš velký, i když střední hodnota počtu kroků pro všechny
obrazy je nízká; þstřední hodnota počtu kroků potřebných k rozhodnutí může být příliš velká,
požadujeme-li malé pravděpodobnosti chybných rozhodnutí;

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
MODIFIKOVANÉ WALDOVO KRITÉRIUM
þPRAXE
þPo určitém počtu kroků se sekvenční výpočet přeruší a dokončí se na základě nějakého rozhodnutí
vycházejícího z nějakého kritéria založeného na pevném počtu příznaků.
þPřerušení:
þpředepsaný počet kroků;
þzavedení proměnných hranic A(i) a B(i).
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
MODIFIKOVANÉ WALDOVO KRITÉRIUM
þNechť A(i) a B(i) jsou nezáporné nerostoucí, resp. nekladné neklesající funkce počtu
klasifikačních kroků. þJe-li Λi £ eB(i), pak dw(x) = ω2, je-li Λi ³ eA(i), pak dw(x) = ω1; když Λi
Î (eB(i), eA(i)), pokračujeme s dalším příznakem

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
MODIFIKOVANÉ WALDOVO KRITÉRIUM
þURČENÍ FUNKCÍ A(i) A B(i)
þobvykle experimentálně;
þjestliže pro mezní funkce platí A(imax) = B(imax), pak nejpozději pro i = imax je klasifikace
ukončena, přičemž střední počet potřebných kroků je menší než u W.k. za cenu snížení kvality
rozhodnutí
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
MODIFIKOVANÉ WALDOVO KRITÉRIUM
þURČENÍ FUNKCÍ A(i) A B(i)
þ
þ
þ
þkde a,b > 0 a q1,q2 Î (0,1ñ
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
MODIFIKOVANÉ WALDOVO KRITÉRIUM
003.jpg

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
REEDOVO KRITÉRIUM
þpro obecný počet tříd zobecněný věrohodnostní poměr
þ
þ
þ
þtakto vypočítaný poměr se srovná s mezní hodnotou r-té třídy A(ωr), určenou jako
þ
þ
þ
þ kde Prs je pravděpodobnost, že obraz ze třídy ωs zatřídíme do ωr.

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
REEDOVO KRITÉRIUM
þpokud pro třídu ωP platí
þΛi(x|ωP) £ A(ωP), p=1,2,…,R,
þ pak předpokládáme, že obraz x nepatří do třídy ωP, kterou lze z dalších úvah vyloučit; þpo
vyloučení všech možných tříd se spočítají nové hodnoty věrohodnostních poměrů pro zbylé třídy a
proces se opakuje; þnení-li možné vyloučit další třídu, zvýší se počet příznaků a klasifikace
pokračuje, dokud nezbude jediná klasifikační třída;
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
REEDOVO KRITÉRIUM
þpro R=2 je Reedovo kritérium ekvivalentní kritériu Waldovu a má tytéž optimální vlastnosti;
þpro R>2 nebyla optimalita prokázána;
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
MODIFIKOVANÉ REEDOVO KRITÉRIUM
þstejně jako Waldova kritéria lze použít proměnných mezí þproměnných práh je zpravidla definován
vztahem
þ

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/28.0043
þ„INTERDISCIPLINÁRNÍ ROZVOJ STUDIJNÍHO OBORU MATEMATICKÁ BIOLOGIE“
INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ
logo-MU