Decision tree learning (결정 트리 학습법)

Source : https://ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95_%ED%8A%B8%EB%A6%AC_%ED%95%99%EC%8A%B5%EB%B2%95

Decision Tree (DT)

개요

Input과 output을 연결시켜주는 예측 모델로, regression의 문제인 경우 regression tree, classification 문제인 경우 classification tree로 불린다. DT는 시각적인 방법으로 의사 결정이 어떻게 진행되는지를 보여줄 수 있는 장점이 있다. Input과 output을 요구한다는 점에서 supervised learning이다.

DT에서의 학습은 적절한 분할 기준에 따라 부분 집합들로 나누는 과정이고, 나뉘어진 자료 부분 집합에 다시 분할 과정이 진행되어 새로운 예측 값이 추가되지 않거나 부분 집합 노드가 목표 변수와 같은 값을 지닐 때 까지 계속된다. 이러한 방식을 Top-down induction of decision trees로 Greedy algorithm의 한 예이다.

용어를 보면, 내부노드 (비 리프노드)는 feature에 대한 test를 나타내고, 각각의 가지는 test의 결과를 나타낸다 (True or False). 그리고 각 리프노드 (터미널 노드)는 class의 label을 나타낸다. 마지막으로 트리의 최상위 노드는 root 노드이다.

다양한 알고리즘이 사용되고 있는데,

ID3, C4.5, C5.0, CART, CHAID, MARS, CIT등이 있다. 

학습 방법

DT의 알고리즘에서는 주로 하향식 기법이 사용되고, 각 단계에서는 주어진 데이터 집합을 가장 '적합한' 기준으로 분할하는 변수 값이 선택된다. 그렇다면 '분할의 적합성'을 측정하는 기준을 정해야한다.

1. 지니 불순도

Set에 이질적인 것이 얼마나 섞였는지를 측정하는 지표, CART에서 사용된다. 어떤 집합에서 한 항목을 뽑아 무작위로 라벨을 추정할 때 틀릴 확률을 말한다. 집합에 있는 항목이 모두 같다면 지니 불순도는 최솟값 0을 갖게 되고 이 집합은 순수하다고 표현한다.

지니 불순도는 다음과 같다.

fi는 i로 표시된 집합 안의 항목의 부분이다.

2. Information gain

이 식은 information theory의 entropy 개념에 근거를 둔다.

장점

1. 결과를 해석하고 이해하기 쉽다. - 명시적으로 어떻게 기준들이 생겼는지를 확인할 수 있어 이해하기 쉽다.

2. 자료를 가공할 필요가 거의 없다. - No 정규화

3. 수치 자료와 범주 자료에 모두 적용 가능. - regression과 classification에 모두 적용가능

4. 화이트박스 모델에 사용 

5. 안정적

6. 대규모의 데이터 셋에서도 잘 동작한다.

단점

1. Greedy algorithm을 사용하기 때문에, 최적의 결정 트리를 찾아내는 것은 아니다. (Greedy의 한계다.)

2. 복잡한 트리가 형성된다. (과적합, overfitting) 이때 pruning을 해야한다.

3. 데이터의 특성이 특정 변수에 수직/수평적으로 구분되지 못할 때 분류율이 떨어지고, 트리가 복잡해진다. 반대로 신경망은 여러 변수를 동시에 고려한다.