Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Analýza a klasifikace dat Bayesov klasifikátor Institut biostatistiky a analýz Masarykova univerzita 4. listopadu 2012 Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Bayesov vzorec Bayesov vzorec P(ωi |x) = p(x|ωi)P(ωi) p(x) = fi(x)πi k j=1 fj(x)πj skupiny ω1, ω2, . . . , ωk πi - apriórna pravdepodobnosť skupiny ωi fi - hustota skupiny ωi Kritéria klasifikácie minimalizovať očakávanú cenu za chybnú klasifikáciu (minimalizovať strednú stratu) minimalizovať celkovú pravdepodobnosť chybného zaradenia maximalizovať aposteriórne pravdepodobnosti maximalizovať pravdepodobnosti Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Minimalizovanie strednej straty Označme Ri ako množinu tých výsledkov, ktoré zaradíme do skupiny ωi Označme c(ωi |ωj ) ako cenu, ktorú zaplatíme, keď prvok zo skupiny ωj nesprávne zaradíme do skupiny ωi , c(ωi |ωi ) = 0 Podmienené očakávanie ceny za chybné zaradenie pre skupinu ωi ECM(i) = k j=1 c(ωj |ωi )P(X ∈ Rj |X ∈ ωi ) Očakávaná cena chybného zaradenia je ECM = k i=1 πi ECM(i) = k i=1 πi ( k j=1 c(ωj |ωi )P(X ∈ Rj |X ∈ ωi )) Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Minimalizovanie strednej straty Zaraďovacie pravidlo x0 zaradíme do skupiny ωi , i = 1, 2, . . . , k, pre ktorú bude mať funkcia gi (x0) najmenšiu hodnotu gi (x0) = k j=1 πj c(ωi |ωj )fj (x0) Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Minimalizovanie celkovej pravdepodobnosti chybného zaradenia V tomto prípade berieme cenu za chybné zaradenie rovnakú pre všetky skupiny, c(ω2|ω1) = c(ω3|ω1) = · · · = c(ωk−1|ωk) = 1 Ale c(ωi |ωi ) = 0 Zaraďovacie pravidlo x0 zaradíme do skupiny ωi , i = 1, 2, . . . , k, pre ktorú bude mať funkcia gi (x0) najmenšiu hodnotu gi (x0) = k j=1,j=i πj fj (x0) Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Maximalizovanie aposteriórnych pravdepodobností Zaraďovacie pravidlo x0 zaradíme do skupiny ωi , i = 1, 2, . . . , k, pre ktorú bude mať funkcia gi (x0) najväčšiu hodnotu gi (x0) = fi (x0) Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Maximalizovanie pravdepodobnosti Nepoznáme apriórne pravdepodobnosti, preto ich zvolíme rovnaké πi = 1 k Ďalší výpočet je rovnaký ako pre minimalizovanie strednej straty Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Hodnotenie úspešnosti klasifikácie Keby sme prvok zaraďovali náhodne len na základe apriórnych pravdepodobností, celková pravdepodobnosť mylnej klasifikácie by bola p = k i=1 πi (1 − πi ) pre k = 2 je p = 0, 5, pre k = 3 je p = 0, 67 Využitie informácie obsiahnutej v dátach a použitie vhodného zaraďovacieho kritéria by malo túto pravdepodobnosť chybného zaradenia podstate znížiť Pravdepodobnosť chybnej klasifikácie je preto užitočnou informáciou o kvalite zaraďovacieho kritéria Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Resubstitúcia Najjednoduchší odhad chybnej klasifikácie Zaraďovanie kritéria použijeme na dáta, z ktorých sme ich získali Vedie k podhodnoteniu odhadovaných pravdepodobností Ak kritérium nedosahuje dobré výsledky na dátach, z ktorých bolo odvodené, môžeme očakávať, že u nových dát bude pracovať ešte horšie Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Cross-validation Rozdelenie súboru na dve skupiny použitím dát jednej skupiny určíme zaraďovacie kritéria dáta druhej skupiny klasifikujeme pomocou týchto odvodených kritérií a porovnáme so skutočným zaradením do jednotlivých skupín Dostaneme nestranný odhad pravdepodobnosti mylnej klasifikácie Nevýhodou je, že množstvo dát, ktoré máme k dispozícii musí byť dostatočne veľké, lebo časť z neho nepoužijeme na určenie klasifikačného kritéria Takto odhadnuté kritéria budú horšie, ako keby sme na ich určenie použili celý súbor dát Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Krížové overovanie: "Jackknife procedure" Kritérium je odhadnuté na základe údajov o všetkých prvkoch okrem i-tého, i = 1, 2, . . . , n Následne je i-tý prvok zaradený pomocou tohto kritéria a toto zaradenie je porovnané so skutočným Odhad je takmer nestranný Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Pravdepodobnosť chybnej klasifikácie Pravdepodobnosť chybnej klasifikácie odhadujeme ako pomer chybne zaradených prvkov ku celkovému počtu prvkov p = n i=1 n ˆi=1 niˆi n , i = ˆi Konfusná matica matica typu kxk na diagonále má správne zaradené prvky, mimo nesprávne zaradené s ohľadom na klasifikáciu Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Upravenie súboru, odstránenie rušenia,... Grafické zobrazenie dát Určenie rozloženia pravdepodobnosti jednotlivých skupín, testy dobrej zhody pre jednotlivé rozloženia Určenie parametrov rozložení a mnohorozmerného rozloženia pre jednotlivé skupiny Výber vhodného klasifikačného kritéria Úspešnosť klasifikácie Porovnanie s iným možným použiteľným klasifikačným kritériom Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Analýza a klasifikace dat Lineárna klasifikácia Institut biostatistiky a analýz Masarykova univerzita 4. listopadu 2012 Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Lineárna diskriminácia Úlohou je nájsť pre skupiny prípadov reprezentovaných ako n-rozmerný vektor lineárnu diskriminačnú funkciu v tvare g(x) = a0 + a1x1 + · · · + anxn, a0 je prah diskriminačnej funkcie, konštanta ai , i = 1, 2, . . . , n, sú váhové koeficienty pre danú skupinu ωi Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Lineárna diskriminácia - dichotomická úloha Máme dve skupiny ω1 a ω2 Diskriminačnú funkciu môžeme napísať v tvare g(x) = w x + w0 pozorovanie x zaradíme do skupiny ω1 ak y(x) ≥ 0 pozorovanie x zaradíme do skupiny ω2 ak y(x) < 0 hraničná priamka: y(x) = w x + w0 = 0 w - normálový vektor hraničnej priamky Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Lineárna diskriminácia pre viac tried Zaraďovacie pravidlo je v tvare gr (x) = wr x + w0 x0 ∈ ωi : gi (x) > gj (x), i = j určuje sa hraničná priamka pre každú dvojicu skupín Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Metoda najmenších štvorcov Označme pre k skupín a n pozorovaní ˜x = (1, x ) ˜w = (w0, w ) ˜W = (˜w1, . . . , ˜wk ) ˜X = (˜x1, . . . , ˜xn) T - matica vyjadrujúca príslušnosť ku skupine koeficienty ˜w určíme pomocou metódy najmenších štvorcov ˜W = (˜X ˜X)−1 ˜X T pozorovanie zaradíme do tej skupiny, pre ktorú má zaraďovacie pravidlo najväčšiu hodnotu gi (x) = ˜w ˜x Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Fisherova diskriminačná funkcia Úlohou je nájsť takú lineárnu kombináciu sledovaných premenných Y = v x, aby lepšie ako ktorákoľvek iná lineárna kombinácia separovala skupiny v tom zmysle, že jej vnútroskupinová variabilita bude čo najmenšia a medziskupinová variabilita čo najväčšia. Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Fisherova diskriminácia - dichotomická úloha Zaraďovacie pravidlo pre dichotomickú úlohu g(x) = v µ1 − v µ2 v Σv chceme maximalizovať koeficienty vyrátame v = Σ−1 (µ1 − µ2) potom Y = x v = x Σ−1 (µ1 − µ2) stred medzi skupinami sa určí pomocou vzťahu c = 1 2 (µ1v + µ2v) = 1 2 (µ1 + µ2) Σ−1 (µ − 1 − µ2) zaradíme do skupiny ω1 ak x v > c Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Fisherova diskriminácia Z predpokladu viacrozmerného normálneho rozloženia pozorovaní v jednotlivých skupinách sa dá odvodiť zaraďovacie pravidlo, ktoré zaradí pozorovanie x0 do skupiny ω1 (v prípade dvoch skupín) ak f1(x0) f2(x0) > 1 Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Fisherova diskriminácia - Bayesov prístup Bayesov vzorec pre dve skupiny πi fi (x) π1f1(x) + π2f2(x) V prípade zaraďovania podľa maximálnej aposteriórnej pravdepodobnosti zaradíme pozorovanie x0 do skupiny ω1 ak f1(x0) f2(x0) > π2 π1 v prípade, že berieme do úvahy aj nejakú strátovu funkciu, môžeme tvar upraviť na f1(x0) f2(x0) > c2π2 c1π1 Analýza a klasifikace dat Zaraďovacie kritéria Hodnotenie úspešnosti kritérií Spracovanie a hľadanie klasifikačného kritéria Lineárna diskriminácia MNČ Fisherova diskriminačná funkcia Z normálneho rozloženia môžeme odvodiť zaraďovaciu funkciu gi (x) = µi Σ−1 x − 1 2 µi Σ−1 µi + ln(π1) odhady odhadom strednej hodnoty µi je výberový priemer (¯x) odhadom variačnej matice pre k je spoločná variančná matica S = 1 k k i=1 Si Analýza a klasifikace dat