Päätöspuut: Kuinka optimoida päätöksentekoprosessiani?

Oletetaan, että pelaat peliä Kaksikymmentä kysymystä. Vastustajasi on valinnut salaa aiheen, ja sinun on selvitettävä, mitä hän valitsi. Jokaisella vuorollaan voit kysyä kyllä ​​tai ei-kysymyksen, ja vastustajan on vastattava totuudenmukaisesti. Kuinka selvität salaisuuden harvoissa kysymyksissä?

Pitäisi olla selvää, että jotkut kysymykset ovat parempia kuin toiset. Esimerkiksi ensimmäisen kysymyksesi kysyminen “Voiko se lentää?” On todennäköisesti hedelmätöntä, kun taas kysymys “Onko se elossa?” On hieman hyödyllisempi. Intuitiivisesti haluat, että jokainen kysymys kaventaa merkittävästi mahdollisten salaisuuksien tilaa, johtaen lopulta vastaukseesi.

Se on päätöspuiden perusajatus. Jokaisessa vaiheessa pohdit joukko kysymyksiä, jotka voivat osioida tietojoukon. Valitset kysymyksen, joka tarjoaa parhaan jaon, ja löydät taas parhaat osiot osioille. Pysäytät, kun kaikki ajatellut pisteet ovat samaan luokkaan. Silloin luokittelu on helppoa. Voit yksinkertaisesti tarttua pisteeseen ja iskutella sen puun alapuolelle. Kysymykset ohjaavat sen sopivaan luokkaan.

Tärkeät ehdot

Päätöspuu on eräänlainen ohjattu oppimisalgoritmi, jota voidaan käyttää sekä regressio- että luokitteluongelmissa. Se toimii sekä kategoriallisissa että jatkuvissa tulo- ja lähtömuuttujissa.

Tunnistetaan tärkeät terminologiat päätöksentekopuussa tarkastelemalla yllä olevaa kuvaa:

  • Juurisolmu edustaa koko populaatiota tai otosta. Lisäksi se jaetaan kahteen tai useampaan homogeeniseen joukkoon.
  • Halkaisu on prosessi, jolla solmu jaetaan 2 tai useampaan alisolmuun.
  • Kun alisolmu jakaantuu edelleen alisolmuihin, sitä kutsutaan päätössolmuksi.
  • Solmuja, jotka eivät jakaudu, kutsutaan päätesolmuksi tai lehtiä.
  • Kun poistat päätössolmun alisolmuja, tätä prosessia kutsutaan karsimiseksi. Leikkaamisen vastakohta on halkaisu.
  • Koko puun osaosaa kutsutaan haaraksi.
  • Solmua, joka on jaettu alisolmuihin, kutsutaan alisolmujen vanhemmaksi solmuksi; kun taas alisolmuja kutsutaan vanhemman solmun lapsiksi.

Kuinka se toimii

Puhun tässä vain luokittelupuusta, jota käytetään ennustamaan laadullinen vastaus. Regressiopuuta käytetään ennustamaan kvantitatiiviset arvot.

Luokittelupuussa ennustamme, että jokainen havainto kuuluu yleisimmin esiintyvään harjoitushavaintojen luokkaan alueella, johon se kuuluu. Tulkitsemalla luokittelupuun tuloksia, olemme usein kiinnostuneita paitsi tietyn päätesolmun aluetta vastaavasta luokan ennustamisesta, myös luokan suhteista siihen alueeseen kuuluvien harjoitushavaintojen joukossa. Luokittelupuun kasvatuksen tehtävänä on käyttää yhtä näistä kolmesta menetelmästä kriteerinä binaaristen halkaisujen tekemiseen:

1 - Luokitteluvirheaste: Voimme määrittää ”osumaprosentin” osana harjoitushavaintoja tietyllä alueella, jotka eivät kuulu yleisimmin esiintyvään luokkaan. Virhe annetaan seuraavalla yhtälöllä:

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

