Otsustuspuud: kuidas optimeerida minu otsustusprotsessi?

Kujutame ette, et mängite mängu Kakskümmend küsimust. Teie vastane on salaja teema valinud ja peate välja mõtlema, mille ta valis. Igal sammul võite küsida jah või ei küsimuse ja vastane peab vastama tõepäraselt. Kuidas saate saladuse teada kõige vähem küsimustes?

Peaks olema ilmne, et mõned küsimused on paremad kui teised. Näiteks kui teie esimese küsimuse küsimine „Kas see suudab lennata?“ On tõenäoliselt viljatu, samas kui küsimine „Kas see on elus?“ On natuke kasulikum. Intuitiivselt soovite, et iga küsimus kitsendaks võimalike saladuste ruumi, viies lõpuks teie vastuseni.

See on otsustuspuude põhiidee. Igas punktis kaalute küsimuste kogumit, mille abil saab teie andmekogu eraldada. Valite küsimuse, mis tagab parima jaotuse, ja jälle leidke partitsioonide jaoks parimad küsimused. Peatate pärast seda, kui kõik kaalutavad punktid on samast klassist. Siis on klassifitseerimise ülesanne lihtne. Võite lihtsalt punkti haarata ja puu otsast selle maha lüüa. Küsimused suunavad selle sobivasse klassi.

Olulised tingimused

Otsustuspuu on teatud tüüpi juhendatud õppealgoritm, mida saab kasutada nii regressiooni- kui ka klassifitseerimisprobleemide lahendamisel. See töötab nii kategooriliste kui ka pidevate sisend- ja väljundmuutujate jaoks.

Selgitame välja olulised terminid otsustuspuul, vaadates ülemist pilti:

  • Juursõlm esindab kogu populatsiooni või valimit. Edasi jagatakse see kaheks või enamaks homogeenseks komplektiks.
  • Poolitamine on sõlme jagamine kaheks või enamaks alamsõlmeks.
  • Kui alamsõlm jaguneb täiendavateks alamsõlmedeks, nimetatakse seda otsussõlmeks.
  • Sõlme, mis ei jagune, nimetatakse terminalisõlmeks või leheks.
  • Kui eemaldate otsussõlme alamsõlmed, nimetatakse seda protsessi pügamiseks. Kärpimise vastand on poolitamine.
  • Terve puu alasektsiooni nimetatakse haruks.
  • Sõlme, mis jaguneb alamsõlmedeks, nimetatakse alamsõlmede vanemsõlmeks; arvestades, et alam-sõlme nimetatakse vanema sõlme lapseks.

Kuidas see töötab

Siinkohal räägin ainult klassifitseerimispuust, mida kasutatakse kvalitatiivse vastuse ennustamiseks. Kvantitatiivsete väärtuste ennustamiseks kasutatakse regressioonipuu.

Klassifikatsioonipuu puhul ennustame, et iga vaatlus kuulub kõige sagedamini esinevasse treenimisvaatluste klassi selles piirkonnas, kuhu ta kuulub. Klassifikatsioonipuu tulemuste tõlgendamisel huvitab meid sageli mitte ainult konkreetsele terminalisõlme piirkonnale vastav klasside ennustus, vaid ka klasside proportsioonid sellesse piirkonda langevate koolitusvaatluste hulgas. Klassifikatsioonipuu kasvatamise ülesandeks on binaarsete lõhede tegemise kriteeriumina ühe neist kolmest meetodist kasutamine:

1 - klassifitseerimise veamäär: võime määratleda „löögisageduse” kui konkreetse piirkonna treeningvaatluste osa, mis ei kuulu kõige laialdasemalt esinevasse klassi. Vea annab järgmine võrrand:

E = 1 - argmax_ {c} (π̂ mc)

kus π̂ mc tähistab klassi C kuuluvate treeningandmete murdosa piirkonnas R_m.

2 - Gini indeks: Gini indeks on alternatiivne veamõõdik, mille eesmärk on näidata, kui piirkond on puhas. Puhtus tähendab sel juhul seda, kui suur osa konkreetse piirkonna treeninguandmetest kuulub ühte klassi. Kui piirkond R_m sisaldab andmeid, mis pärinevad enamasti ühest klassist c, on Gini indeksi väärtus väike:

3 - Rist-Entroopia: Kolmas alternatiiv, mis sarnaneb Gini indeksiga, on Rist-Entroopia või Deviance:

Rist-entroopia väärtus on nullilähedane, kui π̂ mc-d on kõik 0 lähedal või lähedal. Seega, nagu ka Gini indeks, võtab rist-entroopia väikese väärtuse, kui m-nda sõlme on puhas. Tegelikult selgub, et Gini indeks ja rist-entroopia on arvuliselt üsna sarnased.

