결정트리

의사결정 나무란?

주어진 입력값들의 조합에 대한 의사결정 규칙(rule)에 따라 출력값을 예측하는 모형으로 트리구조의 그래프로 표현하는 알고리즘이다.

• 의사결정나무모형의 예측력은 다른 지도학습 기법들에 비해 대체로 떨어지지만, 해석이 수월하다는 장점이 있다.
• 분류문제를 다루는 분류나무, 회귀문제를 다루는 회귀나무가 있다.
• 의사결정나무모형에 사용되는 용어
  • 뿌리마디 (root node) : 시작되는 마디로 전체 자료를 포함
  • 자식마디 (child node) : 하나의 마디로부터 분리되어 나간 2개 이상의 마디들
  • 부모마디 (parent node) : 주어진 마디의 상위마디
  • 끝마디 (terminal node): 자식마디가 없는 마디
  • 중간마디 (internal node) : 부모마디와 자식마디가 모두 있는 마디
  • 가지(branch) : 뿌리마디로부터 끝마디까지 연결된 마디들
  • 깊이 ( depth ) :뿌리마디로부터 끝마디까지의 중간마디들의 수

가장 중요하다 생각하는 결정규칙 (decision rule)을 어떻게 정하는지 설명하겠다.

각 노드에서 여러 Feature들 중에서 목표변수(가격, 성공예측 등)를 가장 잘 구분할 변수를 찾는다. 이떄 순수도(purity), 불순도(impurity) 개념을 사용한다.

순수도가 높다는건 한 노드에 비슷한 값이 많이 모인다를 의미한다.

 

불순도 측정 방법

1. 분류 문제 ( 범주형 ) : 지니지수, 엔트로피

2. 회귀 문제 ( 연속형 ) : 분산감소, MSE 등

 

---

지니 지수 ( Gini index )

쉽게 설명해보겠다. 총 10개의 클래스가 있고 A 클래스가 7개 B 클래스가 3개가 존재한다.

이때, Pa = 0.7, Pb = 0.3으로 표현할 수있다.

이때 제곱을 하면 0.49, 0.09로 나오게 된다 이 두 값을 합하고 1을 빼면 지니계수를 구할 수 있다.

0에 가까울수록 순수, 1에 가까울수록 불순하다고 할 수 있다.

 

엔트로피 ( Entropy index )

지니 계수와 연산 과정이 비슷하지만 로그를 적용함으로써 복잡도가 늘어났다.

 

각 연산의 특징을 정리해보겠다.

• 지니계수와 엔트로피는 모두 불순도를 측정하지만, 계산 방식과 분할 특성, 연산 효율성에서 차이가 있다.
• 지니계수는 계산이 빠르고 단순하며, 엔트로피는 정보 이론적 해석이 가능하고 분할의 균형을 중시한다.
• 실제 의사결정나무에서는 두 지표 모두 사용 가능하며, 데이터 특성이나 목적에 따라 선택한다.

 

과정

1. 모든 변수와 가능한 분할값을 시험

2. 각 경우마다 분할 후 자식 노드의 순수도가 얼마나 높아지는지(불순도가 얼마나 낮아지는지) 계산한다.

3. 최적의 변수와 기준값을 선택해서 분할한다.

4. 반복

 

분할이 무의미하거나, 최대 깊이 도달시 정지한다.

과적합을 방지하기위해 Pruning을 한다.