1/28
Klasifikace a predikce Roman LUKÁŠ
2/28
Základní pojmy • •
Klasifikace = zařazení daného objektu do jisté skupiny na základě jeho vlastností Dvě fáze klasifikace: I.
Na základě trénovacích vzorů (u nichž víme, do jaké skupiny patří) určení „pravidel“, podle nichž bude klasifikace prováděna II. Pravidla z kroku I. jsou testována na jiných vzorech, následně použita pro zařazování nových dat
• Predikce = předpověď jisté hodnoty (ze spojité funkce) pro daný objekt
3/28
Klasifikace: Ilustrace I. Fáze:
Klasifikační algoritmus
Trénovací data Jméno
Věk
Příjem
Úvěryschopnost
Jan Novák
<= 30
malý
špatná
Ota Tesař
31..40
velký
dobrá
Vít Tomšů
> 40
střední
špatná
Leoš Nový
31..40
velký
dobrá
…
…
…
…
II. Fáze: Trénovací data
Klasifikační pravidla: If Věk = “31..40” and Příjem = “velký” then Úvěryschopnost = „dobrá“ …
Klasifikační pravidla
Jméno
Věk
Příjem
Úvěryschopnost
Petr Malý
31..40
velký
dobrá
Jakub Král
<= 30
malý
špatná
…
…
…
…
Nová data
(Jan Ryba, 31..40, velký, ?)
? = dobrá
4/28
Příprava dat pro klasifikaci • Čištění dat = Redukce „šumu“ v datech, upravení dat z chybějící hodnotou • Významnostní analýza = odstranění nepotřebných atributů v datech pro danou klasifikaci • Transformace dat = zobecnění dat, například číselných na diskrétní hodnoty Příklad: Konkrétní zisk → malý/velký • Speciální případ transformace: Normalizace dat Příklad: obecný interval → interval <0, 1>
5/28
Porovnávání klasifikačních metod • Přesnost předpovědí = schopnost dobře třídit neznámá data • Rychlost = výpočetní složitost pro vygenerování a používání klasifikačních pravidel • Robustnost = schopnost vytvořit správný model, pokud daná data obsahují šum a chybějící hodnoty • Stabilita = schopnost vytvořit správný model pro velké množství dat • Interpretovatelnost = jak je model složitý pro pochopení
6/28
Rozhodovací strom Příklad: Zařazení osoby do tříd: (Koupí počítač/nekoupí počítač) Věk <= 30 Student ne NE
31..40
> 40 Příjem
ANO ano ANO
malý NE
velký ANO
7/28
Vytvoření rozhodovacího stromu function induce_tree(Example_set, Properties) : TTree; begin if all entries in Example_set are in the same class then return leaf node labeled with this class else if Properties is empty then return leaf node labeled with most common class else begin select a property P, delete it from Properties and make it the root of the current tree; for each value V of P do begin create a branch of the tree labeled with V; Ex_V = elements of Example_set with V for property P call induce_tree(Ex_V, Properties) and attach result to branch V; end; end; end;
8/28
Výběr „vhodné“ vlastnosti P • Nechť S je množina vzorků rozdělovaných do tříd C1, …, Cm • Nechť si je počet vzorků z množiny S ve třídě Ci • Definujme očekávanou informaci I(s1, …, sm) jako: m
I ( s1 ,..., sn ) = −∑ pi log2 ( pi ) i =1
pi = si /|S|
• Nechť jistá vlastnost P má může nabývat hodnot a1, …, av. Proveďme rozklad S na vzájemně disjunktní podmnožiny S1, …, Sv: Sj ⊆ S, Sj = {x: vlastnost P prvku x má hodnotu aj} pro j = 1..v • Nechť sij je počet vzorků ze třídy Ci ve množině Sj • Definujme entropii E(P) jako: v
s1 j + ... + smj
j =1
|S|
E ( P ) = −∑
m
(∑ pij log2 pij ) pij = sij /|Sj| i =1
• Vybereme vlastnost P s největší hodnotou I(s1, …, sm) – E(P) !
9/28
Ořezání stromu 2 metody pro ořezání stromu: •
Prepruning = již v průběhu vytváření stromu nejsou generovány větve, které mají malý význam pro rozhodování
•
Postpruning = nejdříve vytvořen strom jako celek, teprve pak jsou větve s malým významem odstraněny
10/28
Rozhodovací strom ⇒ klasif. pravidla Příklad:
Věk <= 30 Student
ne NE
Zařazení osoby do tříd: (Koupí počítač/nekoupí počítač)
31..40 > 40 ANO
ano
Příjem malý
ANO
if Věk = “<= 30“ and Student = “ne” if Věk = “<= 30“ and Student = “ano” if Věk = “31..40“ if Věk = “> 40“ and Příjem = “malý” if Věk = “> 40“ and Příjem = “velký”
NE
velký ANO
then result = NE then result = ANO then result = NE then result = NE then result = ANO
11/28
Bayesova klasifikace 1/3 Označení pravděpodobností • P(X) = pravděpodobnost jevu X • P(H|X) = pravděpodobnost jevu H, pokud víme, že nastal jev X Bayessův teorém:
P( X | H ) P( H ) P( H | X ) = P( X )
12/28
Bayesova klasifikace 2/3 • Nechť je dán jistý vzorek dat X = (x1, …, xn), který má být zařazen do jedné z tříd C1, …, Cm. Zařadíme jej do třídy Ci, pro kterou platí: P(Ci | X ) je maximální. • Protože P(Ci | X ) =
P ( X | Ci ) P (Ci ) , kde P(X) je konst. P( X )
hledáme maximální P(Ci | X) P(Ci)
13/28
Bayesova klasifikace 3/3 si = počet trénovacích vzorů ve třídě Ci s = počet všech trénovacích vzorů
si P (Ci ) = s
i
n
P ( X | Ci ) = ∏ P ( x k | C i ) k =1
P(xk | Ci)
sik xk je diskrétní atribut: P ( xk | Ci ) = si kde sik je počet trénovacích vzorů ze třídy Ci splňující podmínku, že jeho k-tý atribut = xk xk je spojitý atribut: P(xk | Ci) = g(xk, µCi, σCi) kde g(xk, µCi, σCi) je Gaussova normální funkce
14/28
Klasifikace: NS Backpropagation Činnost jednohon neuronu: …
x1 w1 w2 x2 xn
θ
∑xw i =1
i
i
+θ
f
wn
Schéma neuronové sítě: x1 x2 …
…
… xi
Oj
wij
Ok
wjk
Vstupní vrstva Skrytá vrstva
Výstupní vrstva
15/28
NS Backpropagation: Algoritmus 1/2 Inicializační část: • Inicializuj všechny váhy wij a biasy θj libovolnými malými hodnotami
Šíření vstupu k výstupu: • Postupně pro každý trénovací vzor dělej: • Pro každý neuron ve skryté vrstvě spočítej:
I j= ∑ wij Oi + θ j i
• Pro každý neuron ve výstupní vrstvě spočítej:
1 O j= −I j 1+ e
16/28
NS Backpropagation: Algoritmus 2/2 Zpětné šíření chyby: • Pro každý neuron výstupní vrstvy spočítej:
Err j = O j (1 − O j )(T j − O j )
Poznámka: Tj je výstup, který měl vyjít
• Pro každý neuron skryté vrstvy spočítej:
Err j = O j (1 − O j )∑ Errk w jk k
• Každou váhu wij modifikuj následovně:
∆wij = (l ) Errj Oi
wij = wij + ∆wij
∆θ j = (l) Errj
θ j = θ j + ∆θ j
• Každý bias θj modifikuj následovně:
Poznámka: (l) ∈ <0, 1> je tzv. koeficient učení doporučená hodnota: l = 1/t, kde t je akt. počet iteračních kroků
17/28
Další metody klasifikace • k-shlukování – Založeno na vytvoření k-tříd. Každá třída má svého reprezentanta. Neznámý prvek je zařazen do té třídy jehož reprezentant je nejpodobnější neznámému prvku. • Generické algoritmy – využití myšlenek přírodního vývoje. • Fuzzy logika – pravidla pro rozdělování do tříd nemají diskrétní charakter ale spojitý.
18/28
Predikce: Lineární regrese 1/2 • Metoda nejmenších čtverců: Y = aX + b
= skutečné hodnoty
x1
x2
x3
x4
• Snaha najít koeficienty a, b tak, aby součet znázorněných čtverců dosáhl co nejmenší hodnoty:
19/28
Predikce: Lineární regrese 2/2 • Soubor hodnot: (x1, y1), (x2, y2), …, (xs, ys) • Výpočet koeficientů a, b pro regresní přímku Y = aX + b: s
a =
∑ (x i =1
i
s
∑
i =1
− x )( y i − y )
b = y − ax
( xi − x ) 2
Poznámka:
1 x = s
s
∑
i =1
xi
1 y = s
s
∑
i =1
yi
20/28
Vícenásobná a nelineární regrese • Vícenásobná regrese – výsledná hodnota y je závislá na více parametrech x1, x2 , …, xn • Regresní funkce je potom ve tvaru:
Y = a1X1 + a2X2 + … + anXn + b • Nelineární regrese – většinou transformujeme na lineární regresi Příklad:
Y = aX3 + bX2 + cX + d Y = aX1 + bX2 + cX3 + d Kde: X1 = X3, X2 = X2, X1 = X
21/28
Testování vytvořených modelů • Bloková metoda – Data jsou náhodně rozdělena do dvou množin: • Data z 1. množiny jsou použita k trénovaní • Data z 2. množiny jsou použita k testování • Křížová metoda – Data jsou náhodně rozdělena do k množin S1, S2, …, Sk. • Data z S2, …, Sk jsou použita k trénovaní a testování je prováděno na datech z množiny S1 • Data z S1, S3 ,…, Sk jsou použita k trénovaní a testování je prováděno na datech z množiny S2
…
• Data z S1,…, Sk-1 jsou použita k trénovaní a testování je prováděno na datech z množiny Sk
22/28
Ukázka SAS-EM: Definice problému • Definice problému: Předmět IFJ měl v letošním roce celkem 383 studentů. Bodové rozdělení tohoto předmětu je následující: 1) Půlsemestrální zkouška 20b. 2) Projekt 25b. 3) Závěrečná zkouška 55b.
• Úkoly: 1) Pokusíme se předpovědět zda student udělal kvalitně projekt (dostal za něj minimálně 20 bodů) pouze za předpokladu znalostí jeho výsledků z 1) & 3) 2) Pokusíme se předpovědět zda student dostane z IFJ jedničku (celkový počet bodů ≥ 90) pouze za předpokladu znalostí jeho výsledků z 1) & 2)
23/28
Celkový náhled na implementaci Úkol 2
Úkol 1
24/28
Data a transformace dat
Dopočítané proměnné Proměnné získané z DB
25/28
Nastavení atributů Nastavení atributů pro úkol 1.
Nastavení atributů pro úkol 2.
26/28
Úkol 1: Výsledky
27/28
Úkol 2: Výsledky
28/28
Zhodnocení výsledků • Pro řešení obou úloh je nejhorší alternativa
použít rozhodovací strom (diskrétní charakter!) • Použití neuronové sítě i regresní funkce je srovnatelné
• Příčiny nepřesnosti predikce: 1) Student má dostatečný počet bodů během semestru a nenaučí se na závěrečnou zkoušku 2) Student má naopak málo bodů během semestru a o to více se na závěrečnou zkoušku připraví 3) Student zvládá učivo jen teoreticky (hodně bodů ze zkoušek), ale neovládá praxi (málo bodů z projektu) …