Klassifikatsioonipuu ehitamisel kasutatakse konkreetse lõhe kvaliteedi hindamiseks tavaliselt Gini indeksit või rist-entroopiat, kuna need on sõlme puhtuse suhtes tundlikumad kui klassifitseerimise veamäär. Puu pügamisel võib kasutada mõnda neist kolmest lähenemisviisist, kuid klassifitseerimise veamäär on eelistatavam, kui eesmärk on lõpliku pügatud puu ennustamistäpsus.

Rakendamine nullist

Jalutame läbi otsustuspuu loomise algoritmi koos kõigi selle detailidega. Otsustuspuu ehitamiseks peame tegema andmekogumis esialgse otsuse, et dikteerida, millist funktsiooni kasutatakse andmete jagamiseks. Selle kindlakstegemiseks peame proovima kõiki funktsioone ja mõõtma, milline jagamine annab meile parimad tulemused. Pärast seda jaotame andmestiku alamkomplektidesse. Seejärel läbivad alamkomplektid esimese otsussõlme harud. Kui harude andmed on sama klass, siis oleme selle õigesti klassifitseerinud ja me ei pea selle jagamist jätkama. Kui andmed pole samad, peame jagama selle alamhulga jagamisprotsessi. Selle alamhulga jagamise otsus tehakse samamoodi nagu algses andmekogumis ja korrame seda toimingut seni, kuni oleme kõik andmed klassifitseerinud.

Kuidas jaotame oma andmekogumi? Üks viis selle jama korraldamiseks on teabe mõõtmine. Infoteooria abil saame mõõta teavet enne ja pärast jaotust. Teabe muutust enne ja pärast jaotust nimetatakse teabe saamiseks. Kui me teame, kuidas arvutada teabe juurdekasvu, saame jagada oma andmed kõigi funktsioonide vahel, et näha, milline jaotus annab meile suurima teabekasvu. Jaotus suurima teabekasvuga on meie parim võimalus.

Teabekasumi arvutamiseks võime kasutada Shannoni entroopiat, mis on meie klassi kõigi võimalike väärtuste kogu teabe eeldatav väärtus. Vaatame selle Pythoni koodi:

Nagu näete, arvutame esmalt andmekogumis olevate eksemplaride arvu. Seejärel loome sõnastiku, mille võtmed on viimases veerus olevad väärtused. Kui võtit varem ei kohanud, luuakse see. Iga võtme puhul jälgime, mitu korda see silt ilmub. Lõpuks kasutame selle sildi tõenäosuse arvutamiseks kõigi erinevate siltide sagedust. Seda tõenäosust kasutatakse Shannoni entroopia arvutamiseks ja see võetakse kõigi siltide jaoks kokku.

Pärast andmekogu entroopia mõõtmise viisi leidmist peame selle jagama, mõõtma jagatud komplektide entroopia ja vaatama, kas selle jagamine oli õige asi. Selleks on vaja järgmist koodi:

See kood sisaldab kolme sisestust: jagatavad andmed, jagatav funktsioon ja tagastatava funktsiooni väärtus. Koostame iga kord alguses uue loendi, kuna helistame sellele funktsioonile mitu korda samal andmestikul ja me ei soovi, et algset andmestikku muudetaks. Meie andmestik on loendite loend; kui itereerime iga loendi üksuse kohal ja kui see sisaldab otsitavat väärtust, siis lisame selle oma vastloodud loendisse. If-lause sisest lõikasime välja funktsiooni, mille me jagasime.

Nüüd ühendame 2 funktsiooni: ShannonEntropy ja splitDataset, et liikuda läbi andmestiku ja otsustasime, millist funktsiooni on kõige parem jagada.

Uurime koodi kiiresti:

  • Arvutame kogu andmestiku Shannoni entroopia enne jaotuse tekkimist ja omistame väärtuse muutujale baseEntropy.
  • Esimene - kõigi meie andmetes sisalduvate silmuste silmuste jaoks. Kasutame loendite mõistmist, et luua loetelu kõigist i-ndatest kirjetest või kõigist andmetes esinevatest võimalikest väärtustest (featList).
  • Järgmisena loome loendist uue komplekti, et saada kordumatud väärtused välja (uniqueVals).
  • Seejärel vaatame läbi kõik selle funktsiooni unikaalsed väärtused ja jaotame iga funktsiooni (subData) andmed. Uus entroopia arvutatakse (newEntropy) ja summeeritakse selle funktsiooni kõigi kordumatute väärtuste jaoks. Teabe saamine (infoGain) on entroopia vähenemine (baseEntropy - newEntropy).
  • Lõpuks võrdleme teabe juurdekasvu kõigi funktsioonide vahel ja saadame parima omaduse indeksi, mille vahel jagada (bestFeature).

Nüüd, kui saame mõõta, kui korraldatud on andmekogum ja saame andmeid jagada, on aeg see kõik kokku panna ja otsustuspuu üles ehitada. Andmekogumist jagasime selle jagamiseks parima atribuudi alusel. Pärast jagamist liiguvad andmed puu okstest teise sõlme. Seejärel jagab see sõlme andmed uuesti. Selle käsitlemiseks kasutame rekursiooni.

