A valószínűségi fa tipikusan statisztikai megközelítése a problémáknak. Építünk egy modellt, ismerjük az eloszlásokat és az ezeknek megfelelő valószínűségeket. De mi van , ha ez nem igaz? Ha csak megfigyeléseink vannak, akkor ismerjük, hogy mi volt a bemenet, és mi lett az eredmény de az utat, a valószínűségi fát nem. Ekkor megpróbálhatjuk az egész folyamatot megfordítani és a megfigyelésekből kialakítani a fánkat. Ez lesz a döntési fa.
A döntési fa csúcsai döntési helyzetek Pl: X tulajdonság értéke nagyobb mint Y állandó. Míg az élek válaszok pl: Igen X nagyobb. Döntési fák készítésére több algoritmust is kidolgoztak, mi ezek közül a CART algoritmust fogjuk részletesebben megvizsgálni. Azért ezt, mert a jelenlegi scikit-learn megvalósítás ezen alapul. A CART a Classification And Regression Trees kifejezés rövidítése és az eljárást 1984-ben publikálta Leo Breiman. A poszt további része a már megszokott formát ölti: először egy kisebb tesztadatsort tárgyalunk, majd átnézzük a számítást kézzel, végül pedig egy naiv Python megvalósítást készítünk.
Teszt adatok
A következő pontban részletezett kézi számításhoz értelemszerűen szükségünk van egy kicsi, jól áttekinthető példa adatsorra. Ez a jelen esetben a következő lesz:
| Sorszám | Légnedvesség (%) | Szélerősség (km/óra) | Esni fog 2 órán belül |
| 1 | 5,1 | 3,5 | Igen |
| 2 | 4,7 | 3,2 | Nem |
| 3 | 4,6 | 1,5 | Igen |
| 4 | 5 | 3,6 | Nem |
| 5 | 3,4 | 0,2 | Igen |
| 6 | 1,5 | 0,1 | Igen |
| 7 | 1,6 | 0,2 | Nem |
| 8 | 1,5 | 0,4 | Igen |
| 9 | 3,9 | 0,4 | Igen |
| 10 | 1,5 | 0,2 | Nem |
A fenti táblázatból a szélerősség és a légnedvesség lesz a megfigyelt független tulajdonságok és az “esni fog 2 órán belül” a függő tulajdonság.
CART
Mint említettem a döntési fa csúcsai egyszerű igen-nem döntési helyzetek adott tulajdonságokra vonatkozólag. Például: a légnedvesség nagyobb mint 3,4? Első ránézésre egyből 20 lehetséges csúcsot tudunk kialakítani: minden egyes megfigyelés minden egyes tulajdonságára egyet-egyet. Ha nagyon akarnánk, akkor minden egyes csúcs felhasználásával is létrehozhatnánk egy fát. Ez egy valódi döntési fa lenne? Igen. Viszont gondolom nem lep meg senkit, ha azt mondom, hogy ez a fa a túlillesztés problémájától szenvedne. Gondolom az is természetes intuíció, hogy nem minden fa modell egyformán jó: az ami kevesebb csúccsal ábrázolja ugyanazt jobb, mivel gyorsabb és könnyebben megérthető. Ezek után az algoritmus célja gondolom már világos: megtalálni azt a döntési fát, ami a legáltalánosabban a legkevesebb csúcsból épül fel.
Hogy ezt megtehessük, valahogy rangsorolni kell a lehetséges csúcsainkat. A CART erre a Gini indexet használja:
Ahol:
- G — a Ginit index
- c — a kimeneti osztályok száma, a fenti példa esetén 2: “esik” és “nem esik”
— az osztály valószínűsége az adott csúcs esetén
Ez talán elsőre nem egyértelmű, de gyorsan kiszámítjuk a gyökér csúcs esetére, és egyből világosabb lesz: A gyökér csúcsban ugye minden megfigyelés benne van. Összesen 10 megfigyelés, amiből 6 db. “Igen esik”, és 4 db “Nem esik”. Így a gyökér Gini indexe:
Mit is jelent ez a Gini index? Számszerűsíti a megfigyelések hasonlóságát. Minél több egyforma kimenetű megfigyelés van a csúcshoz tartozó megfigyelések között, a Gini index annál kisebb. A minimum 0 (amikor csak egyforma megfigyelések vannak a csoportban). A maximuma két kimeneti osztály esetén 1/2 (ami semmiben nem segít nekünk a csúcs meghatározásában, mert egyforma arányban található meg benne az összes kimeneti osztály). Ennek megfelelően ez egy minimalizációs probléma.
Most nézzük mi történik, ha a gyökér csúcsnak azt az állítás tesszük, hogy: a szélerősség nagyobb mint 3,5 km/óra. Ez két részre osztja a megfigyeléseket és mindkettő esetén ki tudjuk számolni a Gini indexet. Lássuk:
Rendben, a csúcs által létrejött két csoport, aminek ismerjük a Gini indexét. Azt is tudjuk, hogy minimalizálni szeretnénk ezeket. Innen nem nagy logikai ugrással eljuthatunk oda, hogy egy csúcs jósága mérhető, ha átlagoljuk a két létrehozott csoport indexét. Ami a fenti esetben:
Ezzel csak az a probléma, hogy a sima átlagolás során a kisebb csoportokat létrehozó csúcsok átlaga mindig jobb lesz. Nem meglepő módon könnyebb kisebb homogén csoportokat kialakítani ,mint nagyobbakat. A fenti példa is jól szemlélteti ezt az esetet. Ha az egyik csoportban egy elem van, annak a Gini indexe mindig 0. A megoldás kézenfekvő: súlyozott átlagot számoljunk, ahol a súlyok a csoportok egyedszámai. Tehát a végső megoldás:
Innen már gondolom egyértelmű mit kell tennünk az optimális fa megtalálásáért: Kiszámítjuk minden egyes lehetséges csúcsra a Gini indexet és azt választjuk, amelyiké a legkisebb. Értelemszerűen ez csak egy darab csúcs lesz, de az adott ágban a legoptimálisabb. A teljes fa elkészítéséhez csak ezt a lépést kell ismételnünk addig, amíg minden levél homogén nem lesz. Csak van ezzel egy probléma. Ha az adatok nem jól elválaszthatók, akkor előfordulhat, hogy a fánknak sok olyan levele lesz, amiben egyetlen megfigyelés lesz. Ez pedig túlillesztéshez vezet. Ezért a gyakorlatban a fenti algoritmust még ki szokták egészíteni néhány paraméterrel:
- max_depth — maximum mennyi csúcs érintésével juthatunk el egy levélhez.
- min_sample_leaf — minimum mennyi megfigyelés legyen egy levélben.
- min_sample_split — mi az a minimális megfigyelésszám, amit tovább csúcsokkal vágni lehet.
A fenti algoritmus sebessége:
Ahol:
— a tulajdonságok száma, a fenti példa esetén 2
— mintanagyság, a fenti példa esetén 10
Ebből egyértelműen következik, hogy a tulajdonságok száma egyenesen arányos az futási sebességge. Ha lassú, gondolkozzunk el azon, hogy dobjunk néhányat, vagy végezzünk főkomponens analízist.
Vegyünk még egyvalamit észre: a tulajdonságokat nem kell skálázni. A Gini index számára csak az a fontos, hogy a két oldalra milyen és mennyi függő változó kerül.
Naiv Python megvalósítás
Először készítsük el a példa adatokat:
x = np.array([
[5.1, 4.7, 4.6, 5.0, 3.4, 1.5, 1.6, 1.5, 3.9, 1.5],
[3.5, 3.2, 1.5, 3.6, 0.2, 0.2, 0.2, 0.4, 0.4, 0.2]
]).T
tulajdonsag_nev = ['Légnedvesség', 'Szélerősség']
y = np.array([1, 0, 1, 0, 1, 1, 0, 1, 1, 0])Most egy függvény a Gini index számítására:
# Gini index
def gini_index(data):
# megszámoljuk az egyes függő tulajdonságokat
_, p = np.unique(data, return_counts=True)
# Gini index számítás
return 1.0 - sum( (pi/len(data))**2 for pi in p )Majd egy másikat az optimális csúcs megtalálására:
def optimaliscsucs(x, y):
# csucsok gini értéke
ginis = []
for idx in range(x.shape[1]):
megfigyelesek = x[:, idx]
# a tulajdonság egyedi értékei
csucs_ertekek = sorted(list(set(megfigyelesek)))
for cse in csucs_ertekek:
# bal oldali függő tulajdonságok
bal_oldal = y[np.where(megfigyelesek > cse)]
# jobb oldali függő tulajdonságok
jobb_oldal = y[np.where(megfigyelesek <= cse)]
# gini
gini = (
(
len(bal_oldal) * gini_index(bal_oldal) +
len(jobb_oldal) * gini_index(jobb_oldal)
) / len(y)
)
ginis.append((gini, idx, cse))
# legjobb gini az agon
return sorted(ginis)[0]
Végül futtassuk a gyökérben, hogy megtaláljuk mi legyen az első vágás:
gini_ertek, tulajdonsag_index, tulajdonsag_ertek = optimaliscsucs(x,y)
print(f"Gyökér optimális csúcsa {tulajdonsag_nev[tulajdonsag_index]} > {tulajdonsag_ertek}")Ami eredménye: Gyökér optimális csúcsa Szélerősség > 3,5
A teljes fa elkészítéséhez most már csak írnunk kellene egy osztályt, amiben a csúcsokat tároljuk, és egy függvényt, ami végig lépked az ágakon. Ezt most én kihagyom. Triviális, és nem is segítene sokban a döntési fa megértésében.
Végezetül
Fentebb megismertünk egy egyszerű, de mégis rugalmas modellt. Sajnos van vele néhány nem tárgyalt probléma: a modell konkrét megfigyelések alapján határozza meg a csúcsokat. Ez sajnos azzal jár, hogy egyrészt mindenféleképp diszkrét modell, még akkor is ha a változóink folytonosak. Másrészt újabb megfigyelések esetén a fa drasztikus változásokon tud átmenni. Magyarul a modellünk instabil. A következő bejegyzésben megnézzük egy olyan eljárást ami megpróbálja megoldani ezt a problémát, a Véletlenszerű erdőt (Random Forest).
Irodalom
- deepankar: Decision Tree with CART Algorithm
- Scikit-learn dokumntáció: Decision Trees
Sajó Zsolt Attila 
“Döntési fa” bejegyzéshez 2 hozzászólás