ANALÝZA A KLASIFIKACE BIOMEDICÍNSKÝCH DAT

                                   prof. Ing. Jiří Holčík, CSc.

                                                VI.
                                       SEKVENČNÍ KLASIFIKACE

                                             ZAČÍNÁME

þ až dosud (bayesovské klasifikátory, neuronové sítě, …) – 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;



                                             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;

                                             ZAČÍNÁME

                                             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);

                                              princip

                                         Waldovo kritérium

þ předpokládejme dichotomický klasifikátor obrazů popsaných příznakovými vektory (x[1], x[2], …);

þ nechť p(x[1], x[2], …, x[i]|ω[1]) a p(x[1], x[2], …, x[i]|ω[2]) jsou i-rozměrné hustoty
pravděpodobnosti výskytu obrazu x = (x[1], x[2], …, x[i]) 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<∞);

                                         Waldovo kritérium

þ pokud pro věrohodnostní poměr







   je Λ[i] £ B, pak d[w](x) = ω[2], je-li Λ[i] ³ A, pak d[w](x) = ω[1]; když Λ[i ]Î (B,A),
pokračujeme s dalším příznakem

                                         Waldovo kritérium

þ jsou-li dány pravděpodobnosti chybné klasifikace





   můžeme určit meze A a B podle vztahů

                                         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.

                                  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í;

                                  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).



                                  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] £ e^B(i), pak d[w](x) = ω[2], je-li Λ[i] ³ e^A(i), pak d[w](x) = ω[1]; když Λ[i ]Î
(e^B(i), e^A(i)), pokračujeme s dalším příznakem

                                  Modifikované waldovo kritérium

                                     URČENÍ FUNKCÍ A(i) A B(i)

þ obvykle experimentálně;

þ jestliže pro mezní funkce platí A(i[max]) = B(i[max]), pak nejpozději pro i = i[max ]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í



                                  Modifikované waldovo kritérium

                                     URČENÍ FUNKCÍ A(i) A B(i)







kde a,b > 0 a q[1],q[2] Î (0,1



                                  Modifikované waldovo kritérium

                                         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 P[rs] je pravděpodobnost, že obraz ze třídy ω[s ]zatřídíme do ω[r].

                                         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;



                                         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;



                                  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