의사결정 나무(Decision Tree) 구현 시 과적합(overfitting, 오버피팅) 문제를 해결하기 위한 가지치기(pruning) 방법에 대해 알아보자.
■ 과적합(Overfitting)이란?
과적합 문제는 훈련(training) 데이터에서는 정확하나 테스트 데이터에서는 성과가 나쁜 현상을 일컫는다. 훈련 데이터가 적거나 노이즈가 있을 때, 또는 알고리즘 자체가 나쁠 때 발생할 수 있다. 의사결정 나무에서는 나무가 너무 가지가 많거나 나무의 크기가 클 때(이를 fully grown이라고 부르기도 한다.) 과적합 문제가 발생한다. 예시로 살펴보자.
사람의 신용도를 분류하기 위해 왼쪽과 같은 훈련 데이터가 있다고 하자. 지난 글에서 살펴봤듯이 같은 훈련 데이터를 이용해서 다양한 의사결정 나무를 그릴 수 있다. 우측 상단은 부채(Debt)를 기준으로 의사결정 나무를 그리고, 우측 하단은 이름을 기준으로 의사결정 나무를 그렸다.
두 개의 의사결정 나무 모두 신용도(Rating)를 잘 분류했다. 그럼에도 불구하고, 대부분 부채를 기준으로 그린 의사결정 나무를 더 선호할 것이다. 이 때 등장하는 개념이 바로 오캄의 면도날(Occam’s Razor)이다.
■ 오캄의 면도날(Occam’s Razor)
오캄의 면도날이 말하는 것은 간단하다. 어떤 현상을 설명하는 두 가지 다른 가설이 있을 때 더 간단한 것을 골라라!
예를 들어 어떤 길이 젖어 있다는 현상을 설명하려고 한다고 하자. 한 가지 가설은 ‘밤새 비가 내렸다’ 이고, 다른 한가지 가설은 ‘새벽에 배송하는 우유 트럭이 사고가 났고 그 때 우유가 흘렀다. 차는 견인 되었고, 우유팩은 치워졌으나 쏟아진 우유는 여전히 길에 남아있다’. 이 때 우리가 선택해야할 가설은 더 간단한- 첫 번째 밤새 비가 내렸다는 가설이다.
다시 위의 의사결정 나무의 예시를 살펴보자. 부채 기준이 훈련 데이터 상에서 더 간단한 가설이므로 첫 번째 의사결정 나무가 두 번째 의사결정 나무보다 좋다.
의사결정 나무를 그릴 때 과적합을 피하기 위한 방법으로는 ‘사전 가지치기’와 ‘사후 가지치기’가 있다.
■ 사전 가지치기(Pre-Pruning, Early Stopping Rule)
사전 가지치기는 나무가 다 자라기 전에 알고리즘을 멈추는 방법이다. 예를 들어 모든 인스턴스가 하나의 클래스에 속하거나 속성값이 같아지면 멈춘다. 또는 연구자가 임의로 설정한 숫자보다 인스턴스가 적어지면 나무 그리기를 멈춘다거나 역시 연구자가 임의로 불순도 정도를 설정하여 해당 지니 계수/엔트로피에 도달하면 나무 그리기를 멈춘다.
■ 사후 가지치기(Post-Pruning)
사후 가지치기는 일단 의사결정 나무를 끝까지 그린 후 밑에서부터 가지를 쳐나가는 방법이다. 이 때 검증 데이터(validation data)를 사용하거나 일반화 오차(generalization error)를 예측한다. 만약 일반화 오차가 가지를 친 후에 더 좋아진다면 서브트리를 잎노드로 대체한다.
그렇다면 일반화 오차란 무엇인가? 일반화 오차는 아직 관측되지 않은 데이터에서 발생하는 오차를 말한다. 다른 개념으로 훈련 오차(training error)가 있는데, 훈련 데이터에서 발생하는 오차를 일컫는다. 훈련 오차는 훈련 데이터 상에서 잘못 분류된 건수를 찾아 쉽게 계산 가능하지만 일반화 오차는 추정을 통해서만 구할 수 한다.
일반화 오차를 추정하는 방법은 다음과 같다. 먼저 훈련 오차와 일반화 오차가 동일하다고 가정할 수 있다. 그러나 이는 모델을 너무 낙관하기 때문에 정확도가 떨어질 수 밖에 없다.
두 번째 방법은 훈련 오차에 연구자가 임의로 설정한 페널티값을 더해주는 방법이다.
위의 공식에서 볼 수 있듯이 잎노드의 숫자에 연구자가 정한 페널티를 곱해주어 잎노드가 많을수록 일반화 오차가 더 커지게 페널티를 준다. 예시에서 훈련 오차는 0.1이었는데 잎 노드 50개로 분리 후의 일반화 오차는 0.35로 늘어났다. 즉, 잎 노드 50개로 분리할 경우 오차가 더 커지므로 서브 트리는 모두 잘라내 가지치기를 한다.
마지막 방법은 REP(Reduced Error Pruing)이라고 하는데, 검증 데이터를 이용해 일반화 오차를 추정하는 방식이다. 이 방법은 간단히 계산된다는 장점이 있지만 검증 데이터가 훈련 데이터보다 적을 경우 가지치기가 과하게 될 수 있으니 조심해야 한다.