Stabla odlučivanja

Rudarenje podataka

Stabla odlučivanja

Stablo odlučivanja je jedna od najčešće korištenih data mining metoda analize i modeliranja. Primjenjuju se za razvrstavanje (classification), predviđanje (prediction), procjenu vrijednosti (estimation), grupiranje (clustering), opisivanje podataka i vizualizaciju. Prednosti stabla odlučivanja pred drugim data mining metodama (npr. neuronske mreže) je jednostavnost i razumljivost metode, postoje pravila po kojima se stabla brzo i jednostavno konstruiraju i na kraju rezultat koji se dobije je jednostavno shvatljiv.

Stablo odlučivanja je nastalo na bazi statističkih metoda raspoznavanja uzoraka. Najširu primjenu ima za rješavanje prediktivnih problema uz nadzor učenja. Prediktivni problemi uključuju predviđanje vrijednosti ciljne značajke (atributa, varijable) u budućnosti, prepoznavanje uzoraka, regresiju više značajki, razlikovnu analizu, procjenu funkcije više značajki i nadgledano učenje. Za predviđanje vrijednosti ciljne značajke koristi se skup ulaznih značajki. Prediktivnim modelom se mapiraju ulazne značajke na ciljnu. Stabla odlučivanja dijele se po raznim kriterijima. Tako je jedan od kriterija vrsta ciljne značajke prema kojemu se stabla dijele na regresijska stabla više značajki, ukoliko je ciljna varijabla realan broj, te stabla za razvrstavanje, ukoliko je ciljna značajka diskretan skup vrijednosti (nivoa).

Stabla odluke se najviše upotrebljavaju za rješavanje prediktivnih problema kod kojih se predviđa vrijednost binarne ciljne značajke (slučaj kada ciljna značajka ima dva nivoa 0 ili 1). U tom slučaju metoda stabla odlučivanja se koristi za rješavanje jednostavnog nelinearnog problema u čemu je puno uspješnija od drugih data mining metoda.

Metode učenja

Standardna metoda izrade modela korištenjem stabla odlučivanja je rekurzivno particioniranje (recursive partitioning). Rekurzivno particioniranje je metoda kod koje izrada modela kreće od korijena stabla (top-down method). Proces učenja započinje usporedbom mogućih podjela na temelju jedne značajke. Kod realnih brojeva uspoređuju se podjele kod svake vrijednosti koja se pojavljuje u toj značajki. Kod diskretnih vrijednosti kod kojih nije važan redoslijed, uspoređuju se podjele svih mogućih kombinacija bez ponavljanja. Za odabir najbolje podjele postoje razni kriteriji kojima se mjeri smanjenje varijabilnosti distribucije ciljne značajke u granama ispod (child nodes) u usporedbi s granom na kojoj se radi podjela (parent node). Podjela u korijenu predstavlja podjelu ulaznog prostora na dva podprostora s granicom paralelnom jednoj ulaznoj dimenziji (značajki). Ta podjela se tada ponavlja u svakoj slijedećoj grani dok sve grane ne postanu potpuno čiste ili dok se ne zadovolji neki od kriterija zaustavljanja. Moguće je da, pomoću ulaznih značajki koje su na raspolaganju, nije moguće postići potpunu čistoću podgrana.

Evo nekoliko ilustracija složenosti algoritma. Na temelju diskretne značajke kod koje je važan redoslijed vrijednosti (ordinal) sa L različitih vrijednosti, moguće je napraviti

različitih podjela na B grana. Broj mogućih podjela na značajki kod koje nije važan redoslijed vrijednosti (nominal) sa različitih vrijednosti na B grana je S(L,B) gdje je S(L,B) Sterlingov broj druge vrste. Ukupan broj mogućih podjela je za jedan manji od Bellovog broja

Ovaj broj vrlo brzo raste s porastom broja vrijednosti (1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, …). Usporedba svih mogućih podjela najčešće nije provediva zbog prevelikog broja mogućih podjela pa su razvijene razne tehnike kojima se smanjuje broj podjela koje se dalje uspoređuju.

Za odabir najbolje podjele postoje mnogi kriteriji: entropija ili dobitak na informaciji (Morgan i Messenger 1973, Quinlan 1986), omjer dobiti (Quinlan 1986), Gini indeks raznolikosti (Morgan i Messenger 1973, Breiman 1984), Lopez de Mantras-ova funkacija udaljenosti (Lopez de Mantras 1991), ORT (Fayyad i Irani 1992), c2 test (Kass 1980, Quinlan 1986, White i Liu 1994).

Kriterij podjele se koristi prvo za odabir najbolje podjele na svakoj od značajki, a zatim za odabir najbolje od njih. Oba koraka mogu zahtijevati korekcije da bi se mogla napraviti usporedba rezultata, bez odstupanja. Kod usporedbe podjela na jednoj značajki pomoću vrijednosti c2 testa, Gini testa ili entropije potrebno je napraviti korekciju vrijednosti testa, jer s porastom broja grana na koje se dijeli, raste i vrijednost testova. Kod podjela na dvije grane, korekcija nije obavezna. Kod usporedbe podjela na različitim značajkama postoji problem rasta vrijednosti testa s porastom broja mogućih podjela. Zbog toga bi, bez upotrebe korekcije, bile preferirane podjele na značajkama s većim brojem mogućih podjela. Tako je razvijena mjera dobiti informacije, kao omjer vrijednosti testa u podgrani i grani koju se dijeli. Kass je predložio upotrebu Bonferronijeve korekcije. Prema Kassu vrijednost testa se korigira nakon što je određena podjela na svakoj značajki. Korekciju je moguće napraviti prije ili poslije odabira najbolje podjele na pojedinim značajkama. Korekcijom vrijednosti testa prije odabira najbolje podjele dobiva se bolja usporedba podjela nego upotrebom korekcije na temelju broja stupnjeva slobode.

