Együttes módszerek

A fejezetben eddig látott osztályozási módszerek a legközelebbi szomszéd módszer kivételével ismeretlen esetek osztálycímkéit egyetlen a tanulóadatokból létrehozott osztályozó segítségével jelzik előre. Ez a szakasz módszereket mutat be az osztályozás pontosságának több osztályozó előrejelzéseinek összesítése általi javításához. Ezeket a módszereket együttes (ensemble) vagy kombinált osztályozó (classifier combination) módszereknek nevezik. Egy együttes módszer alaposztályozók (base classifier) egy halmazát hozza létre a tanulóadatokból és úgy végez osztályozást, hogy egy többségi szavazást tart az egyes alaposztályozók által adott előrejelzéseken. A fejezet megmagyarázza, hogy miért érnek el általában jobb eredményt az együttes módszerek, mint bármelyik osztályozó külön, és módszereket mutat be az osztályozó-együttes létrehozásához.

Az együttes módszer magyarázata

A következő példa szemlélteti, hogy hogyan javítja egy osztályozó teljesítményét egy együttes módszer.

5.7. Példa.

Vegyük huszonöt bináris osztályozó egy együttesét, amelyek mindegyikének hibaaránya ε=0,35 . Az együttes osztályozó úgy jelzi előre egy teszteset osztálycímkéjét, hogy egy többségi szavazást tart az alaposztályozók előrejelzései alapján. Ha az alaposztályozók azonosak, akkor az együttes ugyanazokat az eseteket osztályozza hibásan, amelyeket helytelenül prediktálnak az alaposztályozók. Így az együttes hibaaránya 0,35 marad. Másrészt ha az alaposztályozók függetlenek -- azaz a hibáik korrelálatlanok --, akkor az együttes csak akkor ad hibás előrejelzést, ha az alaposztályozók több mint fele helytelenül prediktál. Ebben az esetben az együttes osztályozó hibaaránya

e együttes = i=13 25 ( 25 i ) ε i (1ε) 25i =0,06, (5.66)

amely lényegesen kisebb, mint az alaposztályozók hibaaránya.

Az 5.30. ábra huszonöt bináris osztályozó egy együttesének hibaarányát ( e együttes ) mutatja különböző alaposztályozó hibaarányokra ( ε ). Az átlós vonal azt az esetet ábrázolja, amelyben az alaposztályozók azonosak, míg a folytonos vonal azt az esetet, amelyben az alaposztályozók függetlenek. Vegyük észre, hogy az együttes rosszabb eredményt ér el az alaposztályozóknál, amikor ε nagyobb, mint 0,5 .

5.30. ábra - Az alaposztályozók hibái és az együttes osztályozó hibái közötti összehasonlítás

Az alaposztályozók hibái és az együttes osztályozó hibái közötti összehasonlítás

Az előbbi példa két szükséges feltételét szemlélteti annak, hogy egy együttes osztályozó jobb eredményt érjen el, mint egyetlen osztályozó: (1) az alaposztályozók függetlenek kell, hogy legyenek egymástól, (2) az alaposztályozók jobb eredmény kell, hogy elérjenek, mint egy véletlen találgatást végző osztályozó. A gyakorlatban bonyolult az alaposztályozók közötti teljes függetlenség biztosítása. Mindazonáltal az osztályozási pontosságok javulását figyelték meg olyan együttes módszerekben, amelyekben az alaposztályozók gyengén korreláltak.

Módszerek együttes osztályozó építésére

Az együttes módszer egy logikai nézetét az 5.31. ábra mutatja be. Az alapötlet az eredeti adatokból több osztályozó alkotása, és az ismeretlen esetek osztályozásánál az előrejelzéseik összesítése. Az osztályozók együttese sokféleképpen alkotható meg:

5.31. ábra - Az együttes tanulási módszer egy logikai nézete

