의사결정나무 – 중첩된 결정 규칙의 놀라운 힘

• 데이터 분류를 위해 특징 공간을 반복적으로 분할하는 구조로, 각 단계에서 가장 정보 이득이 큰 분할을 선택함
• 엔트로피(Entropy) 를 이용해 데이터의 순도(purity) 를 측정하고, 이를 기반으로 정보 이득(Information Gain) 을 계산함
• ID3 알고리듬 은 부모 노드와 자식 노드의 엔트로피 차이를 계산해 최적의 분할 지점을 찾으며, 재귀적으로 트리를 확장함
• 엔트로피 대신 Gini 불순도 를 사용할 수도 있으며, 두 방법은 대부분 유사한 결과를 보이지만 계산 효율이 다름
• 과도한 분할은 과적합(overfitting) 과 불안정성 을 초래하므로, 가지치기(pruning) 나 랜덤 포레스트(Random Forest) 로 이를 완화함

의사결정나무의 기본 개념

• 의사결정나무는 데이터를 위에서 아래로 분할하며, 각 단계에서 조건 규칙을 적용해 데이터를 잘 구분되는 영역으로 나눔
  • 각 분할은 데이터의 특정 특징(feature) 과 임계값(cutoff value) 에 따라 결정됨
  • 목표는 분류(classification) 시 클래스가 잘 구분되는 순수한 노드를 만드는 것임

엔트로피(Entropy)의 정의와 성질

• 엔트로피는 정보의 불확실성을 측정하는 지표로, 확률 (p_i) 에 대해 (H = -\sum p_i \log_2(p_i)) 로 정의됨
• 주요 성질
  1. 하나의 사건만 확률 1이고 나머지가 0일 때 (H=0), 즉 불확실성이 없음
  2. 모든 사건의 확률이 동일할 때 엔트로피가 최대가 되어 가장 불순한 상태를 나타냄
  3. 확률이 균등해질수록 엔트로피가 증가함
• 따라서 순수한 노드는 엔트로피가 0이고, 혼합된 노드는 높은 엔트로피 값을 가짐

정보 이득(Information Gain)과 ID3 알고리듬

• 정보 이득은 분할 전후의 엔트로피 차이로 계산되며, 데이터 분할의 효율성을 나타냄
  • 수식: (\Delta IG = H_{\text{parent}} - \frac{1}{N}\sum N_{\text{child}} \cdot H_{\text{child}})
• ID3 알고리듬 단계
  1. 각 특징의 엔트로피 계산
  2. 다양한 분할 기준으로 데이터셋을 나누고 정보 이득 계산
  3. 정보 이득이 최대인 분할을 선택해 결정 노드 생성
  4. 더 이상 분할할 수 없을 때 리프 노드 생성
  5. 모든 하위 집합에 대해 재귀 수행, 단 모든 요소가 동일 클래스일 경우 중단
• 예시로, Diameter ≤ 0.45 조건이 정보 이득 0.574로 최대였기 때문에 첫 번째 분할로 선택됨

Gini 불순도와 대안적 측정

• Gini 불순도(Gini impurity) 는 엔트로피의 대안으로, 정보의 불순도를 측정하는 또 다른 방식임
  • 로그 계산이 없어 계산 속도가 빠름
  • 불균형 데이터셋에서는 엔트로피가 더 신중한 선택이 될 수 있음
• 두 방법 모두 일반적으로 유사한 결과를 산출함

과적합과 불안정성 문제

• ID3 알고리듬은 엔트로피를 최소화하기 위해 계속 분할을 수행하므로, 트리가 지나치게 깊어질 수 있음
  • 이는 과적합(overfitting) 을 유발해 새로운 데이터에 대한 일반화 성능이 저하됨
• 또한 데이터의 작은 변화에도 트리 구조가 크게 달라지는 불안정성(high variance) 문제가 존재함
  • 예: 훈련 데이터의 5%에 작은 가우시안 노이즈를 추가해도 완전히 다른 트리가 생성됨
• 해결책으로 가지치기(pruning) 를 통해 트리의 깊이, 리프 수, 최소 샘플 수 등을 제한할 수 있음

랜덤 포레스트로의 확장

• 단일 의사결정나무의 불안정성을 완화하기 위해, 여러 개의 트리를 서로 다른 데이터 샘플로 학습시켜 예측을 결합하는 방식이 사용됨
  • 이 접근법이 랜덤 포레스트(Random Forest) 로, 높은 안정성과 일반화 성능을 제공함
• 이는 의사결정나무의 단점을 보완하며, 현재까지 가장 성공적인 머신러닝 알고리듬 중 하나로 평가됨

결론 및 추가 학습

• 의사결정나무는 해석이 용이하고 학습 속도가 빠르며 전처리가 간단한 모델임
• 그러나 과적합과 불안정성 문제를 해결하기 위해 가지치기나 앙상블 기법이 필요함
• 글에서는 회귀용 트리, 엔드컷 선호(end-cut preference), 하이퍼파라미터 등은 다루지 않았으며, 관련 자료를 통해 추가 학습을 권장함