Döntési fa

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

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

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:

• A legnagyobb entrópiájú attribútumot választja

// 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: https://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: https://web.archive.org/web/20160906085645/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 p_i az i-edik attribútum érték relatív gyakorisága az n csúcshoz tartozó mintában, és p_ij a magyarázott változó j-edik értékének relatív gyakorisága a c_i 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

• operációkutatás: a döntéselemzések során segít megtalálni a legkedvezőbb stratégiát, egy cél eléréséhez.
• adatbányászat: nagy méretű adathalmazokra is hatékonyan felépíthető.
• mesterséges intelligencia

Fordítás

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. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• Dr. Bodon Ferenc - Adatbányászati algoritmusok
• Sántáné Tót Edit: Szakértői rendszerek
• Dr. Tick József - Szoftvertechnológia előadás