[인공지능 기초] 결정 트리(Decision Tree)

▶ 결정 트리(Decision Tree)란?

결정 트리는 분류(classification)와 회귀(regression)에 모두 사용 가능한 지도학습 모델 중 하나입니다. 결정 트리의 기본적인 작동 방식은 예/아니오 질문을 이어가며 학습하는 것입니다. 아래 그림은 결정트리의 작동 방식을 도식화한 것입니다.

위 그림에서 알 수 있듯이 한번의 분기마다 변수 영역을 두개로 구분합니다. 결정 트리에서 질문이나 정답이 담긴 네모상자를 노드라고 합니다. 가장 첫 질문을 루트 노드(root node), 정답이 담긴 마지막 노드를 터미널 노드(terminal node) 또는 리프 노드(leaf node)라고 합니다. 터미널 노드들의 개수를 통해 전체 데이터가 몇개의 부분집합으로 나눠지는 알 수 있고 터미널 노드 간에는 교집합이 존재하지 않습니다.

​

● 작동 과정​

먼저 위와 같이 데이터를 가장 잘 구분 할 수 있는 질문을 기준으로 나눕니다.

​

그 다음 나뉜 각 범주에서 또 다시 데이터를 가장 잘 구분 할 수 있는 질문을 기준으로 나눕니다.

이를 지나치게 많이하면 오버피팅이 발생하기 때문에 가지치기(pruning)라는 기법을 사용하기도 합니다.

​

● 가지치기(pruning)

오버피팅을 해결하기 위한 방법으로 가지치기라는 기법이 있습니다. 트리에 가지가 너무 많다면 오버피팅에 해당됩니다. 이는 트리의 최대 깊이나 터미널 노드의 최대 개수 또는 한 노드가 분할하기 위한 최소 데이터수를 제한 하는 것을 말합니다. 최소 데이터 수를 제한하는 것은 한 노드에 들어갈 수 있는 최소 데이터 수를 정해주는 것을 말합니다. 이렇게 가지치기를 하는데는 아래와 같은 비용함수가 필요합니다.

$CC\left(T\right)\ =\ Err\left(T\right)\ +\ \alpha \ \times L\left(T\right)$CC(T) = Err(T) + α ×L(T)​

- CC(T) : 결정 트리의 비용 복잡도이며 오류가 적으면서 터미널 노드의 수가 적은 단순한 모델일수록 작은 값을 가집니다.

- Err(T) : 검증데이터에 대한 오분류율을 나타냅니다.

- L(T) : 터미널 노드의 수이며 구조의 복잡도를 의미합니다.

- a : Err(T)와 L(T)를 결합하는 가중치입니다. 사용자에 의해 부여되며 보통 0.01 - 0.1 사이의 값을 사용합니다.

​

​

● 결정 트리가 분류에 사용될 때

새로운 데이터가 특정 터미널 노드에 속한다는 정보를 확한 후 해당 터미널 노드에서 가장 빈도수가 높은 범주에 새로운 데이터를 분류하게 됩니다.

​

​

● 결정 트리가 회귀에 사용될 때

해당 터미널 노드의 종속변수 y의 평균을 예측값으로 반환하게 됩니다. 이때 예측값의 종류는 터미널 노드의 개수와 일치합니다.

​

​

▶불순도(impurity)와 불확실성(uncertainty)

앞서 결정트리는 한번 분기시 변수 영역을 두개로 구분하는 모델이라고 설명하였습니다. 이때 분류하는 기준은 순도가 증가하고 불순도(impurity)나 불확실성(uncertainty)이 감소하는 방향입니다. 불순도는 해당 범주안에 서로 다른 데이터가 얼마나 섞여 있는지를 뜻합니다. 순도가 증가하고, 불확실성이 감소하는 것을 정보획득(information gain)이라고 합니다.

위 그림을 보면 위쪽은 파란점이 하나뿐이므로 불순도가 낮습니다. 반면 아래쪽은 위쪽보다 불순도가 높다고 할 수 있습니다. 한 범주에 하나의 데이터만 있다면 불순도가 최소이고 , 서로 다른 두 데이터가 5:5의 비율로 있다면 불순도가 최대입니다. 결정 트리는 이 불순도를 최소화 하는 방향으로 학습합니다. 불순도를 나타내는 지표에는 엔트로피(entropy)와 지니계수(gini index)가 있습니다.

​

● 엔트로피(Entropy)

엔트로피가 높다는 것은 불순도가 높다는 의미입니다. m개의 데이터가 속하는 영역에 대한 엔트로피는 아래와 같은 식으로 정의됩니다.

이 식을 바탕으로 위 그림의 네모 박스 전체의 엔트로피를 구해보겠습니다. 전체 16개이므로 m=16이고 빨간 점은 10개, 파란점은 6개입니다.

이 후, 빨간 점선으로 영역을 나눴다면 두 개이상의 영역에 대한 엔트로피 계산은 아래와 같습니다. 새로 추가된 변수 R은 분할 전 데이터들 중에서 분할 후 영역i에 속하는 데이터의 비율을 의미합니다.

분할 전과 비교하여 엔트로피가 감소한 것을 확인할 수 있습니다. 또한 엔트로피가 액 0.95에서 0.75로 감소하였기 때문에 0.2만큼 정보 획득이 일어났다고 할 수 있습니다.

​

​

● 지니계수(gini index)

지니계수를 계산하는 공식은 아래와 같습니다.

​

▶ 결정 트리 프로세스(예시)- 출처

아래와 같은 데이터가 있다고 해보겠습니다.

1. 먼저 루트 노드의 불순도를 계산합니다.

2. 나머지 속성에 대해 분할 후 자식 노드의 불순도를 계산해줍니다. 순서대로 날씨, 온도, 습도, 바람입니다.

3. 각 속성에 대한 information gain을 계산한 후 information gain이 최대가 되는 분기 조건을 찾아 분기합니다.

4. 모든 터미널 노드의 불순도가 0이 될때까지 2-3을 반복하여 수행합니다.

5. 최종 결과

​

​

▶ 결정 트리의 장단점

- 장점 : 계산 복잡성대비 높은 예측 성능을 낼 수 있습니다. 또한 데이터를 전처리하지 않아도 되며 수치형과 범주형 데이터를 모두 다룰 수 있습니다.

- 단점 : 오버피팅이 발생할 가능성이 높습니다. 한번에 하나의 변수만 고려하기 때문에 변수들 간에 상호작용이 있는 경우는 파악이 어렵습니다. 두 변수가 비슷한 수준의 정보력을 갖는다고 했을 때 약간의 차이에 의해 다른 변수가 선택되어 트리 구성이 크게 달라질 수 있습니다.

=> 이러한 문제점을 해결한 것이 바로 랜덤포레스트(RandomForest)입니다. 같은 데이터에 대해 결정트리를 여러 개 만들어 그 결과를 종합해 예측 성능을 높히는 방법인데 다음 게시물에서 다루도록 하겠습니다.