Sprendimų medžių mokymas

**Sprendimų medžio mokymosi** metodas naudoja sprendimų medį kaip prognozavimo modelį, kuris sujungia pastabas apie objektą (pavaizduojama šakomis) su išvadomis apie elemento siektina verte (vaizduojama lapais). Tai - vienas iš prognozavimo modeliavimo metodų, naudojamų statistikoje, duomenų išgavime (data-mining) ir mašininiame mokymesi (machine learning). Medžio modeliai,  kuriuose priklausomas kintamasis gali įgauti baigtinę reikšmių aibę, yra vadinami **klasifikuojančiais medžiais**; tokiuose medžiuose lapai vaizduoja klases, o šakos – sutampančias ypatybes, kurios ir priveda į susijusias klases. Sprendimų medžiai, kur priklausomas kintamasis įgauna nuolatines vertes (paprastai tai - realieji skaičiai) yra vadinami **regresijos medžiais**.

Sprendimų analizėje, sprendimų medis gali būti panaudotas aiškiai ir vizualiai parodyti sprendimus ir kaip tie sprendimai buvo priimti. Duomenų išgavime sprendimų medis aprašo duomenis, tačiau  gautas ​​klasifikavimo medis gali būti naudojamas sprendimų priėmimui. Šiame puslapyje bus aprašomi sprendimų medžiai duomenų išgavimo srityje. 

## Apžvalga

Sprendimų medžio mokymosi metodas yra dažniausiai naudojamas metodas duomenų išgavime. Metodo tikslas - sukurti modelį, kuris prognozuoja priklausomo kintamojo vertę remdamasis keliais nepriklausomais kintamaisiais. Dešinėje schemoje galite pamatyti pavyzdį. Kiekvienas vidinis mazgas atitinka vieną iš nepriklausomų kintamųjų;  tiesės keliauja iki pošakių kiekvienam įmanomam nepriklausomo kintamojo variantui. Kiekvienas lapas – tai priklausomo kintamojo reikšmė atsižvelgiant į nepriklausomus kintamuosius, kurie yra pavaizduoti kelyje nuo medžio kamieno iki lapo.

Sprendimų medžio metodas - paprastas klasių pavaizdavimo pavyzdys. Šiame skirsnyje, tarkime, kad visos ypatybės  bus imamos iš baigtinės bei diskrečios srities, o išskirtinė norima ypatybė bus vadinama  klasifikacija. Kiekvienas klasifikacijos srities elementas bus vadinamas klase. 
Sprendimų medis (arba klasifikavimo medis) - medis, kuriame kiekvienas vidinis (belapis) mazgas paženklinti tam tikra įvesties ypatybe. Lankai, einantys iš mazgo, pažymėto ta ypatybe, arba žymi  visas gautas galimas ypatybes, arba  veda prie antraeilio sprendimų mazgo kitai įvesties ypatybei. Visi medžio lapai pažymėti savo klase ar tikimybiniu klasių skirstiniu.

Medis gali būti "išmoktas" padalijant pradinę duotą aibę į poaibius besiremiant elemento verte. Šis procesas kartojamas kiekvienoje  gautoje poaibėje  grįžtamuoju (rekursiniu) būdu vadinamas rekursiniu dalinimu. Pavyzdžiai parodyti paveikslėlyje: erdvės, kurios  nebuvo suskirstytos naudojant rekursinį padalinimu, bei erdvės po rekursinio dvejetainio padalinimo. Dalinimas (rekursija) yra baigtas, kai mazge vaizduojamas poaibis įgauna tą pačią vertę kaip ir priklausomas kintamasis, arba kai tolesnis dalinimas nebeduoda vertės prognozuojant. Ši iš viršaus į apačią vykstanti indukcija sprendimų medžiams (TDIDT  – Top-Down Induction of Descision Trees)  - gobšaus algoritmo pavyzdys, ir  iki šiol išliko labiausiai paplitusi strategija mokantis iš duomenų.

Duomenų išgavimo srityje sprendimų medžiai gali būti apibūdinami, kaip sąjunga tarp matematinių ir skaičiuojamųjų technikų, naudojamų geriau apibūdinti, suskaidyti bei subendrinti duotus duomenis. 

