Otsustuspuu algoritm – täielik juhend

See artikkel avaldati osana Andmeteaduse ajaveebi

Siiani oleme õppinud tundma lineaarset regressiooni, logistilist regressiooni ja neid oli üsna raske mõista. Alustame nüüd otsustuspuuga ja ma kinnitan teile, et see on tõenäoliselt masinõppe lihtsaim algoritm. Siin pole palju matemaatikat. Kuna seda on väga lihtne kasutada ja tõlgendada, on see üks masinõppes kõige laialdasemalt kasutatavaid ja praktilisemaid meetodeid.

Sisu

1. Mis on otsustuspuu?

2. Otsustuspuu näide

3. Entroopia

4. Teabe kogumine

5. Millal poolitamine lõpetada?

6. Kuidas lõpetada liigne istumine?

• max_sügavus
• min_samples_split
• min_samples_leaf
• max_features

7. Pügamine

• Järellõikamine
• Eellõikamine

8. Lõpumärkused

Mis on otsustuspuu?

See on tööriist, mille rakendused hõlmavad mitut erinevat valdkonda. Otsustuspuid saab kasutada nii klassifitseerimiseks kui ka regressiooniprobleemide lahendamiseks. Nimi ise viitab sellele, et see kasutab vooskeemi nagu puustruktuuri, et näidata ennustusi, mis tulenevad funktsioonipõhistest jaotustest. See algab juursõlmest ja lõpeb lehtede poolt tehtud otsusega.

Pilt 1

Enne otsustuspuude kohta lisateavet tutvume mõne terminoloogiaga.

Juuresõlmed – See on sõlm, mis asub otsustuspuu alguses. Sellest sõlmest hakkab populatsioon jagunema erinevate tunnuste järgi.

Otsustussõlmed – sõlme, mille saame pärast juursõlmede jagamist, nimetatakse otsustussõlmedeks

Lehtede sõlmed – sõlme, kus edasine poolitamine ei ole võimalik, nimetatakse lehesõlmedeks või lõppsõlmedeks

Aluspuu – nii nagu väikest osa graafist nimetatakse alamgraafikuks, samamoodi nimetatakse selle otsustuspuu alamosa alampuuks.

Pügamine – pole midagi muud kui mõne sõlme mahavõtmine, et lõpetada liigne paigaldamine.

Pilt 2

Otsustuspuu näide

Mõistame näite abil otsustuspuid.

Pilt 3

Otsustuspuud on tagurpidi, mis tähendab, et juur on tipus ja seejärel jagatakse see juur mitmeks sõlmeks. Otsustuspuud pole midagi muud kui võhiku terminites hunnik kui-muidu väiteid. See kontrollib, kas tingimus on tõene, ja kui see on tõsi, läheb see järgmisele sellele otsusele lisatud sõlmele.

Alloleval diagrammil küsib puu kõigepealt, milline on ilm? Kas on päikesepaisteline, pilvine või vihmane ilm? Kui jah, siis läheb see järgmisele funktsioonile, milleks on niiskus ja tuul. Ta kontrollib uuesti, kas on tugev või nõrk tuul, kui on nõrk tuul ja sajab vihma, siis võib inimene minna mängima.

Pilt 4

Kas märkasite ülaltoodud vooskeemis midagi? Näeme, et kui ilm on pilves siis peame mängima minema. Miks see rohkem ei jagunenud? Miks see seal peatus?

Sellele küsimusele vastamiseks peame teadma veel mõnda mõistet, nagu entroopia, teabe saamine ja Gini indeks. Lihtsamalt öeldes võin siinkohal aga öelda, et pilvise ilma korral on treeningandmete kogumi väljund alati jah, kuna siin pole häireid, ei pea me sõlme edasi poolitama.

Masinõppe eesmärk on vähendada andmestiku ebakindlust või häireid ja selleks kasutame otsustuspuid.

Nüüd mõtlete kindlasti, kuidas ma tean, mis peaks olema juursõlm? milline peaks olema otsustussõlm? millal peaksin poolitamise lõpetama? Selle otsustamiseks on olemas mõõdik nimega "entroopia", mis näitab andmestiku määramatuse suurust.

Entroopia

Entroopia pole midagi muud kui ebakindlus meie andmekogus või häiremõõdus. Proovin seda näite abil selgitada.

Oletame, et teil on sõpruskond, kes otsustab, millist filmi nad saavad pühapäeval koos vaadata. Filmide jaoks on 2 valikut, üks on "Lucy" ja teine ​​on "Titanic" ja nüüd peab igaüks oma valiku ütlema. Kui kõik on oma vastuse andnud, näeme seda "Lucy" saab 4 häält ja “Titanic” saab 5 häält. Millist filmi me nüüd vaatame? Kas pole praegu raske 1 filmi valida, sest mõlema filmi hääled on mõnevõrra võrdsed.

