Döntési fák: Hogyan lehet optimalizálni a döntéshozatali folyamatomat?

Képzeljük el, hogy húsz kérdés játékot játszik. Az ellenfeled titokban választott tárgyat, és Önnek kitalálnia kell, hogy mit választott. Minden körben feltehet egy igen vagy nem kérdést, és ellenfelének igazságosan kell válaszolnia. Hogyan találja meg a titkot a legkevesebb kérdésben?

Nyilvánvaló, hogy néhány kérdés jobb, mint mások. Például az első kérdés valószínűleg eredménytelen, ha felteszi a kérdést: „Repülni tud?”, Míg kicsit hasznosabb a „Még él?” Feltevés. Intuitív módon azt akarja, hogy minden kérdés jelentősen szűkítse a lehetséges titkok helyét, végül pedig a válaszhoz vezet.

Ez az alapötlet a döntési fák mögött. Minden ponton mérlegel egy olyan kérdést, amely megoszthatja az adatkészletet. Kiválasztja azt a kérdést, amelyik biztosítja a legjobb osztást, és ismét megtalálja a legjobb kérdéseket a partíciókhoz. Ha abbahagyja az összes pont, amelyet figyelembe vesz, ugyanabból az osztályból áll. Akkor az osztályozás feladata könnyű. Egyszerűen megragadhat egy pontot, és ütheti le a fára. A kérdések a megfelelő osztályba vezetik.

Fontos feltételek

A döntési fa egy felügyelt tanulási algoritmus, amely regressziós és osztályozási problémákban egyaránt használható. Mind kategorikus, mind folyamatos bemeneti és kimeneti változókra működik.

A fenti képen nézzük meg a döntési fa fontos terminológiáit:

  • A gyökér csomópont a teljes populációt vagy mintát képviseli. Ez tovább osztható 2 vagy több homogén halmazra.
  • A felosztás egy csomópont 2 vagy több alcsomópontra osztása.
  • Amikor egy alcsomópont további alcsomópontokra osztódik, úgy döntési csomópontnak nevezzük.
  • Azokat a csomópontokat, amelyek nem oszlanak el, terminálcsomópontnak vagy levélnek nevezzük.
  • A döntési csomópont alcsomópontjainak eltávolításakor ezt a folyamatot metszésnek nevezik. A metszés ellentéte a hasítás.
  • A teljes fa egy részét ágnak nevezzük.
  • Az alcsomópontokra osztott csomópontot az alcsomópontok szülőcsomójának nevezzük; mivel az alcsomópontokat a szülő csomópont gyermekének nevezzük.

Hogyan működik

Itt csak az osztályozási fáról beszélek, amely a kvalitatív válasz előrejelzésére szolgál. A regressziós fát használják a kvantitatív értékek becslésére.

Egy osztályozási fában azt jósoljuk, hogy minden megfigyelés azon régióban a leggyakrabban előforduló edzési megfigyelések osztályához tartozik, amelyhez tartozik. A besorolási fa eredményeinek értelmezésekor gyakran nem csak egy adott terminálcsomópont-régiónak megfelelő osztálybecslés érdekli, hanem az osztályba eső arányok az ebbe a régióba eső gyakorlati megfigyelések között. A besorolási fa növekedésének feladata a három módszer egyikének a felhasználása kritériumként a bináris hasítások készítéséhez:

1 - Osztályozási hibaarány: A „találati arányt” úgy definiálhatjuk, mint egy adott régióban az edzésmegfigyelések azon részét, amelyek nem tartoznak a legszélesebb körben előforduló osztályba. A hibát az alábbi egyenlet adja:

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

ahol π̂ mc képviseli az R_m régióban a c osztályhoz tartozó edzési adatok töredékét.

2 - Gini-index: A Gini-index egy alternatív hibamérő, amelynek célja, hogy megmutassa, mennyire „tiszta” egy régió. A „tisztaság” ebben az esetben azt jelenti, hogy egy adott régióban az edzési adatok mekkora része tartozik egy osztályhoz. Ha az R_m régió olyan adatokat tartalmaz, amelyek többnyire egyetlen c osztályból származnak, akkor a Gini Index értéke kicsi:

3 - Kereszt-entrópia: A Gini-indexhez hasonló harmadik alternatíva kereszt-entrópia vagy Deviance néven ismert:

A kereszt-entrópia nullához közeli értéket vesz fel, ha a π̂ mc értéke 0 közelében vagy 1 közelében van. Ezért, hasonlóan a Gini-indexhez, a kereszt-entrópia kis értéket vesz fel, ha az m-es csomópont tiszta. Valójában kiderül, hogy a Gini-index és a kereszt-entrópia számszerűen nagyon hasonló.

Osztályozási fa felépítésekor vagy a Gini-indexet, vagy a kereszt-entrópiát használják egy adott hasítás minőségének értékelésére, mivel ezek érzékenyebbek a csomópont tisztaságára, mint az osztályozási hibaarány. A 3 megközelítés bármelyike ​​használható a fa metszésekor, de az osztályozási hibaarány előnyösebb, ha a cél a végső metszett fa előrejelzési pontossága.

