Modell túlillesztés

Egy osztályozási modellben elkövetett hibák általában két csoportba sorolhatóak: tanítási hibák (training errors) és általánosítási hibák (generalization errors). A tanítási hiba, vagy más néven visszahelyettesítési hiba (resubstitution error) vagy látszólagos hiba a tanulórekordokon elkövetett helytelen osztályozási hibák száma, míg az általánosítási hiba a modell várható hibája korábban nem látott rekordokon.

A 4.2. szakaszból emlékeztetünk arra, hogy egy jó osztályozási modell nem csak a tanulóadatokra illeszkedik jól, hanem azokat a rekordokat is pontosan osztályozza, amelyeket még soha sem látott. Más szóval, egy jó modellnek kis tanítási hibával, valamint kis általánosítási hibával kell rendelkeznie. Ez azért fontos, mert egy olyan modell, amely túl jól illeszkedik a tanulóadatokra, rosszabb általánosítási hibával rendelkezhet, mint egy nagyobb tanítási hibájú modell. Ez a helyzet modell túlillesztésként ismert.

Egy túlillesztési példa kétdimenziós adatokon

A túlillesztési probléma egy konkrétabb példájaként tekintsük a 4.22. ábrán látható kétdimenziós adatállományt. Az adatállomány olyan adatpontokat tartalmaz, amelyek két különböző, egyenként o-val és +-szal jelölt, osztályba tartoznak. Az o osztálybeli adatpontokat három Gauss eloszlás keverékéből generáltuk, míg a + osztálybeli adatpontok létrehozására egyenletes eloszlást használtunk. Összesen 1200 pont tartozik az o osztályba és 1800 pont + osztályba. A pontok 30% -át választottuk ki tanításra, míg a fennmaradó 70% -ot a tesztelésre használjuk. Ezután a Gini-indexet szennyezettségi mértéknek használó döntési fa osztályozót alkalmaztunk a tanulóhalmazon. A túlillesztés hatásának vizsgálatára különböző szintű metszéseket alkalmaztunk a kezdeti, teljesen felépített fára. A 4.23. ábra mutatja a döntési fa tanítási és tesztelési hibaarányait.

4.22. ábra - Példa adatállományra bináris osztályokkal

Példa adatállományra bináris osztályokkal

4.23. ábra - Tanítási és tesztelési hibaarányok

Tanítási és tesztelési hibaarányok

Vegyük észre, hogy a modell tanítási és tesztelési hibaarányai nagyok, ha a fa mérete nagyon kicsi. Ez a helyzet modell alulillesztésként (model underfitting) ismert. Az alulillesztés azért lép fel, mert a modell még nem tanulta meg az adatok igazi szerkezetét. Ennek eredményeként gyengén teljesít a tanuló- és a teszthalmazon egyaránt. Ahogy a döntési fa csúcsainak száma nő, a fa tanítási és tesztelési hibái csökkennek. Amennyiben azonban a fa túl naggyá válik, a tesztelési hibaarány elkezd nőni annak ellenére, hogy a tanítási hibaarány folyamatosan csökken. Ez a jelenség modell túlillesztésként (model overfitting) ismert.

Ahhoz, hogy megértsük a túlillesztés jelenségét, megjegyezzük, hogy a modell tanítási hibája csökkenthető a modell bonyolultságának növelésével. A fa levélcsúcsai például addig bővíthetőek, amíg a fa tökéletesen nem illeszkedik a tanulóadatokra. Bár egy ilyen összetett fa tanítási hibája nulla, a tesztelési hiba már nagy lehet, mert a fa olyan csúcsokat is tartalmazhat, amelyek csak véletlenül illeszkednek a tanulóadatok néhány zajos pontjára. Ezek a csúcsok rontják a fa teljesítményét, mert nem általánosítanak jól a tesztesetekre. A 4.24. ábra két különböző csúcsszámú döntési fa szerkezetét mutatja. Annak a fának, amelyik kevesebb számú csúcsot tartalmaz, nagyobb a tanítási hibaaránya, de kisebb a tesztelési hibaaránya, mint a bonyolultabb fáé.

4.24. ábra - Különböző modell bonyolultságú döntési fák

Különböző modell bonyolultságú döntési fák

