시험 직전 요약장

현재 노드 t에서 후보 변수와 분할점을 모두 비교한 뒤 불순도 또는 오차 감소가 가장 큰 후보를 선택한다. 자식 노드에서 같은 절차를 반복한다.

훈련 노드→후보 분할 생성 → 각 후보의 가중 감소량 계산→현재 최선 분할 선택 → 자식 노드에서 반복 → 정지·가지치기

수치형 변수의 후보는 보통 정렬된 서로 다른 값 사이의 임곗값에서 만든다. 범주형 변수는 범주 집합 분할, 순서화 또는 원-핫 인코딩 등 구현에 따라 처리법이 다르다. 결측값·학습 때 없던 범주의 처리도 라이브러리마다 다르므로 사용 구현을 확인한다.

이 선택은 현재 노드에서의 국소 최적이다. 첫 분할을 나중에 되돌려 모든 가능한 나무를 전수 탐색하지 않으므로 전체적으로 가장 좋은 나무가 보장되지는 않는다. 감소량이 같은 후보의 처리도 구현과 설정에 따라 달라질 수 있다.

시험에서는 알고리즘 이름보다 “분류·회귀 가능 여부, 분할 기준, 이진·다지 분할, 가지치기 방식”의 조합을 확인한다.

부모 노드에 양성 6개, 음성 4개가 있고, 분할 뒤 왼쪽은 (양성 5, 음성 0), 오른쪽은 (양성 1, 음성 4)라고 하자.

따라서 가중 자식 Gini는 0.16, 감소량은 0.48-0.16=0.32다. 자식 크기가 다르면 단순 평균이 아니라 반드시 nL/n, nR/n으로 가중한다.

정보이득은 엔트로피의 같은 형태의 감소량이다. 범주 수나 후보 분할점이 많은 변수는 우연히 큰 감소를 만들 기회가 많다. 정보이득을 쓰는 알고리즘에서는 이를 완화하기 위해 분할정보로 나눈 이득비(gain ratio)를 사용하기도 한다.