회귀트리(regression tree)와 분류트리(classification tree) 예측

회귀트리(regression tree) 만드는 법(기본)

회귀트리 빌딩의 기본은 설명변수 X1, X2…Xp 기준의 값들로 J개의 다르고 겹치지 않은 집합 R1,R2…RJ로 분할하는 것이다. 수행 과정은 다음과 같다.

1. 분할은 모든 Rj내 각각의 데이터와 예측값 Rj간의 RSS를 최소화하는 Rj를 구함으로써 수행된다. 이때 예측값 Rj란 j번째 Group 데이터들의 평균 반응변수 값이다.
   
   
   
2. RSS를 최소화하는 각각의 Rj를 구하기 위해, 모든 경우의 수를 고려하는것은 불가능하다. 때문에 다중회귀 변수 선택법 중 전진 선택법과 같이 특정 단계에서 가장 좋은 분할(RSS 최소)을 선택 후 다음 단계로 넘어가는 방법을 취한다. 이를 재귀이진분할(recursive binary splitting)이라 한다. 말로 설명해서 어려워 보이나 2개의 트리 영역(terminal node)를 만드는 예를 식으로 표현하면 아래와 같다. 즉, 이 식을 최소화하는 j와 트리를 나누는 기준 값 s를 찾는다.
   
   
   
3. 앞서 분할된 트리 영역을 다시 분할한다. 이 과정은 어떤 정지 기준이 만족될 때까지 계속한다. (예: 어떤 영역도 5개 보다 많은 데이터가 있어야한다 등)
4. 분할이 종료되면 각각의 검정셋 데이터가 속하는 훈련셋의 Rj의 평균을 사용하여 에측한다.

가지치기(Pruning)

상기 방법은 다중회귀에서 변수 갯수와 같이 트리가 많을 경우 검정셋을 과적합할 가능성이 높고 적을 경우엔 편향은 증가할 수 있으나 분산이 작아 해석은 쉬워진다. 이 문제의 균형을 위한 해결안은 분할로 인한 RSS감소가 어떤 기준값보다 클 때만 분할 하도록 기준 정하는 것이다. 그러나 이 방법은 앞선 트리분할에서 분할이 중지될 경우 나중에 RSS 감소가 큰 경우를 적용 못하고 트리를 완성하게 되는 문제점을 내포하고 있다. 비용 복잡성 pruning은 이 방법을 해결한다. 이것은 RSS와 트리의 갯수(터미널 노드수)의 합이 최소가 되는 것을 기준으로 서브 트리를 비교한다. 식은 다중회귀 변수 선택에서 AIC, BIC의 공식과 유사하다. 이 방법은 알파값이 양(+)이 되는 경우만 고려하므로 모든 서브 트리를 고려할 필요가 없는 장점을 가진다.

최종 회귀트리 빌딩 요약

최종적인 트리 Guideline은 재귀이진분할 + 비용 복잡성 pruing + 교차검증로 요약할 수 있다. 상세 과정은 다음과 같다. 

Step 1: 훈련셋을 재귀이진분할하여 전체 트리를 만든다. 각 트리내 데이터 수가 특정 값보다 작을 경우 분할을 중지한다. 

Step 2: 만들어 놓은 트리별로 비용 복잡성 pruning식을 적용해 가장 좋은 서브트리들을 알파의 함수로 얻는다.(예: 특정 설명변수와 그것의 기준 값 s, 서브트리 갯수 T개로 구성될 때의 알파값) 

Step 3: k-folds 교차검증을 통해 위의 알파값을 선택한다. 1) 훈련셋의 k번째 fold외 다른 데이터를 가지고 상기 1,2번을 한다. 이때 k는 훈련셋 데이터수의 약수로 한다.(예: 132개면 6 folds 적용) 2) 남겨진 k번째 fold 데이터에 대해 평균제곱예측오차를 알파의 함수로 구하고 각 테스트 fold별로 알파값을 평균하여 평균제곱예측오차를 최소하는 알파를 선택한다. 

Step 4: 선택된 알파에 대응하는 위 2번째 단계에서 얻은 서브트리를 반환한다. 

