Döntési fa következtetés

Döntési fa következtetés
Vissza	4. fejezet - Osztályozás:Alapfogalmak, döntési fák és modellek kiértékelése	Előre

Ebben a szakaszban a döntési fa (decision tree) osztályozót vezetjük be, ami egy egyszerű, mégis széles körben használt osztályozási módszer.

4.3.1 Hogyan működik a döntési fa

Annak szemléltetésére, hogy hogyan osztályozhatunk egy döntési fával, tekintsük az előző szakaszban leírt gerinces osztályozási feladat egy egyszerűbb változatát. Ahelyett, hogy a gerinceseket öt különböző fajba osztályoznánk, rendeljük őket két kategóriába úgy, mint emlősök és nem-emlősök.

Tegyük fel, hogy egy új fajt fedeznek fel a tudósok. Hogyan tudjuk megmondani, hogy ez az új faj emlős vagy nem emlős? Egy lehetséges megközelítés, hogy egy sor kérdést teszünk fel a faj jellemzőiről. Az első kérdés, amit feltehetünk az, hogy a faj hideg- vagy melegvérű. Ha hidegvérűnek bizonyul, akkor biztosan nem lehet emlős, egyébként madár vagy emlős. Az utóbbi esetben fel kell tenni a következő kérdést: a faj nőstényei elevenen szülik-e az utódokat? Határozottan emlősök az elevenszülők, míg a nem elevenszülők valószínűleg nem-emlősök (kivéve a tojásrakó emlősöket, mint a kacsacsőrű emlős és a tüskés hangyász).

Az előző példa azt szemlélteti, hogy hogyan tudunk megoldani úgy egy osztályozási feladatot, hogy gondosan kidolgozott kérdések egy sorozatát tesszük fel a tesztrekord attribútumaira vonatkozóan. Minden alkalommal, amikor választ kapunk, egy következő kérdést teszünk fel addig, amíg következtetésre nem jutunk a rekord osztálycímkéjéről. A kérdések sorozata és a lehetséges válaszok egy olyan döntési fa alakjába szervezhetőek, amely egy csúcsokból és irányított élekből álló hierarchikus struktúra. A 4.4. ábra az emlős osztályozási feladat döntési fáját mutatja. A fának háromféle csúcsa van:

Gyökér csúcs (root node), amelynek nincs bemenő éle és nulla vagy több kimenő éle van.
Belső csúcsok (internal nodes), amelyek mindegyikének pontosan egy bemenő éle és kettő vagy több kimenő éle van.
Levél- vagy terminális csúcsok (leaf, terminal nodes) amelyek mindegyikének pontosan egy bemenő éle van és nincs kimenő éle.

4.4. ábra - Az emlős osztályozási feladat döntési fája

Egy döntési fában minden levélcsúcshoz egy osztálycímkét rendelünk. A nemterminális (non-terminal) csúcsok, amelyek magukban foglalják a gyökér csúcsot és a belső csúcsokat, attribútum tesztfeltételeket tartalmaznak azért, hogy elkülönítsék a különböző tulajdonságokkal rendelkező rekordokat. Például 4.4. ábrán látható gyökér csúcs a Testhőmérséklet attribútumot használja arra, hogy elkülönítse a melegvérű és a hidegvérű gerinceseket. Mivel minden hidegvérű gerinces nem-emlős, egy Nem-emlős címkéjű levélcsúcsot hozunk létre, mint a gyökér csúcs jobboldali gyerekét. Ha a gerinces melegvérű, akkor egy következő attribútumot, az Elevenszülőt, használjuk az emlősök más melegvérű élőlényektől való megkülönböztetésére, amelyek többnyire a madarak.

Amint felépítettünk egy döntési fát, egy tesztrekord osztályozása már nagyon egyszerű. A gyökér csúcsból indulva alkalmazzuk a tesztfeltételt a rekordra, majd kövessük a teszt kimenetelének megfelelő ágat. Ez vagy egy másik belső csúcshoz vezet minket, amelynél egy új tesztfeltételt alkalmazhatunk, vagy pedig egy levélcsúcshoz. A levélcsúcshoz tartozó osztálycímkét rendeljük a rekordhoz. Szemléltetésként 4.5. ábrán bejelöltük azt az utat a döntési fán, amely egy flamingó osztálycímkéjének az előrejelzésére használható. Az út egy Nem-emlős címkéjű levélcsúcsnál ér véget.

4.5. ábra - Egy címkézetlen gerinces osztályozása. A szaggatott vonalak a címkézetlen gerincesre alkalmazott különböző attribútum tesztfeltételek kimenetelét jelölik. A gerincest végül a Nem-emlős osztályhoz rendeljük.

Egy címkézetlen gerinces osztályozása. A szaggatott vonalak a címkézetlen gerincesre alkalmazott különböző attribútum tesztfeltételek kimenetelét jelölik. A gerincest végül a Nem-emlős osztályhoz rendeljük.

Hogyan építsünk döntési fát

Elvben exponenciálisan sok döntési fát lehet felépíteni attribútumok egy adott halmazából. Míg egyes fák pontosabbak mint mások, az optimális fa megtalálása kiszámításilag végrehajthatatlan, mivel a keresési tér exponenciális méretű. Ennek ellenére hatékony algoritmusokat fejlesztettek ki viszonylag pontos, jóllehet az optimálisnál rosszabb döntési fa ésszerű időn belül való előállítására. Ezek az algoritmusok általában olyan mohó stratégiát alkalmaznak, amelyek úgy növelik a döntési fát, hogy egy sor lokálisan optimális döntést hoznak arról, hogy melyik attribútumot használjuk az adatok particionálására. Az egyik ilyen algoritmus Hunt algoritmusa, amely sok létező döntési fa következtetési algoritmus alapja, beleértve az ID3, C4.5 és a CART algoritmusokat. Ez a szakasz Hunt algoritmusának egy magas szintű tárgyalását nyújtja és néhány tervezési kérdését szemlélteti.

