DMS Pregled područja - Evaluacija stvorenih modela

Evaluacija modela (otkrivenog znanja)

Tehnike višestrukog particioniranja za odredjivanje greške klasifikacijskog modela (t&t -train and test)

U prethodnom je dijelu objašnjeno zbog čega pogreška klasifikacijskog modela na skupu primjera za učenje može biti vrlo različita os stvarne greške.Ova netočnost proizlazi iz prekomjerne specijalizacije modela na skupu primjera za učenje. Najjednostavnija tehnika 'poštenog' procjenjivanja greške klasifikacijskog modela jest upotreba testnog skupa primjera. No, ova tehnika takodjer može dati loše rezultate na skupovima s manjim brojem podataka. Na manjim skupovima podataka višestruke t&t tehnike daju znatno bolje rezultate.

Višestruke t&t metode - "Random subsampling"

Kod višestrukih t&t metoda novi klasifikacijski model uči se praktično na osnovu svakog primjera iz skupa dostupnih podataka. Tako procijenjena greška klasifikacijskog modela jest prosječna vrijednost modela 'stvaranih' na osnovu particija osnovnog skupa podataka slučajnim odabirom primjera. Ove metode daju bolju procjenu stvarne greške modela od jednostruke podjele skupa podataka na skup za učenje modela i na skup za testiranje (t&t). U tablici 5 prikazan je način particioniranja skupa podataka za jednostruku t&t metodu i za metode višestrukog t&t particioniranja skupa podataka. Metodom višestrukih t&t particija rješava se problem oslanjanja na jednu, moguće nekarakterističnu particiju skupa primjera za učenje odnosno testiranje modela. Višestruki t&t eksperimenti omogućuju bolju procjenu usrednjavanjem rezultata preko više različitih, slučajno generiranih t&t particija. U Tablici n označava ukupan broj primjera j predstavlja veličinu particije koja se koristi za učenje modela (koja može varirati od 1 do n), a B označava ukupan broj particija.

	t&t metoda	"Random Subsampling" - višestruke t&t metode
Broj primjera za učenje	j	j
Broj primjera za testiranje	n - j	n - j
Broj iteracija	1	B<<n

Tablica 5: Usporedba jednostruke i višestruke t&t metode "random subsampling"

Prije nego prodiskutiramo koje veličine particija su potrebne, prikazat ćemo neke od mogućih načina particioniranja skupa podataka.

Unakrsna validacija/provjera - "Cross validation"

Specijalan slučaj višestrukog t&t pristupa jest unakrsna validacija "leaving-one-out" (LOO u daljnjem tekstu). LOO je jednostavna i elegentna tehnika za ocjenu točnosti klasifikacijskog modela, no istovremeno računalno relativno skupa. Zbog toga često se primjenjuje jedino na problemima s relativno malim skupom primjera.
Za danu metodu modeliranja i skup podataka s ukupno n primjera, klasifikacijski model se generira korištenjem (n-1) primjera i testira na jedinom preostalom primjeru iz skupa podataka. Ovaj se postupak ponavlja n puta, svaki put generiranjem modela izostavljanjem drugog primjera iz skupa primjera za učenje. Dakle, svaki pojedini primjer koristi se kao testni primjer, a u svakoj iteraciji gotovo svi primjeri se koriste za odredjivanje klasifikacijskog modela. Konačna procjena greške jest ukupan broj grešaka u svim iteracijama podijeljen sa ukupnim brojem primjera. LOO je evidentno superioran pristup ocjenjivanju stvarne greške klasifikacijskih modela. LOO procjena greške rijetko kada sistematski odstupa od stvarne greške ("bias"). To znači da se preko mnogo različitih skupova primjera veličine n-1, procjena usrednjiti prema stvarnoj greški klasifikacijskog modela. Iako je LOO preferirana tehnika, za skupove s većim brojem podataka često je i preskupa. No, kako raste broj primjera u skupu podataka, tako i točnost drugih t&t tehnika raste. LOO je specijalan slučaj čitave klase metoda unakrsne validacije. U tzv. k-unakrsnoj validaciji primjeri iz skupa podataka, slučajno su razdijeljeni u k medjusobno različitih particija, približno iste veličine. Tipično je da se u jednoj iteraciji k-1 particija koristi za učenje modela, koji se potom testira na preostaloj testnoj particiji. Postupak se ponavlja k puta, tako da je svaka od particija po jednom u ulozi testne particije. Prosječna greška preko svih k particija naziva se greškom unakrsne validacije/provjere ("cross-validated error rate"). Ova procedura testirana je na različitom broju particija, a 10-terostruka unakrsna validacija pokazala se kao adekvatna i dovoljno točna, naročito za skupove podataka s velikim brojem primjera, kada je LOO pristup računalno 'preskup'. Empirički rezultati takodjer 'podupiru' stratifikaciju primjera u skupovima za učenje i testiranje, radi aproksimacije prevalencije svake od klasa primjera u čitavom skupu primjera.

Tablica 6 usporedjuje tehnike procjene greške za skup od n primjera. Procjenjena greška jest prosjek grešaka preko svih iteracija. Iako su tehnike unakrsne validacije poznate još od 60-tih godina, tek su u novije doba postale praktično upotrebljive i za realne probleme s velikim brojem primjera i za kompleksne tehnike modeliranja, prvenstveno zahvaljujući eksponencijalnom porastu moći modernih računala.

	("Leaving-one-out")	10-struka unakrsna validacija CV