Step 5: 최종 트리를 검정셋에 적용해 MSE를 구한다.

실제 아래에서 제시할 예는 Step 1 –> Step 3 –> Step 4 –> Step 5처럼 보인다. Step 2는 실질적으로 Step 3 전에 수행하나 굳이 할 필요 없으며  Step 4는 실제로 Step 2를 의미하기 때문이다.

트리 빌딩은 교차검증을 통해 트리의 갯수(터미널 노드수) 먼저 확정하고 (Step 3) 확정된 트리의 갯수에 해당하는 최적화된 tree를 구하는 점(Step 4)에서 다중회귀모델의 변수 선택 방법과 유사하다.

분류트리(classification tree)

분류트리는 반응변수가 양적인 회귀트리와 달리 질적 반응 변수를 가진다. 따라서, 분류트리에서는 관측치가 속하는 영역 내 훈련 관측치들이 가장 많이 포함된 클래스에 속하는지를 예측한다. 따라서 이진 분할시 회귀트리의 RSS가 아닌 분류오류율이 기준이 된다.(아래 식) 분류 오류율은 가장 자주 발생하는 클래스에 속하지 않는 그 영역 내 훈련 관측치들의 비율이다.

그러나 분류오류율은 노드순도에 민감하지 않아 지니 지수 또는 교차엔트로피라 불리는 값을 사용한다. 이 두 계수 모두 노드가 pure하면(확률이 0또는 1에 가까우면) 거의 0이 된다. prune시 이 3가지 중 하나를 사용할 수 있지만 최종 트리의 예측 정확도가 목적인 경우는 분류오류율 사용이 선호된다. 특이점은 노드 순도에 따라 분할을 하기 때문에 분할된 트리가 모두 Yes 또는 No의 같은 질적변수를 가질 수 있다. 이것은 분류오차는 줄이지 않지만 노드 순도에 민감한 지니 지수나 교차엔트로피를 향상시키기 때문에 발생한다.

트리 기반 예측의 장단점

1. 다중선형회귀보다 해석이 어렵다.
2. f가 비선형적이고 복잡하다면 다중선형회귀보다는 나을 수 있다.
3. 더미변수를 만들지 않고 질적 변수를 쉽게 처리할 수 있다.
4. 다중회귀변수나 KNN분류에 비해 예측정확도가 좋지 못한다.

상기 4번의 단점은 배깅, 랜덤포리스트, 부스팅과의 앙상블을 통해 예측성능을 향상 시킬 수 있다.

실전 예제

1.회귀트리 Step 1: 훈련셋을 통해 전체 tree 빌딩 Boston근교의 집값을 예측해보자. 전체 데이터의 반을 훈련셋으로 설정하여 전체 트리를 만든다. tree함수는 tree package에 있다.

library(MASS)
library(tree)
set.seed(1)
train.reg<-sample(1:nrow(Boston),nrow(Boston)/2)#sample에 따라 값 달라짐 
tree.boston<-tree(medv~.,Boston,subset=train.reg)
summary(tree.boston)

## 
## Regression tree:
## tree(formula = medv ~ ., data = Boston, subset = train.reg)
## 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

summary결과 설명변수는 3개(“lstat” “rm” “dis”)만 사용하였고 트리갯수는 8개이다. 회귀 트리의 이탈도(deviance)는 RSS으로 3099이고 이것을 전체 253개 데이터에서 트리 갯수 8개를 뺀 245로 나누면 잔차평균이탈도가 구해진다. Step 1에서 구한 전체 트리를 plot하면 다음과 같다. 해석하면 lstat가 <9.715 이면서 rm>=인 경우 주택가격은 $46,400이라고 예측한다. pretty=0은 각 카테고리의 문자뿐 아니라 질적변수 카테고리 이름도 포함한다.

plot(tree.boston)
text(tree.boston,pretty=0)

Step 3: 교차 검증 통해 트리 갯수 선정 cv.tree함수는 pruning을 통해 성능을 개선시킨다. 253개 데이터이므로 약수인 11을 K값으로 사용하자.

cv.boston<-cv.tree(tree.boston,K=11) #default K=10, FUN=prune.tree
plot(cv.boston$size,cv.boston$dev,type="b")