See on täpselt see, mida me nimetame korrarikkumiseks, mõlema filmi jaoks on võrdne arv hääli ja me ei suuda tegelikult otsustada, millist filmi peaksime vaatama. Palju lihtsam oleks olnud, kui “Lucy” poolt oleks hääli saanud 8 ja “Titanicu” poolt 2. Siin võib vabalt öelda, et enamus hääli on “Lucy” poolt, seega kõik vaatavad seda filmi.

Otsustuspuus on väljund enamasti "jah" või "ei".

Entroopia valem on näidatud allpool:

Siin lk₊ on positiivse klassi tõenäosus

p_- on negatiivse klassi tõenäosus

S on koolitusnäite alamhulk

Kuidas otsustuspuud entroopiat kasutavad?

Nüüd teame, mis on entroopia ja mis on selle valem. Järgmiseks peame teadma, kuidas see täpselt selles algoritmis töötab.

Entroopia mõõdab põhimõtteliselt sõlme lisandit. Ebapuhtus on juhuslikkuse aste; see näitab, kui juhuslikud on meie andmed. A puhas alajaotus tähendab, et sa peaksid saama "jah" või "ei".

Oletame, et a tunnusjoon on algselt 8 "jah" ja 4 "ei", pärast vasakpoolse sõlme esimest poolitamist saab 5 "jah" ja 2 "ei" kusjuures parem sõlm saab 3 "jah" ja 2 "ei".

Me näeme siin, et lõhe pole puhas, miks? Sest mõlemas sõlmes on endiselt näha negatiivseid klasse. Otsustuspuu tegemiseks peame arvutama iga jaotuse lisandi ja kui puhtus on 100%, teeme selle lehesõlmena.

Funktsiooni 2 ja funktsiooni 3 ebapuhtuse kontrollimiseks kasutame entroopia valemi abi.

Pildi allikas: autor

Funktsiooni 3 jaoks

Puust endast näeme selgelt, et vasakpoolsel sõlmel on madal entroopia või suurem puhtus kui parempoolsel sõlmel, kuna vasakpoolsel sõlmel on suurem arv "jah" ja siin on lihtne otsustada.

Pidage alati meeles, et mida kõrgem on entroopia, seda madalam on puhtus ja seda kõrgem on ebapuhtus.

Nagu varem mainitud, on masinõppe eesmärk vähendada andmestiku ebakindlust või ebapuhtust, siin saame entroopiat kasutades konkreetse sõlme lisandi, me ei tea, kas vanementroopia või konkreetse sõlme entroopia. on vähenenud või mitte.

Selleks toome uue mõõdiku nimega "Teabekast", mis annab meile teada, kui palju on vanementroopia vähenenud pärast selle jagamist mõne funktsiooniga.

Teabe kogumine

Teabe juurdekasv mõõdab ebakindluse vähenemist mõne funktsiooni tõttu ja see on ka otsustav tegur, milline atribuut tuleks valida otsustussõlmeks või juursõlmeks.

See on lihtsalt kogu andmestiku entroopia – andmestiku entroopia, mis on antud mõnele funktsioonile.

Selle paremaks mõistmiseks vaatleme näidet:
Oletame, et kogu meie elanikkonnal on kokku 30 juhtumit. Andmekogum ennustab, kas inimene läheb jõusaali või mitte. Oletame, et 16 inimest käib jõusaalis ja 14 inimest mitte

Nüüd on meil kaks funktsiooni, et ennustada, kas ta läheb jõusaali või mitte.

Funktsioon 1 on "Energia" mis võtab kaks väärtust "kõrge ja madal"

Funktsioon 2 on "Motivatsioon" mis võtab 3 väärtust “Pole motivatsiooni”, “Neutraalne” ja “Kõrgelt motiveeritud”.

Vaatame, kuidas meie otsustuspuu neid kahte funktsiooni kasutades tehakse. Kasutame teabe kogumist, et otsustada, milline funktsioon peaks olema juursõlm ja milline funktsioon tuleks asetada pärast jagamist.

Pildi allikas: autor

Arvutame entroopia:

Iga sõlme entroopia kaalutud keskmise vaatamiseks toimime järgmiselt.

Nüüd on meil väärtused E(Parent) ja E(Parent|Energy), teabe juurdekasv on:

Meie vanementroopia oli 0.99 lähedal ja pärast seda teabe võimenduse väärtust vaadates võime öelda, et andmestiku entroopia väheneb 0.37 võrra, kui teeme juursõlmeks "Energia".

Samamoodi teeme seda teise funktsiooniga "Motivatsioon" ja arvutame selle teabe juurdekasvu.

