Decision tree for classification

노드를 어떻게 결정할까?

  • 각 feature에 대해 multiple test를 해본다.
  • homogeneous group 을 생성한다.
  • 각 그룹의 member 수를 계산한다.
  • member 수가 가장 많은 feature를 node로 결정

아래의 경우에서는 outlook feature가 node 가 된다.

 

하지만, dataset이 커질수록 homogeoeous group이 하나도 없는 경우가 발생함

사실 일반적으로 이런 경우가 더 많음

→ Impurity 기준으로 나누게 되고, 불순도를 줄이는 방향으로 확장해나간다.

 

확장 방법

Entropy-based expansion


+ 엔트로피란 ?
엔트로피는 Impurity 즉 불순도를 수치적으로 나타낸 척도이다.
엔트로피가 높다는 것은 불순도가 높다는 뜻
한 범주에 하나의 데이터만 있다면? 불순도 최소 = 0

 

각 테스트별로 entropy를 계산한다.

weighted avarage로 분기 이후 엔트로피를 계산한다.

Q(test) 값이 가장 낮은 feature를 노드로 !

 


Gini impurity-based expansion

지니 불순도 : 무작위로 선택된 샘플이 잘못 분류될 확률

불순도 최소 : 0

불순도 최대 : 1 - (1/2)*2 - (1/2)*2 = 0.5

 

 

역시 Q(test) 값이 가장 낮은 feature를 노드로 !

 

연속적인 숫자형 데이터는 ?

임계값(threshold)을 찾아서 데이터 구분 ( ex) 나이 > 30, 온도 < 20)

  1. 값들을 sort 한다.
  2. 모든 행들에 대해 행간 평균값을 구한다.
  3. 각 평균값마다 임계값으로 설정해서 테스트 실행한다.
  4. 엔트로피 또는 지니 불순도를 계산한다.
  5. 최솟값을 가지는 feature를 선택한다.

 

Regression Tree

위와 같은 경우는 Linear Regression 사용할 수 없다.

regression tree 쓰면 되지 !

  1. 각 spot들의 중간 지점마다 split bar를 둔다.
  2. 각 split point 마다 SSR(Sum of Squared Residuals)를 계산한다.두 그룹의 SSR을 각각 계산하고, 둘을 합하여 그 분할 지점에서의 SSR을 구한다.

   3. 가장 작은 SSR을 가지는 분할 지점을 선택한다.

 

+ 왜 가장 작은 SSR?

SSR, 즉 잔차 제곱합은 모델이 예측하는 값과 실제 값의 차이를 나타내는 지표 !

따라서 SSR이 작을수록 모델이 데이터를 더 잘 예측하고 있다는 의미

Decision Tree 의 Overfitting

Overfitting?

모델이 훈련 데이터에 너무 적합하게 학습되어서 새로운 테스트 데이터에 대해서는 일반화가 잘 되지 않는 현상

Decision Tree가 너무 복잡해지면 ( 즉, 트리의 노드 수가 너무 많아지면 )

훈련 데이터에는 완벽하게 맞추지만 테스트 데이터에 대해서는 성능이 떨어지는 경우 발생

 

트리의 크기가 증가하면 훈련 데이터에 대한 정확도는 계속 증가하지만,

테스트 데이터에 대한 정확도는 어느 순간 이후로 개선되지 않거나 오히려 감소함

 

Overfitting의 조건

error_te(h) > error_tr(h)

테스트 데이터에서의 오류율이 훈련 데이터에서의 오류율보다 클 때

 

Overfitting의 정도

error_te(h) − error_tr(h)

테스트 데이터에서의 오류율과 훈련 데이터에서의 오류율 차이가 클수록 과적합이 심하다.

 

 

Pruning

 

Overfitting을 막기위한 전략

최대 깊이나 터미널 노드의 최대 개수, 혹은 한 노드가 분할하기 위한 최소 데이터 수를 제한

  1. Pre-pruning (사전 가지치기)
    • 트리의 성장이 특정 기준에 도달하면 더 이상 트리를 확장하지 않고 그 지점에서 멈춤
    • 트리를 학습하는 동안, 트리가 지나치게 복잡해지기 전에 미리 가지치기를 한다.
  2. Post-pruning (사후 가지치기)
    트리를 완전히 학습한 후, 나중에 가지치기를 함

    Ex) Reduced Error Pruning
    1. 리프 노드에서부터 시작해서 위로 올라감
    2. 가지치기 대상이 내부 노드일 경우, 해당 서브트리가 제거되고 그 내부 노드는 리프 노드가 된다.
    3. 그 노드에 가장 많이 나타나는 분류 라벨을 할당한다.
      • 예를 들어, 해당 노드의 하위 데이터가 A 클래스가 60%, B 클래스가 40% 였다면 해당 노드를 A 클래스로 분류
    4. 가지치기 후 해당 트리의 성능을 검증 데이터로 확인
    5. 검증 정확도가 나빠지지 않았다면, 가지치기 변화를 유지
    6. 검증 정확도가 떨어질때까지 위의 가지치기 과정을 계속 반복하고, 그 지점에서 가지치기를 중단한다.
  1.  

 

Decision Tree 의 장점과 단점

장점

  1. 직관적이고 시각적으로 쉽게 이해할 수 있는 구조
  2. 데이터 전처리가 거의 필요하지 않음
    • 데이터 스케일링이나 변수 변환이 필요하지 않고, 이산형 또는 연속형 데이터 모두 처리할 수 있다.
  3. 다양한 유형의 데이터 처리 가능
    • 분류와 회귀 문제에 모두 적합함
  4. Overfitting을 방지하는 가지치기 가능
  5. 결과 해석이 명확함
    • Decision Tree의 결과는 조건문 형태로 표현되기 때문에 예측에 영향을 미친 요인을 명확하게 알 수 있음
  6. 결측치 처리 가능
    • 일부 결측치(missing data)가 있더라도 그 데이터들을 무시하고 다른 데이터를 사용해 학습을 진행할 수 있다.

 

단점

  1. Overfitting 가능성
    • 트리의 깊이가 깊어질수록 훈련 데이터에 과도하게 맞춰질 가능성이 높아짐
  2. 작은 변화에도 민감함
    • 데이터가 조금만 변경되어도 트리의 구조가 크게 바뀔 수 있음.
    • 예측의 일관성이 떨어질 수 있다.
    • 이 문제를 해결하기 위해 앙상블 기법이 사용됨
  3. 최적의 트리 찾기 어려움
    • 결정 트리는 greedy 알고리즘을 사용하여 노드를 분할하므로, 항상 최적의 트리를 보장하지 못할 수 있음
  4. 비교적 낮은 예측 성능
    • 단일 Decision Tree는 다른 알고리즘과 비교했을 때 예측 성능이 떨어질 수 있음
  5. 변수 간 상호작용 파악 어려움
    • 각각의 분할이 독립적으로 이루어지기 때문에, 변수들 간의 상호작용을 명시적으로 나타내지 않음.
  6. 데이터 불균형에 취약함
    • 클래스 간 데이터의 불균형이 심한 경우 편향된 예측을 할 수 있다.
    • 데이터의 클래스 비율을 적절히 조정하거나 재샘플링 기법을 사용해야 할 수도 있다.

+ Recent posts

티스토리툴바