Machine learning: Bagging ja puumallit

Esittelen koneoppimiseen kuuluvan bagging-menetelmän, jolla puumallien ennustusten varianssia pystytään vähentämään. Puumallien yleinen ongelma on ylisovittaminen (Overfitting), jonka takia mallit ennustavat hyvin harjoitusdataan, mutta huonosti uuteen dataan. Ne siis löytävät harjoitusdatasta rakenteita, jotka eivät kuitenkaan ole yleistettävissä muuhun dataan. Alla kuvassa malli on ylisovittanut ja hakenut punaisia pisteitä sinisten joukosta. Musta viiva antaa kuitenkin parhaan ennustustuloksen, kun mallia kokeillaan uuteen dataan. Punaiset pisteet sinisten joukossa eivät siis tässä muodossa toistu usein, kun otetaan uusia otoksia perusjoukosta.

Lähde: https://kaggle2.blob.core.windows.net/competitions/kaggle/2489/logos/front_page.png

Puumalli on mahdollista sovittaa täydellisesti harjoitusdataan, jolloin malli ennustaisi virheettömästi harjoitusdatan. Tämä johtuu siitä, että puumalli voi aina tehdä uuden oksan, kunnes kussakin oksan lehdessä on enää 1 havainto jäljellä. Esim. luottoriskiluokituksiin liittyen tämä tarkoittaisi sitä, että jokainen yksilö luokiteltaisiin loppuun asti, eli kukin yksilö kulkisi puussa omaan lehteensä, jossa ei olisi ketään muuta. Esimerkiksi kaksi lainanhakijaa, joista toisella olisi todettu maksukyvyttömyys, voitaisiin puumallilla jakaa eri lehtiin, vaikka heidän ainoa eronsa olisi yksi euro säästötilillä. Tällöin puumalli veisi hakijat samaa reittiä viimeiseen oksaan, jossa se tekisi jaon säästötilin rahasumman mukaan. Jos tällaista puuta käyttäisi luotonantoon, niin näistä kahdesta käytännössä identtisestä hakijasta vain toinen saisi lainan. Ylisovittamisen estämiseksi puumalleihin voi asettaa erilaisia ehtoja, kuten havaintojen minimimäärät lehdissä ja oksien maksimimäärät mallissa. Lisäksi ns. boostrap aggregating (bagging) on tehokas keino välttää ylisovittaminen.

Bagging

Sen sijaan, että käyttäisimme yhden puumallin harjoitusdatasta muodostamaa ennustetta, voimme ottaa harjoitusdatasta monta otosta ja muodostaa niiden pohjalta useita puumalleja. Kun näillä puumalleilla sitten ennustetaan testidataa, niin käytämmekin yksittäisten mallien sijaan niiden ennusteiden keskiarvoa. Tällä tavoin saamme luotua vakaamman ennusteen, jolloin yksittäisten mallien ylisovittuminen ei ole enää yhtä suuri ongelma (Baggingin avulla pienet muutokset datassa eivät aiheuta suuria muutoksia ennusteissa). Havainnollistan baggingin vaikutusta simuloimalla datan, jossa on kaksi muuttujaa y ja x. Lisään y:n vähän "kohinaa", jotta näemme, kuinka lähelle mallin ennusteet menevät, kun kohina häiritsee puumalleja. Muodostan sitten datasta harjoitusdatan (60% havainnoista) sekä testidatan (40% havainnoista). Alla on kuva testsetistä, johon ennustukset tehdään. Kuvassa oleva sininen viiva kuvaa parasta mahdollista ennustetta, koska se on simuloidun datan funktio ilman hajontaa aiheuttavaa satunnaista kohinaa.
R-koodi:

