Mi az a döntési fa?

Mi az a döntési fa?

A döntési fa egy hasznos gépi tanulási algoritmus, amelyet regressziós és osztályozási feladatokhoz egyaránt használnak. A „döntési fa” elnevezés onnan ered, hogy az algoritmus egyre kisebb részekre osztja az adathalmazt, amíg az adatokat egyedi példányokra osztják fel, amelyeket aztán osztályoznak. Ha vizualizálná az algoritmus eredményeit, a kategóriák felosztása fára és sok levélre emlékeztetne.

Ez a döntési fa gyors definíciója, de vessünk egy pillantást a döntési fák működésére. Ha jobban megérti a döntési fák működését, valamint használati eseteiket, akkor könnyebben megtudhatja, mikor használja őket gépi tanulási projektjei során.

A döntési fa formátuma

A döntési fa az olyan, mint egy folyamatábra. A folyamatábra használatához a diagram kezdőpontjától vagy gyökerétől kell kezdenie, majd az adott kezdő csomópont szűrési feltételeinek megválaszolása alapján át kell lépnie a következő lehetséges csomópontok egyikére. Ezt a folyamatot addig ismételjük, amíg el nem érjük a végét.

A döntési fák lényegében azonos módon működnek, a fa minden belső csomópontja valamilyen teszt/szűrési kritérium. A külső csomópontok, a fa végpontjai a kérdéses adatpont címkéi, és ezeket „leveleknek” nevezik. A belső csomópontoktól a következő csomóponthoz vezető ágak jellemzők vagy jellemzők konjunkciói. Az adatpontok osztályozására használt szabályok azok az útvonalak, amelyek a gyökértől a levelekig futnak.

Algoritmusok döntési fákhoz

A döntési fák algoritmikus megközelítésen működnek, amely az adatkészletet különböző kritériumok alapján egyedi adatpontokra bontja. Ezeket a felosztásokat különböző változókkal vagy az adatkészlet különböző jellemzőivel hajtják végre. Például, ha a cél annak meghatározása, hogy a bemeneti jellemzők leírnak-e egy kutyát vagy macskát, akkor az adatok felosztása olyan változók lehetnek, mint a „karmok” és „ugatás”.

Tehát milyen algoritmusokat használnak az adatok tényleges felosztására ágakra és levelekre? Különféle módszerek használhatók egy fa feldarabolására, de a legelterjedtebb felosztási módszer valószínűleg a „rekurzív bináris felosztás”. Ennek a felosztási módszernek a végrehajtásakor a folyamat a gyökérnél kezdődik, és az adatkészletben lévő jellemzők száma a lehetséges felosztások számát jelenti. Egy függvényt használnak annak meghatározására, hogy minden lehetséges felosztás mekkora pontosságba kerül, és a felosztás a legkevesebb pontosságot feláldozó kritériumok alapján történik. Ezt a folyamatot rekurzív módon hajtják végre, és az alcsoportokat ugyanazzal az általános stratégiával alakítják ki.

Azért, hogy határozza meg a felosztás költségét, költségfüggvényt használnak. A regressziós és osztályozási feladatokhoz más költségfüggvényt használnak. Mindkét költségfüggvény célja annak meghatározása, hogy mely ágak rendelkeznek a leginkább hasonló válaszértékekkel, vagy a leghomogénebb ágakkal. Vegyük fontolóra, hogy azt szeretnénk, hogy egy bizonyos osztály tesztadatai bizonyos útvonalakat kövessenek, és ennek intuitív értelme van.

A rekurzív bináris felosztás regressziós költségfüggvénye szempontjából a költség kiszámításához használt algoritmus a következő:

sum(y – jóslat)^2

Az adatpontok egy adott csoportjára vonatkozó előrejelzés az adott csoportra vonatkozó betanítási adatok válaszainak átlaga. Az összes adatpontot a költségfüggvényen futtatják, hogy meghatározzák az összes lehetséges felosztás költségét, és a legalacsonyabb költségű felosztás kerül kiválasztásra.

Az osztályozás költségfüggvényét illetően a függvény a következő:

G = összeg(pk * (1 – pk))

Ez a Gini-pontszám, és egy felosztás hatékonyságának mérése az alapján, hogy hány különböző osztály van a felosztás eredményeként kapott csoportokban. Más szóval, számszerűsíti, hogy a csoportok mennyire vegyesek a felosztás után. Az optimális felosztás az, ha a felosztásból származó összes csoport csak egy osztály bemeneteiből áll. Ha létrehoztunk egy optimális felosztást, a „pk” értéke 0 vagy 1 lesz, és G egyenlő lesz nullával. Lehetséges, hogy kitalálhatja, hogy a legrosszabb eset felosztása az, ahol a felosztásban lévő osztályok 50-50 reprezentációja van, bináris osztályozás esetén. Ebben az esetben a „pk” érték 0.5 és G is 0.5 lenne.

A felosztási folyamat akkor fejeződik be, amikor az összes adatpontot levéllé alakították és osztályozták. Érdemes azonban korán megállítani a fa növekedését. A nagy, összetett fák hajlamosak a túlillesztésre, de ez ellen többféle módszer is alkalmazható. A túlillesztés csökkentésének egyik módja az, hogy meghatározza a levél létrehozásához felhasználandó adatpontok minimális számát. Egy másik módszer a túlillesztés szabályozására a fának egy bizonyos maximális mélységre való korlátozása, amely szabályozza, hogy mennyi ideig nyúlhat az út a gyökértől a levélig.

Egy másik folyamat a döntési fák létrehozásában metszés van. A metszés segíthet a döntési fa teljesítményének növelésében azáltal, hogy lecsupaszítja azokat az ágakat, amelyek olyan jellemzőket tartalmaznak, amelyeknek kicsi a prediktív ereje/kis jelentősége van a modell számára. Ily módon csökken a fa összetettsége, kevésbé valószínű, hogy túlilleszkedik, és nő a modell prediktív használhatósága.

A metszés során a folyamat kezdődhet akár a fa tetején, akár a fa alján. A metszés legegyszerűbb módja azonban az, ha a levelekkel kezdi, és megpróbálja eldobni azt a csomópontot, amely a levelen belül a leggyakoribb osztályt tartalmazza. Ha a modell pontossága ennek során nem romlik, akkor a változás megmarad. Léteznek más technikák is a metszés végrehajtására, de a fent leírt módszer – csökkentett hibás metszés – valószínűleg a leggyakoribb módszer a döntési fa metszésére.

Megfontolások a döntési fák használatához

Döntési fák gyakran hasznosak amikor az osztályozást el kell végezni, de a számítási idő jelentős korlát. A döntési fák világossá tehetik, hogy a kiválasztott adatkészletek mely jellemzői rendelkeznek a legnagyobb előrejelző erővel. Ezenkívül sok olyan gépi tanulási algoritmussal ellentétben, ahol az adatok osztályozására használt szabályok nehezen értelmezhetők, a döntési fák értelmezhető szabályokat tudnak előállítani. A döntési fák is képesek kategorikus és folytonos változókat egyaránt felhasználni, ami azt jelenti, hogy kevesebb előfeldolgozásra van szükség, mint azokhoz az algoritmusokhoz, amelyek csak egy ilyen változótípust képesek kezelni.

A döntési fák általában nem teljesítenek túl jól, ha folytonos attribútumok értékeinek meghatározására használják őket. A döntési fák másik korlátja, hogy osztályozáskor, ha kevés a tanítási példa, de sok az osztály, a döntési fa pontatlan.