4주차_5장_트리_알고리즘_윤서환.md

트리 알고리즘(5-1) - 4주차

5-1까지 내용을 정리함을 서두에 밝힙니다.
책 내용에서 보다 깊이 있게 다루면 좋을 요소 위주의 정리를 진행했습니다. 따라서 책 전체 내용의 기술되어 있지 않을 수 있습니다. 궁금한 사항이나, 잘못된 부분이 있다면, 언제든 issue에 의견을 남겨주시면 감사하겠습니다. 해당 내용은 기계학습 - 이상민 교수님자료와 핸즈온 머신러닝 3판을 참고하여 만들었습니다.

CART 알고리즘

CART는 DT를 구성하는 알고리즘 중 하나입니다. 사실 저희가 생각하는 DT는 다양한 방식으로 구현이 가능합니다. 그 중, 가장 대중적으로 사용되며 sklearn에서도 채택하고 있는 알고리즘이 바로 CART입니다. 그렇다면 왜 CART를 사용할까요? 그 이유는 아래와 같습니다.

재귀적인 분리(Recursive partitioning)

• 데이터가 같은 파트에 속하는 데이터의 균질성(homogeneity)이 최대가 되도록 반 복적으로 두 node로 분리
• 학습데이터(Training data)에 대해 100% accuracy로 적합(fitting) 할 수 있음
  
  

가지치기 (Pruning the tree)

• 과적합(overfitting)의 방지를 위해 끝자락 가지들을 잘라냅니다. (규칙을 제거한다.)
• 학습데이터 분리 100% accuracy는 곧 overfit을 의미하기 때문에, 일반화 성능 (generalization)을 높이기 위해서 반드시 pruning을 수행해야 함

즉, 위와 같은 핵심적인 아이디어로 인해 CART를 현재까지도 가장 보편적으로 사용하고 있습니다. 그렇다면, DT만의 장점은 무엇일까요? 바로 직관적입니다. 대부분의 알고리즘은 하나의 rule을 도출하기 굉장히 어렵습니다. 그러나 DT는 node를 나누는 과정에서 명확한 규칙이 존재하기 때문에 보다 사람이 받아들이기 굉장히 편합니다. 또 categorical feature에 대한 전처리도 필요없기 때문에 아직까지도 많이 사용되는 알고리즘 입니다.