25일차 알고리즘 기초3

결정트리

결정트리(Decision Tree)는 데이터를 분류하거나 예측할 때 사용하는 지도 학습 알고리즘입니다. 나무(Tree) 구조를 이용해 의사결정 규칙을 모델링하며, 각 노드(Node)는 특정 조건, 가지(Branch)는 조건의 분기, 잎(Leaf Node)은 최종 결과(분류 또는 값)를 나타냅니다.

용어 정리

용어	설명
루트 노드(Root Node)	가장 첫 번째 기준이 되는 노드
내부 노드(Internal Node)	조건에 따라 분기되는 중간 노드
리프 노드(Leaf Node)	최종 결과(클래스 또는 값)를 나타내는 노드
가지(Branch)	조건에 따라 갈라지는 경로
깊이(Depth)	루트부터 리프까지의 최대 거리

작동 원리

1. 모든 특성 중에서 데이터를 가장 잘 나누는 기준(feature + threshold)를 선택합니다.
2. 해당 기준으로 데이터를 둘로 분할합니다.
3. 분할된 각 그룹에 대해 위 과정을 반복합니다.
4. 종료 조건을 만나면(예: 최대 깊이 도달, 분할 불가능 등) 리프 노드로 설정합니다.

분할 기준 (불순도 측정)

결정트리는 데이터를 분할할 때 "불순도(impurity)"를 최소화하는 방향으로 학습합니다.

✅ 지니 지수(Gini Index)

• $( p_i )$: 클래스 $( i )$의 비율
• 값이 작을수록 순수(pure)

✅ 엔트로피(Entropy)

• 정보 이득(Information Gain)을 통해 분할 성능 평가

✅ 분산(RSS: Residual Sum of Squares)

• 회귀(Regression) 트리에서 사용하는 기준
• 노드의 응답값의 분산을 기준으로 분할

장점

• 이해하기 쉬움 (시각화 가능)
• 전처리가 거의 필요 없음
• 범주형, 수치형 모두 처리 가능
• 비선형 문제에 강함

단점

• 과적합(overfitting) 발생 가능성 큼
• 작은 변화에 민감함 (불안정성)
• 일반화 성능 낮을 수 있음 → 가지치기(pruning) 필요

---

CART 알고리즘 (Classification and Regression Tree)

CART (Classification and Regression Tree) 알고리즘은 결정트리 계열에서 가장 널리 사용되는 알고리즘 중 하나입니다. 이름 그대로, 분류(Classification)와 회귀(Regression) 문제 모두에 사용할 수 있습니다.

✅ CART는 이진 트리(binary tree) 구조를 사용하며, 분할 기준으로 지니 지수(Gini Index) 또는 분산(Variance)를 사용합니다.

---

CART의 핵심 특징

항목	설명
트리 구조	이진 트리 (각 노드가 두 개의 자식만 가짐)
분류 기준	지니 지수(Gini Index)
회귀 기준	평균제곱오차(MSE) 또는 분산(Variance)
가지치기	사후 가지치기(Post-Pruning) 방식
사용 목적	분류 + 회귀 모두 가능

---

분류 기준 – 지니 지수 (Gini Index)

CART는 분류 문제에서 노드를 나눌 때 불순도(impurity)를 최소화하는 방향으로 작동합니다.
지니 지수는 다음과 같이 정의됩니다:

• $( p_i )$: 노드 t에서 클래스 $( i )$의 비율
• 값이 0에 가까울수록 순수한 노드입니다.

---

앙상블 러닝

앙상블 러닝은 여러 개의 머신러닝 모델(약한 학습기, weak learners)을 조합하여 하나의 강력한 모델(strong learner)을 만드는 기법입니다. 단일 모델보다 더 높은 정확도와 일반화 성능을 얻기 위해 사용됩니다.

✅ 다양한 모델의 예측을 결합(Aggregation)하여 전체적인 예측 성능을 향상시킵니다.

앙상블 러닝의 종류

앙상블 러닝은 크게 다음과 같이 나눌 수 있습니다.

방법	설명
배깅 (Bagging)	여러 모델을 병렬로 학습, 예측을 평균 또는 투표로 결정
페이스팅 (Pasting)	배깅과 유사하나, 데이터 샘플링 시 복원 없이 추출
부스팅 (Boosting)	모델을 순차적으로 학습, 이전 모델의 오류를 보완
스태킹 (Stacking)	여러 모델의 예측 결과를 또 다른 모델에 입력

---

배깅 (Bagging: Bootstrap Aggregating)

개념

• 원 데이터셋에서 복원 추출(Bootstrap sampling)로 여러 데이터셋을 만듦
• 각각의 데이터셋으로 모델을 학습 (병렬적)
• 최종 결과는 평균(회귀) 또는 다수결(분류)로 결정

대표 알고리즘

• 랜덤 포레스트(Random Forest)
  → 여러 개의 결정트리를 배깅한 알고리즘

장점

• 분산(variance)을 줄여 과적합(overfitting) 방지
• 병렬 처리가 가능하여 학습 속도 빠름

---

페이스팅 (Pasting)

개념

• 배깅과 거의 동일하지만, 복원 없이 샘플링(without replacement)
• 즉, 중복 없는 데이터 샘플을 여러 세트로 나누어 학습

특징

• 복원 없이 데이터를 샘플링하므로 더 다양한 샘플 구성 가능
• 데이터셋이 충분히 클 경우 효과적

---

부스팅 (Boosting)

개념

• 모델을 순차적으로 학습시키며, 이전 모델의 오류를 보완
• 각 단계마다 잘못 예측된 샘플에 가중치를 높여 다음 모델이 집중 학습하도록 유도

대표 알고리즘

알고리즘	설명
AdaBoost	오류에 따라 샘플 가중치를 조정
Gradient Boosting	잔차(residual)를 예측하는 방식
XGBoost / LightGBM	Gradient Boosting 개선 버전 (속도, 정확도 향상)