Hunt algoritmusa

Hunt algoritmusánál a döntési fa rekurzív módon nő a tanulórekordok egymás utáni, tisztább részhalmazokra való particionálásával. Legyen D t a t csúcshoz tartozó tanulórekordok halmaza és y={ y 1 , y 2 ,…, y c } az osztálycímkék halmaza. Hunt algoritmusának rekurzív definíciója az alábbi.

1. lépés

Ha az összes D t -beli rekord ugyanahhoz az y t osztályhoz tartozik, akkor t egy levélcsúcs y t -vel címkézve.

2. lépés

Ha D t olyan rekordokat tartalmaz, amelyek egynél több osztályhoz tartoznak, akkor egy attribútum tesztfeltételt (attribute test condition) választunk a rekordok kisebb részhalmazokra való particionálására. A tesztfeltétel mindegyik kimenetelére egy gyerek csúcs jön létre, és a D t -beli rekordok szétoszlanak a kimenetelek alapján a gyerekek között. Az algoritmust ezután rekurzívan alkalmazzuk mindegyik gyerek csúcsra.

Az algoritmus működésének szemléltetésére tekintsük azt az előrejelzési feladatot, hogy egy hitelkérelmező eleget tesz-e a hitelkötelezettségének, vagy kötelesség mulasztóvá válik és késedelembe esik. Úgy készíthetünk tanulóhalmazt erre a problémára, hogy korábbi hitelfelvevők rekordjait vizsgáljuk meg. A 4.6. ábrán látható példában minden rekord a hitelfelvevők személyes adatait tartalmazza egy olyan osztálycímkével együtt, amely jelzi, hogy az adós késedelembe esik-e a hitel visszafizetésében.

4.6. ábra - Azon hitelfelvevők előrejelzésének tanulóhalmaza, akik késedelembe esnek a hitel visszafizetésében

Az osztályozási feladat kiinduló fája egyetlen, Késedelmes = Nem osztálycímkéjű csúcsot tartalmaz (lásd a.4.7. (a) ábrát), ami azt jelenti, hogy a legtöbb hitelfelvevő sikeresen visszafizeti a hitelét.

4.7. ábra - Hunt algoritmusa döntési fa következtetésre

A fa azonban finomításra szorul, mivel a gyökér csúcs mindkét osztályból tartalmaz rekordokat. A rekordokat ezután kisebb részhalmazokra bontjuk a Háztulajdonos tesztfeltétel kimenetelei alapján, ahogy az a 4.7. (b) ábrán látható. A választott attribútum tesztfeltétel indoklásáról később lesz szó. Most azt feltételezzük, hogy ezen a ponton ez a legjobb kritérium az adatok kettévágására. Hunt algoritmusát ezután rekurzívan alkalmazzuk a gyökér csúcs minden gyerekére. a 4.7. ábrán adott tanulóhalmazból vegyük észre, hogy minden hitelfelvevő, aki háztulajdonos, sikeresen visszafizeti a hitelét. A gyökér bal gyermeke ezért egy Késedelmes = Nem címkéjű levélcsúcs lesz (lásd a 4.7 (b) ábrát). A jobboldali gyerekre tovább kell alkalmaznunk a Hunt algoritmus rekurzív lépését, amíg az összes rekord azonos osztályba nem tartozik. Az egyes rekurzív lépésekből származó fákat mutatják a 4.7. (c) és (d) ábrák.

Hunt algoritmusa akkor működik, ha az attribútumértékek minden kombinációja jelen van a tanulóhalmazban, és mindegyik kombinációhoz egyedi osztálycímke tartozik. Ezek a feltevések azonban túl szigorúak ahhoz, hogy a legtöbb gyakorlati helyzetben használhassuk őket. További feltételekre van szükség, hogy a következő eseteket is kezelni tudjuk:

Lehetséges, hogy néhány, a 2. lépésben létrehozott gyermek csúcs üres, azaz nincs rekord hozzárendelve ezekhez a csúcsokhoz. Ez akkor történhet meg, ha nincs olyan tanulórekord, amely az ilyen csúcsokhoz tartozó attribútumérték kombinációval rendelkezik. Ebben az esetben a csúcsot levélcsúcsnak nyilvánítjuk ugyanazzal az osztálycímkével, mint amivel a szülő csúcsbeli tanulórekordok többsége rendelkezik.
A 2. lépésben, ha az összes D t -beli rekord azonos attribútumértékekkel rendelkezik (az osztálycímkét kivéve), akkor nem lehet tovább osztani ezeket a rekordokat. Ebben az esetben a csúcsot levélcsúcsnak nyilvánítjuk ugyanazzal az osztálycímkével, mint amivel az ezen csúcsbeli tanulórekordok többsége rendelkezik.

A döntési fa következtetés tervezési kérdései

Egy döntési fa következtetés tanuló algoritmusának a következő két kérdéssel kell foglalkoznia.

Hogyan vágjuk szét a tanulórekordokat? A faépítési folyamat minden rekurzív lépésében ki kell választani egy attribútum tesztfeltételt, hogy a rekordokat kisebb részhalmazokra osszuk. Ezen lépés megvalósítása érdekében az algoritmusnak egy módszert kell adnia a tesztfeltétel meghatározására különböző attribútumtípusok esetén, valamint egy objektív mérőszámot mindegyik tesztfeltétel jóságának a kiértékelésére.
Mikor álljunk meg a vágási folyamatban? Egy megállási feltétel szükséges a faépítési folyamat megszakítására. Egy lehetséges stratégia az, hogy addig folytatjuk a csúcsok bővítését, amíg vagy az összes rekord (csúcsonként) ugyanahhoz az osztályhoz nem tartozik, vagy az összes rekord azonos attribútumértékekkel nem rendelkezik. Bár mindkét feltétel elégséges egy döntési fa következtetési algoritmus megállításához, más kritériumokat is kiszabhatunk, hogy a faépítési eljárást korábban befejezzük. A korai befejezés előnyeiről a későbbiekben, 4.4.5. szakaszban lesz szó.

