나무모형 이재용 서울대학교통계학과 2015 년 2 월 16 일
의사결정나무 I Years < 4.5 238 R 3 Hits R 1 117.5 5.11 Hits < 117.5 R 2 6.00 6.74 1 4.5 24 Years 1 Hitters 자료 1. ISLR 패키지에있는자료 2. 1986 년 322 명의메이저리그선수들에대한관측치. 20 개의변수 3. log(salary) 를 Hits(1986 년안타의개수 ) 와 Years( 메이저리그에서뛴햇수 ) 등을이용해예측하는것이목적.
의사결정나무 II 개요 1. 예측변수의공간을분할하여분할된부분에서반응변수의값을예측하는회귀분석혹은분류방법. 2. 의사결정나무 (decision tree) 방법이라고도한다. 3. 예측변수의공간을분할하기때문에해석이쉽다. 4. 예측성능은보통좋지않다. 5. 배깅 (bagging), 랜덤숲 (random forest), 부스팅 (boosting) 과같이다수의나무를합치면종종매우좋은결과를나타낸다. 6. 반응변수 Y 가범주형인가, 연속형인가에따라분류나무, 회귀나무로나뉜다. 용어 1. 종점마디혹은종점노드 (terminal nodes, or leaves) : R 1, R 2, R 3 를말한다. 2. 내부마디혹은내부노드 (internal nodes) : 예측변수의공간이분할된곳으로종점노드가아닌노드를말한다. 3. 가지 (branch) : 노드에서분리되는나무의일부분을가지라한다.
의사결정나무의적합 I 의사결정나무의적합의요약 1. 예측변수공간의분할. 예측변수 X 1,..., X p 가취할수있는값들의공간을 R 1,..., R J 로분할한다. 2. 예측값 R j 에속하는예측변수의값에는동일한 ŷ 의값으로예측한다. 예. R j 에속한관측치들의평균을쓴다. 3. 의사결정나무의적합은나무기르기와가지치기두가지단계로이루어진다.
의사결정나무의적합 II 나무기르기 : 반복이진분할 (recursive binary splitting) 1. i:x i R 1(j,s) (y i ŷ R1 ) 2 + i:x i R 2(j,s) (y i ŷ R2 ) 2 를최소로하는 j 와 s 를 찾고예측변수의공간을 R 1 (j, s) 와 R 2 (j, s) 로나눈다. R 1 (j, s) = {X : X j < s} R 2 (j, s) = {X : X j s} ŷ R1 = R 1 에속한 y 들의평균 ŷ R2 = R 2 에속한 y 들의평균. 2. 동일한방식으로 R 1 이나 R 2 를분할하여 R 1, R 2, R 3 라고한다. 즉, R 1 내에서분할하여가장 RSS 를최소화하는분할과 R 2 내에서분할하여 RSS 를최소화하는분할을비교하여 RSS 를더작게하는분할을하여분할된공간을 R 1, R 2, R 3 라고한다. 3. R 1,..., R j 가주어져있을때, 각 R i 를두개로분할하는방법들을비교하여 RSS 를최소화하는분할방법을찾고새로분할된영역들을 R 1,..., R j+1 이라한다.
의사결정나무의적합 III 4. 분할을계속하여정해진기준이만족될때까지분할한다. 예. 모든 R i 가 5 개이하의관측치를포함한다.
의사결정나무의적합 IV 가지치기 : 비용복잡도가지치기 (cost complexity pruning) 모든부분나무를교차검증으로비교하는것은계산량이많으므로다음과같은방법을쓴다. 1. 주어진 α 0 에대해서, T m=1 를최소화하는 T α 를구한다. i:x i R m (y i ŷ Rm ) 2 + α T 2. α 의추정. K 겹교차검증을통해 ˆα 를구한다. T ˆα 이추정량이된다.
의사결정나무의적합 V 의사결정나무의적합 Years < 4.5 RBI < 60.5 Putouts < 82 Years < 3.5 Hits < 117.5 Mean Squared Error 0.0 0.2 0.4 0.6 0.8 1.0 Training Cross Validation Test 5.487 Years < 3.5 4.622 5.183 5.394 6.189 Walks < 43.5 Walks < 52.5 Runs < 47.5 RBI < 80.5 6.407 Years < 6.5 6.015 5.571 6.549 7.289 6.459 7.007 2 4 6 8 10 Tree Size
분류나무 I 분류나무의적합방식은회귀나무와동일하다. 다만, 잔차제곱합대신아래의순수성측도중하나를사용한다. 순수성측도 1. 오분류율 E = 1 max ˆp mk k 2. 기니지수 (Gini index) K G = ˆp mk (1 ˆp mk ) k=1 예측치 ŷ Rm = R m 에서가장빈도가높은범주 3. 엔트로피 (cross-entropy) K D = ˆp mk log ˆp mk k=1
분류나무 II 장점 1. 사람들에게설명하기쉽다. 2. 의사결정나무는사람들의의사결정과매우흡사하다. 3. 나무는그림으로표현될수있고, 비전문가도해석을쉽게할수있다. 4. 범주형예측변수도쉽게이용이가능하다. 가변수가필요없다. 의사결정나무방법의분산 단점 1. 예측력이떨어진다. 2. 분산이커서추정량이안정적이지않다. 의사결정나무방법은분산이매우크다. 주어진자료를반으로나누어의사결정나무를적합하면두개의매우다른나무가나온다. 회귀모형은그렇지않다.
분류나무 R 코드 I library(tree) library(islr) attach(carseats) High=ifelse(Sales<=8,"No","Yes") Carseats=data.frame(Carseats,High) tree.carseats=tree(high~.-sales,carseats) summary(tree.carseats) ## ## Classification tree: ## tree(formula = High ~. - Sales, data = Carseats) ## Variables actually used in tree construction: ## [1] "ShelveLoc" "Price" "Income" "CompPrice" "Population" ## [6] "Advertising" "Age" "US" ## Number of terminal nodes: 27 ## Residual mean deviance: 0.4575 = 170.7 / 373 ## Misclassification error rate: 0.09 = 36 / 400 Sales 를제거하고나무모형을적합했다. 가지치기이전의나무이다. 이탈도 (deviance) 는 2 n mk log ˆp mk 이다. 여기서, m 의마지막노드의인덱스이고, k 는카테고리인덱스이다.
분류나무 R 코드 II plot(tree.carseats) text(tree.carseats,pretty=0) ShelveLoc: Bad,Medium Price < 92.5 CompPrice Population Income < 110.5 < 57 Advertising < 13.5 < 207.5 CompPrice < 124.5 NoYesYesYes Price < 106.5Price < 122.5 Population < 177 Income < 100 Income < 60.5 ShelveLoc: CompPrice Bad < 147.5 Price < 109.5Price 147 NoYes NoNo Age CompPrice < 49.5 < 152.5 No No YesYesNo YesNo No Price < 135 Income < 46 US: No Price < 109 Age < 54.5 YesNo Yes NoYes CompPrice CompPrice < 130.5 122.5 Price < 125 NoYes YesNo YesNo plot 은나무그림만그린다. text 는그림에변수들이름을써넣는다.
분류나무 R 코드 III tree.carseats 나무자체를출력한다. set.seed(2) train=sample(1:nrow(carseats), 200) Carseats.test=Carseats[-train,] High.test=High[-train] tree.carseats=tree(high~.-sales,carseats,subset=train) tree.pred=predict(tree.carseats,carseats.test,type="class") table(tree.pred,high.test) ## High.test ## tree.pred No Yes ## No 86 27 ## Yes 30 57 (86+57)/200 ## [1] 0.715 예측오차를계산한다.
분류나무 R 코드 IV set.seed(3) cv.carseats=cv.tree(tree.carseats,fun=prune.misclass) names(cv.carseats) ## [1] "size" "dev" "k" "method" cv.carseats ## $size ## [1] 19 17 14 13 9 7 3 2 1 ## ## $dev ## [1] 55 55 53 52 50 56 69 65 80 ## ## $k ## [1] -Inf 0.0000000 0.6666667 1.0000000 1.7500000 2.0000000 ## [7] 4.2500000 5.0000000 23.0000000 ## ## $method ## [1] "misclass" ## ## attr(,"class") ## [1] "prune" "tree.sequence"
분류나무 R 코드 V 교차검증오차를계산한다. cv.tree 함수에서 FUN=prune.misclass 는교차검증을할때, 오분류율을기준으로사용한다는뜻이다. 이옵션의디폴트는 deviance 이다. cv.carseats 의 size 는나무의끝마디의개수, k 는비용복잡도식의 α 에대응하는값이다. size 는작아지고 k 는커진다. dev 는교차검증오차로가장작은것이좋은것이다.
분류나무 R 코드 VI par(mfrow=c(1,2)) plot(cv.carseats$size,cv.carseats$dev,type="b") plot(cv.carseats$k,cv.carseats$dev,type="b") cv.carseats$dev 50 55 60 65 70 75 80 cv.carseats$dev 50 55 60 65 70 75 80 5 10 15 cv.carseats$size 0 5 10 15 20 cv.carseats$k
분류나무 R 코드 VII par(mfrow=c(1,1)) 교차검증오차를나무의크기와조율파라미터에대해그렸다.
분류나무 R 코드 VIII prune.carseats=prune.misclass(tree.carseats,best=9) plot(prune.carseats) text(prune.carseats,pretty=0) ShelveLoc: Bad,Medium Price < 142 Price < 142.5 ShelveLoc: Bad Price < 86.5 No Advertising < 6.5 Yes Age < 37.5 CompPrice < 118.5 No Yes No Yes No Yes No 가지치기하여끝마디가 9 개인나무를얻는다.
분류나무 R 코드 IX tree.pred=predict(prune.carseats,carseats.test,type="class") table(tree.pred,high.test) ## High.test ## tree.pred No Yes ## No 94 24 ## Yes 22 60 오차율을계산하였다.
회귀나무 R 코드 I MASS 패키지에있는 Boston 자료를이용한다. 보스톤내의 506 개동네에관한자료이다. 14 개의변수가있다. medv 는자가소유주택가격의중앙값으로단위는천불이다. library(mass) set.seed(1) train = sample(1:nrow(boston), nrow(boston)/2) tree.boston=tree(medv~.,boston,subset=train) summary(tree.boston) ## ## Regression tree: ## tree(formula = medv ~., data = Boston, subset = train) ## Variables actually used in tree construction: ## [1] "lstat" "rm" "dis" ## Number of terminal nodes: 8 ## Residual mean deviance: 12.65 = 3099 / 245 ## Distribution of residuals: ## Min. 1st Qu. Median Mean 3rd Qu. Max. ## -14.10000-2.04200-0.05357 0.00000 1.96000 12.60000 plot(tree.boston) text(tree.boston,pretty=0)
회귀나무 R 코드 II lstat < 9.715 rm < 6.7815 dis < 2.6221 rm < 6.4755 37.40 22.54 26.84 rm < 7.437 32.05 46.38 lstat < 21.49 lstat < 14.48 21.04 17.16 11.10 나무를적합하였다.
회귀나무 R 코드 III cv.boston=cv.tree(tree.boston) plot(cv.boston$size,cv.boston$dev,type='b') cv.boston$dev 5000 10000 15000 20000 1 2 3 4 5 6 7 8 cv.boston$size 교차검증한결과이다.
회귀나무 R 코드 IV prune.boston=prune.tree(tree.boston,best=5) plot(prune.boston) text(prune.boston,pretty=0) lstat < 9.715 rm < 6.7815 25.52 32.05 rm < 7.437 46.38 lstat < 21.49 19.16 11.10 가지치기한결과이다.
회귀나무 R 코드 V yhat=predict(tree.boston,newdata=boston[-train,]) boston.test=boston[-train,"medv"] plot(yhat,boston.test) abline(0,1) boston.test 10 20 30 40 50 10 15 20 25 30 35 40 45 yhat
회귀나무 R 코드 VI mean((yhat-boston.test)^2) ## [1] 25.04559 시험자료에예측한결과이다.
배깅 (bagging) I 붓스트랩샘플 X 1, X 2,..., X B 를 X 에서추출한다. 각붓스트랩샘플 X b 에의사결정나무를적합해서 ˆf b 라부른다. 이를평균낸것이배깅추정량이다. 즉, ˆf bag (x) = 1 B B b=1 ˆf b (x) 이다. y 가범주형일때는다수결 (majority vote) 방법을쓴다. 즉, ˆf bag (x) 는 ˆf b (x), b = 1, 2,..., B 중가장많은값을갖는범주를예측값으로한다.
배깅 (bagging) II 근거 : Brieman 의설명 D 를주어진자료라하고 X, Y 를미래의관측치라하자. f (X, D) 를 D 로구축한추정량의 X 에서의값, 즉 Ŷ 이라하자. 또한, 평균추정량을 와같이표기하자. 젠센의부등식을이용하면 f A (X ) = E D f (X, D) E (X,Y ) E D (Y f (X, D)) 2 E (X,Y ) (Y f A (X )) 2 가성립하는것을알수있다. 자료 D 의분포를붓스트랩분포로근사를한다고생각하면 f A 는배깅추정량과비슷하다. 따라서, 우변은배깅추정량의예측오차와비슷하다. 좌변은 f 라는추정방법이평균적으로갖는예측오차이다. 여기서평균은주어진자료 D 와미래의자료 (X, Y ) 에대해이루어졌다. 이를해석하면배깅추정량의예측오차는주어진자료로한번구축한추정량 f (X, D) 보다평균적으로좋다고해석할수있다.
배깅 (bagging) III 배깅으로얻는것 예측오차의차이는 E (X,Y ) E D (Y f (X, D)) 2 E (X,Y ) (Y f A (X )) 2 = E (X,Y ) Var D f (X, D) 라는것이알려져있다. 이는배깅으로줄일수있는것은추정량의분산이라는것을알수잇다. 분산이작으면배깅으로얻는것이별로없다. 이는배깅을할때, 그루터기 (stump) 를이용하는이유이다.
랜덤숲 (random forest) I 랜덤숲도의사결정나무의배깅과매우흡사하다. 다른점은분할이필요할때마다모든 p 개의변수를다고려하는것이아니라 m p 개의변수를랜덤하게골라이변수들에서만분할을한다. m = p 이면배깅과같다. 직관적근거 주어진변수중한개의변수가매우중요하고나머지변수들은중간정도의중요성을가진다고하자. 배깅을하면모든나무들이매우중요한변수부터분할을하게될것이다. 그러면나무들이서로비슷해지고나무를이용한추정치사이에상관계수들이커질것이다. 그런데 m개의변수만고려한다면매우중요한변수로분할을시작하지않을나무가 p m 의확률이나될것이다. 이는붓스트랩나무들사이의상관성을 p 줄여서평균의분산을줄여준다.
배깅과랜덤숲 R 코드 I 배깅은랜덤숲의일종이다. randomforest 패키지를이용해서적합할수있다. library(randomforest) ## randomforest 4.6-12 ## Type rfnews() to see new features/changes/bug fixes. set.seed(1) bag.boston=randomforest(medv~.,data=boston, subset=train, mtry=13, importance=true) bag.boston ## ## Call: ## randomforest(formula = medv ~., data = Boston, mtry = 13, importance = TRUE, subs ## Type of random forest: regression ## Number of trees: 500 ## No. of variables tried at each split: 13 ## ## Mean of squared residuals: 11.02509 ## % Var explained: 86.65 mtry 옵션은매반복에서 13 개의설명변수가고려되어야한다는뜻이다. 다시말하면배깅을하라는뜻이다. importance 는변수의중요성을평가하라는뜻이다.
배깅과랜덤숲 R 코드 II yhat.bag = predict(bag.boston,newdata=boston[-train,]) plot(yhat.bag, boston.test) abline(0,1) boston.test 10 20 30 40 50 10 20 30 40 50 yhat.bag
배깅과랜덤숲 R 코드 III mean((yhat.bag-boston.test)^2) ## [1] 13.47349 시험오차를계산하였다. bag.boston=randomforest(medv~.,data=boston,subset=train,mtry=13,ntree=25) yhat.bag = predict(bag.boston,newdata=boston[-train,]) mean((yhat.bag-boston.test)^2) ## [1] 13.43068 ntree 옵션은계산하는나무의개수를정한것이다. set.seed(1) rf.boston=randomforest(medv~.,data=boston,subset=train,mtry=6,importance=true) yhat.rf = predict(rf.boston,newdata=boston[-train,]) mean((yhat.rf-boston.test)^2) ## [1] 11.48022 나무숲을구했다. mtry=6 를썼다. 디폴트는회귀나무의경우는 p/3, 분류나무의경우는 p 이다.
배깅과랜덤숲 R 코드 IV importance(rf.boston) ## %IncMSE IncNodePurity ## crim 12.547772 1094.65382 ## zn 1.375489 64.40060 ## indus 9.304258 1086.09103 ## chas 2.518766 76.36804 ## nox 12.835614 1008.73703 ## rm 31.646147 6705.02638 ## age 9.970243 575.13702 ## dis 12.774430 1351.01978 ## rad 3.911852 93.78200 ## tax 7.624043 453.19472 ## ptratio 12.008194 919.06760 ## black 7.376024 358.96935 ## lstat 27.666896 6927.98475 변수의중요성을계산했다. 첫번째열은주어진변수를제거했을때, 나무모형의평균제곱오차의변화율이고, 두번째열은주어진변수를제거했을때노드의순수도 ( 분류나무의경우는이탈도, 회귀나무의경우는잔차제곱합 ) 의변화율이다. varimpplot(rf.boston)
배깅과랜덤숲 R 코드 V rf.boston rm lstat nox dis crim ptratio age indus tax black rad chas zn lstat rm dis crim indus nox ptratio age tax black rad chas zn 5 10 15 20 25 30 %IncMSE 0 2000 4000 6000 IncNodePurity 변수의중요도를그림으로그렸다.
부스팅 (boosting) I 알고리듬 1. ˆf (x) 0, r i = y i, i = 1, 2,..., n 이라놓는다. 2. b = 1, 2,..., B 2.1 잔차 r 을반응변수로하여 (X, r) 에종료노드가 d + 1 개인나무를적합하여 ˆf b 라한다. 2.2 ˆf ˆf (x) + λˆf b (x) 2.3 r i r i λˆf b (x i ) 3. 최종추정량 ˆf (x) = B λˆf b (x). b=1
부스팅 (boosting) II 근거 부스팅방법은느린예측모형 (slow learner) 라고하는데한꺼번에 ˆf 을발견하는것이아니라조금씩잔차를늘려가며 ˆf 을개선시켜나가는것이다. 조율파라미터 λ 의선택 교차검증을통해결정한다. 참고 1. B 가커지면배깅과다르게과적합할수있다. 과적합이매우느리게나타난다. 교차검증을통해 B 를결정한다. B 가커질수록모형공간이커진다. 즉유연해진다. 2. λ 를보통 0.01 이나 0.001 을쓴다. λ 가매우작으면 B 가커져야한다. 3. d = 1 인나무, 즉 1 번분할한나무를많이쓴다. 1 번분할한나무를그루터기 (stump) 라고한다.
부스팅 (boosting) III Test Classification Error 0.05 0.10 0.15 0.20 0.25 Boosting: depth=1 Boosting: depth=2 RandomForest: m= p 0 1000 2000 3000 4000 5000 Number of Trees
부스팅 (boosting) IV 15 개범주 cancer gene expression 자료의예. boosting with d = 1 이가장좋다. 아다부스트 (adaboost) : 분류문제에서부스팅 여기서반응변수의값은 1, 1 를갖는다고하자. 1. 가중치 w i = 1, i = 1, 2,... 라초기화한다. n 2. b = 1, 2,..., B. 2.1 가중치 (w i ) 를이용하여분류기 f b 를적합한다. 2.2 오차를다음과같이계산한다. n i=1 err b := w ii (y i f b (x i )) n i=1 w i 2.3 c b := log 1 err b err b 로놓는다. 2.4 가중치를 w i = w i e c bi (y i f b (x i )) 로업데이트한다.
부스팅 R 코드 I library(gbm) ## Loading required package: survival ## Loading required package: lattice ## Loading required package: splines ## Loading required package: parallel ## Loaded gbm 2.1.1 set.seed(1) boost.boston=gbm(medv~.,data=boston[train,], distribution="gaussian", n.trees=5000, interac summary(boost.boston)
부스팅 R 코드 II zn indus ptratio rm 0 10 20 30 40 Relative influence
부스팅 R 코드 III ## var rel.inf ## lstat lstat 45.9627334 ## rm rm 31.2238187 ## dis dis 6.8087398 ## crim crim 4.0743784 ## nox nox 2.5605001 ## ptratio ptratio 2.2748652 ## black black 1.7971159 ## age age 1.6488532 ## tax tax 1.3595005 ## indus indus 1.2705924 ## chas chas 0.8014323 ## rad rad 0.2026619 ## zn zn 0.0148083 회귀나무이어서 distribution= gaussian 를썼다. 분류나무인경우는 bernoulli 를쓴다. n.tree=5000 은 B = 5000 개의반복을한다는뜻이다. interaction.depth=4, 는각반복에서더해지는나무의깊이를 4 로제한한다는뜻이다. summary 결과의 rel.inf 는상대적영향력 (relative influence) 를말한다. par(mfrow=c(1,2)) plot(boost.boston,i="rm") plot(boost.boston,i="lstat")
부스팅 R 코드 IV f(rm) 22 26 30 f(lstat) 20 25 30 4 5 6 7 8 rm 5 10 20 30 lstat 변수들의주변효과 (marginal effect) 를그린다. yhat.boost=predict(boost.boston,newdata=boston[-train,],n.trees=5000) mean((yhat.boost-boston.test)^2) ## [1] 11.84434
부스팅 R 코드 V 시험오차를계산한다. boost.boston=gbm(medv~.,data=boston[train,],distribution="gaussian",n.trees=5000,interactio shrinkage 옵션은부스팅알고리듬에서조율파라미터 λ 의값을정한다. 디폴트는 0.001 이다. 여기서는 λ = 0.2 를썼다. yhat.boost=predict(boost.boston,newdata=boston[-train,],n.trees=5000) mean((yhat.boost-boston.test)^2) ## [1] 11.51109
참고문헌 1. 아래의책에서제공되는그림을써서슬라이드를만들었다. James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). An introduction to statistical learning. New York: springer. 2. 배깅에관한설명은김진석교수 ( 동국대 ) 의배깅에관한강의노트를참고하였다.