Tree 기반의 방법

Tree 기반의방법 박창이 서울시립대학교통계학과 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 1 / 25

학습내용 의사결정나무 (decision tree) 회귀나무 (regresion tree) 분류나무 (classification tree) 비교앙상블알고리즘 (ensemble algorithm) 배깅 (bagging) 랜덤포레스트 (random forest) 부스팅 (boosting) 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 2 / 25

개요 입력변수의공간을여러개의지역으로나누고, 주어진관측값에대한예측값으로그지역에속하는훈련데이터의반응변수평균값으로예측함. 입력변수에대한분할규칙이나무형태로요약되므로의사결정나무라고함해석이쉽지만예측력은떨어짐배깅 (bagging), 랜덤포레스트 (random forest), 부스팅 (boosting) 등여러개의나무모형을결합하여예측하는앙상블은예측력은향상되지만해석은어려워짐 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 3 / 25

의사결정나무 : 회귀나무 I Hitters 데이터에서 Years 와 Hits 를이용한 Salary 의예측 Salary 값이결측인관측값을제거하고 Salary 에대하여로그변환후회귀나무적용 회귀나무 Years < 4.5 5.11 Hits < 117.5 6.00 6.74 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 4 / 25

의사결정나무 : 회귀나무 II 영역분할 238 R 3 Hits R 1 117.5 R 2 1 4.5 24 Years 1 R 1 = {X Years < 4.5}, R 2 = {X Years >= 4.5, Hits < 117.5}, R 3 = {X Years >= 4.5, Hits >= 117.5} Years<4.5일때평균로그 Salary가 5.107이므로 e 5.107 혹은 165,174 달러로예측 Years가가장중요한변수임 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 5 / 25

의사결정나무 : 회귀나무 III 회귀나무모형적합 ( 단계 1) 입력변수 X 1,..., X p 들의공간을 J j=1 i R j (y i ŷ Rj ) 2 이최소가되도록 J개의서로겹치지않는영역 R 1,..., R J 로나눔. 여기서 ŷ Rj 는 R j 에서훈련데이터들의평균반응값 ( 단계 2) R j 에속하는입력값에대하여 R j 에속하는훈련데이터의 출력변수값의평균으로예측 모든가능한분할에대하여단계 1 을실시하는것은불가능. 대신반복이진분할 (recursive binary split) 를이용함 R 1 (j, s) = {X X j < s}, R 2 (j, s) = {X X j s} arg min j,s i:x i R 1(j,s) (y i ŷ R1 ) 2 + i:x i R 2(j,s) (y i ŷ R2 ) 2 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 6 / 25

의사결정나무 : 회귀나무 IV 분할영역예시 R5 R2 t4 X2 X2 R3 t2 R4 R1 t1 t3 X1 X1 X1 t1 X2 t2 X1 t3 X2 t4 R1 R2 R3 X2 X1 R4 R5 왼쪽위 : 반복이진분할로는불가능, 오른쪽위, 아래 : 반복이진분할에 의한영역분할, 나무모형, 예측값 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 7 / 25

의사결정나무 : 회귀나무 V 분할은종료조건 ( 가령, 각영역은적어도 5개이상의관측값이있어야함 ) 을만족할때까지계속이렇게생성된나무모형은너무복잡하여과대적합하는경향이있음. 따라서일단큰나무모형 T 0 를적합하고가지치기 (pruning) 하여부분나무모형을얻음 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 8 / 25

의사결정나무 : 회귀나무 VI 보통비용복잡도가지치기 (cost complexity pruning) 를적용각 α에대하여 T m=1 i:x i R m (y i ŷ Rm ) 2 + α T 를최소화하는부분모형 T T 0 를찾음 여기서 T : T 의단말노드 (terminal node) 의갯수, R m : m 번째 단말노드에대응되는영역, ŷ Rm : R m 에서의예측값. α 는조율모수로 CV 를이용하여결정함. α = 0 이면 T = T 0 이고 α 가 커지면단말노드의갯수에벌점이부여됨 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 9 / 25

