모든 지도 머신러닝 모델과 마찬가지로 결정 트리는 일련의 학습 예를 가장 잘 설명하도록 학습됩니다. 결정 트리에 대한 최적의 학습은 NP-난해 문제입니다. 따라서 학습은 일반적으로 휴리스틱을 사용하여 이루어집니다. 휴리스틱은 최적화되지는 않지만 최적의 결정 트리에 가까운 최적의 결정 트리를 제공하는, 생성하기 쉬운 학습 알고리즘입니다.
결정 트리를 학습시키는 데 사용되는 대부분의 알고리즘은 탐욕적인 분할 및 정복 전략을 통해 작동합니다. 알고리즘은 단일 노드 (루트)를 만드는 것으로 시작해서 재귀적이고 탐욕적으로 결정 트리를 확장합니다.
각 노드에서 가능한 모든 조건을 평가하고 점수를 매깁니다. 알고리즘이 '최적'의 조건, 즉 점수가 가장 높은 조건을 선택합니다. 지금은 점수가 작업과 상관관계가 있는 측정항목이며 해당 측정항목을 최대화하기 위한 조건이 선택된다는 것만 알아두세요.
예를 들어 이 과정의 뒷부분에 나오는 코드 예에 사용된 Palmer Penguins 데이터 세트에서 대부분의 아델리 펭귄과 친스트랩 펭귄은 지표 길이가 16mm 이상이지만 대다수 젠투 펭귄은 부피가 더 작습니다. 따라서 bill_length_mm ≥ 16 조건은 젠투 펭귄을 거의 완벽히 예측하지만 아델리와 친스트랩을 구분할 수는 없습니다. 알고리즘이 이 조건을 선택할 가능성이 높습니다.
그림 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' 조건이 발견되었습니다. 두 개의 하위 노드가 생성됩니다.
결정 트리를 성장시키는 다른 방법도 있습니다. 널리 사용되는 대안은 분할 정복 전략을 사용하는 대신 전역적으로 노드를 최적화하는 것입니다.
growing_strategy="BEST_FIRST_GLOBAL" 매개변수를 사용하여 글로벌 성장을 사용 설정할 수 있습니다.
자세한 내용은
문서를 참조하세요.
입력 특성의 수와 유형에 따라 특정 노드에서 가능한 조건의 수는 매우 많고 일반적으로 무한할 수 있습니다. 예를 들어 임곗값 조건 $\mathrm{feature}_i \geq t$의 경우 $t \in \mathbb{R}$ 에 대해 가능한 모든 기준값의 조합은 무한합니다.
최적의 상태를 찾는 루틴을 스플리터라고 합니다. 가능한 여러 조건을 테스트해야 하므로 스플리터는 결정 트리를 학습시킬 때 병목 현상을 일으키는 역할을 합니다.
분할에 의해 최대화되는 점수는 작업에 따라 다릅니다. 예를 들면 다음과 같습니다.
여러 스플리터 알고리즘이 있으며 각 알고리즘은 다음을 다양하게 지원합니다.
- 특성 유형(예: 숫자, 범주형, 텍스트)
- 태스크, 예: 이진 분류, 다중 클래스 분류, 회귀 모델
- 조건 유형(예: 임계값 조건, 설정 조건, 사선 조건)
- 정규화 기준(예: 임곗값 조건의 정확한 또는 근사치 분할기)
또한 동일한 스플리터 변형이 있으며 메모리 사용량, CPU 사용량, 계산 분산 등과 관련하여 장단점이 다릅니다.