9. Decision Tree

트리 구조 (Tree structure)

: 노드(node)와 노드간 연결을 표현하는 에지(edge)로 구성된 노드 → 분기 → 계층적 구조가 형성.

• 하나 이상의 자식 노드를 가질 수 있음

상위: 루트 노드 root node

하위: 잎 노드 leaf node

Decision Tree

: 데이터의 특징(feature)과 클래스(label) 사이의 관계를 트리 구조로 나타내는 지도학습.

• 각 노드에서 “하나의” 특징에 대한 테스트를 수행, 분기 생성
• 분기는 나눌 수 없을 때까지 수행, 마지막 리프 노드 생성
• 리프 노드: 최종적 클래스(label) 값을 예측하는 역할.

<aside> 💻 과일크기 데이터 셋

</aside>

Node의 역할: 특성값에 따라 공간을 둘로 나누는 역할

• 차원에 따라 공간을 쪼개어지는 것 → Decision Tress에 질문을 추가하는 것.
• 두 Label이 잘 분리되도록 공간을 쪼개면, 좋은 Decision Tree

<aside> 💻 Decision Tree와 공간의 분할 (X1 가로, X2 세로)

</aside>

어떤 분할이 좋은 분할인가?

노드에서 선택된 특정에 대해 분할의 기준값을 어떻게 선택해야할까?

엔트로피 (entropy) ⭐⭐⭐⭐⭐ 0이 될수록 좋음!!

: 노드의 데이터를 나눌 때 사용되는 지표

• 어떤 집합이 가지고 있는 혼잡도(무질서도)를 나타내는 지표

${H(X)=}$

${P(x_i):}$ 집단 내의 i라는 클래스를 가진 데이터의 비율

<aside> 💻 엔트로피 (entropy) 계산 예시1

완벽하게 나눠진 경우 → entropy = 0

</aside>

Information Gain: 공간을 쪼갬으로 인해서 얻어지게 되는 무질서함의 “감소” 정도. 1이 될수록 좋음!! ⭐⭐⭐

• 무질서도가 얼마나 개선되었는지 측정함.
• 해당 특성을 기준으로 데이터를 분할했을 때 얼마나 많은 정보를 얻을 수 있는지
• 최댓값 1

$$ {IG(A)=H(T)-\sum_{\upsilon \in Values(A)} \frac{|T_v|}{|T|}H(T_v)} $$

${H(T)=}$ 분할 전 엔트로피

${H(T_v)=}$ 분할 후 생성된 각 집단의 엔트로피

${T=}$ 분할 전 전체 데이터의 개수

${T_v=}$ 분할 후 생셩된 집단의 데이터의 개수

<aside> 💻 엔트로피 (entropy) 계산 예시2

완벽하게 나눠진 경우 → IG = 1

</aside>

• 불확실하다 (엔트로피가 크다)
• 엔트로피가 낮을 수록 많은 정보를 가지고 있다???

1. 트리를 초기화. 루트 노드를 만들고 모든 데이터를 루트 노드의 분류에 사용

1. 모든 데이터의 클래스가 같거나 종료 조건에 해당 → 해당 노드 리프 노드, 클래스 할당
2. 모든 특성에 대하여 Information Gain 계산
3. IG가 가장 큰 특성을 선택하여, 해당 특성으로 데이터를 분할
4. 분할된 데이터 집합에 대해, Decision Tree 알고리즘으로 **“재귀적”**으로 적용

<aside> 💻 Decision Tree 알고리즘 예시

1. 분할 전, 목표 속성인 참가여부에 대한 엔트로피 계산
2. E(경기) =

2-1. 날씨 (조건부 확률)

E(경기|날씨) =

2-2. 온도

E(경기|온도) =

2-3. 습도

E(경기|습도) =

2-4. 바람

E(경기|바람) =

1. Information Gain이 가장 큰 변수로 데이터를 분할하기.IG(경기, 온도) =IG(경기, 바람) =
2. IG(경기, 습도) =
3. IG(경기, 날씨) =
4. 각각 분할된 데이터 집합에 대해, Decision Tree 알고리즘을 재귀적으로 적용
5. E(경기 참가) =

4-1. 맑음

E(경기|온도) =

E(경기|습도) =

E(경기|바람) =

---

IG(경기, 온도) =

IG(경기, 습도) =

IG(경기, 바람) =

4-2. 흐림

E(경기|온도) =

E(경기|습도) =

E(경기|바람) =

---

IG(경기, 온도) =

IG(경기, 습도) =

IG(경기, 바람) =

4-3. 비

E(경기|온도) =

E(경기|습도) =

E(경기|바람) =

---

IG(경기, 온도) =

IG(경기, 습도) =

IG(경기, 바람) =