jossa π̂ mc edustaa luokan c kuuluvaa harjoitustiedon osaa alueella R_m.

2 - Gini-indeksi: Gini-indeksi on vaihtoehtoinen virhemetriikka, joka on suunniteltu osoittamaan kuinka puhdas alue on. ”Puhtaus” tarkoittaa tässä tapauksessa sitä, kuinka suuri osa tietyn alueen harjoitustiedoista kuuluu yhteen luokkaan. Jos alue R_m sisältää tietoja, jotka ovat pääosin yhdestä luokasta c, Gini-indeksin arvo on pieni:

3 - Cross-Entropy: Kolmas vaihtoehto, joka on samanlainen kuin Gini-indeksi, tunnetaan nimellä Cross-Entropy tai Deviance:

Risti-entropialla on arvo lähellä nollaa, jos π̂ mc: n arvot ovat kaikki lähellä 0: ta tai lähellä yhtä. Siksi, kuten Gini-indeksillä, ristiennografialla on pieni arvo, jos m. Solmu on puhdas. Itse asiassa käy ilmi, että Gini-indeksi ja risti-entropia ovat numeerisesti melko samanlaisia.

Luokittelupuuta rakennettaessa joko Gini-indeksiä tai risti-entropiaa käytetään tyypillisesti tietyn jaon laadun arviointiin, koska ne ovat herkempiä solmujen puhtaudelle kuin luokitteluvirheaste. Mitä tahansa näistä kolmesta lähestymistavasta voitaisiin käyttää puun karsimisessa, mutta luokitteluvirheaste on parempi, jos lopullisen karsitun puun ennustetarkkuus on tavoite.

Toteutus tyhjästä

Kävelemme päätöksentekopuun rakennusalgoritmin läpi kaikilla sen hienoilla yksityiskohdilla. Päätöspuun rakentamiseksi meidän on tehtävä alustava päätös tietojoukosta sanelemaan, mitä ominaisuutta käytetään tietojen jakamiseen. Tämän määrittämiseksi meidän on kokeiltava kaikkia ominaisuuksia ja mitattava, mikä jako antaa meille parhaat tulokset. Sen jälkeen me jaamme tietojoukon osajoukkoihin. Osajoukot kulkevat sitten ensimmäisen päätöksentekoisolmun haaraa pitkin. Jos oksilla olevat tiedot ovat samaa luokkaa, niin me olemme luokitelleet ne oikein eikä meidän tarvitse jatkaa sen jakamista. Jos tiedot eivät ole samat, meidän on toistettava jakaminen tällä alajoukolla. Tämän alajoukon jakamista koskeva päätös tehdään samalla tavalla kuin alkuperäinen tietojoukko, ja toistamme tämän prosessin, kunnes olemme luokittaneet kaikki tiedot.

Kuinka jaamme tietojoukkomme? Yksi tapa järjestää tämä sotkuisuus on mitata tiedot. Tietoteorian avulla voimme mitata tiedot ennen jakoa ja sen jälkeen. Tietojen muutos ennen jakoa ja sen jälkeen tunnetaan tiedon saamisena. Kun tiedämme kuinka laskea tiedon hyöty, voimme jakaa tietomme jokaisen ominaisuuden kesken nähdäksemme, mikä jako antaa meille korkeimman tiedonsaannin. Jako, jolla on suurin informaatiovoitto, on paras vaihtoehto.

Tietojen voiton laskemiseksi voimme käyttää Shannon Entropiaa, joka on kaikkien tietojemme odotettu arvo kaikista luokkamme mahdollisista arvoista. Katsotaanpa sen Python-koodi:

Kuten voitte nähdä, laskemme ensin tietojoukon esiintymien määrän. Sitten luomme sanakirjan, jonka avaimet ovat arvot viimeisessä sarakkeessa. Jos avainta ei ole havaittu aiemmin, se luodaan. Jokaiselle avaimelle seuraamme, kuinka monta kertaa tämä tarra esiintyy. Lopuksi käytämme kaikkien eri merkkien taajuutta laskeaksemme kyseisen tarran todennäköisyyden. Tätä todennäköisyyttä käytetään laskemaan Shannon-entropia, ja me summaamme tämän kaikkien merkintöjen osalta.