Az együttes tanulási módszer egy logikai nézete

  1. A tanulóhalmaz manipulálásával. Ebben a megközelítésben több tanulóhalmazt hozunk létre az eredeti adatok valamilyen mintavételi eloszlás szerinti újramintavételezésével. A mintavételi eloszlás meghatározza, hogy mennyire valószínű az, hogy egy eset kerül kiválasztásra a tanításhoz, ez kísérletenként változhat. Ezután egy osztályozót építünk minden egyes tanulóhalmazból egy adott tanuló algoritmus segítségével. A zsákolás (bagging) és gyorsítás (boosting) két példa a tanulóhalmazt manipuláló együttes módszerekre. Ezeket a módszereket részletesebben az 5.6.4. és 5.6.5. szakaszok írják le.

  2. A bemeneti jellemzők manipulálásával. Ebben a megközelítésben a bemeneti jellemzők egy részhalmazát választjuk ki minden egyes tanulóhalmaz képzéséhez. A részhalmaz választható véletlenszerűen vagy szakterületi szakértők ajánlása alapján. Néhány tanulmány azt mutatja, hogy a módszer nagyon jól működik erősen redundáns jellemzőket tartalmazó adatokkal. Az 5.6.6. szakaszban ismertetett véletlen erdő (random forest) egy együttes módszer, amely a bemeneti jellemzőket manipulálja és döntési fákat használ fel alaposztályozókként.

  3. Az osztálycímkék manipulálásával. Ez a módszer akkor használható fel, ha az osztályok száma elegendően nagy. A tanulóadatokat egy bináris osztályozási feladattá alakítjuk úgy, hogy az osztálycímkéket véletlenszerűen két diszjunkt halmazra ( A 0 és A 1 ) osztjuk. A 0. osztályhoz rendeljük azokat a tanulóeseteket, amelyek osztálycímkéje az A 0 részhalmazhoz tartozik, míg az 1. osztályhoz azokat, amelyeké az A 1 részhalmazhoz. Ezután az átcímkézett eseteket használjuk egy alaposztályozó tanításához. Az osztály átcímkéző és modellépítő lépés többszöri megismétlésével alaposztályozók egy együttesét kapjuk. Használjuk mindegyik C i alaposztályozót az osztálycímke előrelzéséhez, amikor egy tesztesetet kapunk. Ha a tesztesetet a 0 . osztályba tartozóként prediktáljuk, akkor minden A 0 -hoz tartozó osztály egy szavazatot kap. Ennek megfelelően, ha az 1 . osztályba tartozóként prediktáljuk, akkor minden A 1 -hez tartozó osztály egy szavazatot kap. Összesítjük a szavazatokat, és a legtöbb szavazatot kapó osztályhoz rendeljük hozzá a tesztesetet. Erre a megközelítésre egy példa a 315. oldalon ismertetett hibajavító kimeneti kódolás (error-correcting output coding).

  4. A tanuló algoritmus manipulálásával. Sok tanuló algoritmus manipulálható úgy, hogy az algoritmus többször egymás utáni alkalmazása ugyanazokra a tanulóadatokra különböző modelleket eredményezhet. Például egy mesterséges neurális háló különböző modelleket alkothat a hálózati topológia vagy a neuronok közötti kapcsolatok kezdeti súlyainak megváltoztatásával. Hasonlóan alkotható döntési fák egy együttese a faépítő eljárásba véletlenszerűség juttatásával. Például ahelyett, hogy minden egyes csomópontban a legjobb vágó attribútumot választanánk, vágáshoz válaszhatjuk véletlenszerűen a legjobb k attribútum egyikét.

5.5. algoritmus. Az együttes módszer általános eljárása

1: Jelölje D az eredeti tanulóadatokat, k az alaposztályozók számát és T a tesztadatokat

2: for i=1 to k do

3: Hozzuk létre a Di tanulóhalmazt D-ből

4: Építsünk egy Ci alaposztályozót Di-ből

5: end for

6: for minden xT tesztrekordra do

7: C*(x)=Szavazás(C1(x),C2(x), …, Ck(x))

8: end for

Az első három megközelítés tetszőleges osztályozóra alkalmazható általános módszer, míg a negyedik megközelítés a használt osztályozó típusától függ. Ezeknek a módszereknek a többségéhez az alaposztályozókat szekvenciálisan (egymás után) vagy párhuzamosan (egyszerre) lehet generálni. Az 5.5. algoritmus mutatja egy együttes osztályozó szekvenciális építéséhez szükséges lépéseket. Az első lépés, hogy hozzunk létre egy tanulóhalmazt a D eredeti adatokból. A használt együttes módszer típusától függően a tanulóhalmazok azonosak D -vel vagy annak kismértékű módosításai. A tanulóhalmaz mérete gyakran megegyezik az eredeti adatokéval, de az esetek eloszlása eltérhet, azaz bizonyos esetek többször is előfordulhatnak a tanulóhalmazban, míg mások lehet, hogy egyszer sem. Ezután minden egyes D i tanulóhalmazból egy C i alaposztályozót hozunk létre. Az együttes módszerek jobban működnek instabil osztályozókkal, azaz olyan alaposztályozókkal, amelyek érzékenyek a tanulóhalmaz kis perturbációira. Instabil osztályozók például a döntési fák, a szabályalapú osztályozók és a mesterséges neurális hálók. Ahogyan az 5.6.3. szakaszban tárgyalásra kerül majd, egy osztályozóban az elsődleges hibaforrások egyike a tanulóesetek közötti variabilitás. A különböző tanulóhalmazokból épített alaposztályozók aggregálása segítséget nyújthat az ilyen típusú hibák csökkentéséhez.

Végül egy x tesztesetet úgy osztályozunk, hogy kombináljuk a C i (x) alaposztályozók által adott előrejelzéseket:

C * (x)=Szavazás( C 1 (x), C 2 (x),, C k (x)).

