bélyegkép|jobbra|300px|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ó.Ugyancsak helyesen szerepel Dr. Kovács László órajegyzet 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" 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:
„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 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
Hivatkozások
Fordítás
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
Kategória:Számítógép-tudomány Kategória:Gráfelmélet