Skip navigation

Döntési fák

Előismeret

Annak szemléltetésére, hogy hogyan osztályozhatunk egy döntési fával, tekintsük az előző szakaszban leírt gerinces osztályozási feladat egy egyszerűbb változatát. Ahelyett, hogy a gerinceseket öt különböző fajba osztályoznánk, rendeljük őket két kategóriába úgy, mint emlősök és nem-emlősök.

Tegyük fel, hogy egy új fajt fedeznek fel a tudósok. Hogyan tudjuk megmondani, hogy ez az új faj emlős vagy nem emlős? Egy lehetséges megközelítés, hogy egy sor kérdést teszünk fel a faj jellemzőiről. Az első kérdés, amit feltehetünk az, hogy a faj hideg- vagy melegvérű. Ha hidegvérűnek bizonyul, akkor biztosan nem lehet emlős, egyébként madár vagy emlős. Az utóbbi esetben fel kell tenni a következő kérdést: a faj nőstényei elevenen szülik-e az utódokat? Határozottan emlősök az elevenszülők, míg a nem elevenszülők valószínűleg nem-emlősök (kivéve a tojásrakó emlősöket, mint a kacsacsőrű emlős és a tüskés hangyász).

Az előző példa azt szemlélteti, hogy hogyan tudunk megoldani úgy egy osztályozási feladatot, hogy gondosan kidolgozott kérdések egy sorozatát tesszük fel a tesztrekord attribútumaira vonatkozóan. Minden alkalommal, amikor választ kapunk, egy következő kérdést teszünk fel addig, amíg következtetésre nem jutunk a rekord osztálycímkéjéről. A kérdések sorozata és a lehetséges válaszok egy olyan döntési fa alakjába szervezhetőek, amely egy csúcsokból és irányított élekből álló hierarchikus struktúra. A 4.4. ábra az emlős osztályozási feladat döntési fáját mutatja. A fának háromféle csúcsa van:

  • Gyökér csúcs (root node), amelynek nincs bemenő éle és nulla vagy több kimenő éle van.

  • Belső csúcsok (internal nodes), amelyek mindegyikének pontosan egy bemenő éle és kettő vagy több kimenő éle van.

  • Levél- vagy terminális csúcsok (leaf, terminal nodes) amelyek mindegyikének pontosan egy bemenő éle van és nincs kimenő éle.

Az emlős osztályozási feladat döntési fája
Az emlős osztályozási feladat döntési fája

Egy döntési fában minden levélcsúcshoz egy osztálycímkét rendelünk. A nemterminális (non-terminal) csúcsok, amelyek magukban foglalják a gyökér csúcsot és a belső csúcsokat, attribútum tesztfeltételeket tartalmaznak azért, hogy elkülönítsék a különböző tulajdonságokkal rendelkező rekordokat. Például 4.4. ábrán látható gyökér csúcs a Testhőmérséklet attribútumot használja arra, hogy elkülönítse a melegvérű és a hidegvérű gerinceseket. Mivel minden hidegvérű gerinces nem-emlős, egy Nem-emlős címkéjű levélcsúcsot hozunk létre, mint a gyökér csúcs jobboldali gyerekét. Ha a gerinces melegvérű, akkor egy következő attribútumot, az Elevenszülőt, használjuk az emlősök más melegvérű élőlényektől való megkülönböztetésére, amelyek többnyire a madarak.

Amint felépítettünk egy döntési fát, egy tesztrekord osztályozása már nagyon egyszerű. A gyökér csúcsból indulva alkalmazzuk a tesztfeltételt a rekordra, majd kövessük a teszt kimenetelének megfelelő ágat. Ez vagy egy másik belső csúcshoz vezet minket, amelynél egy új tesztfeltételt alkalmazhatunk, vagy pedig egy levélcsúcshoz. A levélcsúcshoz tartozó osztálycímkét rendeljük a rekordhoz. Szemléltetésként 4.5. ábrán bejelöltük azt az utat a döntési fán, amely egy flamingó osztálycímkéjének az előrejelzésére használható. Az út egy Nem-emlős címkéjű levélcsúcsnál ér véget.

Egy címkézetlen gerinces osztályozása. A szaggatott vonalak a címkézetlen gerincesre alkalmazott különböző attribútum tesztfeltételek kimenetelét jelölik. A gerincest végül a Nem-emlős osztályhoz rendeljük.
Egy címkézetlen gerinces osztályozása. A szaggatott vonalak a címkézetlen gerincesre alkalmazott különböző attribútum tesztfeltételek kimenetelét jelölik. A gerincest végül a Nem-emlős osztályhoz rendeljük.

[forrás: Bevezetés az adatbányászatba]