Kun olemme keksineet tavan mitata tietojoukon entropia, meidän on jaettava tietojoukko, mitattava entropia jakojoukkoissa ja tarkastettava, onko sen jakaminen oikein. Tässä on koodi, jolla se tehdään:

Tämä koodi vaatii 3 syöttöä: jaettavat tiedot, jaettava ominaisuus ja palautettavan ominaisuuden arvo. Luomme joka kerta uuden luettelon alussa, koska kutsumme tätä toimintoa useita kertoja samaan tietojoukkoon, emmekä halua, että alkuperäistä aineistoa muutetaan. Tietomme on luettelo luetteloista; kun iteroimme luettelon kaikkia kohteita ja jos se sisältää etsimämme arvon, lisäämme sen uuteen luetteloomme. If-lauseen sisällä me leikkasimme piirretyn funktion.

Nyt yhdistämme 2 toimintoa: ShannonEntropy ja splitDataset selataksesi tietojoukkoa ja päättää, mikä ominaisuus on paras jakaa.

Tutkitaan koodi nopeasti:

  • Laskemme koko tietojoukon Shannon-entropian ennen jakautumista ja määrittelemme arvon muuttujalle baseEntropy.
  • Ensimmäinen silmukkasilmukoille, jotka kattavat kaikki tietomme ominaisuudet. Käytämme luettelon ymmärtämistä luettelon (featList) luomiseksi kaikista datan i-des merkinnöistä tai kaikista mahdollisista arvoista, jotka esiintyvät tiedoissa.
  • Seuraavaksi luomme uuden joukon luettelosta, jotta yksilölliset arvot saadaan ulos (uniqueVals).
  • Sitten käydään läpi tämän ominaisuuden kaikki ainutlaatuiset arvot ja jaetaan tiedot jokaiselle ominaisuudelle (subData). Uusi entropia lasketaan (newEntropy) ja summataan kyseisen ominaisuuden kaikille ainutlaatuisille arvoille. Informaatiovoitto (infoGain) on entropian väheneminen (baseEntropy - newEntropy).
  • Lopuksi vertaamme tiedon saamista kaikkien ominaisuuksien välillä ja palautamme parhaan jaettavan ominaisuuden hakemiston (bestFeature).

Nyt kun voimme mitata tietojoukon järjestäytymisen ja jakaa tiedot, on aika koota tämä kaikki yhteen ja rakentaa päätöksentekopuu. Jakaamme sen tietojoukosta parhaan jaettavan ominaisuuden perusteella. Kun se on jaettu, se kulkee puun oksien kautta toiseen solmuun. Sitten tämä solmu jakaa tiedot uudelleen. Käytämme rekursiota käsittelemään tätä.

Pysäytämme vain seuraavissa olosuhteissa: (1) määritteet, joille jakaa, loppuu tai (2) kaikki haarassa olevat esiintymät ovat samaa luokkaa. Jos kaikilla esiintymillä on sama luokka, luomme lehtisolmun. Kaikkien tietojen, jotka saapuvat tähän lehtisolmuun, katsotaan kuuluvan kyseisen lehtisolmun luokkaan.

Tässä on koodi päätöksentekopuudemme rakentamiseksi:

Koodissamme on 2 syötettä: tiedot ja luettelo tarroista:

  • Luomme ensin luettelon kaikista luokan tunnisteista tietojoukossa ja kutsumme tätä classList. Ensimmäinen pysäytysedellytys on, että jos kaikki luokan etiketit ovat samat, palautamme tämän tarran. Toinen pysäytysedellytys on tapaus, jossa jaettavia ominaisuuksia ei ole enää. Jos emme täytä pysäytysolosuhteita, valitsemme parhaan ominaisuuden valitsemalla toiminto selectBestFeatureToSplit.
  • Puun luomiseksi tallennamme sen sanakirjaan (myTree). Sitten saamme kaikki ainutlaatuiset arvot valitun ominaisuuden (bestFeat) aineistosta. Yksilöivä arvokoodi käyttää sarjoja (uniqueVals).
  • Lopuksi iteroimme kaikki valitun ominaisuuden yksilölliset arvot ja kutsumme rekursiivisesti createTree () jokaiselle tietojoukon jaolle. Tämä arvo lisätään myTree-sanakirjaan, joten saamme paljon puun sisäkkäisiä sanakirjoja.

