You Nicholas

가고 가고 또 가면 알게되고, 행하고 행하고 또 행하게 되면 이루게 된다.

1 분 소요

Decision Tree

  • 결정 트리라고도 불린다.

    비용함수를 최소로 하는 특성과 그 값에 대한 옳고 그름의 답을 통해 데이터를 분할하는 알고리즘이다.

트리 구조

  • node(노드)
    • root(루트)

      부모가 없는 노드로 최초의 노드이다.

    • internal(내부)

      단말 노드가 아닌 노드들을 의미한다. 대개는 중간에 존재한다.

    • leaf(단말)

      자식이 없는 노드로 ‘잎 노드’라고도 불린다.

    • Parent(부모)

      Sub-tree에서 상위에 위치해있는 노드이다. 자식이 존재하는 노드이다.

    • Chile(자식)

      Parent 노드 밑에 이어지는 노드로서 부모가 좋재하는 노드이다.

    • Sibiling(형제)

      같은 부모를 가지고 있는 노드이다.

  • edge(엣지)

    노드와 노드를 연결하는 선을 의미한다.

장점

  1. 시각화가 가능하기에 해석이 직관적이다.
  2. EDA 과정이 많이 필요하지 않다.
  3. 상관관계를 트리의 분기과정에서 확인이 가능하다.
  4. Multi-output(다중 출력)이 가능하여, 다중 출력이 필요한 문제 해결이 가능하다.

단점

  1. 제약사항이 없는 유연한 모델이기에 과적합 가능성이 있다.
  2. 데이터 변동으로 다수의 트리가 생겨 불안정할 수 있다.
  3. 주어진 데이터에 대해서 분할하기에 분할된 근사치에 예측값 반환하기에 외삽이 어렵다.

종류

  1. Binary Tree
    • 이진트리라고 불리우며, 트리의 가장 기본적인 형태이다.
    • 각 노드가 최대 2개의 자식을 가지고 있다.
    • 단, 모든 트리가 이진으로 이루어지지 않았다.
  • 이진트리의 순회방식
    1. in-order traversal

      중위 순회

      왼쪽 가지 -> 현재 노드 -> 오른쪽 가지

    2. pre-order traversal

      전위 순회

      현재 노드 -> 왼쪽 가지 -> 오른쪽 가지

    3. post-order traversal

      후위 순회

      왼쪽 가지 -> 오른쪽 가지 -> 현재 노드

  1. Heap
  • Min Heap

    최소힙

    1. 트리의 마지막 단계에서 오른쪽을 뺀 나머지 부분이 가득 채워진 완전 이진트리
    2. 노드의 원소가 자식들의 원소보다 작다.
    3. 부모 노드가 자식 노드보다 크거나 같은 완전 이진트리

  • Max Heap

    최대힙

    1. 원소가 내림차순으로 정렬되어 있다는 점
    2. 각 노드의 원소가 자식들보다 크다. 3. Trie
  • Prefix Tree(접두사 트리)
    1. n차 트리의 다른 버젼이다.
    2. 각 노드에 문자를 저장하는 자료구조이다.
    3. 접두사를 빠르게 찾아보기 위한 방식중에 하나로, 모든 언어를 저장해 놓은 방식이다.
    4. 유효한 단어 집합을 이용하면 트라이를 통해 다수의 문제를 최적화할 수 있다.

참고