Az attribútum tesztfeltételek kifejezésének módszerei

A döntési fa következtetési algoritmusoknak módszert kell adni egy attribútum tesztfeltétel kifejezésére és a megfelelő kimeneteleikre különböző attribútumtípusok esetén.

Bináris attribútumok

Egy bináris attribútumra a tesztfeltétel két lehetséges kimenetelt generál, amint azt . ábra mutatja.

4.8. ábra - Tesztfeltételek bináris attribútumokra

Névleges attribútumok

Mivel egy névleges attribútum sok értéket vehet fel, a tesztfeltételt kétféle módon lehet kifejezni, ahogy az . ábrán látható. Egy többágú vágás (4.9. (a) ábra) esetén a kimenetelek száma a megfelelő attribútum különböző értékeinek számától függ. Például, ha egy attribútum, mint a családi állapot, három különböző értéket – egyedülálló, házas vagy elvált – vesz fel, akkor a tesztfeltétel egy háromágú vágást állít elő.

4.9. ábra - Tesztfeltételek névleges attribútumokra

Másrészt, egyes döntési fa algoritmusok, mint például a CART, kizárólag bináris vágásokat állítanak elő az összes 2 k−1 −1 számú lehetőséget figyelembe véve, amely k számú attribútumérték egy bináris partíciójának létrehozásánál adódhat. 4.9. (b) ábra szemlélteti annak három különböző módját, ahogy a családi állapot attribútum értékei két részhalmazba csoportosíthatóak.

Sorrendi attribútumok

Sorrendi attribútumok is állíthatnak elő bináris vagy többágú vágásokat. Addig csoportosíthatjuk a sorrendi attribútumértékeket, amíg a csoportosítás nem sérti meg az attribútumértékek rendezési tulajdonságát. A 4.10. ábra a tanulórekordoknak az Ingméret attribútumon alapuló különböző vágásait szemlélteti. 4.10. (a) és (b) ábrán látható csoportosítások megőrzik a rendezést az attribútumértékek között, míg 4.10. (c) ábrán látható csoportosítás megsérti ezt a tulajdonságot, mert ugyanabba a partícióba egyesíti a Kicsi és Nagy attribútumértékeket, míg a Közepes és Extra nagy egy másik partícióba kerül.

4.10. ábra - Sorrendi attribútumértékek csoportosításának különböző módjai

Folytonos attribútumok

Folytonos attribútumok esetén a tesztfeltétel úgy fejezhető ki, mint egy (A≤v) vagy (A≥v) bináris kimenetelekkel bíró összehasonlítás, vagy pedig egy tartomány alapú lekérdezés v i ≤A≤ v i+1 , i=1,…,k , alakú kimenetelekkel. A megközelítések közötti különbség 4.11. ábrán látható. A bináris esetben a döntési fa algoritmusnak az összes lehetséges v vágási értéket meg kell vizsgálnia, és azt kell kiválasztani, ami a legjobb partíciót adja. Többágú vágás esetén az algoritmusnak a folytonos értékek összes lehetséges tartományát figyelembe kell venni. Egy lehetséges megközelítés az, hogy 2.3.6. szakaszban az 59. oldalon leírt diszkretizálási stratégiákat alkalmazzuk. A diszkretizálás után egy új sorrendi skálán mért értéket rendelünk mindegyik diszkretizált intervallumhoz. Szomszédos intervallumokat is egyesíthetünk nagyobb tartományokká, amennyiben megmarad a rendezés.

4.11. ábra - Tesztfeltételek folytonos attribútumok esetén

Mérőszámok a legjobb vágás kiválasztására

Számos mérőszám van, melyet arra használhatunk, hogy meghatározzuk a rekordok szétvágásának a legjobb módját. Ezeket a mérőszámokat a rekordok vágás előtti és utáni osztályeloszlása segítségével definiálhatjuk.

Jelölje p(i|t) azoknak a rekordoknak az arányát, amelyek az i osztályhoz tartoznak egy adott t csúcsban. Néha elhagyjuk a t csúcsra való hivatkozást, és az arányt mint p i adjuk meg. Egy kétosztályos feladatnál egy tetszőleges csúcsbeli osztályeloszlás úgy írható, mint ( p 0 , p 1 ) , ahol p 1 =1− p 0 . Ennek szemléltetésére tekintsük a 4.12. ábrán látható tesztfeltételeket. Az osztályeloszlás a vágás előtt (0,5;0,5) , mivel mindegyik osztályban azonos számú rekord van. Ha a Nem attribútum alapján vágjuk szét az adatokat, akkor a gyermek csúcsok osztályeloszlása (0,6;0,4) és (0,4;0,6) lesz. Bár az osztályok már nem egyenletesen oszlanak el, a gyerek csúcsok még mindig mindkét osztályból tartalmaznak rekordokat. A második jellemző (Autótípus ) alapján való vágás már tisztább partíciókat eredményez.

4.12. ábra - Többágú és bináris vágás összehasonlítása

A legjobb vágás kiválasztására kidolgozott mérőszámok gyakran a gyermek csúcsok szennyezettségi (impurity) mértékén alapulnak. Minél kisebb a szennyezettség mértéke, annál ferdébb az osztályeloszlás. Például egy (0,1) osztályeloszlású csúcsnak nulla a szennyezettsége, míg a (0,5;0,5) egyenletes osztályeloszlású csúcsnak a legmagasabb a szennyezettsége. Szennyezettségi mértékre példa többek között:

Entrópia(t)=− ∑ i=0 c−1 p(i|t) log 2 p(i|t), (4.3)

Gini(t)=1− ∑ i=0 c−1 [p(i|t)] 2 , (4.4)

