Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
˝ Random Forests - Véletlen erdok
Szabó Adrienn Adatbányászat és Webes Keresés Kutatócsoport
2010
sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Tartalom Fo˝ forrás:
Leo Breiman: Random Forests Machine Learning, 45, 5-32, 2001
Alapok Döntési fa ˝ Véletlen erdok ˝ építése Véletlen erdok Nem formálisan Formálisan Véletlen erdo˝ típusok ˝ jó tulajdonságai A véletlen erdok Belso˝ becslések Kiértékelés Klasszifikáció További eredmények Regresszió
sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
˝ építkezni fogunk: döntési fa Amibol Az egyes attribútumok értékei alapján a mintákat hierarchikusan csoportosítjuk. A levelek: osztálycímkék. ID
Gyártás helye
Kor
Motor
Szín
ccm
Jól eladható?
1
Németo.
3-6
dízel
fehér
1300-1600
igen
2
Japán
6-10
dízel
piros
1600 felett
igen
3
Japán
3-6
dízel
piros
1300-1600
nem
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Döntési fa • A jó döntési fa: példákkal konzisztens, minél tömörebb
(leheto˝ legkevesebb teszttel döntésre jussunk) Hogyan építsük fel? • Legegyszerubb ˝ az ID3 algoritmus:
˝ kezdve építjük a fát, mohó módon mindig úgy a gyökértol válasszunk döntési attribútumot egy csúcspontban, hogy az információnyereség ( IG(S, a) = H(S) − H(S|a) ) maximális legyen • Továbbfejlesztés: Information Gain helyett Gain Ratio, ami
nem súlyozza túl azokat az attribútumokat amik sok különbözo˝ értéket felvehetnek sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Döntési fa • A jó döntési fa: példákkal konzisztens, minél tömörebb
(leheto˝ legkevesebb teszttel döntésre jussunk) Hogyan építsük fel? • Legegyszerubb ˝ az ID3 algoritmus:
˝ kezdve építjük a fát, mohó módon mindig úgy a gyökértol válasszunk döntési attribútumot egy csúcspontban, hogy az információnyereség ( IG(S, a) = H(S) − H(S|a) ) maximális legyen • Továbbfejlesztés: Information Gain helyett Gain Ratio, ami
nem súlyozza túl azokat az attribútumokat amik sok különbözo˝ értéket felvehetnek sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Döntési fa • A jó döntési fa: példákkal konzisztens, minél tömörebb
(leheto˝ legkevesebb teszttel döntésre jussunk) Hogyan építsük fel? • Legegyszerubb ˝ az ID3 algoritmus:
˝ kezdve építjük a fát, mohó módon mindig úgy a gyökértol válasszunk döntési attribútumot egy csúcspontban, hogy az információnyereség ( IG(S, a) = H(S) − H(S|a) ) maximális legyen • Továbbfejlesztés: Information Gain helyett Gain Ratio, ami
nem súlyozza túl azokat az attribútumokat amik sok különbözo˝ értéket felvehetnek sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Döntési fa • A jó döntési fa: példákkal konzisztens, minél tömörebb
(leheto˝ legkevesebb teszttel döntésre jussunk) Hogyan építsük fel? • Legegyszerubb ˝ az ID3 algoritmus:
˝ kezdve építjük a fát, mohó módon mindig úgy a gyökértol válasszunk döntési attribútumot egy csúcspontban, hogy az információnyereség ( IG(S, a) = H(S) − H(S|a) ) maximális legyen • Továbbfejlesztés: Information Gain helyett Gain Ratio, ami
nem súlyozza túl azokat az attribútumokat amik sok különbözo˝ értéket felvehetnek sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
˝ Mik a véletlen erdok?
• Alapötlet: sok döntési fa, amik valamennyire különbözoek ˝ • Mindegyik tippel majd valamit, a szavazás
végeredményeként a leggykoribb választ fogadjuk el ˝ Az erdo˝ hatékonysága a következokön múlik: • generált fák számán (ált. ha több fa szavaz, javul az
˝ eredmény) és minoségén • generált fák közötti korreláción (ha no˝ a fák közötti
korreláció, az eredmény romlik)
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
˝ Mik a véletlen erdok?
• Alapötlet: sok döntési fa, amik valamennyire különbözoek ˝ • Mindegyik tippel majd valamit, a szavazás
végeredményeként a leggykoribb választ fogadjuk el ˝ Az erdo˝ hatékonysága a következokön múlik: • generált fák számán (ált. ha több fa szavaz, javul az
˝ eredmény) és minoségén • generált fák közötti korreláción (ha no˝ a fák közötti
korreláció, az eredmény romlik)
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
˝ Random forest elonyei
• Jó eredmények (pontos klasszifikáció) • Gyorsan lefut, nagy adatokra is használható • Több ezres dimenziójú bemenetet is képes kezelni • Becsléseket ad arra hogy mely változók fontosak • Hiányzó adatokat képes megbecsülni • Használható regresszióra; kis kiterjesztéssel
klaszterezésre vagy outlier-szurésre ˝ is
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Véletlen erdo˝ építése Breiman módszere: • Képezünk K döntési fát úgy, hogy bootstrapping-gal
˝ N-et sorsolunk) külön-külön (visszatevéses sorsolás, N-bol tanuló adathalmazt készítünk hozzájuk • Az egyes fák építésekor a csomópontokban az attribútum
választáskor a lehetséges attribútumhalmazt megszorítjuk egy jóval kisebb méreture ˝ véletlenszeru˝ választással. (Utána a max. IG-t vesszük) • Nyesést nem alkalmazunk a fákon
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Véletlen erdo˝ építése Breiman módszere: • Képezünk K döntési fát úgy, hogy bootstrapping-gal
˝ N-et sorsolunk) külön-külön (visszatevéses sorsolás, N-bol tanuló adathalmazt készítünk hozzájuk • Az egyes fák építésekor a csomópontokban az attribútum
választáskor a lehetséges attribútumhalmazt megszorítjuk egy jóval kisebb méreture ˝ véletlenszeru˝ választással. (Utána a max. IG-t vesszük) • Nyesést nem alkalmazunk a fákon
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Véletlen erdo˝ építése Breiman módszere: • Képezünk K döntési fát úgy, hogy bootstrapping-gal
˝ N-et sorsolunk) külön-külön (visszatevéses sorsolás, N-bol tanuló adathalmazt készítünk hozzájuk • Az egyes fák építésekor a csomópontokban az attribútum
választáskor a lehetséges attribútumhalmazt megszorítjuk egy jóval kisebb méreture ˝ véletlenszeru˝ választással. (Utána a max. IG-t vesszük) • Nyesést nem alkalmazunk a fákon
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Véletlen erdo˝ építése Breiman módszere: • Képezünk K döntési fát úgy, hogy bootstrapping-gal
˝ N-et sorsolunk) külön-külön (visszatevéses sorsolás, N-bol tanuló adathalmazt készítünk hozzájuk • Az egyes fák építésekor a csomópontokban az attribútum
választáskor a lehetséges attribútumhalmazt megszorítjuk egy jóval kisebb méreture ˝ véletlenszeru˝ választással. (Utána a max. IG-t vesszük) • Nyesést nem alkalmazunk a fákon
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Véletlen erdo˝ építése
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
˝ építése Véletlen erdok Az egyes fák egyes csúcsainál véletlenszeruen ˝ sorsolt attribútumokól választhatjuk csak ki a döntési attribútumot.
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Formális definíció
˝ Véletlen erdonek nevezzük azt az osztályozót amely döntési fák {h(x, θk ), k = 1, . . . K } halmazából áll ahol a {θk }-k független, azonos eloszlású random vektorok, és a fák többségi szavazással döntenek (minden fa egy-egy szavazatot adhat le egy-egy osztályozandó vektorra). ˝ Tétel: A fák számának növelésével a klasszifikáció minosége konvergál (nem lesz túltanulás). ˝ törvénye segítségével. Bizonyítás: Nagy számok eros
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Formális definíció
˝ Véletlen erdonek nevezzük azt az osztályozót amely döntési fák {h(x, θk ), k = 1, . . . K } halmazából áll ahol a {θk }-k független, azonos eloszlású random vektorok, és a fák többségi szavazással döntenek (minden fa egy-egy szavazatot adhat le egy-egy osztályozandó vektorra). ˝ Tétel: A fák számának növelésével a klasszifikáció minosége konvergál (nem lesz túltanulás). ˝ törvénye segítségével. Bizonyítás: Nagy számok eros
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Formális definíció Margin: minél nagyobb, annál biztosabb az eredmény; ha ˝ negatív akkor hibázott az erdo: mg(X, Y ) = avgk I(hk (X) = Y ) − max(avgk I(hk (X) = j)) j6=Y
(X: a bemeneti vektorok, Y : a hozzájuk tartozó osztályok) A döntési fák általánosítási hibája (generalization error): PE = PX,Y (mg(X, Y ) < 0)
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Formális definíció Margin: minél nagyobb, annál biztosabb az eredmény; ha ˝ negatív akkor hibázott az erdo: mg(X, Y ) = avgk I(hk (X) = Y ) − max(avgk I(hk (X) = j)) j6=Y
(X: a bemeneti vektorok, Y : a hozzájuk tartozó osztályok) A döntési fák általánosítási hibája (generalization error): PE = PX,Y (mg(X, Y ) < 0)
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
A fák ereje és korrelációja
Felso˝ korlát adható a véletlen erdo˝ általánosítási hibájára, ami két dologtól függ: • az egyes klasszifikátorok (döntési fák) pontosságától • a fák közötti korrelációtól
PE ≤ ρ(1 − s2 )/s2 ahol ρ az átlagos korreláció a fák között, és s a h(x, θ) klasszifikátorhalmaz ereje: s = EX,Y mg(X, Y )
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
A fák ereje és korrelációja
Felso˝ korlát adható a véletlen erdo˝ általánosítási hibájára, ami két dologtól függ: • az egyes klasszifikátorok (döntési fák) pontosságától • a fák közötti korrelációtól
PE ≤ ρ(1 − s2 )/s2 ahol ρ az átlagos korreláció a fák között, és s a h(x, θ) klasszifikátorhalmaz ereje: s = EX,Y mg(X, Y )
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Véletlen erdo˝ típusok • Egyszeru˝ bagging: lehetne belül más klasszifikátor is, de
döntési fa van • Random Split Selection: faépítésnél mindig a legjobb B
válozóból választunk egyet véletlenszeruen ˝ • Random Subspace: minden fát egy-egy rögzített,
véletlenül választott attribútumhalmaz alapján építünk fel • Breiman módszere: a fent bemutatott (bagging + random
m változóból a legjobb választása a facsúcsoknál, ahol m << M, ahol M az attribútumok száma; általában m < log2 M) sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Véletlen erdo˝ típusok • Egyszeru˝ bagging: lehetne belül más klasszifikátor is, de
döntési fa van • Random Split Selection: faépítésnél mindig a legjobb B
válozóból választunk egyet véletlenszeruen ˝ • Random Subspace: minden fát egy-egy rögzített,
véletlenül választott attribútumhalmaz alapján építünk fel • Breiman módszere: a fent bemutatott (bagging + random
m változóból a legjobb választása a facsúcsoknál, ahol m << M, ahol M az attribútumok száma; általában m < log2 M) sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Véletlen erdo˝ típusok • Egyszeru˝ bagging: lehetne belül más klasszifikátor is, de
döntési fa van • Random Split Selection: faépítésnél mindig a legjobb B
válozóból választunk egyet véletlenszeruen ˝ • Random Subspace: minden fát egy-egy rögzített,
véletlenül választott attribútumhalmaz alapján építünk fel • Breiman módszere: a fent bemutatott (bagging + random
m változóból a legjobb választása a facsúcsoknál, ahol m << M, ahol M az attribútumok száma; általában m < log2 M) sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Véletlen erdo˝ típusok • Egyszeru˝ bagging: lehetne belül más klasszifikátor is, de
döntési fa van • Random Split Selection: faépítésnél mindig a legjobb B
válozóból választunk egyet véletlenszeruen ˝ • Random Subspace: minden fát egy-egy rögzített,
véletlenül választott attribútumhalmaz alapján építünk fel • Breiman módszere: a fent bemutatott (bagging + random
m változóból a legjobb választása a facsúcsoknál, ahol m << M, ahol M az attribútumok száma; általában m < log2 M) sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
„Out-of-bag” becslések • A bagging alkalmazásának elonyei: ˝ a pontosságot növeli,
szórást csökkenti • Minden fánál a tanítómintából kihagyott értékekre („out-of
bag” vagy „OOB” értékek, ált. kb. a minták egyharmada) jóslatokat kérhetünk • Az eredményeket átlagolva elég pontosan becsülheto˝ az
erdo˝ hibája (PE), és a fák közötti korreláció is • Kb olyan pontos becsléseket kapunk a jóságra mintha egy
tanítóhalmaz méretu˝ teszthalmazunk lenne1 • Ezért nem kell Cross Validation-t alkalmazni
1
Breiman egy korábbi cikkének empirikus eredménye, akkor igaz ha K elég nagy (a hiba már konvergált).
sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
„Out-of-bag” becslések • A bagging alkalmazásának elonyei: ˝ a pontosságot növeli,
szórást csökkenti • Minden fánál a tanítómintából kihagyott értékekre („out-of
bag” vagy „OOB” értékek, ált. kb. a minták egyharmada) jóslatokat kérhetünk • Az eredményeket átlagolva elég pontosan becsülheto˝ az
erdo˝ hibája (PE), és a fák közötti korreláció is • Kb olyan pontos becsléseket kapunk a jóságra mintha egy
tanítóhalmaz méretu˝ teszthalmazunk lenne1 • Ezért nem kell Cross Validation-t alkalmazni
1
Breiman egy korábbi cikkének empirikus eredménye, akkor igaz ha K elég nagy (a hiba már konvergált).
sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
„Out-of-bag” becslések • A bagging alkalmazásának elonyei: ˝ a pontosságot növeli,
szórást csökkenti • Minden fánál a tanítómintából kihagyott értékekre („out-of
bag” vagy „OOB” értékek, ált. kb. a minták egyharmada) jóslatokat kérhetünk • Az eredményeket átlagolva elég pontosan becsülheto˝ az
erdo˝ hibája (PE), és a fák közötti korreláció is • Kb olyan pontos becsléseket kapunk a jóságra mintha egy
tanítóhalmaz méretu˝ teszthalmazunk lenne1 • Ezért nem kell Cross Validation-t alkalmazni
1
Breiman egy korábbi cikkének empirikus eredménye, akkor igaz ha K elég nagy (a hiba már konvergált).
sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
„Out-of-bag” becslések • A bagging alkalmazásának elonyei: ˝ a pontosságot növeli,
szórást csökkenti • Minden fánál a tanítómintából kihagyott értékekre („out-of
bag” vagy „OOB” értékek, ált. kb. a minták egyharmada) jóslatokat kérhetünk • Az eredményeket átlagolva elég pontosan becsülheto˝ az
erdo˝ hibája (PE), és a fák közötti korreláció is • Kb olyan pontos becsléseket kapunk a jóságra mintha egy
tanítóhalmaz méretu˝ teszthalmazunk lenne1 • Ezért nem kell Cross Validation-t alkalmazni
1
Breiman egy korábbi cikkének empirikus eredménye, akkor igaz ha K elég nagy (a hiba már konvergált).
sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
„Out-of-bag” becslések • A bagging alkalmazásának elonyei: ˝ a pontosságot növeli,
szórást csökkenti • Minden fánál a tanítómintából kihagyott értékekre („out-of
bag” vagy „OOB” értékek, ált. kb. a minták egyharmada) jóslatokat kérhetünk • Az eredményeket átlagolva elég pontosan becsülheto˝ az
erdo˝ hibája (PE), és a fák közötti korreláció is • Kb olyan pontos becsléseket kapunk a jóságra mintha egy
tanítóhalmaz méretu˝ teszthalmazunk lenne1 • Ezért nem kell Cross Validation-t alkalmazni
1
Breiman egy korábbi cikkének empirikus eredménye, akkor igaz ha K elég nagy (a hiba már konvergált).
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Fontos változók (Feature selection) ˝ Egy v bemeno˝ attribútum (feature) fontossága így becsülheto: • Minden fát szavaztassunk meg a hozzá tartozó „OOB”
bemenetekre • Jegyezzük meg a helyes válaszok arányát • Permutáluk meg az „OOB” halmazon belül a v változó
értékeit, és így is kérjünk jóslatokat a fától • A helyes válaszok aránya mennyivel csökkent? • Ezt átlagoljuk az összes fára =⇒ v fontossági értéke
˝ Nagyon sok bemeneti változó esetén eloször kiválaszthatjuk a ˝ jobbakat, aztán csak ezeket használva új, hatékonyabb erdot építhetünk. sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Fontos változók (Feature selection) ˝ Egy v bemeno˝ attribútum (feature) fontossága így becsülheto: • Minden fát szavaztassunk meg a hozzá tartozó „OOB”
bemenetekre • Jegyezzük meg a helyes válaszok arányát • Permutáluk meg az „OOB” halmazon belül a v változó
értékeit, és így is kérjünk jóslatokat a fától • A helyes válaszok aránya mennyivel csökkent? • Ezt átlagoljuk az összes fára =⇒ v fontossági értéke
˝ Nagyon sok bemeneti változó esetén eloször kiválaszthatjuk a ˝ jobbakat, aztán csak ezeket használva új, hatékonyabb erdot építhetünk. sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Fontos változók (Feature selection) ˝ Egy v bemeno˝ attribútum (feature) fontossága így becsülheto: • Minden fát szavaztassunk meg a hozzá tartozó „OOB”
bemenetekre • Jegyezzük meg a helyes válaszok arányát • Permutáluk meg az „OOB” halmazon belül a v változó
értékeit, és így is kérjünk jóslatokat a fától • A helyes válaszok aránya mennyivel csökkent? • Ezt átlagoljuk az összes fára =⇒ v fontossági értéke
˝ Nagyon sok bemeneti változó esetén eloször kiválaszthatjuk a ˝ jobbakat, aztán csak ezeket használva új, hatékonyabb erdot építhetünk. sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Fontos változók (Feature selection) ˝ Egy v bemeno˝ attribútum (feature) fontossága így becsülheto: • Minden fát szavaztassunk meg a hozzá tartozó „OOB”
bemenetekre • Jegyezzük meg a helyes válaszok arányát • Permutáluk meg az „OOB” halmazon belül a v változó
értékeit, és így is kérjünk jóslatokat a fától • A helyes válaszok aránya mennyivel csökkent? • Ezt átlagoljuk az összes fára =⇒ v fontossági értéke
˝ Nagyon sok bemeneti változó esetén eloször kiválaszthatjuk a ˝ jobbakat, aztán csak ezeket használva új, hatékonyabb erdot építhetünk. sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Fontos változók (Feature selection) ˝ Egy v bemeno˝ attribútum (feature) fontossága így becsülheto: • Minden fát szavaztassunk meg a hozzá tartozó „OOB”
bemenetekre • Jegyezzük meg a helyes válaszok arányát • Permutáluk meg az „OOB” halmazon belül a v változó
értékeit, és így is kérjünk jóslatokat a fától • A helyes válaszok aránya mennyivel csökkent? • Ezt átlagoljuk az összes fára =⇒ v fontossági értéke
˝ Nagyon sok bemeneti változó esetén eloször kiválaszthatjuk a ˝ jobbakat, aztán csak ezeket használva új, hatékonyabb erdot építhetünk. sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Fontos változók (Feature selection) ˝ Egy v bemeno˝ attribútum (feature) fontossága így becsülheto: • Minden fát szavaztassunk meg a hozzá tartozó „OOB”
bemenetekre • Jegyezzük meg a helyes válaszok arányát • Permutáluk meg az „OOB” halmazon belül a v változó
értékeit, és így is kérjünk jóslatokat a fától • A helyes válaszok aránya mennyivel csökkent? • Ezt átlagoljuk az összes fára =⇒ v fontossági értéke
˝ Nagyon sok bemeneti változó esetén eloször kiválaszthatjuk a ˝ jobbakat, aztán csak ezeket használva új, hatékonyabb erdot építhetünk. sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Fontos változók (Feature selection) ˝ Egy v bemeno˝ attribútum (feature) fontossága így becsülheto: • Minden fát szavaztassunk meg a hozzá tartozó „OOB”
bemenetekre • Jegyezzük meg a helyes válaszok arányát • Permutáluk meg az „OOB” halmazon belül a v változó
értékeit, és így is kérjünk jóslatokat a fától • A helyes válaszok aránya mennyivel csökkent? • Ezt átlagoljuk az összes fára =⇒ v fontossági értéke
˝ Nagyon sok bemeneti változó esetén eloször kiválaszthatjuk a ˝ jobbakat, aztán csak ezeket használva új, hatékonyabb erdot építhetünk. sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
A bemeneti vektorok hasonlóságának becslése Mire is jó ez? • Outlier-szurés: ˝ nagyon különbözo˝ ˝ Az összes többitol
˝ (pl. elrontott mérés), jobb tanítóminták zajnak tekinthetok ˝ ha kidobjuk ezeket. Akár osztályonként is szurhetjük ˝ oket. • Klaszterezés: A minták közti hasonlóság alapján
klaszterezést is végezhetünk. Hogyan? • Minden bemenet-párra vegyük azon fáknak az arányát
amikre ugyanabban a levélben ér véget a hozzájuk tartozó döntési folyamat. „Proximity”: si,j p • „Dissimilarity”: di,j = 1 − si,j sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
A bemeneti vektorok hasonlóságának becslése Mire is jó ez? • Outlier-szurés: ˝ nagyon különbözo˝ ˝ Az összes többitol
˝ (pl. elrontott mérés), jobb tanítóminták zajnak tekinthetok ˝ ha kidobjuk ezeket. Akár osztályonként is szurhetjük ˝ oket. • Klaszterezés: A minták közti hasonlóság alapján
klaszterezést is végezhetünk. Hogyan? • Minden bemenet-párra vegyük azon fáknak az arányát
amikre ugyanabban a levélben ér véget a hozzájuk tartozó döntési folyamat. „Proximity”: si,j p • „Dissimilarity”: di,j = 1 − si,j sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
A bemeneti vektorok hasonlóságának becslése Mire is jó ez? • Outlier-szurés: ˝ nagyon különbözo˝ ˝ Az összes többitol
˝ (pl. elrontott mérés), jobb tanítóminták zajnak tekinthetok ˝ ha kidobjuk ezeket. Akár osztályonként is szurhetjük ˝ oket. • Klaszterezés: A minták közti hasonlóság alapján
klaszterezést is végezhetünk. Hogyan? • Minden bemenet-párra vegyük azon fáknak az arányát
amikre ugyanabban a levélben ér véget a hozzájuk tartozó döntési folyamat. „Proximity”: si,j p • „Dissimilarity”: di,j = 1 − si,j sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
A bemeneti vektorok hasonlóságának becslése Mire is jó ez? • Outlier-szurés: ˝ nagyon különbözo˝ ˝ Az összes többitol
˝ (pl. elrontott mérés), jobb tanítóminták zajnak tekinthetok ˝ ha kidobjuk ezeket. Akár osztályonként is szurhetjük ˝ oket. • Klaszterezés: A minták közti hasonlóság alapján
klaszterezést is végezhetünk. Hogyan? • Minden bemenet-párra vegyük azon fáknak az arányát
amikre ugyanabban a levélben ér véget a hozzájuk tartozó döntési folyamat. „Proximity”: si,j p • „Dissimilarity”: di,j = 1 − si,j sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
A bemeneti vektorok hasonlóságának becslése Mire is jó ez? • Outlier-szurés: ˝ nagyon különbözo˝ ˝ Az összes többitol
˝ (pl. elrontott mérés), jobb tanítóminták zajnak tekinthetok ˝ ha kidobjuk ezeket. Akár osztályonként is szurhetjük ˝ oket. • Klaszterezés: A minták közti hasonlóság alapján
klaszterezést is végezhetünk. Hogyan? • Minden bemenet-párra vegyük azon fáknak az arányát
amikre ugyanabban a levélben ér véget a hozzájuk tartozó döntési folyamat. „Proximity”: si,j p • „Dissimilarity”: di,j = 1 − si,j sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
A bemeneti vektorok hasonlóságának becslése Mire is jó ez? • Outlier-szurés: ˝ nagyon különbözo˝ ˝ Az összes többitol
˝ (pl. elrontott mérés), jobb tanítóminták zajnak tekinthetok ˝ ha kidobjuk ezeket. Akár osztályonként is szurhetjük ˝ oket. • Klaszterezés: A minták közti hasonlóság alapján
klaszterezést is végezhetünk. Hogyan? • Minden bemenet-párra vegyük azon fáknak az arányát
amikre ugyanabban a levélben ér véget a hozzájuk tartozó döntési folyamat. „Proximity”: si,j p • „Dissimilarity”: di,j = 1 − si,j sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Hiányzó adatok kitöltése Iteratívan becsülhetjük a tanítóhalmaz hiányzó értékeit: • Elso˝ közelítés: vegyük a hiányzó attribútum átlagát (ill.
leggyakoribb értékét) a többi soron, és ezt helyettesítsük be • Az így kiegészített adatokkal építsünk erdot ˝ • Minden i adatsorhoz amiben f hiányzott, vegyük az összes
(nem-f -hiányos j sorral páronként vett hasonlóságait (si,j ) • Az új becslés: si,j súlyokkal átlagoljuk a j-kben talált
f -értékeket, ezt tegyük if -be • Ezt iterálhatjuk (új erdo˝ építése, stb.) amíg már nem
változnak az értékek (általában 4-6 kör elég) sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Hiányzó adatok kitöltése Iteratívan becsülhetjük a tanítóhalmaz hiányzó értékeit: • Elso˝ közelítés: vegyük a hiányzó attribútum átlagát (ill.
leggyakoribb értékét) a többi soron, és ezt helyettesítsük be • Az így kiegészített adatokkal építsünk erdot ˝ • Minden i adatsorhoz amiben f hiányzott, vegyük az összes
(nem-f -hiányos j sorral páronként vett hasonlóságait (si,j ) • Az új becslés: si,j súlyokkal átlagoljuk a j-kben talált
f -értékeket, ezt tegyük if -be • Ezt iterálhatjuk (új erdo˝ építése, stb.) amíg már nem
változnak az értékek (általában 4-6 kör elég) sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Hiányzó adatok kitöltése Iteratívan becsülhetjük a tanítóhalmaz hiányzó értékeit: • Elso˝ közelítés: vegyük a hiányzó attribútum átlagát (ill.
leggyakoribb értékét) a többi soron, és ezt helyettesítsük be • Az így kiegészített adatokkal építsünk erdot ˝ • Minden i adatsorhoz amiben f hiányzott, vegyük az összes
(nem-f -hiányos j sorral páronként vett hasonlóságait (si,j ) • Az új becslés: si,j súlyokkal átlagoljuk a j-kben talált
f -értékeket, ezt tegyük if -be • Ezt iterálhatjuk (új erdo˝ építése, stb.) amíg már nem
változnak az értékek (általában 4-6 kör elég) sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Hiányzó adatok kitöltése Iteratívan becsülhetjük a tanítóhalmaz hiányzó értékeit: • Elso˝ közelítés: vegyük a hiányzó attribútum átlagát (ill.
leggyakoribb értékét) a többi soron, és ezt helyettesítsük be • Az így kiegészített adatokkal építsünk erdot ˝ • Minden i adatsorhoz amiben f hiányzott, vegyük az összes
(nem-f -hiányos j sorral páronként vett hasonlóságait (si,j ) • Az új becslés: si,j súlyokkal átlagoljuk a j-kben talált
f -értékeket, ezt tegyük if -be • Ezt iterálhatjuk (új erdo˝ építése, stb.) amíg már nem
változnak az értékek (általában 4-6 kör elég) sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Hiányzó adatok kitöltése Iteratívan becsülhetjük a tanítóhalmaz hiányzó értékeit: • Elso˝ közelítés: vegyük a hiányzó attribútum átlagát (ill.
leggyakoribb értékét) a többi soron, és ezt helyettesítsük be • Az így kiegészített adatokkal építsünk erdot ˝ • Minden i adatsorhoz amiben f hiányzott, vegyük az összes
(nem-f -hiányos j sorral páronként vett hasonlóságait (si,j ) • Az új becslés: si,j súlyokkal átlagoljuk a j-kben talált
f -értékeket, ezt tegyük if -be • Ezt iterálhatjuk (új erdo˝ építése, stb.) amíg már nem
változnak az értékek (általában 4-6 kör elég) sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Hiányzó adatok kitöltése Iteratívan becsülhetjük a tanítóhalmaz hiányzó értékeit: • Elso˝ közelítés: vegyük a hiányzó attribútum átlagát (ill.
leggyakoribb értékét) a többi soron, és ezt helyettesítsük be • Az így kiegészített adatokkal építsünk erdot ˝ • Minden i adatsorhoz amiben f hiányzott, vegyük az összes
(nem-f -hiányos j sorral páronként vett hasonlóságait (si,j ) • Az új becslés: si,j súlyokkal átlagoljuk a j-kben talált
f -értékeket, ezt tegyük if -be • Ezt iterálhatjuk (új erdo˝ építése, stb.) amíg már nem
változnak az értékek (általában 4-6 kör elég) sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Hiányzó adatok kitöltése
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
A kiértékeléshez használt adathalmazok
Data set
Train size
Test size
Dimension
Classes
15000
5000
16
26
Sat-images
4435
2000
36
6
Zip-code
7292
2007
256
10
Waveform
300
3000
21
3
Twonorm
300
3000
20
2
Threenorm
300
3000
20
2
Ringnorm
300
3000
20
2
Letters
sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Eredmények (hibaszázalékok) Data set
Adaboost
Forest-RI2
Forest-RI3
One tree
Letters
3.4
3.5
4.7
19.8
Sat-images
8.8
8.6
10.5
17.2
Zip-code
6.2
6.3
7.8
20.6
Waveform
17.8
17.2
17.3
34.0
Twonorm
4.9
?
3.9
24.7
Threenorm
18.8
?
17.5
38.4
Ringnorm
6.9
?
4.9
25.7
˝ véletlen attribútum választással. Forest-RI (Random Input selection): Véletlen erdo, Fák száma: K = 100 (kivéve Zip-code: K = 200) AdaBoost iterációk száma: 50 (kivéve Zip-code: 100)
2 3
m = log2 M m=1
sztaki-logo
˝ építése Véletlen erdok
Alapok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Eredmények (hibaszázalékok) Adaboost
Forest-RC4
Forest-RC5
One tree
Letters
3.4
Sat-images
8.8
3.4
4.1
23.8
9.1
10.2
Zip-code
17.3
6.2
6.2
7.2
22.7
Waveform
17.8
16.0
16.1
33.2
Twonorm
4.9
3.8
3.9
20.9
Threenorm
18.8
16.8
16.9
34.8
Ringnorm
6.9
4.8
4.6
24.6
Data set
˝ Forest-RC: bemenetek lineáris kombinációival épített erdo. Összekombinált változók száma: 3
4 5
m=8 m=2
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
A korreláció és jóslóero˝ változása m növelésével
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
A hiba változása m növelésével
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Zaj tolerancia ˝ sokkal jobban tolerálják a zajt mint az AdaBoost. A véletlen erdok Amikor az AdaBoost elrontja (vagyis valójában jól klasszfikálná) a zaj-bementeteket akkor növekvo˝ súllyal kerül a tanítóhalmazba a hibás adat, és ez eltozítja a végso˝ eredményt is. 5%-os osztálycímke-permutáció után a hibák növekedése (%): Data set
Forest-RI
Forest-RC
43.2
1.8
11.1
6.8
1.7
2.8
Sonar
15.1
-6.6
4.2
Ionosphere
27.7
3.8
5.7
Soybean
26.9
3.2
8.5
Ecoli
7.5
7.9
7.8
Liver
10.3
-0.2
4.8
Breast cancer Diabetes
Adaboost
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Regresszió A döntési fák képesek regresszióra is – ekkor minden elágazásnál az alapján határozzuk meg a döntési attrubútumot és vágási határt, hogy a két új halmazon belül a jóslandó érték szórásnégyzetei minimálisak legyenek. Data set
Train size
Test size
Dimension
Boston Housing
506
10%
12
Ozone
330
10%
8
4177
25%
8
15000
5000
12
Friedman#1
200
2000
10
Friedman#2
200
2000
4
Friedman#3
200
2000
4
Abalone Robot Arm
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Regresszió eredményei ˝ paraméterei: 100 fa, m = 25, random lineáris Erdok kombinációi 2 bemenetnek. Megfigyelések: a fák közti korreláció itt lassababn no˝ m növelésével. Mean squared test set errors Data set
Bagging
Adapt. bag.
Forest
Boston Housing
11.4
9.7
10.2
Ozone
17.8
17.8
16.3
Abalone
4.9
4.9
4.6
Robot Arm
4.7
2.8
4.2
Friedman#1
6.3
4.1
5.7
Friedman#2
21.5
21.5
19.6
Friedman#3
24.8
24.8
21.6 sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Összefoglalás
˝ hatékony klasszifikátorok, nagy A véletlen erdok adathalmazokkal is megbirkóznak. A két paraméter, K és m választására nem túl érzékeny (de K legyen elég nagy, m pedig ne legyen túl nagy).
sztaki-logo
Alapok
˝ építése Véletlen erdok
˝ jó tulajdonságai A véletlen erdok
Kiértékelés
Köszönöm a figyelmet!
sztaki-logo