Duomenys įrašomi žemiau pavaizduota forma:
:(\textbf{x},Y) = (x_1, x_2, x_3, ..., x_k, Y)
Priklausomas kintamasis  Y, yra tas kintamasis, kurį mes bandome suprasti, suklasifikuoti arba subendrinti. Vektorius **x** yra sudarytas iš nepriklausomų kintamųjų, naudojamų šiai  užduočiai, -  x1, x2, x3, ir t. t.

## Tipai
Sprendimų medžiai, naudojami duomenų išgavime, yra dviejų pagrindinių tipų:

* **Klasifikavimo medžio** analize vadinama, kai prognozuojama baigtis yra klasė, kuriai duomenys ir priklauso.
* **Regresijos medžio** analizė - kai prognozuojamas rezultatas gali būti laikoma realiu skaičiumi (pavyzdžiui, namo kaina, arba paciento gulėjimo ligoninėje dienų skaičius).
Terminas **Klasifikavimo ir Regresijos Medžio** (**CART** – Classification And Regression Tree) ​​analizė - terminas, pirmąkart pavartotas Breiman bei kolegų yra vartojamas kalbant apie abi anksčiau minėtas procedūras. Medžiai, naudojami regresijai, ir medžiai, naudojami klasifikavimui turi tam tikrų panašumų, tačiau taip pat ir tam tikrų skirtumų, pavyzdžiui, padalinimo tvarkos procedūra.

Kai kurie metodai, dažnai vadinami sambūrio (ensemble) metodais, sukonstruoja daugiau nei vieną sprendimų medį:
* **Bagging** sprendimų medis (**B**ootstrap **agg**regat**ing**) -  anksti pradėtas naudoti sambūrio metodas – sudaro kelis sprendimų medžius pakartotinai sukaitaliodamas mokymo duomenis su pakaitiniais ir vesdamas medžius ties sutampančia prognoze. 
* Atsitiktinis miško klasifikatorius (random forest classifier) naudoja sprendimo medžių skaičių, siekdamas pagerinti klasifikavimo lygį.
* **Išpūstų medžių** metodas (boosted trees) gali būti naudojamas regresijos ir klasifikacijos tipų problemas spręsti.
* **Sukimosi miškas** – kur kiekvienas sprendimų medis apmokomas pradžioj taikant pagrindinių komponentų analizę (PCA – Principal Components Analysis) įvesties ypatybių atsitiktinės atrankos pogrupyje.
Ypatingas sprendimų medžio atvejis - sprendimų sąrašas, kuris yra vienpusis sprendimų medis, kur kiekvienas vidinis mazgas turi lygiai 1 lapų mazgą ir tiksliai 1 vidaus pomazgį  (išskyrus apatinį mazgą, kurio pomazgis - vieno lapo mazgas). Nors mažiau išraiškingi, sprendimų sąrašai -  neabejotinai lengviau suprantami nei bendrieji sprendimų medžiai dėl jų pridėto retumo, galimybės naudotis negobšiais mokymosi metodais ir taikomiems monotoniškiems suvaržymams.

**Sprendimų medžio mokymasis** - sprendimų medžio klasėmis pažymėto mokymo imties statyba. Sprendimų medis turi į srauto diagramą panašią struktūrą, kurioje kiekvienas vidinis (belapis) mazgas parodo požymio bandymą, kiekviena šaka reprezentuoja bandymo rezultatus, ir kiekvienas lapo (ar terminalo) mazgas turi klasės etiketę. Viršutinis mazgas medyje yra kamieninis mazgas.