Osztályozási hiba(t)=1− max i [p(i|t)], (4.5)

ahol c az osztályok száma és 0 log 2 0:=0 az entrópia számolásánál.

A 4.13. ábra a szennyezettségi mértékeket hasonlítja össze bináris osztályozási feladatok esetén. Itt p azoknak a rekordoknak az arányára utal, amelyek a két osztály egyikéhez tartoznak. Figyeljük meg, hogy mind a három mérték akkor veszi fel a maximális értékét, ha az osztályeloszlás egyenletes, azaz ha p=0.5 . A minimális értékeket pedig akkor veszik fel, amikor az összes rekord azonos osztályba tartozik, azaz ha p egyenlő 0 -val vagy 1 -gyel. Ezután számos példát adunk a különféle szennyezettségi mértékek kiszámolására.

4.13. ábra - A szennyezettségi mértékek összehasonlítása bináris osztályozási feladatoknál

N 1 csúcs	Darab	Gini =1− (0/6) 2 − (6/6) 2 =0
Osztály=0	0	Entrópia =−(0/6) log 2 (0/6)−(6/6) log 2 (6/6)=0
Osztály=1	6	Hiba =1−max[0/6,6/6]=0

N 2 csúcs	Darab	Gini =1− (1/6) 2 − (5/6) 2 =0,278
Osztály=0	1	Entrópia =−(1/6) log 2 (1/6)−(5/6) log 2 (5/6)=0,650
Osztály=1	5	Hiba =1−max[1/6,5/6]=0,167

N 3 csúcs	Darab	Gini =1− (3/6) 2 − (3/6) 2 =0,5
Osztály=0	3	Entrópia =−(3/6) log 2 (3/6)−(3/6) log 2 (3/6)=1
Osztály=1	3	Hiba =1−max[3/6,3/6]=0,5

Az előző példák, valamint 4.13. ábra a különböző szennyezettségi mértékek közötti összhangot szemléltetik. Ezen számolások alapján az N 1 csúcsnak a legkisebb a szennyezettségi mértéke, majd ezt követi N 2 és N 3 . Ezen összhang ellenére a tesztfeltétel által választott attribútum változhat a szennyezettségi mértéktől függően, amint az 3. feladatban a 204. oldalon látható.

Annak meghatározásához, hogy milyen jól teljesít egy tesztfeltétel, össze kell hasonlítani a szülő csúcs (vágás előtti) szennyezettségi mértékét a gyerek csúcsok (vágás utáni) szennyezettségi mértékével. Minél nagyobb a különbség, annál jobb a tesztfeltétel. A Δ nyereség egy olyan kritérium, amely egy vágás jóságának meghatározásához használható:

Δ=I(szülő)− ∑ j=1 k N( v j ) N I( v j ), (4.6)

ahol I(⋅) egy adott csúcsbeli szennyezettségi mérték, N az összes rekord száma a szülő csúcsban, k az attribútumértékek száma és N( v j ) a v j gyerek csúcshoz tartozó rekordok száma. A döntési fa következtési algoritmusok gyakran választanak egy olyan tesztfeltételt, amely maximalizálja a Δ nyereséget. Mivel az I(szülő) minden tesztfeltételre azonos, a nyereség maximalizálása ekvivalens azzal, hogy minimalizáljuk a gyerek csúcsok súlyozott átlagos szennyezettségi mértékét. Végül, amikor az entrópiát használjuk szennyezettségi mértéknek (4.6) egyenletben, akkor az entrópiabeli különbség az úgynevezett információ-nyereség (information gain), melyet Δ info -val jelölünk.

Bináris attribútumok vágása

Tekintsük a.4.14. ábrán látható diagramot. Tegyük fel, hogy kétféleképpen vághatjuk az adatokat kisebb részhalmazokra. Vágás előtt a Gini-index 0,5 , hiszen mindkét osztályban azonos számú rekord van. Ha az A attribútumot választjuk az adatok szétvágására, akkor az N 1 csúcs Gini-indexe 0,4898 , az N 2 csúcsé pedig 0,480 . A leszármazott csúcsok Gini-indexének a súlyozott átlaga (7/12)×0,4898+(5/12)×0,480=0,486 . Hasonlóan mutathatjuk meg, hogy a B attribútum súlyozott átlagú Gini-indexe 0,371 . Mivel a B attribútumra kapott részhalmazok Gini-indexe a kisebb, ezért inkább őt részesítjük előnyben az A attribútummal szemben.

4.14. ábra - Bináris attribútumok vágása

Névleges attribútumok vágása

Mint már korábban említettük, egy névleges attribútum bináris vagy többágú vágásokat egyaránt állíthat elő, mint azt a.4.15. ábra mutatja. Bináris vágás esetén a Gini-index számítása hasonló a bináris attribútumoknál bemutatotthoz. Az Autótípus attribútum első bináris csoportosításánál a {Sport,Luxus} Gini-indexe 0,4922 , míg a {Családi} Gini-indexe 0,3750 . A csoportosítás súlyozott átlagos Gini-indexe az alábbival egyenlő:

16/20×0,4922+4/20×0,3750=0,468.

Hasonlóképpen, a második, {Sport} és {Családi,Luxus} bináris csoportosításra a súlyozott átlagos Gini-index 0,167 . A második csoportosítás Gini-indexe kisebb, mivel a megfelelő részhalmazok sokkal tisztábbak.

4.15. ábra - Névleges attribútumok vágása

Többágú vágásnál a Gini-indexet minden attribútumértékre számoljuk. Mivel Gini({Családi})=0,375 , Gini({Sport})=0 , és Gini({Luxus})=0,219 , a többágú vágás teljes Gini-indexe az alábbival egyenlő:

4/20×0,375+8/20×0+8/20×0,219=0,163.