cv.boston

## $size
## [1] 8 7 6 5 4 3 2 1
## 
## $dev
## [1]  5327.572  5242.758  6418.949  6824.119  6599.406  7275.904 11653.371
## [8] 21126.183
## 
## $k
## [1]      -Inf  255.6581  451.9272  768.5087  818.8885 1559.1264 4276.5803
## [8] 9665.3582
## 
## $method
## [1] "deviance"
## 
## attr(,"class")
## [1] "prune"         "tree.sequence"

Step 4: 선택된 트리 갯수 모델을 pruning 결과를 보면 트리가 7개(size=7)일때의 이탈도(RSS)가 가장 작게 된다. 이탈도 감소가 완만해 지는 것은 size=4 이후이다. 경우에 따라 size=4 경우를 사용해도 되나 여기선 최종 pruning을 이탈도가 가장 낮은 size=7로 하자

prune.boston<-prune.tree(tree.boston,best=7)
plot(prune.boston)
text(prune.boston,pretty=0)

Step 5: 향상된 검정오차 검정오차(RSS)를 구한자. MSE의 제곱근이 5.004이다. 즉 검정셋에 대한 모델 예측값이 실제 주택가격의 평균 $5,004정도 차이가 있음을 알 수 있다.

pred<-predict(tree.boston,newdata=Boston[-train.reg,])
boston.test<-Boston[-train.reg,"medv"] #medv만 변환
plot(pred,boston.test)
abline(0,1)

sqrt(mean((pred-boston.test)^2))

## [1] 5.004557

의문점 및 개선점

1. 교차검증에 의한 서브트리 선택은 초기 선택된 훈련셋에 따라 달라질 수 있을까? –> 서브트리 선택시 초기 선택된 훈련셋을 여러번 샘플하여 비교할 필요가 있다.
2. 최종 MSE의 제곱근도 초기 선택된 검정셋에 따라 달라질 수 있다. 전체 과정을 30번 정도 수행하여 훈련셋, 검정셋에 따른 MSE 변동을 파악 후 1표준오차에 해당하는 MSE를 일반적인 MSE라 말할 수 있다.
3. 상기 1, 2번의 해결책을 동시에 적용해 보자.
   1) 전체 데이터의 1/2인 훈련데이터 샘플을 각각 100개 추출한다. 
   2) 각각의 훈련셋에서 교차검증을 통해 구한 100개의 트리를 pruning한다.
   3) 100개의 pruning한 트리를 100개의 검정데이터에 적용해 검정MSE를 구한다.
   4) 100개의 검정MSE값의 표준오차를 구한다.
   5) 평균 MSE+ 1 표준오차의 MSE 가지는 pruning된 트리모델을 선택한다.
4. 상기 1,2번의 문제 해결을 위해 교차검증내 또 다른 교차검증은 불가능해 보인다. 그것은 첫번재 교차검증을 통해 트리의 갯수가 이미 선정되므로 두번째 교차검증에서 구할 값이 없다.
5. 상기 1~4번의 훈련셋 변동에 따른 문제점은 배깅을 통해 해결한다. 배깅은 변동 문제 만큼은 확실히 제거할 것이다. 예측력은 유지한채로 말이다.  
   
6. cv.tree할 때 set.seed를 해야한다.(default 가 K=10 기준시)

2. 분류트리 

ISLR 패키지에서 400개 판매점의 Car Seats 판매에 대한 정보를 가져온다. Sales의 평균이 7.5이므로 8을 기준으로 작으면 No, 크면 Yes인 질적반응변수를 생성한다.

최종 pruning된 분류트리를 선택하기 위해선 1.훈련오차와 2.검정오차 대비 pruning된 검정오차의 오류율이 얼마나 향상되는가의 확인을 통해 pruning된 트리사용여부를 결정하게 된다. 훈련 오차는 전체데이터를 통해 쉽게 구할 수 있다. 아래 결과 훈련오차율 9%이다. 이탈도는 회귀트리의 RSS 대신 아래식을 사용한다.

library(ISLR)

## Warning: package 'ISLR' was built under R version 3.3.3

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