A túlillesztés és alulillesztés két olyan rendellenesség, amely a modell bonyolultságával kapcsolatos. A szakasz további részében a modell túlillesztés néhány lehetséges okát vizsgáljuk meg.

Zaj miatti túlillesztés

Tekintsük a 4.3. és a 4.4. táblázatokban látható tanuló- és teszthalmazokat az emlős osztályozási feladatra. A tíz tanulórekord közül kettő kapott téves címkét: a denevéreket és a bálnákat osztályoztuk nem-emlősöknek emlősök helyett.

4.3. táblázat - Egy példa tanulóhalmaz az emlősök osztályozására. Csillagozott osztálycímkék jelölik a tévesen címkézett rekordokat.

Név

Test-

Eleven-

Négy-

Téli álmot

Osztály-

hőmérséklet

szülő

lábú

alszik

címke

sündisznó

melegvérű

igen

igen

igen

igen

macska

melegvérű

igen

igen

nem

igen

denevér

melegvérű

igen

nem

igen

nem   *

bálna

melegvérű

igen

nem

nem

nem   *

szalamandra

hidegvérű

nem

igen

igen

nem

komodói sárkány

hidegvérű

nem

igen

nem

nem

óriáskígyó

hidegvérű

nem

nem

igen

nem

lazac

hidegvérű

nem

nem

nem

nem

sas

melegvérű

nem

nem

nem

nem

guppi (hal)

hidegvérű

igen

nem

nem

nem


4.4. táblázat - Egy példa teszthalmaz az emlősök osztályozására

Név

Test-

Eleven-

Négy-

Téli álmot

Osztály-

hőmérséklet

szülő

lábú

alszik

címke

ember

melegvérű

igen

nem

nem

igen

galamb

melegvérű

nem

nem

nem

nem

elefánt

melegvérű

igen

igen

nem

igen

leopárdcápa

hidegvérű

igen

nem

nem

nem

teknősbéka

hidegvérű

nem

igen

nem

nem

pingvin

hidegvérű

nem

nem

nem

nem

angolna

hidegvérű

nem

nem

nem

nem

delfin

melegvérű

igen

nem

nem

igen

hangyászsün

melegvérű

nem

igen

igen

igen

viperagyík

hidegvérű

nem

igen

igen

nem


4.25. ábra - A 4.3. táblázatbeli adatállomány által indukált döntési fa

A 4.3. táblázatbeli adatállomány által indukált döntési fa

Egy a tanulóadatokra tökéletesen illeszkedő döntési fa látható 17. (a) ábrán. Bár a fa tanítási hibája nulla, a tesztelési hibaaránya 30% . Az emberek és a delfinek egyaránt hibásan osztályozódnak mint nem-emlősök, mert a Testhőmérséklet , Elevenszülő és Négylábú attribútumok értékei azonosak a tanulóhalmaz tévesen címkézett rekordjaiéval. A hangyászsünök másrészt egy kivételes esetet jelentenek, amikor egy tesztrekord osztálycímkéje ellentmond más hasonló rekordok osztálycímkéjének a tanulóhalmazban. A kivételes esetek miatti hibák gyakran elkerülhetetlenek, és meghatározzák a bármilyen osztályozó által elérhető minimális hibaarányt.

Ezzel szemben a 4.25. (b) ábrán látható M2 döntési fa tesztelési hibaaránya kisebb ( 10% ) annak ellenére, hogy a tanítási hibaarány valamivel magasabb ( 20% ). Nyilvánvaló, hogy az M1 első döntési fa túlillesztett a tanulóadatokon, mert létezik egy egyszerűbb modell, amelynek kisebb a hibaaránya a teszthalmazon. A Négylábú attribútumon alapuló tesztfeltétel az M1 modellben hamis, mert illeszkedik a tévesen címkézett tanító rekordokra, ami a rekordok téves osztályozására vezet a teszthalmazon.

Túlillesztés jellegzetes minták hiánya miatt

Azok a modellek, amelyeknek az osztályozási döntései kevés számú tanulórekordon alapulnak, szintén érzékenyek a túlillesztésre. Ezek a modellek akkor jöhetnek létre, ha a tanulóadatokból jellegzetes minták hiányoznak, és a tanuló algoritmusok akkor is tovább finomítják a modelljeiket, ha már csak néhány tanulórekord áll rendelkezésre. Ezeket a hatásokat szemléltetjük az alábbi példában.

