가지치기

 가지치기(Pruning)은 의사결정 나무 알고리즘에서 과적합(Overfitting)에 대응하기 위한 대표적 수단입니다. 실제 의사결정 나무 알고리즘을 적용할 때, 나무의 깊이는 얼마나 나아갈지, 최하위 노드의 개수는 몇 개로 할지 등의 하이퍼 파라미터 등을 선택하는데, 어느 정도가 좋은 값인지 저희는 전혀 알 수 없습니다. 다만 미쳤다고 이걸 할 수 있는 최대치로 잡아버리면, 당연히 나무의 가지가 미친듯이 세부적으로 생겨날테고, 이건 학습데이터에 정말 꽉 맞게되는, 과적합이 발생할게 분명하겠지요. 이를 해결하기위해서는 가지들을 좀 잘라서, 모델을 좀 느슨하게 만들 필요가 있습니다. 이렇게하면, 모델의 일반성도 높아질테고, 모델의 무게도 가벼워진다는 장점이 있겠지요. 

 그렇게 어떻게 가지치기를 할 건지 생각을 해보면, 자연스럽게 2가지 방법을 생각할 수 있습니다. 가지를 뻗어나갈 때 부터 다듬기 시작하는 사전 가지치기(Pre-pruning), 나무 한 그루 다 만들고 나서, 하나하나 잘라나가는 사후 가지치기(Post-pruning)이 있겠죠. 그리고 공통적으로, 그럼 무슨 기준으로 가지를 칠거냐-하는 것에 대해서는 굉장히 단순하게, 훈련셋과 검증셋을 나눠서, 훈련셋으로 나무를 만들고, 검증셋에 대한 성능이 좋은 가지만 남겨두면 됩니다. 

 사전 가지치기의 경우에는 자연스럽게 탐욕적(Greedy) 알고리즘이 되어버립니다. 해서 시작할 때부터 당장 도움이 안되는 가지는 잘라버리니, 모델의 과적합 위험을 낮출 뿐아니라, 훈련 시간을 굉장히 단축시켜줍니다. 다만 미래를 보지는 못하기 때문에, 최고 성능이 조금 더 낮게 나올 가능성이 생겨버리지요. 사후 가지치기의 경우에는, 주어진 데이터셋으로 가지를 다 뻗어내리고, 거기서 지속적인 검증으로 불필요한 가지를 잘라버리니, 자연스럽게 비용이 커집니다. 반대로 일반화 성능은 사전 가지치기보다 높겠지요.