가지치기는 의사 결정 트리의 크기를 줄이는 절차입니다. 트리의 크기를 정의하거나 전력을 거의 지원하지 않는 트리 영역을 제거하여 과적합의 위험을 줄일 수 있습니다. 가지치기는 노이즈나 이상치로 인해 훈련 정보의 이상을 따르는 가지들을 잘라내어 지원하고, 트리의 일반화 효율을 높이는 방식으로 원래 트리를 지원한다.
다양한 방법은 일반적으로 가장 신뢰할 수 없는 부서를 삭제하기 위해 통계적 측정을 사용하므로 자주 더 빠른 분류와 독립적인 테스트 데이터를 적절하게 분류하는 트리의 기능이 향상됩니다.
다음과 같은 나무 가지치기에 대한 두 가지 접근 방식이 있습니다 -
사전 가지치기 접근
사전 가지치기 접근 방식에서 트리는 초기에 구성을 통해 "가지치기"됩니다(예:제공된 노드에서 훈련 샘플의 하위 집합을 더 이상 나누거나 분할하지 않기로 결정). 정지하면 노드가 리프로 바뀝니다. 리프는 하위 집합 샘플 간의 가장 일반적인 클래스 또는 해당 샘플의 확률 분포에 영향을 줄 수 있습니다.
나무를 만들 때 통계적 유의성, x2, 정보 이득 등을 포함한 측정값을 사용하여 분할의 관대함을 만들 수 있습니다. 노드에서 샘플을 분할하면 분할이 미리 지정된 임계값 아래로 떨어질 수 있는 경우 지정된 하위 집합의 분할이 중지됩니다. 적절한 임계값을 선택하는 데 문제가 있습니다. 임계값이 높으면 트리가 지나치게 단순화될 수 있고 임계값이 낮으면 단순화가 거의 이루어지지 않을 수 있습니다.
가지치기 후 접근
가지치기 후 접근 방식은 "완전히 자란" 나무에서 가지를 제거합니다. 트리 노드는 분기를 제거하여 정리됩니다. 가격 복잡성 가지치기 알고리즘은 가지치기 후 접근 방식의 한 예입니다. 정리된 노드는 리프로 바뀌고 이전 분기 사이에서 가장 일반적인 클래스로 레이블이 지정됩니다.
트리의 각 비리프 노드에 대해 알고리즘은 해당 노드의 하위 트리가 단축된 경우 나타날 수 있는 예상 오류율을 계산합니다. 다음으로, 노드가 가지치기되지 않았을 때 나타나는 예상 오류율은 각 가지에 대한 관측치의 차원에 따른 가중치로 연결된 각 가지에 대한 오류율을 사용하여 계산된다. 노드 가지치기가 더 높은 예상 오류율로 이어지면 하위 트리가 유지됩니다. 따라서 정리됩니다.
점점 더 많이 제거되는 트리 세트를 생성한 후, 독립적인 테스트 세트가 각 트리의 효율성을 추정할 수 있습니다. 예상 오류 비용을 줄이는 의사 결정 트리가 선호됩니다.