의사결정나무 : 회귀나무 VII 회귀나무적합알고리즘 1. 훈련데이터에반복이진분할을적용하여단말노드에서의관측값들의갯수의최소값의정지규칙만족할때까지나무모형을성장 2. 각 α에대하여비용복잡도가지치기를적용하여부분나무모형을얻음 3. K-fold CV를이용하여 MSE의 K-fold CV값을최소화하는 α를선택 4. 선택된 α에대응되는부분모형을최종모형으로함 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 10 / 25

의사결정나무 : 회귀나무 VIII Hitters 데이터에대한가지치기이전의나무모형 Years < 4.5 RBI < 60.5 Hits < 117.5 Putouts < 82 Years < 3.5 Years < 3.5 5.487 4.622 5.183 5.394 6.189 Walks < 43.5 Runs < 47.5 6.407 6.015 5.571 6.549 Walks < 52.5 RBI < 80.5 Years < 6.5 7.289 6.459 7.007 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 11 / 25

의사결정나무 : 회귀나무 IX Hitters 데이터 : 단말노드의갯수에따른오차 Mean Squared Error 0.0 0.2 0.4 0.6 0.8 1.0 Training Cross Validation Test 2 4 6 8 10 Tree Size 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 12 / 25

의사결정나무 : 분류나무 I 주어진입력값에대하여예측할때입력값이속하는영역의 훈련데이터에서가장많이발생하는클래스 ( 다수결 ) 로예측함 오분류율자체는나무모형을성장시키는데있어충분히민감한측도가아님. 분류나무의영역분할에서는회귀나무의 RSS 대신지니지수 (Gini index) 나 cross-entropy 등의측도를사용함 지니지수 : G = K k=1 ˆp mk(1 ˆp mk ) Cross-entropy: D = K k=1 ˆp mk log ˆp mk 예측의정확도가목표일때에는가지치기시오분류율을측도로 이용함 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 13 / 25

의사결정나무 : 분류나무 II Heart 데이터 HD: 반응변수로 303명의가슴통증이있는환자들중혈관조형검사에서심장병유무를나타냄 Age, Sex, Chol과심장과폐의기능과관련된 13개의설명변수가있음 Sex, Thal(Thalium stress test), ChestPain은질적변수가지치기가안된모형에서 RestECG<1의두분할이동일한 Yes를예측하는것은오분류율이아닌지니지수나 cross-entropy를최소화하여생기는현상임. 사실그분할은오분류율을낮춰주지는않지만불순도의측도 ( 지니나 cross-entropy) 를낮춰줌 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 14 / 25

의사결정나무 : 분류나무 III Thal:a Ca < 0.5 Ca < 0.5 Slope < 1.5 Oldpeak < 1.1 MaxHR < 161.5 RestBP < 157 Chol < 244 MaxHR < 156 MaxHR < 145.5 Yes No No No Yes No ChestPain:bc Chol < 244 Sex < 0.5 No No No Yes Age < 52 Thal:b ChestPain:a Yes No No No Yes RestECG < 1 Yes Yes Yes Error 0.0 0.1 0.2 0.3 0.4 0.5 0.6 Training Cross Validation Test MaxHR < 161.5 No No Ca < 0.5 ChestPain:bc Thal:a Yes Ca < 0.5 Yes 5 10 15 No Yes Tree Size 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 15 / 25

의사결정나무 : 비교 I 선형모형과나무모형 장단점 선형회귀모형 : f (X ) = β 0 + p j=1 β jx j 회귀나무모형 : f (X ) = M m=1 c mi (X R m ) 나무모형은설명하기가쉬움. 또한인간의의사결정과정과유사하다고 생각하는사람들도있음 나무모형은그래프형식으로나타낼수있으며더미변수없이 질적변수를다룰수있음 일반적으로나무모형의예측력은다른방법에비해떨어짐 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 16 / 25

