[Data Science] Decision Tree - Overfitting

The Concept of Overfitting

반응형

Overfitting and Underfitting

Overfitting (과적합, 과대적합)

과적합은 모델이 학습 데이터에 대해 너무 잘 학습되어 기본 패턴 대신 데이터의 노이즈에 맞추기 시작할 때 발생한다.

학습 데이터에 지나치게 맞추면(overfit) 이후 새로운 데이터(new, unseen data)에 대하여 일반화를 하지 못할 수 있다.

 

Underfitting (과소적합)

과소 적합은 모델이 너무 단순하여 데이터의 기본 패턴을 포착할 수 없을 때 발생한다. 이는 모델이 학습 데이터와 테스트 데이터 모두에서 제대로 작동하지 않는다는 것을 의미한다.

즉, 모델이 학습 데이터에서 보이지 않는 새로운 데이터(new, unseen data)를 정확하게 예측할 수 있을 만큼 충분히 학습하지 못했다는 뜻입니다.

How to detect overfitting?

Overfitting in Decision Tree

Decision tree는 알고리즘 태생이 overfitting에 취약한 구조를 갖는다. 따라서 overfitting을 피하기 위한 여러 방법을 이용한다. 대표적으로 prunning(pre-pruning, post-pruning)이 있다.

 

Pre-Pruning (Early stopping)

tree가 모든 training data에 완벽히 학습(perfectly fit)하기 전에 tree의 성장을 멈추는 것이다.

어떤 지표(gain 등)가 threshold보다 적으면 expanding leaf node를 중단

• maximum depth: tree의 최대 깊이에 도달하면 tree 확장을 멈춘다.
• minimum number of samples at a node: 노드가 split하기 위한 최소 sample 개수. sample수가 적으면 node는 더이상 split하지 않고 그대로 leaf node가 된다.
• minimum impurity decrease: entropy, information gain과 같은 impurity가 (특정 threshold보다) 나아지지 않으면 노드를 분할하지 않고 leaf node가 된다.

 

이런 pre-pruning 방법은 tree의 구조가 지나치게 복잡해지는 것을 방지한다. (avoid overly complex subtrees)

 

그러나 적절한 threshold를 고르는 것은 어려운 문제이다.

threshold가 너무 높으면 underfitting의 가능성이 높고, threshold가 너무 낮으면 overfitting의 가능성이 생긴다.

Post-Pruning

post-pruning은 tree를 일단 최대한 크게 만들고(fully growth) validation set과 비교하여 정확도가 향상되지 않는 branch를 제거하여 일반화 성능을 향상시키는 방법이다. (bottom-up fashion)

 

(1) tree를 최대한으로 학습한다.

(2) tree의 맨 아래에서 시작하여 subtree를 leaf node로 바꾼다. (해당 노드에서는 majority class로 분류한다) 

(3) 더이상 향상되지 않으면 pruning을 중단한다.

 

Post-pruning은 일반적으로 pre-pruning보다 좋은 성능을 갖는다. 

그러나 pre-pruning보다 연산량은 많다. (computationally expensive than pre-pruning)

 

아래 다양한 post-pruning algorithm이다.

• Reduced-Error
• Error-Complexity
• Pessimistic Error: C4.5 알고리즘
• Minimum Description Length (MDL)
• Minimum Error
• Critical Value

 

그러나 best pruning algorithm은 없으므로 데이터셋에 따라 적당히 선택하면 된다.