ANALÝZA A KLASIFIKACE DAT prof. Ing. Jiří Holčík, CSc. KDY A KDE SE BUDEME VÍDAT? LITERATURA þ Holčík, J.: přednáškové prezentace þ Holčík, J.: Analýza a klasifikace signálů. [Učební texty VŠ], Brno, FE VUT 1992. LITERATURA þ Bishop, C.M.: Pattern Recognition and Machine Learning, New York, Springer2006, 738s. þ Han, J., Kamber,M.: Data Mining . Concepts &Techniques. 2nd ed., Amsterdam, Elsevier2006, 770s. þ Tan P-N., Steibach M., Kumar V.: Introduction to Data Mining. Boston, Pearson-Addison Wesley 2006, 769s. 0. ČEM TO BUDE? 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í. Základní přístupy jsou vysvětlovány ve spojitosti s praktickými úlohami. V rámci cvičení studenti řeší samostatné úlohy (projekty), buď zadané učitelem nebo související s řešením jejich diplomové práce. Osnova • Klasifikace dat – základní terminologie. Třídění klasifikačních algoritmů. • Příznakové metody. Klasifikace podle diskriminačních funkcí a minimální vzdálenosti. • Stanovení diskriminačních funkcí na základě statistických vlastností množiny obrazů. • Sekvenční klasifikace. • Volba a výběr příznaků. • Analýza hlavních komponent. • Analýza nezávislých komponent. • Faktorová analýza • Učení klasifikátorů. Metody odhadu hustot pravděpodobnosti a odhad apriorních pravděpodobností klasifikačních tříd. • Shlukování. Podobnost mezi obrazy a shluky. • Metody shlukování. • Klasifikace pomocí neuronových sítí. Osnova • Klasifikace dat – základní terminologie. Třídění klasifikačních algoritmů. • Příznakové metody. Klasifikace podle diskriminačních funkcí a minimální vzdálenosti. • Stanovení diskriminačních funkcí na základě statistických vlastností množiny obrazů. • Sekvenční klasifikace. • Volba a výběr příznaků. • Analýza hlavních komponent. • Analýza nezávislých komponent. • Faktorová analýza • Učení klasifikátorů. Metody odhadu hustot pravděpodobnosti a odhad apriorních pravděpodobností klasifikačních tříd. • Shlukování. Podobnost mezi obrazy a shluky. • Metody shlukování. • Klasifikace pomocí neuronových sítí. Osnova • Klasifikace dat – základní terminologie. Třídění klasifikačních algoritmů. • Příznakové metody. Klasifikace podle diskriminačních funkcí a minimální vzdálenosti. • Stanovení diskriminačních funkcí na základě statistických vlastností množiny obrazů. • Sekvenční klasifikace. • Volba a výběr příznaků. • Analýza hlavních komponent. • Analýza nezávislých komponent. • Faktorová analýza • Učení klasifikátorů. Metody odhadu hustot pravděpodobnosti a odhad apriorních pravděpodobností klasifikačních tříd. • Shlukování. Podobnost mezi obrazy a shluky. • Metody shlukování. • Klasifikace pomocí neuronových sítí. • Strukturální (syntaktická) klasifikace Ukončení předmětu Požadavky: þ ústní zkouška è dvě části: q učená rozprava o některém z témat, která budou náplní předmětu; q diskuze nad 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; I. ZAČÍNÁME OBECNÉ SCHÉMA ZPRACOVÁNÍ SIGNÁLŮ (DAT) OBECNÉ SCHÉMA ZPRACOVÁNÍ SIGNÁLŮ (DAT) OBECNÉ SCHÉMA ZPRACOVÁNÍ DAT ZPRACOVÁNÍ þ předzpracování è filtrace rušivých složek x zvýraznění užitečných složek signálu; è rekonstrukce a doplnění chybějících údajů; è konverze typu dat; è redukce dat; è (A/Č převod); þ 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 ZPRACOVÁNÍ þ předzpracování è filtrace rušivých složek x zvýraznění užitečných složek signálu; è rekonstrukce a doplnění chybějících údajů; è konverze typu dat; è redukce dat; è (A/Č převod); þ 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 þ 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. analýza Během 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 Þ 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. 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. Každá klasifikace musí být úplná, tzn., že každý předmět musí patřit do nějaké třídy a nemůže být současně ve dvou či více třídách. klasifikÁTOR þ 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] Î  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; OBECNÉ SCHÉMA ZPRACOVÁNÍ DAT UČENÍ þ učení klasifikátoru è nastavení klasifikačních kritérií; q s učitelem l dokonalým l nedokonalým q bez učitele – typicky shlukování þ výběr prvků popisu dat è stanovení reprezentativních charakteristických rysů zpracovávaného dat; 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ů); þ strukturální (syntaktické) – vstupní data jsou popsána relačními strukturami; þ kombinované – jednotlivá primitiva jsou doplněna příznakovým popisem II. STRUKTURÁLNÍ KLASIFIKACE Strukturální popis þ relační struktura je vytvořena z určitých elementárních popisných částí dat, tzv. primitiv a vzájemných vztahů mezi nimi – relacemi; þ relační struktury zpravidla vyjadřujeme pomocí grafů; Strukturální popis Strukturální popis Typy relačních struktur þ řetězce (uvuuyzuvw) þ pole (především pro reprezentaci 2D obrazů) þ stromy (relační struktura neobsahující cykly a paralelní cesty) þ obecné grafy Strukturální popis Strukturální popis Kombinovaný Strukturální popis Reprezentace klasifikační třídy þ výčtem relačních struktur (může být bohužel velký až nekonečný) Reprezentace klasifikační třídy þ výčtem relačních struktur (může být bohužel velký až nekonečný) þ generátorem relačních struktur – gramatika è Gramatika je čtveřice G = (V[n], V[t], P, S), kde V[n] a V[t ]jsou konečné disjunktní množiny (abecedy), přičemž prvky množiny V[n ] nazývají neteminální pomocné symboly a prvky V[t ] terminální symboly, S Î V[n ]je tzv. axiom gramatiky nebo také počáteční symbol a P je množina substitučních pravidel tvaru a®b, které definují způsob náhrady dílčí relační struktury  novou strukturou . Reprezentace klasifikační třídy þ výčtem relačních struktur (může být bohužel velký až nekonečný) þ generátorem relačních struktur – gramatika è Příklad gramatiky: G = ((A,B), (0,1), P, A), P = (A ® 0B1, 0B00B, B  „e“). Příklad generování řetezce: A  0B1 ® 00B1  000B1  0001 Reprezentace klasifikační třídy þ výčtem relačních struktur (může být bohužel velký až nekonečný) þ generátorem relačních struktur – gramatika þ příjemcem relačních struktur – automat è různé typy automatů podle charakteru relační struktury a substitučních pravidel – nejjednodušší konečný automat è Konečný stavový automat A je pětice A = (X, S, s[0], S[c], Ꮄ), kde X je konečná vstupní abeceda, S je množina vnitřních stavů, s[0] je počáteční stav automatu, S[c] je množina cílových stavů automatu a Ꮄ: X x S  S je přechodová funkce. Reprezentace klasifikační třídy þ výčtem relačních struktur (může být bohužel velký až nekonečný) þ generátorem relačních struktur – gramatika þ příjemcem relačních struktur – automat è Příklad konečného stavového automatu Reprezentace klasifikační třídy þ výčtem relačních struktur (může být bohužel velký až nekonečný) þ generátorem relačních struktur – gramatika þ příjemcem relačních struktur – automat þ ekvivalence gramatiky a automatu – gramatika a automat jsou ekvivalentní, pokud množina relačních struktur generovaná gramatikou a množina akceptovaná automatem jsou stejné Strukturální klasifikace nedeformované relační struktury þ ztotožnění s reprezentativními relačními strukturami; þ přijetí automatem Strukturální klasifikace deformované relační struktury Strukturální popis Strukturální klasifikace deformované relační struktury þ podle vzdálenosti od etalonu jak vzdálenost určíme? Strukturální klasifikace deformované relační struktury þ podle vzdálenosti od etalonu jak vzdálenost určíme? vzdálenost vs. metrika ? METRIKA - VZDÁLENOST Metrický prostor je neprázdná množina X spolu s funkcí ρ: X × X ® R splňující: è 1. totožnost: ρ(x, y) = 0 Û x = y, "x,y Î X; è 2. symetrie: ρ(x, y) = ρ(y, x), "x,y Î X; è 3. trojúhelníková nerovnost: ρ(x, z) £ ρ(x, y) + ρ(y, z), "x,y,z Î X. ρ je nezáporná funkce. Funkci ρ nazýváme metrika na X. Vzdálenost je hodnota určená podle metriky. Strukturální vzdálenost V případě řetězců lze deformační vlivy vyjádřit (na úrovni primitiv) trojicí tzv. elementárních deformačních transformací – eliminací, substitucí a inzercí Váhovaná levenštejnova metrika Váhovaná levenštejnova metrika Další strukturální metriky þ řetězce è prostá (neváhovaná) Levenštejnova metrika è Hammingova metrika þ stromy : : Klasifikace deformovaných struktur þ výpočet vzdálenosti mezi reprezentativními strukturami (etalony) klasifikační třídy a klasifikovanou strukturou; þ začlenění deformačních pravidel do substitučních pravidel gramatiky (resp. automatu); Vytvoření strukturálního etalonu množiny písmen Vytvoření strukturálního etalonu množiny písmen Shrnutí – pokud možno co nejobecněji þ základní klasifikační úloha je zatřídit (z hlediska prostoru i času) (matematický, abstraktní) popis daného klasifikovaného objektu do odpovídající třídy/kategorie; þ děje se to na základě klasifikačního pravidla, pomocí kterého je definována klasifikační třída; þ klasifikační třída může být definována: è výčtem prvků do ní patřících; è vzdáleností/podobností (od) vzorů té které třídy; è hranicemi, vymezujícími prostor dané třídy.