머신러닝 지도학습 - 의사결정나무(Decision Tree)

의사결정나무(Decision Tree)

- 의사결정나무란 의사결정 규칙(Decision Rule)을 나무구조로 도식화하여 관심대상이 되는 집단을 몇 개의 소집단으로 분류(Classificiation)하거나 예측(Regression)하는 계량적 분석 방법
- 분류 또는 예측이 나무구조의 If ~ then 형태의 추론규칙으로 표현되기 때문에 다른 분석 방법에 비하여 이해와 설명이 쉽다.
- 회귀 분석과 달리 각종 가정 불필요하며 직관적이고 해석이 비교적 쉬움
- 종속변수가 명목형인 경우 분류 나무(Classification Tree), 연속형인 경우 회귀 나무(Regression Tree) 사용
- 의사결정나무를 여러 개 합쳐서 만든 모델 중 대표적인 것이 Random Forest

https://ratsgo.github.io/machine%20learning/2017/03/26/tree/

의사 결정 나무(Decision Tree) 용어

- 노드(Node) : 데이터를 담고 있는 부분
- 루트노드(Root Node) : 모든 자료를 포함하고 있는 의사결정나무의 출발점으로 자료를 몇 개의 동질적인 그룹으로 나눔
- 레벨(Level) : 트리 구조 각 층의 번호(깊이)
- 차수(Degree) : 특정 노드가 가지고 있는 자식 노드의 수
- 높이(Height) : 최상위 노드부터 맨 끝 노드 까지의 깊이
-잎(Leaf)/단말(Terminal) : 차수가 0인 노드(마지막 끝단의 노드)
- 부모(Parent) : 서로 연결된 노드 중 레벨이 1만큼 작은 노드
- 자식(Child) : 서로 연결된 노드 중 레벨이 1만큼 큰 노드
- 조상(Ancestor) : 서로 연결된 노드 중 레벨이 2 이상 작은 노드
- 자손(Descentdant) : 서로 연결된 노드 중 레벨이 2 이상 큰 노드
- Splitting : 의사 결정 마디를 주어진 기준에 따라 하위 마디로 나누는 것

의사결정나무 타입

1) 분류 나무(Classification Tree)
 - 종속변수가 명목형인 경우 사용하는 의사결정나무 모델 / 범주형 목표 변수를 기준으로 마디를 나눔
 - 끝마디에 포함된 자료의 범주가 분류 결과값이 됨
 - 각 노드 분류 알고리즘은 이진 분류 시 지니지수(Gini Index) 기반의 CART 사용
 - 과적합 방지 및 모델 다순화를 위해 Depth, Impurity 등 관련 설정 활용
 - 이진 분할(CART, C4.5, C5.0)은 지니 지수와 엔트로피 지수 활용
 - CHAID(다지분할)은 카이제곱 통계량 활용.

2) 회귀 나무(Regression Tree)
 - 종속변수가 연속형인 경우 사용하는 의사결정나무 모델 / 연속형 목표 변수를 기준으로 마디를 나눔
 - 끝마디에 포함된 자료의 평균값이 각 끝마디의 회귀 값이 됨
 - 이진분할(CART)에서는 분산 감소량을 기준으로 계산
 - 다지분할(CHAID)에서는 ANOVA F-통계량을 기준으로 계산
 - 최적의 예측값 산출을 위해 패널티 함수를 사용하며 주로 오차제곱합(SSE) 사용

의사결정 나무 알고리즘

- 불순도를 감소시키는 방향으로 분리(Impurity 감소 = Purity 증가)
 * Pimpurity(불순도) : 특정 노드에 다양한 범주의 개체가 있는지 측정하는 기준, 엔트로피와 지니 지수로 판별
 * Purity(순수도)
*의사결정나무도 지도학습이기때문에 Target Value가 있음
** 현재 보고 있는 Dataset의 Target Value가 모두 같은 값을 갖고 있다 -> Stop
  else -->  tree : 분리 / dataset : segmentation
 *** 분리전보다 분리후의 조각 상태가 분류가 더 잘 되어있는 상태가 좋은 상태!
    -> 순수도/불순도 확인
  - 지니지수(Gini Index) : 엔트로피보다 계산이 빠르며 불순도가 높을수록 0.5에 가깝고 낮을수록 0에 가깝다
  - 엔트로피 지수(Entropy) : 무질서도를 정량화 한 값으로 값이 높을수록 해당 집단의 특징을 찾기 어려움
  **값이 낮을수록 좋다!
   - 가지치기(Pruning) : 과적합을 방지하기 위한 방법으로 오차와 규칙 기반 정확도를 기준으로 실시

step1. 모든 자료를 포함한 뿌리 마디로부터 시작
step2. 자료 가운데 불순도를 낮추는 최적의 요인을 찾는다
step3. 뿌리 마디를 최적 용인의 기준값을 찾아 하위 그룹으로 나눈다
step4. 각 하위 그룹에 대한 의사결정나무의 마디를 만든다.
step5. 반복적으로 새로운 하위 마디에서 최적의 요인과 기준값을 찾고 하위 그룹을 만든 후 각 하위 그룹에 대한 의사결정나무의 마디를 만든다.(Step 3~ Step4) 이 과정을 더 이상 마디를 나눌 수 없을때까지 혹은 정지규칙에 해당할때까지 반복한다.