Az osztály megkapható az egyes előrejelzéseken egy többségi szavazást végezve vagy az előrejelzéseknek az alaposztályozó pontosságával történő súlyozásával.

Torzítás-variancia felbontás

A torzítás-variancia felbontás egy formális módszer egy prediktív modell előrejelzési hibájának elemzéséhez. A következő példa a módszer egy intuíción alapuló magyarázatát adja.

5.32. ábra - Torzítás-variancia felbontás

Torzítás-variancia felbontás

Az 5.32. ábra egy bizonyos szögben kilőtt lövedék röppályáit mutatja. Feltételezzük, hogy a lövedék egy bizonyos x pontban ér földet, d távolságra a t célpozíciótól. A megfigyelt távolság kísérletről kísérletre változhat a lövedékre ható erőtől függően. A megfigyelt távolság több komponensre bontható fel. Az első komponens -- amelyet torzításnak (bias) neveznek -- a célpont és a lövedék földetérésének helye közötti átlagos távolságot méri. A torzítás mértéke a lövedék kilövőszerkezet szögétől függ. A második komponens -- amelyet varianciának (variance) neveznek -- x és és a lövedék földetérésének x Ż átlagos pozíciója közötti eltérést méri. A variancia a lövedékre ható erő mértékében történő változások eredményeként magyarázható. Végül ha a célpont nem mozdulatlan, akkor a megfigyelt távolságra a célpont helyének változásai is hatással vannak. Ezt tekintjük a célpozíció változékonyságához tartozó zaj komponensnek. A komponenseket egymás mellé téve az átlagos távolság az alábbi módon fejezhető ki:

d f,θ (y,t)  =   Torzítás θ +   Variancia f +   Zaj t , (5.67)

ahol f az erőhatás mértékét jelenti, θ pedig a kilövőszerkezet szöge.

Egy adott eset címkéjének előrejelzésének feladata elemezhető ugyanennek a megközelítésnek a segítségével. Egy adott osztályozó esetén bizonyos előrejelzésekről kiderülhet, hogy helyesek, míg a többiek teljesen rosszak lehetnek. Egy osztályozó várható hibáját (5.67) egyenletben adott három tag összegére bonthatjuk fel, ahol a várható hiba annak valószínűsége, hogy az osztályozó hibásan osztályoz egy esetet. A szakasz hátralevő része a torzítás, variancia és zaj jelentését vizsgálja az osztályozással összefüggésben.

Egy osztályozót általában a tanulóhalmazon vett hiba minimalizálására tanítunk. Ahhoz azonban, hogy hasznos legyen, az osztályozónak képesnek kell lennie korábban soha nem látott esetek osztálycímkéiről megalapozott javaslatot adni. Ehhez szükséges, hogy az osztályozó olyan területekre általánosítsa a döntési határát, amelyekben nem állnak rendelkezésre tanulóesetek. Ez egy olyan döntés, amely az osztályozó tervezéskori választásától függ. A döntési fa indukciónál például egy kulcsfontosságú tervezési kérdés egy kis várható hibájú döntési fa nyeréséhez szükséges nyesés. Az 5.33. ábrán két döntési fa látható, T 1 és T 2 , amelyek ugyanazokból a tanulóadatokból lettek létrehozva, de a bonyolultságuk különböző. T 2 -t T 1 addig nyesésével kapjuk, amíg egy legfeljebb két mélységű fához nem jutunk. Másrészt azonban a T 1 döntési fán alig történik nyesés. Ezek a tervezési választások torzítást hoznak be az osztályozóba, amely hasonló az előző példában leírt lövedék kilövőszerkezet torzításához. Általában minél erősebbek az osztályozónak a döntési határának a jellegére vonatkozó feltételezései, annál nagyobb lesz az osztályozó torzítása. Emiatt T 2 torzítása nagyobb, mivel T 1 -hez képest erősebb feltételezésekkel él a döntési határával kapcsolatban (amelyet a fa mérete tükröz). A mesterséges neurális hálók topológiája és a legközelebbi szomszéd osztályozó által tekintett szomszédok száma azok közé a további tervezési választások közé tartoznak, amelyek torzítást vezethetnek be egy osztályozóba.

5.33. ábra - Induktív tanulással ugyanazokból a tanulóadatokból létrehozott két külöböző bonyolultságú döntési fa

Induktív tanulással ugyanazokból a tanulóadatokból létrehozott két külöböző bonyolultságú döntési fa

Egy osztályozó várható hibáját befolyásolja a tanulóadatok változékonysága is, mert a különböző összetételű tanulóhalmazok különböző döntési határokhoz vezethetnek. Hasonló ez x varianciájához, amikor különböző mértékű erők hatnak a lövedékre. A várható hiba utolsó komponense a célosztályban található belső zajhoz tartozik. A célosztály néhány feladatkörben nemdeterminisztikus lehet, azaz ugyanazokkal az attribútumértékekkel rendelkező példányoknak különböző osztálycímkéi lehetnek. Az ilyen hibák még akkor is elkerülhetetlenek, amikor ismert a tényleges döntési határ.