Toteutus Scikit-Learnin kautta

Nyt kun tiedämme kuinka algoritmi voidaan toteuttaa tyhjästä, käytämme scikit-oppia. Käytämme erityisesti DecisionTreeClassifier-luokkaa. Iris-tietojoukon kanssa työskennellessämme ensin tuodaan tiedot ja jaetaan ne koulutus- ja testiosaan. Sitten rakennamme mallin, jossa oletusasetuksella kehitetään puu kokonaan (kasvatetaan puuta, kunnes kaikki lehdet ovat puhtaita). Korjaamme satunnaisvaltion puussa, jota käytetään solmimiseen sisäisesti:

Mallin suorittamisen pitäisi antaa meille testisarjan tarkkuus 95%, mikä tarkoittaa, että malli ennustaa luokan oikein 95%: lle testitiedot sisältävistä näytteistä.

Vahvuudet ja heikkoudet

Päätöspuiden käytön suurin etu on, että ne on intuitiivisesti erittäin helppo selittää. Ne heijastavat tiiviisti ihmisen päätöksentekoa verrattuna muihin regressio- ja luokittelutapoihin. Ne voidaan näyttää graafisesti ja ne voivat helposti käsitellä laadullisia ennustajia ilman, että sinun on luotava tyhjiä muuttujia.

Toinen valtava etu on, että algoritmit ovat täysin muuttumattomia datan skaalaamiseen. Koska kutakin ominaisuutta prosessoidaan erikseen ja tietojen mahdolliset halkaisut eivät riipu skaalaamisesta, päätöksentekopuun algoritmeille ei tarvita esikäsittelyä, kuten ominaisuuksien normalisointia tai standardisointia. Erityisesti päätöksentekopuut toimivat hyvin, kun meillä on ominaisuuksia, jotka ovat täysin eri mittakaavassa, tai sekoitus binaarisia ja jatkuvia ominaisuuksia.

Päätöspuilla ei kuitenkaan yleensä ole ennustetun tarkkuuden tasoa kuin muilla lähestymistavoilla, koska ne eivät ole aivan vankkoja. Pieni muutos tiedoissa voi aiheuttaa suuren muutoksen lopullisessa arvioidussa puussa. Jopa käyttämällä esikarsintaa, niillä on taipumus olla liian suuria ja niiden yleinen suorituskyky on heikko. Siksi useimmissa sovelluksissa, yhdistämällä monia päätöksentekopuita, käyttämällä menetelmiä, kuten pussittaminen, satunnaiset metsät ja tehostamalla, päätöksenpuiden ennustavaa suorituskykyä voidaan parantaa huomattavasti.

Lähde:

  • Gareth Jamesin, Daniela Wittenin, Trevor Hastien ja Robert Tibshiranin johdanto tilastolliseen oppimiseen (2014)
  • Koneoppiminen toiminnassa - Peter Harrington (2012)
  • Johdanto koneoppimiseen Pythonin avulla, kirjoittanut Sarah Guido ja Andreas Muller (2016)

- -

Jos nautit tästä kappaleesta, rakastan sitä, jos osut taputuspainikkeeseen , jotta muut saattavat kompastua siihen. Löydät oman koodini GitHubista, ja lisää kirjoituksistani ja projekteistani osoitteessa https://jameskle.com/. Voit myös seurata minua Twitterissä, lähettää sähköpostia suoraan minulle tai löytää minut LinkedInistä.