</aside>

변수가 연속형일 때 변수를 선택하는 방법

1. 변수에 따라 데이터를 정렬 (오름차순)

2. 변수가 가질 수 있는 값을 하니씩 넣어보면서 계산

Information Gain을 높이는 가장 좋은 Feature 고르기

• 이 값에 따라 두 개의 Child Node 생성 → 각 Child Node에서 반복 → 모든 Child Node가 Pure 할 때까지 반복

Decision Tree의 층, 그 깊이를 Depth라고 한다.

Overfitting

• Depth ⬆️: 개별적인 데이터를 잘 분류할 수 있게 됨. (유연해짐)
• 지나치게 깊어지면 Overfitting 발생할 수 있음.

Hyperparameter

1. Max Depth

: 깊어질수록 모델이 유연해짐

2. Minimum number of samples to split

: Split을 멈추는 데이터의 최소 개수

: 작을수록 → 더 유연한 모델이 됨.

3. Minimum number of samples per leaf

: 리프노드의 최소 데이터 개수

: 작을수록 → 더 유연한 모델이 됨.

Decision Tree의 장단점

장점

• 이해하기 쉬운 규칙 : If ~ Then 형식 (단, Tree가 너무 복잡하지 않을때)
• 분류예측에 유용
• 연속, 범주형 모두 취급 가능
• 비교적 뻐른 속도
• 스케일링 필요 없음 ⭐

단점

• 연속형 변수값을 예측시 적당하지 않음
• 회귀모형에서 예측력 떨어짐
• 트리모형 복잡시 예측력 떨어짐
• 데이터 변형에 민감하여 안정적이지 않음
• (오버피팅이 발생하기 쉽다.)
• 일반화하기 어려움.

앙상블 기법

: 데이터 셋으로부터 다수의 덜 유연한 모델을 만들고, 예측값을 취합하여 예측하는 방식.

1. 배깅 Bagging:

Bootstrap Aggregator

: 병렬적으로 서로 다른 모델의 예측값을 취합하여 사용

: 부트스트래핑 된 여러 개의 데이터셋에 약한 모델을 학습시키고, 이 결과를 취합하여 예측

$$ f(x)=\frac{1}{B}\sum_{b=1}^{B}f_b(x) $$

1. 데이터 샘플링 (B: 데이터셋 수)
2. 서로 다른 모델 적용
3. 평균내기
4. (회귀: 평균, 분류: 다수결)

랜덤 포레스트 (Random Forest) - 일반화 성능이 매우 높음

: 배깅 앙상블을 사용하여 의사결정트리의 성능을 향상시킴

• 여러 개의 의사결정트리를 조합하여 만들어진 앙상블(Ensemble) 학습 알고리즘

1. 데이터 샘플링: 부트스트랩 샘플링, 무작위로 데이터 선택
2. 변수 샘플링: 분할을 결정하는데 사용되는 변수를 무작위로 선택 (전체 특성 중 일부만 사용됨) (data feature 수 ⬆️, model 유연성: ⬆️)
3. 의사 결정 트리 학습: 앙상블
4. 의사 결정 트리 결합 (다수결, 평균)

부트스트래핑을 통해 여러 개의 데이터셋을 만들고 각자 Decision Tree를 학습 → 학습된 결과를 취합하여 예측

장점

• 데이터에 변동성 → 여러모델 → 단일 데이터셋에 의존하지 않게됨 (오버피팅 예방)
• 변수의 개수를 제한 → 약한 모델 → 오버피팅 예방
• Outlier의 영향이 제한 → 모델이 안정화 됨. 로버스트(Robust)하다. 강건하다.

단점

• 여러 개의 Decision Tree가 중첩되어 있으므로 설명하기가 어려움.
• 단일 트리에 비해 계산이 많이 소요됨. (컴퓨팅 파워로 극복 가능)

2. 부스팅 Boosting

: 순차적으로 모델들을 만들어나가고, 최종적으로 만들어진 모델을 취합하여 사용

• 이전 단계에서 잘 분류하지 못한 데이터에 높은 가중치를 부여, 다음 단계에서 사용

$$ f(x)=\sum_{t}\alpha_th_t(x) $$

• 정확도가 높았던 모델에 높은 가중치 부여.

XG Boost - 시간이 많이 걸림

가볍게 의사결정트리 → XG Boost

다루지 않은 방법론

• SVM (Support Vector Machin): 잘안씀
• ANN (Artificial Neural Network)
  • Deep Neural Network
• Random Forest의 개량버전
  • XGBoost (높은 정확도로 유명)
  • LGBM

Model Trade-off

설명력-정확도의 Trade-off를 잘 따져서 문제에 맞는 문제를 풀어햐 함.