A többágú vágás Gini-indexe kisebb mindkét kétágú vágással összehasonlítva. Ez az eredmény nem meglepő, hiszen a kétágú vágás valójában egy többágú vágás néhány kimenetelét egyesíti, és így kevésbé tiszta részhalmazokat eredményez.

Folytonos attribútumok vágása

Tekintsük a.4.16. ábrán látható példát, ahol az Évesjövedelem≤v tesztfeltételt alkalmaztuk a tanulórekordok vágására a késedelmes hitelek osztályozási feladatánál. A megfelelő v -t a nyers erő módszerével úgy találhatjuk meg, hogy az attribútum minden értékét az N számú rekordban egy vágási pozíció jelöltnek tekintjük. Minden egyes v jelöltre az adatállományt egyszer végigfésülve összeszámoljuk azokat a rekordokat, ahol az éves jövedelem kisebb vagy nagyobb, mint v . Ezután kiszámoljuk minden egyes jelölt Gini-indexét, és azt választjuk ki, amelyik a legkisebb értéket adja. Ennek a megközelítésnek nagy a számításigénye, mert O(N) számú műveletet igényel a Gini-index kiszámításához minden egyes vágási pozíció jelöltnél. Mivel N számú jelölt van, a teljes feladat bonyolultsága O( N 2 ) .

4.16. ábra - Folytonos attribútumok vágása

A bonyolultság csökkentése érdekében rendezzük a tanulórekordokat az éves jövedelem alapján, ez a számítás O(NlogN) időt igényel. A vágási pozíció jelölteket úgy azonosítjuk, hogy két szomszédos rendezett érték, 55, 65, 72 és így tovább, felezőpontját vesszük. A nyers erő megközelítéssel szemben azonban nem kell megvizsgálni az összes N rekordot, amikor a vágási pozíció jelölt Gini-indexét értékeljük ki.

Az első jelöltnél ( v=55 ) egyetlen rekordnál sem kevesebb az éves jövedelem, mint 55 000 dollár. Ennek eredményeként, az Évesjövedelem≤55 leszármazott csúcs Gini-indexe nulla. Másrészt az Igen osztályban 3 azoknak a rekordoknak a száma, amelyek éves jövedelme nagyobb vagy egyenlő, mint 55 000 dollár, a Nem osztályban pedig 7. Így ennek a csúcsnak a Gini-indexe 0,420 . A vágási pozíció jelölt teljes Gini-indexe 0×0+1×0,420=0,420 .

A második jelölt ( v=65 ) osztályeloszlását úgy tudjuk meghatározni, hogy frissítjük az előző jelölt eloszlását. Pontosabban, az új eloszlást úgy kapjuk, hogy megvizsgáljuk azoknak a rekordoknak az osztálycímkéit, amelyeknek a legalacsonyabb az éves jövedeleme, azaz 60 000 dollár. Mivel ezeknek a rekordoknak az osztálycímkéje Nem , a Nem osztály 0 -ról 1 -re nő az Évesjövedelem≤65 csúcsra, és 7 -ről 6 -ra csökken az Évesjövedelem≥65 csúcsra. Az Igen osztály változatlan marad. Az új súlyozott átlagos Gini-index erre a vágási pozíció jelöltre 0,400 .

Ezt az eljárást addig ismételjük, amíg ki nem számoljuk az összes jelölt Gini-indexét, amint az a.4.16. ábrán látható. Az lesz a legjobb vágási pozíció, amelynek a legkisebb a Gini-indexe, azaz v=97 . Ez az eljárás kevésbé költséges, mivel állandó mennyiségű időt igényel az osztályeloszlás frissítése minden egyes vágási pozíció jelöltnél. Ezt még tovább lehet optimalizálni csak azokat a vágási pozíció jelölteket figyelembe véve, amelyek két különböző típusú osztálycímkével rendelkező szomszédos rekord között találhatóak. Mivel például az első három rendezett rekord ( 60 000,70 000 és 75 000 dollár éves jövedelem) osztálycímkéje azonos, a legjobb vágási pozíció nem lehet 60 és 75 között. Ezért a v=55,65,72,87,92,110,122,172 és 230 vágási pozíció jelölteket figyelmen kívül hagyhatjuk, mert ezek két különböző típusú osztálycímkével rendelkező szomszédos rekord között helyezkednek el. Ez a megközelítés lehetővé teszi számunkra, hogy a vágási pozíció jelöltek számát 11 -ről 2 -re csökkentsük.

Nyereségarány

Az olyan szennyezettségi mértékek, mint például az entrópia és a Gini-index, azokat az attribútumokat részesítik előnyben, amelyek nagy számú különböző értéket vesznek fel. A 4.12. ábra három alternatív tesztfeltételt mutat ex3:split. oldalon lévő 2. feladatbeli adatállomány particionálására. Az első tesztfeltételt (Nem) a másodikkal ( Autótípus ) összehasonlítva könnyen látható, hogy jobb útnak tűnik az adatok vágására az Autótípus, mivel az általa előállított leszármazott csúcsok tisztábbak. Ugyanakkor, ha összehasonlítjuk a két feltételt az Ügyfélazonosítóval, akkor úgy tűnik, hogy az utóbbi eredményez tisztább partíciókat. Az Ügyfélazonosítóval , mégsem prediktív attribútum, mert értéke minden rekord esetén egyértelmű. Még egy olyan kevésbé szélsőséges helyzet sem kívánatos, ahol a tesztfeltétel nagyszámú kimenetelt eredményez, mert az egyes partíciókhoz kapcsolódó rekordok száma túl kicsi ahhoz, hogy megbízható előrejelzéseket kapjunk.

Két stratégiával lehetünk úrrá ezen a problémán. Az első stratégia az, hogy a tesztfeltételeket csak bináris vágásokra korlátozzuk. Ezt a stratégiát alkalmazzák olyan döntési fa algoritmusok, mint a CART. Egy másik stratégia a vágási kritérium olymódon való módosítása, amely figyelembe veszi az attribútum tesztfeltétel által előállított kimenetelek számát. A C4.5 döntési fa algoritmusban például egy nyereségarányként (gain ratio) ismert vágási kritériumot használunk egy vágás jóságának a meghatározására. Ezt a kritériumot a következőképpen definiáljuk:

