Must Learning With Statistics

의사결정나무 1 [CART] 본문

데이터마이닝

의사결정나무 1 [CART]

Doublek Park 2020. 4. 23. 23:55
데이터마이닝-4장-의사결정나무.utf8

1. CART (Classification and Regression Tree)

 의사결정나무는 정말 많은 분야에서 활용이 됩니다. 최근에는 의사결정나무가 아닌 다른 알고리즘들을 많이 활용한다 해도, 지금 당장 Google scholar에서 ‘Decision Tree’라고 검색을 하면 상당히 많은 최신 논문들이 검색이 되는 것을 확인할 수가 있습니다. 또한 의사결정나무는 보통 기계학습을 입문하시는 분들이 처음 접하시는 알고리즘이기도 합니다. 그렇기에 의사결정나무를 그냥 대충하고 넘어갈 수는 없습니다. 의사결정나무의 기본 컨셉은 알고리즘에 사용되는 Features에 대해 분리를 하는 것에서 시작합니다. 여러분들 모두 심리테스트 책을 보셨을 것이고, 거기서 ’당신은 OO에 해당하나요?’ 라는 질문에 대한 답을 한 적이 있을 것입니다. 의사결정나무는 이와 비슷한 과정으로 분류모형이 이루어진다고 생각하시면 됩니다. 그렇다면 Features를 분리한다는 개념은 어떤 것을 의미하는지 알아보도록 하겠습니다. R에서 기본으로 제공되는 Iris 데이터 셋과 함께 다루어보도록 하겠습니다.

'data.frame':   150 obs. of  5 variables:
 $ Sepal.Length: num  5.1 4.9 4.7 4.6 5 5.4 4.6 5 4.4 4.9 ...
 $ Sepal.Width : num  3.5 3 3.2 3.1 3.6 3.9 3.4 3.4 2.9 3.1 ...
 $ Petal.Length: num  1.4 1.4 1.3 1.5 1.4 1.7 1.4 1.5 1.4 1.5 ...
 $ Petal.Width : num  0.2 0.2 0.2 0.2 0.2 0.4 0.3 0.2 0.2 0.1 ...
 $ Species     : Factor w/ 3 levels "setosa","versicolor",..: 1 1 1 1 1 1 1 1 1 1 ...

Iris 데이터 셋은 유명하기에 데이터 셋에 대한 설명은 넘어가도록 하겠습니다. 우리의 목표는 꽃들의 특성에 따라 분류를 하는 의사결정 알고리즘을 만들고자 하는 것입니다. 일단 의사결정나무 알고리즘의 결과를 먼저 확인한 다음 내용을 다루어보도록 하겠습니다.

의사결정나무는 위의 형태로 생겼습니다. 학습 데이터들에 대해 특정 조건(예를 들어, Petal.Length가 1.9이하인지 아닌지)을 만족하는지 여부에 따라 분류작업을 진행합니다. 여기서 특정조건이라는 것이 바로 Feature들을 분리하는 것이라고 이해하시면 됩니다. Petal.Length, Petal.Width 등의 알고리즘은 모두 연속형 변수들입니다. 우리는 이러한 연속형 변수들에 대해 이진선택을 할 수가 없습니다. 그렇기 때문에 연속형 변수들에 대해 최적의 분리점을 찾는 것이 의사결정나무에서 매우 중요한 과제 중 하나입니다. 우리는 이 최적의 분리점을 찾아가는 방식에 대해 ’재귀적(recursive)’라고 합니다.

위 산점도를 살펴보시면, 의사결정나무 알고리즘은 꽃들의 Species를 분류하기 위한 최적의 분리점을 찾아냈습니다. 의사결정 나무에서는 각 변수들의 분리점으로 인해 생겨난 세부 영역들에 존재하는 데이터들에 대해서는 동일한 예측값을 제공합니다. 만약 영역 내에 다른 범주의 데이터가 함께 포함되어 있다면 그것은 곧 분류 오차라고 할 수 있습니다.

Regression Tree

 보통의 기계학습 알고리즘은 분류문제를 푸는데 많이 활용이 되지만, 의사결정나무는 연속형 반응변수들에 대해서도 예측을 진행할 수가 있습니다. 예측 방법은 동일합니다. 주어진 Features에 대해 분리점을 만든 다음, 분리된 영역들에 대해 예측값을 계산합니다. 최적의 분리점을 찾는 방법은 원리만 생각했을 경우 매우 간단합니다. 이 책을 보시는 분들은 모두 선형회귀의 최소제곱법은 알고 계실 것입니다. 최소제곱법에서 \(\sum(y_{i}-\hat{y}_{i})^2\)이 최소가 되는 회귀 계수를 찾듯이, 의사결정나무또한 잔차가 최소가 되는 Feature들의 분리점을 찾고자합니다. 의사결정나무에서 연속형 변수에 대한 예측식은 다음과 같습니다.

\[ f(x)=\sum_{n=1}^{N}c_{n}I(x\in R_{n}) \]

위 식에서 \(R_{n}\)은 분리된 영역\((R_{1},R_{2},\cdots,R_{N})\)을 의미합니다. \(c_{n}\)은 상수항으로 반응변수를 의미합니다. 즉, 같은 영역에 속해있는 데이터들에 대해서는 상수항인 \(c_{n}\)을 예측값으로 활용한다는 것입니다. 그렇기에 우리가 예측해야되는 값 \(c_{n}\)은 추정값을 의미하는 \(\hat{c}_{n}\)으로 표현할 수 있습니다. \(\hat{c}_{n}\)은 동일 파티션에 포함되는 데이터들의 평균값으로 계산을 합니다.

\[ \hat{c}_{n} = \frac{1}{K}\sum_{i=1}^{K}(y_{i}|x_{i}\in R_{n}) \]

Feature의 최적의 분리점을 찾는 방식은 예들어 변수 \(x\)에 대해 분리점 \(s\)를 적용했다고 생각해보겠습니다. 그렇다면 데이터의 영역은 다음의 2영역으로 나누어집니다.

\[ R_{1}= \{x\leq s\},\ R_{2} = \{x> s\} \]

그렇다면 의사결정나무 알고리즘은 각 영역에 대한 예측값 \(\hat{c}_{1}\)\(\hat{c}_{2}\)를 계산하게 됩니다. 그렇게 되면 예측값과 실제값과의 차이는 다음의 식으로 계산이 됩니다.

\[ \sum_{x_{i}\in R_{1}}(y_{i}-\hat{c}_{1})^2 +\sum_{x_{i}\in R_{2}}(y_{i}-\hat{c}_{2})^2 \]

그리고 의사결정나무는 가장 적은 오차를 발생하는 분리점을 찾을 때까지 계산을 반복합니다. 식을 정리하면 다음과 같습니다.

\[ \min_{x,s}[\min_{c_{1}}\sum_{x_{i}\in R_{1}}(y_{i}-\hat{c}_{1})^2 +\min_{c_{2}}\sum_{x_{i}\in R_{2}}(y_{i}-\hat{c}_{2})^2] \]

Comments