Döntési fa

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ámLégnedvesség (%)Szélerősség (km/óra)Esni fog 2 órán belül
15,13,5Igen
24,73,2Nem
34,61,5Igen
453,6Nem
53,40,2Igen
61,50,1Igen
71,60,2Nem
81,50,4Igen
93,90,4Igen
101,50,2Nem
Teszt adatok

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:

G = 1-\sum_{i=1}^c P_i^2

Ahol:

  • G — a Ginit index
  • c — a kimeneti osztályok száma, a fenti példa esetén 2: “esik” és “nem esik”
  • P_i — 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:

G = 1-\left( (6/10)^2 + (4/10)^2  \right) = 0,48

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:

G_{cs}' = \frac{G_b+G_j}{2} = \frac{0,4\dot{4}+0}{2} = 0,2\dot{2}

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:

G_{cs} = \frac{m_b \cdot G_b+ m_j \cdot G_j}{n} = \frac{9 \cdot 0,4\dot{4}+ 1 \cdot 0}{10} = 0,4

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:

O\left(n_{tulajdonsag}\cdot n_{minta}^2 \cdot \log(n_{minta}) \right)

Ahol:

  • n_{tulajdonsag} — a tulajdonságok száma, a fenti példa esetén 2
  • n_{minta} — 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

Hírdetés

Döntési fa” bejegyzéshez 2 hozzászólás

Vélemény, hozzászólás?

Adatok megadása vagy bejelentkezés valamelyik ikonnal:

WordPress.com Logo

Hozzászólhat a WordPress.com felhasználói fiók használatával. Kilépés /  Módosítás )

Twitter kép

Hozzászólhat a Twitter felhasználói fiók használatával. Kilépés /  Módosítás )

Facebook kép

Hozzászólhat a Facebook felhasználói fiók használatával. Kilépés /  Módosítás )

Kapcsolódás: %s