Zzong's Notes

Decision Tree

16 min read

Decision Tree란

Decision Trees(DT, 의사결정나무)는 비모수(non-parametric)적인 supervised learning 방법으로, 주로 classification과 regression 문제에 사용됩니다. 이 기법의 목적은 데이터의 feature로부터 유도된 간단한 결정 규칙을 학습하여, target 변수의 값을 예측하는 모델을 만드는 것입니다.

B) 장점

  • 이해하기 쉽고 해석이 용이합니다. 또한, 트리를 시각화할 수 있습니다.
  • 트리를 사용한 예측의 비용은 학습에 사용된 데이터 포인트 수 에 대해 으로 매우 효율적입니다.

C) 단점

  • Decision tree 학습자는 데이터를 과도하게 복잡하게 분할(over-complex tree)하여 일반화 성능이 떨어질 수 있습니다. 이러한 현상을 overfitting이라고 합니다.

D) 선형 분류기와의 비교

decision tree는 선형 분류기(e.g., logistic regression, linear SVM)와 비교했을 때, 별도의 데이터 정제(data cleaning)가 적게 들어가더라도 바로(out of box) 우수한 성능을 보이는 경우가 많습니다.

  1. decision tree 방식은 결측치(missing value)에 대한 보간(imputation)에 강인(robust)합니다. 반면, 선형 분류기는 어떤 imputation 기법을 적용하느냐에 따라 성능 차이가 크게 발생할 수 있습니다.
  2. decision tree는 feature의 척도(feature scale)에 영향을 받지 않습니다. 그러나 선형 분류기는 feature 간 비교를 위해 반드시 standardization과 같은 feature scaling이 필요합니다.
  3. decision tree는 이상치(outlier)에 대해 별도의 처리가 필요 없습니다. 반면, 선형 분류기는 이상치의 영향이 크므로 clipping 등의 처리가 요구됩니다.
  4. decision tree는 다중공선성(collinearity)에도 영향을 거의 받지 않습니다. 만약 두 feature가 높은 상관관계를 가진다면, 둘 중 한 feature만 split에 선택되고 나머지는 모델에 더 이상 영향을 미치지 않게 됩니다. 반면, 선형 분류기의 경우 두 feature 간 상관성이 높으면 한 feature가 없을 때 과예측(over-predict)이 발생할 수 있으며, regularization으로 어느 정도 완화 가능하지만 완벽하게 해결되지는 않습니다.
  5. decision tree는 비선형(non-linear)적인 결정 경계(decision boundary)를 형성할 수 있지만, 선형 분류기는 그렇지 못합니다.

E) How to Build the Tree

의사결정 트리(Decision Tree)의 구축 방법

“스무고개” 게임을 생각하시면 이해가 쉽습니다. 스무고개는 ‘예/아니오’로 답할 수 있는 질문을 던져 정답을 맞춰나가는 과정이죠. 의사결정 트리도 이와 유사하게, 데이터의 특징(Feature)에 대한 질문을 연속적으로 던져 데이터를 분류하거나 값을 예측하는 모델입니다.

E.1) 의사결정 트리 구축의 핵심 원리: 재귀적 분할 (Recursive Partitioning)

의사결정 트리의 목표는 가장 순수한(Homogeneous) 부분집합을 만드는 것입니다. 즉, 하나의 노드(네모 상자) 안에는 가능한 한 같은 종류의 데이터만 모이도록 데이터를 반복적으로 나누는 것입니다. 이 과정을 재귀적 분할이라고 부릅니다.

E.1.1) 1단계: 핵심 용어 이해하기

구축 방법을 알기 전에, 트리를 구성하는 요소들의 이름을 알아야 합니다.

  • 루트 노드 (Root Node): 트리가 시작되는 가장 최상위 노드. 전체 데이터를 포함합니다.
  • 결정 노드 (Decision Node / Internal Node): 데이터를 나누는 기준(질문)이 되는 중간 노드들.
  • 리프 노드 (Leaf Node / Terminal Node): 더 이상 데이터가 분할되지 않는 최종 노드. 이 노드에서 예측/분류 결과가 결정됩니다.
  • 가지 (Branch / Edge): 노드와 노드를 연결하는 선. 결정 노드의 질문에 대한 답변(e.g., ‘예’ 또는 ‘아니오’)을 나타냅니다.
  • 깊이 (Depth): 루트 노드에서 특정 노드까지 도달하는 데 거치는 가지의 수.

