의사결정나무(Decision Tree)
#1. 의사결정나무란?
어떤 레코드 집합이 있을때, 이레코드들을 작은 소수의 homogeneous한 그룹으로 나누는 트리
목표변수 측면에서 부모노드보다 더 순수도가 높은 자식노드들이 되도록, 데이터를 반복적으로 더 작은 집단으로 나눔
예를 들어, 스무고개!
앞선 질문에 따라 답이 달라지고, 루트노드로 부터 시작해서 계속적인 질문들이 나오게 되고 자식노드로 이어짐
마지막 말단노드는 특정 분류값을 가지는 class를 가지게 됨
* 의사결정나무는 목표변수가 이산형인 1)분류나무와 목표변수가 연속형인 2)회귀나무로 분류됨
1) 분류나무 (이산형)
- 이진트리 vs. 다진트리
- 집단을 나누는 기준(순수도)은 Gini 척도, 정보이익, 카이제곱 값을 기준으로 나뉨
2) 회귀나무 (연속형)
- 집단의 평균을 이용하여 분산값, F-test를 이용해 가지치기가 진행됨
-좋은 분할은 목표변수의 분산을 줄임(당연)
- 하지만, 보통 인공신경망, 회귀분석이 더 성능이 좋기 때문에 연속형 목표변수일 경우 다른 알고리즘을 추천
#2. 특징
1) 대표적인 분류 기법
- 예측기법으로 쓰일 수 있음. 다만 예측의 경우 신경망이나, 회귀분석의 성능이 더 좋기에 의사결정나무 기법을 대표적인 알고리즘으로 보기 어려움
2) 이해와 설명이 쉬운 모델
- if then의 형태로 매핑되 룰을 이용해 시스템에 구현될 수 있기 때문에 사람들이 봐서 쉽게 이해할 수 있다는 장점이 존재
- 즉, 투명성, 이해가능성이 높음
3) 목표변수에 중요한 변수가 무엇인지 쉽게 이해하는데 도움을 줄 수 있음
4) 분류, 범주 수가 많지 않은 경우 사용(2진, 3진 분류의 경우)
5) 데이터 사전처리가 많이 필요하지 않음
6) 연속형, 범주형 섞여 있어도 사용 가능
- 특히 missing value 값도 의미있게 사용 가능함. 즉, 결측값 자체도 의미가 있다고 봄
#3. FULL TREE
- 분할 시도를 중지할 경우
1) 주어진 노드의 순수도를 유의한 수준으로 증가시키는 분할이 없을 때
2) 해당 노드에 속한 레코드의 수가 미리 설정한 하한선에 도달했을 때
3) 나무의 깊이가 미리 정해 놓은 한계에 도달했을 때
- 분할 시도가 중지되었을 때를 최대나무(FULL TREE)라고 함
- 최대나무(FULL TREE)는 일반적으로 새로운 레코드들의 집합을 분류하는데 최상의 성과를 제공하는 나무는 아님
_Why? Overfitting 때문에
*Overfitting이란, 전체 모집단의 전반적인 패턴 뿐만 아니라 특정 훈련용 데이터 집합에서만 나타나는 지엽적인 패턴까지도 학습한 것
- 복합한 나무 내에, 더 단순하고 더 안정적인 나무들이 존재한다.! --> 가지치기의 필요성
#4. 대표적 알고리즘 (CART, C5)_ 가지치기 방식이 다름
1) CART
- Gini 계수기반 알고리즘
- 이진분류(Binary) 진행
- regression, classification 둘다 지원
* Gini 척도란? 클라스 비율의 제곱의 합 (순수할 경우 1)
<CART의 가지치기 알고리즘>
1. 이진나무(Binary)를 생성, 순수도를 증가시키는 것으로 확인되는 분할들 계속 진행
2. 가지가 제거된 후보 나무들을 생성하여 훈련, validation set 사용하여 가장 나은 나무 선정
- 어떻게 가지 제거? Adjusted Error rate(부정오차비율) 사용
AE(T) = E(T) + α*leaf_count(T)
(α크기가 크면 error가 올라감 즉, 가지 많을수록 penalty를 주는 방식)
3. 테스트 집합을 통한 최종 나무 평가: error가 가장 작은 트리 선택
4. 오분류를 최소화하는 나무 선택
2) C5 (머신러닝 기법)
- Entropy 기반 알고리즘
- validation set 사용하지 X
- 다진분류(Multiple split) 진행
- Bushy trees(잔가지가 많은 트리)의 경우 단순히 가지의 수가 늘어남에 따라서 엔트로피가 감소하게 되는데,
이것을 내재 정보(intrinsic information이라고 부름)_ Information Gain만 사용할 경우 내재정보에 의존
따라서, 내재 정보만을 고려하여 생성된 의사결정나무는 가지가 많아지는 경향이 있으며 이를 해결하기 위해
가지에 패널티를 부과_Information Gain Ratio를 사용하여 가지의 갯수가 많아지는 경우 패널티 부과
*Entropy란? 순수하면 값이 0/ 순수하지 않으면 1
*Information Gain이란?
- IG= 분기 전의 entropy - 분기 후의 entropy
Ex. 1- 0.47 = 0.53 (클수록 잘 분리되었다고 생각하면 됨)
*Information Gain Ratio란?
- IGR = IG/IV(Intrinsic Value)
N: 특정 지표로 분기했을 때 생성되는 가지의 수, pi: 번째 가지에 해당하는 확률
<C5의 가지치기 알고리즘>
1. 비관적 가지치기
- 각 노드의 오차비율을 살펴본 후 실제 오차비율은 이보다 높다고 가정함으로써 나무의 가지를 침
- 쉽게 말해, 훈련용 데이터 에러보다 테스트 데이터 에러가 더 높을 것이라는 가정.!
2. 베르누이 이항분포에 근거
- N개의 레코드가 노드에 도달하고, 그 중 E개가 틀리게 분류 되었다면 오차비율은 E/N
- 여기서 맞을 확률/틀릴 확률 베르누이 이항분포에 근거하여 추론진행. N번 시행 몇개 틀렸는지에 대한 기댓값 구하는 것 가능
- 이에 따라 신뢰수준에 대한 Error 값의 예측구간, 신뢰구간 구하는 것이 가능
- 노드가 적을수록 예측 오차비율은 높아짐 (n이 작으면 신뢰구간 길어지니까 오차비율이 높아진다고 볼 수 있음)
- 만일 부모노드의 오차 수에 대한 상단 끝의 추정값이 자식노드들의 오차 추정 값보다 적다면 자식노드를 가지침
- 즉, C5 알고리즘은 조건절들이 X, 오차비율과 원래의 오차비율을 비관적 오차비율 가정에 의해 비교하면서 최대한 규칙을 줄이고자 함
3. 비용함수를 고려
- 오분류율*오분류비용을 고려한 가중치인 비용함수를 사용하게 됨 (즉, 오차함수 사용X)
- why? domain에 따라 오분류 비용이 다르기 때문임
예시> 의학검사에서는 False Negative가 False Positive보다 해로움
#5. CART와 C5의 문제점
- 불안정한 노드를 제거하지 못함
* 하지만 현재 많은 데이터 마이닝 도구들이 사용자들이 수동으로 의사결정나무를 가지치기 할 수 있도록 지원하고 있음
* 일부 데이터 마이닝 도구는 자동 안정성 기반 가지치기 기능 제공