Peatame ainult järgmistel tingimustel: (1) atribuudid, mida jagada, lõppevad või (2) kõik haru eksemplarid on sama klass. Kui kõigil esinemisjuhtudel on sama klass, loome lehesõlme. Andmeid, mis jõuavad selle lehesõlme, loetakse selle lehesõlme klassi kuuluvaks.

Meie otsustuspuude loomise kood on järgmine:

Meie kood sisaldab 2 sisendit: andmed ja siltide loend:

  • Esmalt loome kõigi andmekogumis olevate klassimärkide loendi ja kutsume seda klassilisti. Esimene peatustingimus on see, et kui kõik klassi sildid on ühesugused, tagastame selle sildi. Teine peatustingimus on juhtum, kui pole enam funktsioone, mida jagada. Kui me ei vasta peatumistingimustele, kasutame parima funktsiooni valimiseks funktsiooni selectBestFeatureToSplit.
  • Puu loomiseks salvestame selle sõnastikku (myTree). Siis saame kõik valitud funktsiooni (bestFeat) andmekogumist kõik ainulaadsed väärtused. Ainulaadne väärtuskood kasutab komplekte (uniqueVals).
  • Lõpuks korratakse kõiki valitud funktsiooni unikaalseid väärtusi ja kutsume rekursiivselt luua andmekogumi iga lõigu jaoks createTree (). See väärtus sisestatakse myTree sõnastikku, nii et lõpuks on meil palju puus sisalduvaid sõnastikke, mis esindavad meie puud.

Rakendamine Scikit-Learn kaudu

Nüüd, kui me teame, kuidas algoritmi nullist rakendada, kasutagem scikit-learning. Eelkõige kasutame klassi DecisionTreeClassifier. Iirise andmestikuga töötades impordime kõigepealt andmed ja jaotame need koolituse ja testi osaks. Seejärel ehitame mudeli, kasutades puu täielikuks arendamiseks vaikimisi seadet (puu kasvatamine, kuni kõik lehed on puhtad). Parandame puusse juhusliku_riigi, mida kasutatakse sisemiselt lipsude murdmiseks:

Mudeli käitamine peaks andma testkomplekti täpsuseks 95%, see tähendab, et mudel ennustas klassi õigesti 95% -le katseandmete komplekti proovidest.

Tugevused ja nõrkused

Otsustuspuude kasutamise peamine eelis on see, et neid on intuitiivselt väga lihtne selgitada. Need peegeldavad tihedalt inimeste otsuste langetamist, võrreldes teiste regressiooni- ja klassifitseerimismeetoditega. Neid saab kuvada graafiliselt ja nad saavad hõlpsasti hakkama kvalitatiivsete ennustajatega, ilma et oleks vaja luua näivmuutujaid.

Veel üks tohutu eelis on see, et algoritmid on andmete mastaapimisel täiesti muutumatud. Kuna igat funktsiooni töödeldakse eraldi ja andmete võimalik lõhe ei sõltu mastaapimisest, pole otsustuspuu algoritmide jaoks vaja eeltöötlust, näiteks funktsioonide normaliseerimist või standardimist. Eelkõige toimivad otsustuspuud hästi siis, kui meil on funktsioone, mis asuvad täiesti erineval skaalal, või segu binaarsetest ja pidevatest omadustest.

Otsustuspuud ei ole tavaliselt ennustava täpsusega samal tasemel kui teised lähenemisviisid, kuna need pole kuigi jõulised. Väike muudatus andmetes võib põhjustada suure muutuse lõplikus hinnangulises puus. Isegi eellõikamise korral kipuvad nad ületäituma ja tagavad halva üldistuse. Seetõttu saab enamiku rakenduste puhul otsustuspuude ennustatavat toimimist märkimisväärselt parandada, liites kokku palju otsustuspuid, kasutades selliseid meetodeid nagu kottide pakkimine, juhuslikud metsad ja turgutamine.

Viiteallikad:

  • Gareth Jamesi, Daniela Witteni, Trevor Hastie ja Robert Tibshirani (2014) sissejuhatus statistilisse õppesse
  • Peter Harringtoni masinõpe tegevuses (2012)
  • Sarah Guido ja Andreas Mulleri sissejuhatus masinõppesse Pythoni abil (2016)

- -

Kui teile see tükk meeldiks, siis meeldiks mulle see, kui te vajutaksite plaksutusnuppu , nii et teised võivad selle otsa komistada. Minu enda koodi leiate GitHubist ja minu kirjutiste ning projektide kohta leiate lisateavet aadressilt https://jameskle.com/. Võite mind jälgida ka Twitteris, saata mulle otse e-kirju või leida mind LinkedInist.