Broj primjera za učenje	n - 1	90%
Broj primjera za testiranje	1	10%
Broj iteracija	n	10

Tablica 6: Usporedba 10-struke unakrsne validacije ui LOO estimators

Velika prednost tehnika unakrsne validacije je da su svi primjeri u skupu podataka iskorišteni za testiranje, a gotovo isto tako i za učenje modela.

("Bootstrapping")

Problem odredjivanja najbolje procjene greške modela za mali broj primjera je posebno zahtjevan. Nije uopće neuobičajeno da broj primjera u realnim problemima bude mali. Na primjer, medicinske studije vrlo često se preliminarno rade na svega nekoliko pacijenata. Stoga je posebna pažnja u analizi podataka dana skupovima podataka s malim brojem primjera.

Tradicionalno, pod statistički malim skupom podataka misli se na 30-tak ili manje primjera. Uglavnom je za takve probleme preporučana LOO tehnika.

Za mali broj primjera, "bootstrapping", metoda novijeg datuma, pokazala se kao relativno pouzdana procjena stvarne greške modela. Iako je LOO procjena praktički 'imuna' na sistematske greške, postoje poteškoće u primjeni ove tehnike. To se prije svega odnosi na veliku varijancu procjene greške na malom broju primjera, koja dominira u ukupnoj nepreciznosti LOO metode. Taj se efekt smanjuje kod "bootstraping" metoda. Postoji veći broj "bootstraping" metoda, no najčešće se primjenjuju e0 i 0.632 "bootstrap".

Kod e0 procjene, skup primjera za učenje sastoji se od n primjera, koji su slučajno odabrani iz skupa od ukupno n primjera, uz dozvoljeno repliciranje primjera u skupu za učenje. Slučajni odabir s repliciranjem znači da se dozvoljava da primjeri u skupu za učenje imaju i višestruke kopije. Na skupu od 100 primjera, procedura stvaranja skupa za učenje i skupa za testiranje izgleda ovako: u jednoj iteraciji slu vcajno odabiremo jedan primjer iz skupa podataka i stavljamo ga u skup primjera za učenje, 'ostavljajući' original u skupu. Ovaj postupak odabira ponavlja se dok broj primjera u novom skupu za učenje nije jednak onom u inicijalnom skupu podataka (100). Primjeri koji nisu zastupljeni u skupu za učenje, čine skup primjera za testiranje. Greška na testnom skupu naziva se e0 procjenom. Naime, prosječan broj medjusobno različitih primjera u skupu za učenje je 0.632 ukupnog broja primjera, dok je broj preostalih (takodjer medjusobno različitih primjera) primjera u testnom skupu 0.368 od ukupnog broja primjera. Tzv. 0.632 "bootstrap" (0.632B) je linearna kombinacija (0.368*trerr+0.632*e0, gdje trerr predstavlja grešku na skupu svih primjera (i iz skupa za učenje i iz testnog skupa). Procjena stvarne greške dobija se ponavljanjem ovog eksperimenta veći broj puta (100-200). Stoga je ova tehnika računalno još zahtjevnija od LOO tehnike. U Tablici 7, sumirane su osnovne karakteristike "bootstrap" tehnike procjene greške modela. I e0 i 0.632B su procjene s malom varijancom. Za umjereno velike skupove podataka e0 sistematski odstupa (daje pesimističniju procjenu od stvarne vrijednosti), stoga što se klasifikacijski model stvara na osnovu samo 63.20rimjera. No, e0 daje vrlo dobru procjenu kada je stvarna greška modela relativno visoka. Kako skup primjera raste, 0.632B je preoptimistična procjena, no za male skupove podataka, s relativno niskom stvarnom greškom modela, daje vrlo dobre rezultate. "Bootstrap" procjene nisu uvijek superiorne LOO procjeni na malom broju primjera. No, mala greška na e0, bolji je indikator dobrog modela negoli LOO procjena.

	Bootstrap
Broje primjera u skupu za učenje	n (j različitih)
Broj primjera u skupu za testiranje	n - j
Broje iteracija	200

Tablica 7: Karakteristike "bootstrap" tehnike procjene greške modela.

Recepti za dizajn dobrog klasifikacijskog modela

Budući da je naš cilj napraviti klasifikacijski model s najnižom mogućom greškom, bilo je potrebno razmotriti tehnike procjenjivanja stvarne greške modela. Za mnoge klasifikacijske tehnike cilje se može izraziti kao traženje modela koji najbolje reproducira medjuovisnost u podacima, uz da model ne bude prekomjerno specijaliziran ("over-fiting").
Evaluacija kvalitete bilo koje metode zahtjeva prije svega dobru procjenu 'stvarne' greške modela, no, neke metode pored toga nastoje mjeriti i kompleksnost modela. Priroda metrike kompleksnosti modela zavisi o tipu reprezentacije modela.
Principi stvaranja klasifikacijskih modela i njihovog testiranja su prilično općeniti, a metode procjene grešaka modela nezavisne od specifične tehnike modeliranja. Na osnovu rezultata i iskustava objavljenih u literaturi, mogu se dati upute o tome kako ekstrahirati maksimalnu količinu informacije iz skupa podataka (t.j. napraviti dobar model podataka). Stoga ćemo u nastavku opisati neke od osnovnih principa pri dizajniranju klasifikacijskih modela podataka.