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. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þKDY A KDE SE BUDEME VÍDAT? þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz LITERATURA þHolčík,J.: Analýza a klasifikace dat. Brno, CERM 2012, 112s. þ http://www.iba.muni.cz/res/file/ucebnice/holcik-analyza-klasifikace-dat.pdf þ http://www.iba.muni.cz/index.php?pg=vyuka--ucebnice þ þHolčík, J.: přednáškové prezentace þHolčík, J.: Analýza a klasifikace signálů. [Učební texty VŠ], Brno, FE VUT 1992. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz LITERATURA þDuda,R.O., Hart,P., Stork,D.G. Pattern Classification. New York, John Wiley & Sons 2001 þTheodoridis S., Koutroumbas K., Pattern Recognition. Amsterdam, Elsevier 2009 þMcLachlan,G.J.: Discriminant Analysis and Statistical Pattern Recognition. J.Wiley&Sons, Hoboken 2004 þWebb,A.: Statistical Pattern Recognition. J.Wiley&Sons, Chichester 2002 þMeloun, M., Militký,J.: Statistická analýza experimentálních dat. Praha, Academia 2004. logo-IBA logo-MU © Institut biostatistiky a analýz 0. ČEM TO BUDE? levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ANOTACE þPředmět poskytne informaci o základních metodách a algoritmech pro výběr popisu, hodnocení a klasifikaci biomedicínských dat. Zabývá se základním tříděním klasifikačních přístupů – příznakové a strukturální a uvádí principy obou přístupů. Dále se zabývá podrobně zejména metodami příznakovými. Klasifikace podle diskriminačních funkcí (princip a stanovení diskriminačních funkcí na základě statistických vlastností množiny obrazů) a minimální vzdálenosti. Sekvenční klasifikace. Volba a výběr příznaků. Selekce a extrakce příznaků – analýza hlavních a nezávislých komponent, faktorová analýza. Učení klasifikátorů. Shlukování – podobnost mezi obrazy, podobnost mezi shluky, metody shlukování. Klasifikace pomocí neuronových sítí. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ANOTACE þPředmět poskytne informaci o základních metodách a algoritmech pro výběr popisu, hodnocení a klasifikaci biomedicínských dat. Zabývá se základním tříděním klasifikačních přístupů – příznakové a strukturální a uvádí principy obou přístupů. Dále se zabývá podrobně zejména metodami příznakovými. Klasifikace podle diskriminačních funkcí (princip a stanovení diskriminačních funkcí na základě statistických vlastností množiny obrazů) a minimální vzdálenosti. Sekvenční klasifikace. Volba a výběr příznaků. Selekce a extrakce příznaků – analýza hlavních a nezávislých komponent, faktorová analýza. Učení klasifikátorů. Shlukování – podobnost mezi obrazy, podobnost mezi shluky, metody shlukování. Klasifikace pomocí neuronových sítí. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz OSNOVA þKlasifikace dat – základní terminologie. Klasifikace vs. diskriminační analýza vs. predikce. Klasifikace vs. regrese. Třídění klasifikačních algoritmů - klasifikace pomocí minimální vzdálenosti, pomocí ztotožnění s etalony, pomocí diskriminačních funkcí (lineární, nelineární), pomocí definice hranic mezi jednotlivými třídami. þParametrické vs. neparametrické přístupy. Učení s učitelem, bez učitele, s nedokonalým učitelem. þStrukturální popis a klasifikace. Primitiva a relace, hierarchický a nehierarchický popis, reprezentace klasifikačních tříd pomocí gramatiky, automatu. Strukturální metriky. þPříznakové metody. – Příznak, znak, diskriminátor, prediktor. Klasifikace podle minimální vzdálenosti – metrika, funkce podobnosti, vzdálenost mezi obrazy, vzdálenost mezi obrazem a množinou obrazů. Příklady metrik – deterministické, pravděpodobnostní. Příklady funkcí podobnosti - asociační koeficienty, korelační koeficienty. þPříznaková klasifikace podle diskriminačních funkcí – Fisherův algoritmus, Bayesův klasifikátor. Stanovení diskriminačních funkcí na základě statistických vlastností množiny obrazů. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz OSNOVA þPříznaková klasifikace podle diskriminačních funkcí – Fisherův algoritmus, Bayesův klasifikátor. Stanovení diskriminačních funkcí na základě statistických vlastností množiny obrazů. þLineární diskriminační funkce – dichotomický a multikategoriální problém, zobecněné lineární diskriminační funkce. Lineárně separabilní a neseparabilní případy. Logistická diskriminace. þKontextová klasifikace – Bayesův klasifikátor, Markovovy modely, Viterbiho klasifikátor, skryté Markovovy modely, þVolba a výběr příznaků. Selekce a extrakce (generování) příznaků, Transformace dat a redukce dimenzionality. Ordinační metody. Kritéria a algoritmy selekce příznaků. þFaktorová analýza – princip, důsledky. þAnalýza komponent. Analýza hlavních komponent – princip, důsledky. þAnalýza nelineárních komponent – princip, důsledky. Analýza nezávislých komponent – princip, důsledky. þSekvenční klasifikace. Princip, Waldovo a Reedovo kritérium, jejich modifikované varianty. 1. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz UKONČENÍ PŘEDMĚTU þPožadavky: þústní zkouška èdvě části: qučená rozprava o některém z témat, která budou náplní předmětu; qdiskuze nad individuálním vyřešeným problémem týkajícím se problematiky klasifikace dat a používajícím některé z technik, které budou náplní předmětu; logo-IBA logo-MU © Institut biostatistiky a analýz I. ZAČÍNÁME levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz CÍL ZPRACOVÁNÍ DAT þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz CÍL ZPRACOVÁNÍ DAT þCílem jakéhokoliv zpracování (analýzy) dat je zpravidla posouzení zkoumaného reálného objektu (živého či neživého), který je zdrojem analyzovaných dat, příp. jeho stavu. þToto posouzení může nejčastěji vyústit: þv rozhodnutí o typu či charakteru objektu – např. že daná rostlina je pomněnka lesní (Myosotis sylvatica), zvíře že je medvěd hnědý (Ursus arctos), nebo že daná budova je vystavěna v renesančním slohu – klasifikační úloha, resp. rozpoznávací; þv posouzení kvality stavu analyzovaného objektu, např. zda je pacient v pořádku, nebo má infarkt myokardu, cirhózu jater, apod. – opět klasifikační, resp. rozpoznávací úloha; þv rozhodnutí o budoucnosti objektu – např. zda lze pacienta léčit a vyléčit, zda les po 20 letech odumře, jaké bude sociální složení obyvatelstva na daném území a v daném čase – klasifikační nebo také predikční úloha levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz CÍL ZPRACOVÁNÍ DAT Chceme-li upřesnit dříve definovanýcíl zpracování (analýzy) dat, pak je to právě odhalení toho příčinného deterministického vztahu, navzdory všemu tomu, co to odhalení kazí. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz OBECNÉ SCHÉMA ZPRACOVÁNÍ DAT levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz OBECNÉ SCHÉMA ZPRACOVÁNÍ DAT levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þZPRACOVÁNÍ þpředzpracování èfiltrace rušivých složek x zvýraznění užitečných složek dat; èrekonstrukce a doplnění chybějících údajů; èkonverze typu dat (A/Č převod); èredukce dat; þanalýza dat èurčení hodnot příznaků (reprezentativních parametrů) – pro příznakové klasifikátory; ènalezení primitiv (charakteristických tvarových segmentů) – strukturální klasifikátory þklasifikátor – èzatřídění do diagnostických kategorií OBECNÉ SCHÉMA ZPRACOVÁNÍ DAT levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þZPRACOVÁNÍ þpředzpracování èfiltrace rušivých složek x zvýraznění užitečných složek dat; èrekonstrukce a doplnění chybějících údajů; èkonverze typu dat (A/Č převod); èredukce dat; þanalýza dat èurčení hodnot příznaků (reprezentativních parametrů) – pro příznakové klasifikátory; ènalezení primitiv (charakteristických tvarových segmentů) – strukturální klasifikátory þklasifikátor – èzatřídění do diagnostických kategorií OBECNÉ SCHÉMA ZPRACOVÁNÍ DAT levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þAnalýza (z řečtiny – rozbor, rozčlenění) je vědecká metoda založená na dekompozici celku na elementární části. Cílem analýzy je identifikovat podstatné a nutné vlastnosti elementárních částí celku, poznat jejich podstatu a zákonitosti. OBECNÉ SCHÉMA ZPRACOVÁNÍ DAT http://www.sweb.cz/vachamarek/smery/expresionismus/klee/pict/analyza_zvracenosti.jpg levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þAnalýza (z řečtiny – rozbor, rozčlenění) je vědecká metoda založená na dekompozici celku na elementární části. Cílem analýzy je identifikovat podstatné a nutné vlastnosti elementárních částí celku, poznat jejich podstatu a zákonitosti. þSyntéza je obecné označení pro proces spojení dvou nebo více částí do jednoho celku. S tímto pojmem se lze setkat v různých spojeních: syntéza obrazu, syntéza řeči, syntéza zvuku, chemická syntéza, jaderná syntéza, termonukleární syntéza, syntéza látek, fotosyntéza, proteosyntéza, biosyntéza, evoluční syntéza. OBECNÉ SCHÉMA ZPRACOVÁNÍ DAT levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ANALÝZA þV bloku analýzy se vytváří formální (abstraktní) popis zpracovávaných dat, který nese podstatnou informaci z hlediska kvality rozhodování při klasifikaci. Abstraktní popis se často nazývá obrazem (pattern)Þ rozpoznávání obrazů (pattern recognition). V datech je vybrána určitá množina elementárních vlastností, příp. jejich elementárních částí a jejich vazeb, jejichž způsob popisu je apriori znám. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE þrozumí se rozdělení (konkrétní či teoretické) dané skupiny (množiny) předmětů či jevů na konečný počet dílčích skupin (podmnožin), v nichž všechny předměty či jevy mají dostatečně podobné společné vlastnosti. Vlastnosti podle nichž lze klasifikaci zadat či provádět, určují klasifikační kritéria. Předměty (jevy), které mají podobnou uvažovanou vlastnost tvoří třídu. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þKlasifikátor je stroj (algoritmus,…) s jedním diskrétním výstupem, který udává třídu, do které klasifikátor zařadil vstupní reprezentaci dat þωr = d(x) þd(x) je funkce argumentu x představujícího reprezentaci vstupních dat, kterou nazýváme rozhodovací pravidlo klasifikátoru; þωr je identifikátor klasifikační třídy; ωr| r=1,…,R Î W KLASIFIKÁTOR levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PRINCIPY KLASIFIKACE levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PRINCIPY KLASIFIKACE þ þpomocí diskriminačních funkcí – funkcí, které určují míru příslušnosti k dané klasifikační třídě; þpomocí definice hranic mezi jednotlivými třídami a logických pravidel; þpomocí vzdálenosti od reprezentativních obrazů (etalonů) klasifikačních tříd; þpomocí ztotožnění s etalony; levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz OBECNÉ SCHÉMA ZPRACOVÁNÍ DAT levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þUČENÍ þ þučení klasifikátoru ènastavení klasifikačních kritérií; qs učitelem ldokonalým lnedokonalým qbez učitele – typicky shlukování þvýběr prvků popisu dat èstanovení reprezentativních charakteristických rysů zpracovávaného dat; OBECNÉ SCHÉMA ZPRACOVÁNÍ DAT levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TYPY KLASIFIKÁTORŮ þZákladní členění vychází z reprezentace vstupních dat þpříznakové – každý vstupní data jsou vyjádřena vektorem hodnot (příznaků); èparalelní (např. Bayesův klasifikátor, …) èsekvenční (např. klasifikační stromy, …) þstrukturální (syntaktické) – vstupní data jsou popsána relačními strukturami; þkombinované – jednotlivá primitiva jsou doplněna příznakovým popisem levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TYPY KLASIFIKÁTORŮ þDeterministický klasifikátor èkaždá deterministická klasifikace musí být jednoznačná a úplná, tzn., že každý obraz (předmět, jev) musí patřit do nějaké třídy a nemůže být současně ve dvou či více třídách. þPravděpodobnostní klasifikátor èpravděpodobnostní klasifikátor stanoví pravděpodobnost zařazení obrazů do daných klasifikačních tříd levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TYPY KLASIFIKÁTORŮ þNa základě typů klasifikačních a učících algoritmů: þparametrické; þneparametrické levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE x PREDIKCE þpredikce (z lat. prae-, před, a dicere, říkat) zjevně nese časové hledisko, když jej používáme ve významu předpověď či prognózu, jako soud o tom, co se stane nebo nestane v budoucnosti. V tomto významu je používán např. v analýze či zpracování časových řad. þ(prediction x forecasting) þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE x PREDIKCE þpojem klasifikace je používán, použije-li se klasifikačního algoritmu pro známá data. Pokud jsou data nová, pro která apriori neznáme klasifikační třídu, pak hovoříme o predikci klasifikační třídy. þ http://www.kdnuggets.com/faq/classification-vs-prediction.html (23.8.2010) þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz KLASIFIKACE x PREDIKCE þpojem klasifikace používáme, pokud vybíráme identifikátor klasifikační třídy z určitého diskrétního konečného počtu možných identifikátorů. Pokud určujeme (predikujeme) spojitou hodnotu, např. pomocí regrese, pak hovoříme o predikci, i když tento pojem nemá časovou dimenzi. þHan, J., Kamber, M.: Data Mining Concepts and Techniques. The Morgan Kaufmann Series in Data Management Systems. 2nd edition, Elsevier; Amsterdam(2005), 800 s. þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz DISKRIMINAČNÍ ANALÝZA þtýká se obecně vztahu mezi kategoriální proměnnou a množinou vzájemně vázaných příznakových proměnných. þKonkrétně, předpokládejme že existuje konečný počet, řekněme R, různých a priori známých populací, kategorií, tříd nebo skupin, které označujeme ωr, r=1,…,R a úkolem diskriminační analýzy je nalézt vztah, na základě kterého pro daný vektor příznaků popisujících konkrétní objekt tomuto vektoru přiřadíme hodnotu ωr. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz OBECNÉ SCHÉMA ZPRACOVÁNÍ DAT levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ZÁVĚREM SHRNUTÍ þco je to klasifikace? þklasifikace vs. predikce vs. diskriminační analýza þzákladní principy klasifikace þparametrická vs. neparametrická klasifikace levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þPříprava nových učebních materiálů þpro obor Matematická biologie þbyla podporována projektem ESF þč. CZ.1.07/2.2.00/07.0318 þ„VÍCEOBOROVÁ INOVACE STUDIA MATEMATICKÉ BIOLOGIE“ INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ logo-MU