10. Overfitting

Training Data를 사용해서 Decision Tree를 Top-down 방식으로 학습하는 것을 봤다

학습을 언제 종료하는 것이 좋을까?
노드에 있는 모든 데이터들이 같은 Class를 가질 때까지 분류한다
그러면 학습 데이터에 대해서 100% 분류 정확도를 보이는 Decision Tree가 만들어지게 된다

 

• 위처럼 학습이 되면 주어진 데이터에 대해 100% 정확히 분류하는 Decision Tree가 학습되었다
• 이게 과연 좋은 것일까? 아니다. Overfitting이 된 것 이다

 

Overfitting of Decision Tree Models

---

Decision Tree는 Overfitting이 발생한다는 문제 가 있다

• Overfitting이 된다는 것은 왜 문제일까
  • 너무 많은 Branch가 생기게 되고, Noise나 Outlier와 같은 이상한 데이터들도 모두 반영이 된다는 문제가 있다
  • 그렇기 때문에 새로운 데이터에 대해 정확히 분류하지 못할 수 있다
• 그럼 어떻게?
  • Overfitting이 되기 전에 중단을 해야 한다

 

Tree Pruning

---

나무 가지치기

• Overfitting이 된다는 것은 Decistion Tree에 너무 많은 Branch가 생긴다고 했다
• 그럼 가지치기 를 해주면 Overfitting을 막아줄 것이다
• Overfitting을 방지하는 기법에는 2가지 정도가 있다
  • Pre-pruning: Tree의 생성을 일찍 중단하는 것 이다
    • 특정 임계치 이상으로 분류가 되었다면, 더 이상 Recursive하게 들어가지 않고 Split을 중단한다
    • 적절한 임계치를 결정하는 것이 어렵다
    • Minimum samples split, Maximum tree depth, Minimum gain,,,
    • 이 중에 어떤 것을 Pruning의 기준으로 잡아야 할지 결정하기가 어렵다
  • Post-pruning: 일단 Tree를 생성하고 Branch들을 제거 하는 방법
    • Testset 중에 일부를 Validation set으로 사용해서 Pruning의 성능을 평가하기 위해서 사용한다
    • Validation set에 대해서 Pruning 후의 성능이 더 좋으면 Pruning을 잘한 것이다
    • 이제는 Pruning을 하는 것이 오히려 성능을 저하시킨다고 판단될 때까지 가지치기를 한다

 

Random Forest

---

Overfitting을 피하는 강력한 방법으로 소개되고 있다

• Radom Forest는 Decision Tree의 앙상블(Ensemble) 버전이다
  • 앙상블은 여러 개의 약한 분류기를 생성하고, 각각의 예측을 결합함으로써 단일 분류기보다 신뢰성이 높은 최종 예측 값을 얻어내는 기법
• Forest?
  • Decision Tree를 여러 개 생성하는 것
  • 여러 개의 Decision Tree가 결정한 Decision을 종합(Aggregation)해서 최종 결과로 산정한다

 

• Original Data로부터 랜덤하게 데이터를 하나씩 뽑는다
• 이걸 N번 반복하면, N개의 데이터가 들어있는 Sample이 생성될 것이다
• 이렇게 생성한 샘플을 Bootstrap Sample이라고 한다

 

• 이때 Sub Training Dataset(Bootstrap Sample)은 Original Dataset과 같은 크기를 갖도록 샘플링 해야한다
  • 단, 중복된 데이터가 샘플링되는 것을 허용 한다
• 학습 데이터에 Randomness를 더해주는 방식

 

• 원래는 Decision Tree를 형성할 때, 전체 Feature에 대해서 최적의 Feature를 찾아서 Split을 했다
• 그런데 Tree를 생성하는 과정에도 Randomness를 더해주어서, Overfitting을 방지한다
  • 각 Recursion마다 후보군 Feature를 랜덤하게 뽑는다
  • 랜덤하게 뽑힌 후보군 중에서 최적의 Feature를 찾고, 해당 Feature로 Split을 한다

 

Aggregation

---

각각의 트리가 만들어낸 결정을 어떻게 종합해서 최종적으로 하나의 결정을 내릴 것인가

 

Majority Voting

• 각각의 트리가 만들어낸 결과를 보고, 더 많이 vote된 쪽으로 결정 (다수결)
• 각 모델의 성능은 고려하지 않고, 오직 결과만 보고 판단을 한다
  • 모든 표가 동일한 힘을 가진다

 

Weighted Voting

• 각각의 트리가 만들어낸 결과에, 각 트리의 Training Accuracy를 함께 고려해서 최종 결과를 낸다
• 가중치를 설정하여 최종 Label을 결정
  • Training Accuracy가 높은 모델의 표가 더 큰 힘을 가진다

 

정리

---

• Decision Tree Model
  • Recursive하게 각 단계에서 최적의 Feature를 선택하여 분리하는 그리디한 방식
  • 최적의 Feature를 선택하는 기준은 Information Gain, Gain Ratio, Entropy, Gini Index 등 다양했다
• Overfitting을 방지하기 위한 방법
  • Tree Pruning
  • Random Forest
• Random Forest
  • 500 ~ 10,000개 정도의 Tree를 앙상블하여 레이블을 결정
  • 각각의 Tree는 Bootstrapped sample을 가지고 학습된다
  • 각 Tree를 생성할 때, 랜덤하게 선택한 Feature를 이용해서 Tree를 만든다
  • Sample와 Tree를 생성하는 과정 모두에 무작위성을 더해주어 Overfitting을 방지

 

Reference

---

[ML] RandomForest(랜덤포레스트)