A várható hibához hozzájáruló torzítás és variancia mértéke a használt osztályozó típusától függ. Az 5.34. ábra egy döntési fa és egy 1-legközelebbi szomszéd osztályozó által előállított döntési határokat hasonlítja össze. Minden egyes osztályozóhoz azt a döntési határt ábrázoljuk, amelyet 100 olyan tanulóhalmazból származtatott modell ``átlagolásával'' kapunk, amelyek mindegyike 100 esetet tartalmaz. Egy szaggatott vonallal ábrázoltuk a tényleges döntési határt is, amelyből az adatokat előállítottuk. A tényleges döntési határ és az ``átlagolt'' döntési határ közötti különbség az osztályozó torzítását tükrözi. A modellek átlagolása után vegyük észre, hogy a tényleges döntési határ és az 1-legközelebbi szomszéd osztályozó által előállított döntési határ közötti eltérés kisebb, mint a döntési fa osztályozónál megfigyelt eltérés. Ez az eredmény arra utal, hogy egy 1-legközelebbi szomszéd osztályozó torzítása kisebb, mint egy döntési fa osztályozó torzítása.

5.34. ábra - Döntési fa és 1-legközelebbi szomszéd osztályozó torzítása

Döntési fa és 1-legközelebbi szomszéd osztályozó torzítása

Másrészt az 1-legközelebbi szomszéd osztályozó érzékenyebb a tanulóesetek összetételére. Ha különböző tanulóhalmazokból származtatott modelleket vizsgálunk, egy 1-legközelebbi szomszéd osztályozó döntési határának nagyobb a variabilitása, mint egy döntési fának. Emiatt kisebb egy döntési fa osztályozó döntési határának varianciája, mint az 1-legközelebbi szomszéd osztályozónak.

Zsákolás

A bootstrap aggregálásnak (bootstrap aggregating) is nevezett zsákolás egy módszer, amely egyenletes eloszlás szerint ismétlődően (visszatevéssel) mintavételez egy adathalmazt. Minden egyes bootstrap minta ugyanolyan méretű, mint az eredeti adatok. Mivel a mintavételezés visszatevéssel történik, bizonyos esetek többször is szerepelhetnek ugyanabban a tanulóhalmazban, míg mások kihagyhatók a tanulóhalmazból. Egy D i bootstrap minta átlagosan az eredeti tanulóadatok 63%-át tartalmazza, mert minden egyes eset D i -be kiválasztásának 1 (11/N) N a valószínűsége. Ha N elég nagy, akkor a valószínűség az 11/e;0,632 értékhez tart. A zsákolás alapalgoritmusát az 5.6. algoritmus foglalja össze. Miután k osztályozót tanítottunk, egy tesztesetet a legtöbb számú szavazatot kapó osztályhoz rendelünk hozzá.

5.6. algoritmus. A zsákolás algoritmusa

1: Legyen k a bootstrap minták száma

2: for i=1 to k do

3: Hozzunk létre egy N méretű Di bootstrap mintát

4: Tanítsunk egy Ci alaposztályozót a Di bootstrap mintán

5: end for

6: C*(x)= argmax y i δ( C i (x)=y)

{ δ(.)=1 , ha igaz az argumentuma, 0 egyébként }

A zsákolás működésének szemléltetéséhez tekintsük az 5.4. táblázatban látható adatokat. Jelöljön x egy egydimenziós attribútumot és jelölje y az osztálycímkét. Tételezzük fel, hogy egy osztályozót alkalmazunk, amely csak egyszintű bináris döntési fákat származtat, egy xk tesztfeltétellel, ahol k egy vágási pont, amelyet úgy határozunk meg, hogy minimalizálja a levélcsúcsok entrópiáját. Egy ilyen fa úgy is ismert, mint egy döntési tönk (decision stump).

5.4. táblázat - Példa zsákoló osztályozók egy együttesének építéséhez felhasznált adatokra

x

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1

y

1

1

1

1

1

1

1

1

1

1


5.35. ábra - Példa zsákolásra

Példa zsákolásra

Zsákolás nélkül a legjobb döntési tönk, amit előállíthatunk x0,35 -nél vagy x0,75 -nél osztja ketté a rekordokat. A fa pontossága mindenképpen legfeljebb 70%. Tételezzük fel, hogy a zsákolási eljárást tíz bootstrap minta felhasználásával alkalmazzuk az adatokra. Az 5.35. ábrán láthatók az egyes zsákolási menetekben tanításhoz kiválasztott esetek. Minden tábla jobb oldalán szemléltetjük az osztályozó által létrehozott döntési határt is.

