Decision Tree

의사결정나무는 교사학습방법 중 하나라고 알려져 있으나 비교사학습에서도 쓰일 수 있다. 의사결정나무는 데이터의 특징에 대한 질문을 하면서 응답에 따라 데이터를 분류해가는 알고리즘이다. 그렇다면 왜 굳이 의사결정나무를 사용할까? 라는 의문이 든다. 이유는 단순 선형분류기로는 풀기 어려운 XOR(eXclusive OR)같은 문제를 풀 수 있다는 것과 나이브베이즈와 같이 데이터에 대한 가정없이 데이터만 있으면 바로 생성할 수 있다는 점이다. 밑에 그림을 보면

 성별, 나이, 배우자/형제자매수라는 특징에 대해 질문을 하여 그 반응에 따라서 사망과 생존을 분류한 결정트리이다.  결정트리의 구조는 크게 2가지로 '노드(node)'와 '가지(branch)'으로 나눌 수 있다.  특정 노드보다 상위의 노드를 부모노드(parent node), 반대로 특정노드보다 하위의 노드를 자식노드(child node)라고 한다. 더 이상 부모노드가 없는 노드를 뿌리노드(root node)라고 하며 더이상 자식노드(child node)가 없는 노드를 잎노드/끝노드(leaf/terminal node)라고 한다. 잎노드가 아니지만 중간에 끝나는 노드를 중간노드(internal node)라고 한다. 끝으로 세로로 난 가지의 개수가 그 트리의 깊이(depth)라고 한다.

위 그림을 보면 각 노드들에서의 질문은 상위노드들의 질문과 연관성이 있다. 예를 들어 '나이가 9.5살보다 많나?'라는 질문은 위의 '남자인가?'라는 질문에서 '예'인 경우에 이어지는 질문이므로 상위 질문인 '남자인가?'가 연관이 있다. 이러한 관계때문에 결정트리는 피처의 연관성을 잘 표현한다는 특징을 갖고 있다. 이러한 특징때문에 비교사학습의 규칙학습/연관분석에서 패턴을 찾을때 결정트리를 사용한다. 

그렇다면 이제 결정트리가 어떻게 작동하는지를 알아보자. 결정트리의 작동방식은 간단하다. 그냥 노드를 잘 나누어 분류 혹은 예측을 잘하면 끝~ 이라고만 하면 좋겠지만 사실 이보다는 복잡하다.

각 설명변수가 순서대로 하나씩 처리가 되는데 설명변수에 따른 엔트로피 혹은 지니불순도를 이용하여 정보획득량(구분조건은 이외에도 카이스퀘어 통계, 이득비율이 있다.)을 측정해 정보획득량이 많은 변수의 Threshold값을 best attribute로 정해 최종적으로 엔트로피가 0인 가장 순수한 잎노드를 만드는 것을 목표로 한다. 처음으로 가장 잘 나누어지는 Threshold값을 찾아내면 이는 목표변수에 대한 설명력이 가장 높은 변수의 Threshold값이 되는것이다. 처음 분류된 이후 그 다음으로 현재 분류상태보다 더 잘 나뉠 수 있는 변수(첫번째도 포함)의 Threshold값을 다시 찾는다. 이러한 방식을 보고 recursive 하다고 한다. 이러한 과정을 반복하여 모든예제가 다 분류가 됐거나, 더 이상 예제간 구별한 속성이 남아 있지 않거나, 미리 정한 크기 범위에 트리가 도달할때 까지 반복을 시킨다 (사전가지치기).

잘 나누어 진다는 말은 분류트리에서는 현 Threshold값을 기준으로 전보다 가장 엔트로피(혹은 지니불순도)가 낮아지는 다시말해 정보이득이 가장 큰 분류가 된다는 말이겠고, 회귀트리에서는 이 Threshold 값으로 나누어 각 영역의 평균값이 반응변수와의 편차를 가장 많이 줄인다는 것이다. 그렇다면 여기서 '잘 나누어진다' 라는 것의 기준은 어떻게 정하는가? (참고로 Threshold와 cut-off value는 같은말이다.)

이를 위해서는 일단 앞에서 나온 엔트로피(지니불순도나 엔트로피 혹은 분산)에 대한 이해가 필요하다.

엔트로피는 순종성을 측정하는 한 방법으로 H(X), 엔트로피 최소값 0은 표본이 완전 하나임(순종성의 최대값)을 나타내고 엔트로피 최대값인 1은 다종성의 최대값을 나타낸다. 

위 그림에서 보듯 0.5 구간이 엔트로피가 가장 높고 한 범주가 다른범주에 우세할 수록 엔트로피는 0 (순종성이 극대화)에 가까워 진다.

쉽게 설명해서 분류된 데이터가 한 범주로만 구성(순종성이 최대)되어 있을때 엔트로피는 낮고 2범주 혹은 그 이상의 범주(다종성)로 구성되어 있으면 엔트로피가 높아진다. (엔트로피가 받아들이기 거북하다면 엔트로피를 그냥 불확실성이라고 생각하자)