아래 결과 값은 가지의 분할기준, 관측치수, 이탈도, 가지의 전체 예측값, Yes와 No의 관측치 비율을 보여준다. 예를 들어 Price < 92.5 기준의 트리는 관측치 46개 이탈도 56.530 이 가지의 예측값은 Yes이고 Yes는30.4%, No는 69.56%로 구성되어 있음을 말한다.)

tree.carseats

## node), split, n, deviance, yval, (yprob)
##       * denotes terminal node
## 
##   1) root 400 541.500 No ( 0.59000 0.41000 )  
##     2) ShelveLoc: Bad,Medium 315 390.600 No ( 0.68889 0.31111 )  
##       4) Price < 92.5 46  56.530 Yes ( 0.30435 0.69565 )  
##    

이제 검정오차를 추정해보자. 전체 데이터의 반을 훈련셋 나머지 반을 검정셋으로 한다. type=“class”는 실제 클래스 예측값을 반환한다. 71.5%(86+57)/200 이다.

set.seed(2)
Carseats.train<-sample(1:nrow(Carseats),200)
Carseats.test<-Carseats[-Carseats.train,]
High.test<-High[-Carseats.train]
Class.carseats<-tree(High~.-Sales,Carseats,subset=Carseats.train)
pred<-predict(Class.carseats,Carseats.test,type="class")
table(pred,High.test)

##      High.test
## pred  No Yes
##   No  86  27
##   Yes 30  57

이제 교차검증 트리 pruning을 통해 검정오차를 개선해보자. 위 이론에서 설명한 비용 복잡성 pruining이 사용된다. 단 분류트리는 분류오류율을 기반으로 교차검증을 해야하므로 FUN=prune.misclass를 입력해준다. 200개 데이터이므로 교차검증의 k값은 default 10으로 한다. 회귀트리와 같이 결과의 k값은 pruning 식의 알파이고 dev는 각 size에 해당하는 교차검증 오차율이다. 9개 노드를 가질 경우 오차율이 50%로 가장 낮다.

set.seed(3)
cv.carseats<-cv.tree(Class.carseats,FUN=prune.misclass)
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"

plot(cv.carseats$size,cv.carseats$dev,type="b")

확정된 트리 갯수에 해당하는 트리를 pruning한다. 검정 오차가 77%((86+62)/200)로 향상됨을 확인할 수 있다.

prune.carseats<-prune.misclass(Class.carseats,best=9)
pred.prune<-predict(prune.carseats,Carseats.test,type="class")
table(pred.prune,High.test)

##           High.test
## pred.prune No Yes
##        No  94  24
##        Yes 22  60

최종 얻은 트리는 다음과 같다.

plot(prune.carseats)
text(prune.carseats,pretty=0)

의문점 및 개선점

1. 회귀트리도 분류트리 예제처럼 훈련오차율, 검정오차율, pruning된 검정오차의 변화의 확인해 보자.
2. 선택된 트리갯수만 pruning하지 말고 실제로 가능한 트리 갯수를 모두 pruning한 후 검정오차율을 서로 비교하면 최적의 pruning 갯수를 거꾸로 구할 수 있다. 예를들면, 회귀 트리에서 size=7뿐만 아니라 4,5를 하듯이 분류트리도 7,13,14 트리를 pruning하여 비교한다. 이것은 일종의 전체부분집합 검사와 같다 할 수 있다.

  선형회귀 vs 트리 예측

   다중선형회귀와 트리기반 예측은 상당히 유사한 점이 많다. 아래 표는 유사점을 비교한다.

 

구분	회귀분석	트리기반 예측
양적 반응변수	다중회귀	회귀트리
질적 반응변수	로지스틱회귀	분류트리
변수 또는 트리 선택 법	전체부분집합(subset)의 AIC, BIC, Cp 비교 또는 교차 검증	전진선택법과 유사한 재귀이진분할 --> 교차검증
변수 또는 트리 선택 기준	교차 검증 통한 변수 갯수 확정	교차 검증 통한 트리 갯수 확정
최종 선택	확정된 변수 갯수에 해당하는 전체 데이터셋의 회귀계수 도출	확정된 트리 갯수에 해당하는 트리 pruning