[ML 머신러닝] 의사결정트리(Decision Tree) 알고리즘 개념 및 코드

 

의사결정트리 (Decision Tree) 란?

 

지도학습에 속하는 모델로, 분류와 회귀에 모두 사용 가능하다. 

의사결정트리는 데이터에서 규칙을 자동으로 학습하여 이를 기반으로 트리 구조의 분류 규칙을 만든다. 쉽게 말해, 스무고개를 생각하면 쉽다. 일반적으로 가장 쉽게 표현하는 방법은 if/else 기반으로 나타내는 것이다.

 

의사결정트리의 기본 개념

한 분기마다 변수 영역을 두 개로 구분한다. 이진트리의 개념으로 생각하면 된다.

• 루트 노드 (Root Node): 트리의 시작점으로 전체 데이터를 포함하는 노드
• 규칙 노드 (Internal Node): 나무 구조의 중간에 있는 노드
• 끝 노드 (Leaf Node): 트리의 끝에 위치한 노드로 최종적으로 분류된 결과를 나타냄

의사결정트리의 목표는 데이터를 잘 나눠서 leaf node에 최대한 순수한, 다른 데이터가 섞이지 않고 균일하게 데이터를 완전히 분류하는 것이다. 즉 복잡성(entorpy)이 낮도록 만드는 것이다.

 

---

데이터 균일?

균일성이란 한 그룹(범주) 내에서 같은 특성을 가진 데이터들이 얼마나 모여 있는지를 뜻한다.

 

이를 위해 트리는 불순도(Impurity)라는 개념을 사용한다.

불순도는 데이터가 섞여있는 정도를 나타내며, 다양한 클래스나 값이 섞여 있을수록 불순도는 높아진다. 

 

따라서, 트리를 분기할 때, 목표는 불순도를 줄이는 것이다. 즉, 현재의 불순도보다 자식 노드의 불순도가 더 낮아지도록 설정해야한다.

 

여기서, 현재 노드와 자식 노드의 불순도 차이를 정보이득(Information)이라고 한다. 

---

불순도 측정 방법

불순도를 측정하는 방법은 목표 변수(\(y\))가 범주형인 경우 엔트로피, 지니 지수를 사용하고,연속형인 경우MSE를 이용해 분산량을 감소시켜 이진 분리를 한다.

 

엔트로피(Entropy)

- 엔트로피는 데이터의 불확실성(불균일성)을 측정하는 지표

- 서로 다른 값이나 데이터가 많이 섞여있으면 엔트로피는 높고, 동일한 데이터가 많을수록 엔트로피가 낮다.

- 공식:

 

 

정보 이득 (Information gain)

- 분기 전과 후의 불순도 차이를 의미

- 분기 전 불순도가 1, 분기 후 불순도가 0.4라면, 정보 이득은 1−0.4=0.61 - 0.4 = 0.61−0.4=0.6

- 분기 과정에서 정보 이득이 최대화되는 조건을 찾는 것이 목표

- 엔트로피와 반대 방향으로 작용한다. 엔트로피가 감소하면, 정보 이득은 증가한다.

- 공식: 1 - 엔트로피 지수

 

정보 이득의 최대화 -> 불순도의 감소 -> 엔트로피의 감소

 

지니 지수(Gini Index)

 

- 한 데이터 집합에서 임의로 두 개의 데이터를 선택했을 때, 그 데이터들이 서로 다를 확률을 나타냄

- 지니 지수는 0에 가까울수록 데이터가 더 균일하고, 0.5에 가까울수록 데이터가 많이 섞여 있다는 것을 의미

- 공식:

 

---

의사결정트리의 과정

• 가능한 한 많은 데이터를 구분지을 수 있는 기준을 선택 (규칙 조건)
• 노드의 불순도 계산
• 각 노드에서 하나의 규칙 조건을 가진 이진 결정 트리를 진행
• 각 분할된 영역이 한 개의 타깃값(하나의 클래스)만 가질 때까지 위의 내용을 반복

from sklearn.model_selection import train_test_split
from sklearn.datasets import load_breast_cancer
from sklearn.tree import DecisionTreeClassifier

cancer = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(cancer.data, cancer.target, stratify=cancer.target, random_state=42)

dt = DecisionTreeClassifier()
dt.fit(X_train, y_train)
accuracy_train = dt.score(X_train, y_train)
accuracy_test = dt.score(X_test, y_test)
print("Train dataset 정확도: ", accuracy_train) # 과적합이 되어 학습 데이터셋에 대해서는 100% 정답
print("Test dataset 정확도: {0:.3f}".format(accuracy_test)) # 테스트 데이터셋은 92%의 정답률

---

의사결정트리 유의점

 

간단하고 직관적인 모델이지만, 모든 리프 노드를 완벽하게 분류하려다 보면 모델이 과대적합(overfitting)에 빠질 수 있다. 이는 모델이 훈련 데이터에 지나치게 맞추어져, 새로운 데이터에 대한 예측 성능이 떨어지게 되는 문제이다. 이를 막기 위해 과대적합 방지 기법을 사용한다.

 

과대적합을 막는 방법

1. 사전 가지치기 (Pre-Pruning)

  - 트리 생성을 일찍 중단하여 모델 복잡도를 제어하는 방법 

• 트리의 최대 깊이 제한 (max_depth) : 깊이가 깊어질수록 모델 복잡해지고, 과대적합 가능성 높아짐
• 리프의 최대 개수 제한 (max_leaf_nodes): 리프 노드의 개수를 제한해 과도한 분할을 방지
• 분할을 위한 최소 데이터 수 설정 (min_samples_split): 분할을 위해 필요한 최소 데이터 포인트 수를 지정

2. 사후 가지치기 (Post-Pruning)

  - 트리를 먼저 완성한 후, 불필요하거나 과도한 노드를 삭제하거나 병합하여 트리를 단순화하는 방법

 

결정 트리의 주요 하이퍼 파라미터

모델을 일반화하고 과대적합을 막기 위해 결정 트리의 하이퍼파라미터 튜닝을 통해 과대적합을 막아야 한다.

주요 하이퍼 파라미터는 다음과 같다.

• max_depth : 트리의 최대 깊이를 설정 (분할하는 횟수, 트리의 개수)
• max_features : 분할할 때 feature의 최대 개수 지정. 모든 특성을 사용하지 않고, 일부만 사용하여 복잡도 줄임
• min_samples_split (defualt : 2) : 노드를 분할할 때 필요한 최소 샘플 수를 설정. 예) samples를 4라고 할 때 samples가 3개 남아있으면 더 이상 분할하지 않는다는 의미
• min_samples_leaf : 분할 후 각 리프 노드에 있어야하는 최소 샘플 개수. 예) 3이라고 하면 남아있는 샘플 데이터 수가 5개라면 어떻게 나눠도 양쪽의 노드에 최소 3개의 샘플 데이터를 줄 수가 없다. 그렇다면 분할을 중단한다.
• max_leaf_nodes : 트리에서 생성될 수 있는 최대 리프 노드 개수를 설정. 리프 노드의 수가 많을수록 모델이 복잡

# 트리의 깊이 제한
dt_limit = DecisionTreeClassifier(max_depth=4, random_state=0)
dt_limit.fit(X_train, y_train)

print("Train dataset 정확도: {0:.3f}".format(dt_limit.score(X_train, y_train))) # train 정확도 0.988
print("Test dataset 정확도: {0:.3f}".format(dt_limit.score(X_test, y_test))) # test 정확도 0.951