Nyereségarány= Δ info Vágás info . (4.7)

Itt Vágás info=− ∑ i=1 k P( v i ) log 2 P( v i ) és k a vágások száma. Ha például minden attribútumértékhez ugyanannyi rekord tartozik, akkor P( v i )=1/k minden i -re, és a vágási információ log 2 k -val egyenlő. Ez a példa azt sugallja, hogy ha egy attribútum sok vágást eredményez, akkor a vágási információ is nagy lesz, ami viszont csökkenti a nyereségarányt.

A döntési fa következtetés algoritmusa

4.1. algoritmus. Egy dontesi fa alapu kovetkeztetesi algoritmus vaza

Faépítés (E,F)

1: if Leállási_Feltétel(E,F) = igaz then

2: levél = Hozz_Létre_Csúcsot()

3: levél.címke = Osztályoz©

4: return levél

5: else

6: gyökér = Hozz_Létre_Csúcsot()

7: gyökér.tesztfeltétel = Keress_Legjobb_Vágást(E,F)

8: Legyen V = {v | v a gyökér.tesztfeltétel egy lehetséges kimenetele}

9: for minden v ∈ V –re do

11: gyerek = Faépítés(Ev, F)

12: Adjuk hozza a gyerek csúcsot a gyökér leszármazottjaként es címkézzük a (gyökér → gyerek) élt v-vel

13: end for

14: end if

15: return gyökér

Egy Faépítés nevű döntési fa következtetési algoritmus váza látható a 4.1. algoritmusban. Az algoritmus inputja az E tanulórekordokból és az F attribútumhalmazból áll. Az algoritmus úgy működik, hogy rekurzívan kiválasztja a legjobb attribútumot, amely szerint az adatokat vágni kell (7. lépés), és levélcsúcsokkal bővíti a fát (11. és 12. lépés), amíg a megállási kritérium nem teljesül (1. lépés). Az algoritmus részleteit az alábbiakban ismertetjük:

A Hozz_Létre_Csúcsot() függvény egy új csúcs létrehozásával bővíti a döntési fát. A döntési fa egy csúcsa vagy egy (csúcs.tesztfeltétel-lel jelölt) tesztfeltétellel, vagy egy (csúcs.címke-vel jelölt) osztálycímkével rendelkezik.
A Keress_Legjobb_Vágást() függvény azt határozza meg, hogy melyik attribútumot kell kiválasztanunk, mint tesztfeltételt, a tanulórekordok vágására. Mint már említettük, a tesztfeltétel megválasztása attól függ, hogy milyen szennyezettségi mértéket használunk egy vágás jóságának meghatározására. Néhány széles körben használt mérték többek között az entrópia, a Gini-index és a χ 2 statisztika.
Az Osztályoz() függvény határozza meg azt az osztálycímkét, amelyet egy levélcsúcshoz kell rendelni. Minden egyes t levélcsúcs esetén jelölje p(i|t) a t csúcshoz tartozó i osztálybeli tanulórekordok arányát. A legtöbb esetben azt az osztályt rendeljük a levélcsúcshoz, amelyhez a legtöbb tanulórekord tartozik:

levél.címke= argmax i p(i|t), (4.8)

ahol argmax azzal az i argumentummal tér vissza, amely maximalizálja a p(i|t) kifejezést. Amellett, hogy egy levélcsúcs osztálycímkéjének a meghatározásához szükséges információt szolgáltatja, a p(i|t) törtet annak a valószínűségnek a becslésére is felhasználhatjuk, hogy egy a t levélcsúcshoz tartozó rekord az i osztályhoz tartozik. 5.7.2. és 5.7.3. szakaszok leírják, hogy hogyan használhatóak fel ezek a valószínűség becslések a döntési fa teljesítőképességének a meghatározására különböző költség-függvények mellett.

A Leállási_Feltétel() függvényt arra használjuk, hogy befejezzük a fa építésének folyamatát azt vizsgálva, hogy az összes rekordnak már vagy azonosak az osztálycímkéi, vagy pedig azonosak az attribútumértékei. Egy másik mód arra, hogy befejezzük a rekurzív függvény hívását, annak tesztelése, hogy a rekordok száma egy minimális érték alá esett-e.

A döntési fa felépítése után egy fametszés (fanyesés, tree-pruning) lépést végezhetünk, hogy csökkentsük a döntési fa méretét. A túl nagy döntési fák fogékonyak a túlillesztés (overfitting) jelenségére. A metszés az eredeti fa ágainak levágásával oly módon segít, hogy javítja a döntési fa általánosítási képességét. A túlillesztés és a fametszés kérdéseit részletesebben 4.4. szakaszban tárgyaljuk.

Példa: web-robot észlelés

A web-használat bányászat adatbányászati módszerek alkalmazásának egy olyan feladata, amellyel hasznos mintázatokat nyerhetünk ki webes naplókból. Ezek a mintázatok az oldalak látogatóinak érdekes jellemzőit tárhatják fel; azok az emberek például, akik többször is ellátogatnak egy weboldalra, és ugyanazt a terméket leíró oldalt tekintik meg, nagyobb valószínűséggel vásárolják meg a terméket, amennyiben bizonyos ösztönzőket, például árengedményt vagy ingyenes szállítást, kínálunk.

4.17. ábra - A web-robot észlelés input adatai

A web-használat bányászat során fontos megkülönböztetni az emberi felhasználók hozzáféréseit a web-robotokéitól. A web-robot (web crawler) egy olyan program, amely automatikusan információkat keres és tölt le az Internetről a weblapokba ágyazott hiperhivatkozásokat követve. Ezek a programok a kereső portálokon vannak telepítve azért, hogy összegyűjtsék a web indexeléséhez szükséges dokumentumokat. A web-robot hozzáféréseket el kell távolítanunk, mielőtt web-bányászati módszereket alkalmazunk az emberi böngészési szokások elemzésére.