E.1.2) 2단계: “최적의 질문”을 찾는 기준 - 불순도(Impurity)

트리를 나눌 때, 어떤 기준으로 나누는 것이 가장 좋을까요? 예를 들어 “오늘 테니스를 칠까?”를 예측하는 데이터가 있다고 합시다. ‘날씨’, ‘습도’, ‘바람’ 중 어떤 질문을 먼저 던져야 가장 효과적으로 데이터를 나눌 수 있을까요?

이때 사용되는 개념이 **불순도(Impurity)**입니다. 불순도는 한 노드 안에 여러 클래스의 데이터가 얼마나 섞여 있는지를 나타내는 지표입니다.

  • 불순도가 높다: 여러 클래스가 마구 섞여 있다. (e.g., 테니스 침: 5, 안 침: 5)
  • 불순도가 낮다 (순수하다): 한 클래스의 데이터가 대부분이다. (e.g., 테니스 침: 9, 안 침: 1)

트리의 목표는 분할을 통해 불순도를 최대한 많이 감소시키는 것입니다.

이 “불순도 감소량”을 **정보 이득(information gain)**이라고 부릅니다. 즉, 정보 이득이 가장 큰 특징(질문)을 찾아 분할 기준으로 삼습니다.

E.1.2.1) 불순도 측정 지표 (대표적인 2가지)

  1. 지니 불순도 (Gini Impurity)

    • CART 알고리즘(대부분의 라이브러리 기본값)에서 사용됩니다.
    • 계산이 비교적 빠릅니다.
    • 공식: 1 - Σ (각 클래스의 비율)²
    • 의미: 0에 가까울수록 순수합니다. (0이면 완전히 순수) 0.5가 최대 불순도입니다 (클래스가 2개일 경우).
    • 예시: 한 노드에 A클래스 5개, B클래스 5개가 있다면,
      • 지니 불순도 =
    • 예시2: 한 노드에 A클래스 9개, B클래스 1개가 있다면,
      • 지니 불순도 =

  2. 엔트로피 (Entropy)

    • ID3, C4.5 알고리즘에서 사용됩니다. 정보 이론에서 유래한 개념입니다.
    • 공식: - Σ (각 클래스의 비율) * log₂(각 클래스의 비율)
    • 의미: 0에 가까울수록 순수합니다. (0이면 완전히 순수) 1이 최대 불순도입니다 (클래스가 2개일 경우).
    • 예시: 한 노드에 A클래스 5개, B클래스 5개가 있다면,
      • 엔트로피 =
    • 예시2: 한 노드에 A클래스 9개, B클래스 1개가 있다면,
      • 엔트로피 =

정보 이득(Information Gain) 계산법

정보 이득 = (분할 전 부모 노드의 불순도) - (분할 후 자식 노드들의 가중 평균 불순도)

알고리즘은 모든 특징과 모든 가능한 분할 지점에 대해 이 정보 이득을 계산하고, 그 값이 가장 큰 것을 이번 단계의 분할 기준으로 선택합니다.

E.1.3) 3단계: 의사결정 트리 구축 과정 (Step-by-Step)

이제 위 개념들을 종합하여 실제 트리를 만드는 과정을 살펴보겠습니다.

(1) 시작

  1. 루트 노드에서 시작: 모든 학습 데이터를 하나의 루트 노드에 넣습니다.