x <- sort(runif(300, 0, 10))
y <- sin(2.5*x)/x + rnorm(300,0,sd=0.10) 
data <- data.frame(y,x)
t <- sort(sample(nrow(data),0.6*nrow(data)))
trainingset <- dataa[t,]
testset <- dataa[-t,]
plot(testset$x, testset$y)
realvalue <- sin(2.5*x)/x
lines(x, realvalue,col="blue",lwd=2)
legend("topright",c("sin(2.5*x)/x",
"sin(2.5*x)/x + rnorm(300,0,sd=0.10)"),col=c("blue","black"),lty=c(1,NA),pch=c(NA,1),lwd=c(2,1))

Seuraavaksi muodostetaan puumalli käyttäen koko trainingset-dataa ja lasketaan sen antamien ennusteiden perusteella RMSE (Root Mean Squared Error, lisää infoa: RMSE). RMSE:lla verrataan ennusteiden osuvuutta oikeisiin arvoihin. Mitä pienempi arvo, sitä paremmin malli on ennustuksissaan onnistunut.
R-koodi:

library(rpart)
m0 <- rpart(y~.,data=trainingset,control=rpart.control(minsplit=5))
testset$pre0 <- predict(m0,testset) 
RMSE <- sqrt(mean((testset$y - testset$pre0)^2))
print(RMSE)
plot(testset$x, testset$y) # Uusi kuva, jossa m0:n ennusteet punaisella
realvalue <- sin(2.5*x)/x
lines(x, realvalue,col="blue",lwd=2)
lines(testset$x,testset$m1,col="red")
legend("topright",c("sin(2.5*x)/x",
"sin(2.5*x)/x + rnorm(300,0,sd=0.10)","m0 (RMSE=0.151)"),col=c("blue","black","red"),lty=c(1,NA,1),pch=c(NA,1,NA),lwd=c(2,1,1))

Ensimmäisen puumallin RMSE arvo on 0.151. Seuraavaksi otan traininigset-datasta viisi 20%:n satunnaisotosta (palautuksella), joista jokaisella muodostan oman puumallin. Ennustan näillä malleilla sitten testsettiin ja lasken RMSE:t. Sitten lasken mallien ennusteista bagging-menetelmän mukaisesti keskiarvot ja lasken uuden RMSE:n.
R-koodi:

a <- sample(nrow(trainingset),0.2*nrow(trainingset))
b <- sample(nrow(trainingset),0.2*nrow(trainingset))
c <- sample(nrow(trainingset),0.2*nrow(trainingset))
d <- sample(nrow(trainingset),0.2*nrow(trainingset))
e <- sample(nrow(trainingset),0.2*nrow(trainingset))
data1 <- trainingset[a,]
data2 <- trainingset[b,]
data3 <- trainingset[c,]
data4 <- trainingset[d,]
data5 <- trainingset[e,]
m1 <- rpart(y~., data=data1, control=rpart.control(minsplit=5))
m2 <- rpart(y~., data=data2, control=rpart.control(minsplit=5))
m3 <- rpart(y~., data=data3, control=rpart.control(minsplit=5))
m4 <- rpart(y~., data=data4, control=rpart.control(minsplit=5))
m5 <- rpart(y~., data=data5, control=rpart.control(minsplit=5))
pre1 <- predict(m1,testset)
pre2 <- predict(m2,testset)
pre3 <- predict(m3,testset)
pre4 <- predict(m4,testset)
pre5 <- predict(m5,testset)
RMSE1 <- sqrt(mean((testset$y - pre1)^2)) #lasketaan kullekin mallille RMSE-arvot
print(RMSE1)

