Search

Statistical Learning [4] - 트리기반 모형

Properties
Lecture
Machine Learning
Reference
ISLR, ELS
Author
Kipoong Kim
Date
2021/02/25
Link
Empty
Created
3/12/2021, 1:10:00 PM
Tags
Empty

Title: Data Mining: From Concepts To Modern Applications : [4] Supervised Learning - Tree-based Models

Tree-based Models

Regression Tree: a toy example

Baseball Player의 안타개수와 활동년수로 연봉을 예측하고자 함. > 가장 직관적인 방법이 무엇일까?

Regression Tree: a toy example

가장 직관적으로 (1) Years가 높을수록 연봉이 높아질 것이고, (2) 안타개수가 높을 수록 연봉이 높을 것이다. > 그리고 각 영역에 포함되는 Players의 연봉 평균을 예측값으로 사용하는 것이다.

Regression Tree: a set of rectangles

Regression Tree를 기하학적으로 표현하면 다음과 같이 predictor space를 partitioning하는 것과 같다.

Classification Tree: an example

Classification Tree는 Regression Tree와 마찬가지로 predictor space를 partitioning하는 것은 동일함. 대신 각 영역에 포함되는 샘플들의 평균값을 취하는 것이 아니라 각 영역에 포함된 관측치들 중에서 가장 많은 비율을 차지하는 클래스를 최종 예측치로 사용하고, 이를 "Majority Voting"이라고 부름.
아래 타이타닉 데이터 예시에서는, (a) 남자 여부, (b) 나이, (c) 형제 수 등의 기준에 따라 생존 비율이 카운트됨 (각각 0.17, 0.05, 0.89, 0.73). 그리고 0.5를 기준으로 생존비율이 높으면 해당 영역은 "생존"으로 예측하고, 생존비율이 0.5보다 낮으면 "사망"으로 예측함. 따라서, 각각 사망(0.17), 사망(0.05), 생존(0.89), 생존(0.73)으로 예측됨.

Classification And Regression Tree (CART) : Growing stage

Classification Tree와 Regression Tree를 합하여 Classification And Regression Tree (CART)라는 알고리즘으로 구현됨.
CART algorithm은 Growing Stage와 Pruning Stage로 구성됨.
(1) Growing Stage > 각 변수에 여러 기준를 적용하며 predictor space를 점점 partitioning하는 과정.
Cutoff value 선정 기준 > Regression Tree: cutoff value 기준으로 두 영역으로 나누었을 때, 각 영역별 SSE의 합이 최소가 되도록 하는 cutoff value를 선정함. > Classification Tree: 나누어진 영역별 불순도 (Gini Index 또는 Entropy) 값의 합계가 최소가 되도록하는 기준을 사용함.

Classification And Regression Tree (CART) : Pruning stage

예측성능 향상을 위한 Growing 과정이 계속 진행될 경우, 오히려 Overfitting 문제가 발생하게 됨.
이를 막기 위해, Pruning (가지치기) Stage를 실시함. > Cost complexity pruning: 트리의 terminal node 개수에 패널티를 주며 너무 많은 terminal node가 갖지 않도록 함. ※ terminal node: 트리의 맨아래쪽 영역 또는 predictor space에서 하나의 partition. > Terminal node 내 샘플의 개수 > Tree Depth (트리의 깊이)

Classification And Regression Tree (CART) : Pros and Cons

Pros > 직관적인 모형이라 설명하기 매우 좋음. > 시각적으로 보여주기 좋음 > 범주형 변수를 처리하기 좋음
Cons > Trade-off between Prediction and Inference에서와 같이, 예측성능이 매우 떨어짐.

Bootstrap Aggregation (Bagging)

우리가 만약 n개의 서로 독립적인 샘플(ZZ)을 가지고 있고 이들 각각의 분산이 σ2\sigma^2이라고 했을 때, 샘플 하나에서의 분산은 σ2\sigma^2이지만, 이들 평균 Zˉ\bar{Z}의 분산은 σ2/n{\sigma^2}/{n}임 > 즉, 우리는 하나의 샘플보다는 여러 샘플을 통합했을 때, 추정 오류를 줄일 수 있음.
그렇다면, 어떻게 새로운 데이터를 얻을 수 있을까?

Bootstrap Aggregation (Bagging): Bootstrap

Original Data로부터 replacement를 허용하는 복원추출을 하는 Bootstrap 과정을 통해 multiple samples를 얻을 수 있음

Bootstrap Aggregation (Bagging): Procedure

1.
Training set으로부터 총 B개의 Bootstrap Samples를 얻음
2.
B개의 Bootstrap samples로부터 B개의 Tree Model를 구축함.
3.
최종 예측치로 B개의 Tree Models로부터의 평균값 in Regression Tree 또는 Majority Vote in Classification Tree를 사용함.

Bootstrap Aggregation (Bagging): Why in classification problem?

25개의 tree model이 있고 각 tree model의 예측 에러는 0.35라고 했을 때 (단일 tree로는 100개 관측치 중 class를 정확하게 맞추는 관측치 비율은 65%임), majority voting으로 에러가 발생할 확률을 계산한다면 단 6%가 됨. ※ Error 발생 개수는 Binomial Distribution을 따르며, majority voting으로 에러가 발생하려면 25개 중 13개 이상의 error가 발생해야함.
즉, Bagging을 통해 Error를 급격히 감소시킬 수 있음.

Bootstrap Aggregation (Bagging): Why do they work?

Single Tree: 혼자서 의사결정 vs Bagged Tree : 다수결에 의한 의사결정

Random Forest

데이터 내 변수가 매우 많은 경우, 이들 모두를 모형에 포함하여 Tree model을 세우는 것은 매우 깊은 tree model로 이어지며 overfitting 문제를 일으킬 수 있음.
뿐만아니라, 변수 간 상관관계가 높은 경우, 상관관계가 높은 변수 모두를 포함한 Tree model은 Bagging을 통해서 dramatic variance reduction을 얻을 수 없음: ρσ2+1ρBσ2\rho \sigma^2 + \frac{1-\rho}{B} \sigma^2, 여기서 ρ\rho는 pairwise correlation between variables.
그에 따라, Random Forest는 각 Bootstrap Step마다 모든 변수를 사용하는 것이 아니라 m개의 변수만을 사용함. 이 때, 일반적으로 m=pm = \sqrt{p} 또는 p/3p/3를 사용함.
Follow me on Facebook and Github. Thank you
TOP