의사결정나무(1) (Decision Tree)

데이터에 내재되어 있는 패터을 변수의 조합으로 나타내는 예측/분류 모델을 나무 형태로 만드는 것이다.

“스무고개” 놀이랑 비슷하다.

1. 의사결정나무 개요

데이터를 알고리즘을 이용하여 모델을 만드는 것

데이터를 2개 혹은 그 이상의 부분집합으로 분할 하여 데이터가 균일해지도록 분할 하는것이다.

분할은 분류와 예측으로 나눌 수 있다

분류 : 비슷한 범주를 가지고 있는 관측치끼리 모음

예측 : 비슷한 수치를 가지고 있는 관측치끼리 모음

2. 의사결정나무 모델(Regression Tree) concept

$X_{1}, X_{2}$ 의 분포를 보면 위 그래프 형태로 되어 있고 비슷한 특성 끼리 분할을 하였다. 파란색 공이 새롭게 오면 R6 분할에 속하고 분할 속의 공의 값이 3,4,5 라면 파란색 공의 값은 $\dfrac{3+4+5}{3} = 4$로 파란색 공의 예측값은 4로 판단할 수 있다.

3. 의사결정나무(Regression Tree) 모델

$C_{m}$ : 회귀나무모델로 부터 예측한 $R_{m}$ 부분의 예측값

$\hat{f}(x) = \sum_{m=1}^{6}c_{m}I{(x_{1},x_{2}) \in R_{m}}$

$= c_{1}I{(x_{1},x_{2}) \in R_{1}} + c_{2}I{(x_{1},x_{2}) \in R_{2}}$

$+ c_{3}I{(x_{1},x_{2}) \in R_{3}} + .. + c_{5}I{(x_{1},x_{2}) \in R_{5}}$

$+ c_{6}I{(x_{1},x_{2}) \in R_{6}}$

I 는 중괄호의 값이 False 이면 0 , True 이면 1을 주는 indicator function 이다. 데이터가 $R_{m}$에 속하는면 1, 속하지 않으면 0

예를 들어 데이터가 $R_{3}$ 지역에 속할 때,

$\hat{f}(x) = c_{1} \times 0 + c_{2} \times 0 + c_{3} \times 1 + c_{4} \times 0 + c_{5} \times 0$

$= c_{3}$

예측할 데이터가 들어 왔을 때 하나의 숫자로 예측하는 모델이다.

4. 예측나무 모델링 프로세스

데이터를 M개로 분할 : $R_{1}, R_{2},…,R_{m}$ <- 끝마디가 M개

최상의 분할은 cost function 를 최소로 할 때 얻어진다.

$min_{c_{m}}\sum^{N}_{i=1}(y_{i}-f(x_{i}))^{2}$

$= min_{c_{m}}\sum^{N}_{i=1}(y_{i}-\sum_{m=1}^{M}c_{m}I(x \in R_{m}) )^{2}$

$\hat{c}_{m} = ave(y_{i}|x_{i} \in R_{m})$

$c_{m}$은 각 분할에 속해 있는 y값들의 평균으로 예측했을 때 오류가 최소

5. 분할변수와 분할점의 결정방법

$argmin_{j,s}[min_{c_{1}}\sum_{x_{i} \in R_{1}(j,s)}(y_{i} – c_{1})^{2}$

$+ min_{c_{2}}\sum_{x_{i}R_{2}(j,s)}(y_{i}-c_{2})^{2}]$

$= argmin_{j,s}[\sum_{x_{i} \in R_{1}(j,s)}(y_{i} – \hat{c}_{1})^{2}$

$+ \sum_{x_{i}R_{2}(j,s)}(y_{i}-\hat{c}_{2})^{2}]$

$\hat{c}_{1} = ave(y_{i}|x_{i} \in R_{1}(j,s))$ and $\hat{c}_{2} = ave(y_{i}|x_{i} \in R_{2}(j,s))$

예를 들어 $X_{1}, X_{2}, X_{3}$의 변수 3개가 있고

$X_{1}$ 변수는 2, 3

$X_{2}$ 변수는 5, 6

$X_{3}$ 변수는 1, 7

의 값을 가지고 있다.

$X_{1} > 2$

$X_{1} > 3$

$X_{2} > 5$

$X_{2} > 6$

$X_{3} > 1$

$X_{3} > 7$

인 모두의 경우의 수를 대입했을 때 $X_{2} > 5$ 인 경우에 최소값인 경우 분할변수 $X_{2}$, 분할점 5 가 된다.