Tekintsük a 4.5. táblázatban látható öt tanulórekordot. Mindegyik tanulórekord helyesen címkézett, és a megfelelő döntési fát a 4.26. ábrán ábrázoltuk. Bár a tanítási hiba nulla, a hibaarány 30% a teszthalmazon.

4.5. táblázat - Egy példa tanítóhalmaz az emlősök osztályozására.

Név

Test-

Eleven-

Négy-

Téli álmot

Osztály-

hőmérséklet

szülő

lábú

alszik

címke

szalamandra

hidegvérű

nem

igen

igen

nem

guppi (hal)

hidegvérű

igen

nem

nem

nem

sas

melegvérű

nem

nem

nem

nem

kecskefejő (madár)

melegvérű

nem

nem

igen

nem

kacsacsőrű emlos

melegvérű

nem

igen

igen

igen


4.26. ábra - A 4.5. táblázatbeli adatállomány által indukált döntési fa

A 4.5. táblázatbeli adatállomány által indukált döntési fa

Az emberek, elefántok és delfinek tévesen osztályozódnak, mert a döntési fa az összes téli álmot nem alvó melegvérű gerincest nem-emlősnek osztályozza. A fa azért jut erre az osztályozási döntésre, mert csak egy tanulórekord van ilyen jellemzőkkel, a sas. Ez a példa világosan demonstrálja a rossz előrejelzés veszélyét, amikor nincs elég reprezentatív eset egy döntési fa levélcsúcsaiban.

Túlillesztés és a többszörös összehasonlítási eljárás

A modell túlillesztés olyan tanuló algoritmusoknál is felmerülhet, amelyek a többszörös összehasonlítási eljárásként ismert módszertant alkalmazzák. Ahhoz, hogy megértsük a többszörös összehasonlítási eljárást, tekintsük annak előrejelzésének a feladatát, hogy a tőzsde növekedni vagy csökkenni fog-e a következő tíz kereskedési napon. Ha egy tőzsdei elemző egyszerű véletlen találgatásokat tesz, akkor 0,5 annak a valószínűsége, hogy az előrejelzése helyes bármelyik kereskedési napon. Ugyanakkor annak a valószínűsége, hogy tízből legalább nyolcszor helyesen jósol

( 10 8 )+( 10 9 )+( 10 10 ) 2 10 =0,0547,

amely igen valószínűtlennek tűnik.

Tegyük fel, hogy ötven tőzsdei elemző közül egy befektetési tanácsadó kiválasztása iránt érdeklődünk. Stratégiánk az, hogy azt az elemzőt választjuk ki, aki a legtöbb helyes előrejelzést hozza az elkövetkező tíz kereskedési napon. A hiba ebben a stratégiában az, hogy még ha minden elemző véletlenszerű módon jelez előre,

1 (10,0547) 50 =0,9399

annak a valószínűsége, hogy legalább az egyik közülük legalább nyolc pontos előrejelzést tesz, ami nagyon magas. Bár mindegyik elemző kis valószínűséggel jelez helyesen előre legalább nyolc alkalommal, összekötve őket már nagy valószínűséggel találunk egy olyan elemzőt, aki ezt képes megtenni. Nincs garancia továbbá a jövőben arra, hogy egy ilyen elemző továbbra is pontos előrejelzéseket fog adni véletlenszerű találgatással.

Hogyan kapcsolódik a többszörös összehasonlítási eljárás a modell túlillesztéshez? Sok tanuló algoritmus független alternatívák egy { γ i } halmazát tárja fel, majd azt a γ max alternatívát választja, amely egy adott kritérium függvényt maximalizál. Az algoritmus hozzáadja γ max -ot az aktuális modellhez azért, hogy javítsa annak összteljesítményét. Ezt az eljárást addig ismételjük, amíg további javulás nem figyelhető meg. A döntési fa építése során például több vizsgálatot végzünk, hogy melyik attribútum tudja legjobban vágni a tanulóadatokat. A legjobb vágáshoz vezető attribútumot választjuk a fa növelésére addig, amíg a megfigyelt javulás statisztikailag szignifikáns.

