[IT기술] 결정트리(Decision Tree)란?

오늘은 IT 컴퓨터 수학 알고리즘에서 가장 기초적인 분류 방식이며 가장 많이 사용하는 방식인 결정트리 알고리즘에 대해 알아보도록 하겠습니다. 결정 트리 학습법(decision tree learning)은 어떤 항목에 대한 관측값과 목표값을 연결시켜주는 예측 모델로써 결정 트리를 사용합니다. 이는 통계학과 데이터 마이닝, 기계 학습에서 사용하는 예측 모델링 방법 중 하나입니다. 트리 모델 중 목표 변수가 유한한 수의 값을 가지는 것을 분류 트리라 합니다. 이 트리 구조에서 잎(리프 노드)은 클래스 라벨을 나타내고 가지는 클래스 라벨과 관련있는 특징들의 논리곱을 나타냅니다. 결정 트리 중 목표 변수가 연속하는 값, 일반적으로 실수를 가지는 것은 회귀 트리라 합니다.

1. 결정트리란?

결정 트리는 주어진 데이터를 반복 적으로 분할하고, 나무(Tree) 구조로 표현하여 어떤 범주에 있는 의사인지 결정을 내리는 방법입니다. 일반적으로 스무 고개 게임을 해본 사람이라면 결정 트리분석의 분류 과정을 이해하기가 쉬울 것이라 생각합니다. 이 게임은 우선 한 사람이 다른 사람들이 알고 있는 특정한 장소나 물건, 사람 등을 마음속에서 결정합니다. 그러나 그 사람은 그것에 대한 힌트는 주지 않습니다. 다만 다른 사람들의 질문에 대하여 YES와 NO로 대답을 할 뿐입니다. 잘 하는 사람은 20개의 질문을 모두 사용하지 않고 서도 답을 맞추게 됩니다. 결정 트리도 이러한 질문의 과정이라고 볼 수 있습니다. 게임에서 첫 번째 질문이 다음에 가야 할 경로(해야 할 질문)를 결정하게 됩니다. 질문이 잘 선택되면, 짧은 시간에 들어온 들어온 레코드를 잘 분류 시킬 수 있게 됩니다.

2. 결정트리 예시에 대해 알아보자.

결정 트리 분석은 위쪽에 뿌리 노드를 그리고 밑으로 가지를 치면서 끝 마디를 형성시킵니다. 레코드가 뿌리 마디에 놓여지고 그것이 다음의 어떤 자식 마디에 속해지는 지가 결정됩니다 .처음에 어떤 분류 기준을 선택할 것 인가를 결정하는 것은 여러 알고리즘이 있다. 들어온 레코드가 끝 마디에 갈 때까지 이러한 과정이 반복됩니다. 

"테니스 치기에 적합한 토요일 아침" 에 대해 분류하는 다음과 같은 Decision Tree가 있을 수 있습니다.

instance를 분류하는 방법은 tree의 root node에서 시작하여 노드에서 지정하는 attribute의 값을 테스트 하여 그 값에 해당하는 가지를 따라 내려가면 됩니다.

예로, instance <Outlook = Sunny, Temperature = Hot, Humidity = High, Wind = Strong>은 위의 Decision Tree에서 가장 왼쪽의 가지를 따라 내려가며 결과는 "No"가 됨을 알 수 있습니다.

3. 결정 트리 표현 방법을 알아보자.

일반적으로 Decision Tree는 attribute 값들의 conjunction의 disjunction을 표현합니다.

leaf node까지의 하나의 path가 하나의 conjunction을 나타내며 이 path들이 모인 tree 자체는 disjunction을 표현합니다.

즉, 위의 Decision Tree는 다음과 같은 conjunction들의 disjunction으로 표현할 수 있습니다.

(Outlook = Sunny ∧ Humidity = Normal) ∨ (Outlook = Overcast) 

∨ (Outlook = Rain ∧ Wind = Weak)

4. 결정트리 문제점은 무엇일까?

어떤 attribute값을 갖지 않는 training example이 포함될 수 있는 문제가 있으면 어떻게 해야 할까? 이런 경우 해당 attribute에 대해 값을 가지고 있는 training examples을 참조하여 attribute 값을 할당하는 것이 일반적이며 다음과 같은 방법들이 있습니다.(현재 이 attribute A에 대해 테스트 하기 위해 노드 n에서 Gain(S, A)를 구하려하며 이 attribute 값이 비어 있는 training example을 x라고 가정한다.) 이 노드 n에 있는 training examples이 가지고 있는 attribute A의 값을 x의 attribute A의 값으로 할당합니다.

- instance가 위에서 처럼 attribute-value 쌍들로 표현이 되는 문제 발생됩니다.

- target function이 discrete한 값을 output으로 갖는 문제 발생됩니다.

- disjunctive한 표현이 필요할 수 있는 문제 발생됩니다.

- error를 가질 수도 있는 문제 발생됩니다.

5. 결정 트리 학습 알고리즘의 종류를 알아보자.

데이터 마이닝에서 사용되는 결정 트리 분석법은 크게 두 종류가 있습니다. 먼저 분류 트리 분석은 예측된 결과로 입력 데이터가 분류되는 클래스를 출력합니다. 다음으로 회귀 트리 분석은 예측된 결과로 특정 의미를 지니는 실수 값을 출력합니다. (예: 주택의 가격, 환자의 입원 기간) 회귀 및 분석 트리(Classification And Regression Tree, CART)는 두 트리를 아울러 일컫는 용어로, 레오 브레이만에 의해 처음 사용되었습니다. 회귀 트리와 분류 트리는 일정 부분 유사하지만, 입력 자료를 나누는 과정 등에서 차이점이 있습니다. 랜덤 포레스트 분류기에서는 분류 속도를 향상시키기 위해서 결정 트리들을 사용합니다. 부스트 트리는 회귀 분석과 분류 문제에 사용될 수 있습니다. 회전 포레스트는 모든 결정 트리가 먼저 입력 트리 중 임의의 부분 집합에 대한 주성분 분석 (PCA)을 적용하여 훈련됩니다. 의사 결정 트리 학습은 클래스-라벨 훈련 쌍으로부터의 결정 트리에 의해 구성된다. 결정 트리의 각각의 노드는 서로 다른 특성을 가집니다. 각각의 내부노드(또는 비 리프노드)는 속성에 대한 테스트를 나타내고, 각각의 가지는 테스트의 결과를 나타냅니다. 그리고 각 리프노드(또는 터미널 노드)는 클래스의 라벨을 나타냅니다. 마지막으로 트리의 최상위 노드는 루트 노드입니다.

결정 트리 분석을 수행하는 알고리즘들은 ID3, C4.5, C5.0, CART 등 여러 가지가 있습니다. 그 중 ID3 알고리즘은 대표적인 의사결정트리 기반 분류 알고리즘입니다. ID3 알고리즘은 1970년대 후반 J. Ross Quinlan 박사에 의해 제안되었습니다. 그 이후에 개발된 다양한 의사결정트리 기반의 분류 알고리즘(C4.5, CART, CHAID 등)들도 기본적으로 ID3 알고리즘의 아이디어에 기초하고 있습니다.