모든 지도 학습 머신러닝 모델과 마찬가지로 결정 트리는 일련의 학습 예시를 가장 잘 설명하도록 학습됩니다. 결정 트리의 최적 학습은 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" 매개변수를 사용하여 전 세계 성장을 사용 설정할 수 있습니다.
자세한 내용은
문서를 참고하세요.
입력 지형지물의 수와 유형에 따라 특정 노드에 가능한 조건의 수는 엄청나게 많을 수 있으며 일반적으로 무한대입니다. 예를 들어 임곗값 조건 가 주어지면 의 가능한 모든 임곗값 조합은 무한합니다.
최적의 조건을 찾는 루틴을 분할자라고 합니다. 가능한 조건을 많이 테스트해야 하므로 스플리터는 결정 트리를 학습할 때 병목 현상입니다.
스플리터가 최대화하는 점수는 태스크에 따라 다릅니다. 예를 들면 다음과 같습니다.
여러 분할 알고리즘이 있으며 각 알고리즘은 다음을 다르게 지원합니다.
- 특성 유형(예: 숫자, 범주형, 텍스트)
- 작업(예: 이진 분류, 다중 클래스 분류, 회귀)
- 조건 유형입니다(예: 기준점 조건, 세트 내 조건, 경사 조건).
- 정규화 기준(예: 임곗값 조건의 정확한 또는 근사적인 스플리터)
또한 메모리 사용량, CPU 사용량, 계산 분산 등과 관련하여 다른 절충점을 가진 등가 분할기 변형이 있습니다.