Pildi allikas: autor

Arvutame entroopia siin:

Iga sõlme entroopia kaalutud keskmise vaatamiseks toimime järgmiselt.

Nüüd on meil väärtused E(Parent) ja E(Parent|Motivation), teabe juurdekasv on:

Nüüd näeme, et funktsioon "Energia" vähendab rohkem, mis on 0.37 kui funktsioon "Motivatsioon". Seetõttu valime funktsiooni, millel on suurim teabevõimendus, ja seejärel jagame sõlme selle funktsiooni alusel.

Selles näites on "Energia" meie juursõlm ja me teeme sama alamsõlmede puhul. Siin näeme, et kui energia on “kõrge”, on entroopia madal ja seega võib öelda, et kui energia on kõrge, läheb inimene kindlasti jõusaali, aga mis siis, kui energiat on vähe? Jagame sõlme uuesti osadeks, tuginedes uuele funktsioonile, milleks on "Motivatsioon".

Millal lõhestamine lõpetada?

Kindlasti esitate endale selle küsimuse, et millal me oma puu kasvatamise lõpetame? Tavaliselt on reaalmaailma andmekogudel suur hulk funktsioone, mille tulemuseks on suur hulk poolitusi, mis omakorda annab tohutu puu. Selliste puude ehitamine võtab aega ja võib põhjustada ülepaigutamist. See tähendab, et puu annab treeningandmete kogumile väga hea täpsuse, kuid annab testiandmetes halva täpsuse.

Selle probleemi lahendamiseks on hüperparameetrite häälestamise kaudu palju võimalusi. Saame määrata oma otsustuspuu maksimaalse sügavuse, kasutades max_sügavus parameeter. Mida suurem on väärtus max_sügavus, seda keerulisem on teie puu. Treeningu viga väheneb loomulikult, kui suurendame max_sügavus väärtus, kuid kui meie testiandmed pildile tulevad, saame väga halva täpsuse. Seetõttu vajate väärtust, mis ei sobiks meie andmetega nii üle kui ka alla, ja selleks saate kasutada GridSearchCV-d.

Teine võimalus on määrata iga väljavoolamise jaoks minimaalne proovide arv. Seda tähistab min_samples_split. Siin täpsustame tühjendamiseks vajalike proovide minimaalse arvu. Näiteks saame otsuse tegemiseks kasutada minimaalselt 10 näidist. See tähendab, et kui sõlmel on vähem kui 10 näidist, saame seda parameetrit kasutades peatada selle sõlme edasise jagamise ja muuta selle lehesõlmeks.

Hüperparameetreid on rohkem, näiteks:

min_samples_leaf – tähistab minimaalset proovide arvu, mis on nõutav lehesõlmes. Mida rohkem arvu suurendate, seda suurem on ülepaigutamise võimalus.

max_features – see aitab meil otsustada, millist funktsioonide arvu parimat jaotust otsides arvestada.

Nende hüperparameetrite kohta lisateabe saamiseks lugege seda siin.

Pügamine

See on veel üks meetod, mis aitab meil vältida liigset istumist. See aitab parandada puu jõudlust, lõigates ebaolulised sõlmed või alamsõlmed. See eemaldab väga väikese tähtsusega oksad.

Pügamiseks on peamiselt kaks võimalust:

(I) Eellõikamine - saame puu kasvatamise varem lõpetada, mis tähendab, et saame kärpida/eemaldada/lõigata sõlme, kui sellel on vähe tähtsust kasvades puu.

(Ii) Järellõikamine - kunagi meie puu on ehitatud selle sügavusele, saame alustada sõlmede kärpimist nende olulisuse alusel.

Lõppmärkused

Kokkuvõtteks saime sellest artiklist teada otsustuspuude kohta. Mille alusel puu sõlmed poolitab ja kuidas saab ülepaigutamise lõpetada. miks lineaarne regressioon klassifitseerimisprobleemide korral ei toimi.

Järgmises artiklis selgitan Random forests, mis on jällegi uus tehnika, et vältida ülepaigutamist.
Otsustuspuude täieliku rakendamisega tutvumiseks vaadake minu Github hoidla.

Andke mulle teada, kui teil on allolevates kommentaarides küsimusi.

Teave Autor

Selles artiklis näidatud meediumid ei kuulu Analytics Vidhyale ja neid kasutatakse autori äranägemisel.

Pildiallikad

1. Pilt 1 – https://wiki.pathmind.com/decision-tree
2. Pilt 2 – https://wiki.pathmind.com/decision-tree
3. Pilt 3 – www.hackerearth.com
4. Pilt 4 – www.hackerearth.com

seotud

Allikas: https://www.analyticsvidhya.com/blog/2021/08/decision-tree-algorithm/