왜 이런 엔트로피가 필요하느냐? 우리가 데이터가 분류가 잘된 데이터인지 그렇지 않은 데이터인지를 볼때 계량적인 수치가 있어야 이를 정확하고 객관적으로 판단할 수 있기 때문에 이것이 필요하다. 

하지만 이런 엔트로피로는 현재의 데이터의 순종성만 나타낼 뿐 어떠한 속성으로 구분할 지를 결정해 주진 못한다. 따라서 속성간의 비교를 할 수 있는 정보이득이 나온다. 이 정보이득이 가장 높은 변수의 Threshold 값을 분류기준으로 선택한다.

정보이득의 공식은 다음과 같다.

회귀트리에서는 불순도를 분산 혹은 표준편차로 측정하고 분류트리에서는 정보이득이라는 말이 회귀트리에서는 분산축소 혹은 표준편차축소라는 것으로 바뀐것 빼고는 내용은 같다. 단지 회귀같은 연속형 변수값들을 다루는데에는 이산형 변수값을 보는 entropy는 어울리지 않기 때문에 분산, 표준편차를 불순도의 기준으로 삼아 표준편차축소를 구하여 해당 변수의 Threshold가 분류가 잘 되었는지를 판단한다.

아래의 공식은 표준편차 축소 공식이다. 엔트로피가 표준편차로 바뀌었을뿐 식은 정보이득 식과 같다.

이 기준들을 이용하여 정보획득량(Information gain)이 높아지는 방향으로 가면 이 변수의 threshold값이 예제를 잘 나눈다는 말이고, 회귀트리는 분산 혹은 표준편차 축소가 많이 되는 것이 이 변수의 threshold값이 y편차를 가장 줄이는 임계값이라는 말이다. 여기서 분류트리에서는 노드를 나누는 기준에 따라서 알고리즘들이 CART와 ID3, C4.5, C5.0 그룹으로 나뉜다. 

그러나 결정트리에는 몇가지 단점이 있는데

1.  결정트리는 탐욕 알고리즘 같은 휴리스틱 기법을 기반으로 하기때문에 전역 최적값을 찾는다는 보장이 없다는 것이다. greedy하기 때문에 현재에서 가장 정보이득이 큰 변수를 선택할 것이다.(지역최적해) 그러나 전역적으로 보면 그 시기에 2번째로 정보이득이 큰 변수를 선택 할때 그 다음 자식노드들에서 엔트로피가 가장 감소하는 혹은 지니불순도가 가장 작아지는 상황이 나올 수 있다. 위의 예제를 들어 설명하면 정보이득이 가장 큰 성별로 먼저 나누어 결과를 냈지만 성별보다 정보이득은 작지만 나이로 먼저 나눈다면 더 좋은 분류결과를 냈을수도 있다는것이다.(전역최적해) 다시말해, 성별변수의 변수값(남,여)로 나누는 것에서는 최적의 분류(최종적으로는 같은 결과를 냈으나 더 간단한 트리를 만드는 것, 혹은 더 좋은 분류결과를 낸 것)를 만들어 낼 수 있으나 (지역최적값) 전체적으로는 최적화된 답(나이로 먼저 나누었을때)를 놓칠 수 있다는 것이다. 이로인해 몇몇 단계로 분류가 가능한 여러 변수를 포함하는 데이터에서 많은 단계를 가지는 변수쪽으로 정보 획득량이 편향되는 문제도 생긴다.

2. 과다적합/과소적합 문제가 항상 도사리고 있다. 모든 예제가 같은 범주이거나 예제 간 구별할 속성이 남아있지 않을때 까지 나누기 때문에 이렇다. 

3. 결정트리는 한노드에 한개의 변수만들 선택해 분류하기 때문에 데이터의 특성이 특정 변수에 수직/수평적으로 구분되지 못할때 분류율이 떨어지고 복잡해지는 문제가 있다. 크게 이렇게 3가지의 문제가 있다. 

앞의 2가지 탐욕알고리즘의 문제와 과적합의 문제는 조건부 추론 나무나 앙상블 학습법의 하나인 랜덤포레스트나 가지치기로 해결이 가능하다. 

가지치기는 크게 사전 가지치기와 사후 가지치기가 있는데 사전 가지치기는 결정이 일정수에 도달하거나 결정 트리가 적은 수의 예제를 포함하면 성장을 멈추게 하는 것인데 트리에 필요없는 작업을 피할 수 있어 자원을 아낄 수 있으나 좀 더 큰 중요한 패턴을 잃을 수도 있다는 점이 단점이다. 이에 대한 대안적 방안으로 사후 가지치기가 나왔는데 트리를 과적합시켜 성장시킨후 분류 오차를 가진 노드와 가지를 제거한다. 일부 경우에 전체 가지는 좀 더 단 순한 결정으로 교체되거나 옮겨지는데 이런 변경과정을 부분트리 생성과 부분 트리 대체라고 한다. 

다음 포스팅에서는 랜덤포레스트에 대해서 설명하겠다.