Ez a szakasz leírja, hogyan használható egy döntési fa osztályozó arra, hogy különbséget tegyünk az emberi felhasználók és a web-robotok hozzáférései között. Az input adatokat egy web-szerver naplóállományából kaptuk, melyből egy minta látható a 4.17. (a) ábrán. Minden sor egy webes kliens (egy felhasználó vagy egy web-robot) által kért egyetlen oldalnak felel meg. A web-naplóban rögzített mezők a kliens IP-címét, a kérés időbélyegjét, a kért dokumentum webcímét, a dokumentum méretét és az ügyfél személyazonosságát (a User Agent mező révén) tartalmazzák. Egy web munkamenet egy kliens kéréseinek sorozata egy weboldal egyszeri meglátogatása során. Minden web munkamenet úgy modellezhető, mint egy irányított gráf, amelyben a csúcsok a weblapoknak felelnek meg, az élek pedig egy weboldalt egy másikkal összekötő hiperhivatkozásoknak. a 4.17. (b) ábra a web-szerver logfájlban adott első web munkamenet grafikus ábrázolását mutatja.

A web munkamenetek osztályozása céljából jellemzőket hozunk létre a munkamenetek leírására. A 4.17. © ábra néhány olyan jellemzőt mutat, amelyet a web-robot észlelésének feladatánál használunk. Az említésre méltó jellemzők közé tartozik a bejárás mélysége (depth) és szélessége (breadth). A mélység határozza meg a maximális távolságot egy kért laptól, ahol a távolságot a hiperhivatkozások számában mérjük a webhely belépési pontjától. Feltételezzük például, hogy a http://www.cs.umn.edu/ : kumar honlap mélysége 0, míg a http://www.cs.umn.edu/kumar/MINDS/MINDS_papers.htm lap 2 mélységben található. A 4.17. (b) ábrán mutatott web-gráf alapján a mélység attribútum az első munkamenetnél kettővel egyenlő. A szélesség attribútum a megfelelő web-gráf szélességét méri. Például a 4.17. (b) ábrán látható web munkamenet szélessége kettővel egyenlő.

Az osztályozásra használt adatállomány 2916 rekordot tartalmaz, amelyek közül egyenlő számú munkamenet köszönhető web-robotoknak (1. osztály) és humán felhasználóknak (0. osztály). Az adatok 10% -át a tanításra tartottuk fenn, míg a fennmaradó 90% -ot tesztelésre használtuk. a A 4.18. ábra mutatja az eredményül kapott döntési fa modellt. A fa hibaaránya 3,8% a tanuló- és 5,3% a teszthalmazon.

4.18. ábra - Web-robot észlelés döntési fa modellje

A modell azt sugallja, hogy a web-robotokat a következő módon lehet megkülönböztetni az emberi felhasználóktól:

A web-robotok hozzáférései általában szélesek, de sekélyek, míg az emberi felhasználókéi általában koncentráltabbak (keskenyek, de mélyek).
Az emberi felhasználókkal ellentétben a web-robotok ritkán töltenek le webes dokumentumhoz kapcsolódó képet tartalmazó oldalakat.
A web-robotok munkamenetei általában hosszúak és nagy számú lekért oldalt tartalmaznak.
A web-robotok nagyobb valószínűséggel ismétlik meg az ugyanarra a dokumentumra vonatkozó lekérésüket, mivel az emberi felhasználók által letöltött weblapok gyakran a böngésző gyorsítótárába kerülnek.

A döntési fa következtetés jellemzői

Az alábbiakban összefoglaljuk a döntési fa következtetési algoritmusok legfontosabb jellemzőit.

