© Institut biostatistiky a analýz Analýza a klasifikace dat – přednáška 5 RNDr. Eva Koriťáková, Ph.D. Podzim 2017 Typy klasifikátorů – podle principu klasifikace 2Koriťáková: Analýza a klasifikace dat • klasifikace pomocí diskriminačních funkcí: – diskriminační funkce určují míru příslušnosti k dané klasifikační třídě – pro danou třídu má daná diskriminační funkce nejvyšší hodnotu • klasifikace pomocí vzdálenosti od etalonů klasif. tříd: – etalon = reprezentativní objekt(y) klasifikační třídy – počet etalonů klasif. třídy různý – od jednoho vzorku (např. centroidu) po úplný výčet všech objektů dané třídy (např. u klasif. pomocí metody průměrné vazby) • klasifikace pomocí hranic v obrazovém prostoru: – stanovení hranic (hraničních ploch) oddělujících klasifikační třídy x1 x2 ? x1 x2 ? 0 1 2 3 4 5 6 7 4 6 8 10 12 14 0 0.05 x1x2 x2 x1 3Koriťáková: Analýza a klasifikace dat Motivace x1 x2 Hranice je nadplocha o rozměru o jedna menší než je rozměr prostoru • ve 2-rozměrném prostoru je hranicí křivka (v lineárním případě přímka) • v 3-rozměrném prostoru plocha (v lineárním případě rovina) Hranice je tedy dána rovnicí: h 𝐱 = 𝐰 𝑇 𝐱 + w0 = 0 Výpočet hranice různými metodami (např. Fisherova LDA, SVM apod. – viz dále) 2-rozměrný prostor 3-rozměrný prostor x1 x2 x3 4Koriťáková: Analýza a klasifikace dat • použití pro lineární klasifikaci • princip: transformace do jednorozměrného prostoru tak, aby se třídy od sebe maximálně oddělily (maximalizace vzdálenosti skupin a minimalizace variability uvnitř skupin) Fisherova lineární diskriminace (FLDA) projekce 1 projekce2 x1 x2 pacienti kontroly centroid pacientů centroid kontrol • předpoklad: vícerozměrné normální rozdělení u jednotlivých skupin Metoda podpůrných vektorů (SVM) 5Koriťáková: Analýza a klasifikace dat • princip: proložení klasifikační hranice (nadroviny) tak, aby byla v co největší vzdálenosti od subjektů z obou tříd • použití pro lineární i nelineární klasifikaci • výhoda oproti FLDA: nemá předpoklady o rozdělení dat x1 x2 • nevýhoda: vyžaduje stanovení parametrů (např. C) a případně i typu jádra Metoda podpůrných vektorů (SVM) - varianty • varianty SVM dle typu vstupních dat: 6 x1 x2 x1 x2 x1 x2 a) b) c) a) lineární verze metody podpůrných vektorů pro lineárně separabilní třídy (anglicky maximal margin classifier) b) lineární verze metody podpůrných vektorů pro lineárně neseparabilní třídy (anglicky support vector classifier) c) nelineární verze metody podpůrných vektorů (anglicky support vector machine) Koriťáková: Analýza a klasifikace dat Lineární SVM – lineárně separabilní třídy 7Koriťáková: Analýza a klasifikace dat pacienti kontroly x2 x1 • proložení klasifikační hranice (nadroviny) tak, aby byla v co největší vzdálenosti od subjektů z obou tříd → tzn. aby byl okolo hranice co nejširší pruh bez bodů • na popis hranice (nadroviny) stačí pouze nejbližší body, kterých je obvykle málo a nazývají se podpůrné vektory (support vectors) h 𝐱 = 𝐰 𝑇 𝐱 + w0 = 0 Lineární SVM – lineárně separabilní třídy 8Koriťáková: Analýza a klasifikace dat • hranice: h 𝐱 = 𝐰 𝑇 𝐱 + w0 = 0 (kde 𝐰 a 𝑤0 je orientace a poloha hranice) • vzdálenost jakéhokoliv bodu od klasifikační hranice je: 𝑑 = 𝐰T 𝐱+𝑤0 𝐰 , kde 𝐰 je velikost vektoru 𝐰 Τ1 𝐰 Τ1 𝐰 x1 x2 h 𝐱 = 0 h 𝐱 > 0 h 𝐱 < 0 • pak na každé straně od dělící přímky máme toleranční pásmo o šířce 1 𝐰 , ve kterém se nenachází žádný bod • pro nejbližší bod 𝐱 𝒊 ze třídy 𝜔 𝐷 zvolíme hodnotu výrazu 𝐰T 𝐱 𝐢 + 𝑤0 rovnu +1 • pro nejbližší bod 𝐱 𝒋 ze třídy 𝜔 𝐻 zvolíme hodnota výrazu 𝐰T 𝐱𝐣 + 𝑤0 rovnu −1 • klasifikace subjektu x do třídy 𝜔 𝐷, resp. 𝜔 𝐻, bude dána tím, jestli je výraz 𝐰T 𝐱 + 𝑤0 větší, resp. menší, než 0 9Koriťáková: Analýza a klasifikace dat Lineární SVM – lineárně separabilní třídy • Pro všechny body z trénovací množiny platí: 𝐰T 𝐱 + 𝑤0 ≥ 1 pro všechna x z 𝜔 𝐷, 𝐰T 𝐱 + 𝑤0 ≤ −1 pro všechna x z 𝜔 𝐻, • hledáme takové hodnoty 𝐰 a 𝑤0, aby byla celková šířka tolerančního pásma 1 𝐰 + 1 𝐰 = 2 𝐰 co největší • hledat maximum funkce 2 𝐰 je to stejné, jako hledat minimum funkce 𝐰 2 a toto minimum se nezmění, když kladnou hodnotu v čitateli umocníme na druhou (což nám zjednoduší výpočty), takže dostáváme následující kriteriální funkci, jejíž hodnotu se snažíme minimalizovat: J 𝐰, 𝑤0 = 𝐰 2 2 → řešení pomocí metody Lagrangeových součinitelů • což můžeme stručněji zapsat jako 𝛿 𝑥 𝑘 𝐰T 𝐱 𝑘 + 𝑤0 ≥ 1, pro k=1, …, N, • kde 𝛿 𝑥 𝑘 = 1 pro 𝐱 𝑘 ze třídy 𝜔 𝐷 a 𝛿 𝑥 𝑘 = -1 pro 𝐱 𝑘 ze třídy 𝜔 𝐻 Lineární SVM – metoda Lagrangeova součinitele • Chceme minimalizovat výraz J 𝐰, 𝑤0 = 𝐰 2 2 za podmínek 𝛿 𝑥 𝑘 𝐰T 𝐱 𝑘 + 𝑤0 ≥ 1 10 𝐿 𝐰, 𝑤0, 𝛌 = 𝐰 2 2 − ෍ 𝑘=1 𝑁 λ 𝑘 𝛿 𝑥 𝑘 𝐰T 𝐱 𝑘 + 𝑤0 − 1 za podmínek λ 𝑘 𝛿 𝑥 𝑘 𝐰T 𝐱 𝑘 + 𝑤0 − 1 = 0, 𝑘 = 1,2, … , 𝑁 𝐰 = ෍ 𝑘=1 𝑁 λ 𝑘 𝛿 𝑥 𝑘 𝐱 𝑘 → patrné, že pro výpočet orientace hranice důležité jen ty body, pro které platí λ 𝑘 > 0 • tuto Lagrangeovu funkci zderivujeme podle proměnných 𝐰 a 𝑤0 a derivace položíme rovny nule → po dalších úpravách dostaneme soustavu nelin. rovnic: ෍ 𝑘=1 𝑁 λ 𝑘 𝛿 𝑥 𝑘 = 0 → každý takový bod musí splňovat podmínku výše, tedy 𝛿 𝑥 𝑘 𝐰T 𝐱 𝑘 + 𝑤0 − 1 = 0 → tedy musí ležet přesně na hranici tolerančního pásma • Zavedeme vektor Lagrangeových součinitelů 𝛌 = λ1, λ2, … , λ 𝑁 , kde λ 𝑘 ≥ 0 a pomocí nich vyjádříme optimalizovanou funkci jako: → takovým bodům říkáme podpůrné vektory a jen na nich závisí umístění a orientace dělící přímky Koriťáková: Analýza a klasifikace dat Lineární SVM – vliv odlehlých hodnot 11 x1 x2 x1 x2 x1 x2 klasifikace v případě dat neobsahujících odlehlé hodnoty klasifikace v případě odlehlé hodnoty, která není podpůrným vektorem (poloha klasifikační hranice se nezmění) klasifikace v případě odlehlé hodnoty, která je podpůrným vektorem (poloha hranice se změní) → lepší použít lineární SVM pro lineárně neseparabilní třídy, kterou tato odlehlá hodnota téměř neovlivní Koriťáková: Analýza a klasifikace dat 12Koriťáková: Analýza a klasifikace dat Lineární SVM – lineárně neseparabilní třídy • zavedeme relaxační proměnné 𝜉 𝑘 ≥ 0 vyjadřující, jak moc každý bod porušuje podmínku 𝛿 𝑥 𝑘 𝐰T 𝐱 𝑘 + 𝑤0 ≥ 1 • 3 situace: • podmínky jsou pak ve tvaru: 𝛿 𝑥 𝑘 𝐰T 𝐱 𝑘 + 𝑤0 ≥ 1 − 𝜉 𝑘 𝜉 𝑘 = 0 0 < 𝜉 𝑘 ≤ 1 𝜉 𝑘 > 1 𝜉 𝑘 = 0 0 < 𝜉 𝑘 ≤ 1 𝜉 𝑘 > 1 1. objekt leží vně pásma a je správně klasifikován: 𝜉 𝑘 = 0 2. objekt leží uvnitř pásma a je správně klasifikován (body s čtverečky): 0 < 𝜉 𝑘 ≤ 1 3. objekt leží na opačné straně hranice a je chybně klasifikován (body s hvězdičkami): 𝜉 𝑘 > 1 x1 x2 13 Lineární SVM – lineárně neseparabilní třídy • když chceme najít hranici poskytující co nejrobustnější klasifikaci, musíme se snažit: • řešíme opět pomocí metody Lagrangeova součinitele • to můžeme vyjádřit jako minimalizaci kriteriální funkce: • kde 𝐶 vyjadřuje poměr vlivu obou členů kriteriální funkce: – pro nízké hodnoty C bude toleranční pásmo širší a počet trénovaních subjektů v tolerančním pásmu a počet chybně klasifikovaných trénovacích subjektů bude vyšší – pro vysoké hodnoty C bude toleranční pásmo užší, ale počet trénovaních subjektů v tolerančním pásmu a počet chybně klasifikovaných trénovacích subjektů bude nižší – maximalizovat šířku tolerančního pásma – minimalizovat počet subjektů z trénovací množiny, které leží v tolerančním pásmu nebo jsou dokonce špatně klasifikovány (tj. těch, pro které 𝜉 𝑘 > 0) J 𝐰, 𝑤0, 𝛏 = 𝐰 2 2 + 𝐶 ෍ 𝑘=1 𝑁 𝜉 𝑘 Koriťáková: Analýza a klasifikace dat SVM – vliv parametru C 14 pacienti kontroly podpůrné vektory x1 x2 pacienti kontroly podpůrné vektory x1 x2 pacienti kontroly podpůrné vektory x1 x2 C = 0.1 C = 1 C = 10 • pro nízké hodnoty C – toleranční pásmo širší, ale počet trénovaních subjektů v tolerančním pásmu a počet chybně klasifikovaných trénovacích subjektů vyšší • pro vysoké hodnoty C – toleranční pásmo užší, ale počet trénovaních subjektů v tolerančním pásmu a počet chybně klasifikovaných trénovacích subjektů nižší • zpravidla nevíme, jaká hodnota parametru C pro data nejvhodnější → volba C podle křížové validace Koriťáková: Analýza a klasifikace dat Lineární SVM – metoda Lagrangeova součinitele • Zavedeme vektor Lagrangeových součinitelů 𝛌 = λ1, λ2, … , λ 𝑁 , kde λ 𝑘 ≥ 0, a pomocí nich vyjádříme optimalizovanou funkci jako: • za podmínek λ 𝑘 𝛿 𝑥 𝑘 𝐰T 𝐱 𝑘 + 𝑤0 − 1 + 𝜉 𝑘 = 0 a 𝜇 𝑘 𝜉 𝑘 ≥ 0, pro 𝑘 = 1, … , 𝑁. 15 𝐿 𝐰, 𝑤0, 𝛏, 𝛌, 𝛍 = 𝐰 2 2 + 𝐶 ෍ 𝑘=1 𝑁 𝜉 𝑘 − ෍ 𝑘=1 𝑁 λ 𝑘 𝛿 𝑥 𝑘 𝐰T 𝐱 𝑘 + 𝑤0 − 1 + 𝜉 𝑘 − ෍ 𝑘=1 𝑁 𝜇 𝑘 𝜉 𝑘 𝐰 = ෍ 𝑘=1 𝑁 λ 𝑘 𝛿 𝑥 𝑘 𝐱 𝑘 • tuto Lagrangeovu funkci zderivujeme podle proměnných 𝐰, 𝑤0 a 𝛏 a derivace položíme rovny nule → po dalších úpravách dostaneme soustavu nelin. rovnic: • Chceme minimalizovat J 𝐰, 𝑤0 = 𝐰 2 2 + 𝐶 σ 𝑘=1 𝑁 𝜉 𝑘 za podmínek 𝛿 𝑥 𝑘 𝐰T 𝐱 𝑘 + 𝑤0 ≥ 1 − 𝜉 𝑘 ෍ 𝑘=1 𝑁 λ 𝑘 𝛿 𝑥 𝑘 = 0 ቑ λ 𝑘 + 𝜇 𝑘 = 𝐶, λ 𝑘 𝛿 𝑥 𝑘 𝐰T 𝐱 𝑘 + 𝑤0 − 1 + 𝜉 𝑘 = 0, 𝜇 𝑘 𝜉 𝑘 = 0. pro 𝑘 = 1, … , 𝑁 Koriťáková: Analýza a klasifikace dat • zobrazíme původní p-rozměrný obrazový prostor nelineární transformací do nového m-rozměrného prostoru tak, aby v novém prostoru byly klasifikační třídy lineárně separabilní 16Koriťáková: Analýza a klasifikace dat Nelineární SVM 17Koriťáková: Analýza a klasifikace dat Nelineární SVM – ukázka 2 dvourozměrný prostor s oddělovací hranicí ve tvaru x1 2 + x2 2 ≤ 1 tatáž situace zobrazená do trojrozměrného prostoru (x1 2, x2 2, 2x1x2) – kruhová hranice se stane lineární 18Koriťáková: Analýza a klasifikace dat Nelineární SVM – ukázka 3 Nelineární SVM • transformace do nového prostoru může proběhnout navýšením počtu proměnných (např. přidáním kvadratických forem původních proměnných, tedy soubor pak bude obsahovat proměnné 𝐱1, x1 2 , 𝐱2, x2 2 , … , 𝐱 𝑝, x 𝑝 2) 19 • tento přístup však výpočetně náročný → použití jader (kernels) • u lineárního SVM pro lineárně separabilní i neseparabilní třídy lze Lagrangeovu funkci přepsat do podoby 𝐿 𝐰, 𝑤0, 𝛌 = ෍ 𝑘=1 𝑁 λ 𝑘 − 1 2 ෍ 𝑖,𝑗 λ𝑖 λ𝑗 𝛿 𝑥 𝑖 𝛿 𝑥 𝑗 𝐱 𝑖 𝑇 𝐱𝑗 • kde si skalární součin 𝐱 𝑖 𝑇 𝐱𝑗 můžeme zapsat obecně jako 𝐾 𝐱 𝑖, 𝐱𝑗 , kde 𝐾 je nějaká funkce, kterou nazveme jádro • typy jader: – lineární jádro: 𝐾 𝐱 𝑖, 𝐱𝑗 = 𝐱 𝑖 𝑇 𝐱𝑗 – polynomiální jádro stupně d: 𝐾 𝐱 𝑖, 𝐱𝑗 = 1 + 𝐱 𝑖 𝑇 𝐱𝑗 𝑑 = 1 + σ𝑙=1 𝑝 x 𝑖𝑙x𝑗𝑙 𝑑 – radiální bázové jádro: 𝐾 𝐱 𝑖, 𝐱𝑗 = exp −𝛾 σ𝑙=1 𝑝 x 𝑖𝑙 − x𝑗𝑙 2 – atd. → lineární SVM nelineární SVM Koriťáková: Analýza a klasifikace dat 20Koriťáková: Analýza a klasifikace dat Příklad Příklad: Bylo provedeno měření objemu hipokampu a mozkových komor (v cm3) u 3 pacientů se schizofrenií a 3 kontrol: 𝐗 𝐷 = 2 12 4 10 3 8 , 𝐗 𝐻 = 5 7 3 9 4 5 . Určete, zda testovací subjekt 𝐱0 = 3,5 9 patří do skupiny pacientů či kontrolních subjektů pomocí metody podpůrných vektorů. pacienti kontroly testovací subjekt 1 2 3 4 5 6 4 5 6 7 8 9 10 11 12 13 Objem hipokampu Objemmozkovýchkomor • výsledkem jsou hodnoty 𝛌 = 0, 1 2 , 1, 1 2 , 1, 0 21Koriťáková: Analýza a klasifikace dat Příklad – řešení pro parametr 𝑪 = 𝟏 • podpůrnými vektory jsou tedy body 𝐱2, 𝐱3, 𝐱4 a 𝐱5, protože jim příslušející 𝜆2, 𝜆3, 𝜆4 𝑎 𝜆5 jsou nenulové. Vypočítáme orientaci hranice: 𝐰 = ෍ 𝑘=1 6 λ 𝑘 𝛿 𝑥 𝑘 𝐱 𝑘 = 1 2 𝐱2 + 𝐱3 − 1 2 𝐱4 − 𝐱5 = 1 2 4 10 + 3 8 − 1 2 5 7 − 3 9 = −1/2 1/2 • Pokud zvolíme takové 𝐱 𝑘, pro které platí 0 < 𝜆 𝑘 < 𝐶, tak podle vztahu λ 𝑘 + 𝜇 𝑘 = 𝐶 musí být 𝜇 𝑘 > 0 a odtud podle vztahu 𝜇 𝑘 𝜉 𝑘 = 0 plyne, že 𝜉 𝑘 = 0. Vzorec se tak zjednoduší na 𝛿 𝑥 𝑘 𝐰T 𝐱 𝑘 + 𝑤0 = 1. Tedy například pro 𝐱2 (0 < 𝜆2 = 1 2 < 𝐶 = 1): 𝐰T 𝐱2 + 𝑤0 = 1 ֜ 𝑤0 = 1 − − 1 2 1 2 4 10 = 1 − 3 = −2 • hranice je tedy dána rovnicí: 𝐰T 𝐱 + 𝑤0 = − 1 2 1 2 𝐱 − 2 • hranice je dána rovnicí: 𝐰T 𝐱 + 𝑤0 = − 1 2 1 2 𝐱 − 2 22Koriťáková: Analýza a klasifikace dat Příklad – řešení pro parametr 𝑪 = 𝟏 • můžeme klasifikovat subjekt 𝐱 = 3,5 9 : 𝐰T 𝐱 + 𝑤0 = − 1 2 1 2 3,5 9 − 2 = −1,75 + 4,5 − 2 = 0,75 23Koriťáková: Analýza a klasifikace dat Příklad – řešení pro parametr 𝑪 = 𝟏 • protože 0,75 > 0, testovací subjekt bude zařazen do třídy pacientů • ověříme, že natrénovaný klasifikátor zařadí subjekty z trénovací množiny tak, jak to odpovídá situaci na obrázku; tj. správně subjekty 𝐱1, 𝐱2, 𝐱3, 𝐱4 a 𝐱6 a chybně subjekt 𝐱5: 𝐰T 𝐱 𝟏 + 𝑤0 = − 1 2 1 2 2 12 − 2 = −1 + 6 − 2 = 3 𝐰T 𝐱 𝟐 + 𝑤0 = − 1 2 1 2 4 10 − 2 = −2 + 5 − 2 = 1 𝐰T 𝐱 𝟑 + 𝑤0 = − 1 2 1 2 3 8 − 2 = −1,5 + 4 − 2 = 0,5 𝐰T 𝐱 𝟒 + 𝑤0 = − 1 2 1 2 5 7 − 2 = −2,5 + 3,5 − 2 = −1 𝐰T 𝐱 𝟓 + 𝑤0 = − 1 2 1 2 3 9 − 2 = −1,5 + 4,5 − 2 = 1 𝐰T 𝐱 𝟔 + 𝑤0 = − 1 2 1 2 4 5 − 2 = −2 + 2,5 − 2 = −1,5 • výsledkem jsou hodnoty 𝛌 = ሾ0, 3,6371, 8,7629, 2,0371, 10, 24Koriťáková: Analýza a klasifikace dat Příklad – řešení pro parametr 𝑪 = 𝟏𝟎 • Polohu dělící přímky určíme opět ze 𝛿 𝑥 𝑘 𝐰T 𝐱 𝑘 + 𝑤0 = 1. Tedy například pro 𝐱2 (0 < 𝜆2 = 3,6371 < 𝐶 = 10): 𝐰T 𝐱2 + 𝑤0 = 1 ֜ 𝑤0 = 1 − − 4 5 2 5 4 10 = 1 − 4 5 = 1 5 • podpůrnými vektory jsou tedy body 𝐱2, 𝐱3, 𝐱4, 𝐱5 a 𝐱6 , protože jim příslušející 𝜆2, 𝜆3, 𝜆4, 𝜆5 𝑎 𝜆6 jsou nenulové. Vypočítáme orientaci hranice: 𝐰 = ෍ 𝑘=1 6 λ 𝑘 𝛿 𝑥 𝑘 𝐱 𝑘 = 3,6371𝐱2 + 8,7629𝐱3 − 2,0371𝐱4 − 10𝐱5 − 0,3629𝐱6 = 3,6371 4 10 + 8,7629 3 8 − 2,0371 5 7 − 10 3 9 − 0,3629 4 5 = −4/5 2/5 • hranice je tedy dána rovnicí: 𝐰T 𝐱 + 𝑤0 = − 4 5 2 5 𝐱 + 1 5 • hranice je tedy dána rovnicí: 𝐰T 𝐱 + 𝑤0 = − 4 5 2 5 𝐱 + 1 5 25Koriťáková: Analýza a klasifikace dat Příklad – řešení pro parametr 𝑪 = 𝟏𝟎 • můžeme klasifikovat subjekt 𝐱 = 3,5 9 : 𝐰T 𝐱 + 𝑤0 = − 4 5 2 5 3,5 9 + 1 5 = −2,8 + 3,6 + 0,2 = 1 26 Příklad – řešení pro parametr 𝑪 = 𝟏𝟎 • protože 1 > 0, testovací subjekt bude zařazen do třídy pacientů • ověříme, že natrénovaný klasifikátor zařadí subjekty z trénovací množiny tak, jak to odpovídá situaci na obrázku; tj. správně subjekty 𝐱1, 𝐱2, 𝐱3, 𝐱4 a 𝐱6 a chybně subjekt 𝐱5: 𝐰T 𝐱 𝟏 + 𝑤0 = − 4 5 2 5 2 12 + 1 5 = − 8 5 + 24 5 + 1 5 = 17 5 = 3,4 𝐰T 𝐱 𝟐 + 𝑤0 = − 4 5 2 5 4 10 + 1 5 = − 16 5 + 20 5 + 1 5 = 5 5 = 1 𝐰T 𝐱 𝟑 + 𝑤0 = − 4 5 2 5 3 8 + 1 5 = − 12 5 + 16 5 + 1 5 = 5 5 = 1 𝐰T 𝐱 𝟒 + 𝑤0 = − 4 5 2 5 5 7 + 1 5 = − 20 5 + 14 5 + 1 5 = − 5 5 = −1 𝐰T 𝐱 𝟓 + 𝑤0 = − 4 5 2 5 3 9 + 1 5 = − 12 5 + 18 5 + 1 5 = 7 5 = 1,4 𝐰T 𝐱 𝟔 + 𝑤0 = − 4 5 2 5 4 5 + 1 5 = − 16 5 + 10 5 + 1 5 = − 5 5 = −1 Koriťáková: Analýza a klasifikace dat Příklad – srovnání výsledků pro 𝑪 = 𝟏 a 𝑪 = 𝟏𝟎 27Koriťáková: Analýza a klasifikace dat 𝑪 = 𝟏: 𝑪 = 𝟏𝟎: Detailní řešení příkladu zde: http://portal.matematickabiologie.cz/res/file/Vicerozmerky%20-%20kap11_4%20-%20SVM%20-%20reseni%20prikladu(1).pdf Sekvenční klasifikace 28Koriťáková: Analýza a klasifikace dat Typy klasifikátorů 29Koriťáková: Analýza a klasifikace dat 1. Podle reprezentace vstupních dat: – příznakové klasifikátory: paralelní x sekvenční – strukturální (syntaktické) klasifikátory – kombinované klasifikátory 2. Podle jednoznačnosti zařazení do skupin: – deterministické klasifikátory – pravděpodobnostní klasifikátory 3. Podle typů klasifikačních a učících algoritmů: – parametrické klasifikátory – neparametrické klasifikátory 4. Podle způsobu učení: – učení s učitelem: dokonalým x nedokonalým – učení bez učitele 5. Podle podle principu klasifikace: – klasifikace pomocí diskriminačních funkcí – klasifikace pomocí vzdálenosti od etalonů klasifikačních tříd – klasifikace pomocí hranic v obrazovém prostoru Typy klasifikátorů – podle reprezentace vstupních dat 30Koriťáková: Analýza a klasifikace dat • příznakové – vstupní data vyjádřena vektorem hodnot jednotlivých proměnných (příznaků): – paralelní – zpracování vektoru jako celku (např. Bayesův klasifikátor) – sekvenční – zpracování (občas i měření) proměnných postupně (např. klasifikační stromy) • strukturální (syntaktické) – vstupní data popsána relačními strukturami • kombinované – jednotlivá primitiva doplněna příznakovým popisem Sekvenční klasifikace - motivace • až dosud (bayesovské klasifikátory, klasifikátory s diskriminační hranicí, s minimální vzdáleností, …) – pevný konstantní počet příznaků 31Koriťáková: Analýza a klasifikace dat • kolik a jaké proměnné? – málo proměnných – možná chyba klasifikace – moc proměnných – možná nepřiměřená pracnost, vysoké náklady – použít proměnné, které nesou co nejvíce informace o klasifikační úloze • sekvenční klasifikace – kompromis mezi velikostí klasifikační chyby a cenou určení příznaků – klasifikace s rostoucím počtem proměnných, 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. objektů v nich) – klasifikace na základě klasifikačního stromu Klasifikační (rozhodovací) stromy a lesy 32Koriťáková: Analýza a klasifikace dat Zmenšený hipokampus Zmenšená amygdalaZvětšené komory Pacient Kontrola KontrolaPacient Ano Ne Ano Ne Ano Ne Princip: Postupné rozdělování datasetu do skupin podle hodnot jednotlivých proměnných. Klasifikační lesy – použití více klasifikačních stromů ke klasifikaci. Princip: Seřadíme proměnné podle množství informace, které nesou, a pak opakovaně provádíme klasifikaci objektu (subjektu) s postupně se zvyšujícím počtem proměnných, dokud objekt nejsme schopni jednoznačně zařadit 33 Klasifikace s rostoucím počtem proměnných oblast nejistoty x1 x2 hranice přidání proměnné x1 x3 x2 hranice oblast nejistoty Kritéria pro řízení sekvenčního klasifikátoru: • Waldovo kritérium • Reedovo kritérium • Modifikované Waldovo kritérium • Modifikované Reedovo kritérium Koriťáková: Analýza a klasifikace dat Waldovo kritérium 34Koriťáková: Analýza a klasifikace dat • objekt x popsán množinou hodnot proměnných {x1, x2, …} • mějme p(x1, x2, …, xi|ω1) a p(x1, x2, …, xi|ω2), což jsou i-rozměrné hustoty pravděpodobnosti (tzn. dané prvními i proměnnými) výskytu objektu x = (x1, x2, …, xi) v i-tém klasifikačním kroku v třídách ω1 a ω2 • A a B jsou konstanty (0