classification with trees

data mining
공개

2025년 4월 14일

gini 지수가 낮을수록, misclassification error가 낮을수록, entropy가 낮을수록 Information gain이 높을수록, gain ratio가 클수록 순도가 높고 좋다. 최댓값은 0.5. entropy는 최댓값 1.

과적합 pruning 할 때 misclassification error를 기준으로 한다.

의사결정 트리는 데이터 마이닝에서 가장 널리 사용되는 분류 기법 중 하나로, 데이터의 패턴을 트리 구조로 표현하여 예측 모델을 구축한다.

What is Data minig

  • 데이터 마이닝은 대량의 데이터에서 암시적이고 이전에 알려지지 않았던 잠재적으로 유용한 지식이나 패턴을 추출하는 과정입니다.

종류

  • 지도 학습1: 주어진 학습 데이터를 이용하여 목표 속성의 값을 예측하는 모델을 생성하는 과정으로, 입력(속성)과 출력(정답)이 모두 주어진 데이터를 바탕으로 학습
  • 비지도 학습

분류

  • 목표
    • 새로운 데이터에 대해서도 정확한 예측이 가능한 일반화된 모델을 만드는 것
    • 이를 위해 과거 데이터를 학습용과 테스트용으로 나누어 모델의 성능을 검증

의사결정 트리의 구조와 원리

  • 의사결정 트리는 노드와 가지로 구성된 계층적 구조로, 각 노드는 특성(attribute)을 나타내며 가지는 테스트 결과를 표현.

  • 잎 노드는 클래스 레이블이나 클래스 분포를 나타냄

  • 의사결정 트리 구축은 주로 탐욕적 전략(Greedy strategy)을 사용하며, 각 단계에서 가장 좋은 분할 기준을 선택함.

  • 대표적인 의사결정 트리 알고리즘으로는 CART, ID3, C4.5, SLIQ, SPRINT 등이 있다.

노드 불순도 측정 방법

의사결정 트리에서 최적의 분할을 결정하기 위해 다양한 불순도 측정 방법이 사용됩니다:

  1. Gini Index: 노드의 불순도를 측정하는 방법으로, 1-∑[p(j|t)]²로 계산됩니다. 값이 0에 가까울수록 순수한 노드를 의미합니다.

  2. Entropy(엔트로피): 노드의 동질성을 측정하는 방법으로, -∑p(j|t)log₂p(j|t)로 계산됩니다. 0일 때 완전히 동질적인 노드를 의미합니다.

  3. Information Gain(정보 이득): 분할 전후의 엔트로피 차이로, 분할로 인해 얻어지는 불확실성 감소량을 의미합니다. 높은 정보 이득은 해당 속성이 데이터를 잘 나누는 것을 의미합니다.

  4. Gain Ratio(이득 비율): 정보 이득을 분할의 내재 정보량(Split Information)으로 나눈 값으로, 분기가 많은 속성에 대한 편향을 줄이기 위해 고안되었습니다.

트리 분할 기준

트리 분할 시 고려해야 할 주요 이슈는 다음과 같습니다: - 데이터 분할 방법 선택 - 속성의 테스트 조건 명시 - 최고의 분할 정의 - 트리 분기 종료 시점 결정

최적의 분할은 불순도를 최소화하는 방향으로 이루어지며, CART는 Gini 기반 분할을, ID3와 C4.5는 Information Gain 기반 분할을 주로 사용합니다.

모델 평가 기준

의사결정 트리 모델의 평가는 다음과 같은 기준으로 이루어집니다: - 테스트 세트에서의 정확도(%) - 오류율 - 혼동 행렬(Confusion Matrix) - 속도와 확장성 - 노이즈와 결측값 처리 능력

결론

의사결정 트리는 직관적이고 이해하기 쉬운 분류 모델을 제공하지만, 과적합(overfitting)이나 데이터 단편화와 같은 문제가 발생할 수 있습니다. 이를 해결하기 위해 C4.5와 같은 알고리즘은 Gain Ratio를 도입하여 분기가 많은 속성에 대한 편향을 줄이는 방법을 제시했습니다.

의사결정 트리의 성공적인 구축을 위해서는 적절한 불순도 측정 방법 선택, 가지치기(pruning), 그리고 다양한 속성 선택 기준의 이해가 필요합니다. 이러한 방법들을 통해 보다 정확하고 일반화된 모델을 구축할 수 있습니다.

맨 위로

각주

  1. 규칙 기반 시스템 != 연관 규칙 학습↩︎