범주형 목표 변수 (각 범주에 속하는 빈도에 기초하여 분리, Classification)	연속형 목표 변수 (목표 변수의 평균에 기초하여 분리,  Regression)
Entropy Reduction Gini Reduction Chi-square test	F-test Reduction of variance

*지니 불순도 : 확률의 제곱을 다 더해서 1을 뺀다!

**지니 & 엔트로피 그래프 : 값이 0 에 가까울수록 분류가 잘되어있다.

의사결정나무의 장점 & 단점

 1) 장점
  - 시각화를 통한 쉬운 이해
  - 자료 가공이 거의 필요 없음
  - 수치형 및 범주형 데이터 모두 적용 가능
  - 선형성, 정규성 등의 가정이 필요없는 비모수적 방법
  - 대량 데이터 처리에도 적합

2) 단점
  - 휴리스틱에 근거한 실용적 알고리즘으로 전역최적화를 얻지 못할 수 있음
  - 과적합이 쉽게 발생
  - 자료에 따라 불안정함(특히 적은 자료, Class 수에 비교하여 학습 데이터가 적은 규모이면 높은 분류 에러 발생
  - Feature간의 복잡한 관계를 처리하지 못함
  - 자료가 복잡하면 실행 시간이 급격히 증가

정보이득(Information Gain)

 - 분기 이전 부모 노드의 불순도와 분기 이후 자식 노드의 불순도 차이

https://velog.io/@i-zro/%EC%A4%91%EA%B0%84%EA%B3%A0%EC%82%AC-%EB%8C%80%EB%B9%84

 1) 부모의 지니 불순도를 구한다.
    Yes -> 86 + 52 = 138
    No -> 29 + 33 = 62
  전체 N = 200
    1-((138/200)^2 +(62/200)^2) =  0.4278

  2) C1의 불순도
    Yes -> 86
    No-> 29
  전체 N = 115
 1 - ((86 / 115)^2 + (29/115)^2) = 0.377

  3) C2의 불순도
    Yes = 52
    No = 33
   N = 85
 1 - ((52/85)^2 + (33/85)^2) = 0.475

*Information Gain : 부모의 지니 불순도에서 C1의 불순도, C2의 불순도를 더한값을 빼준다. 이 때 C1의 확률, C2의 확률, P를 곱한 값을 넣어줘야 한다.
 왜 확률 값을 곱하나? 
 -> 그냥 더하면 둘다 같은 영향력으로 값이 계산된다. 두 개의 샘플 데이터가 다르기 때문에 확률을 곱하면 샘플이 많은 쪽엔 힘을 주고, 샘플이 적은쪽엔 힘을 빼줄 수있다. 서로 다른 값을 보정! -> '가중치(Weight)'를 곱해준다.

 4) 확률 계산
 C1의 확률 = 115/200
 C2의 확률 = 85/200

의사결정나무의 과적합

 과적합(Overfitting)
 - 학습데이터에 대해서는 좋은 결과를 내나, 새로운 데이터에 대해서는 정확한 예측을 하지 못하는 것
  1) 학습 데이터가 부족한 경우
  2) 학습 데이터에 잡음이 있는 경우
  3) 학습데이터에 너무 특화되어 있는 상황
 *데이터를 더 넣어서 해결!?

정지규칙(Early Stopping Rule)

 1) 모든 마디가 순수한 상태가 되면 정지
  - 노드의 모든 데이터가 하나의 클래스만 남음(순수도 100%인 경우)

  2) 의사결정나무가 완전히 다 자라기 전에 정지하도록 하여 과적합을 방지하거나 지나치게 긴 실행 시간을 제한할 수 있음
  - 트리의 깊이(depth)가 지정한 값(Max Depth)에 도달
  - 노드의 크기가 지정한 값(Min Instance Per Node)보다 작음
  - 불순도의 감소량이 지정된 값(Min Information Gain)보다 적음
 => 미리 사전에 끊는 방식 **

가지치기(Pruning)

-Post-pruning
  1) 의사결정나무가 끝까지 자라도록 한 후 상향식으로 가지치기 실행
  2) 가지치기 결과로 Generalization error가 개선되면 sub-tree를 마디로 대체
  3) 해당 끝마디의 클래스는 sub-tree내 클래스의 다수결로 결정
** 끝에서부터 가지를 치면서 모델을 단순화한다, 모델을 단순화하며 자를때마다 Pruning성능을 체크!
***끝에서부터 자르기때문에 순수도는 떨어질 수 있다. (데이터가 섞일 순 있다.) -> 많은쪽으로 결정

중요 Variables

 - 트리 상단의 변수가 하단보다 중요(그러나 반드시 상단의 변수가 다 중요한것은 아님)
 - 자주 사용되는것
 - 혼잡도 개선 효과가 높은 것.