A döntési fa következtetés egy nemparaméteres megközelítés osztályozási modellek építésére. Más szóval, nem igényel semmilyen előzetes feltételezést az osztályozó és más attribútumok valószínűségi eloszlásainak a típusával kapcsolatban (ellentétben néhány 5. fejezetben leírt módszerrel).
Az optimális döntési fa megtalálása egy NP-teljes probléma. Sok döntési fa algoritmus heurisztikus megközelítést alkalmaz a hatalmas hipotézis térben való keresés irányítására. 4.3.5. szakaszban bemutatott algoritmus például egy mohó, felülről lefelé haladó, rekurzív particionáló stratégiát használ a döntési fa építésére.
A döntési fák építésére kifejlesztett módszerek kis számításigényűek, lehetővé téve modellek gyors felépítését még akkor is, ha a tanulóhalmaz mérete igen nagy. Továbbá, ha már felépült egy döntési fa, akkor egy tesztrekord osztályozása már rendkívül gyors, a legrosszabb esetben O(w) bonyolúltságú, ahol w a fa maximális mélysége.
A döntési fák, különösen a kisebb méretű fák, viszonylag könnyen értelmezhetőek. A fák pontossága szintén összevethető más osztályozási módszerekével sok egyszerű adatállomány esetén.
A döntési fák diszkrét értékű függvények tanításának egy kifejező reprezentációját nyújtják. Bizonyos típusú Boole feladatoknál azonban már nem általánosítanak jól. Egy figyelemre méltó példa a paritás függvény, melynek értéke 0 (1) aszerint, hogy az Igaz értékkel rendelkező Boole attribútumok száma páratlan (páros). Egy ilyen függvény pontos modellezése egy teljes döntési fát igényel 2 d számú csúccsal, ahol d a Boole attribútumok száma (lásd 1. feladatot a 204. oldalon).
A döntési fa algoritmusok zaj jelenléte esetén is eléggé robusztusak, különösen amikor olyan, 4.4. szakaszban leírt, módszereket alkalmazunk, amelyek elkerülik a túlillesztést.
A felesleges (redundáns) attribútumok jelenléte nem befolyásolja károsan a döntési fák pontosságát. Egy attribútum felesleges, ha az adatok alapján erősen korrelál egy másik attribútummal. Nem fogjuk két redundáns attribútum egyikét vágásra használni, miután a másik attribútumot már kiválasztottuk. Ha azonban az adatállomány sok lényegtelen attribútumot tartalmaz, azaz olyan attribútumokat, amelyek nem használhatóak az osztályozási feladatnál, akkor véletlenül kiválaszthatunk egyes lényegtelen attribútumokat a faépítési folyamat során, amely így egy, a szükségestől nagyobb döntési fát eredményez. Jellemző kiválasztási módszerek segítségével növelhetjük a döntési fák pontosságát úgy, hogy elhagyjuk a lényegtelen attribútumokat az előfeldolgozás során. A túl sok lényegtelen attribútum kérdését 4.4.3. szakaszban fogjuk vizsgálni.
Mivel a legtöbb döntési fa algoritmus felülről lefelé haladó, rekurzív particionáló megközelítést alkalmaz, a rekordok száma egyre kisebb lesz, ahogy lefelé haladunk a fában. A levélcsúcsokban a rekordok száma már túl kicsi lehet ahhoz, hogy statisztikailag szignifikáns döntést hozzunk a csúcsokat reprezentáló osztályokról. Ez az úgynevezett adat-töredezettségi (data fragmentation) probléma. Az egyik lehetséges megoldás, hogy nem engedélyezünk további vágást, amennyiben a rekordok száma nem ér el egy bizonyos küszöbértéket.
Egy részfa többször is ismétlődhet egy döntési fában, amint azt 9. ábra mutatja. Ez a döntési fát a szükségestől bonyolultabbá és talán nehezebben értelmezhetővé teszi. Ilyen helyzet adódhat olyan döntési fa implementálásakor, amelyek egyetlen attribútumon alapuló tesztfeltételre hagyatkoznak minden egyes belső csúcsnál. Mivel a legtöbb döntési fa algoritmus az oszd meg és uralkodj particionálási stratégiát alkalmazza, ugyanazt a tesztfeltételt lehet alkalmazni az attribútumtér különböző részein, ami így a részfa ismétlődési problémára vezet.

4.19. ábra - A fa ismétlődési probléma. Ugyanaz a részfa több ágon is megjelenhet.

Az ebben a fejezetben eddig leírt tesztfeltételek egy időben csak egy attribútumot használnak fel. Ennek következtében a faépítési eljárást egy olyan folyamatnak lehet tekinteni, mint amely az attribútumteret diszjunkt tartományokra osztja addig, amíg minden egyes tartomány azonos osztályba tartozó rekordokat nem tartalmaz (lásd 10. ábrát).

4.20. ábra - Egy példa döntési fára és döntési határára kétdimenziós adatállomány esetén

Különböző osztályok két szomszédos tartománya közötti határt döntési határnak (decision boundary) nevezzük. Mivel a tesztfeltétel csak egy attribútumot tartalmaz, a döntési határok egyenes vonalúak, azaz párhuzamosak a ,,koordináta tengelyekkel’’. Ez korlátozza a döntési fa ábrázolás kifejezőképességét folytonos attribútumok közötti összetett kapcsolatok modellezésénél. 10. ábra egy olyan adatállományt szemléltet, amely nem osztályozható hatékonyan egy olyan döntési fa algoritmussal, amely egy időben csak egy attribútumot bevonó tesztfeltételeket használ.

4.21. ábra - Példa olyan adatállományra, amely nem particionálható optimálisan egyetlen attribútumot bevonó tesztfeltételek használatával

A ferde (oblique) döntési fa használatával túlléphetünk ezen a korlátozáson, ugyanis ez a fa olyan tesztfeltételeket is megenged, amelyek egynél több attribútumra épülnek. 10. ábrán adott adatállomány könnyen szemléltethető egy olyan ferde döntési fával, amely egyetlen csúcsot tartalmaz az

x+y≤1

tesztfeltétellel. Bár az ilyen módszerek sokkal kifejezőbbek és képesek sokkal tömörebb fákat előállítani, az optimális tesztfeltétel megtalálása egy adott csúcsra számításigényes lehet.

A konstruktív indukció (constructive induction) egy másik módja annak, hogy az adatokat homogén, nemtéglalap alakú tartományokra osszuk fel (lásd a.2.3.5. fejezetet 58. oldalon). Ez a megközelítés összetett attribútumokat hoz létre meglévő attribútumok aritmetikai vagy logikai kombinációiként. Az új attribútumok az osztályok jobb megkülönböztetését adják és megnövelik az adatállományt a döntési fa alapú következtetés előtt. A ferde döntési fa megközelítéssel ellentétben a konstruktív indukció kevésbé költséges, mert a döntési fa felépítése előtt egyszer azonosítja az attribútumok összes releváns kombinációját. Ezzel szemben egy ferde döntési fának dinamikusan meg kell határoznia a helyes attribútum kombinációt minden egyes alkalommal, amikor egy belső csúccsal bővül a fa. A konstruktív indukció azonban attribútum ismétlődést is behozhat az adatokba, mivel az új attribútum több meglévő attribútum kombinációja.

Vizsgálatok mutatták ki, hogy a szennyezettségi mérték megválasztásának kis hatása van a döntési fa következtetési algoritmusok teljesítményére. Ez azért van, mert a szennyezettségi mértékek többsége meglehetősen konzisztens egymással, amint azt a 4.13. ábra mutatja 164. oldalon. Valójában, a fa metszésére használt stratégia nagyobb hatással van a végső fára, mint a választott szennyezettségi mérték.

Vissza	Fel	Előre
Az osztályozási probléma megoldásának általános megközelítése	Főoldal	Modell túlillesztés