Yllä olevassa kuvassa näkyvät m1-m5:n ennusteet sekä niiden yhteiset mAvg:n ennusteet. Pienimmän RMSE:n antaa malli mAvg, eli bagging on parantanut ennusteita verrattuna yksittäisiin malleihin m1-m5. Alla on vielä yllä oleva kuva ilman sinistä viivaa, jotta bagging:n merkitys näkyy selkeämmin. Kuvasta näkee, kuinka vaihtelevia yksittäisten puumallien ennustukset ovat, vaikka ne ovat kaikki peräisin saman trainingsetin arvoista. Baggingin avulla näistäkin ailahtelevista puumalleista saadaan luotua vakaa ennustus (ennusteet ovat vakaita, koska baggingin takia tapahtuu konvergoitumista, eli lisäämällä otosten määrää trainingsetistä mAvg:n tulokset eivät radikaalisti poikkea nykyisestä), koska keskiarvotus jättää yksittäisten puumallien rajut ylisovittamiset vähemmälle huomiolle. Lisäksi, jos enemmistö puumalleista on ennusteessaan melko oikeassa, niin nämä ennusteet saavat enemmän painoarvoa (esim. katso kuvaa, kun x=3). Tietysti, jos enemmistö puumalleista olisi väärässä, niin myös huonot ennusteet painottuisivat. Kuitenkin Ensemble learning -menetelmät perustuvat ajatukseen, että keskinkertaisista malleista saadaan luotua hyviä yhdistämällä, ja pahimmassakin tapauksessa yhdistetty malli on yksittäisen mallin veroinen, eli ei muutu sitä huonommaksi. Kahden mallin yhdistäminen voi olla hyvä ajatus erityisesti, jos kummankin mallin ennusteet poikkeavat toisistaan ja mallit ovat melko varmoja oikeissa ennusteissaan, kun taas epävarmoja ollessaan väärässä. Tällaiset mallit yhdistämällä niiden oikeaksi menneet ennusteet pysyvät sellaisina myös keskiarvotusten jälkeen ja lisäksi osa toisen mallin epäonnistumisista korjaantuu, koska toinen malli ennusti ne oikein. Näin väärien ennustusten määrä onkin yhdistetyssä mallissa pienempi kuin yksittäisissä. Lisää tieto löytyy mm. täältä

"A necessary and sufficient condition for an ensemble of classifiers to be more accurate than any of its individual members is if the classifiers are accurate and diverse. An accurate classifier is one that has an error rate of better than random guessing on new x values Two classifiers are diverse if they make different errors on new data points"

Lähde: http://web.engr.oregonstate.edu/~tgd/publications/mcs-ensembles.pdf

Yhdistetty malli mAvg on tällä hetkellä m0:n veroinen ennustuksissaan, joten baggingista ei ole ollut käytännössä vielä huomattavaa hyötyä. Seuraavaksi otan viisi uutta satunnaisotosta trainingset-datasta ja muodostan uudet puumallit, joiden ennusteet yhdistän m1-m5:n kanssa. R-koodi on vastaava kuin aiempi. Nyt RMSE on 0.141. Alla kuva, jossa vanha ja uusi malli.

Alla vielä kuva koneoppimiseen liittyvän Random forest -menetelmän ennusteista. RMSE on tälle mallille 0.119. Random forest -menetelmässä algoritmi muodostaa useita puumalleja (tässä 5000 kpl) ja keskiarvottaa niiden ennusteet (luokittelevassa ennustamisessa se käyttää ennusteiden moodia). Puumallit tehdään bagging-menetelmällä, mutta myös muuttujista käytetään vain osaa kussakin puumallissa (muuttujat kuhunkin jakoon (split) valitaan sattumanvaraisesti). Oletuksena R:ssa muuttujia "n" käytetään kussakin jaossa neliöjuuri(n) (luokittelu) tai n/3 (regressio) määrä. Random forest on kätevä menetelmä, jolla saa parempia ennusteita kuin yksittäisillä puumalleilla. Random forest ei kuitenkaan juuri paranna ennusteita verrattuna logistiseen regressioon, kun ennustetaan binääristä selitettävää muuttujaa. Random forest löytää kuitenkin muuttujien välisiä yhteisvaikutuksia (Interactions) ja on siten avuksi logistisen regression rinnalla. Näiden mallien yhdistämisestä kirjoittelen jatkossa.