Az 5.4. táblázatban adott teljes adathalmazt úgy osztályozzuk, hogy egy többségi szavazást tartunk az egyes alaposztályozók által adott előrejelzések között. Az 5.36. ábrán láthatók az előrejelzések eredményei. Mivel az osztálycímkék 1 -ek vagy +1 -ek, a többségi szavazás ekvivalens az y -ra előrejelzett értékek összadásával és az eredményül kapott összeg előjelének vizsgálatával (lásd az utolsó előtti sort az 5.36. ábrán). Vegyük észre, hogy az együttes osztályozó tökéletesen osztályozza az eredeti adatok mind a tíz esetét.

5.36. ábra - Példa a zsákolási módszer segítségével alkotott osztályozók kombinálására

Példa a zsákolási módszer segítségével alkotott osztályozók kombinálására

Az előbbi példa az együttes módszerek felhasználásának egy másik előnyét szemlélteti a célfüggvény reprezentációjának javítása szempontjából. Bár minden alaposztályozó egy döntési tönk, az osztályozók kombinálása egy kettő mélységű döntési fához vezethet.

A zsákolás az alaposztályozók varianciájának csökkentése által javítja az általánosítási hibát. A zsákolás teljesítménye az alaposztályozók stabilitásától függ. Ha egy alaposztályozó instabil, a zsákolás segít a tanulóadatok véletlen változásaihoz tartozó hibákat csökkenteni. Ha egy alaposztályozó stabil, azaz robusztus a tanulóhalmaz kis perturbációira, akkor az együttes hibáját elsősorban az alaposztályozó torzítása okozza. Ebben az esetben lehet, hogy a gyorsítás nem tudja jelentősen javítani az alaposztályozók teljesítményét. Akár ronthatja is az osztályozók teljesítményét, mivel az egyes tanulóhalmazok tényleges mérete megközelítőleg 37%-kal kisebb, mint az eredeti adatoké.

Végül mivel minden mintának azonos valószínűsége van a kiválasztásra, a zsákolás nem összpontosít semmilyen meghatározott mintára a tanulóadatokban. Ezért zajos adatokra alkalmazásnál kevésbé hajlamos a modell túlillesztésre.

Gyorsítás

A gyorsítás egy iteratív eljárás, ami a tanulóesetek eloszlásának adaptív módosítására szolgál, hogy az alaposztályozók a nehezen osztályozható esetekre összpontosítsanak. A zsákolástól eltérően a gyorsítás minden egyes tanulóesethez egy súlyt rendel hozzá, és a súlyt minden gyorsítási menet végén adaptív módon módosítja. A tanulóesetekhez hozzárendelt súlyokat az alábbiak szerint lehet felhasználni:

  1. Felhasználhatóak mintavételezési eloszlásként az eredeti adatokból egy bootstrap mintahalmaz választásához.

  2. Felhasználhatja őket az alaposztályozó egy a nagyobb súlyú esetek felé hajló modell megtanulásához.

Ez a szakasz egy algoritmust ír le, amely a tanulóhalmaz mintavételezési eloszlásának meghatározásához az esetek súlyait használja fel. Kezdetben minden esethez azonos súlyokat, 1/N -t rendelünk, hogy egyforma valószínűséggel legyenek kiválaszthatók a tanításhoz. Egy mintát választunk a tanulóesetek mintavételezési eloszlása szerint, hogy egy új tanulóhalmazt kapjunk. Ezután egy osztályozót származtatunk a tanulóhalmazból és az eredeti adatok minden esetét osztályozzuk vele. A tanulóesetek súlyait minden egyes gyorsítási menet végén módosítjuk. A helytelenül osztályozott esetek súlyait növeljük, míg a helyesen osztályozottak súlyait csökkentjük. Ez arra kényszeríti az osztályozót, hogy a következő iterációkban azokra az esetekre összpontosítson, amelyeket nehéz osztályozni.

A következő táblázat mutatja az egyes gyorsítási menetek során kiválasztott eseteket.

Gyorsítás (1. menet):

7

3

2

8

7

9

4

10

6

3

Gyorsítás (2. menet):

5

4

9

4

2

5

1

7

4

2

Gyorsítás (3. menet):

4

4

8

10

4

5

4

6

3

4

Kezdetben minden mintához ugyanazt a súlyt rendeljük. Bizonyos esetek azonban -- például a 3. és 7. -- egynél többször kerülhetnek kiválasztásra, mert a mintavételezés visszatevéssel történik. Ezután egy, az adatokból épített osztályozót használunk az összes eset osztályozásához. Tételezzük fel, hogy a 4. eset nehezen osztályozható. Ennek a mintának a súlyát növelni fogjuk a jövőbeli iterációkban, amennyiben ismételten tévesen osztályozzuk. Eközben nagyobb esélye van a következő menetben kiválasztásra azoknak az eseteknek is, amelyek az előző menetben nem lettek kiválasztva -- például az 1. és 5. eseteknek --, mivel az előrejelzéseik valószínűleg rosszak voltak az előző menetben. A gyorsítási menetek előrehaladtával a legnehezebben osztályozható esetek még inkább túlsúlyba kerülnek. A végső együttest az egyes gyorsítási menetekből nyert alaposztályozók összességeként kapjuk meg.

