의사결정 트리(decision tree)

의사결정 트리는 데이터 분류 및 회귀에 사용되는 지도학습 알고리즘이다. 간단하게 의사결정 트리가 무엇인지 비유하자면 스무고개 놀이와 비슷하다고 말할 수 있다. 즉, 여러 질문을 하여 답을 도출해내는 방법이라고도 할 수 있다.

다음과 같은 데이터를 예시로 설명을 이어가겠다.

 

이름	군대를 다녀왔는가	긴 생머리인가	성별
김덕수	네	아니요	남자
이쁜이	아니요	아니요	여자
박장군	네	아니요	남자
최빛나	아니요	네	여자
최강민	네	아니요	남자
지화자	아니요	아니요	여자

 

위 데이터를 바탕으로 각 사람이 남자인지 여자인지를 구별하는 질문을 만든다고 해보자. 먼저 군대를 다녀왔는지를 먼저 물어보면 한 번에 남자와 여자가 분류된다. 하지만 긴 생머리인지 먼저 물어보게되면 정확하게 남자와 여자를 구분할 수 없으므로 이후 군대를 다녀왔는지를 한번 더 물어봐야한다.

 

여기서 군대를 다녀왔는지를 물어보는 것이 영향력이 가장 큰 질문이고 긴 생머리인지 물어보는 질문은 영향력이 더 작은 질문이다. 영향력이 크다는 것의 의미는 답을 도출해내는데 얼마나 큰 도움을 주었는가를 말한다. 그리고 영향력이 클수록 상위노드(우선순위가 높은 질문), 영향력이 작을수록 하위노드(우선순위가 작은 질문)로 선택하는 것이 핵심일고 할 수 있다.

 

의사결정 트리 알고리즘과 정보 엔트로피의 관계

질문을 한 던질 때마다 약간씩의 정보를 획득하고 이 정보로 인해 정답에 대한 불확실성이 줄어든다. 이 불확실성을 수치적으로 표현한 값을 "엔트로피"라고 한다. 또한 불확실성이 줄어 든 정보를 "정보 이득"이라고 한다.

정보 이득에 관한 식은 다음과 같다.

# 질문 후의 정보 이득 = 질문 전의 엔트로피 - 질문 후의 엔트로피
Gain(T, X) = Entropy(T) - Entropy(T, X)

 

정보 엔트로피

엔트로피를 구하는 공식은 다음과 같다.

앞서 살펴본 데이터를 사용하여 정보 엔트로피를 구해보겠다.

엔트로피 = -p(남자) * log(p(남자)) - p(여자)*log(p(여자))

의사 결정 트리의 최초 엔트로피는 1, 불확실성이 100%라는 말이랑 같다. 계산 방법은 다음과 같다.

-(3/6) * log(3/6) - (3/6) * log(3/6) = 1

 

하나의 특징에 대한 엔트로피

각 특징에 대한 엔트로피를 계산하여 가장 영향력이 큰 특징이 무엇인지 알아보겠다.
공식은 다음과 같다.

- X : 선택된 특징

- c : 선택된 특징에 의해 생성되는 하위 노드

- P(c) : 선택된 특징에 의해 생성된 하위 노드에 데이터가 속할 확률

- E(c) : 선택된 특징에 의해 생성된 하위 노드의 엔트로피

 

우선 군대를 다녀왔는지에 대한 특징으로 계산하면 다음과 같다.

3/6 * E[3,0] + 3/6 * E[0,3]
3/6 * (-(3/3)*log(3/3) - (0/3)*log(0/3)) + 3/6 * (-(0/3)*log0 - (3/3)*log(3/3)) = 0

E[3,0]에서 "[3,0]"은 남자가 3명, 여자가 0명이 속한다는 뜻이다. 또한 [0,3]이라고 하면 남자가 0명, 여자가 3명이라는 뜻이 되겠다. 그리고 E[3,0], E[0,3]는 각각 군대를 다녀왔을 때와 안다녀왔을 때로 구분하여 계산하는 식이다.

다음으로 긴생머리 특징으로 계산하면 다음과 같다.

1/6 * E[0,1] + 5/6 * E[3,2] = 0
1/6 * (-(0/1)*log(0/1) - (1/1)*log(1/1)) + 5/6 * (-(3/5)*log(3/5) - (2/5)*log(2/5)) = 0.966

따라서 "군대" 특징으로 정보 이득은 1, "긴생머리" 특징올 정보 이득은 0.034이므로 정보 이득이 높은 "군대"를 상위 노드로 선택할 경우 효율적인 의사결정 트리를 구성할 수 있게 된다.

 

지니 계수

우선 지니 계수의 특징을 한 번 살펴보겠다.

1. 특징이 항상 이진 분류로 나뉠 때 사용됨
2. 지니 계수가 높을수록 순도가 높음

위 특징을 보면 지니 계수는 이진 분류할 때 사용된다는 것을 알 수 있지만 순도가 높다는 것이 무슨 말인지 모를 것이다. 순도가 높다는 말은 한 그룸에 모여있는 데이터들의 속성들이 얼마나 많이 일치하느냐는 뜻이다. 또 데이터들의 속성들이 얼마나 많이 일치하느냐는 말은 예를 들어서 군대를 다녀왔느냐 안 다녀왔느냐로 남자와 여자를 구분했을 때 얼마나 일치하느냐는 뜻이기도 하다. 간단하게 말하면 해당 특징으로 얼마나 구분이 잘되느냐를 순도가 높다라고 표현했다고 생각하면 된다.

"군대"라는 특징으로 지니 계수를 구하면 다음과 같다.

군대를 다녀옴 : (0/3)^2 + (3/3)^2 = 1
군대를 다녀오지 않음 : (3/3)^2 + (0/3)^2 = 1
군대 특징의 지니 계수 : 3/6 * 1 + 3/6 * 1 = 1

다음으로 "긴 생머리"를 특징으로 계산하면 다음과 같다.

긴생머리 : (0/1)^2 + (1/1)^2 = 1
긴생머리 아님 : (3/5)^2 + (2/5)^2 = 13/25
긴생머리 특징의 지니 계수 : 1/6 * 1 + 5/6 * 13/25 = 0.6

지니 계수도 정보 이득 값과 마찬가지로 값이 높을수록 의사결정 트리의 상위 노드로 결정한다.

 

의사결정 트리의 장단점

• 장점

1. 수학적인 지식이 없어도 결과를 해석하고 이해하기 쉽다.
2. 수치 데이터 및 범주 데이터에 모두 사용 가능하다.

• 단점

1. 과대적합의 위험이 높다. 질문을 많이 할게될수록 과하게 학습된다는 말이다.