4. Decision Tree

 

 

 

의사결정 트리 분류기 (Decision Tree Classifier)

• 의사결정 트리 분류기는 트리 모양의 순차형 다이어그램을 통해 주어진 데이터를 분류.
  
  • 트리의 루트부터 시작해서 모든 중간 노드들은 의사 결정 사항 (조건)
  • 트리의 맨 끝에 있는 리프 노드는 의사 결정 사항에 따른 최종 결과
• 의사결정 트리 분류기의 동작은 의사결정 트리를 생성하는 학습 단계와 생성된 의사결정 트리에 따라 주어진 데이터를 분류하는 분류 단계로 나눠 볼 수 있다.
  • 대표적인 트리 생성 알고리즘 : ID3, C4.5, CART, CHAID
• 예시 

• 의사결정 트리는 데이터를 재귀적으로 파티셔닝하여 생성.

파티셔닝의 예시.

---

CART (Classification and Regression Tree)

• 학습데이터를 사용하여 각 노드를 왼쪽 자식 노드와 오른쪽 자식 노드로 분할해 가며 트리를 생성.

• 기본적으로는 클래스 별로 데이터를 잘 가를 수 있으면 좋은 분할.
• 하지만 하나의 피처와 해당 값으로 전체 데이터를 클래스 별로 완벽하게 가를 수는 없기 때문에, 단계적으로 분할 조건들을 탐색해 나가야 한다.
• CART는 각 노드에서 분할을 위한 피처와 해당 피처의 값의 조합을 탐욕적(Greedy) 방식으로 탐색
  • Global Optima가 아니라 Local Optima를 우선 고려.
• 작동 과정
  • 분할 
    • 각 노드에서 분할을 위한 피처와 해당 피처의 값의 조합을 탐욕적(Greedy) 방식으로 탐색
    • Global Optima가 아니라 Local Optima를 우선 고려.
  • 정지 : 분할 과정은 다음과 같은 조건들이 만족되면 중지
    • 분할 후 만들어질 노드의 샘플 수가 일정 수준 이하일 때
    • 트리의 깊이가 일정 수준 이상일 때 -> 오버피팅을 피하기 위한 조치
  • 분할되지 않은 마지막 노드들에 클래스 레이블을 할당하는데, 각 노드에 있는 데이터의 클래스 중 가장 다수 클래스를 할당.
• 이를 위해서는 어떤 피처와 해당 값을 선택했을 때 데이터를 클래스 별로 얼마나 잘 분할해 내는지 평가할 수 있는 값이 필요하다. -> 트리 분할 척도 (지니계수, 정보이득)

---

트리 분할 측정 척도

• 각 피처와 해당 값들이 가장 잘 조합된 결과를 선택하기 위해 분할이 얼마나 잘 이루어졌는지를 측정하는 척도
• 대표적인 트리 분할 츨정 척도
  • 지니 계수 (Gini Impurity)
  • 정보 이득 (Information Gain), Entropy

---

지니 계수 (Gini Impurity)

• 데이터가 클래스 별로 고르게 분포되어 있는지, 아니면 특정 클래스에 편중되어 분포되어 있는지 나타냄
  
  • 편중될수록 지니 계수가 작고, 고를수록 크다.

• 두 개의 클래스가 존재할 때,
  
  • 모든 데이터가 한 클래스에만 속한다면 지니계수는 1 - (1*1 + 0*0) = 0
  • 두 클래스가 반반씩 속한다면 지니계수는 1 - (0.5 * 0.5 + 0.5 * 0.5) = 0.5
• 분할한 결과로 만들어진 자식 노드들 각각에 대해서 지니 계수를 구하고 가중평균하여 분할 결과를 측정.
  • 지니 계수가 작을수록 클래스를 편중해서 잘 갈라냈음을 의미.

---

정보 이득

• 트리 분할 후 얼마나 순도가 더 좋아졌는지 평가한다.
  •  = 트리 분할을 통해 불확실성이 얼마나 줄어드는지를 축정한다.
• 불확실성이 높다는 것은 클래스 별로 고르게 분포되어 있다는 것.
• 모든 클래스에 똑같은 비율로 데이터가 존재할 때, 여기서 어떤 데이터를 임의로 뽑는다면 이 데이터가 어떤 클래스에 속할지 불확실하다.
• 반대로, 특정 클래스에 편중되어 있으면 데이터의 클래스에 대한 불확실성이 낮다.
• 정보 이득은 트리 분할 전 후의 엔트로피 값 차이로 계산된다.

엔트로피

• 2개의 클래스가 존재할 때,
  
  • 모든 데이터 한 클래스에만 속한다면 엔트로피는 -( 1 * log2(1) + 0 ) = 0
  • 두 클래스에 반반씩 속한다면 엔트로피는 -( 0.5 * log2(0.5) + 0.5 * log2(0.5) ) = 1
• 정보 이득은 트리 분할 전 (부모 노드) 엔트로피와 트리 분할 수 (자식 노드들) 엔트로피 값의 차이로 정의
  • 자식 노드들의 엔트로피 값은 지니 계수와 같은 방식으로 가중 평균하여 계산.

정보 이득