Legyen T 0 a kezdeti döntési fa és T x az új fa az x attribútumhoz tartozó belső csúcs beszúrása után. Elvileg x -et akkor lehet hozzáadni a fához, ha a Δ( T 0 , T x ) megfigyelt nyereség nagyobb, mint egy előre meghatározott α küszöbérték. Ha csak egy attribútum tesztfeltételt kell kiértékelni, akkor el tudjuk elkerülni hamis csúcsok beszúrását úgy, hogy egy elég nagy α értéket választunk. A gyakorlatban azonban egynél több tesztfeltétel áll rendelkezésre, és a döntési fa algoritmusnak kell kiválasztani a legjobb x max attribútumot jelöltek egy { x 1 , x 2 ,, x k } halmazából, hogy az adatokat particionáljuk. Ebben az esetben az algoritmus valójában egy többszörös összehasonlítási eljárást használ annak eldöntésére, hogy megnöveljen-e egy döntési fát. Pontosabban, Δ( T 0 , T x )α helyett a Δ( T 0 , T x max )α egyenlőtlenséget vizsgálja. Mivel az alternatívák k száma nő, így vele együtt nő annak az esélye, hogy egy olyan x max -ot találunk, melyre Δ( T 0 , T x max )α . Kivéve ha a Δ nyereségfüggvényt, vagy az α küszöbértéket a k nagyságához nem igazítjuk, az algoritmus akaratlanul is hamis csúcsokat ad hozzá a modellhez, ami modell túlillesztéshez vezet.

Ez a hatás egyre kifejezettebb lesz, ha a tanulórekordok, ahonnan x max -ot választjuk, száma kicsi, mert Δ( T 0 , T x max ) varianciája nagy, ha kevesebb eset áll a tanítás rendelkezésére. Ennek eredményeként ha nagyon kevés tanulórekord van, akkor nő annak a valószínűsége, hogy egy olyan x max -ot találunk, melyre Δ( T 0 , T x max )α . Ez gyakran előfordul, amikor a döntési fa mély lesz, ami viszont csökkenti a csúcsok által lefedett rekordok számát, és növeli annak valószínűségét, hogy felesleges csúcsot adunk a fához. A nagy számú alternatíva vagy a kis számú tanulórekord hibájának kompenzálása ezért modell túlillesztéshez vezet.

Általánosítási hibák becslése

Bár a túlillesztés elsődleges oka még mindig vita tárgya, általában egyetértenek abban, hogy a modell bonyolultsága (összetettsége) hatással van a modell túlillesztésre, mint ahogy azt a 4.23. ábra mutatja. A kérdés az, hogyan határozzuk meg a megfelelő modell bonyolultságot? Ideális bonyolultságról akkor beszélünk, ha egy modell a legkisebb általánosítási hibát adja. A probléma az, hogy a tanuló algoritmus csak a tanulórekordokhoz fér hozzá a modell építése során (lásd a 4.3. ábrát). Nem ismeri a teszthalmazt, és így nem tudja, milyen jól fog majd működni a fa olyan rekordokon, amelyeket még sohasem látott. A legjobb, amit tehetünk, hogy megbecsüljük a felépített fa általánosítási hibáját. Ez a szakasz több módszert is ismertet a becslés végrehajtására.

Visszahelyettesítéses becslés használata

A visszahelyettesítéses becslés megközelítés feltételezi, hogy a tanulóhalmaz jól reprezentálja az összes adatot. Következésképpen a tanítási hiba, vagy más néven visszahelyettesítéses hiba használható arra, hogy az általánosítási hiba egy optimista becslését adja. E feltételezés szerint egy döntési fa következtetési algoritmus egyszerűen azt a modellt választja ki, mint végleges modellt, amelyik a legkisebb tanítási hibaarányt adja. A tanítási hiba ugyanakkor általában az általánosítási hiba rossz becslése.

4.27. ábra - Példa azonos tanulóadatokból előállított két döntési fára