(2) 반복 2. 최적의 분할 기준 찾기:

  • 현재 노드에 있는 데이터에 대해 모든 특징(e.g., 날씨, 습도, 바람)을 하나씩 살펴봅니다.
  • 각 특징에 대해 가능한 모든 분할 지점을 기준으로 데이터를 나눠봅니다.
    • 범주형 특징 (e.g., 날씨): ‘맑음’, ‘흐림’, ‘비’ 각 경우로 나눕니다.
    • 연속형 특징 (e.g., 습도): 70, 75, 80 등 모든 값을 기준으로 ‘이상/이하’로 나눠봅니다.
  • 각 분할마다 **정보 이득(Information Gain)**을 계산합니다.
  • 계산된 정보 이득 중 가장 큰 값을 갖는 특징과 분할 지점을 이번 노드의 분할 기준으로 선택합니다.
  1. 데이터 분할: 2단계에서 찾은 최적의 기준으로 현재 노드의 데이터를 2개 이상의 자식 노드로 분할합니다.
  2. **재귀적 반복:**생성된 모든 자식 노드에 대해 2~3단계 과정을 반복합니다.

(3) 종료

분할 중단 (Stopping Condition): 아래 조건 중 하나라도 만족하면 더 이상 분할하지 않고 해당 노드를 리프 노드로 만듭니다.

  • 노드가 완벽하게 순수해진 경우 (노드 안의 모든 데이터가 같은 클래스일 때).
  • 더 이상 분할할 특징이 없는 경우.
  • 미리 정해둔 최대 깊이(max_depth) 에 도달한 경우.
  • 노드에 포함된 데이터 샘플 수가 미리 정해둔 최소 샘플 수(min_samples_leaf) 보다 적을 경우.
  • 분할을 통해 얻는 정보 이득이 매우 미미하여 거의 없는 경우.

(4) 예측값 할당: 분할이 중단되어 만들어진 리프 노드에 예측값을 할당합니다.

  • 분류 트리: 해당 리프 노드에서 가장 빈도가 높은 클래스를 예측값으로 할당합니다. (e.g., ‘테니스 침’ 8개, ‘안 침’ 2개 -> ‘테니스 침’으로 예측)
  • 회귀 트리: 해당 리프 노드에 속한 데이터들의 평균값을 예측값으로 할당합니다.

E.1.4) 4단계: 과적합(Overfitting) 방지와 가지치기(Pruning)

위 과정대로 트리를 제한 없이 성장시키면, 학습 데이터의 아주 사소한 특징까지 모두 학습하여 매우 복잡한 트리가 만들어집니다. 이는 학습 데이터는 100% 맞추지만, 새로운 데이터에 대해서는 성능이 떨어지는 과적합(Overfitting) 문제를 야기합니다.

이를 해결하기 위한 방법이 **가지치기(Pruning)**입니다.

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

    • 트리가 성장하는 과정에서 미리 중단시키는 방법입니다.
    • 위의 [종료 조건] 에서 max_depth, min_samples_leaf 같은 하이퍼파라미터를 설정하는 것이 바로 사전 가지치기입니다.
    • 예: “트리의 깊이는 최대 5까지만 허용”, “리프 노드는 최소 10개 이상의 샘플을 가져야 함”.

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

    • 일단 트리를 최대한 크게 만든 후, 불필요한 가지를 제거하는 방법입니다.
    • 검증 데이터셋(Validation set)을 사용하여 특정 가지를 제거했을 때 예측 오류가 감소하는지를 평가하고, 오류가 감소하면 해당 가지를 잘라냅니다.
    • 일반적으로 사전 가지치기보다 성능이 더 좋다고 알려져 있지만, 계산 비용이 더 큽니다.

E.1.5) 요약: 의사결정 트리 구축의 흐름

  1. 시작: 전체 데이터를 루트 노드에 둔다.
  2. 기준 선택: 현재 노드의 불순도를 가장 많이 낮출 수 있는(정보 이득이 최대인) 특징과 분할점을 찾는다.
  3. 분할: 선택된 기준으로 데이터를 자식 노드로 나눈다.
  4. 반복/종료: 모든 자식 노드에 대해 2~3번 과정을 반복하되, 정지 조건(순수도 100%, 최대 깊이 도달 등)을 만족하면 멈추고 리프 노드로 만든다.
  5. 가지치기: 과적합을 막기 위해 너무 복잡해진 트리의 가지를 잘라내 모델을 단순화한다.

