2021.10.6 TIL : [ML] 지도 학습 - Decision Tree (의사결정 트리)

만약 다음과 같은 데이터가 있다고 할 때, 분류를 위해서는 어떤 선을 그어야 할까?

SVM이나 linear regression, Naive Bayes 등을 이용하면 하나의 선을 그을 수도 있겠지만, DT에서는 x축 혹은 y축과 평행한 직선부터 그려서 나눈다. 그럼 다음 선들 중에 어떤 선을 처음으로 그려야 가장 효율적으로 사과와 배를 구분할 수 있을까?

 

height를 기준으로 선을 그으면 최소 2개의 오류가 발생한다. 반면에 width를 기준으로 그으면 최소 오류가 하나이다. 이 때 주의해야 할 점은 사과와 배를 구분하는 기준선은 train data 위에 그을 수 없다는 점이다. train data들은 이미 분류가 된 데이터들인데, 이 위에 선을 그으면 선에 위치한 데이터들을 분류할 수 없기 때문이다. 종합적으로 보면 width가 최소 오류가 더 적기 때문에 width를 기준으로 나누면 된다.

 

위 사진만 봐도 우리는 왼쪽보다 오른쪽이 잘 분류했다는 점을 알 수 있다. 그렇지만 항상 머신러닝이나 통계학에서는 어째서 더 나은 지 그 성능을 비교하는 기준이 필요하다. 이 때 등장하는 것이 '지니 계수(gini index)'이다. 

 

지니 계수 (gini index)

지니계수를 구하는 방법은 아래와 같다. pi는 전체에서 i번째 범주가 차지하는 비중을 의미한다. 

예를 들어 다음 산점도 전체를 하나의 영역으로 봤을 때 지니 계수를 구해보자.

이 때 P1, 즉 사과의 비중은 6/12 = 1/2 이고, P2인 배의 비중 역시도 6/12 = 1/2 이다. 따라서 배와 사과를 따로 분류하지 않았을 때의 지니 인덱스는 1 - {(1/2)^2 + (1/2)^2} = 1 - (1/4 + 1/4) = 1/2 이다. (원래 0.5라는 지니 계수는 최악의 지니 계수이다.)

 

영역을 나누게 되었을 때 전체 산점도 분류의 지니 인덱스는 (해당 영역의 지니 인덱스) x (전체에서 해당 영역이 포함하는 데이터의 비중)을 영역마다 구해 합한 것이 된다. 

따라서 위의 그림에서 전체 영역의 지니 계수를 구하면 2/12 x 0 + 10/12 x 48/100 = 0.4 가 된다. 오른쪽에 있던 영역 분류의 지니 계수를 계산해보자.

전체 영역의 지니 계수를 구해보면 7/12 x 0.25 + 0 ≒ 0.143 이다. 지니 인덱스가 0이라는 것은 오분류된 것이 없다는 뜻으로 가장 잘 분류된 형태라는 것이다. 지니 계수는 낮을수록 분류의 정확도가 높은 것이기 때문에 첫 번째 분류보다 두 번째 분류가 더 잘 나누었다는 것을 기준에 따라 알 수 있다.

 

이렇게 영역을 구분짓는 행위가 두 범주를 나눌 수 있는 정보를 주었다고 하여 '정보 획득(information gain)'이라고 하는데, 각각의 정보 획득은 다음과 같다. 

• information gain(upper) = 0.5 - 0.4 = 0.1
• information gain(lower) = 0.5 - 0.143 = 0.357

즉, 아래의 그림이 더 많은 정보를 준다고 할 수 있다. 이렇게 feature 중 하나를 선택하여 이를 기준으로 나누는 작업을 계속하다 보면 트리의 형태는 다음과 같은 모습을 보인다.

결정 트리는 한 번에 하나의 변수를 사용해 단계를 거쳐가면서 예측이 가능한 규칙들의 집합을 생성한다. 따라서 위의 그림들처럼 사람들이 보기에 이해하기 쉬운 결과를 얻을 수 있다. 

 

타 분류들이 그렇듯이 결정 트리도 분류의 정확도만을 좇아가면 과정이 복잡해지고 과적합(overfitting)되는 문제가 발생한다. 

위의 예처럼 하나의 인스턴스를 잘 분류하기 위해서 세 번이나 더 depth를 가지게 되면, 불필요한 과적합이라고 볼 수 있다. 이렇게 순도(purity)가 100% 되도록 그리는 트리를 full tree라고 하며, 대부분의 경우에 사용하지 않는다. 따라서 적당한 선의 depth를 선택하는 가지치기가 필요하다.

가지치기 (Pruning)

일정 정도 이상의 decision tree를 나누다보면, 정확도가 크게 높아지지 않는 범위가 생긴다. 물론 이런 범위에서도 계속 결정 트리를 뻗어 내려 간다면 훈련 데이터에 대해서 정확도가 1에 가깝게 될 수 있지만, DT를 선택하는 이유 중에 하나가 간단하다는 점이기 때문에 보통은 depth를 설정해 둔다. 따라서 decision tree 기법은 정확성을 요구하는 금융 데이터나 의료 데이터에서는 적합하지 않을 수 있다. 

 

※ 앙상블 기법 : 하나의 알고리즘을 확장시켜 만드는 기법. 예를 들면 Decision tree를 매우 많이 만들어서 forest가 되도록 하고, 이 중에서 최적의 트리를 선택하는 random forest 알고리즘을 파생시키는 것이 앙상블 기법이다. 

 

((추후 깃헙 코드 업로드))