의사결정나무 : 비교 II 분류문제예시 X 2 2 1 0 1 2 X 2 2 1 0 1 2 2 1 0 1 2 2 1 0 1 2 X 1 X 1 X 2 2 1 0 1 2 X 2 2 1 0 1 2 2 1 0 1 2 2 1 0 1 2 X 1 X 1 위 : 분류경계가선형, 아래 : 분류경계가비선형 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 17 / 25

배깅 I 선형회귀는다른데이터에반복적용해도유사한결과를얻는분산이작은방법인반면, 의사결정나무는적합할때마다다른결과를얻을수있는매우분산이큰방법임 Z 1,..., Z n 이서로독립이며분산이 σ 2 일때 Z 의분산은 σ 2 /n을줄어듬따라서모집단에서여러개의훈련데이터를얻어서로다른예측모형을만든후결과에대한평균으로예측하면분산을줄일수있음그러나모집단에서여러훈련데이터를얻기어렵고대신 B개의다른붓스트랩 (bootstrap) 표본을생성하고각표본에서모형 ˆf b (x) 를적합한후 ˆf bag (x) = 1 B ˆf B b=1 b (x) 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 18 / 25

배깅 II 배깅에서는가지치기를하지않음으로써분산은크지만편의가작은모형을적합함. 이후평균을냄으로써분산을줄임분류문제에서는예측시 B개의나무모형의예측값에대한다수결원칙을적용함 OOB(out-of bag) 관측값은붓스트랩표본에서선택되지않은표본을말함. i번째관측값에대하여그관측값이 OOB인나무모형을이용하여예측할수있음. OOB 오차는 LOOCV와유사함 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 19 / 25

배깅 III Heart 데이터 Error 0.10 0.15 0.20 0.25 0.30 Test: Bagging Test: RandomForest OOB: Bagging OOB: RandomForest 0 50 100 150 200 250 300 Number of Trees 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 20 / 25

배깅 IV 배깅은단일나무모형보다예측력은향상되지만해석이어려움각변수의중요도는주어진변수에의한분할로인하여줄어드는 RSS 의평균으로구할수있음 Heart 데이터에서변수의중요도 Fbs RestECG ExAng Sex Slope Chol Age RestBP MaxHR Oldpeak ChestPain Ca Thal 0 20 40 60 80 100 Variable Importance 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 21 / 25

랜덤포레스트 I 배깅에서는 p개의설명변수모두를이용하여나무모형을적합하는반면랜덤포레스트는 m < p개의변수를랜덤하게선택하여나무모형을적합함. 보통 m p 설명변수들중하나가매우설명력이강한것이있을때, 배깅에서의모든나무모형은서로비슷해지며예측값에강한상관관계가존재하여평균을취하여분산이감소하는효과가줄어듬랜덤포레스트에서는평균적으로 (p m)/p개의분할에서는설명력이강한한변수가포함되지않음으로써예측값들의상관관계를줄여주는효과가있음 m = p인랜덤포레스트는배깅에해당 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 22 / 25

랜덤포레스트 II 15 클래스유전자데이터 (p = 500) Test Classification Error 0.2 0.3 0.4 0.5 m=p m=p/2 m= p 0 100 200 300 400 500 Number of Trees 단일분류나무 : 오분류율 45.7% 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 23 / 25

부스팅 I 회귀나무에대한부스팅알고리즘 1. ˆf (x) = 0, ri = y i, i 2. b = 1,..., B 에대하여 1 훈련데이터 (X, r) 에대하여 d 분할 (d + 1 개의단말노드 ) 나무모형 ˆf b 적합 2 ˆf (x) ˆf (x) + λˆf b (x) 3 r i r i λˆf b (x i ) 3. ˆf (x) = B b=1 λˆf b (x) 조율모수 나무모형의갯수 B 는너무크면과대적합이일어날수있음. CV 로선택 축소모수 λ = 0.01 혹은 0.001 사용 분할수 d( 교호작용의깊이 ). d = 1: stump 로가법모형 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 24 / 25

부스팅 II 15 클래스유전자데이터 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 단일분류나무 : 시험오분류율 24%, λ = 0.01 박창이 ( 서울시립대학교통계학과 ) Tree 기반의방법 25 / 25