Végrehajtás a semmiből

Séta végig a döntésfa-építő algoritmust, annak minden apró részletével. A döntési fa felépítéséhez meg kell hoznunk egy kezdeti döntést az adatkészletről, hogy diktáljuk, melyik szolgáltatás használható az adatok felosztására. Ennek meghatározásához minden olyan tulajdonságot meg kell próbálnunk, és meg kell mérnünk, hogy melyik megosztás adja a legjobb eredményt. Ezt követően az adatkészletet alcsoportokra osztjuk. Az alkészletek ezután végighaladnak az első döntési csomópont ágain. Ha az ágak adatai ugyanaz az osztály, akkor megfelelően osztályoztuk őket, és nem kell folytatnunk a felosztásukat. Ha az adatok nem azonosak, akkor meg kell ismételnünk a felosztási folyamatot ezen az alkészleten. A részhalmaz megosztására vonatkozó döntés ugyanúgy történik, mint az eredeti adatkészletnél, és ezt a folyamatot addig ismételjük, amíg az összes adatot besorozzuk.

Hogyan oszthatjuk fel az adatkészletünket? Ennek a rendetlenségnek az egyik módja az információ mérése. Az információelmélet felhasználásával mérhetjük az információkat a felosztás előtt és után. Az információk megosztása előtti és utáni változása az információgyűjtés. Amikor tudjuk, hogyan kell kiszámítani az információszerzést, akkor minden elemre feloszthatjuk adatainkat, hogy megnézhessük, melyik megoszlás adja a legnagyobb információhozadást. A legjobb választás a legnagyobb információszerzési nyereség.

Az információgyarapodás kiszámításához használhatjuk a Shannon entrópiát, amely osztályunk minden lehetséges értékére vonatkozó információ várható értéke. Nézzük meg a Python-kódot:

Mint láthatja, először kiszámoljuk az adatbázisban szereplő példányszámot. Ezután létrehozunk egy szótárt, amelynek kulcsai az utolsó oszlopban szereplő értékek. Ha egy kulccsal korábban nem találkoztak, akkor létrejön egy. Minden kulcsnál nyomon követjük, hogy hányszor fordul elő ez a címke. Végül az összes különféle címke gyakoriságát használjuk annak kiszámításához. Ezt a valószínűséget használják a Shannon entrópia kiszámításához, és ezt összes címkére összegezzük.

Miután kitaláltunk egy módszert az adatkészlet entrópiájának mérésére, meg kell osztani az adatkészletet, meg kell mérni az entrópiát a split halmazokon, és meg kell vizsgálnunk, hogy a felosztás volt-e a helyes dolog. Íme a kód erre:

Ez a kód 3 bemenetet igényel: az adatokat meg kell osztani, a megosztandó funkciót és a visszatérő szolgáltatás értékét. Minden alkalommal elején új listát állítunk össze, mivel ezt a funkciót többször felhívjuk ugyanazon adatkészletre, és nem akarjuk, hogy az eredeti adatkészlet módosuljon. Adatkészletünk egy listák listája; amikor a lista minden elemére iterálunk, és ha az tartalmazza a keresett értéket, akkor hozzáadjuk az újonnan létrehozott listához. Az if állításon belül kivágtuk azt a funkciót, amelyet felosztottunk.

Most összekapcsoljuk a 2 funkciót: a ShannonEntropy és a splitDataset, hogy átjárhassuk az adatkészletet, és eldöntöttük, melyik funkció a legjobb a felosztáshoz.

Vizsgáljuk meg gyorsan a kódot:

  • Kiszámoljuk a teljes adatkészlet Shannon entrópiáját, mielőtt bármilyen felosztás megtörténne, és hozzárendeljük az értéket a baseEntropy változóhoz.
  • Az első a hurok hurkok számára az összes adatunkban. Listamegértésekkel készítünk egy listát (featList) az összes i. Tételből vagy az adatokban szereplő összes lehetséges értékből.
  • Ezután létrehozunk egy új készletet egy listából az egyedi értékek kinyerése érdekében (uniqueVals).
  • Ezután átvizsgáljuk ennek a szolgáltatásnak az összes egyedi értékét, és megosztjuk az egyes jellemzőkre vonatkozó adatokat (subData). Az új entrópiát kiszámítják (newEntropy) és összegzik az adott szolgáltatás összes egyedi értékére. Az információszerzés (infoGain) az entrópia csökkenése (baseEntropy - newEntropy).
  • Végül összehasonlítottuk az információszerzést az összes szolgáltatás között, és visszaadjuk a megosztandó legjobb szolgáltatás indexét (bestFeature).

Most, hogy meg tudjuk mérni, hogy az adatkészlet milyen szervezett és hogyan oszthatjuk fel az adatokat, itt az ideje, hogy mindezt összerakjuk, és felépítsük a döntési fát. Egy adatkészletből a felosztásra kerülő legjobb tulajdonság alapján osztottuk fel. A felosztás után az adatok áthaladnak a fa ágain egy másik csomóponthoz. Ez a csomópont ezután ismét megosztja az adatokat. Ezt a rekurziót fogjuk használni.