Yra daug konkrečių sprendimų medžių algoritmų. Žymiausi yra:
* ID3 (Kartotinis Dichotomiser 3)
* C4.5 (ID3 įpėdinis)
* CART (Klasifikavimo Ir Regresijos Medis (CART – Classification And Regression Tree))
* CHAID (automatinis chi-kvadrato sąveikos detektorius (CHi-squared Automatic Interaction Detector)). Sudarant sprendimų medžius atlieka kelių lygių dalinimą.
* MARS: ištęsia sprendimų medžio metodą, kad būtų galima lengviau tvarkyti kiekybinius duomenis.
* Sąlyginės išvados medžiai. Statistika pagrįstas požiūris, kuris naudoja neparametrinius testus,  kaip dalinimo kriterijų, pakoreguotą daugeliui bandymų, kad būtų galima išvengti per aukšto kompleksiškumo. Šis požiūris lemia objektyviai prognozuojamas atrankas ir nereikalauja genėjimo.
ID3 ir CART buvo išrasti nepriklausomai vienas nuo kito maždaug tuo pačiu laiku (tarp 1970 ir 1980), tačiau abu laikosi panašios strategijos dėl sprendimų medžio mokymo iš apmokymų imties.

## Metrikos, skaičiavimai
Sprendimų medžių konstravimo algoritmai paprastai veikia iš viršaus į apačią kiekviename žingsnyje pasirenkant tokį kintamąjį, kuris padalintų elementų rinkinį geriausiu būdu. Įvairūs algoritmai naudoja skirtingus skaičiavimo būdus (metrikas) matuojant "geriausius" padalinimus  - paprastai poaibėje išmatuojamas priklausomų kintamųjų homogeniškumas (pavyzdžiai pateikti žemiau). Šios metrikos taikomos kiekvienam galimam poaibiui, o susidarančios vertės sukombinuojamos (pvz., suvidurkintos) pateikiant padalijimo kokybės matą.

### Gini priemaiša

Naudojamas CART (klasifikavimo ir regresijos medžio) algoritme, Gini priemaiša (Gini impurity)– priemonė apskaičiuoti, kaip dažnai atsitiktinai iš rinkinio pasirinkti elementai būtų neteisingai suženklinti, jei jie buvo atsitiktinai ženklinami pagal etikečių pasiskirstymą pogrupyje. Gini priemaiša gali būti apskaičiuota sudedant elemento i tikimybę būti pasirinktam f_i  kart tikimybė 1-f_i , kad tas elementas bus sukategorizuotas neteisingai. Gini priemaišos indeksas pasiekia savo minimumą (nulis), kai visų mazgų atvejai patenka į vieną tikslinę kategoriją.

Gini priemaišos elementų aibei su J klasių skaičiumi apskaičiuoti, kur i \in \{1, 2, ...,J\}, o f_i – elementų, pažymėtu klase i duotoje aibėje, funkcija, naudokite
:I_{G}(f) = \sum_{i=1}^{J} f_i (1-f_i) = \sum_{i=1}^{J} (f_i - {f_i}^2) = \sum_{i=1}^J f_i - \sum_{i=1}^{J} {f_i}^2
 = 1 - \sum^{J}_{i=1} {f_i}^{2} = \sum_{i\neq k}f_i f_k 

### Informacijos išlošis
Šis metodas naudojamas ID3, C4.5 bei C5.0 medžių generavimo algoritmuose. Informacijos išlošis (Information gain) yra paremtas entropijos samprata, naudojama informacijos teorijoje.
: H(T) = I_{E}(p_1, p_2, ..., p_n) = - \sum^{J}_{i=1} p_i \log^{}_2 p_i
: kur p_1,p_2,... – trupmenos, reprezentuojančios kiekvienos klasės egzistavimo pomazgyje, gauto po medžio išsišakojimo, procentą, ir jos susideda į 1. 
Informacijos išlošis = Entropija (prieš) – Suskaičiuota Entropijų Suma (Pomazgyje)

 IG(T,a) = H(T) - H(T|a) 

Informacijos išlošis naudojamas nustatant, kokia ypatybė skelia medį kiekviename žingsnyje. Paprastumas yra labiausiai vertinamas, tad tikslas – išlaikyti medį kuo mažesnį, o kad taip įvyktų, reikia medį iššakoti į kuo tikslesnius pomazgius. Dažnai tikslumui nustatyti naudojamas būdas – informacija (matuojama bitais), kuri neturėtų būti maišoma su kompiuterine atmintimi. Kiekvienam medžio mazgui, informacijos vertė reprezentuoja trokštamą informacijos kiekį, kuris yra reikiamas norint nurodyti, ar naujas pavyzdys turėtų būti klasifikuojamas teigiamai ar neigiamai, žinant, kad pavyzdys pasiekė mazgą.

