Skip navigation

Véletlen erdők (Random Forests)

Előismeret

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 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.

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:

(5.72)

ahol a fák közötti átlagos korreláció, 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:

(5.73)

ahol az 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 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 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 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 nagyságától függhet. Ha 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 számának növekedésével. Kompromisszumként a jellemzők számára szokásos választás , ahol 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 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 számút. A bemeneti jellemzőket a tartományon egyenletes eloszlásból generált együtthatókkal kombináljuk lineárisan. Minden csúcsban 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 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 . 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.

[forrás: Bevezetés az adatbányászatba]