[ML] Decision Tree (결정트리) 기본 다지기

 

 

Decision Tree란?

 

- 데이터를 분석하여 이들 사이에 존재하는 패턴을 예측 가능한 규칙(Rules)들의 조합으로 나타냄

- 모양이 '나무'와 같다고 해서 의사 결정 나무 라고 불림

 - 질문을 던져서 대상을 좁혀 나가는 '스무고개' 놀이와 비슷한 개념

 

 

아래 의사 결정 나무를 시각화 표시한 것으로 간략하게 어떤 기준으로 분류가 되면서 데이터를 분류하는 지 눈으로 한번 익혀보자

 

 

 

 

 

Decision Tree의 기본적인 원리

 

 

- Linear Regression과 다르게 Model의 Complexity를 극한으로 높일 수 있음(하지만 이로 인해 Overfitting이 일어날 수 있음)

- 아래 예제와 같이 만약 Terminal node수가 3개 뿐이라서 새로운 데이터가 100개, 1000개가 주어진다고 해도 의사 결정 나무는 정확히 3종류의 답(Rule)만을 출력함.

 

※ Root node : 뿌리 마디

※ Internal node : 중간 마디

※ Terminal node : 끝 마디 

 

 

 

 

 

그럼 이 각 Node들은 어떤 원리로 나뉘어지게 되는 걸까 ? 

 

바로, Classification Measuring Impurity 방법으로 node를 나누게 된다.

이렇게 되면

- 순도 (Homogeneity)를 최대로 증가시키는 방향

- 불순도(Impurity) 혹은 불확실성(Uncertainty)을 최소로 감소시키는 방향으로 나누게 된다.

 

예시로는 불순도를 사용 할 것이다.  이때 불순도를 지니 계수(Gini index)를 사용하여 node를 나누게 되는데 지니 계수에 대해 잠시 알아보면,

 

지니 계수란, 불순도를 측정하는 지표로서, 데이터의 통계적 분산 정도를 정량화해서 표현한 값으로 이를 식으로 표현하면 다음과 같다.

 

 

 

만약 파랑 공 6개(K=1)와, 주황 공 10개(K=2)가 한 네모상자안에 들어있다고 가정해보자 이때의 불순도는 아래와 같은 식에 의해 0.47이 될 것이다.

 

 

※ Measuring Impurity 1 : Gini Index (Max 0.5, 0일때 가장 잘 나누어 진 것)

 

여기에 추가로  나누어 2개 이상의 영역으로 나뉘어질 경우 불순도 값을 구하는 식은 다음과 같다.

 

 

식이 어려우니 예를 들어 추가 설명 하면, 위의 예시에서 반으로 나누어 영역을 분할 했다고 가정하면 이때의 불순도를 측정 하면

다음과 같다. 

이렇게 전체의 불순도는 0.47 이었는데 영역을 분할 후에 불순도는 0.34로 0.13 정도 하락하게 된다 이때 이 값을 Information gain이라고 한다.

 

이때 가장 큰 Information gain을 가지는 곳을 먼저 Split 하게 된다

 

 

 

 

위에 배운 내용을 토대로 Decision Tree를 나누는 것을 그림으로 표현 하여 설명해보겠다.

 

아래 와 같이 각 변수 들에 대해 변수의 Min, Max 범위에서 영역을 반으로 나눠가며 Gini Index를 산출한다.

이렇게 Gini Index가 가장 낮은 Point를 갖고 있는 변수가 Root Node가 되는 것이다.

(아래 그림에 순서에 따라 확인해보면 된다.)

 

 

자 이제 Information Gain을 활용해서 하위 Node(internal, terminal node)가 어떻게 구성되는지 알아보자

 

1. 위의 작업을 통해 Gini Index가 가장 낮은 Point를 갖고 있는 변수를 찾는다

2. 아래 예시와 같이 변수 1이 가장 낮은 Gini index를 갖고 있고 그 Point는 70이라고 가정 하면

3. 변수 2는 변수 1의 70이하에 대한 데이터를 기준으로 Min, Max 영역에 따른 Information Gain이 가장 큰 Point를 찾는것이다.

 

 

 

 

 

 

하지만, 모든 변수의 경우의 수에 대해 전부 다 Split 을 하게 되면 100%의 순도와 불순도 0%를 갖게 될 수 도 있다.

이는 Overfitting을 발생 시켜 오히려 Error을 더 심하게 할 수 있는 요인이 된다.

 

 

 

 

이렇게 모든 Terminal node의 불순도가 0, 순도가 100%인 상태를 Full Tree 라고 정의하는 데 Overfitting을 방지 하기 위해서 적절한 수준에서 Terminal node를 잘라줘야 한다.

 

 

 

Decision Tree은 위와 같이 복잡하다고 해서 좋은 것이 아니다. Model 이 복잡해질 수록 해석력이 떨어져 오히려 좋지 않은 모델이 될 수 있다.

 

이를 위해 Max Depth 라는 것이 있다. 경우의 수라고 보면 되는데 아래 예시의 경우 Max depth가 5이다. 

추천 하는 것은 Max depth를 5를 넘기지 않는 것을 추천 한다.

사실 Decision Tree의 경우 가장 중요한 점이 강력한 해석력을 갖고 있고 Rule을 Extraction을 할수 있다는 가장 큰 장점이 있다.

이를 위해 Max Depth가 5를 넘어갈 경우 해석력이 떨어져 그다지 권장을 하지 않는 편이다.

 

Simple is the Best!!!

 

 

이상 여기까지 머신러닝 알고리즘 중 하나인 Decision Tree에 대해 알아보았다.