Az évek során a gyorsítási algoritmusnak számos implementációja került kifejlesztésre. Ezek az algoritmusok a következők tekintetében térnek el: (1) hogy hogyan történik a tanulóesetek súlyainak módosítása az egyes gyorsítási menetek végén, és (2) hogy hogyan történik az egyes osztályozók által adott előrejelzések kombinálása. Egy AdaBoost nevű implementációval foglalkozik a következő szakasz.

AdaBoost

Jelölje {( x j , y j )  |  j=1,2,,N} N számú tanulóeset egy halmazát. Az AdaBoost algoritmusban egy C i alaposztályozó fontossága a hibaarányától függ, amelynek definíciója

ε i = 1 N [ j=1 N w j   I( C i ( x j ) y j )], (5.68)

ahol I(p)=1 , ha a p predikátum igaz, 0 egyébként. Egy C i osztályozó fontosságát a következő paraméter adja meg:

α i = 1 2 ln( 1 ε i ε i ).

Megjegyezzük, hogy α i -nek nagy pozitív értéke van, ha a hibaarány közel van 0 -hoz, és nagy negatív értéke, ha a hibaarány közel van 1-hez, amint az az 5.37. ábrán látható.

5.37. ábra - α ábrázolása az ε tanulóhalmazon vett hiba függvényeként

α ábrázolása az ε tanulóhalmazon vett hiba függvényeként

Az α i paramétert felhasználjuk a tanulóesetek súlyainak módosításához is. A szemléltetéshez jelölje w i (j) az ( x i , y i ) esethez a j -edik gyorsítási menet során hozzárendelt súlyt. Az alábbi egyenlet adja meg az AdaBoost súlymódosítási mechanizmusát:

w i (j+1) = w i (j) Z j ×( e α j , haC j ( x i )= y i , e α j , haC j ( x i ) y i , (5.69)

ahol Z j normalizáló tényező, amely a i w i (j+1) =1 feltételt biztosítja.Az (5.69) (5.69) egyenletben megadott súlymódosítási formula növeli a hibásan osztályozott esetek súlyait és csökkenti azokét, amelyek helyesen osztályozottak.

Többségi szavazási séma helyett minden egyes C j osztályozó előrejelzését α j -nek megfelelően súlyozzuk. Ez a módszer lehetővé teszi az AdaBoost számára, hogy büntesse azokat a modelleket, amelyeknek gyenge a pontossága, például azokat, amelyek a korábbi gyorsítási menetben lettek létrehozva. Ezenkívül, ha bármelyik közbenső menet 50%-nál nagyobb hibaarányt ad, akkor a súlyokat visszaállítjuk az eredeti egyforma értékeikre, w i =1/N -re, és megismételjük az újramintavételezési eljárást. Az AdaBoost algoritmust az 5.7. algoritmus foglalja össze.

5.7. algoritmus. AdaBoost algoritmus

1: w = {wj=1/N | j=1,2,…,N} {az N eset súlyainak inicializálása}

2: Legyen k a gyorsítási menetek száma

3: for i=1 to k do

4: D z D , a z -hez legközelebbi k tanulóeset halmazának kiválasztása

5: y' = argmax v ( x i , y i ) D z I(v= y i )

6: Tanítsunk egy Ci alaposztályozót Di-n Alkalmazzuk Ci-t az eredeti tanulóhalmaz, D, valamennyi esetére

7: ε i = 1 N [ j w j   δ( C i ( x j ) y j )] {a súlyozott hiba kiszámítása}

8:if ε i 0,5 then

9: w = { w j =1/N  |  j=1,2,,N} az N {eset súlyainak visszaállítása}

10: Menjünk vissza a 4. lépésre

11: end if

12: α i = 1 2 ln 1 ε i ε i

13: Módosítsuk minden eset súlyát az (5.69) egyenlet szerint

14: end for

15: C * (x)= argmax y j=1 T α j δ( C j (x)=y))

Vizsgáljuk meg, hogy hogyan működik a gyorsítási módszer 20. táblázatban látható adatokra. Kezdetben minden mintelemnek azonos súlya van. Az 5.38. (a) ábrán láthatók a tanításhoz kiválasztott esetek három gyorsítási menet után. Minden mintaelem súlyát az (5.69) egyenlet segítségével módosítjuk minden egyes gyorsítási menet végén.

5.382. ábra - Példa gyorsításra

Példa gyorsításra

5.39. ábra - Példa az AdaBoost módszer segítségével alkotott osztályozók kombinálására

Példa az AdaBoost módszer segítségével alkotott osztályozók kombinálására