Példa azonos tanulóadatokból előállított két döntési fára

  1. Példa.

    Tekintsük a.4.27. ábrán látható bináris döntési fákat. Tegyük fel, hogy mindkét fát ugyanazok a tanulóadatok generálják, és mindkettő a többségi osztálynak megfelelően hozza osztályozási döntéseit minden levélcsúcsban. Megjegyezzük, hogy a T L baloldali fa összetettebb, mert a T R jobboldali fa néhány levélcsúcsát terjesztettük ki. A baloldali fa tanítási hibaaránya e( T L )=4/24=0,167 , míg a jobboldali fa tanítási hibaaránya e( T R )=6/24=0,25 . A visszahelyettesítéses becslés alapján a baloldali fa jobb, mint a jobboldali fa.

A modell bonyolultságának beépítése

Mint már említettük, a modell túlillesztés esélye nő, amint a modell egyre bonyolultabbá válik. Emiatt inkább az egyszerűbb modelleket részesítjük előnyben. Ez a stratégia a jól ismert Occam borotvája (Occam’s razor) elv vagy a takarékosság elve:

  1. Definíció

(Occam borotvája) Két azonos általánosítási hibájú modell közül az egyszerűbb modellt részesítjük előnyben az összetettebb modellel szemben. Az Occam borotvája egy intuitív elv, mert egy bonyolult modellben a további összetevők a puszta véletlen miatt nagyobb eséllyel fognak illeszkedni. Einstein szavaival: ,,Tegyünk mindent a lehető legegyszerűbbé, de nem egyszerűbbé, mint ami valójában’’. Ezután két módszert mutatunk be a modell bonyolultság beépítésére osztályozási modellek kiértékelésénél.

Pesszimista hibabecslés

Az első megközelítés úgy számolja ki explicit módon az általánosítási hibát, mint a tanítási hiba és egy, a modell bonyolultságát leíró büntető tag összege. Az így kapott általánosítási hiba annak pesszimista hibabecslésének tekinthető. Legyen például n(t) a t csúcs által osztályozott tanulórekordok száma, e(t) pedig a tévesen osztályozott rekordok száma. Egy T döntési fa e g (T) pesszimista becslési hibáját az alábbiak szerint lehet kiszámítani:

e g (T)= i=1 k [e( t i )+Ω( t i )] i=1 k n( t i ) = e(T)+Ω(T) N t ,

ahol k a levélcsúcsok száma, e(T) a döntési fa teljes tanítási hibája, N t a tanulórekordok száma, Ω( t i ) pedig az egyes t i csúcsokhoz tartozó büntető tag.

  1. Példa.

Tekintsük a 4.27. ábrán látható bináris döntési fákat. Ha a büntető tag 0,5 -del egyenlő, akkor a baloldali fa pesszimista hibabecslése

e g ( T L )= 4+7×0,5 24 = 7,5 24 =0,3125

és a jobboldali fa pesszimista hibabecslése

e g ( T R )= 6+4×0,5 24 = 8 24 =0,3333.

Így a baloldali fa pesszimista hibaaránya jobb, mint a jobboldali fáé. A bináris fáknál a 0,5 -es büntető tag azt jelenti, hogy egy csúcsot mindaddig ki kell terjeszteni a két gyerek csúcsára, amíg legalább egy tanulórekordon javul az osztályozás, mert egy csúcs kiterjesztése, amely 0,5 -nek a teljes hibához való hozzáadásával egyenértékű, kevésbé költséges, mint egy tanítási hiba elkövetése.

Ha Ω(t)=1 minden t csúcs esetén, akkor a baloldali fa pesszimista hibabecslése e g ( T L )=11/24=0,458 , míg a jobboldali fa pesszimista hibabecslése e g ( T R )=10/24=0,417 . A jobboldali fa ezért jobb pesszimista hibaaránnyal bír, mint a baloldali fa. Így egy csúcsot nem kell kiterjeszteni a gyerek csúcsaira, kivéve, ha egynél több tanulórekordnál csökken a téves osztályozás hibája.

Legrövidebb leíró hossz elve