Tarkime, jog turime duomenų su keturiomis ypatybėmis: apžvalga (saulėta, vėjuota, lyja), temperatūra (karšta, vidutinė, šalta), drėgnumas (aukštas, normalus), vėjuotumas (didelis, mažas), pavyzdį, su dvinariu (taip arba ne) priklausomu kintamuoju, 14 duomenų taškų bei atsitikimais. Tam, kad pagal šiuos duomenis sukonstruotume sprendimų medį, reikia palyginti keturių medžių, kiekvieno padalintų pagal vieną iš keturių ypatybių,  informacijos išlošius. Padalinimas, turintis didžiausia informacijos išlošį, yra priimamas kaip tikrasis padalinimas, o procesas toliau vykdomas tol, kol visi pomazgiai yra gryni (tikslūs), arba kol informacijos išlošis tampa lygus 0.  

Padalijimas pagal ypatybę vėjuotumas duoda du pomazgius, vienas skirtas dideliam vėjuotumui, kitas mažam. Šioje duomenų aibėje, yra šeši duomenų taškai su vejuotumo verte, trys su teigiama atsitikimo verte bei trys su neigiama atsitikimo verte. Aštuoni likę duomenų taškai, kurių vėjuotumo vertė yra maža turi du neigiamus atsitikimus ir šešis teigiamus. Didelio vėjuotumo mazgo informacija apskaičiuojama naudojant aukščiau pateiktą entropijos lygtį. Kadangi yra lygus teigiamų ir neigiamų atsitikimų skaičius, turime:  
: I_{E}([3,3]) = -(3/6)\log^{}_2 (3/6) - (3/6)\log^{}_2 (3/6) = -(1/2)\log^{}_2 (1/2) - (1/2)\log^{}_2 (1/2) = 1 
Mažo vėjuotumo mazge turime 8 duomenų taškus – 6 taip ir 2 ne, tad:
: I_{E}([6,2]) = -(6/8)\log^{}_2 (6/8) - (2/8)\log^{}_2 (2/8) = -(3/4)\log^{}_2 (3/4) - (1/4)\log^{}_2 (1/4) = 0.8112781 
Kad galėtume rasti padalinimo informaciją, imame numerių, paskaičiuotų pagal tai, kiek stebinių patenka į kiekvieną mazgą, vidurkį.
: I_{E}(ar vejuota) = (6/14)(1) + (8/14)(0.8112781) = 0.8921589 
Kad galėtume rasti informacijos išlošį padalinimui pagal vėjuotumą, paskaičiuojama duomenų informaciją prieš dalinimą. Pradiniai duomenys turėjo 9 teigiamus bei 5 neigiamus atsitikimus. 
: I_{E}([9,5]) = -(9/14)\log^{}_2 (9/14) - (5/14)\log^{}_2 (5/14) = 0.940286 
Dabar galima apskaičiuoti informacijos išlošį, gautą po padalinimo pagal vėjuotumą.
: IG(vejuotumas) = I_{E}([9,5]) - I_{E}([3,3],[2,6]) = 0.940286 - 0.8921589 = 0.0481271 
Norint sukonstruoti medį, turi būti suskaičiuotas kiekvieno įmanomo pirmojo padalinimo informacijos išlošis. Geriausias pirmasis dalinimas – tas su didžiausiu informacijos išlošiu. Procesas tuomet kartojamas kiekvienam negrynam (netiksliam) mazgui, kol užbaigiamas medis. Šis pavyzdys pritaikytas iš pavyzdžio, parodyto Witten bei kolegų darbe.

