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

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

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

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

  ㅇ 통상, 이진트리 형식을 갖춤
     - 사실상, 모든 트리가 이진 트리로 변환 가능

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


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

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