Egy másik mód a modell bonyolultságának figyelembe vételére a legrövidebb leíró hosszon vagy MDL (Minimum Description Length) elven alapuló információelméleti megközelítés. Ezen elv szemléltetésére tekintsük a 4.28. ábrán látható példát. Ebben a példában A és B számára egyaránt rekordok egy halmaza adott, ismert x attribútumértékekkel. Ezen kívül az A személy ismeri minden egyes rekord pontos osztálycímkéjét, míg a B személy nem tudja ezt az információt. B megkaphatja az összes rekord osztályozását úgy, hogy kérésére A szekvenciálisan továbbítja neki az osztálycímkéket. Egy ilyen üzenet Θ(n) bit információt igényel, ahol n a rekordok száma.

4.28. ábra - A minimális leíró hossz (MDL) elv

A minimális leíró hossz (MDL) elv

Alternatívaként A dönthet úgy, hogy egy olyan osztályozási modellt épít, amely az x és y közötti kapcsolatot összegzi. A modell a B számára történő továbbítás előtt tömör formában kódolható. Ha a modell 100% -osan pontos, akkor az átvitel költsége egyenértékű a modell kódolásának költségével. Egyébként A azt az információt is át kell hogy küldje, hogy mely rekordot sorolta be helytelenül a modell. Így az átvitel teljes költsége

Költség(modell,adat)=Költség(model)+Költség(adat|modell), (4.9)

ahol a jobb oldalon az első tag a modell kódolásának költsége, míg a második tag a tévesen címkézett rekordok kódolásának költségét reprezetálja. Az MDL elv szerint egy olyan modellt kellene keresnünk, amely minimalizálja a teljes költségfüggvényt. A 207. oldalon a 9. feladatban található példa bemutatja, hogyan kell kiszámítani egy döntési fa teljes leíró hosszát.

Becslő statisztikai korlátok

Az általánosítási hiba a tanítási hiba statisztikai korrekciójaként is becsülhető. Mivel az általánosítási hiba hajlamos arra, hogy nagyobb legyen, mint a tanítási hiba, a statisztikai korrekciót általában a tanítási hiba felső korlátjaként számoljuk ki azon tanulórekordok számát figyelembe véve, amelyek egy adott levélcsúcsba kerülnek. A C4.5 döntési fa algoritmus például az egyes levélcsúcsok által elkövetett hibák számáról feltételezi, hogy binomiális eloszlást követ. Az általánosítási hiba kiszámításához a megfigyelt tanítási hiba felső korlátját kell meghatározni, amint azt a következő példa szemlélteti.

4.3. Példa.

Tekintsük a 4.27. ábrán látható bináris döntési fák bal szélső ágát. Figyeljük meg, hogy T R bal szélső levélcsúcsa két gyerek csúccsal bővült T L -ben. Vágás előtt a csúcs hibaaránya 2/7=0,286 . A binomiális eloszlást normális eloszlással közelítve az e hibaarányra a következő felső korlátot lehet levezetni:

e felső (N,e,α)= e+ Z α/2 2 2N + Z α/2 e(1e) N + Z α/2 2 4 N 2 1+ Z α/2 2 N , (4.10)

ahol α a megbízhatósági szint, Z α/2 a standard normális eloszlás α/2 kvantilise, N pedig az e kiszámításához használt összes tanulórekord száma. Az α=25% , N=7 és e=2/7 helyettesítéssel a hibaarány felső korlátja e felső (7;2/7;0,25)=0,503 , ami 7×0,503=3,521 hibának felel meg. Ha kiterjesztjük a csúcsot a gyerek csúcsaira ahogy T L mutatja, akkor a gyerek csúcsok tanítási hibaaránya egyenként 1/4=0,250 és 1/3=0,333 . (4.10) egyenletet használva ezeknek hibaarányoknak a felső határai egyenként e felső (4;1/4;0,25)=0,537 és e felső (3;1/3;0,25)=0,650 . A gyerek csúcsok teljes tanítási hibája így 4×0,537+3×0,650=4,098 , ami nagyobb, mint a T R -beli megfelelő csúcs becsült hibája.

Validációs halmaz használata

Ennél a megközelítésnél ahelyett, hogy az általánosítási hiba becslésére a tanulóhalmazt használnánk, az eredeti tanulóadatokat két kisebb részhalmazra bontjuk. Az egyik részhalmazt a tanításra használjuk, míg a másikat, az úgynevezett validációs (érvényesítő) halmazt (validation set), használjuk az általánosítási hiba becslésre. Általában a tanulóhalmaz kétharmadát a modellépítésére tartják fenn, míg a fennmaradó egyharmadot használják hibabecslésre.