### Variacijos sumažinimas
Pirmąkart panaudotas CART metode, variacijos sumažinimas dažnai naudojamas situacijose kai priklausomas kintamasis yra tolydus (regresijos medis), kadangi naudojantis daugeliu kitų metrikų pradžioje reikalauja diskretizavimo išpildymo. Mazgo N variacijos sumažinimas yra aprašomas, kaip visas priklausomo kintamojo x variacijos sumažinimas šio mazgo dalinime.
:
I_{V}(N) = \frac{1}{|S|^2}\sum_{i\in S} \sum_{j\in S} \frac{1}{2}(x_i - x_j)^2 - \left(\frac{1}{|S_t|^2}\sum_{i\in S_t} \sum_{j\in S_t} \frac{1}{2}(x_i - x_j)^2 + \frac{1}{|S_f|^2}\sum_{i\in S_f} \sum_{j\in S_f} \frac{1}{2}(x_i - x_j)^2\right)

kur S– aibė, sudaryta iš dalinimo indeksų imties prieš dalinimą, S_t -aibė, sudaryta iš dalijimo indeksų imties, kur dalinimo testas teigiamas, bei S_f – aibė, sudaryta iš dalinimo indeksų imties po dalinimo, kur dalinimo testas neigiamas. Apibūdinti dydžiai reikalingi nustatant variaciją nors ir yra surašyti taip, kad tiesiogiai nenurodo vidurkio.

## Sprendimų medžių privalumai
Tarp visų kitų metodų duomenų išgavime, sprendimo medžiai turi įvairių privalumų:
* **Paprasta suprasti ir interpretuoti**. Žmonės jau po trumpų paaiškinimų sugeba juos suprasti. Medžiai taip pat gali būti pavaizduojami grafiškai, tad net ir nepatyrusiems asmenims tampa lengva juos interpretuoti. 
* **Susidoroja tiek su skaitiniais tiek su kategoriniais duomenimis.**  Kiti metodai labiau sutelkti ties vieno kintamojo tipo duomenimis (pavyzdžiui, sąryšio taisyklės naudojamos tik su nominaliais kintamaisiais, kai neuroniniai tinklai naudojami tik su skaitiniais kintamaisiais).
* **Nereikalauja daug duomenų ruošimo**. Kiti metodai dažnai reikalauja duomenų normalizavimo. Kadangi medžiai veikia su kokybiniais faktoriais, nėra prasmės naudoti fiktyviųjų kintamųjų.
* **Naudoja „baltosios dėžės“ modelį**.  Jei duota situacija atsispindi modelyje, sąlygą lengva paaiškinti naudojant Boolean logiką (Boolean logic). Palyginant, „juodosios dėžės“ modelyje dažnai tampa sunku paprastai paaiškinti sąlygą, kaip ir yra su dirbtiniais neuroniniais tinklais. 
* **Galima patikrinti modelį naudojant statistinius testus**, o tai modeliui prideda daug patikimumo.
* **Patikimas**. Puikiai dirba net ir prielaidos pažeidžiamos tikrojo modelio, iš kurio duomenys buvo sugeneruoti.
* **Puikiai tinka didelėms duomenų apimtims**. Didelės duomenų apimtys gali būti apdorojamos įprastais kompiuteriniais ištekliais bei per priimtiną laiką. 
* **Atvaizduoja žmogaus sprendimų eigą tikroviškiau, nei kiti metodai.** Tai labai patogu analizuojant žmonių elgesį.