Csak a következő feltételek mellett állhatunk le: (1) elfogynak az attribútumok, amelyeket fel kell osztani, vagy (2) az ág összes példánya azonos osztály. Ha az összes példány azonos osztályú, akkor létrehozunk egy levélcsomót. Bármely adat, amely eléri ezt a levélcsomót, a levélcsomópont osztályához tartozik.

Íme a kód a döntési fák felépítéséhez:

Kódunk 2 bemeneti adatot vesz fel: az adatokat és a címkék listáját:

  • Először összeállítunk egy listát az adatkészlet összes osztálycímkéjéről, és ezt az osztálylistát hívjuk. Az első leállítási feltétel az, hogy ha az összes osztálycímke azonos, akkor ezt a címkét visszaadjuk. A második leállítási feltétel abban az esetben fordul elő, ha nincs több megosztandó funkció. Ha nem felel meg a megállási feltételeknek, akkor a selectBestFeatureToSplit függvényt használjuk a legjobb szolgáltatás kiválasztására.
  • A fa létrehozásához szótárban tároljuk (myTree). Ezután megkapjuk az összes egyedi értéket a kiválasztott szolgáltatásunk (bestFeat) adatkészletéből. Az egyedi értékkód halmazokat (uniqueVals) használ.
  • Végül megismételjük a kiválasztott szolgáltatás minden egyedi értékét, és rekurzívan hívjuk a createTree () -ot az adatkészlet minden egyes felosztására. Ezt az értéket beillesztjük a myTree szótárba, tehát sok beágyazott szótár végzi a fát.

Végrehajtás a Scikit-Learn segítségével

Most, hogy tudjuk, hogyan kell az algoritmust a semmiből megvalósítani, használjuk a scikit-learning eszközt. Különösen a DecisionTreeClassifier osztályt fogjuk használni. Az írisz adatkészlettel együtt először importáljuk az adatokat, és felosztjuk egy képzési és teszt részre. Ezután felépítünk egy modellt, amely az alapértelmezett beállítást használja a fa teljes kifejlesztéséhez (a fa növekedéséig, amíg az összes levél tiszta lesz). Rögzítjük a random_state-t a fában, amelyet belsőleg a kötés megszakításához használunk:

A modell futtatásakor 95% -os tesztkészlet-pontosságot kell kapnunk, ami azt jelenti, hogy a modell helyesen megjósolta az osztályt a teszt-adatkészletben szereplő minták 95% -ához.

Erősségeit és gyengeségeit

A döntési fák alkalmazásának fő előnye, hogy intuitív módon nagyon könnyen megmagyarázhatók. Szorosan tükrözik az emberi döntéshozatalt, összehasonlítva más regressziós és osztályozási megközelítésekkel. Grafikusan megjeleníthetők, és könnyen kezelhetők a kvalitatív prediktorok nélkül, dummy változók létrehozása nélkül.

Egy másik hatalmas előnye az, hogy az algoritmusok teljesen változatlanok az adatok méretezéséhez. Mivel az egyes szolgáltatások külön-külön kerülnek feldolgozásra, és az adatok lehetséges felosztása nem függ a méretezéstől, így nincs szükség előfeldolgozásra, például a szolgáltatások normalizálására vagy szabványosítására a döntési fa algoritmusaihoz. Különösen a döntési fák akkor működnek jól, ha olyan funkciókkal rendelkezünk, amelyek teljesen eltérő skálán vannak, vagy bináris és folyamatos jellemzők keveréke.

A döntési fák általában nem ugyanolyan szintű prediktív pontossággal rendelkeznek, mint más megközelítések, mivel nem elég robusztusak. Az adatok kis változása nagy változást okozhat a becsült fában. Még az előmetszés használatakor is túlterheltek és gyenge általánosítási teljesítményt nyújtanak. Ezért a legtöbb alkalmazásban sok döntési fa egyesítésével, olyan módszerek felhasználásával, mint a zsákolás, a véletlenszerű erdők és a fellendítés, a döntési fák prediktív teljesítménye jelentősen javulhat.

Referenciaforrások:

  • Bevezetés a statisztikai tanulásba: Gareth James, Daniela Witten, Trevor Hastie és Robert Tibshirani (2014)
  • Peter Harrington (2012) gépi tanulás akcióban (2012)
  • Bevezetés a gépi tanulásba a Python segítségével: Sarah Guido és Andreas Muller (2016)

- -

Ha élvezte ezt a darabot, akkor nagyon szeretem, ha megüt a taps gombra button, így mások megbotlik. A saját kódomat a GitHub-on, valamint az írásomat és a projekteimet a https://jameskle.com/ oldalon találhatja meg. Ön is követhet engem a Twitter-en, közvetlenül küldhet e-mailt, vagy megtalálhat a LinkedIn-en.