Ezt a megközelítést általában olyan osztályozási módszereknél használják, amelyek úgy paraméterezhetőek, hogy különböző bonyolultsági szintű modellek adódnak. A legjobb modell bonyolultsága a tanuló algoritmus paraméterének a módosításával becsülhető (például egy döntési fa metszési szintje), míg a tanuló algoritmus által kapott empirikus modell a legalacsonyabb hibaarányt el nem éri a validációs halmazon. Bár ez a megközelítés jobb módot ad annak becslésére, hogy mennyire jól teljesít a modell a korábban nem látott rekordokon, kevesebb adat áll rendelkezésre a tanításra.

A túlillesztés kezelése döntési fa következtetésnél

Az előző szakaszban számos módszert írtunk le egy osztályozási modell általánosítási hibájának becslésére. Az általánosítási hiba egy megbízható becslése lehetővé teszi, hogy a tanuló algoritmus egy olyan pontos modellt találjon, amely nincs túlillesztve a tanulóadatokon. Ez a szakasz két stratégiát mutat be a modell túlillesztés elkerülésére döntési fa következtetési környezetben.

Előmetszés (prepruning, korai megállási szabály)

Ebben a megközelítésben a faépítő algoritmus megszakad, mielőtt előállítaná azt a teljesen kifejlett fát, amely tökéletesen illeszkedik a teljes tanulóhalmazra. Ehhez szigorúbb megállási feltételt kell alkalmazni, például meg kell állni egy levélcsúcs bővítésével, ha a szennyezettségi mértékben megfigyelt nyereség (vagy a becsült általánosítási hibában való javulás) nem ér el egy bizonyos küszöbértéket. Az az előnye ennek a megközelítésnek, hogy elkerüli olyan túlságosan bonyolult részfák előállítását, amelyek túlillesztődnek a tanulóhalmazon. Mindazonáltal nehéz kiválasztani a megfelelő küszöbértéket a korai leállásra. Túl magas küszöbérték alulillesztett modellt eredményez, míg a túl alacsony küszöbérték nem elegendő ahhoz, hogy úrrá legyünk a modell túlillesztési problémán. Továbbá, még ha nem is kaptunk szignifikáns nyereséget a létező attribútum tesztfeltételek egyikét használva, egy újabb vágás jobb részfát eredményezhet.

Utómetszés (postpruning)

Ebben a megközelítésben a döntési fát először a maximális méretére növeljük. Ezt egy fametszési lépés követi, amely során a teljesen kifejlett fát alulról felfelé haladóan lenyessük. A nyesést megtehetjük úgy, hogy a részfát helyettesítjük (1) egy olyan új levélcsúccsal, amelynek osztálycímkéjét a részfához tartozó rekordok többségi osztálya határozza meg, vagy (2) a részfa leggyakoribb ágával. A fa-metszést akkor fejezzük be, amikor további javulás már nem figyelhető meg. Az utómetszés általában jobb eredményt ad, mint az előmetszés, mert a nyesésről hozott döntés a teljesen kifejlett fán alapszik, ellentétben az előmetszéssel, amely a faépítési folyamat túl korai megszakításától szenved. Ugyanakkor utómetszésnél a teljes fa felépítéséhez szükséges további számítások hiábavalóak lehetnek, amikor a részfát lemetszük.

4.29. ábra - A döntési fa utómetszése web-robot észlelésnél

A döntési fa utómetszése web-robot észlelésnél

A 4.29. ábra az egyszerűsített döntési fa modellt szemlélteti 4.3.6. szakaszbeli web-robot észlelő példához. Figyeljük meg, hogy a depth=1 gyökerű részfa helyébe az ImagePages attribútumot bevonó ágak egyike kerül. Ez a megközelítés részfa növelés (subtree raising) néven is ismert. A depth1 és MultiAgent=0 részfát pedig egy a 0 osztályhoz rendelt levélcsúcs váltotta fel. Ez a megközelítés az úgynevezett részfa csere (subtree replacement). A depth1 és MultiAgent=1 részfa érintetlen marad.