Priručnik za pripremu prijemnog ispita iz veštačke inteligencije za master studije Softversko inženjerstvo i veštačka inteligencija PDF

PRIRUČNIK ZA PRIPREMU PRIJEMNOG ISPITA IZ VEŠTAČKE INTELIGENCIJE ZA MASTER STUDIJE SOFTVERSKO INŽENJERSTVO I VEŠTAČKA INTELIGENCIJA PROF. JELENA JOVANOVIĆ PROF. BOJAN TOMIĆ PROF. ZORAN ŠEVARAC  1. MAŠINSKO UČENJE PREGLED TEMA ▪ Šta je mašins...

PRIRUČNIK ZA PRIPREMU PRIJEMNOG ISPITA IZ VEŠTAČKE INTELIGENCIJE ZA MASTER STUDIJE SOFTVERSKO INŽENJERSTVO I VEŠTAČKA INTELIGENCIJA PROF. JELENA JOVANOVIĆ PROF. BOJAN TOMIĆ PROF. ZORAN ŠEVARAC  1. MAŠINSKO UČENJE PREGLED TEMA ▪ Šta je mašinsko učenje? ▪ Zašto (je potrebno/bitno) m. učenje? ▪ Oblasti primene m. učenja ▪ Oblici m. učenja ▪ Osnovni koraci i elementi procesa m. učenja ▪ Podaci ▪ Atributi (features) ▪ Odabir algoritma m. učenja ▪ Validacija i testiranje kreiranog modela ŠTA JE MAŠINSKO UČENJE ? Mašinsko učenje se odnosi na sposobnost softverskog sistema da: ▪ generalizuje na osnovu prethodnog iskustva, i ▪ da koristi kreirane generalizacije kako bi pružio odgovore na pitanja koja se odnose na entitete/pojave koje pre nije sretao Pod iskustvom se podrazmeva skup podataka o pojavama / entitetima koji su predmet učenja ŠTA JE MAŠINSKO UČENJE ? Za kompjuterski program se kaže da uči iz iskustva E (experience), vezanog za zadatak T (task), i meru performansi P (performance), ukoliko se njegove performanse na zadatku T, merene metrikama P, unapređuju sa iskustvom E Tom Mitchell (1997) ŠTA JE MAŠINSKO UČENJE ? Primer: program koji označava poruke kao spam i non-spam ▪ Zadatak (T): klasifikacija email poruka na spam i non-spam ▪ Iskustvo (E): email poruke označene kao spam i non-spam; podaci o oblicima interakcije korisnika sa spam i non-spam porukama ▪ Performanse (P): procenat email poruka korektno klasifikovanih kao spam, odnosno non-spam ZAŠTO MAŠINSKO UČENJE ? 1) Neke vrste zadataka ljudi rešavaju vrlo lako, a pri tome nisu u mogućnosti da precizno (algoritamski) opišu kako to rade Primeri: prepoznavanje slika, zvuka, govora 2) Za neke vrste zadataka mogu se definisati algoritmi za rešavanje, ali su ti algoritmi vrlo složeni i/ili zahtevaju velike baze znanja Primeri: automatsko prevođenje ZAŠTO MAŠINSKO UČENJE ? 3) U mnogim oblastima se kontinuirano prikupljaju podaci sa ciljem da se iz njih “nešto sazna”; npr.: ▪ u medicini: podaci o pacijentima i korišćenim terapijama ▪ u sportu: o odigranim utakmicama i igri pojedinih igrača ▪ u marketingu: o korisnicima/kupcima i tome šta su kupili, za šta su se interesovali, kako su proizvode ocenili,… Analiza podataka ovog tipa zahteva pristupe koji će omogućiti da se otkriju pravilnosti, zakonitosti u podacima koje nisu ni poznate, ni očigledne, a mogu biti korisne GDE SE PRIMENJUJE MAŠINSKO UČENJE ? Brojne oblasti primene ▪ Kategorizacija teksta prema temi, iskazanim osećanjima i/ili stavovima i sl. ▪ Mašinsko prevođenje teksta ▪ Razumevanje govornog jezika ▪ Prepoznavanje lica na slikama ▪ Segmentacija tržišta ▪ Uočavanje paterna u korišćenju različitih aplikacija ▪ Autonomna vozila (self-driving cars) ▪... OBLICI MAŠINSKOG UČENJA Osnovni oblici mašinskog učenja: ▪ Nadgledano učenje (supervised learning) ▪ Nenadgledano učenje (unsupervised learning) ▪ Učenje uz podsticaje (reinforced learning) NADGLEDANO UČENJE Obuhvata skup problema i tehnika za njihovo rešavanje u kojima program koji uči dobija: ▪ skup ulaznih podataka (x1, x2, …, xn) i ▪ skup željenih/tačnih vrednosti, tako da za svaki ulazni podatak xi, imamo željeni/tačan izlaz yi Zadatak programa je da “nauči” kako da novom, neobeleženom ulaznom podatku dodeli tačnu izlaznu vrednost Izlazna vrednost može biti: ▪ labela (tj. nominalna vrednost) – reč je o klasifikaciji ▪ realan broj – reč je o regresiji NADGLEDANO UČENJE Primer linearne regresije: predikcija cena nekretnina na osnovu njihove površine Podaci za učenje: površine (x) i cene (y) nekretnina u nekom gradu Cena (u 1000$) Površina (feet2) Izvor: https://www.coursera.org/course/ml NADGLEDANO UČENJE Primer linearne regresije (nastavak) Funkcija koju treba „naučiti“ u ovom slučaju (samo jedan atribut) je: h(x) = a + bx a i b su koeficijenti koje program u procesu „učenja“ treba da proceni na osnovu datih podataka Cena (u 1000$) Površina (feet2) NENADGLEDANO UČENJE Kod nenadgledanog učenja ▪ nemamo informacija o željenoj izlaznoj vrednosti ▪ program dobija samo skup ulaznih podataka (x1, x2, …, xn) Zadatak programa je da otkrije paterne tj. skrivene strukture/zakonitosti u podacima NENADGLEDANO UČENJE Primer: određivanje konfekcijskih veličina na osnovu visine i težine ljudi Izvor: https://www.coursera.org/course/ml UČENJE UZ PODSTICAJE Ovaj oblik učenja podrazumeva da program (agent) deluje na okruženje izvršavanjem niza akcija Ove akcije utiču na stanje okruženja, koje povratno utiče na agenta pružajući mu povratne informacije koje mogu biti “nagrade” ili “kazne” Cilj agenta je da nauči kako da deluje u datom okruženju tako da vremenom max. nagrade (ili min. kazne) Primer: autonomna vozila ILUSTRACIJA AGENTA KOJI UČI UZ PODSTICAJE Senzori Agent Stanje Opšte znanje o Interpretacija Okruženje promenama u okruženju Efekti akcija Pravila Odluka o akciji Aktuatori 1.1. OSNOVNI KORACI I ELEMENTI PROCESA MAŠINSKOG UČENJA  OSNOVNI KORACI PROCESA M. UČENJA 1) Prikupljanje podataka potrebnih za formiranje dataset-ova za obuku, (validaciju) i testiranje modela m. učenja 2) Priprema podataka, što tipično podrazumeva “čišćenje” i transformaciju podataka 3) Analiza rezultujućih dataset-ova, i njihovo, eventualno, dalje unapređenje kroz selekciju/transformaciju atributa 4) Izbor 1 ili više algoritama m. učenja 5) Obuka, konfiguracija i evaluacija kreiranih modela 6) Izbor modela koji će se koristiti (na osnovu rezultata koraka 5) i njegovo testiranje PODACI Podaci su potrebni za trening, validaciju i testiranje modela ▪ Tipična podela podataka kojima raspolažemo je 60% za trening, 20% za validaciju i 20% za testiranje ▪ Izbor uzoraka za trening, validaciju i testiranje treba da se uradi na slučajan način (random selection) Za nadgledano učenje, moramo imati “obeležene” podatke ▪ Npr. obeležiti slike koje sadrže lice, elektronsku poštu koja je nepoželjna, e-mail adrese koje su lažne, i sl. PODACI Izvori podataka: ▪ Javno dostupne kolekcije podataka ▪ Pogledati npr. https://www.kaggle.com/datasets ▪ Podaci dostupni posredstvom Web API-a ▪ Pogledati npr. https://developer.twitter.com/en/docs/twitter-api ▪ Sve veće tržište gde je moguće kupiti podatke ▪ Pogledati npr. https://about.datarade.ai/ PODACI Preporuka: predavanje Peter Norvig*-a na temu značaja podataka za mašinsko učenje: The Unreasonable Effectiveness of Data URL: http://www.youtube.com/watch?v=yvDCzhbjYWs *Peter Norvig je autor jedne od najpoznatijih knjiga u domenu Veštačke inteligencije i trenutno na poziciji Director of Research u Google-u ATRIBUTI (FEATURES) Osnovna ideja: ▪ pojave/entitete prepoznajemo uočavajući njihove osobine (ili izostanak nekih osobina) i uviđajući odnose između različitih osobina ▪ omogućiti programu da koristi osobine pojava/entiteta za potrebe njihove identifikacije/grupisanja Izazov: ▪ odabrati atribute koji najbolje opisuju neki entitet/pojavu, tj. omogućuju distinkciju entiteta/pojava različitog tipa ATRIBUTI (FEATURES) Primeri: ▪ Za eletronsku poštu: naslov (tj. polje subject), reči napisane velikim slovom, dužina email-a, prva reč i sl. ▪ Za stan: površina, lokacija, broj soba, tip grejanja i sl. ▪ Za tweet poruke: prisustvo linkova, prisustvo hashtag-ova, vreme slanja, pošiljalac, … ODABIR ALGORITMA Generalno, zavisi od: ▪ vrste problema koji rešavamo, ▪ karakteristika skupa atributa (features) ▪ tip atributa i stepen homogenosti tipova i opsega vrednosti atributa ▪ stepen međuzavisnosti (korelisanosti) atributa ▪ obima podataka koji su nam na raspolaganju ODABIR ALGORITMA Primer: pokušaj aproksimacije četiri različita skupa podataka primenom iste linearne funkcije (tj. linearne regresije) Izvor: http://goo.gl/yjm0El ODABIR ALGORITMA Primer (nastavak): Očigledno, linearna funkcija neće biti najbolje rešenje za sve skupove podataka; za mnoge će nam biti potrebna neka složenija funkcija (npr. polinomijalna funkcija). U zavisnosti od odabira kompleksnosti funkcije, imaćemo bolju ili lošiju aproksimaciju podataka. TESTIRANJE Pošto se algoritam obučavao na podacima za trening, njegova uspešnost na tim podacima nije indikator stvarne uspešnosti Za procenu uspešnosti modela, potrebni su podaci koje model nije imao prilike da “vidi” u fazi učenja Reč je o podacima za testiranje, za koje se obično izdvaja 20-30% ukupnih podataka Uspešnost modela se utvrđuje različitim metrikama: tačnost, preciznost, odziv, … TRAIN/VALIDATE/TEST Pored treniranja i testiranja modela, najčešće se radi i validacija modela kako bi se: a) izabrao najbolji algoritam između više kandidata b) odredila optimalna konfiguracija parametara modela c) izbegli problemi over/under-fitting-a U ovim slučajevima, ukupan dataset deli se u odnosu 60/20/20 na podatke za trening, validaciju i testiranje Podaci za validaciju koriste se za poređenje performansi ▪ različitih algoritama (tačka (a) iznad) ▪ izabranog algoritma sa različitim vrednostima parametara (tačka (b) iznad) UNAKRSNA VALIDACIJA (CROSS-VALIDATION) Čest pristup za efikasno korišćenje raspoloživih podataka Kako funkcioniše: ▪ raspoloživi skup podataka za trening se podeli na K delova ili podskupova (folds) ▪ najčešće se uzima 10 podskupova (10 fold cross validation) ▪ zatim se obavlja K iteracija treninga + validacije modela ; u svakoj iteraciji: ▪ uzima se 1 deo podataka za potrebe validacije, a ostatak (K-1 deo) se koristi za učenje ▪ bira se uvek različiti podskup koji će se koristiti za validaciju Sledeći slajd ilustruje postupak UNAKRSNA VALIDACIJA (CROSS-VALIDATION) Izvor: http://goo.gl/BLIKRv UNAKRSNA VALIDACIJA (CROSS-VALIDATION) Pri svakoj iteraciji računaju se performanse modela (npr. mera tačnosti modela) Na kraju se računa prosečna uspešnost na nivou svih K iteracija – tako izračunate mere uspešnosti daju bolju sliku o performansama modela Ukoliko su rezultati u svih K iteracija vrlo slični, smatra se da je procena uspešnosti modela pouzdana ANALIZA GREŠKE Podrazumeva “ručno” pregledanje primera na kojima je model pravio greške i uočavanje paterna u tim primerima Pomaže da se stekne osećaj zbog čega model greši, i šta bi se moglo uraditi da se greške otklone; Npr. ▪ identifikovati suvišne atribute ▪ identifikovati atribute koji nedostaju ▪ drugačije podesiti parametre modela ▪… PROBLEM PREVELIKOG PODUDARANJA SA PODACIMA (OVER-FITTING) Odnosi na situaciju u kojoj model savršeno nauči da prepoznaje instance iz trening seta, ali nije u mogućnosti da prepozna instance koje se i malo razlikuju od naučenih poželjno rešenje over fitting Izvor: https://www.coursera.org/course/ml PROBLEM NEDOVOLJNOG PODUDARANJA SA PODACIMA (UNDER-FITTING) Under-fitting se odnosi na slučaj kad model ne uspeva da aproksimira podatke za trening, tako da ima slabe performanse čak i na trening setu poželjno rešenje under fitting Izvor: https://www.coursera.org/course/ml OVER-FITTING VS. UNDER-FITTING UNDER - FITTING OVER - FITTING Izvor: http://www.astroml.org/sklearn_tutorial/practical.html  2. KLASIFIKACIJA PREGLED TEMA ▪ Šta je klasifikacija? ▪ Binarna i više-klasna klasifikacija ▪ Algoritmi klasifikacije ▪ Naive Bayes (NB) algoritam ▪ Ilustracija NB algoritma: klasifikacija teksta ▪ Mere uspešnosti klasifikatora ŠTA JE KLASIFIKACIJA? ▪ Zadatak određivanja klase kojoj neka instanca pripada ▪ instanca je opisana vrednošću atributa ▪ skup mogućih klasa je poznat i dat ▪ Klase su date kao nominalne vrednosti, npr. ▪ klasifikacija email poruka: spam, non-spam ▪ klasifikacija novinskih članaka: politika, sport, kultura i sl. BINARNA I VIŠE-KLASNA KLASIFIKACIJA Zavisno od broja klasa, razlikujemo: ▪ binarnu klasifikaciju - postoje dve klase ▪ više-klasnu klasifikaciju - postoji više klasa u koje se instance mogu svrstati Princip rada algoritma u oba slučaja je gotovo isti: u slučaju postojanja više klasa, algoritam iterativno uči, tako da u svakoj iteraciji “nauči” da jednu od klasa razgraniči od svih ostalih VIŠE-KLASNA KLASIFIKACIJA 1. ITERACIJA 2. ITERACIJA 3. ITERACIJA Izvor: https://www.coursera.org/course/ml ALGORITMI KLASIFIKACIJE Postoje brojni pristupi/algoritmi za klasifikaciju: ▪ Logistička regresija ▪ Naive Bayes ▪ Algoritmi iz grupe Stabala odlučivanja ▪ Algoritmi iz grupe Neuronskih mreža ▪ k-Nearest Neighbor (kNN) ▪ Support Vector Machines (SVM) ▪… 2.1. NAIVE BAYES ZAŠTO BAŠ NAIVE BAYES? Naive Bayes (NB) se navodi kao algoritam koji treba među prvima razmotriti pri rešavanju zadataka klasifikacije Razlozi: ▪ Jednostavan je ▪ Ima dobre performanse ▪ Vrlo je skalabilan ▪ Može se prilagoditi za gotovo bilo koji problem klasifikacije PODSEĆANJE: BAYES-OVO PRAVILO P (H|E) = P(E|H) * P(H) / P(E) ▪ H – hipoteza (hypothesis) ▪ E – opažaj (evidence) vezan za hipotezu H, tj. podaci na osnovu kojih bi trebalo da potvrdimo ili odbacimo hipotezu H ▪ P (H) – verovatnoća hipoteze H (prior probability) ▪ P (E) – verovatnoća opažaja tj. stanja na koje ukazuju prikupljeni podaci ▪ P (E | H) – (uslovna) verovatnoća opažaja E ukoliko važi hipoteza H ▪ P (H | E) – (uslovna) verovatnoća hipoteze H ukoliko imamo opažaj E BAYES-OVO PRAVILO - PRIMER Pretpostavite sledeće: ▪ jednog jutra ste se probudili sa povišenom temperaturom ▪ prethodnog dana ste čuli da je u gradu počela da se širi virusna infekcija, ali da je verovatnoća zaraze mala, svega 2.5% ▪ takođe ste čuli da je u 50% slučajeva virusna infekcija praćena povišenom temperaturom ▪ u vašem slučaju, povišena temperatura se javlja svega par puta u godini, tako da je verovatnoća da imate povišenu temp. 6.5% Pitanje: kolika je verovatnoća da, pošto imate povišenu temp., da imate i virusnu infekciju? BAYES-OVO PRAVILO - PRIMER Teorija Primer Hipoteza (H) Imate virusnu infekciju P(H) 0.025 Opažaj (evidence - E) Imate povišenu temperaturu P(E) 0.065 (uslovna) verovatnoća Verovatnoća da je virusna infekcija praćena opažaja E ukoliko važi povišenom temperaturom hipoteza H: P(E|H) 0.50 (uslovna) verovatnoća Verovatnoća da pošto imate povišenu temp., hipoteze H ukoliko imamo da imate i virusnu infekciju opažaj E: P(H|E) ? P(H|E) = P(E|H) * P(H) / P(E) P(H|E) = 0.50 * 0.025 / 0.065 = 0.19 NAIVE BAYES U KLASIFIKACIJI TEKSTA NB je jedan od najčešće korišćenih algoritama za klasifikaciju teksta Zadatak klasifikacije teksta: odrediti kojoj klasi (c) iz datog skupa klasa (C), dati tekst pripada Na primer: ▪ tematska klasifikacija novinskih članaka ▪ klasifikacija tweet poruka prema iskazanom stavu (poz./neg.) FORMIRANJE VEKTORA ATRIBUTA Tekst koji je predmet klasifikacije se tretira kao prost skup reči (tzv. bag-of-words) ▪ Reči iz teksta su osnova za kreiranje atributa (features) sa kojima će NB algoritam raditi ▪ Postoji više načina da se reči iz teksta upotrebe za definisanje vektora atributa (feature vector) za klasifikaciju FORMIRANJE VEKTORA ATRIBUTA Pristup koji se često primenjuje: ▪ Estrahovati reči iz dokumenata koji čine skup za trening D, i formirati rečnik R koji sadrži jedinstvena pojavljivanja reči iz skupa D ▪ Rečnik R se može kreirati na osnovu svih reči iz skupa D ili samo na osnovu onih reči koje mogu biti značajne za dati zadatak klasifikacije ▪ Zatim se svaki document d iz skupa D predstavlja kao vektor učestanosti pojavljivanja reči iz rečnika R ▪ Drugim rečima, reči iz rečnika su atributi koji se koriste u klasifikaciji, a njihove vrednosti su učestanosti pojavljivanja u pojedinačnim dokumentima FORMIRANJE VEKTORA ATRIBUTA - PRIMER Klasifikacija komentara (reviews) filmova; dokumenti su ovde pojedinačni komentari (reviews); svaki komentar je označen kao pozitivan ili negativan Izvor: http://www.stanford.edu/class/cs124/lec/naivebayes.pdf FORMIRANJE VEKTORA ATRIBUTA - PRIMER Ilustracija predstavljanja dokumenta (review) preko formiranog rečnika, odnosno skupa atributa (xi), i vrednosti atributa za dati dokument (review) atribut (xi) vrednost (TFi) x1 = love TF1 = 1 x2 = sweet TF2 = 1 x3 = satirical TF3 = 1 … x11 = happy TF11 = 2 x12 = laugh TF12 = 2 … TF= Term Frequency NB U KLASIFIKACIJI TEKSTA Ako je c klasa, a d dokument, verovatnoća da je upravo c klasa dokumenta d biće: P (c|d) = P(d|c) * P(c) / P(d) (1) Za dati skup klasa C i dokument d, želimo da pronađemo onu klasu c iz skupa C koja ima najveću uslovnu verovatnoću za dokument d, što daje sledeću funkciju: f = argmaxc iz C P(c|d) (2) Primenom Bayes-ovog pravila, dobijamo: f = argmaxc iz C P(d|c) * P(c) (3) NB U KLASIFIKACIJI TEKSTA f = argmaxc iz C P(d|c) * P(c) (3) Potrebno je odrediti verovatnoće P(c) i P(d|c) P(c) se može proceniti relativno jednostavno: brojanjem pojavljivanja klase c u skupu dokumenata za trening D P(d|c) - verovatnoća da u klasi c zateknemo dokument d – nije tako jednostavno odrediti i tu uvodimo pretpostavke koje NB algoritam čine “naivnim” NB U KLASIFIKACIJI TEKSTA Kako odrediti P(d|c)? ▪ dokument d predstavljamo kao skup atributa (x1, x2,...,xn) ▪ umesto P(d|c) imaćemo P(x1, x2, x3,...xn|c) ▪ da bi izračunali P(x1, x2, x3,...xn|c) uvodimo 2 naivne pretpostavke: ▪ dokument d posmatramo kao prost skup reči (bag-of-words); tj. pozicija i redosled reči u tekstu se smatraju nevažnim ▪ pojavljivanje određene reči u datoj klasi c je nezavisno od pojavljivanja neke druge reči u toj klasi NB U KLASIFIKACIJI TEKSTA Uvedene pretpostavke ▪ dovode do značajnog gubitka informacija koje iz podataka možemo da izvučemo, ali, ▪ omogućuju značajno jednostavnije računanje P(x1, x2,...,xn|c), a time i ceo problem klasifikacije NB U KLASIFIKACIJI TEKSTA Na osnovu uvedenih pretpostavki, P(x1, x2,...,xn |c) možemo da predstavimo kao proizvod individualnih uslovnih verovatnoća P(x1, x2,...,xn |c) = P(x1|c) * P(x2|c) * … * P(xn|c) Time dolazimo do opšte jednačine NB algoritma: f = argmaxc iz C P(c) * Пi=1,nP(xi|c) NB U KLASIFIKACIJI TEKSTA Procena verovatnoća se vrši na osnovu skupa za trening, i zasniva na sledećim jednačinama: P(c) = br. dok. klase c / ukupan br. dok. u skupu za trening P(xi|c) = br. pojavljivanja reči ri u dok. klase c (TF) / ukupan br. reči iz rečnika R u dok. klase c OSOBINE NB ALGORITMA ▪ Veoma brz i efikasan ▪ Najčešće daje dobre rezultate ▪ često se pokazuje kao bolji ili bar podjednako dobar kao drugi, sofisticiraniji modeli ▪ Nije memorijski zahtevan ▪ Ima vrlo mali afinitet ka preteranom podudaranju sa podacima za trening (overfitting) ▪ Pogodan kada imamo malu količinu podataka za trening OSOBINE NB ALGORITMA ▪ “Otporan” na nevažne atribute ▪ atributi koji su podjednako distribuirani kroz skup podataka za trening, pa nemaju veći uticaj na izbor klase ▪ Namenjen primarno za rad sa nominalnim atributima; u slučaju numeričkih atributa: ▪ koristiti raspodelu verovatnoća atributa (tipično Normalna raspodela) za procenu verovatnoće svake od vrednosti atributa ▪ uraditi diskretizaciju vrednosti atributa 2.2. STABLA ODLUČIVANJA  PRIMER: KLASIFIKACIJA IGRAČA BEJZBOLA Potrebno je klasifikovati igrače bejzbola na one koji su jako dobro plaćeni i one koji to nisu (WellPaid), na osnovu broja ostvarenih poena u prethodnoj godini (Hits) i broja godina koje je igrač proveo u glavnoj ligi (Years) 62 PRIMER: KLASIFIKACIJA IGRAČA BEJZBOLA Stablo odlučivanja ukazuje da su dobro plaćeni oni igrači koji su ostvarili bar 122 pogotka u prethodnoj godini i koji bar 5.5 godina igraju u glavnoj ligi Verovatnoća da je igrač sa opisanim karakteristikama dobro plaćen je 0.75 Ti igrači čine 24% svih igrača za koje su nam raspoloživi podaci (skup za trening) 63 DRUGI NAČIN ZA VIZUELIZACIJU STABLA ODLUČIVANJA… R1 R3 R2 64 OSNOVNA IDEJA KLASIFIKACIONIH STABALA Podeliti prostora atributa kojima su objekti opisani u više različitih i međusobno nepreklopljenih regiona R1, R2, …, Rn prostor atributa je p-dimenzionalni prostor koga čine moguće vrednosti p atributa (x1,x2,…,xp) kojima su dati objekti opisani Za novi objekat X, određuje se pripadnost jednom od regiona R1…Rn na osnovu vrednosti atributa (x1,x2,…,xp) kojima je X opisan Klasa novog objekta će biti ona klasa koja dominira (majority class) u regionu Rj u koji je X svrstan 65 PODELA PROSTORA ATRIBUTA Podela prostora atributa na regione Rj je iterativni proces koji se sastoji od: ▪ izbora atributa xi koji će biti osnova za podelu ▪ izbora vrednosti atributa xi koja će poslužiti kao ‘granična’ vrednost 66 PODELA PROSTORA ATRIBUTA Za prvu podelu, u Hits = 122 datom primeru, izabran je atribut Hits, i vrednost 122 67 PODELA PROSTORA ATRIBUTA Prva podela: Hits = 122 Ukoliko je Hits > 122, sledeća podela je na atributu Years: Years= 5.5 68 PODELA PROSTORA ATRIBUTA 122 Prva podela: Hits = 122 Ako je Hits > 122, R3 sledeća podela: Years = 5.5 R1 5.5 R2 69 PODELA PROSTORA ATRIBUTA Pitanja koja se prirodno nameću: ▪ Kako i gde izvršiti podelu? ▪ drugim rečima, kako kreiramo regione R1, R2,…,Rn? ▪ Kako odrediti klasu instanci u svakom od regiona R1,..,Rn? 70 KAKO ODREDITI KLASU INSTANCI U REGIONIMA R …RK ? 1 Jednostavno, koristeći princip većinske klase (majority class): svakom regionu Rj, pridružiti klasu kojoj pripada većina instanci iz skupa za trening koja je svrstana u region Rj U datom primeru, u regionu R1, 90% instanci čine igrači koji nisu visoko plaćeni => svaki novi igrač koji bude svrstan u region R1 biće klasifikovan kao igrač koji nije vrhunski plaćen 71 KAKO I GDE IZVRŠITI PODELU? 72 KAKO I GDE IZVRŠITI PODELU? Pristup koji se primenjuje da bi se identifikovali regioni koji minimizuju grešku pri klasifikaciji zasniva se na rekurzivnoj, binarnoj podeli (recursive binary splitting) prostora atributa Osnovne karakteristike ovog pristupa: top-down pristup greedy pristup 73 REKURZIVNA, BINARNA PODELA PROSTORA ATRIBUTA Top-down pristup kreće od vrha stabla, gde sve (trening) instance pripadaju jednoj (zajedničkoj) regiji, a zatim sukcesivno deli prostor atributa na regione Greedy pristup pri svakom koraku, najbolja podela se određuje na osnovu stanja u tom koraku, odnosno, ne uzima se u obzir šta će biti u narednim koracima, tj koja bi to podela mogla dovesti do boljih rezultata u nekom narednom koraku 74 REKURZIVNA, BINARNA PODELA Algoritam razmatra svaki atribut xj (j=1,p) i svaku tačku podele sj za taj atribut, i bira onu kombinaciju koja će podeliti prostor atributa u dva regiona {X|xj > sj} i {X|xj < sj} tako da se minimizuje greška klasifikacije 75 KAKO I GDE IZVRŠITI PODELU? Osim greške pri klasifikaciji (Classification Error Rate), kao kriterijumi za podelu prostora atributa, često se koriste i: Gini index Cross-entropy 76 GINI INDEX Osim greške pri klasifikaciji (Classification Error Rate), kao kriterijumi za podelu prostora atributa, često se koriste i: Gini index Cross-entropy 77 CROSS-ENTROPY Definiše se na sledeći način: Kao i Gini indeks, cross-entropy predstavlja meru ‘čistoće’ čvora (što je vrednost manja, to je čvor ‘čistiji’) 78 OREZIVANJE STABLA (TREE PRUNING) Velika klasifikaciona stabla, tj. stabla sa velikim brojem terminalnih čvorova (listova), imaju tendenciju over-fitting-a (tj. prevelikog uklapanja sa trening podacima) Ovaj problem se može rešiti ‘orezivanjem’ stabla, odnosno odsecanjem nekih terminalnih čvorova 79 OREZIVANJE STABLA (TREE PRUNING) Kako ćemo znati na koji način i u kojoj meri treba da ‘orežemo’ stablo? Preporuka je primenom kros validacije (cross validation) utvrditi grešku pri klasifikaciji za podstabla različite veličine (tj broja terminalnih čvorova) i izabrati podstablo koje daje najmanju grešku 80 OREZIVANJE STABLA KROZ KROS VALIDACIJU U primeru klasifikacije igrača bejzbola, kros validacija pokazuje da se najmanja greška klasifikacije postiže u slučaju stabla veličine 3 (tj. stabla sa 3 terminalna čvora) 81 OREZIVANJE STABLA KROZ KROS VALIDACIJU Grafikon potvrđuje da veličina stabla utvrđena kros validacijom (n=3), vodi minimalnoj grešci na test setu 82 PREDNOSTI I NEDOSTACI STABALA ODLUČIVANJA Prednosti: Mogu se grafički predstaviti i jednostavno interpretirati Mogu se primeniti kako na klasifikacione, tako i regresione probleme Mogu se primeniti i u slučaju da atributi imaju nedostajuće vrednosti Nedostaci: Daju slabije rezultate (manje tačne predikcije) nego drugi pristupi nadgledanog m. učenja 83 MERE USPEŠNOSTI KLASIFIKATORA Neke od najčešće korišćenih metrika: ▪ Matrica zabune (Confusion Matrix) ▪ Tačnost (Accuracy) ▪ Preciznost (Precision) i Odziv (Recall) ▪ F mera (F measure) ▪ Površina ispod ROC krive (Area Under the Curve - AUC) MATRICA ZABUNE (CONFUSION MATRIX) Služi kao osnova za računanje mera performansi (uspešnosti) algoritama klasifikacije U slučaju binarne klasifikacije izgleda ovako: TP = True Positive FP = False Positive TN = True Negative FN = False Negative MATRICA ZABUNE - PRIMER Primer: klasifikacija studenata da li će položiti ispit (Yes) ili ne (No) Značenje termina u matrici: TP: broj studenata za koje je predvidjeno da će položiti ispit i koji su stvarno položili TN: broj studenata za koje je predvidjeno da neće položiti ispit i koji ga stvarno nisu položili FP: broj studenata za koje je predvidjeno da će položiti ispit, a nisu ga položili (pogrešno su klasifikovani kao da će položiti) FN: broj studenata za koje je predvidjeno da neće položiti ispit, a položili su ga (pogrešno su klasifikovani kao da neće položiti) TAČNOST (ACCURACY) Tačnost (Accuracy) predstavlja procenat slučajeva (instanci) koji su uspešno (korektno) klasifikovani Accuracy = (TP + TN) / N gde je: ▪ TP – True Positive; TN – True Negative ▪ N – ukupan broj uzoraka (instanci) u skupu podataka TAČNOST (ACCURACY) U slučaju vrlo neravnomerne raspodele instanci između klasa (tzv. skewed classes), ova mera je nepouzdana Npr. u slučaju klasifikacije poruka na spam vs. non-spam, možemo imati skup za trening sa 0.5% spam poruka Ako primenimo “klasifikator” koji svaku poruku svrstava u non-spam klasu, dobijamo tačnost od 99.5% Očigledno je da ova metrika nije pouzdana i da su u slučaju skewed classes potrebne druge metrike PRECIZNOST (PRECISION) I ODZIV (RECALL) Precision = TP / no. predicted positive = TP / (TP + FP) Npr. od svih poruka koje su označene kao spam poruke, koji procenat čine poruke koje su stvarno spam Recall = TP / no. actual positive = TP/ (TP + FN) Npr. od svih poruka koje su stvarno spam poruke, koji procenat poruka je detektovan/klasifikovan kao spam PRECIZNOST I ODZIV U praksi je nužno praviti kompromis između ove dve mere: ako želimo da povećamo Odziv, smanjićemo Preciznost, i obrnuto. Izvor: http://groups.csail.mit.edu/cb/struct2net/webserver/images/prec-v-recall-v2.png F MERA (F MEASURE) F mera kombinuje Preciznost i Odziv i omogućuje jednostavnije poređenje dva ili više algoritama F = (1 + β2) * Precision * Recall / (β2 * Precision + Recall) Parametar β kontroliše koliko više značaja će se pridavati Odzivu u odnosu na Preciznost U praksi se najčešće koristi tzv. F1 mera („balansirana“ F mera) koja daje podjednak značaj i Preciznosti i Odzivu: F1 = 2 * Precision * Recall / (Precision + Recall) POVRŠINA ISPOD ROC KRIVE Površina ispod ROC* krive – Area Under the Curve (AUC): ▪ meri diskriminacionu moć klasfikatora tj. sposobnost da razlikuje instance koje pripadaju različitim klasama ▪ primenjuje se za merenje performansi binarnih klasifikatora ▪ vrednost za AUC se kreće u intervalu 0-1 ▪ za metodu slučajnog izbora važi da je AUC = 0.5; što je AUC vrednost klasifikatora > 0.5, to je klasifikator bolji ▪ 0.7–0.8 se smatra prihvatljivim; 0.8–0.9 jako dobrim; sve > 0.9 je odlično *ROC = Receiver Operating Characteristic; http://en.wikipedia.org/wiki/Receiver_operating_characteristic  POVRŠINA ISPOD ROC KRIVE TPR = TP/(TP + FN) Izvor: http://goo.gl/Aeauuh FPR = FP/(FP + TN)  3. KLASTERIZACIJA PREGLED TEMA ▪ Šta je klasterizacija? ▪ Koje su oblasti/primeri primene? ▪ Klasterizacija primenom K-Means algoritma ▪ Upoznavanje sa algoritmom kroz primer ▪ K-Means algoritam ▪ Potencijalni problemi pri primeni algoritma ŠTA JE KLASTERIZACIJA? Klasterizacija je jedan od oblika nenadgledanog m. učenja ▪ ono što je raspoloživo od podataka su podaci o instancama koje je potrebno na neki način grupisati; ▪ ne posedujemo podatke o poželjnoj / ispravnoj grupi za ulazne instance ŠTA JE KLASTERIZACIJA? Klasterizacija je zadatak grupisanja instanci, tako da za svaku instancu važi da je sličnija instancama iz svoje grupe (klastera), nego instancama iz drugih grupa (klastera) Sličnost instanci se određuje primenom neke od mera za računanje ▪ sličnosti (npr. Kosinusna sličnost) ili ▪ udaljenosti dva objekta (npr. Euklidska udaljenost) ŠTA JE KLASTERIZACIJA? Za razliku od klasifikacije, ovde nemamo “tačno” rešenje ▪ ocena uspešnosti algoritma je dosta teža nego kod klasifikacije ▪ pogodnost rešenja zavisi od domena i slučaja primene – jedno isto rešenje može biti različito ocenjeno u različitim slučajevima primene ▪ zahteva angažovanje domenskih eksperata koji će evaluirati rešenje Primer različitih dobrih rešenja za isti polazni skup podataka OBLASTI PRIMENE ▪ Segmentacija tržišta ▪ Uočavanje grupa u društvenim mrežama ▪ Identifikacija paterna u ponašanju korisnika nekog Web sajta ▪ Grupisanje objekata (npr., slika/dokumenata) prema zajedničkim karakteristikama ▪ … 3.1. K-MEANS ALGORITAM K-MEANS Jedan od najpoznatijih i najjednostavnijih algoritama klasterizacije Najlakše ga je razumeti na primeru, pa ćemo prvo razmotriti jedan primer Primer je preuzet iz kursa: https://www.coursera.org/course/ml K-MEANS ALGORITAM – PRIMER Pretpostavimo da su ovo ulazni podaci kojima raspolažemo, opisani vrednostima dva atributa K-MEANS: PRIMER Inicijalizacija: Inicijalni izbor težišta klastera (K = 2) metodom slučajnog izbora K-MEANS: PRIMER Iteracija 1, korak 1: razvrstavanje instanci po klasterima na osnovu udaljenosti od težišta klastera K-MEANS: PRIMER Iteracija 1, korak 2: određivanje novog težišta za svaki klaster, na osnovu proseka vrednosti instanci u datom klasteru K-MEANS: PRIMER Iteracija 2, korak 1: (ponovno) razvrstavanje instanci po klasterima na osnovu udaljenosti od težišta klastera K-MEANS: PRIMER Iteracija 2, korak 2: Ponovno određivanje novog težišta za svaki klaster K-MEANS: PRIMER Iteracija 3, korak 1: (ponovno) razvrstavanje instanci po klasterima na osnovu udaljenosti od težišta klastera K-MEANS: PRIMER Iteracija 3, korak 2: Ponovno određivanje novog težišta za svaki klaster K-MEANS: PRIMER Algoritam već konvergira: dalje iteracije neće dovesti do značajnijih promena i proces se zaustavlja K-MEANS: ALGORITAM Ulaz: ▪ K - broj klastera ▪ (neobeležen) skup za trening sa m instanci; svaka instanca u skupu je vektor opisan sa n atributa (x1, x2, …, xn) ▪ max - max broj iteracija (opcioni parametar) K-MEANS: ALGORITAM Koraci: 1) Inicijalni izbor težišta klastera, slučajnim izborom ▪ težišta se biraju iz skupa instanci za trening, tj. K instanci za trening se nasumično izabere i proglasi za težišta 2) Ponoviti dok algoritam ne konvergira ili broj iteracija