성장 트리 성장

모든 지도 학습 머신러닝 모델과 마찬가지로 결정 트리는 일련의 학습 예시를 가장 잘 설명하도록 학습됩니다. 결정 트리의 최적 학습은 NP-난해 문제입니다. 따라서 일반적으로 최적은 아니지만 최적에 가까운 결정 트리를 제공하는 만들기 쉬운 학습 알고리즘인 휴리스틱을 사용하여 학습이 이루어집니다.

결정 트리를 학습하는 데 사용되는 대부분의 알고리즘은 탐욕스러운 분할 정복 전략을 사용합니다. 이 알고리즘은 단일 노드 (루트)를 만들고 재귀적으로 탐욕스럽게 결정 트리를 확장합니다.

각 노드에서 가능한 모든 조건이 평가되고 점수가 매겨집니다. 알고리즘은 '가장 좋은' 조건, 즉 점수가 가장 높은 조건을 선택합니다. 지금은 점수가 태스크와 관련된 측정항목이며 이 측정항목을 최대화하도록 조건이 선택된다는 사실만 알아두세요.

예를 들어 이 과정의 뒷부분에 나오는 코드 예시에서 사용되는 Palmer Penguins 데이터 세트에서 대부분의 아델리펭귄과 턱끈펭귄은 부리 길이가 16mm를 초과하는 반면 대부분의 젠투펭귄은 부리가 더 작습니다. 따라서 bill_length_mm ≥ 16 조건은 젠투 펭귄을 거의 완벽하게 예측하지만 아델리 펭귄과 턱끈펭귄을 구분할 수는 없습니다. 알고리즘은 이 조건을 선택할 가능성이 높습니다.

하나의 조건이 두 개의 리프로 이어집니다. 조건은 'bill_length_mm >= 16'입니다.
그렇다면 'Adelie or Chinstrap'(애드리 또는 턱끈펭귄)입니다.  그렇지 않으면 리프는 'Gentoo'입니다.

그림 7. 나무를 키우는 첫 번째 단계입니다.

 

그런 다음 알고리즘은 두 하위 노드에서 독립적으로 재귀적으로 반복됩니다. 충족하는 조건이 없으면 노드가 리프가 됩니다. 리프 예측은 예시에서 가장 대표적인 라벨 값으로 결정됩니다.

알고리즘은 다음과 같습니다.

def train_decision_tree(training_examples):
  root = create_root() # Create a decision tree with a single empty root.
  grow_tree(root, training_examples) # Grow the root node.
  return root

def grow_tree(node, examples):
  condition = find_best_condition(examples) # Find the best condition.

  if condition is None:
    # No satisfying conditions were found, therefore the grow of the branch stops.
    set_leaf_prediction(node, examples)
    return

  # Create two childrens for the node.
  positive_child, negative_child = split_node(node, condition)

  # List the training examples used by each children.
  negative_examples = [example for example in examples if not condition(example)]
  positive_examples = [example for example in examples if condition(example)]

  # Continue the growth of the children.
  grow_tree(negative_child, negative_examples)
  grow_tree(positive_child, positive_examples)

특정 결정 트리를 학습하는 단계를 자세히 살펴보겠습니다.

1단계: 루트를 만듭니다.

물음표가 있는 노드

2단계: 노드 1을 성장시킵니다. 'x1 ≥ 1' 조건이 발견되었습니다. 두 개의 하위 노드가 생성됩니다.

정의되지 않은 두 노드로 연결되는 루트 노드

3단계: 노드 2를 성장시킵니다. 충족하는 조건이 없습니다. 따라서 노드를 리프로 만듭니다.

정의되지 않은 두 노드로 연결되는 루트 노드

4단계: 노드 3을 성장시킵니다. 'x2 ≥ 0.5' 조건이 발견되었습니다. 두 개의 하위 노드가 생성됩니다.

루트 노드, 조건, 리프 3개

결정 트리를 확장하는 다른 방법도 있습니다. 많이 사용되는 대안은 분할 정복 전략을 사용하는 대신 전역적으로 노드를 최적화하는 것입니다.

YDF 코드
YDF에서는 기본적으로 위에서 설명한 '탐욕스러운 분할 정복' 알고리즘을 사용하여 결정 트리가 확장됩니다. 또는 growing_strategy="BEST_FIRST_GLOBAL" 매개변수를 사용하여 전 세계 성장을 사용 설정할 수 있습니다. 자세한 내용은 문서를 참고하세요.

입력 지형지물의 수와 유형에 따라 특정 노드에 가능한 조건의 수는 엄청나게 많을 수 있으며 일반적으로 무한대입니다. 예를 들어 임곗값 조건 featureit가 주어지면 tR 의 가능한 모든 임곗값 조합은 무한합니다.

최적의 조건을 찾는 루틴을 분할자라고 합니다. 가능한 조건을 많이 테스트해야 하므로 스플리터는 결정 트리를 학습할 때 병목 현상입니다.

스플리터가 최대화하는 점수는 태스크에 따라 다릅니다. 예를 들면 다음과 같습니다.

  • 정보 이득지니 지수 (둘 다 나중에 설명)는 일반적으로 분류에 사용됩니다.
  • 평균 제곱 오차는 일반적으로 회귀에 사용됩니다.

여러 분할 알고리즘이 있으며 각 알고리즘은 다음을 다르게 지원합니다.

  • 특성 유형(예: 숫자, 범주형, 텍스트)
  • 작업(예: 이진 분류, 다중 클래스 분류, 회귀)
  • 조건 유형입니다(예: 기준점 조건, 세트 내 조건, 경사 조건).
  • 정규화 기준(예: 임곗값 조건의 정확한 또는 근사적인 스플리터)

또한 메모리 사용량, CPU 사용량, 계산 분산 등과 관련하여 다른 절충점을 가진 등가 분할기 변형이 있습니다.

YDF 코드
YDF에서는 자동으로 감지된 (또는 수동으로 지정된) 특성 유형, 하이퍼파라미터, 각 스플리터의 예상 속도에서 스플리터가 암시적으로 선택됩니다 (학습 중에 YDF는 소형 모델을 실행하여 각 후보 스플리터의 속도를 예측함).