Döntési fa

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.^{[* 1]}^{[* 2]}^{[* 3]}
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

Megjegyzések

↑ 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ó.
↑ Ugyancsak helyesen szerepel Dr. Kovács László órajegyzet^{[halott link]} 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.”
↑ Az ID3 algoritmus angol wikipédia-oldalán is helytelenül szerepel, ld.: en:ID3 algorithm "The higher the entropy, the higher the potential to improve the classification here." Viszont a következő értekezésben már szintén helyesen: (archív) "and the attribute which has the lowest entropy is the most useful determiner"

Hivatkozások

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

Informatikaportál
Matematikaportál

[bodon-1] 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ó.

[kovacs-2] Ugyancsak helyesen szerepel Dr. Kovács László órajegyzet^{[halott link]} 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.”

[:3-3] Az ID3 algoritmus angol wikipédia-oldalán is helytelenül szerepel, ld.: en:ID3 algorithm "The higher the entropy, the higher the potential to improve the classification here." Viszont a következő értekezésben már szintén helyesen: (archív) "and the attribute which has the lowest entropy is the most useful determiner"

[* 1]

[* 2]

[* 3]