이러한 과정을 통해 데이터의 패턴을 스스로 학습하고, 새로운 데이터에 대한 예측을 수행할 수 있는 강력하고 해석하기 쉬운 의사결정 트리 모델이 완성됩니다.

링크된 언급

10
bagging

Bagging 분류 및 회귀 문제를 위해서, 여러 bootstrapping 샘플을 가지고 독립적인 모델 (e.g. Decision Tree) 들을 여러개 만든 다음 각 모델에서 나온 예측값을 평균 (분류 문제에서는 과반수 투표) 내는 것을 방식을 의미한다. A.1) Figure A.2) 특징 부트스트랩 데이터를 활용하여 ...

classification

...tic regression, linear SVM) Kernel Machines (kernel trick 을 사용한 SVMs) deep learning 계열의 neural network Decision Tree 와 ensemble 기반의 tree (random forest, GBM) KNN 또는 Naïve Bayes 와 같은 Naive 한 기술들 E) Related F) References ...

collinearity

...까지 변수를 제거해야 한다. 공선성이 문제가 되는 이유는 1) 회귀 모델에서 계산하는 추정 값의 표준 오차 가 커지고, 2) 회귀 분석의 결과 해석을 어렵게 만들기 때문이다. 반대로, Decision Tree 나 KNN 과 같은 방식에서는 공선성이 그다지 문제가 되진 않는다. 그래서 공선성을 피하기 위해 random forest 또는 GBM 을 통해 최적의 상호작용 항들을 걸러내는 전략을 ...

Gradient Boosting Machine

... 수행할 수 있는 예측모형이며 예측모형의 ensemble 방법론 중 boosting 계열에 속하는 알고리즘 여러개의 weak models 을 조합해서 하나의 결과를 만든다. 일반적으로 Decision Trees 를 많이 사용하며, 이 경우 알고리즘 이름은 gradient boosted trees 로 불리게 된다. 일반적으로 random forest 보다 성능이 좋다고 알려져 있다. A.1)...

information gain

Information Gain Decision Tree 에서 tree 의 node 를 나눌 때, feature 를 선택하는 기준으로 information gain 을 사용한다.

Label Encoding

... 을 나타낸 거라면, ‘cat’ 과 ‘apple’의 평균은 ‘dog’으로 오해할 수 있다: (0 + 2) / 2 = 1 위와 같은 단점에도 불구하고, tree based model 인 Decision Tree 또는 random forest 와 같은 모델에는 잘 적용될 수 있다. Pros 장점: One Hot Encoding 에 비해 저장 공간을 적게 필요로 한다. C) References

Learning-to-Rank

...e y i 를 가 존재하고, 이를 추정하려는 predicted score s {i}=f\left(x {i}\right) 가 출력값으로 있다. 이 score 를 계산하기 위해 일반적으로 Decision Tree 또는 neural network 등 을 활용한다. D.3) Loss Function D.3.1) Pointwise Methods 각 document d i 에 정의된 loss term...

LightGBM

...ing Machine, XGBoost I) 단점: ID 간의 관계 학습 부재 “LightGBM이 ID 간의 관계를 학습하지 못한다”는 말의 핵심적인 이유는 LightGBM이 결정 트리(Decision Tree)에 기반한 모델이기 때문입니다. 결정 트리가 동작하는 방식을 이해하면 그 이유를 명확히 알 수 있습니다. I.1.1) 결정 트리의 작동 방식: “질문을 통한 그룹 나누기” 결정 트리는...

Normalization

...ors, PCA 처럼 feature scale 에 민감한 방법에서는 normalization 또는 standardization 이 모델 품질과 학습 안정성에 직접 영향을 준다. 반대로 Decision Tree 계열은 feature 내부의 순서와 threshold split 에 더 의존하므로 scaling 영향이 상대적으로 작다.

standardization

...게 다르면 parameter 마다 업데이트 속도가 달라진다. 어떤 feature 는 큰 단위 때문에 gradient 를 지배하고, 어떤 feature 는 거의 반영되지 않을 수 있다. Decision Tree 계열은 split 기준이 feature 내부의 순서에 더 의존하므로 standardization 영향이 작다. 반대로 logistic regression, support vector ...