Gyorsítás nélkül a döntési tönk pontossága legfeljebb 70%. Az 5.39. (b) ábrán adjuk meg az előrejelzések eredményeit az AdaBoost használata esetén. Az együttes osztályozó végső előrejelzését úgy kapjuk meg, hogy az egyes alaposztályozók által adott előrejelzések súlyozott átlagát vesszük, amely az 5.39. (b) ábra utolsó sorában látható. Figyeljük meg, hogy az AdaBoost tökéletesen osztályozza a tanulóadatok minden esetét.

A gyorsítás egy fontos analitikus eredménye azt mutatja, hogy az együttes tanulóhalmazon vett hibáját a következő kifejezés korlátozza:

e együttes i [ ε i (1 ε i ) ], (5.70)

ahol ε i az i -edik alaposztályozó hibaaránya. Ha a hibaarány kisebb mint 50%, akkor ε i =0,5 γ i írható, ahol γ i azt méri, hogy mennyivel jobb az osztályozó a véletlen találgatásnál. Az együttes osztályozó tanulóhalmazon vett hibájára a korlát az alábbi lesz:

e együttes i 14 γ i 2 exp(2 i γ i 2 ). (5.71)

Ha γ i γ* minden i -re, akkor az együttes osztályozó tanulóhalmazon vett hibája exponenciálisan csökken, amely az algoritmus gyors konvergenciájához vezet. Mindazonáltal a gyorsítási módszer meglehetősen érzékeny a túlillesztésre, mert hajlamos a tévesen osztályozott tanulóesetekre fókuszálni.

Véletlen erdők

A véletlen erdők az együttes módszerek egy olyan osztályát képviselik, amelyeket kifejezetten döntési fa osztályozókhoz terveztek. Több döntési fa által adott előrejelzéseket kombinálnak, ahol mindegyik fa véletlen vektorok egy független halmazának értékei alapján kerül létrehozásra, ahogyan az az 5.40. ábrán látható. A véletlen vektorok egy rögzített valószínűségi eloszlásból jönnek létre, ellentétben az AdaBoost-ban használt adaptív módszertől, ahol a valószínűségi eloszlás módosításra kerül, hogy azokra az esetekre koncentráljon, amelyeket nehéz osztályozni. A döntési fákat felhasználó zsákolás a véletlen erdők egy speciális esete, ahol úgy viszünk véletlenszerűséget a modellépítő eljárásba, hogy az eredeti tanulóhalmazból véletlenszerűen választunk visszatevéssel N mintát. A zsákolás a teljes modellépítő eljárás során ugyanazt az egyenletes valószínűségi eloszlást használja a bootstrap minták előállításához is.

5.40. ábra - Véletlen erdők

Véletlen erdők

Elméletileg bizonyított, hogy a véletlen erdők általánosítási hibájának felső korlátja a következő kifejezéshez konvergál, amikor a fák száma elég nagy:

általánosítási hiba   ρ Ż (1 s 2 ) s 2 , (5.72)

ahol ρ Ż a fák közötti átlagos korreláció, s pedig egy a fa osztályozók ``erejét'' mérő mennyiség. Osztályozók egy halmazának ereje az osztályozók átlagos teljesítményét jelenti, ahol a teljesítményt valószínűségileg mérjük az osztályozók margói szerint:

Margó:    M(X,Y)=P( Y ̂ θ =Y) max ZY P( Y ̂ θ =Z), (5.73)

ahol Y ̂ θ az X egy valamilyen θ véletlen vektorból épített osztályozó szerint prediktált osztálya. Minél nagyobb a margó, annál valószínűbb, hogy az osztályozó helyesen prediktál egy adott X esetet. Az (5.72) egyenlet elég intuitív: amint a fák erősebben korrelálttá válnak vagy csökken az osztályozó-együttes ereje, nő az általánosítási hiba korlátja. A randomizálás úgy segít csökkenteni a döntési fák közötti korrelációt, hogy az osztályozó-együttes általánosítási hibája javítható.

Minden döntési fa egy valamilyen rögzített valószínűségi eloszlásból generált véletlen vektort használ fel. Sokféleképpen építhető be a faépítő folyamatba egy véletlen vektor. Az első módszer az, hogy válasszunk véletlenszerűen F számú bemeneti jellemzőt a döntési fa minden csúcsának vágásához. Következésképpen, az összes jellemző vizsgálata helyett egy csúcs vágásához, a döntés meghatározása ebből az F kiválasztott jellemzőből történik. A fát ezután nyesés nélkül építjük teljes egésszé. Ez segít csökkenteni a létrejött fában jelenlévő torzítást. A fák megalkotását követően az előrejelzéseket egy többségi szavazási séma segítségével kombináljuk. Ez a módszer Forest-RI néven ismert, ahol RI a véletlenszerű bemenet kiválasztást (random input selection) jelenti. A véletlenszerűség növeléséhez a zsákolás is felhasználható ahhoz, hogy bootstrap mintákat generáljunk a Forest-RI számára. A véletlen erdők ereje és korrelációja F nagyságától függhet. Ha F elég kicsi, akkor a fák általában gyengébben korrelálttá válnak. Másrészt, a fa osztályozó ereje hajlamos javulni a jellemzők F számának növekedésével. Kompromisszumként a jellemzők számára szokásos választás F= log 2 d+1 , ahol d a bemeneti jellemzők száma. Mivel csak a jellemzők egy részhalmazát kell megvizsgálni minden egyes csúcsban, ez a módszer segít jelentősen csökkenteni az algoritmus futásidejét.

