Döntési fa

A Wikipédiából, a szabad enciklopédiából
Döntési fa ábra

A döntési fa egy olyan, a döntéshozatalban használt grafikus modell, amit az optimális tevékenység határoz meg olyan esetekben, amikor több választási lehetőség is rendelkezésre áll, és a kimeneteik bizonytalanok. A diagram arról kapta a nevét, hogy egy faágra hasonlít. A döntési fák matematikailag gráfok.

Leírása[szerkesztés | forrásszöveg szerkesztése]

A döntési fa a különböző döntési lehetőségeket ábrázolja, az esetleges következményeket, esélyeket, hasznosságot és erőforrásokat figyelembe véve, attól függően, hogy mire használják. A döntési fa egy olyan faszerkezet, amelyben minden belső csúcs egy értékre vonatkozó ellenőrzést jelöl, a csúcsból kivezető minden él pedig az ellenőrzés egy-egy kimenetének feleltethető meg, így lehetővé téve, hogy fa formában ábrázoljunk függvényeket. Könnyen érthető, magyarázható; inkább értékek, mint függvények szerepelnek benne. Az induktív tanulási módszerek közé tartozik, és mindig csak egy eredményt ad magyarázattal, akkor is, ha több legjobb megoldás lenne. Érzékeny a tanulóhalmaz hibáira, és a további tanuláshoz újabb döntési fát kell generálni. Kombinálható más módszerekkel, így javítani lehet a hibáin.

Döntési fát előállító algoritmusok[szerkesztés | forrásszöveg szerkesztése]

A döntési fa előállítására több eljárást is kidolgoztak. Ezek mind rekurzív algoritmusok, amik egy kérdésre adott válasz szerint szétbontják a tanulóhalmazt. A kérdéseket úgy teszik fel, hogy a kisebb részek homogénebbek legyenek a magyarázandó változó szempontjából, mint az egész.

Több kritériumot is megadnak a rekurzió leállítására az egyes ágakon:

  • Nincs értelme tovább osztani a csomópont elemeit:
  • A csomóponthoz tartozó elemek homogének a vizsgált tulajdonságokra
  • Elfogytak a csomóponthoz tartozó elemek
  • Elfogytak az osztályozó attribútumok
Ekkor a csomóponthoz tartozó elemek típusáról szavazás dönt, vagy feljegyzik az ide tartozó elemek osztályát
  • Az adott ág elért egy bizonyos mélységet

Három nagy algoritmuscsalád létezik a döntési fák generálására:

  • ID3 Interactive Dichotomizer 3
  • CART Classification and Regression Trees
  • CHAID Chi-squared Automatic Interaction Detection

Az ID3 családba tartozó algoritmus:

// Dr. Bodon Ferenc - Adatbányászati algoritmusok című írásának 143. oldalán ez áll "Az ID3 az Y attribútum szerinti klasszifikálásakor olyan X attribútum értékei szerint ágazik szét, amelyre I (Y, X ) maximális, azaz H (Y |X ) minimális." Ez gyakorlatilag azt mondja, hogy az ID3 a legkisebb entrópiájú attribútumot választja. Ez abszolút logikus, hiszen az entrópia egy valószínűségi változó értékével kapcsolatos bizonytalanságot fejezi ki, és a döntési fánál a legnagyobb bizonyosság alapján választunk. Ha van egy megfigyelt X esemény, akkor ez a bizonytalanság annál kisebb, minél nagyobb az I(Y,X) kölcsönös információ. Ugyanúgy helyesen szerepel Dr. Kovács László http://www.iit.uni-miskolc.hu/iitweb/export/sites/default/department/labs/iit-szolgaltatasok/www-db/Tantargyak/OLAP_DM_MSc/ora_13.pdf előadásanyagában az 5. oldal második diáján, hogy a cél "a legkisebb entrópiát adó attribútum kiválasztása". Viszont az ID3 algoritmus angol wiki oldalán is helytelenül szerepel: http://en.wikipedia.org/wiki/ID3_algorithm "The higher the entropy, the higher the potential to improve the classification here." Viszont ebben az értekezésben már szintén helyesen: http://www.soc.napier.ac.uk/~peter/vldb/dm/node11.html "and the attribute which has the lowest entropy is the most useful determiner"

  • Csak magukra az attribútumokra tesztel, és nem attribútumok lineáris kombinációira
  • Nominális attribútumra annyi felé ágazik, ahány értéket az attribútum felvehet
  • Nagy méretű fát épít
  • Ha egymás után kevés attribútumot tesztel, akkor lehet, hogy az attribútumok egy függvénye az igazi kritérium

A CART családba tartozó algoritmus:

  • A Gini-indexet használja:
\mathrm{Gini}(n)=\sum _{i=1}^k p_i \left ( 1-\sum_{j=1}^l p_{ij}^2 \right )
„ahol pi az i-edik attribútum érték relatív gyakorisága az n csúcshoz tartozó mintában, és pij a magyarázott változó j-edik értékének relatív gyakorisága a ci gyerekhez tartozó almintában.” Azaz mindig a lehető legnagyobb homogén osztályt választja le.
  • Az attribútumok lineáris kombinációit is teszteli
  • Nagy bináris fát épít
  • Az intervallum skálán mért magyarázandó változó szórásának csökkenését is figyeli

A CHAID családba tartozó algoritmus:

  • A khi-tesztet használja
  • Csak magukra az attribútumokra tesztel
  • Intervallum skálán mért magyarázott változó esetén F-tesztet használ
  • Csak addig növeli a bináris fát, amíg a legjobb szétvágás szignifikanciája meghalad egy bizonyos szintet
  • Ha egymás után kevés attribútumot tesztel, akkor lehet, hogy az attribútumok egy függvénye az igazi kritérium

Az ID3 fák csak osztályozásra, a többi fa osztályozásra és előrejelzésre is használható.

A fák hajlamosak túltanulni a tanulóhalmazt, vagyis kitűnően működni a tanulóhalmazon, de a teszthalmazon kevésbé. Hibás adatokból hibás ágak lesznek, ezért a terebélyes döntési fákat a teszthalmaz segítségével meg szokták metszeni.

Felhasználási területei[szerkesztés | forrásszöveg szerkesztése]

Fordítás[szerkesztés | forrásszöveg szerkesztése]

Ez a szócikk részben vagy egészben a Decision tree című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.

Forrás[szerkesztés | forrásszöveg szerkesztése]