## Apribojimai, suvaržymai
* Medžiai ne tokie tikslūs kaip kiti metodai. 
* Yra atvejų, kai jie tampa labai nepatikimi. Mažas pokytis mokymo imtyje gali reikšti didelį pokytį medžio struktūroje bei esminiuose spėjimuose.
* Optimalių sprendimų medžių mokymo problema žinoma yra kaip NP-užbaigta kai kuriais optimalumo bei paprastais aspektais. Dėl to praktinis sprendimų medžio algoritmas yra paremtas tokiomis euristikomis, kaip „smalsusis algoritmas“ (Greedy algorithm), kur lokaliai optimalūs sprendimai priimami kiekviename mazge.Tokie algoritmai negali garantuoti  globaliai optimalaus gaunamo sprendimų medžio. Norint sumažinti lokalaus optimalumo godumo efektą buvo pasiūlyti metodai, tokie kaip dvejopas informacijos atstumas (DID – dual information distance). http://www.eng.tau.ac.il/~bengal/DID.pdf 
* Sprendimų medžio mokymas gali sukurti per sudėtingus medžius, kurie aiškiai nesubendrins mokymo imties (tai dar žinoma kaip perspaudimas (overfitting)). Metodai, kaip medžio genėjimas, tampa reikalingi norint išvengti šios problemos (su kai kurių algoritmų, kaip sąlyginių išvadų metodas, kuris nereikalauja genėjimo, išimtimi.)
* Kai kurias sąvokas sunku išmokti, kadangi sprendimų medžiai jų aiškiai neparodo, tarkim XOR, lyginumo ar daugiklio problemos. Tokiais atvejais sprendimų medis tampa pernelyg didelis., o šios problemos sprendimas įtraukia problemos esmės pakeitimą (žinomą kaip siūlymavimas (propositionalization )) arba algoritmų, paremtų išraiškingesnėmis reprezentacijomis (kaip statistinis sąryšių mokymasis ar induktyvus loginis programavimas), naudojimas.
* Kategorinių kintamųjų su skirtingais lygių skaičiais duomenims sprendimų medžių informacijos išlošis yra šališkas ypatybių su daugiau lygių naudai. Tačiau ši problema aplenkiama sąlyginių išvadų metodu.

## Plėtiniai

### Sprendimų grafikai
Sprendimų medžiuose keliai nuo kamieno iki lapų mazgų eina jungtukiniu būdu, arba IR. Sprendimų grafikuose galima naudoti ir skirtinius (ARBA), sujungiant du ar daugiau kelių, naudojant minimalaus žinutės ilgio metodą (MML- minimum message length). Sprendimų grafikai buvo dar išplėsti tam, kad leistų dinamiškai išmokti anksčiau neįvardintas naujas ypatybes bei jas naudoti skirtingose grafikų vietose. Bendrinės schemos kūrimas duoda didesnį spėjimo tikslumą  bei logaritminį tikimybinį skaičiavimą. Apskritai, sprendimų grafikai išveda medžius su mažiau lapų, nei sprendimų medžiai.

### Alternatyvūs paieškos metodai
Bandant išvengti lokalių optimalių sprendimų bei rasti sprendimų medžių erdvę su mažu išankstiniu nusistatymu, buvo pasiūlyti novatoriški algoritmai.

Medžiui taip pat įmanoma naudoti MCMC imtį.

Medis gali būti apieškomas ir iš apačios į viršų.

## Vykdymas
Daugelis duomenų išgavimo programinių paketų  duoda vieno ar kito sprendimų medžio algoritmo vykdymą. Verti paminėjimo yra Salford Systems CART (kurie turi originaliems CART autoriams priklausomo kodo licenciją, IBM SPSS Modeler, RapidMiner, SAS Enterprise Miner, Matlab, R (atviro kodo statistinių skaičiavimų programinė įranga, turinti kelis CART skaičiavimo vykdymus, tokius kaip rpart, party bei randomForest paketus), Weka (nemokamas atviro kodo duomenų išgavimo rinkinys), Orange (nemokamas duomenų išgavimo mašininio mokymo rinkinys, įtraukiantis ir medžių modulį orngTree), KNIME, Microsoft SQL Server http://technet.microsoft.com/en-us/library/cc645868.aspxbei scikit-learn (nemokama atviro kodo mšininio mokymo biblioteka Python programavimo kalbai).

## Šaltiniai

## Nuorodos
* Statybos Sprendimų Medžiai "Python" programavimo kalba  Iš O' Reilly.
* Papildymas "Statybos Sprendimų Medžiai "Python" programavimo kalba" Iš O' Reilly.
* Sprendimų Medžiai Pamoka naudojant "Microsoft Excel".
* Sprendimų Medžiai puslapyje aitopics.orgpuslapis su komentavo nuorodos.
* Sprendimų medis įgyvendinimo Ruby (AI4R)
* Evoliucijos Mokymosi Sprendimo Medžių C++
* "Java" įgyvendinimo Sprendimų Medžiai remiantis Informacija Pelnas
* Labai aiškų paaiškinimą, informaciją įgyti kuo skaldymo kriterijus