Ha az eredeti jellemzők d száma túl kicsi, akkor bajos a döntési fa építéséhez véletlen jellemzők egy független halmazát kiválasztani. A jellemzők terének növelésének egy módja a bemeneti jellemzők lináris kombinációinak képzése. Nevezetesen, minden egyes csúcsban egy új jellemzőt generálunk véletlenszerűen kiválasztva a bemeneti jellemzők közül L számút. A bemeneti jellemzőket a [1;1] tartományon egyenletes eloszlásból generált együtthatókkal kombináljuk lineárisan. Minden csúcsban F ilyen véletlenszerűen kombinált új jellemzőt generálunk, ezt követően pedig közülük a legjobbat választjuk a csúcs vágásához. Ez a módszer Forest-RC néven ismert.

Egy harmadik módszer a véletlen fák generálásához a döntési fa minden csúcsában az F legjobb vágás egyikének véletlenszerű választása. Ez a módszer erősebben korrelált fákat generálhat potenciálisan, mint a Forest-RI és Forest-RC, hacsak nem megfelelően nagy F . Nem rendelkezik a Forest-RI és Forest-RC futásidő-megtakarításaival sem, mivel az algoritmus a döntési fa minden egyes csúcsában meg kell, hogy vizsgálja az összes vágási jellemzőt.

Tapasztalatilag igazolható, hogy a véletlen erdők osztályozási pontosságai elég hasonlóak az AdaBoost algoritmushoz. Robusztusabbak a zajra és sokkal gyorsabbak is, mint az AdaBoost algoritmus. A következő szakaszban hasonlítjuk össze a különféle együttes módszerek osztályozási pontosságait.

Együttes módszerek közötti empirikus összehasonlítás

Az 5.5. táblázat mutatja egy döntési fa zsákolással, gyorsítással és véletlen erdővel kapott teljesítménye összehasonlításának tapasztalati eredményeit. Mindegyik együttes módszer ötven döntési fából álló alaposztályozókat használ. A táblázatban közölt osztályozási pontosságokat 10-szeres keresztellenőrzésből kaptuk. Vegyük észre, hogy az együttes osztályozók általában sok adathalmazon felülmúlnak egyetlen döntési fa osztályozót.

5.5. táblázat - Döntési fa osztályozó pontosságának összehasonlítása három együttes módszer ellenében. (Az utolsó oszlopban RF a véletlen erdőt jelenti.)

Adathalmaz

Szám

Döntési

Zsákolás

Gyorsítás

RF

(attribútumok, osztályok,

fa (%)

(%)

(%)

(%)

rekordok)

Anneal

(39, 6, 898)

92,09

94,43

95,43

95,43

Australia

(15, 2, 690)

85,51

87,10

85,22

85,80

Auto

(26, 7, 205)

81,95

85,37

85,37

84,39

Breast

(11, 2, 699)

95,14

96,42

97,28

96,14

Cleve

(14, 2, 303)

76,24

81,52

82,18

82,18

Credit

(16, 2, 690)

85,8

86,23

86,09

85,8

Diabetes

(9, 2, 768)

72,40

76,30

73,18

75,13

German

(21, 2, 1000)

70,90

73,40

73,00

74,5

Glass

(10, 7, 214)

67,29

76,17

77,57

78,04

Heart

(14, 2, 270)

80,00

81,48

80,74

83,33

Hepatitis

(20, 2, 155)

81,94

81,29

83,87

83,23

Horse

(23, 2, 368)

85,33

85,87

81,25

85,33

Ionosphere

(35, 2, 351)

89,17

92,02

93,73

93,45

Iris

(5, 3, 150)

94,67

94,67

94,00

93,33

Labor

(17, 2, 57)

78,95

84,21

89,47

84,21

Led7

(8, 10, 3200)

73,34

73,66

73,34

73,06

Lymphography

(19, 4, 148)

77,03

79,05

85,14

82,43

Pima

(9, 2, 768)

74,35

76,69

73,44

77,60

Sonar

(61, 2, 208)

78,85

78,85

84,62

85,58

Tic-tac-toe

(10, 2, 958)

83,72

93,84

98,54

95,82

Vehicle

(19, 4, 846)

71,04

74,11

78,25

74,94

Waveform

(22, 3, 5000)

76,44

83,30

83,90

84,04

Wine

(14, 3, 178)

94,38

96,07

97,75

97,75

Zoo

(17, 7, 101)

93,07

93,07

95,05

97,03