Podrezivanje

Složenost stabla odlučivanja je funkcija broja grana, broja podjela jedne grane i dubine stabla. Dobro stablo odlučivanja ima karakteristiku da ima malo odstupanje (dobro se adaptira na signal) i malu varijancu (ne adaptira se na šum). Stablo nedovoljne kompleksnosti imat će veliko odstupanje i malu varijancu, dok će stablo prevelike kompleksnosti imati malo odstupanje uz veliku varijancu. U odabiru konačnog stabla najčešće se odlučujemo za neku sredinu. Određivanje kompleksnosti se još naziva podrezivanje stabla. Postoje dvije tehnike podrezivanja. Prva je odozgo prema dolje, kod koje se pomoću pravila zaustavljanja prekida daljnji rast stabla. Druga je odozdo prema gore, kod koje se prvo kreira stablo najveće kompleksnosti, a zatim se odstranjuju grane dok se ne postigne željena složenost.

Rast stabla je moguće ograničiti limitiranjem maksimalne dubine stabla (definiranjem maksimalnog broja nivoa), definiranjem minimalnog broja jedinki u čvoru da bi se napravila podjela ili nekom drugom statističkom metodom (npr. podjela se neće raditi ako nije statistički opravdana).

Odstranjivanje grana za vrijeme rasta stabla je obično brže, ali manje djelotvorno od odstranjivanja grana nakon što se kreira cijelo stablo. Ove dvije tehnike je moguće i kombinirati i na taj način postići i brzinu i kvalitetu. Tehnikom odstranjivanja grana nakon što je stablo kreirano, grane se odstranjuju uz istovremeno mjerenje performansi stabla.

Kvalitetu modela je najbolje mjeriti na neviđenim podacima upotrebom npr. odvojene tablice s podacima za provjeru (validacijska tablica) ili upotrebom zahtjevnije kros-validacijske metode. Logičan kriterij prema kojem će se ocjenjivati kvaliteta stabla je njegova točnost. Točnost stabla je moguće definirati na više načina.

Mjerenje postotka točno razvrstanih uzoraka je jedna od tehnika mjerenja točnosti modela. Svaka krajnja grana stabla se razvrstava u neki od nivoa izlazne značajke ovisno o omjeru klijenata u toj grani. Tako se npr. kod stabla za razvrstavanje s binarnom ciljnom značajkom, sve jedinke iz grane u kojoj je postotak jedinki jedne klase veći od 50%, sve jedinke iz te grane proglašavaju jedinkama te klase. Prag od 50% može biti i niži ukoliko modelom opisujemo rijetku pojavu.

Ukoliko je moguće definirati dobitak, odnosno gubitak po jedinici analize, tada je moguće kao kriterij kvalitete koristiti ukupan profit/gubitak i odabrati stablo s maksimalnim profitom, odnosno minimalnim gubitkom. Kada se stablo koristi za određivanje vjerojatnosti pripadnosti jedinki nekoj od klasa, Breiman preporučuje korištenje Gini indeksa za određivanje grana koje treba odstraniti. Tako je nastala jedna nova vrsta stabla koja koristi Gini indeks i kod rasta stabla i kod odstranjivanja suvišnih grana (class probability tree).

Prednosti i nedostatci

U pozitivne karakteristike metode stabla odlučivanja ubraja se i mogućnost rada s nedostajućim vrijednostima (missing values), koje se promatraju kao dodatna kategorija vrijednosti značajke. Kod upotrebe drugih metoda raspoznavanja uzoraka (regresije ili neuronskih mreža) nije moguće direktno koristiti nedostajuće vrijednosti pa se redak u kojem se one pojavljuju u bilo kojoj značajki odbacuje. Zbog postojanja dodatnog nivoa (vrijednosti) ulazne značajke, povećava se broj mogućih podjela pa je potrebna dodatna korekcija vrijednosti testova.

Kako bi se stabla učinila što robusnija, dodana je mogućnost pronalaženja zamjene za svaku značajku pomoću koje je napravljena podjela (surogat). U tom slučaju, kod apliciranja modela na neviđene podatke, kada model naiđe na nedostajuću vrijednost značajke na kojoj treba napraviti podjelu, model će upotrijebiti zamjensku značajku.

Jedan od nedostataka metode stabla odlučivanja je njezina nestabilnost, tj. mala promjena ulaznih podataka pomoću kojih se trenira model, može rezultirati velikim promjenama topologije stabla. Istovremeno performanse stabla će najvjerojatnije ostati približno iste. Nestabilnost se javlja zbog velikog broja mogućih podjela koje često imaju približno jednaku važnost (competitor splits). Zbog toga mala promjena podataka može dovesti do sasvim druge podjele, koja dalje unosi promjene u sve grane ispod sebe.

Metoda stabla odlučivanja je vrlo omiljena metoda među analitičarima već dugo vremena. Kroz vrijeme su razvijane različite tehnike izrade stabala odlučivanja pa su tako nastale mnoge poznate tehnike koje se kriju iza naziva poput: ID3, C4.5, C5.0, CHAID, BFOS. U okviru ovog članka nećemo detaljno opisivati nabrojane tehnike, no zainteresirane čitatelje upućujem na internet stranicu www.kdnuggets.com na kojoj je moguće pronaći tehničke detalje o mnogim data mining metodama. (I.V.)