Decision Tree 플루닝

프루닝 전과 후

프루닝은 머신러닝 및 검색 알고리즘의 데이터 압축 기술입니다.인스턴스를 분류하기 위해 중요하지 않고 장황한 트리 섹션을 삭제함으로써 의사결정 트리의 크기를 줄입니다.플루닝은 최종 분류기의 복잡성을 줄여 과적합 감소를 통해 예측 정확도를 향상시킵니다.

의사결정 트리 알고리즘에서 발생하는 질문 중 하나는 최종 트리의 최적 크기입니다.너무 큰 트리는 교육 데이터를 과적합하고 새 표본에 제대로 일반화하지 못할 위험이 있습니다.작은 트리는 표본 공간에 대한 중요한 구조 정보를 캡처하지 못할 수 있습니다.단, 추가 노드를 1개 추가하면 오류가 대폭 줄어들지 여부를 알 수 없기 때문에 트리 알고리즘이 언제 정지해야 하는지 알 수 없습니다.이 문제를 수평 효과라고 합니다.일반적인 전략은 각 노드에 소수의 인스턴스가 포함될 때까지 트리를 키운 후 플루닝을 사용하여 추가 ^[1]정보를 제공하지 않는 노드를 삭제하는 것입니다.

가지치기는 교차 검증 세트로 측정되는 예측 정확도를 감소시키지 않고 학습 트리의 크기를 줄여야 한다.트리 프루닝에는 성능 최적화에 사용되는 측정값에 차이가 있는 많은 기술이 있습니다.

기술

플루닝 프로세스는 두 가지 유형(프루닝 전 및 후)으로 나눌 수 있습니다.

사전 프루닝 절차는 유도 알고리즘의 중지() 기준을 대체하여 교육 세트의 완전한 유도를 방지합니다(예: max).트리 깊이 또는 정보 게인(Attr)> 최소 게인.사전 가지치기 방법은 전체 세트를 유도하지 않고 처음부터 트리가 작기 때문에 더 효율적인 것으로 간주됩니다.프리프루닝 방법은 공통적인 문제인 수평선 효과를 공유합니다.이는 정지() 기준에 의한 바람직하지 않은 유도 조기 종료로 이해해야 한다.

가지치기(또는 가지치기)는 트리를 단순화하는 가장 일반적인 방법입니다.여기서는 노드 및 서브트리를 리프(leaf)로 대체하여 복잡성을 줄입니다.가지치기는 크기를 크게 줄일 수 있을 뿐만 아니라 보이지 않는 물체의 분류 정확도를 향상시킬 수 있습니다.열차 세트에 대한 할당의 정확도가 저하될 수 있지만, 트리의 분류 속성의 정확도는 전반적으로 증가합니다.

절차는 트리의 접근방식(상하향 또는 상향)에 따라 구별된다.

상향식 프루닝

이러한 순서는 트리의 마지막 노드(최저점)에서 시작합니다.재귀적으로 위쪽으로 이동하면 각 노드의 관련성이 결정됩니다.분류에 대한 관련성이 지정되지 않은 경우 노드가 삭제되거나 리프(leaf)로 대체됩니다.이 방법에서는 관련된 서브트리가 손실되지 않는다는 장점이 있습니다.이러한 방법에는 Reduced Error Pruning(REP), Minimum Cost Complexity Pruning(MCCP), Minimum Error Pruning(MEP) 등이 있습니다.

톱다운 프루닝

상향식 방식과 달리 이 방법은 트리의 루트에서 시작합니다.아래 구조에 따라 노드가 n개 항목의 분류에 관련된지를 판정하는 관련성 체크를 실시한다.내부 노드에서 트리를 플루닝하면 (관련성에 관계없이) 서브트리 전체가 폐기될 수 있습니다.이러한 대표 중 하나가 비관적 오류 가지치기(PEP)로, 보이지 않는 항목에서 상당히 좋은 결과를 가져옵니다.

프루닝 알고리즘

에러 프루닝의 삭감

플루닝의 가장 간단한 형태 중 하나는 에러 플루닝의 감소입니다.왼쪽부터 시작하여 각 노드가 가장 많이 사용되는 클래스로 교체됩니다.예측 정확도가 영향을 받지 않으면 변경 내용이 유지됩니다.에러 플루닝의 감소는 다소 순진하지만, 심플함과 스피드가 향상됩니다.

비용 복잡성 해소

코스트 복잡도 플루닝에 의해 일련의 $T_{0}\dots T_{m}$ T $T_{0}\dots T_{m}$ … T $T_{0}\dots T_{m}$ { $displaystyle T_{0}$ \ $dots$ T_ ${m}$ 이 $T_{0}\dots T_{m}$ 생성됩니다. $T_{0}$ 서 T $T_{0}$ 0 { $displaystyle$ T_ ${0}$ 은 $T_{0}$ 초기 $T_{m}$ 이고 $T_{m}$ m { $displaystyle$ T_ ${m}$ 은 $T_{m}$ 루트만입니다. $스텝$ i $displaystyle$ $i$ 에서는 $i-1$ i - $1$ 에서 $i-1$ 서브트리를 제거하고 트리 구축 알고리즘에서 선택한 값을 가진 리프 노드로 대체하여 트리를 만듭니다.삭제되는 서브트리는 다음과 같이 선택됩니다.

데이터 $세트$ S {\ $displaystyle$ S $}$ 에 $S$ 대한 $트리$ T {\ $displaystyle$ T $}$ 의 $T$ 오류율을 err $\operatorname {err} (T,S)$ ( $\operatorname {err} (T,S)$ , $\operatorname {err} (T,S)$ ) { $displaystyle \operatorname {err$ } $\operatorname {err} (T,S)$ ( $T$ , $S$ )로 $\operatorname {err} (T,S)$ 합니다.
에러 ${\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}$ 를 ${\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}$ 하는 $(\displaystyle$ t $t$ ${\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}$ - ${\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}$ - 에러( ${\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}$ S)는 ${\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}$ ${\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}$ prune $T$ ${\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}$ - 를 남깁니다.{ $displaystyle {err} (\operatorname$ { $prune} (\T),$ $ratorname {leaves}(\operatorname {prune}(T,t))\right\vert }}$ 이 ${\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}$ (가) 삭제 대상으로 선택되었습니다.

The function $\operatorname {prune} (T,t)$ defines the tree obtained by pruning the subtrees $t$ from the tree $T$ . Once the series of trees has been created, the best tree is chosen by generalized accuracy as measured by a training set or cross-validation.

「」를 참조해 주세요.

레퍼런스

Pearl, Judea (1984). Heuristics. Addison-Wesley.
Mansour, Y. (1997). "Pessimistic decision tree pruning based on tree size". Proc. 14th International Conference on Machine Learning. pp. 195–201.
Breslow, L. A.; Aha, D. W. (1997). "Simplifying Decision Trees: A Survey". The Knowledge Engineering Review. 12 (1): 1–47. doi:10.1017/S0269888997000015.
Quinlan, J. R. (1986). "Induction of Decision Trees". Machine Learning. Kluwer Academic Publishers. 1: 81–106. doi:10.1007/BF00116251.

^ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2001). The Elements of Statistical Learning. Springer. pp. 269–272. ISBN 0-387-95284-5.

추가 정보

외부 링크

[tib-1] Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2001). The Elements of Statistical Learning. Springer. pp. 269–272. ISBN 0-387-95284-5.

[1]

Search

Decision Tree 플루닝

네임스페이스

더

목차