Klasifikacija Flashcards
Sta je zadatak klasifikacije?
odredjivanje funkcije koja preslikava svaki skup atributa X u jednu predefinisanu vrednost y
Kako se proverava karakteristika modela ?
Ulazni podaci se dele na 2 disjunktna dela,trening i test skup.Pri proveri se uporedjuju predvidjene vrednosti sa stvarnim vrednostima
Hantov algoritam
Opsta procedura za formiranje drveta,opisuje nacin podele materijala u cvorovu
Ako je Dt skup slogova za trening koji se nalazi u cvoru t i neka su y={y1,y2..yc} oznake klasa
opsti postupak je :
1.Ako Dt sadrzi samo slogove koji pripadaju istoj klasi yt tada je cvor list oznacen po nazivu klase yt.
2.Ako Dt sadrzi slogove koji se nalaze u vise od jedne klase,tada se na osnovu test atributa vrsi podela materijala u manje podskupove na koje se rekurzivno primenjuje kompletna procedura
Odredjivanje najbolje podele
Najbolja podela se odredjuje pomocu mere necistoce ,mera homogenosti distribucije klasa u cvoru.
Gini,Entropija (nauciti formule)
Greska klasifikacije (formula)
Ginijev indeks = minimum (0.0) kada svi slogovi pripadaju jednoj klasi sadrzi najinteresantnije informacije
Kriterijum podele po cvorovima
Posmatra se razlika mere necistoce u roditelj cvoru i deci cvorovima.Sto je razlika veca to je podela kvalitetnija.(Formule za dobitak za gini i eentropiju)
Uslovi testiranja atributa za podelu
u zavisnosti od tipa atributa:
Бинарни Именски Редни Непрекидни
u zavisnosti od broja nacina za podelu:
Binarni: uvek se dele na 2 grane
Imenski: podela na vise grana ,podela na 2 grane(trazi se optimalna podela)
jako je bitno ocuvati raspored !!
diskretizacija: od neprekidnih atributa formiraju se redni kategoricki atributi
binarna podela : A <v>= v</v>
Alternativni kriterijum podele
Gini i entropija favorizuju atribute sa velikim brojem razlicitih vrednosti ,u nekim slucajevima se dobijaju pogresni rezultati
Strategije prevazilazenja problema:
-upotreba iskljucivo binarne podele
-ukljucivanje broja mogucih vrednosti
Kriterijum zaustavljanja
Formiranje novih cvorova deobom sloga tekuceg cvora se zaustavlja kada:
1.svi slogovi u tekucem cvoru pripadaju istoj klasi
2.svi slogovi imaju iste vrednosti (svih ) atributa
3.ispunjen kriterijum ranijeg zaustavljanja
Karakteristike drveta odlucivanja
-jeftina za konstruisanje
-jako brza u klasifikaciji nepoznatog materijala
-laka za interpretaciju za drveta male velicine
-preciznost je uporediva sa ostalim tehnikama klasifikacije za jedinstvene tipove podataka
-izbor mere necistoce nema veliki uticaj na preformanse
-primenljivost
-efikasnost izracunavanja
-rad sa nedostajucim vrednostima
-rad sa irelevantnim atributima i redudantnim atributima
-salba mogucnost rada sa povezanim atributima
-kriterijum podele samo jedan atribut —-> interval je pravouganog oblika
-kriterijum podele kombinacija vise atributa —–>moguce je obraditi i kose podatke
-izbor nacina potkresivanja znacajno utice na rezultate
-problem preprilagodjavanja i podprilagodjavanja
Preprilagodjavanje i potprilagodjavanje
Model koji je isuvise dobro klasifikuje podatke za trening moze da ima losije karakteristike pri generalizaciji od modela koji ima vecu gresku u procesu pravljenja modela(overfitting)
ako je model isuvise jednostavan greske pri treniranju i uopstavanju mogu da budu jako visoke -premalo prilagodjen model (underfitting)
preprilagodjavanje se javlja kod drveta koja su slozenija nego sto je potrebno ,u tom slucaju greska pri treniranju ne daje korektnu procenu ponasanja drveta u slucaju primene na prethodno nepoznate podatke
Procena greske u generalizaciji
Metode za procenu greske
- optimisticki pristup e(t) = e(t)
-pesimisticki pristup e(t) =e(t) + 0.5(list)
od 2 modela sa slicnom greskom generalizacije izabrati onaj koji je jednostavniji Okamov princip
Princip najmanje duzine (MDL)
Nacin na koji se ukljuci slozenost modela,dat je skup slogova sa poznatim X
Osoba A poznaje sve vrednosti klasa atributa y
Osoba B nema tu informaciju i moze da posalje zahtev A da prosledi sve oznake klasa-O(n) bitova gde je n broj slogova
Alternativno A moze da napravi model,kodira i posalje B
Ako je modle 100% tacan cena prenosa je jednaka ceni kodiranja modela,Ako nije potrebne su i informacije o nekorektno klasifikovanim slogovima.
MDL trazi model minimalne cene
pravilo ranijeg zaustavljanja
Algoritam se zaustavlja pre nego sto drvo naraste do maksimalne velicine
tipicni uslovi zaustavljanja:
-sve instance pripadaju istoj klasi
- vrednosti svih atributa su iste
-broj instanci je manji od neke unapred zadate granice
-distribucija instanci je nezavisna od raspolozivih atributa
-sirenje tekucih cvorova ne poboljsava meru cistoce
Potkreesivanje po zavrsetku
Drvo odlucivanja raste do krajnjih granica,iseku se cvorovi u drvetu od dna ka vrhu
ako se greska generalizacije poboljsa posle otsecanja poddrvo se zameni sa cvorom koji je list
-Oznake klasa lista se odredjuje prema vecini klasa instanci poddrveta
-za potkresivanje se moze koristiti i MDL
mere preformansi izracunavanja
matrica konfuzije,tacnost,preciznost,odziv,F mera,tezinska preciznost,F(beta) (formule)
