Decision Tree, Decoding Tree   결정 트리, 결정도, 디코딩 트리

1. 결정 트리 (Decision Tree), 디코딩 트리 (Decoding Tree) 이란?

  ㅇ 개요
     - 각 노드 마다 하나의 결정(Yes/No 등)을 나타내고,
     - 이 결정에 따르는 가능한 출력들을, 자손들(부 트리,subtree)로써 갖으며,
     - 말단 노드(Leaf Node)에 이르면, 최종 결정을 하게되는 (결과값을 갖게되는) 트리

  ㅇ 고려 사항  :  (흔련 집합을 통해, 결정 트리를 만들 때 유념해야 할 것)
     - 각 노드 마다 결정(판단) 조건(질문)을 어떻게 만들 것인가?
     - 각 노드 마다 몇 개의 분기(가지)를 갖게 할 것인가?
     - 언제 멈출 것인가?
     - 매 잎(leaf) 노드 마다 어느 부류로 할당(결정)할 것인가?

  ㅇ 특징
     - 통상, 이진트리 형식을 갖춤
        . 사실상, 모든 트리가 이진 트리로 변환 가능
     - 선형 모델과 달리 복수의 비교식(분기)을 갖음
        . 보다 일반적이고 유연성 있음

  ㅇ 용도
     - 기계 학습에서, 분류기(Classifier)로써 활용
        . 컴퓨터를 이용하여 분기(Yes/No 결정) 질문을 자동으로 만들어냄
     - 결정 트리 구조를 통해, 어떤 규칙이 내재해 있는가를 알 수 있는 등

  ㅇ 例) 예/아니오로 20번 이내로 답하며, 정답을 맞추는(최종 결정을 하게 되는), 스무고개 놀이


2. 코드를 만들어가는 단순한 결정 트리의 例)

  ㅇ 하나의 초기 상태와 심볼 수 만큼의 결정 상태를 갖음
  ㅇ 매 분기점(branch) 마다 단일 조건으로 검사를 함
  ㅇ 결정 상태(leaf)에 이르면 심볼을 결정하게됨.
     
     -  소스 알파벳 S = {s1,s2,s3,s4}
     -  코드 알파벳 C = {0,1}
     *  코드 심볼의 결정 
        . s1 = 0, s2 = 10, s3 = 110, s4 = 111